Andmestruktuuri artikkel (1)
1. Valikvastustega küsimused (2 punkti küsimuse kohta, kokku 20 punkti)
1. Virnade ja järjekordade ühised omadused on ( ).
V. Lubada elementide lisamist ja kustutamist ainult lõpp-punktis
B. Kõik esimesena sisse, viimasena välja
C. Kõik on esimene sisse, esimene välja
D. Ühist pinnast ei ole
2. Järjekord, mis on salvestatud lingitud viisil, lisatakse sisestamistoimingu sooritamisel ( ).
A. Ainult pea osutit muudetakse B. Pea ja saba osutid peavad olema muudetud
C. Muuda ainult saba osutit D. Pea ja saba osutid võivad vajada muutmist
3. Milline järgmistest andmestruktuuridest on mittelineaarne struktuur? ( )
A. Järjekord B. Virna C. Lineaarne tabel D. Binaarpuu
4. Kui eksisteerib kahemõõtmeline massiiv A[m][n], eeldades, et A[0][0] salvestatakse 644 (10) ja A[2][2] on salvestatud 676 (10), siis iga element hõivab ruumi, kus on A[3][3][3][10)? Jalus (10) näitab, et see on väljendatud kümnendsüsteemis.
A.688 B.678 C.692 D.696
5. Puid kasutatakse kõige paremini ( ).
A. Järjestatud andmeelemendid B. Järjestamata andmeelemendid
C. Andmed, millel on harunevad hierarhilised suhted elementide vahel D. Andmed ilma elementide vahelise ühenduseta
6. Binaarpuu k-nda kihi maksimaalne sõlmede arv on ( ).
A.2k-1 B.2K+1 C.2K-1 D. 2k-1
7. Kui ühemõõtmelises massiivis A[19] on järjestatud tabel 18 elemendist, paigutatakse esimene element A[1] ja nüüd tehakse binaarne otsing, siis võrdlusjärjestuse indeks A[3] leidmiseks on ( )
A. 1,2,3 B. 9,5,2,3
C. 9,5,3 D. 9,4,2,3
8. Sorteeri kiiresti n kirje failid ja vajalik abisalvestusruum on ligikaudu sama suur
A. O(1) B. O(n) C. O(1og2n) D. O(n2)
9. Lineaartabelite (7, 34, 55, 25, 64, 46, 20, 10) puhul räsi salvestamiseks, kui H(K)=K %9 on valitud räsi funktsiooniks, on ( ) elemente, mille räsi aadress on 1.
A.1 B.2 C.3 D.4
10. Suunamata graaf 6 sõlmega ning graafil peaks olema vähemalt ( ) servad, et tagada ühendatud graaf.
A.5 B.6 C.7 D.8
2. Täida tühimikud (1 punkt tühiku kohta, kokku 26 punkti)
1. Algoritmi kvaliteeti hinnatakse tavaliselt neljast aspektist: _________, _________, _________ ja _________.
2. Algoritmi ajaline keerukus on (n3+n2log2n+14n)/n2 ning selle suurusjärk väljendatakse kujul ________.
3. Eeldades, et puu üldistatud tabel on esitatud kujul A(C,D(E,F,G),H(I,J)), siis puus sisalduvate sõlmede arv on __________, puu sügavus on ___________ ja puu aste on _________.
4. Järelliide valemi 9 2 3 +- 10 2 / - väärtus on __________. Keskmise valemi (3+4X)-2Y/3 järelliite valem on _______________________________.
5. Kui binaarpuu salvestatakse koos lingitud nimekirjaga, on igal sõlmel lisaks andmeväljale kaks viidet vasakule lapsele ja paremale lapsele. Selles salvestusstruktuuris on binaarsel puul, kus on n sõlme, kokku ________ osuti välja, millest ________ osutaja väljad salvestavad aadresse ja ________________ osutid on tühjad.
6. Suunatud graafi ja suunamata graafi puhul, millel on n tippu ja E-riba serva, on vastavas naabertabelis vastavalt _______ ja ________ servasõlme.
7. AOV-võrk on ___________________ graafik.
8. Suunamata täielikus graafis, millel on n tippu, on ________ serva ning suunatud täielikus graafis, kus on n tippu, on ________ serva.
9. Eeldades, et lineaartabel on (12,23,74,55,63,40), siis kui sama jäägi elemendid muutuvad alamtabeliks vastavalt Key % 4 tingimusele, on saadud neli alamtabelit ____________________________, ___________________, _______________________ ja __________________________.
10. Elementide lisamise protsessis B_ puusse, kui puu juursõlm lõpuks jagatakse, on uue puu kõrgus ___________ kui algse puu kõrgus.
11. Kuhjade sorteerimise protsessis on iga harusõlme sõelumise ajakeerukus ________ ja kogu kuhja sorteerimisprotsessi ajakeerukus ________.
12. Kiires sorteerimises, kuhjade sorteerimises ja liitmissorteerimises _________ sorteerimine stabiilne.
Andmestruktuuri artikkel (2)
1. Valikvastustega küsimused (24 punkti)
1. Järgmine lineaartabelite kirjeldus on vale ().
(A) Lineaarsed tabelid salvestatakse järjestikku ja peavad hõivama järjestikust salvestusruumi
(B) Lineaarsed tabelid on aheldatud ega võta pidevat salvestusruumi
(C) Lineaarsed tabelid on rakendatud aheldatud salvestusega, et hõlbustada lisamis- ja kustutamistoiminguid
(d) Lineaarsed tabelid on rakendatud järjestikuse salvestusega, et hõlbustada lisamise ja kustutamise toiminguid.
2. Oletame, et Huffmani puu lehesõlmede koguarv on m ja kui salvestusstruktuurina kasutatakse binaarset lingitud loendit, on Huffmani puus kokku ( ) tühje osuti välju.
(A) 2m-1 (B)2m (C)2m+1 (D)4m
3. Kui järjestikuse silmuse järjekorra Q[0:M-1] pea- ja saba osutid on vastavalt F ja R, siis pea osuti F osutab alati peaelemendi eelmisele asukohale ja saba osuti R alati saba elemendi praegusele asukohale, siis silmusjärjekorra elementide arv on ( ).
(A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M
4. Kui binaarpuu keskmise järgu läbimisjärjestus on ABCD ja eelmine järjestuse läbimine on CABD, siis binaarpuu järgmises järjekorras liikumisel saadud järjestus on ().
(A) BADC (B) BCDA (C) CDAB (D) CBDA
5. Oletame, et täiesti suunamata graafis on n tippu, siis on ( ) servasid täiesti suunamata graafis.
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
6. Oletame, et binaarpuus on 2000 sõlme, siis binaarpuu minimaalne kõrgus on ( ).
(A) 9 (B) 10 (C) 11 (D) 12
7. Oletame, et suunatud graafis on n tippu, siis on ( ) päisõlmed naabertabelis, mis vastavad suunatud graafile.
(A) n-1 (B) n (C) n+1 (D) 2n-1
8. Sea algsete kirjete märksõnajadade komplekt (5, 2, 6, 3, 8) ja kiire sorteerimise tulemus esimese kirje märksõna 5 põhjal on ( ).
(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. Täida lüngad (24 punkti)
1. HASH-otsingu tehnoloogia tõhusaks rakendamiseks tuleb lahendada kaks probleemi: ____________________ ja __________________________.
2. Järgmise programmi segmendi funktsioon realiseerib andmed x virna ja nõuab õige lause täitmist allajoonis.
typedefstruct {int s[100]; int top; } sqstack;
Void Push(sqstack&stack,int x)
{
if (stack.top==m-1) printf("ülevool");
else {____________________; _________________; }
}
3. Jada, mis saadakse binaarse sorteerimispuu läbimisel keskmises järjekorras, on ___________ järjestus (täidetud järjestatud või järjestamata).
4. Kiire sorteerimise halvim ajakompleksus on ___________ ja keskmine ajakeerukus on __________.
5. Kui binaarpuus on sõlmede arv, mille aste on 0, on N0 ja sõlmede arv, mille aste on 1, on N1, siis binaarpuus on sõlmede arv, mille aste on 2, _________; Kui binaarpuu salvestusstruktuurina kasutatakse binaarset lingitud loendit, on binaarpuus _______ tühja osuti välja.
6. Oletame, et teatud suunamata graafi tippude ja servade arv on vastavalt n ja e ning kõigi tippude astmete summa on d, siis e = _______.
7. Kui algne kirje märksõnajada on (55, 63, 44, 38, 75, 80, 31, 56), siis sõelumismeetodi poolt määratud algne kuhja on ___________________________.
8. On teada, et suunatud graafi naabertabeli salvestusstruktuur on järgmine: Tipust 1 on DFS-liikumise väljundjärjestus järgmine:
, BFS-i läbimise väljundjärjestus on
Andmestruktuuri artikkel (3)
1. Valikvastustega küsimused (1 punkt küsimuse kohta, kokku 20 punkti)
1. Kui andmestruktuuri binaarne vorm on väljendatud kujul 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>}, siis on andmestruktuur A ( ).
(A) Lineaarne struktuur (B) Puustruktuur (C) Füüsiline struktuur (D) Graafiline struktuur
2. Järgmise programmi ajakompleks on ()
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. Sea osuti muutuja p osutama sõlmele A ühes lingitud loendis, kui kustutad sõlme A ühest lingitud loendist, pead muutma osuti operatsioonijärjestuse ().
(A) q=p->next; p->andme=q->andmed; p->next=q->next; vaba(q);
(B) q=p->järgmine; q->andme=p->andmed; p->next=q->next; vaba(q);
(C) q=p->next; p->next=q->next; vaba(q);
(D) q=p->järgmine; p->andme=q->andmed; vaba(q);
4. Kui on n kirje märksõna, mida sorteerida, ( ) kuhja sorteerimisel on vaja abikirje ühikuid.
(A) 1 (B) n (C) nlog2n (D) n2
5. Kui algsed märksõnakirje märksõnad on (20, 15, 14, 18, 21, 36, 40, 10), siis tulemus pärast kiiret sorteerimist, mis on märgitud 20 võrdluspunktiga, on ( ).
(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. Oletame, et binaarsortimispuus on n sõlme, siis binaarsorteerimispuu keskmine otsingupikkus on ( ).
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7. Oletame, et suunamata graafis G on n tippu e serva, siis vastava külgnemistabeli päisõlmede ja tabelisõlmede arv on ( ).
(A) n,e (B) e,n (C) 2n,e (D) n,2e
8. Oletame, et tugevas ühendusgraafis on n tippu, siis on tugeva ühenduse graafis vähemalt ( ) serva.
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9. Sorteerida tuleb 5000 kirje märksõna, kui vajad kõige kiiremat meetodit kõige väiksemate 10 kirje märksõnade valimiseks, saad selle eesmärgi saavutamiseks kasutada järgmist ( ) meetodit.
(A) Kiire sorteerimine (B) Kuhjade sorteerimine (C) Ühenda sort (D) Sisesta sorteerimine
10. Järgmised neli tüüpi ( ) on suurima ruumilise keerukusega.
(A) Sisestussorteerimine (B) Mullitamise sorteerimine (C) Kuhjade sorteerimine (D) Ühendamise sorteerimine
2. Täida tühimikud (1 punkt tühiku kohta, kokku 20 punkti)
1. Andmete füüsiline struktuur hõlmab peamiselt kahte olukorda: _____________ ja ______________.
2. Kui täielikus binaarpuus on 500 sõlme, on binaarpuu sügavus __________; Kui kasutada binaarset lingitud nimekirja täielikult binaarse puu salvestusstruktuurina, on ___________ tühje osuti välju.
3. Kui sisendjärjestus on 1, 2, 3, siis saab pärast virna tegevust saada ___________ erinevat väljundjärjestust.
4. Kui graafi G salvestusstruktuurina kasutatakse naabermaatriksit A[n][n], siis on kõigi elementide summa reas i tipu i summa võrdne tipu i ________-ga ning kõigi elementide summa veerus i on võrdne tipu i ________-ga.
5. Kui Huffmani puus on n sõlme, siis on ________ sõlme, mille aste on 1.
6. Kui suunagraafis G on n tippu e suunaservadega ja kõigi astmetesse sisenevate tippude summa on d, siis e ja d vaheline seos on _________.
7. __________ binaarse sorteerimispuu sõlmede läbimine võimaldab saada märksõnade järkjärgulise jada (täidetud, keskmine või tagumine).
8. Kui otsingutabelis on 100 elementi, siis kui kasutad dikotoomset otsingumeetodit andmeelemendi X leidmiseks, tuleb seda võrrelda kuni ________ korda, et määrata, kas andmeelement X on otsingutabelis.
9. Olgu tegemist järjestikuse salvestusstruktuuriga virna või ahela salvestusstruktuuriga virnaga, virnasiseste ja väliste operatsioonide ajakeerukus on ____________.
10. Täielik binaarpuu, millel on n sõlme, kui nummerdada ülevalt alla ja vasakult paremale alates 1-st, on i-nda sõlme vanemasõlm nummerdatud ____________ ja parema lapssõlme number on ___________.
11. Kui registreeritud märksõnade algne hulk on (72, 73, 71, 23, 94, 16, 5), siis kiire sorteerimise tulemus kirje märksõna 72 põhjal on ___________________________.
12. Kui suunagraafis G E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>}, siis on graafi topoloogiline jada ____________________.
13. Järgmine algoritm rakendab järjestikuses räsi loendis märksõna väärtusega x, palun täida allkriipsu õige väide.
struct record{int key; int teised; };
inthashsqsearch(struct kirje hashtable[ ],int k)
{
inti,j; j=i=k % p;
while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; kui (i==j) return(-1); }
kui (_______________________ ) return(j); else return(-1);
}
14. Järgmine algoritm rakendab võtmeväärtust k binaarsorteerimispuus, palun täida õige väide allkriipsu.
typedefstruct node{int key; struct sõlm *lchild; struct sõlm *rchild; }bitree;
bitree *bstsearch(bitree *t, int k)
{
kui (t==0) return(0); else while (t!=0)
if (t->key==k)_____________; else if (t->võti>k) t=t->lchild; else_____________;
}
Andmestruktuuri testpaber (1) Vaata vastust
1. Valikvastustega küsimused (2 punkti küsimuse kohta, kokku 20 punkti)
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
2. Täida tühimikud (1 punkt tühiku kohta, kokku 26 punkti)
1. Korrektsus, loetavus, tugevus ja kõrge efektiivsus
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. Suunatud ja mitte-vooluring
8.n(n-1)/2 n(n-1)
9.（12，40） （ ） （74） （23,55，63）
10. Lisa 1
11.O(log2n) O(nlog2n)
12. Konsolideerimine
Vastuseid teistele testiküsimustele on näha:
Turistid, kui soovite näha selle postituse peidetud sisu, palun Vastuse
|
Postitatud 25.11.2014 12:46:30
|
|
|
Postitatud 30.12.2014 00:10:55