Datastruktur-papir (1)
1. Multiple choice-spørgsmål (2 point pr. spørgsmål, i alt 20 point)
1. De fælles karakteristika for stakke og køer er ( ).
A. Tillad kun indsættelse og sletning af elementer ved endepunktet
B. Alle først ind, sidst ud
C. Det er først ind, først ud
D. Der er ikke noget fælles grundlag
2. Køen, der er lagret på en linket måde, indsættes under indsættelsesoperationen ( ).
A. Kun hovedmarkøren modificeres B. Hoved- og halemarkørerne skal modificeres
C. Modificerer kun halepegeren D. Hoved- og halepegerne kan have behov for at modificeres
3. Hvilken af følgende datastrukturer er en ikke-lineær struktur? ( )
A. Kø B. Stak C. Lineær tabel D. Binært træ
4. Hvis der findes et todimensionelt array A[m][n], forudsat at A[0][0] er lagret på 644 (10), og A[2][2] er lagret på 676 (10), optager hvert element et rum, hvor er A[3][3][3](10) gemt? Fodnote (10) angiver, at den udtrykkes i decimal.
A.688 B.678 C.692 D.696
5. Træer bruges bedst til at repræsentere ( ).
A. Ordnede dataelementer B. Uordnede dataelementer
C. Data med forgrenede hierarkiske relationer mellem elementer D. Data uden forbindelse mellem elementer
6. Det maksimale antal noder i det k-te lag i det binære træ er ( ).
A.2k-1 B.2K+1 C.2K-1 D. 2k-1
7. Hvis der er en ordnet tabel med 18 elementer lagret i et endimensionelt array A[19], placeres det første element i A[1], og der nu udføres en binær søgning, så er indekset af sammenligningssekvensen for at finde A[3] ( )
A. 1,2,3 B. 9,5,2,3
C. 9,5,3 D. 9,4,2,3
8. Sorter hurtigt filerne med n poster, og den nødvendige ekstra lagringsplads er omtrent den samme
A. O(1) B. O(n) C. O(1og2n) D. O(n2)
9. For lineære tabeller (7, 34, 55, 25, 64, 46, 20, 10) til hashlagring, hvis H(K)=K %9 vælges som hashfunktion, er der ( ) elementer med hashadressen 1.
A.1 B.2 C.3 D.4
10. En urettet graf med 6 noder, og grafen bør have mindst ( ) kanter for at sikre en sammenhængende graf.
A.5 B.6 C.7 D.8
2. Udfyld hullerne (1 point pr. blank, 26 point i alt)
1. Kvaliteten af algoritmen vurderes normalt ud fra fire aspekter: _________, _________, _________ og _________.
2. Tidskompleksiteten af en algoritme er (n3+n2log2n+14n)/n2, og dens størrelsesorden udtrykkes som ________.
3. Hvis man antager, at den generaliserede tabel for et træ repræsenteres som A(C,D(E,F,G),H(I,J)), så er antallet af noder i træet __________, træets dybde er ___________, og træets grad er _________.
4. Værdien af suffiksformelen 9 2 3 +- 10 2 / - er __________. Suffiksformlen, der svarer til den midterste formel (3+4X)-2Y/3, er _______________________________.
5. Hvis et binært træ gemmes med en sammenkædet liste, har hver node to pegere til venstre barn og højre barn ud over datafeltet. I denne lagringsstruktur har det binære træ med n noder i alt ________ pointerfelter, hvoraf ________ pegerfelter gemmer adresser, og ________________ pegere er tomme pegere.
6. For en rettet graf og en urettet graf med n hjørner og E-bar-kanter findes der henholdsvis _______ og ________ kantnoder i dens tilsvarende naboskabstabell.
7. AOV-netværket er en ___________________ graf.
8. I en urettet komplet graf med n hjørner er der ________ kanter, og i en rettet komplet graf med n knuder er der ________ kanter.
9. Hvis man antager, at en lineær tabel er (12,23,74,55,63,40), hvis elementerne i samme rest bliver en undertabel i henhold til Key % 4-betingelsen, er de fire deltabeller, der opnås, ____________________________, ___________________, _______________________ og __________________________.
10. I processen med at indsætte elementer i et B_ træ, hvis rodknuden i træet endeligt splittes, er højden af det nye træ ___________ end den oprindelige træs.
11. I processen med heap-sortering er tidskompleksiteten ved at si en hvilken som helst forgreningsnode ________, og tidskompleksiteten for hele heap-sorteringsprocessen er ________.
12. Ved hurtigsortering, bunksortering og sammenfletningssortering er _________ sortering stabil.
Datastrukturpapir (2)
1. Multiple-choice spørgsmål (24 point)
1. Følgende beskrivelse af lineære tabeller er forkert ().
(A) Lineære tabeller opbevares sekventielt og skal optage et sammenhængende lagringsområde
(B) Lineære tabeller er kædede og optager ikke et sammenhængende stykke lagringsplads
(C) Lineære tabeller implementeres med kædebaseret lagring for at lette indsættelses- og sletningsoperationer
(d) Lineære tabeller implementeres med sekventiel lagring for at lette indsættelses- og sletningsoperationer
2. Antag, at det samlede antal bladnoder i Huffman-træet er m, og hvis en binær kædet liste bruges som lagringsstruktur, er der i alt ( ) tomme pointerfelter i Huffman-træet.
(A) 2m-1 (B)2m (C)2m+1 (D)4m
3. Hvis hoved- og halepegerne i den sekventielle løkkekø Q[0:M-1] er henholdsvis F og R, hovedpegeren F altid peger på hovedelementets forrige position, og halepegeren R altid peger på haleelementets nuværende position, så er antallet af elementer i løkkekøen ( ).
(A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M
4. Hvis mellemordens traverseringssekvens i et binært træ er ABCD, og den forrige sekvens er CABD, så er sekvensen, der opnås ved at gennemgå det binære træ i den efterfølgende rækkefølge, ().
(A) BADC (B)BCDA (C) CDAB (D) CBDA
5. Antag, at der er n hjørner i en fuldstændig urettet graf, så er der ( ) kanter i den fuldstændigt urettede graf.
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
6. Antag, at der er 2000 noder i et binært træ, så er minimumshøjden af det binære træ ( ).
(A) 9 (B) 10 (C) 11 (D) 12
7. Antag, at der er n hjørner i en rettet graf, så er der ( ) header-noder i nabotabellen, der svarer til den rettede graf.
(A) n-1 (B) n (C) n+1 (D) 2n-1
8. Sæt et sæt af indledende nøgleordssekvenser for posten (5, 2, 6, 3, 8), og resultatet af en hurtig sortering baseret på det første nøgleord 5 er ( ).
(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. Udfyld hullerne (24 point)
1. For effektivt at anvende HASH-opslagsteknologi skal to problemer løses: ____________________ og __________________________.
2. Funktionen af det følgende programsegment realiserer dataene x i stakken og kræver, at den korrekte sætning udfyldes i understregningen.
typedefstruct {int s[100]; int top; } sqstack;
Void Push (sqstack&stack,int x)
{
hvis (stack.top==m-1) printf("overflow");
ellers {____________________; _________________; }
}
3. Sekvensen, der opnås ved at gennemgå det binære sorteringstræ i mellemorden, er en ___________ sekvens (udfyldt i ordnet eller uordnet).
4. Den værste tidskompleksitet ved hurtig sortering er ___________, og den gennemsnitlige tidskompleksitet er __________.
5. Hvis antallet af noder med graden 0 i et binært træ er N0, og nodenummeret med grad 1 er N1, så er antallet af noder med grad 2 i det binære træ _________; Hvis en binær linked list bruges som lagringsstruktur for det binære træ, er der _______ tomme pointerfelter i det binære træ.
6. Antag at antallet af knuder og kanter i en bestemt urettet graf er henholdsvis n og e, og summen af graderne af alle hjørner er d, så er e = _______.
7. Hvis den indledende nøgleordssekvens for posten er (55, 63, 44, 38, 75, 80, 31, 56), så er den indledende heap, der er etableret af screeningsmetoden, ___________________________.
8. Det er kendt, at nabotabel-lagringsstrukturen for en rettet graf er som følger: Fra hjørne 1 er outputsekvensen for DFS-gennemgang:
, er outputsekvensen for BFS-gennemgang
Datastruktur-papir (3)
1. Multiple-choice spørgsmål (1 point pr. spørgsmål, i alt 20 point)
1. Hvis den binære form af en datastruktur udtrykkes 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å er datastrukturen A ( ).
(A) Lineær struktur (B) Træstruktur (C) Fysisk struktur (D) Grafisk struktur
2. Tidskomplekset for det følgende program er ()
for(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. Sæt pointervariabelen p til at pege på node A i en enkelt linket liste; hvis du sletter node A i en enkelt linket liste, skal du ændre operationssekvensen for pointeren til ().
(A) q=p->næste; p->data=q->data; p->next=q->next; free(q);
(B) q=p->næste; q->data=p->data; p->next=q->next; free(q);
(C) q=p->næste; p->next=q->next; free(q);
(D) q=p->næste; p->data=q->data; free(q);
4. Hvis der er n nøgleord for posten, der skal sorteres, kræves ( ) hjælpepostenheder i heap-sorteringen.
(A) 1 (B) n (C) nlog2n (D) n2
5. Hvis nøgleordene i den indledende søgeordspost er (20, 15, 14, 18, 21, 36, 40, 10), så er resultatet efter afslutningen af en hurtig sortering registreret med 20 som benchmark ( ).
(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, at der er n noder i det binære sorteringstræ, så er den gennemsnitlige opslagslængde i det binære sorteringstræ ( ).
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7. Antag, at der er n hjørner e kanter i den urettede graf G, så er antallet af header-noder og tabelnoder i den tilsvarende naboskabstabel ( ).
(A) n,e (B) e,n (C) 2n,e (D) n,2e
8. Antag, at der er n hjørner i en stærk forbindelsesgraf, så er der mindst ( ) kanter i den stærke forbindelsesgraf.
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9. Der er 5000 nøgleord, der skal sorteres, hvis du skal bruge den hurtigste metode til at vælge de mindste 10-post-nøgleord, kan du bruge følgende ( ) metode til at opnå dette formål.
(A) Hurtigsortering (B) Heapsortering (C) Sammenfletning, sortering (D) Indsæt sortering
10. De følgende fire slags ( ) har den største rumlige kompleksitet.
(A) Indsættelsessortering (B) Boblersortering (C) Heap-sortering (D) Sammenfletningsortering
2. Udfyld hullerne (1 point pr. blank, i alt 20 point)
1. Den fysiske struktur af data omfatter hovedsageligt to situationer: _____________ og ______________.
2. Hvis der er 500 noder i et komplet binært træ, er dybden af det binære træ __________; Hvis du bruger en binær linked list som lagringsstruktur for det fuldt binære træ, er der ___________ tomme pointerfelter.
3. Hvis inputsekvensen er 1, 2, 3, kan ___________ forskellige outputsekvenser opnås efter stakkens handling.
4. Hvis adjacensmatricen A[n][n] bruges som lagringsstruktur for graf G, så er summen af alle elementer på række i i adjacensmatricen lig med ________ af hjørne i, og summen af alle elementer i kolonne i er lig med ________ af hjørne i.
5. Hvis der er n noder i Huffman-træet, er der ________ noder med graden 1 i Huffman-træet.
6. Hvis der er n hjørner e i den retningsbestemte graf G med retningsbestemte kanter, og summen af alle knuder, der går ind i grader, er d, så er forholdet mellem e og d _________.
7. __________ at bevæge sig gennem noderne i det binære sorteringstræ kan opnå en inkrementel sekvens af nøgleord (fyldte, midterste eller posterior).
8. Hvis der er 100 elementer i opslagstabellen, og du bruger den dikotome søgemetode til at finde dataelement X, skal du sammenligne det op til ________ gange for at afgøre, om dataelement X er i opslagstabellen.
9. Uanset om det er en stak med en sekventiel lagringsstruktur eller en stak med kædelagerstruktur, er tidskompleksiteten for in-stack og out-stack operationer ____________.
10. Et komplet binært træ med n noder, hvis det nummereres fra top til bund og fra venstre mod højre startende fra 1, nummereres forældrenoden til den i-te node ____________, og nummeret på højre barnnode er ___________.
11. Hvis det oprindelige sæt af registrerede nøgleord er (72, 73, 71, 23, 94, 16, 5), så er resultatet af en hurtig sortering baseret på nøgleordet 72 ___________________________.
12. Hvis der findes et sæt rettede kanter i den retningsbestemte graf G E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>}, så er en topologisk sekvens af grafen ____________________.
13. Følgende algoritme implementerer nøgleordet med værdien x i den sekventielle hashliste, udfyld venligst den korrekte sætning i understregningen.
struct record{int key; int andre; };
inthashsqsearch(struct record hashtable[ ],int k)
{
inti,j; j=i=k % p;
mens (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; hvis (i==j) returnerer(-1); }
hvis (_______________________ ) returnerer (j); ellers returnere (-1);
}
14. Følgende algoritme implementerer nøgleværdien k i det binære sorteringstræ, udfyld venligst den korrekte sætning i understregningen.
typedefstruct node{int key; strukturnode *lchild; strukturnode *rchild; }bitree;
Bitree *bstsearch(bitree *t, int k)
{
hvis (t==0 ) returner(0); ellers mens (t!=0)
hvis (t->nøgle==k)_____________; ellers hvis (t->nøgle>k) t=t->lchild; else_____________;
}
Datastrukturtestpapir (1) Se svaret
1. Multiple-choice spørgsmål (2 point pr. spørgsmål, i alt 20 point)
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
2. Udfyld hullerne (1 point pr. blank, 26 point i alt)
1. Korrekthed, læsbarhed, styrke og høj 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. Retningsbestemt og ikke-kredsløb
8.n(n-1)/2 n(n-1)
9.（12，40） （ ） （74） （23,55，63）
10. Tilføj 1
11.O(log2n) O(nlog2n)
12. Konsolidering
Svarene på andre testspørgsmål kan ses:
Turister, hvis I vil se det skjulte indhold i dette indlæg, så vær venlig Svar
|
Opslået på 25/11/2014 12.46.30
|
|
|
Opslået på 30/12/2014 00.10.55