Datastrukturuppsats (1)
1. Flervalsfrågor (2 poäng per fråga, totalt 20 poäng)
1. De gemensamma egenskaperna hos stackar och köer är ( ).
A. Tillåt endast insättning och borttagning av element vid ändpunkten
B. Alla först in, sista ut
C. Allt handlar om först in, först ut
D. Det finns ingen gemensam grund
2. Kön som lagras på ett länkat sätt infogas när insättningsoperationen utförs ( ).
A. Endast huvudpekaren modifieras B. Huvud- och svanspekarna måste modifieras
C. Modifiera endast svanspekaren D. Huvud- och svanspekarna kan behöva modifieras
3. Vilken av följande datastrukturer är en icke-linjär struktur? ( )
A. Kö B. Stack C. Linjär tabell D. Binära träd
4. Om det finns en tvådimensionell array A[m][n], under antagandet att A[0][0] lagras vid 644 (10), och A[2][2] lagras vid 676 (10), upptar varje element ett utrymme, där är A[3][3][3](10) lagrad? Fotnot (10) anger att den uttrycks i decimal.
A.688 B.678 C.692 D.696
5. Träd används bäst för att representera ( ).
A. Ordnade dataelement B. Oordnade dataelement
C. Data med förgrenade hierarkiska relationer mellan elementen D. Data utan koppling mellan elementen
6. Det maximala antalet noder i det k:te lagret i det binära trädet är ( ).
A.2k-1 B.2K+1 C.2K-1 D. 2k-1
7. Om det finns en ordnad tabell med 18 element lagrad i en endimensionell array A[19], placeras det första elementet i A[1], och nu utförs en binär sökning, så är indexet av jämförelsesekvensen för att hitta A[3] ( )
A. 1,2,3 B. 9,5,2,3
C. 9,5,3 D. 9,4,2,3
8. Sortera snabbt filerna med n poster, och det extra lagringsutrymmet som krävs är ungefär detsamma
A. O(1) B. O(n) C. O(1og2n) D. O(n2)
9. För linjära tabeller (7, 34, 55, 25, 64, 46, 20, 10) för hashlagring, om H(K)=K %9 väljs som hashfunktion, finns ( ) element med hashadressen 1.
A.1 B.2 C.3 D.4
10. En ostyrd graf med 6 noder, och grafen bör ha minst ( ) kanter för att säkerställa en sammanhängande graf.
A.5 B.6 C.7 D.8
2. Fyll i luckorna (1 poäng per tom, totalt 26 poäng)
1. Algoritmens kvalitet utvärderas vanligtvis utifrån fyra aspekter: _________, _________, _________ och _________.
2. En algoritms tidskomplexitet är (n3+n2log2n+14n)/n2, och dess storleksordning uttrycks som ________.
3. Om vi antar att den generaliserade tabellen för ett träd representeras som A(C,D(E,F,G),H(I,J)), så är antalet noder i trädet __________, trädets djup är ___________ och graden av trädet är _________.
4. Värdet på suffixformeln 9 2 3 +- 10 2 / - är __________. Suffixformeln som motsvarar den mellersta formeln (3+4X)-2Y/3 är _______________________________.
5. Om ett binärt träd lagras med en länkad lista har varje nod två pekare till vänster barn och höger barn utöver datafältet. I denna lagringsstruktur har det binära trädet med n noder totalt ________ pekarfält, varav ________ pekarfält lagrar adresser och ________________ pekare är tomma pekare.
6. För en riktad graf och en oriktad graf med n noder och E-bar-kanter finns det _______ och ________ kantnoder i dess motsvarande närhetstabell.
7. AOV-nätverket är en ___________________ graf.
8. I en oriktad komplett graf med n noder finns ________ kanter, och i en riktad komplett graf med n noder finns ________ kanter.
9. Om vi antar att en linjär tabell är (12,23,74,55,63,40), om elementen i samma resterande blir en deltabell enligt nyckel % 4-villkoret, är de fyra deltabeller som erhålls ____________________________, ___________________, _______________________ och __________________________.
10. I processen att infoga element i ett B_ träd, om rotnoden i trädet slutligen delas, är höjden på det nya trädet ___________ än den ursprungliga trädets.
11. I processen med heapsortering är tidskomplexiteten för att sålla en grennod ________, och tidskomplexiteten för hela heapsorteringsprocessen är ________.
12. Vid snabbsortering, högsortering och sammanslagningssortering är _________ sortering stabil.
Datastrukturuppsats (2)
1. Flervalsfrågor (24 poäng)
1. Följande beskrivning av linjära tabeller är felaktig ().
(A) Linjära tabeller lagras sekventiellt och måste uppta ett sammanhängande lagringsutrymme
(B) Linjära tabeller är kedjade och tar inte upp ett kontinuerligt lagringsutrymme
(C) Linjära tabeller implementeras med kedjad lagring för att underlätta insättnings- och borttagningsoperationer
(d) Linjära tabeller implementeras med sekventiell lagring för att underlätta insättnings- och borttagningsoperationer
2. Antag att det totala antalet bladnoder i Huffmanträdet är m, och om en binär länkad lista används som lagringsstruktur, finns det totalt ( ) tomma pekfält i Huffmanträdet.
(A) 2m-1 (B)2m (C)2m+1 (D)4m
3. Om huvud- och svanspekarna i den sekventiella loopkön Q[0:M-1] är F respektive R, pekar huvudpekaren F alltid till föregående position för huvudelementet, och svanspekaren R pekar alltid till den nuvarande positionen för svanselementet, så är antalet element i loopkön ( ).
(A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M
4. Om den mellanordningens traverseringssekvens i ett binärt träd är ABCD och den föregående sekvensens traverseringssekvens är CABD, så är sekvensen som erhålls genom att gå genom binära trädet i efterföljande ordning ().
(A) BADC (B)BCDA (C) CDAB (D) CBDA
5. Antag att det finns n noder i en helt oriktad graf, då finns det ( ) kanter i den helt oriktade grafen.
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
6. Antag att det finns 2000 noder i ett binärt träd, då är den minsta höjden för det binära trädet ( ).
(A) 9 (B) 10 (C) 11 (D) 12
7. Antag att det finns n noder i en riktad graf, då finns det ( ) header-noder i närhetstabellen som motsvarar den riktade grafen.
(A) n-1 (B) n (C) n+1 (D) 2n-1
8. Sätt en uppsättning initiala nyckelordssekvenser för posten (5, 2, 6, 3, 8), och resultatet av en snabbsortering baserad på det första postnyckelordet 5 är ( ).
(A) 2,3,5,8,6 (B) 3,2,5,8,6
(C) 3,2,5,6,8 (D) 2,3,6,5,8
2. Fyll i luckorna (24 poäng)
1. För att effektivt kunna tillämpa HASH-uppslagsteknik måste två problem lösas: ____________________ och __________________________.
2. Funktionen för följande programsegment realiserar data x i stacken och kräver att rätt sats fylls i understrecket.
typedefstruct {int s[100]; Int Top; } sqstack;
Void Push (sqstack&stack,int x)
{
om (stack.top==m-1) printf("overflow");
annars {____________________; _________________; }
}
3. Sekvensen som erhålls genom att gå genom det binära sorteringsträdet i mittordningen är en ___________ sekvens (ifylld ordnad eller oordnad).
4. Den värsta tidskomplexiteten för snabbsortering är ___________, och den genomsnittliga tidskomplexiteten är __________.
5. Om antalet noder med graden 0 i ett binärt träd är N0 och nodnumret med grad 1 är N1, så är antalet noder med grad 2 i det binära trädet _________; Om en binär länkad lista används som lagringsstruktur för det binära trädet finns det _______ tomma pekarfält i det binära trädet.
6. Antag att antalet noder och kanter i en viss oriktad graf är n respektive e, och summan av graderna för alla noder är d, då är e = _______.
7. Om den initiala nyckelordssekvensen för posten är (55, 63, 44, 38, 75, 80, 31, 56), så är den initiala heap som fastställs av screeningmetoden ___________________________.
8. Det är känt att adjacenstabellens lagringsstruktur för en riktad graf är följande: Från nod 1 är utgångssekvensen för DFS-genomgång:
, är utgångssekvensen för BFS-genomgång
Datastruktursuppsats (3)
1. Flervalsfrågor (1 poäng per fråga, totalt 20 poäng)
1. Om den binära formen av en datastruktur uttrycks som A=(D,R),D={01,02,03,04,05,06,07,08,09}, R={r},r={<01,02>,<01,03><01,04>,<02,05>,<02,06><03,07>,<03,08>,<03,09>}, så är datastrukturen A ( ).
(A) Linjär struktur (B) Trädstruktur (C) Fysisk struktur (D) Grafisk struktur
2. Tidskomplexet för följande program är ()
för(i=1,s=0; i<=n; i++) {t=1;for(j=1;j<=i; j++) t=t*j; s=s+t; }
(A) O(n) (B) O(n2) (C) O(n3) (D) O(n4)
3. Ställ in pekarvariabeln p att peka på nod A i en enda länkad lista, om du tar bort nod A i en enda länkad lista måste du ändra operationssekvensen för pekaren till ().
(A) q=p->nästa; p->data=q->data; p->next=q->next; free(q);
(B) q=p->nästa; q->data=p->data; p->next=q->next; free(q);
(C) q=p->nästa; p->next=q->next; free(q);
(D) q=p->nästa; p->data=q->data; free(q);
4. Om det finns n postnyckelord som ska sorteras, krävs ( ) hjälppostenheter i heapsorteringen.
(A) 1 (B) n (C) nlog2n (D) n2
5. Om de initiala nyckelordsregistret är (20, 15, 14, 18, 21, 36, 40, 10), så är resultatet efter slutet av en snabbsortering registrerad med 20 som riktmärke ( ).
(A) 10,15,14,18,20,36,40,21
(B) 10,15,14,18,20,40,36,21
(C) 10,15,14,20,18,40,36,2l
(D) 15,10,14,18,20,36,40,21
6. Antag att det finns n noder i det binära sorteringsträdet, då är den genomsnittliga uppslagslängden i det binära sorteringsträdet ( ).
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7. Antag att det finns n hörn e kanter i den oriktade grafen G, då är antalet header-noder och tabellnoder i motsvarande närhetstabell ( ).
(A) n,e (B) e,n (C) 2n,e (D) n,2e
8. Antag att det finns n noder i en stark kopplingsgraf, då finns det minst ( ) kanter i den starka kopplingsgrafen.
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9. Det finns 5000 postnyckelord att sortera, om du behöver använda den snabbaste metoden för att välja de minsta 10-postnyckelorden kan du använda följande ( ) metod för att uppnå detta syfte.
(A) Snabbsortering (B) Heapsortering (C) Sammanfoga sortering (D) Infoga sortering
10. Följande fyra typer av ( ) har störst rumslig komplexitet.
(A) Insättningssortering (B) Bubblingssortering (C) Heapsortering (D) Sammanslagningssortering
2. Fyll i luckorna (1 poäng per tom, totalt 20 poäng)
1. Datans fysiska struktur omfattar huvudsakligen två situationer: _____________ och ______________.
2. Om det finns 500 noder i ett komplett binärt träd är djupet i det binära trädet __________; Om du använder en binär länkad lista som lagringsstruktur för det helt binära trädet finns det ___________ tomma pekarfält.
3. Om inmatningssekvensen är 1, 2, 3, kan ___________ olika utdatasekvenser erhållas efter stackens åtgärd.
4. Om adjacensmatrisen A[n][n] används som lagringsstruktur för graf G, så är summan av alla element på rad i i adjacensmatrisen lika med ________ av nod i, och summan av alla element i kolumn i är lika med ________ av nod i.
5. Om det finns n noder i Huffman-trädet finns det ________ noder med graden 1 i Huffman-trädet.
6. Om det finns n noder e i den riktade grafen G med riktade kanter, och summan av alla hörn som går in i grader är d, är relationen mellan e och d _________.
7. __________ genom att passera noderna i det binära sorteringsträdet kan man få en inkrementell sekvens av nyckelord (fyllda, mitten eller posterior).
8. Om det finns 100 element i uppslagstabellen, om du använder den dikotoma sökmetoden för att hitta dataelement X, behöver du jämföra det upp till ________ gånger för att avgöra om dataelement X finns i uppslagstabellen.
9. Oavsett om det är en stack med sekventiell lagringsstruktur eller en stack med kedjelagringsstruktur, är tidskomplexiteten för in- och utstackoperationer ____________.
10. Ett komplett binärt träd med n noder, om numrerade från topp till botten och från vänster till höger från 1, numreras föräldranoden till den i:te noden ____________, och numret på höger barnnod är ___________.
11. Om den initiala uppsättningen inspelade nyckelord är (72, 73, 71, 23, 94, 16, 5), är resultatet av en snabb sortering baserat på postnyckelordet 72 ___________________________.
12. Om det finns en mängd riktade kanter i den riktade grafen G E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>}, så är en topologisk följd av grafen ____________________.
13. Följande algoritm implementerar nyckelordet med värdet x i den sekventiella hashlistan, vänligen fyll i rätt formulering i understrecket.
struct record{int key; int others; };
inthashsqsearch(struct record hashtable[ ],int k)
{
inti,j; j=i=k % p;
medan (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; om (i==j) returnerar(-1); }
om (_______________________ ) returnerar(j); annars returnera (-1);
}
14. Följande algoritm implementerar nyckelvärdet k i det binära sorteringsträdet, vänligen fyll i rätt formulering i understrecket.
typedefstruct node{int key; struct node *lchild; Struct node *rchild; }bitree;
Bitree *bstsearch(bitree *t, int k)
{
om (t==0) returnerar(0); annars medan (t!=0)
om (t->nyckel==k)_____________; annars om (t->nyckel>k) t=t->lchild; else_____________;
}
Datastrukturtestpapper (1) Se svaret
1. Flervalsfrågor (2 poäng per fråga, totalt 20 poäng)
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
2. Fyll i luckorna (1 poäng per tom, totalt 26 poäng)
1. Korrekthet, läsbarhet, styrka och hög effektivitet
2.O(n)
3.9 3 3
4.-1 3 4 X * + 2 Y * 3 / -
5,2n n-1 n+1
6.e 2e
7. Riktad och icke-krets
8.n(n-1)/2 n(n-1)
9.（12，40） （ ） （74） （23,55，63）
10. Lägg till 1
11.O(log2n) O(nlog2n)
12. Konsolidering
Svaren på andra provfrågor kan ses:
Turister, om ni vill se det dolda innehållet i detta inlägg, snälla Svar
|
Publicerad på 2014-11-25 12:46:30
|
|
|
Publicerad på 2014-12-30 00:10:55