Článek o datových strukturách (1)
1. Otázky s výběrem odpovědí (2 body za otázku, celkem 20 bodů)
1. Běžné charakteristiky zásobníků a front jsou ( ).
A. Povolit vkládání a mazání prvků pouze na koncovém bodu
B. Všichni první dovnitř, poslední ven
C. Je to všechno první dovnitř, ten první ven
D. Neexistuje žádná společná půda
2. Fronta uložená v propojeném způsobu je vložena při provádění vkládací operace ( ).
A. Pouze ukazatel hlavy je upraven B. Ukazatele hlavy a ocasu musí být upraveny
C. Upravit pouze ukazatel na ocas, D. Ukazatele na hlavě a ocasu mohou být nutné upravit
3. Která z následujících datových struktur je nelineární struktura? ( )
A. Fronta B. Zásobník C. Lineární tabulka D. Binární strom
4. Pokud existuje dvourozměrné pole A[m][n], za předpokladu, že A[0][0] je uloženo na 644 (10) a A[2][2] na 676 (10), každý prvek zabírá místo, kde je uloženo A[3][3][3][3](10)? Poznámka pod čarou (10) uvádí, že je vyjádřena v desetinné části.
A.688 B.678 C.692 D.696
5. Stromy jsou nejlepší pro reprezentaci ( ).
A. uspořádané datové prvky B. Neuspořádané datové prvky
C. Data s větvícími se hierarchickými vztahy mezi prvky D. Data bez spojení mezi prvky
6. Maximální počet uzlů v k-té vrstvě binárního stromu je ( ).
A.2K-1 B.2K+1 C.2K-1 D. 2K-1
7. Pokud je uspořádaná tabulka 18 prvků uložena v jednorozměrném poli A[19], první prvek je umístěn do A[1] a nyní se provádí binární vyhledávání, pak index porovnávací sekvence pro nalezení A[3] je ( )
A. 1,2,3 B. 9,5,2,3
C. 9,5,3 D. 9,4,2,3
8. Rychle seřadit soubory n záznamů a potřebný pomocný úložný prostor je přibližně stejný
A. O(1) B. O(n) C. O(1og2n) D. O(n2)
9. Pro lineární tabulky (7, 34, 55, 25, 64, 46, 20, 10) pro ukládání hashů, pokud je jako hash funkce zvoleno H(K)=K %9, existují prvky ( ) s hashovací pomocí 1.
A.1 B.2 C.3 D.4
10. Neorientovaný graf se 6 uzly, a graf by měl mít alespoň ( ) hrany, aby byl zajištěn souvislý graf.
A.5 B.6 C.7 D.8
2. Doplňte mezery (1 bod na prázdné místo, celkem 26 bodů)
1. Kvalita algoritmu se obvykle hodnotí ze čtyř aspektů: _________, _________, _________ a _________.
2. Časová složitost algoritmu je (n3+n2log2n+14n)/n2 a jeho řád velikosti je vyjádřen jako ________.
3. Za předpokladu, že zobecněná tabulka stromu je reprezentována jako A(C,D(E,F,G),H(I,J)), pak počet uzlů ve stromu je __________, hloubka stromu je ___________ a stupeň stromu je _________.
4. Hodnota příponového vzorce 9 2 3 +- 10 2 / - je __________. Příponový vzorec odpovídající prostřední formuli (3+4X)-2Y/3 je _______________________________.
5. Pokud je binární strom uložen s propojeným seznamem, každý uzel má kromě datového pole dva ukazatele na levého a pravého potomka. V této struktuře úložiště má binární strom s n uzly celkem ________ ukazatelových polí, z nichž ________ ukazatelová pole uchovávají adresy a ________________ ukazatele jsou prázdné ukazatele.
6. Pro orientovaný graf a neorientovaný graf s n vrcholy a E-barovými hranami existuje v odpovídající sousední tabulce _______ a ________ hran.
7. AOV síť je ___________________ graf.
8. V neorientovaném úplném grafu s n vrcholy je ________ hran a v orientovaném úplném grafu s n vrcholy je ________ hran.
9. Za předpokladu, že lineární tabulka je (12,23,74,55,63,40), pokud se prvky stejného zbytku stanou podtabulkou podle podmínky Key % 4, získané čtyři podtabulky jsou ____________________________, ___________________, _______________________ a __________________________.
10. Při vkládání prvků do B_ stromu, pokud je kořenový uzel stromu nakonec rozdělen, je výška nového stromu ___________ než výška původního stromu.
11. Při třídění haldy je časová složitost prosítání libovolného uzlu větve ________ a časová složitost celého procesu třídění haldy je ________.
12. Při rychlém třídění, třídění haldami a seřazení sloučením je _________ třídění stabilní.
Článek o datových strukturách (2)
1. Otázky s výběrem z odpovědi (24 bodů)
1. Následující popis lineárních tabulek je nesprávný ().
(A) Lineární tabulky jsou ukládány postupně a musí zabírat souvislý úložný prostor
(B) Lineární tabulky jsou řetězené a nezabírají souvislý úložný prostor
(C) Lineární tabulky jsou implementovány s řetězeným úložištěm pro usnadnění vkládání a mazání operací
(d) Lineární tabulky jsou implementovány se sekvenčním úložením pro usnadnění vkládání a mazání operací
2. Předpokládejme, že celkový počet listových uzlů v Huffmanově stromu je m, a pokud je jako paměťová struktura použita binární propojená seznam, je v Huffmanově stromu celkem ( ) prázdných ukazatelových polí.
(A) 2m-1 (B)2m (C)2m+1 (D)4m
3. Pokud jsou ukazatele na hlavě a ocasu sekvenční smyčky Q[0:M-1] F a R, ukazatel hlavy F vždy ukazuje na předchozí pozici hlavního prvku a ukazatel na ocasní R vždy ukazuje na aktuální pozici ocasního prvku, pak počet prvků ve frontě smyčky je ( ).
(A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M
4. Pokud je střední posloupnost procházení binárního stromu ABCD a předchozí sekvence procházení je CABD, pak posloupnost získaná procházením binárního stromu v následujícím pořadí je ().
(A) BADC (B)BCDA (C) CDAB (D) CBDA
5. Předpokládejme, že v zcela neorientovaném grafu je n vrcholů, pak v zcela neorientovaném grafu jsou ( ) hrany.
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
6. Předpokládejme, že v binárním stromu je 2000 uzlů, pak minimální výška binárního stromu je ( ).
(A) 9 (B) 10 (C) 11 (D) 12
7. Předpokládejme, že v orientovaném grafu je n vrcholů, pak v tabulce sousedství odpovídajících orientovanému grafu jsou ( ) hlavičkové uzly.
(A) n-1 (B) n (C) n+1 (D) 2n-1
8. Nastavte sadu počátečních sekvencí klíčových slov záznamu (5, 2, 6, 3, 8) a výsledek rychlého seřazení na základě prvního klíč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. Doplnit mezery (24 bodů)
1. Pro efektivní použití HASH vyhledávací technologie je třeba vyřešit dva problémy: ____________________ a __________________________.
2. Funkce následujícího segmentu programu realizuje data x do zásobníku a vyžaduje vyplnění správného příkazu v podtržení.
typedefstruct {int s[100]; int top; } sqstack;
Void Push (sqstack&stack, int x)
{
if (stack.top==m-1) printf ("přetečení");
jinak {____________________; _________________; }
}
3. Posloupnost získaná procházením binárního třídicí stromu ve středním řádu je ___________ posloupnost (vyplněná v pořadí nebo neuspořádané).
4. Nejhorší časová složitost rychlého třídění je ___________ a průměrná časová složitost je __________.
5. Pokud je počet uzlů se stupněm 0 v binárním stromu N0 a číslo uzlů se stupněm 1 je N1, pak počet uzlů se stupněm 2 v binárním stromu je _________; Pokud je binární propojený seznam použit jako paměťová struktura binárního stromu, v binárním stromu jsou _______ prázdná ukazatelová pole.
6. Předpokládejme, že počet vrcholů a hran v určitém neorientovaném grafu je n a e, respektive, a součet stupňů všech vrcholů je d, pak e = _______.
7. Pokud je počáteční sekvence klíčových slov záznamu (55, 63, 44, 38, 75, 80, 31, 56), pak počáteční halda vytvořená metodou screeningu je ___________________________.
8. Je známo, že struktura úložiště tabulky sousedství orientovaného grafu je následující: Z vrcholu 1 je výstupní sekvence DFS procházení:
, výstupní sekvence průchodu BFS je
Článek o datových strukturách (3)
1. Otázky s výběrem z odpovědi (1 bod za otázku, celkem 20 bodů)
1. Pokud je binární forma datové struktury vyjádřena jako 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>}, pak je datová struktura A ( ).
(A) Lineární struktura (B) Stromová struktura (C) Fyzická struktura (D) Grafická struktura
2. Časový komplex následujícího 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 ukazatelovou proměnnou p tak, aby ukazovala na uzel A v jednom propojeném seznamu, pokud odstraníte uzel A v jednom propojeném seznamu, musíte změnit pořadí operací ukazatele na ().
(A) q=p->další; p->data=q->data; p->další=q->další; free(q);
(B) q=p->další; q->data=p->data; p->další=q->další; free(q);
(C) q=p->další; p->další=q->další; free(q);
(D) q=p->další; p->data=q->data; free(q);
4. Pokud je k třídění n klíčových slov záznamů, ( ) jsou v třídění haldy vyžadovány pomocné jednotky záznamů.
(A) 1 (B) n (C) nlog2n (D) n2
5. Pokud jsou počáteční klíčová slova (20, 15, 14, 18, 21, 36, 40, 10), pak výsledek po skončení rychlého třídění zaznamenaný s 20 jako benchmarkem 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. Předpokládejme, že v binárním stromu je n uzlů, pak průměrná délka vyhledávání v binárním stromu je ( ).
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7. Předpokládejme, že v neorientovaném grafu G je n vrcholových e hran, pak počet uzlů hlaviček a uzlů tabulky v odpovídající sousední tabulce je ( ).
(A) n,e (B) e,n (C) 2n,e (D) n,2e
8. Předpokládejme, že v grafu silných spojení je n vrcholů, pak v grafu silných spojení existuje alespoň ( ) hran.
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9. Existuje 5000 klíčových slov záznamů, které je třeba třídit, pokud potřebujete použít nejrychlejší metodu výběru nejmenších 10 klíčových slov záznamu, můžete k tomu dosáhnout následujícím ( ) způsobem.
(A) Rychlé seřazení (B) Třídění haldy (C) Sloučení třídění (D) Vložení třídění
10. Následující čtyři druhy ( ) mají největší prostorovou složitost.
(A) Třídění vložením (B) Bublinkové třídění (C) Třídění haldy (D) Třídění sloučením
2. Doplňte mezery (1 bod za jedno místo, celkem 20 bodů)
1. Fyzická struktura dat zahrnuje především dvě situace: _____________ a ______________.
2. Pokud je v úplném binárním stromu 500 uzlů, hloubka binárního stromu je __________; Pokud použijete binární propojený seznam jako paměťovou strukturu pro plně binární strom, zůstávají ___________ prázdná ukazatelová pole.
3. Pokud je vstupní sekvence 1, 2, 3, lze získat ___________ různých výstupních sekvencí po akci zásobníku.
4. Pokud je matice sousedství A[n][n] použita jako paměťová struktura pro graf G, pak součet všech prvků v řádku i v matici sousedství je roven ________ vrcholu i a součet všech prvků ve sloupci i je roven ________ vrcholu i.
5. Pokud je v Huffmanově stromu n uzlů, je v Huffmanově stromu ________ uzlů se stupněm 1.
6. Pokud je v směrovém grafu G n vrcholů e s směrovými hranami a součet všech vrcholů vstupujících do stupňů je d, pak je vztah mezi e a d _________.
7. __________ procházení uzlů v binárním třídicí stromu může získat inkrementální sekvenci klíčových slov (vyplněných, prostředních nebo posteriorních).
8. Pokud je v tabulce vyhledávání 100 prvků, pokud použijete dichotomickou metodu vyhledávání k nalezení datového prvku X, musíte jej porovnat až ________krát, abyste zjistili, zda se datový prvek X nachází ve vyhledávání.
9. Ať už jde o stack se sekvenční úložnou strukturou, nebo stack s řetězovou strukturou úložiště, časová složitost operací uvnitř a ven zásobníku je ____________.
10. Kompletní binární strom s n uzly, pokud je číslován shora dolů dolů a zleva doprava od 1, mateřský uzel i-tého uzlu je očíslován ____________ a číslo pravého poduzlu je ___________.
11. Pokud je počáteční množina zaznamenaných klíčových slov (72, 73, 71, 23, 94, 16, 5), pak je výsledek rychlého seřazení založený na klíčovém slově záznamu 72 ___________________________.
12. Pokud existuje množina orientovaných hran v směrovém grafu G E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>}, pak je topologická posloupnost grafu ____________________.
13. Následující algoritmus implementuje klíčové slovo s hodnotou x v sekvenčním seznamu hashů, prosím vyplňte správné tvrzení v podtržítku.
struct record{int key; int others; };
inthashsqsearch(hashtable záznamu struktur[ ],int k)
{
inti,j; j=i=k % p;
zatímco (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; pokud (i==j) return(-1); }
pokud (_______________________ ) vrať(j); jinak return(-1);
}
14. Následující algoritmus implementuje klíčovou hodnotu k v binárním třídicím stromu, prosím vyplňte správné tvrzení v podtržítku.
typedefstruct node{int key; Struct node *lchild; struct node *rchild; }bitree;
Bitree *bstsearch(bitree *t, int k)
{
pokud (t==0 ) return(0); Jinak zatímco (t!=0)
pokud (t->klíč==k)_____________; Jinak pokud (t->key>k) t=t->lchild; else_____________;
}
Testovací práce o datové struktuře (1) Viz odpověď
1. Otázky s výběrem odpovědí (2 body za otázku, celkem 20 bodů)
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
2. Doplňte mezery (1 bod na prázdné místo, celkem 26 bodů)
1. Správnost, čitelnost, pevnost a vysoká účinnost
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. Směrové a neokruhové
8.n(n-1)/2 n(n-1)
9.（12，40） （ ） （74） （23,55，63）
10. Přidej 1
11.O(log2n) O(nlog2n)
12. Konsolidace
Odpovědi na další testové otázky jsou k dispozici:
Turisté, pokud chcete vidět skrytý obsah tohoto příspěvku, prosím Odpověď
|
Zveřejněno 25.11.2014 12:46:30
|
|
|
Zveřejněno 30.12.2014 0:10:55