Článok o dátových štruktúrach (1)
1. Otázky s výberom odpovede (2 body za otázku, spolu 20 bodov)
1. Bežné charakteristiky zásobníkov a frontov sú ( ).
A. Povoľte vkladanie a mazanie prvkov iba na koncovom bode
B. Všetci prvý dnu, posledný von.
C. Je to všetko prvý dnu, prvý vonku
D. Neexistuje žiadna spoločná pôda
2. Fronta uložená prepojeným spôsobom sa vkladá pri vykonávaní vkladacej operácie ( ).
A. Iba ukazovateľ hlavy je upravený B. Ukazovátka na hlave a chvoste musia byť upravené
C. Upraviť iba ukazovateľ na chvost D. Ukazovátka na hlave a chvoste môžu byť potrebné upraviť
3. Ktorá z nasledujúcich dátových štruktúr je nelineárna štruktúra? ( )
A. Queue B. Stack C. Lineárna tabuľka D. Binárny strom
4. Ak existuje dvojrozmerné pole A[m][n], za predpokladu, že A[0][0] je uložené na 644 (10) a A[2][2] je uložené na 676 (10), každý prvok zaberá priestor, kde je uložený A[3][3][3][3](10)? Poznámka pod čiarou (10) uvádza, že je vyjadrená v desatinnej časti.
A.688 B.678 C.692 D.696
5. Stromy sa najlepšie používajú na reprezentáciu ( ).
A. Usporiadané dátové prvky B. Neusporiadané dátové prvky
C. Dáta s vetviacimi hierarchickými vzťahmi medzi prvkami D. Dáta bez spojenia medzi prvkami
6. Maximálny počet uzlov v k-tej vrstve binárneho stromu je ( ).
A.2K-1 B.2K+1 C.2K-1 D. 2K-1
7. Ak je usporiadaná tabuľka 18 prvkov uložená v jednorozmernom poli A[19], prvý prvok sa umiestni do A[1] a teraz sa vykoná binárne vyhľadávanie, potom index porovnávacej sekvencie na nájdenie A[3] je ( )
A. 1,2,3 B. 9,5,2,3
C. 9,5,3 D. 9,4,2,3
8. Rýchlo zoradiť súbory n záznamov a potrebný pomocný úložný priestor je približne rovnaký
A. O(1) B. O(n) C. O(1og2n) D. O(n2)
9. Pre lineárne tabuľky (7, 34, 55, 25, 64, 46, 20, 10) na ukladanie hashov, ak je ako hash funkcia zvolené H(K)=K %9, existujú prvky ( ) s hash adresou 1.
A.1 B.2 C.3 D.4
10. Neorientovaný graf so 6 uzlami a graf by mal mať aspoň ( ) hrany, aby sa zabezpečilo prepojenie grafu.
A.5 B.6 C.7 D.8
2. Doplňte medzery (1 bod na prázdne miesto, celkovo 26 bodov)
1. Kvalita algoritmu sa zvyčajne hodnotí zo štyroch aspektov: _________, _________, _________ a _________.
2. Časová zložitosť algoritmu je (n3+n2log2n+14n)/n2 a jeho rád veľkosti sa vyjadruje ako ________.
3. Za predpokladu, že generalizovaná tabuľka stromu je reprezentovaná ako A(C,D(E,F,G),H(I,J)), potom počet uzlov obsiahnutých v strome je __________, hĺbka stromu je ___________ a stupeň stromu je _________.
4. Hodnota formuly prípony 9 2 3 +- 10 2 / - je __________. Príponová formula zodpovedajúca strednej formule (3+4X)-2Y/3 je _______________________________.
5. Ak je binárny strom uložený s prepojeným zoznamom, každý uzol má okrem dátového poľa dva ukazovatele na ľavého a pravého potomka. V tejto štruktúre ukladania má binárny strom s n uzlami celkovo ________ ukazovateľových polí, z ktorých ________ ukazovadla ukladajú adresy a ________________ ukazovatele sú prázdne ukazovatele.
6. Pre orientovaný graf a neorientovaný graf s n vrcholmi a E-barovými hranami je v zodpovedajúcej susednej tabuľke _______ a ________ hrán.
7. AOV sieť je ___________________ graf.
8. V neorientovanom úplnom grafe s n vrcholmi je ________ hrán a v orientovanom úplnom grafe s n vrcholmi je ________ hrán.
9. Za predpokladu, že lineárna tabuľka je (12,23,74,55,63,40), ak sa prvky toho istého zvyšku stanú podtabuľkou podľa podmienky Key % 4, získané štyri podtabuľky sú ____________________________, ___________________, _______________________ a __________________________.
10. Pri vkladaní prvkov do B_ stromu, ak je koreňový uzol stromu nakoniec rozdelený, výška nového stromu je ___________ ako výška pôvodného stromu.
11. Pri procese triedenia haldy je časová náročnosť preosievania akéhokoľvek uzla vetvy ________ a časová náročnosť celého procesu triedenia haldy je ________.
12. Pri rýchlom triedení, triedení haldov a triedení zlúčením je _________ triedenie stabilné.
Článok o dátových štruktúrach (2)
1. Otázky s výberom odpovede (24 bodov)
1. Nasledujúci popis lineárnych tabuliek je nesprávny ().
(A) Lineárne tabuľky sa ukladajú postupne a musia zaberať súvislý úložný priestor
(B) Lineárne tabuľky sú reťazené a nezaberajú súvislý úložný priestor
(C) Lineárne tabuľky sú implementované reťazeným úložiskom na uľahčenie vkladania a mazania
(d) Lineárne tabuľky sú implementované so sekvenčným úložiskom na uľahčenie vkladania a mazania operácií
2. Predpokladajme, že celkový počet listových uzlov v Huffmanovom strome je m, a ak sa ako pamäťová štruktúra použije binárny prepojený zoznam, v Huffmanovom strome je celkovo ( ) prázdnych ukazovateľových polí.
(A) 2m-1 (B)2m (C)2m+1 (D)4m
3. Ak sú ukazovateľ hlavy a chvosta sekvenčnej slučkovej fronty Q[0:M-1] F a R, ukazovateľ hlavy F vždy ukazuje na predchádzajúcu pozíciu hlavného prvku a ukazovateľ na chvost R vždy ukazuje na aktuálnu pozíciu chvostového prvku, potom počet prvkov v slučkovej rade je ( ).
(A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M
4. Ak je stredná postupnosť prechodu binárneho stromu ABCD a predchádzajúca sekvencia prechádzania je CABD, potom postupnosť získaná prechodom binárneho stromu v nasledujúcom poradí je ().
(A) BADC (B)BCDA (C) CDAB (D) CBDA
5. Predpokladajme, že v úplne neorientovanom grafe je n vrcholov, potom v úplne neorientovanom grafe je ( ) hrán.
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
6. Predpokladajme, že v binárnom strome je 2000 uzlov, potom minimálna výška binárneho stromu je ( ).
(A) 9 (B) 10 (C) 11 (D) 12
7. Predpokladajme, že v orientovanom grafe je n vrcholov, potom v tabuľke susedov zodpovedajúcich orientovanému grafu sú ( ) hlavičkové uzly.
(A) n-1 (B) n (C) n+1 (D) 2n-1
8. Nastavte sadu počiatočných sekvencií kľúčových slov záznamu (5, 2, 6, 3, 8) a výsledok rýchleho zoradenia na základe prvého kľúčového slova záznamu 5 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. Doplniť medzery (24 bodov)
1. Aby bolo možné efektívne použiť technológiu vyhľadávania HASH, je potrebné vyriešiť dva problémy: ____________________ a __________________________.
2. Funkcia nasledujúceho segmentu programu realizuje dáta x do zásobníka a vyžaduje vyplnenie správneho príkazu v podčiarknutí.
typedefstruct {int s[100]; int top; } sqstack;
Void push (sqstack&stack, int x)
{
if (stack.top==m-1) printf ("pretečenie");
inak {____________________; _________________; }
}
3. Postupnosť získaná prechodom binárnym triediacim stromom v strednom poradí je ___________ postupnosť (vyplnená usporiadaným alebo neusporiadaným).
4. Najhoršia časová zložitosť rýchleho triedenia je ___________ a priemerná časová zložitosť je __________.
5. Ak je počet uzlov so stupňom 0 v binárnom strome N0 a číslo uzla so stupňom 1 je N1, potom počet uzlov so stupňom 2 v binárnom strome je _________; Ak sa binárny prepojený zoznam použije ako pamäťová štruktúra binárneho stromu, v binárnom strome sú _______ prázdne polia ukazovateľa.
6. Predpokladajme, že počet vrcholov a hrán v určitom neorientovanom grafe je n a e, a súčet stupňov všetkých vrcholov je d, potom e = _______.
7. Ak je počiatočná sekvencia kľúčových slov záznamu (55, 63, 44, 38, 75, 80, 31, 56), potom počiatočná halda vytvorená metódou filtrovania je ___________________________.
8. Je známe, že štruktúra úložiska v tabuľke susedstva orientovaného grafu je nasledovná: Z vrcholu 1 je výstupná sekvencia DFS prechádzania:
, výstupná sekvencia prechodu BFS je
Článok o dátových štruktúrach (3)
1. Otázky s výberom odpovede (1 bod za otázku, spolu 20 bodov)
1. Ak je binárna forma dátovej štruktúry vyjadrená ako 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>}, potom je dátová štruktúra A ( ).
(A) Lineárna štruktúra (B) Stromová štruktúra (C) Fyzická štruktúra (D) Grafická štruktúra
2. Časový komplex nasledujúceho programu 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. Nastavte premennú ukazovateľa p tak, aby ukazovala na uzol A v jednom prepojenom zozname, ak odstránite uzol A v jednom prepojenom zozname, musíte zmeniť poradie operácií ukazovateľa na ().
(A) q=p->ďalší; p->data=q->data; p->next=q->next; free(q);
(B) q=p->ďalší; q->data=p->data; p->next=q->next; free(q);
(C) q=p->ďalší; p->next=q->next; free(q);
(D) q=p->ďalší; p->data=q->data; free(q);
4. Ak je na triedenie n kľúčových slov záznamov, ( ) sú v triedení haldy potrebné pomocné jednotky záznamov.
(A) 1 (B) n (C) nlog2n (D) n2
5. Ak sú počiatočné kľúčové slová záznamu kľúčových slov (20, 15, 14, 18, 21, 36, 40, 10), potom výsledok po skončení rýchleho triedenia zaznamenaný s benchmarkom 20 je ( ).
(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. Predpokladajme, že v binárnom triediacom strome je n uzlov, potom priemerná dĺžka vyhľadávania v binárnom triediacom strome je ( ).
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7. Predpokladajme, že v neorientovanom grafe G je n vrcholových hrán, potom počet uzlov hlavičky a tabuliek v príslušnej susednej tabuľke je ( ).
(A) n,e (B) e,n (C) 2n,e (D) n,2e
8. Predpokladajme, že v grafe silných spojení je n vrcholov, potom v grafe silných spojení je aspoň ( ) hrán.
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9. Existuje 5000 kľúčových slov záznamov, ktoré treba zoradiť, ak potrebujete použiť najrýchlejšiu metódu na výber najmenších 10 kľúčových slov záznamov, môžete použiť nasledujúcu ( ) metódu na dosiahnutie tohto cieľa.
(A) Rýchle zoradenie (B) Triedenie haldy (C) Zlúčenie triedenia (D) Vloženie triedenia
10. Nasledujúce štyri druhy ( ) majú najväčšiu priestorovú zložitosť.
(A) Triedenie vkladaním (B) Triedenie bublinkami (C) Triedenie haldy (D) Triedenie zlúčením
2. Doplňte medzery (1 bod na prázdne miesto, spolu 20 bodov)
1. Fyzická štruktúra dát zahŕňa najmä dve situácie: _____________ a ______________.
2. Ak je v úplnom binárnom strome 500 uzlov, hĺbka binárneho stromu je __________; Ak použijete binárny prepojený zoznam ako štruktúru úložiska pre plne binárny strom, sú tam ___________ prázdne ukazovacie polia.
3. Ak je vstupná sekvencia 1, 2, 3, potom je možné získať ___________ rôzne výstupné sekvencie po akcii zásobníka.
4. Ak sa ako pamäťová štruktúra pre graf G použije matica susedstva A[n][n], potom súčet všetkých prvkov v riadku i v matici susednosti je rovný ________ vrcholu i a súčet všetkých prvkov v stĺpci i je rovný ________ vrcholu i.
5. Ak je v Huffmanovom strome n uzlov, v Huffmanovom strome je ________ uzlov so stupňom 1.
6. Ak je v smerovom grafe G n vrcholov e s smerovými hranami a súčet všetkých vrcholov vstupujúcich do stupňov je d, potom vzťah medzi e a d je _________.
7. __________ prechádzaním uzlov v binárnom triediacom strome môže získať postupnú sekvenciu kľúčových slov (vyplnených, stredných alebo zadných).
8. Ak je v tabuľke vyhľadávania 100 prvkov, ak použijete dichotomickú metódu vyhľadávania na nájdenie dátového prvku X, musíte ho porovnať až ________-krát, aby ste zistili, či sa dátový prvok X nachádza v tabuľke vyhľadávania.
9. Či už ide o stack so sekvenčnou úložnou štruktúrou alebo stack so štruktúrou reťazového úložiska, časová náročnosť operácií v rámci a out-stacku je ____________.
10. Kompletný binárny strom s n uzlami, ak je očíslovaný zhora nadol a zľava doprava od 1, rodičovský uzol i-tého uzla je očíslovaný ____________ a číslo pravého potomka je ___________.
11. Ak je počiatočná množina zaznamenaných kľúčových slov (72, 73, 71, 23, 94, 16, 5), potom výsledok rýchleho zoradenia založeného na kľúčovom slove záznamu 72 je ___________________________.
12. Ak existuje množina orientovaných hrán v smerovom grafe G E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>}, potom je topologická postupnosť grafu ____________________.
13. Nasledujúci algoritmus implementuje kľúčové slovo s hodnotou x v sekvenčnom zozname hashov, prosím, vyplňte správne vyjadrenie v podčiarknutí.
struct record{int key; int others; };
inthashsqsearch(hashtable štruktúrneho záznamu[ ],int k)
{
inti,j; j=i=k % p;
zatiaľ čo (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; ak (i==j) return(-1); }
ak (_______________________ ) vráť(j); else return(-1);
}
14. Nasledujúci algoritmus implementuje kľúčovú hodnotu k v binárnom triediacom strome, prosím, vyplňte správne vyjadrenie v podčiarknutí.
typedefstruct node{int key; struct node *lchild; struct node *rchild; }bitree;
bitree *bstsearch(bitree *t, int k)
{
ak (t==0 ) return(0); Inak keď (t!=0)
ak (t->key==k)_____________; inak ak (t->key>k) t=t->lchild; else_____________;
}
Testová práca o dátovej štruktúre (1) Pozri odpoveď
1. Otázky s výberom odpovede (2 body za otázku, spolu 20 bodov)
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
2. Doplňte medzery (1 bod na prázdne miesto, celkovo 26 bodov)
1. Správnosť, čitateľnosť, pevnosť a vysoká účinnosť
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. Smerové a neobvodové
8.n(n-1)/2 n(n-1)
9.（12，40） （ ） （74） （23,55，63）
10. Pridaj 1
11.O(log2n) O(nlog2n)
12. Konsolidácia
Odpovede na ďalšie testovacie otázky si môžete pozrieť:
Turisti, ak chcete vidieť skrytý obsah tohto príspevku, prosím. Odpoveď
|
Zverejnené 25. 11. 2014 12:46:30
|
|
|
Zverejnené 30. 12. 2014 0:10:55