Datastrukturpapir (1)
1. Flervalgsspørsmål (2 poeng per spørsmål, totalt 20 poeng)
1. De felles kjennetegnene til stabler og køer er ( ).
A. Tillat kun innsetting og sletting av elementer ved endepunktet
B. Alle først inn, sist ut
C. Alt er først inn, først ut
D. Det finnes ikke noe felles grunnlag
2. Køen lagret på en lenket måte settes inn når innsettingsoperasjonen utføres ( ).
A. Kun hodepekeren modifiseres B. Hode- og halpekeren må modifiseres
C. Endre kun halepekeren D. Hode- og halpekeren kan måtte endres
3. Hvilken av følgende datastrukturer er en ikke-lineær struktur? ( )
A. Kø B. Stabel C. Lineær tabell D. Binært tre
4. Hvis det finnes et todimensjonalt array A[m][n], forutsatt at A[0][0] lagres på 644 (10), og A[2][2] lagres på 676 (10), opptar hvert element et rom, hvor A[3][3][3][3](10) lagres? Fotnote (10) indikerer at den er uttrykt i desimal.
A.688 B.678 C.692 D.696
5. Trær brukes best til å representere ( ).
A. Ordnede dataelementer B. Uordnede dataelementer
C. Data med forgrenede hierarkiske relasjoner mellom elementene D. Data uten forbindelse mellom elementene
6. Det maksimale antallet noder i det k-te laget i det binære treet er ( ).
A.2k-1 B.2K+1 C.2K-1 D. 2k-1
7. Hvis det finnes en ordnet tabell med 18 elementer lagret i et endimensjonalt array A[19], plasseres det første elementet i A[1], og nå utføres et binært søk, så er indeksen av sammenligningssekvensen for å finne A[3] ( )
A. 1,2,3 B. 9,5,2,3
C. 9,5,3 D. 9,4,2,3
8. Sorter raskt filene med n poster, og den ekstra lagringsplassen som kreves 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) for hashlagring, hvis H(K)=K %9 velges som hash-funksjon, finnes det ( ) elementer med en hash-adresse på 1.
A.1 B.2 C.3 D.4
10. En urettet graf med 6 noder, og grafen bør ha minst ( ) kanter for å sikre en sammenhengende graf.
A.5 B.6 C.7 D.8
2. Fyll inn hullene (1 poeng per blank, totalt 26 poeng)
1. Kvaliteten på algoritmen vurderes vanligvis ut fra fire aspekter: _________, _________, _________ og _________.
2. Tidskompleksiteten til en algoritme er (n3+n2log2n+14n)/n2, og størrelsesordenen uttrykkes som ________.
3. Forutsatt at den generaliserte tabellen til et tre representeres som A(C,D(E,F,G),H(I,J)), så er antallet noder i treet __________, dybden på treet er ___________, og graden på treet er _________.
4. Verdien av suffiksformelen 9 2 3 +- 10 2 / - er __________. Suffiksformelen som tilsvarer den midtre formelen (3+4X)-2Y/3 er _______________________________.
5. Hvis et binært tre lagres med en lenket liste, har hver node to pekere til venstre barn og høyre barn i tillegg til datafeltet. I denne lagringsstrukturen har det binære treet med n noder totalt ________ pekerfelt, hvorav ________ pekerfelt lagrer adresser og ________________ pekere er tomme pekere.
6. For en rettet graf og en urettet graf med n hjørner og E-bar-kanter, finnes det henholdsvis _______ og ________ kantnoder i den tilsvarende nabotabellen.
7. AOV-nettverket er en ___________________ graf.
8. I en urettet komplett graf med n noder finnes det ________ kanter, og i en rettet komplett graf med n noder finnes det ________ kanter.
9. Forutsatt at en lineær tabell er (12,23,74,55,63,40), hvis elementene i samme rest blir en deltabell i henhold til Key % 4-betingelsen, er de fire deltabellene som oppnås ____________________________, ___________________, _______________________ og __________________________.
10. I prosessen med å sette inn elementer i et B_ tre, hvis rotnoden i treet til slutt splittes, er høyden på det nye treet ___________ enn på det opprinnelige treet.
11. I prosessen med heapsortering er tidskompleksiteten ved å sikte en hvilken som helst grennode ________, og tidskompleksiteten for hele heapsorteringsprosessen er ________.
12. I hurtigsortering, heap-sortering og sammenslåingssortering er _________ sortering stabil.
Datastruktur-artikkel (2)
1. Flervalgsspørsmål (24 poeng)
1. Følgende beskrivelse av lineære tabeller er feil ().
(A) Lineære tabeller lagres sekvensielt og må oppta et sammenhengende lagringsområde
(B) Lineære tabeller er lenket sammen og tar ikke opp et sammenhengende lagringsområde
(C) Lineære tabeller implementeres med kjedet lagring for å lette innsettings- og slettingsoperasjoner
(d) Lineære tabeller implementeres med sekvensiell lagring for å lette innsettings- og slettingsoperasjoner
2. Anta at det totale antallet bladnoder i Huffman-treet er m, og hvis en binær lenket liste brukes som lagringsstruktur, finnes det totalt ( ) tomme pekerfelt i Huffman-treet.
(A) 2m-1 (B)2m (C)2m+1 (D)4m
3. Hvis hode- og halepekerne til den sekvensielle løkkekøen Q[0:M-1] er henholdsvis F og R, peker hodepekeren F alltid til forrige posisjon til hodeelementet, og halepekeren R alltid peker til den nåværende posisjonen til haleelementet, så er antall elementer i løkkekøen ( ).
(A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M
4. Hvis mellomordens traverseringssekvens i et binært tre er ABCD og den forrige sekvenstraverseringssekvensen er CABD, så er sekvensen som oppnås ved å gå gjennom det binære treet i påfølgende rekkefølge ().
(A) BADC (B)BCDA (C) CDAB (D) CBDA
5. Anta at det finnes n noder i en helt urettet graf, da finnes det ( ) kanter i den helt urettede grafen.
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
6. Anta at det er 2000 noder i et binært tre, da er minimumshøyden til det binære treet ( ).
(A) 9 (B) 10 (C) 11 (D) 12
7. Anta at det finnes n noder i en rettet graf, da finnes det ( ) header-noder i nabotabellen som tilsvarer den rettede grafen.
(A) n-1 (B) n (C) n+1 (D) 2n-1
8. Sett et sett med initiale nøkkelordsekvenser (5, 2, 6, 3, 8), og resultatet av en rask sortering basert på det første nøkkelordet 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. Fyll inn hullene (24 poeng)
1. For å effektivt anvende HASH-oppslagsteknologi må to problemer løses: ____________________ og __________________________.
2. Funksjonen til det påfølgende programsegmentet realiserer dataene x i stakken, og krever at riktig setning fylles ut i understrekingen.
typedefstruct {int s[100]; Int Top; } sqstack;
void push (sqstack&stack,int x)
{
hvis (stack.top==m-1) printf("overflow");
else {____________________; _________________; }
}
3. Sekvensen som oppnås ved å gå gjennom det binære sorteringstreet i mellomordenen er en ___________ sekvens (utfylt ordnet eller uordnet).
4. Den verste tidskompleksiteten ved hurtigsortering er ___________, og gjennomsnittlig tidskompleksitet er __________.
5. Hvis antall noder med grad 0 i et binært tre er N0 og nodenummeret med grad 1 er N1, så er antallet noder med grad 2 i det binære treet _________; Hvis en binær lenket liste brukes som lagringsstruktur for det binære treet, finnes det _______ tomme pekerfelt i det binære treet.
6. Anta at antall hjørner og kanter i en viss urettet graf er henholdsvis n og e, og summen av gradene til alle hjørner er d, da er e = _______.
7. Hvis den innledende nøkkelordsekvensen er (55, 63, 44, 38, 75, 80, 31, 56), er den opprinnelige heapen etablert av screeningmetoden ___________________________.
8. Det er kjent at lagringsstrukturen for nabotabeller i en rettet graf er som følger: Fra node 1 er utgangssekvensen for DFS-traversering:
, er utgangssekvensen for BFS-traversering
Datastrukturpapir (3)
1. Flervalgsspørsmål (1 poeng per spørsmål, totalt 20 poeng)
1. Hvis den binære formen av en datastruktur uttrykkes 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) Trestruktur (C) Fysisk struktur (D) Grafisk struktur
2. Tidskomplekset til 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. Sett pekervariabelen p til å peke på node A i en enkelt lenket liste; hvis du sletter node A i en enkelt lenket liste, må du endre operasjonssekvensen til pekeren til ().
(A) q=p->neste; p->data=q->data; p->next=q->next; free(q);
(B) q=p->neste; q->data=p->data; p->next=q->next; free(q);
(C) q=p->neste; p->next=q->next; free(q);
(D) q=p->neste; p->data=q->data; free(q);
4. Hvis det er n postnøkkelord som skal sorteres, kreves ( ) hjelpepostenheter i heap-sorteringen.
(A) 1 (B) n (C) nlog2n (D) n2
5. Hvis nøkkelordene i den opprinnelige nøkkelordposten er (20, 15, 14, 18, 21, 36, 40, 10), er resultatet etter slutten av en rask sortering registrert med 20 som referansepunkt ( ).
(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. Anta at det finnes n noder i det binære sorteringstreet, da er gjennomsnittlig oppslagslengde i det binære sorteringstreet ( ).
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7. Anta at det finnes n hjørner e kanter i den urettede grafen G, da er antallet header-noder og tabellnoder i den tilsvarende nabotabellen ( ).
(A) n,e (B) e,n (C) 2n,e (D) n,2e
8. Anta at det finnes n noder i en sterk forbindelsesgraf, da finnes det minst ( ) kanter i den sterke forbindelsesgrafen.
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9. Det er 5000 post-nøkkelord som skal sorteres, hvis du trenger å bruke den raskeste metoden for å velge de minste 10-post-nøkkelordene, kan du bruke følgende ( ) metode for å oppnå dette formålet.
(A) Rasksortering (B) Heapsortering (C) Sammenslåing sortering (D) Sett inn sortering
10. De følgende fire typene ( ) har størst romlig kompleksitet.
(A) Innsettingssortering (B) Boblesortering (C) Heapsortering (D) Sammenslåingssortering
2. Fyll inn hullene (1 poeng per tomrom, totalt 20 poeng)
1. Den fysiske strukturen til data omfatter hovedsakelig to situasjoner: _____________ og ______________.
2. Hvis det er 500 noder i et komplett binært tre, er dybden til det binære treet __________; Hvis du bruker en binær lenket liste som lagringsstruktur for det fullt binære treet, finnes det ___________ tomme pekerfelt.
3. Hvis inngangssekvensen er 1, 2, 3, kan ___________ forskjellige utgangssekvenser oppnås etter at stakken har virket.
4. Hvis adjacensmatrisen A[n][n] brukes som lagringsstruktur for graf G, er summen av alle elementene på rad i i adjacensmatrisen lik ________ til node i, og summen av alle elementene i kolonne i er lik ________ til node i.
5. Hvis det finnes n noder i Huffman-treet, finnes det ________ noder med grad 1 i Huffman-treet.
6. Hvis det er n hjørner e i retningsgrafen G med retningskanter, og summen av alle hjørner som går inn i grader er d, er forholdet mellom e og d _________.
7. __________ gjennom nodene i det binære sorteringstreet kan man oppnå en inkrementell sekvens av nøkkelord (fylt, midt eller bak).
8. Hvis det er 100 elementer i oppslagstabellen, og du bruker den dikotome søkemetoden for å finne dataelement X, må du sammenligne det opptil ________ ganger for å avgjøre om dataelement X er i oppslagstabellen.
9. Enten det er en stabel med sekvensiell lagringsstruktur eller en stabel med kjedelagringsstruktur, er tidskompleksiteten for inn- og utstakkoperasjoner ____________.
10. Et komplett binært tre med n noder, hvis det nummereres fra topp til bunn og fra venstre til høyre fra 1, er foreldrenoden til den i-te noden nummerert ____________, og nummeret til høyre barnenode er ___________.
11. Hvis det opprinnelige settet med registrerte nøkkelord er (72, 73, 71, 23, 94, 16, 5), er resultatet av en rask sortering basert på nøkkelordet 72 ___________________________.
12. Hvis det finnes et sett med rettede kanter i den retningsbestemte grafen G E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>}, så er en topologisk sekvens av grafen ____________________.
13. Følgende algoritme implementerer nøkkelordet med verdien x i den sekvensielle hashlisten, vennligst fyll inn riktig setning i understreken.
struct record{int key; i 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økkelverdien k i det binære sorteringstreet, vennligst fyll inn riktig setning i understreken.
typedefstruct node{int key; struct node *lchild; struct-node *rchild; }bitree;
bitree *bstsearch(bitree *t, int k)
{
hvis (t==0) returner(0); ellers mens (t!=0)
hvis (t->nøkkel==k)_____________; ellers hvis (t->nøkkel>k) t=t->lchild; else_____________;
}
Testoppgave for datastruktur (1) Se svaret
1. Flervalgsspørsmål (2 poeng per spørsmål, totalt 20 poeng)
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
2. Fyll inn hullene (1 poeng per blank, totalt 26 poeng)
1. Korrekthet, lesbarhet, styrke og høy 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-krets
8.n(n-1)/2 n(n-1)
9.（12，40） （ ） （74） （23,55，63）
10. Legg til 1
11.O(log2n) O(nlog2n)
12. Konsolidering
Svarene på andre testspørsmål kan sees:
Turister, hvis dere vil se det skjulte innholdet i dette innlegget, vær så snill Svare
|
Publisert på 25.11.2014 12:46:30
|
|
|
Publisert på 30.12.2014 00:10:55