Članek o podatkovni strukturi (1)
1. Vprašanja z več izbirami (2 točki na vprašanje, skupaj 20 točk)
1. Skupne značilnosti skladov in vrst so ( ).
A. Dovolite vstavljanje in brisanje elementov le na končni točki
B. Vsi prvi noter, zadnji ven
C. Vse je prvi noter, prvi ven
D. Ni skupne točke
2. Vrsta, shranjena na povezan način, se vstavlja ob izvajanju operacije vstavljanja ( ).
A. Spremenjen je le kazalec za glavo B. Kazalec na glavi in repu je treba spremeniti
C. Spremenite le kazalec na repu D. Kazalec na glavi in repu je morda treba spremeniti
3. Katera od naslednjih podatkovnih struktur je nelinearna struktura? ( )
A. Vrsta B. Sklad C. Linearna tabela D. Binarno drevo
4. Če obstaja dvodimenzionalna tabela A[m][n], če predpostavimo, da je A[0][0] shranjena pri 644 (10), in A[2][2] pri 676 (10), vsak element zaseda prostor, kje je shranjen A[3][3][3](10)? Opomba (10) označuje, da je izražena v decimalnem sistemu.
A.688 B.678 C.692 D.696
5. Drevesa so najbolje uporabljena za predstavitev ( ).
A. Urejeni podatkovni elementi B. Neurejeni podatkovni elementi
C. Podatki z razvejanimi hierarhičnimi odnosi med elementi D. Podatki brez povezave med elementi
6. Največje število vozlišč v k-ti plasti binarnega drevesa je ( ).
A.2K-1 B.2K+1 C.2K-1 D. 2K-1
7. Če je v enodimenzionalni tabeli A[19] shranjena urejena tabela 18 elementov, je prvi element postavljen v A[1], nato pa se izvede binarno iskanje, potem je indeks primerjalnega zaporedja za iskanje A[3] ( )
A. 1,2,3 B. 9,5,2,3
C. 9,5,3 D. 9,4,2,3
8. Hitro razvrstite datoteke n zapisov, pri čemer je pomožni pomnilni prostor približno enak
A. O(1) B. O(n) C. O(1og2n) D. O(n2)
9. Za linearne tabele (7, 34, 55, 25, 64, 46, 20, 10) za shranjevanje zgoščenk, če je kot zgoščevalna funkcija izbrana H(K)=K %9, obstajajo elementi ( ) z zgoščevalnim naslovom 1.
A.1 B.2 C.3 D.4
10. Neusmerjen graf s 6 vozlišči, pri čemer mora imeti graf vsaj ( ), da se zagotovi povezan graf.
A.5 B.6 C.7 D.8
2. Dopolnite praznine (1 točka na prazno, skupaj 26 točk)
1. Kakovost algoritma se običajno ocenjuje s štirih vidikov: _________, _________, _________ in _________.
2. Časovna zahtevnost algoritma je (n3+n2log2n+14n)/n2, njegov red velikosti pa je izražen kot ________.
3. Predpostavimo, da je posplošena tabela drevesa predstavljena kot A(C,D(E,F,G),H(I,J)), je število vozlišč v drevesu __________, globina drevesa ___________, stopnja drevesa pa _________.
4. Vrednost formule za pripono 9 2 3 +- 10 2 / - je __________. Formula s pripono, ki ustreza srednji formuli (3+4X)-2Y/3, je _______________________________.
5. Če je binarno drevo shranjeno s povezanim seznamom, ima vsako vozlišče poleg podatkovnega polja dva kazalca na levega otroka in desnega otroka. V tej strukturi shranjevanja ima binarno drevo z n vozlišči skupaj ________ polj kazalec, od katerih ________ polja kazalcev shranjujejo naslove, ________________ kazalcev pa prazne kazalce.
6. Za usmerjen graf in neusmerjen graf z n vozlišči in E-barovnimi povezavami sta v ustrezni tabeli sosednjosti _______ oziroma ________ vozlišč povezav.
7. AOV omrežje je ___________________ graf.
8. V neusmerjenem popolnem grafu z n vozlišči je ________ povezav, v usmerjenem popolnem grafu z n vozlišči pa ________ povezav.
9. Če predpostavimo, da je linearna tabela (12,23,74,55,63,40), če elementi istega ostanka postanejo podtabela po pogoju Key % 4, so štiri dobine podtabele ____________________________, ___________________, _______________________ in __________________________.
10. Pri postopku vstavljanja elementov v B_ drevo, če je korensko vozlišče drevesa končno razdeljeno, je višina novega drevesa ___________ višine izvirnega drevesa.
11. Pri procesu sortiranja kupa je časovna zahtevnost presejanja kateregakoli vozlišča ________, časovna zahtevnost celotnega procesa sortiranja pa ________.
12. Pri hitrem razvrščanju, sortiranju s kupi in sortiranju z združitvijo je _________ razvrščanje stabilno.
Članek o podatkovnih strukturah (2)
1. Vprašanja z več izbirami (24 točk)
1. Naslednji opis linearnih tabel je napačen ().
(A) Linearne tabele se shranjujejo zaporedno in morajo zasedati sosednji prostor za shranjevanje
(B) Linearne tabele so verižne in ne zavzamejo neprekinjenega prostora za shranjevanje
(C) Linearne tabele so implementirane z verižnim shranjevanjem za lažje vstavljanje in brisanje
(d) Linearne tabele so implementirane s sekvenčnim pomnilnikom za lažje vstavljanje in brisanje
2. Predpostavimo, da je skupno število listnih vozlišč v Huffmanovem drevesu m, in če se kot shranjevalna struktura uporablja binarni povezani seznam, je v Huffmanovem drevesu skupaj ( ) praznih kazalnih polj.
(A) 2m-1 (B)2m (C)2m+1 (D)4m
3. Če sta kazalca na glavi in repu zaporedne zanke Q[0:M-1] F in R, kazalec na glavo F vedno kaže na prejšnji položaj elementa glave, kazalec na rep R pa vedno kaže na trenutno pozicijo elementa na repu, potem je število elementov v zanki ( ).
(A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M
4. Če je zaporedje prehoda srednjega reda binarnega drevesa ABCD, prejšnje zaporedje pa CABD, potem je zaporedje, pridobljeno s prečkanjem binarnega drevesa v naslednjem vrstnem redu, ().
(A) BADC (B)BCDA (C) CDAB (D) CBDA
5. Predpostavimo, da je v popolnoma neusmerjenem grafu n vozlišč, potem je v popolnoma neusmerjenem grafu ( ) povezav.
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
6. Predpostavimo, da je v binarnem drevesu 2000 vozlišč, je minimalna višina binarnega drevesa ( ).
(A) 9 (B) 10 (C) 11 (D) 12
7. Predpostavimo, da je v usmerjenem grafu n vozlišč, potem so v tabeli sosednosti, ki ustrezajo usmerjenemu grafu, vozlišča glave ( ).
(A) n-1 (B) n (C) n+1 (D) 2n-1
8. Nastavite niz začetnih zaporedij ključnih besed zapisa (5, 2, 6, 3, 8), rezultat hitrega sortiranja na podlagi prve ključne besede zapisa 5 pa je ( ).
(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. Dopolnite praznine (24 točk)
1. Za učinkovito uporabo tehnologije iskanja HASH je treba rešiti dva problema: ____________________ in __________________________.
2. Funkcija naslednjega programskega segmenta realizira podatke x v sklad in zahteva, da se v spodnji črti izpolni pravilen stavek.
typedefstruct {int s[100]; int top; } sqstack;
Void Push (sqstack&stack,int x)
{
if (stack.top==m-1) printf("preliv");
drugače {____________________; _________________; }
}
3. Zaporedje, pridobljeno s prečkanjem binarnega sortirnega drevesa v srednjem redu, je ___________ zaporedje (izpolnjeno v urejenem ali neurejenem stanju).
4. Najhujša časovna zahtevnost hitrega razvrščanja je ___________, povprečna časovna zahtevnost pa __________.
5. Če je število vozlišč s stopnjo 0 v binarnem drevesu N0, število vozlišč s stopnjo 1 pa N1, je število vozlišč s stopnjo 2 v binarnem drevesu _________; Če se kot shranjevalna struktura binarnega drevesa uporablja binarni povezani seznam, je v binarnem drevesu _______ praznih kazalnih polj.
6. Predpostavimo, da je število vozlišč in povezav v določenem neusmerjenem grafu n in e, in da je vsota stopenj vseh vozlišč d, potem je e = _______.
7. Če je začetno zaporedje ključnih besed zapisa (55, 63, 44, 38, 75, 80, 31, 56), je začetni kup, ki ga določi metoda presejanja, ___________________________.
8. Znano je, da je struktura shranjevalne tabele sosednosti usmerjenega grafa naslednja: Iz vozlišča 1 je izhodno zaporedje DFS prehoda:
, izhodno zaporedje prehoda BFS je
Članek o strukturi podatkov (3)
1. Vprašanja z več izbirami (1 točka na vprašanje, skupaj 20 točk)
1. Če je binarna oblika podatkovne strukture izražena kot 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>}, potem je podatkovna struktura A ( ).
(A) Linearna struktura (B) Drevesna struktura (C) Fizična struktura (D) Grafična struktura
2. Časovni kompleks naslednjega programa je ()
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. Nastavite kazalec p tako, da kaže na vozlišče A v enem povezanem seznamu; če izbrišete vozlišče A v enem povezanem seznamu, morate spremeniti zaporedje operacij kazalca na ().
(A) q=p->naslednji; p->data=q->data; p->next=q->next; free(q);
(B) q=p->naslednje; q->data=p->data; p->next=q->next; free(q);
(C) q=p->naslednji; p->next=q->next; free(q);
(D) q=p->naslednje; p->data=q->data; free(q);
4. Če je n ključnih besed zapisov, ki jih je treba razvrstiti, so ( ) pomožne enote zapisov potrebne v sortiranju kupa.
(A) 1 (B) n (C) nlog2n (D) n2
5. Če so začetne ključne besede (20, 15, 14, 18, 21, 36, 40, 10), potem je rezultat po koncu hitrega sortiranja, zabeležen z 20 kot merilom, ( ).
(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. Predpostavimo, da je v binarnem drevesu razvrščanja n vozlišč, potem je povprečna dolžina iskanja v binarnem sortirnem drevesu ( ).
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7. Predpostavimo, da je v neusmerjenem grafu G n vozlišč e povezav, potem je število glavnih vozlišč in vozlišč tabele v ustrezni sosedniški tabeli ( ).
(A) n,e (B) e,n (C) 2n,e (D) n,2e
8. Predpostavimo, da je v grafu močne povezave n vozlišč, potem je vsaj ( ) povezav v grafu močne povezave.
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9. Na voljo je 5000 ključnih besed za zapise, ki jih je treba razvrstiti; če potrebujete najhitrejši način za izbiro najmanjših 10 ključnih besed zapisov, lahko za ta namen uporabite naslednjo ( ) metodo.
(A) Hitro sortiranje (B) Sortiranje kupa (C) Združevanje sortiranje (D) Vstavljanje urejanje
10. Naslednje štiri vrste ( ) imajo največjo prostorsko kompleksnost.
(A) Vstavljanje (B) Mehurčkasto razvrščanje (C) Sortiranje po kupu (D) Združevanje
2. Dopolnite praznine (1 točka na prazno, skupaj 20 točk)
1. Fizična struktura podatkov vključuje predvsem dve situaciji: _____________ in ______________.
2. Če je v popolnem binarnem drevesu 500 vozlišč, je globina binarnega drevesa __________; Če uporabite binarni povezani seznam kot shranjevalno strukturo za popolnoma binarno drevo, je ___________ praznih polj kazalec.
3. Če je vhodno zaporedje 1, 2, 3, je mogoče po akciji sklada pridobiti ___________ različnih izhodnih zaporedij.
4. Če se matrika sosednosti A[n][n] uporabi kot shranjevalna struktura za graf G, je vsota vseh elementov v vrstici i v matriki sosednosti enaka ________ vozlišč i, vsota vseh elementov v stolpcu i pa je enaka ________ vozlišča i.
5. Če je v Huffmanovem drevesu n vozlišč, je v Huffmanovem drevesu ________ vozlišč s stopnjo 1.
6. Če je v smernem grafu G n vozlišč e z usmerjenimi robovi, in je vsota vseh vozlišč, ki vstopajo v stopnje, enaka d, potem je razmerje med e in d _________.
7. __________ prečkanje vozlišč v binarnem sortirnem drevesu lahko pridobi inkrementalno zaporedje ključnih besed (izpolnjenih, srednjih ali posteriornih).
8. Če je v iskalni tabeli 100 elementov, če uporabite dihotomno metodo iskanja za iskanje podatkovnega elementa X, ga morate primerjati do ________-krat, da ugotovite, ali je podatkovni element X v iskalni tabeli.
9. Ne glede na to, ali gre za sklad s sekvenčno shranjevalno strukturo ali za sklad z verižno strukturo, je časovna zahtevnost operacij znotraj in zunaj sklada ____________.
10. Popolno binarno drevo z n vozlišči, če je oštevilčeno od zgoraj navzdol in od leve proti desni, začenši z 1, je starševsko vozlišče i-tega vozlišča oštevilčeno ____________, številka desnega podvozlja pa ___________.
11. Če je začetni nabor zabeleženih ključnih besed (72, 73, 71, 23, 94, 16, 5), je rezultat hitrega sortiranja na podlagi zapisne ključne besede 72 ___________________________.
12. Če obstaja množica usmerjenih povezav v smernem grafu G E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>}, potem je topološko zaporedje grafa ____________________.
13. Naslednji algoritem implementira ključno besedo z vrednostjo x v zaporednem seznamu zgoščenih točk, prosimo, vnesite pravilno izjavo v spodnji črti.
struct record{int key; v drugih; };
inthashsqsearch(hashtable zapisa strukture[ ],int k)
{
inti,j; j=i=k % p;
medtem ko (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; če (i==j) vrni(-1); }
če (_______________________ ) vrni(j); else return(-1);
}
14. Naslednji algoritem implementira ključno vrednost k v binarnem drevesu sortiranja, prosimo, vnesite pravilno izjavo v spodnji črti.
typedefstruct node{int key; struct vozlišče *lchild; struct node *rchild; }bitree;
bitree *bstsearch(bitree *t, int k)
{
če (t==0 ) vrni(0); sicer medtem ko (t!=0)
če (t->ključ==k)_____________; sicer če (t->key>k) t=t->lchild; else_____________;
}
Testna naloga o podatkovni strukturi (1) Glejte odgovor
1. Vprašanja z več izbirami (2 točki na vprašanje, skupaj 20 točk)
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
2. Dopolnite praznine (1 točka na prazno, skupaj 26 točk)
1. Pravilnost, berljivost, trdnost in visoka učinkovitost
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. Usmerjeni in nevezni
8.n(n-1)/2 n(n-1)
9.（12，40） （ ） （74） （23,55，63）
10. Dodaj 1
11.O(log2n) O(nlog2n)
12. Konsolidacija
Odgovori na druga vprašanja na testu so na voljo naslednji:
Turisti, če želite videti skrito vsebino te objave, prosim Odgovoriti
|
Objavljeno na 25. 11. 2014 12:46:30
|
|
|
Objavljeno na 30. 12. 2014 00:10:55