Lucrare despre structura datelor (1)
1. Întrebări grilă multiplă (2 puncte pe întrebare, 20 de puncte în total)
1. Caracteristicile comune ale stivelor și cozilor sunt ( ).
A. Permite inserarea și ștergerea elementelor doar la capătul final
B. Toți primul intrat, ultimul eliminat
C. Totul este primul intrat, primul eliminat
D. Nu există un teren comun
2. Coada stocată într-un mod legat este inserată atunci când se efectuează operația de inserție ( ).
A. Doar indicatorul de cap este modificat B. Indicatorii de cap și coadă trebuie modificați
C. Modificați doar pointerul de coadă D. Pointerii de cap și coadă pot necesita modificări
3. Care dintre următoarele structuri de date este o structură neliniară? ( )
A. Coada B. Stiva C. Tabelul liniar D. Arbore binar
4. Dacă există un tablou bidimensional A[m][n], presupunând că A[0][0] este stocat la 644 (10), iar A[2][2] este stocat la 676 (10), fiecare element ocupă un spațiu, unde este stocat A[3][3][3](10)? Nota de subsol (10) indică faptul că este exprimată în zecimal.
A.688 B.678 C.692 D.696
5. Arborii sunt cel mai bine folosiți pentru a reprezenta ( ).
A. Elemente de date ordonate B. Elemente de date neordonate
C. Date cu relații ierarhice ramificate între elemente D. Date fără conexiune între elemente
6. Numărul maxim de noduri în al k-lea strat al arborelui binar este ( ).
A.2k-1 B.2K+1 C.2K-1 D. 2k-1
7. Dacă există un tabel ordonat cu 18 elemente stocate într-un tablou unidimensional A[19], primul element este plasat în A[1], iar acum se efectuează o căutare binară, atunci indicele secvenței de comparație pentru a găsi A[3] este ( )
A. 1,2,3 B. 9,5,2,3
C. 9,5,3 D. 9,4,2,3
8. Sortează rapid fișierele din n înregistrări, iar spațiul de stocare auxiliar necesar este aproximativ același
A. O(1) B. O(n) C. O(1og2n) D. O(n2)
9. Pentru tabelele liniare (7, 34, 55, 25, 64, 46, 20, 10) pentru stocarea hash, dacă H(K)=K %9 este selectată ca funcție hash, există elemente ( ) cu adresa hash de 1.
A.1 B.2 C.3 D.4
10. Un graf neorientat cu 6 noduri, iar graful ar trebui să aibă cel puțin ( ) muchii pentru a asigura un graf conex.
A.5 B.6 C.7 D.8
2. Completează golurile (1 punct per spațiu, 26 puncte în total)
1. Calitatea algoritmului este de obicei evaluată din patru aspecte: _________, _________, _________ și _________.
2. Complexitatea temporală a unui algoritm este (n3+n2log2n+14n)/n2, iar ordinul său de mărime este exprimat ca ________.
3. Presupunând că tabelul generalizat al unui arbore este reprezentat ca A(C,D(E,F,G),H(I,J)), atunci numărul de noduri conținute în arbore este __________, adâncimea arborelui este ___________, iar gradul arborelui este _________.
4. Valoarea formulei sufixului 9 2 3 +- 10 2 / - este __________. Formula sufixului corespunzătoare formulei mijlocii (3+4X)-2Y/3 este _______________________________.
5. Dacă un arbore binar este stocat cu o listă legată, fiecare nod are doi pointeri către copilul stâng și copilul drept, pe lângă câmpul de date. În această structură de stocare, arborele binar cu n noduri are un total de ________ câmpuri pointer, dintre care ________ câmpuri pointeri stochează adrese, iar ________________ pointeri sunt pointeri goali.
6. Pentru un graf orientat și un graf neorientat cu n vârfuri și muchii E-bar, există _______ și ________ noduri de muchie în tabelul său de adiacență corespunzător, respectiv.
7. Rețeaua AOV este un graf ___________________.
8. Într-un graf complet neorientat cu n vârfuri, există ________ muchii, iar într-un graf complet orientat cu n vârfuri, există ________ muchii.
9. Presupunând că un tabel liniar este (12,23,74,55,63,40), dacă elementele aceluiași rest devin un subtabel conform condiției Key % 4, cele patru subtabele obținute sunt ____________________________, ___________________, _______________________ și __________________________.
10. În procesul de inserare a elementelor într-un arbore B_, dacă nodul rădăcină al arborelui este în cele din urmă divizat, înălțimea noului arbore este ___________ decât cea a arborelui original.
11. În procesul de sortare a heap-ului, complexitatea temporală a cernerii oricărui nod de ramură este ________, iar complexitatea de timp a întregului proces de sortare a heap-ului este ________.
12. În sortarea rapidă, sortarea heap-ului și sortarea prin fuziune, sortarea _________ este stabilă.
Lucrare despre structura datelor (2)
1. Întrebări cu răspunsuri multiple (24 de puncte)
1. Următoarea descriere a tabelelor liniare este incorectă ().
(A) Tabelele liniare sunt stocate secvențial și trebuie să ocupe o bucată contiguă de spațiu de stocare
(B) Mesele liniare sunt lanțate și nu ocupă o bucată continuă de spațiu de stocare
(C) Tabelele liniare sunt implementate cu stocare în lanț pentru a facilita operațiunile de inserare și ștergere
(d) Tabelele liniare sunt implementate cu stocare secvențială pentru a facilita operațiunile de inserție și ștergere
2. Să presupunem că numărul total de noduri frunză din arborele Huffman este m, iar dacă se folosește o listă binară legată ca structură de stocare, există un total de ( ) câmpuri pointer goale în arborele Huffman.
(A) 2m-1 (B)2m (C)2m+1 (D)4m
3. Dacă pointerii cap și coadă ai cozii secvențiale de buclă Q[0:M-1] sunt F și R, respectiv, pointerul de cap F indică întotdeauna poziția anterioară a elementului de cap, iar pointerul de coadă R indică întotdeauna poziția curentă a elementului de coadă, atunci numărul de elemente din coada de buclă este ( ).
(A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M
4. Dacă secvența de traversare de ordin mijlociu a unui arbore binar este ABCD, iar secvența anterioară este CABD, atunci secvența obținută prin traversarea arborelui binar în ordinea ulterioară este ().
(A) BADC (B)BCDA (C) CDAB (D) CBDA
5. Să presupunem că există n vârfuri într-un graf complet neorientat, atunci există ( ) muchii în graful complet neorientat.
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
6. Să presupunem că există 2000 de noduri într-un arbore binar, atunci înălțimea minimă a arborelui binar este ( ).
(A) 9 (B) 10 (C) 11 (D) 12
7. Să presupunem că există n vârfuri într-un graf orientat, atunci există ( ) noduri de antet în tabelul de adiacență corespunzător grafului orientat.
(A) n-1 (B) n (C) n+1 (D) 2n-1
8. Setați un set de secvențe inițiale de cuvinte-cheie de înregistrare (5, 2, 6, 3, 8), iar rezultatul unei sortări rapide bazate pe primul cuvânt-cheie de înregistrare 5 este ( ).
(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. Completează golurile (24 de puncte)
1. Pentru a aplica eficient tehnologia de căutare HASH, două probleme care trebuie rezolvate sunt ____________________ și __________________________.
2. Funcția următorului segment de program realizează datele x în stivă și necesită completarea instrucțiunii corecte în subliniere.
typedefstruct {int s[100]; int top; } stack pătrat;
Void push(sqstack&stack,int x)
{
if (stack.top==m-1) printf("overflow");
altfel {____________________; _________________; }
}
3. Secvența obținută prin parcurgerea arborelui binar de sortare în ordinea mijlocie este o secvență ___________ (completată în ordine sau neordonată).
4. Cea mai slabă complexitate temporală a sortării rapide este ___________, iar complexitatea medie de timp este __________.
5. Dacă numărul de noduri cu grad 0 într-un arbore binar este N0 și numărul nodului cu grad 1 este N1, atunci numărul nodurilor cu grad 2 în arborele binar este _________; Dacă o listă binară legată este folosită ca structură de stocare a arborelui binar, există _______ câmpuri de pointer goale în arborele binar.
6. Să presupunem că numărul de vârfuri și muchii dintr-un anumit graf neorientat sunt n și e, respectiv, iar suma gradelor tuturor vârfurilor este d, atunci e = _______.
7. Dacă secvența inițială de cuvinte-cheie a înregistrărilor este (55, 63, 44, 38, 75, 80, 31, 56), atunci grămada inițială stabilită de metoda de screening este ___________________________.
8. Se știe că structura de stocare a tabelului de adiacență a unui graf orientat este următoarea: De la vârful 1, secvența de ieșire a traversării DFS este:
, secvența de ieșire a traversării BFS este
Lucrare despre structura datelor (3)
1. Întrebări cu răspunsuri multiple (1 punct pe întrebare, 20 de puncte în total)
1. Dacă forma binară a unei structuri de date este exprimată ca 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>}, atunci structura de date A este ( ).
(A) Structură liniară (B) Structură arborelui (C) Structură fizică (D) Structură grafică
2. Complexul de timp al următorului program este ()
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. Setați variabila pointer p să indice nodul A într-o singură listă legată, dacă ștergeți nodul A dintr-o singură listă legată, trebuie să schimbați secvența de operații a pointerului la ().
(A) q=p->următorul; p->data=q->data; p->următor=q->următorul; liber(q);
(B) q=p->următor; q->data=p->data; p->următor=q->următorul; liber(q);
(C) q=p->următorul; p->următor=q->următorul; liber(q);
(D) q=p->următorul; p->data=q->data; liber(q);
4. Dacă există n cuvinte-cheie de înregistrare de sortat, ( ) unități auxiliare de înregistrare sunt necesare în sortarea heap-ului.
(A) 1 (B) n (C) nlog2n (D) n2
5. Dacă primele cuvinte cheie înregistrate sunt (20, 15, 14, 18, 21, 36, 40, 10), atunci rezultatul după finalul unui sortare rapidă înregistrat cu 20 ca referință este ( ).
(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. Să presupunem că există n noduri în arborele binar de sortare, atunci lungimea medie a căutării în arborele binar este ( ).
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7. Să presupunem că există n vârfuri e în graful neorientat G, atunci numărul de noduri de antet și noduri de tabel în tabelul de adiacență corespunzător este ( ).
(A) n,e (B) e,n (C) 2n,e (D) n,2e
8. Să presupunem că există n vârfuri într-un graf de conexiune puternică, atunci există cel puțin ( ) muchii în graful conexiunii puternice.
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9. Există 5000 de cuvinte-cheie pentru înregistrări de sortat; dacă trebuie să folosiți cea mai rapidă metodă pentru a selecta cele mai mici 10 cuvinte-cheie de înregistrare, puteți folosi următoarea metodă ( ) pentru a atinge acest scop.
(A) Sortare rapidă (B) Sortare heap (C) Sortare prin fuziune (D) Inserare sortare
10. Următoarele patru tipuri de ( ) au cea mai mare complexitate spațială.
(A) Sortare prin inserție (B) Sortare prin bule (C) Sortare heap (D) Sortare prin combinație
2. Completează golurile (1 punct per gol, 20 de puncte în total)
1. Structura fizică a datelor include în principal două situații: _____________ și ______________.
2. Dacă există 500 de noduri într-un arbore binar complet, adâncimea arborelui binar este __________; Dacă folosești o listă binară legată ca structură de stocare pentru arborele complet binar, există ___________ câmpuri pointer goale.
3. Dacă secvența de intrare este 1, 2, 3, atunci ___________ secvențe diferite de ieșire pot fi obținute după acțiunea stivei.
4. Dacă matricea de adiacență A[n][n] este folosită ca structură de stocare pentru graful G, atunci suma tuturor elementelor de pe rândul i din matricea de adiacență este egală cu ________ vârfului i, iar suma tuturor elementelor de pe coloana i este egală cu ________ vârfului i.
5. Dacă există n noduri în arborele Huffman, există ________ noduri cu grad 1 în arborele Huffman.
6. Dacă există n vârfuri e în graful direcțional G cu muchii direcționale, iar suma tuturor vârfurilor care intră în grade este d, atunci relația dintre e și d este _________.
7. __________ parcurgerea nodurilor din arborele binar de sortare poate obține o secvență incrementală de cuvinte-cheie (umplute, din mijloc sau postere).
8. Dacă există 100 de elemente în tabelul de căutare, dacă folosești metoda de căutare dicotomică pentru a găsi elementul de date X, trebuie să-l compari de până la ________ ori pentru a determina dacă elementul de date X se află în tabelul de căutare.
9. Fie că este vorba de un stack cu o structură de stocare secvențială sau de un stack cu o structură de stocare în lanț, complexitatea temporală a operațiunilor in-stack și out-stack este ____________.
10. Un arbore binar complet cu n noduri, dacă este numerotat în ordine de sus în jos și de la stânga la dreapta începând de la 1, nodul părinte al nodului i-lea este numerotat ____________, iar numărul nodului copil din dreapta este ___________.
11. Dacă setul inițial de cuvinte-cheie înregistrate este (72, 73, 71, 23, 94, 16, 5), atunci rezultatul unei sortări rapide bazate pe cuvântul cheie de înregistrare 72 este ___________________________.
12. Dacă există un set de muchii orientate în graful direcțional G E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>}, atunci o secvență topologică a grafului este ____________________.
13. Următorul algoritm implementează cuvântul cheie cu valoarea x în lista secvențială de hash-uri, vă rugăm să completați instrucțiunea corectă în subliniere.
struct record{int key; în alții; };
inthashsqsearch(hashtable de înregistrare struct[ ],int k)
{
inti,j; j=i=k % p;
în timp ce (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; dacă (i==j) return(-1); }
dacă (_______________________ ) return(j); altfel returnează(-1);
}
14. Următorul algoritm implementează valoarea cheie k în arborele binar de sortare, vă rugăm să completați instrucțiunea corectă în subliniere.
typedefstruct node{int key; nodul struct *lchild; nodul struct *rchild; }bitree;
bitree *bstsearch(bitree *t, int k)
{
dacă (t==0) returnează(0); altfel, în timp ce (t!=0)
dacă (t->cheie==k)_____________; altfel dacă (t->cheie>k) t=t->lchild; else_____________;
}
Lucrare de test pentru structura datelor (1) Consultă răspunsul
1. Întrebări cu răspunsuri multiple (2 puncte pe întrebare, 20 de puncte în total)
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
2. Completează golurile (1 punct per spațiu, 26 puncte în total)
1. Corectitudine, lizibilitate, rezistență și eficiență ridicată
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. Direcțional și non-circuit
8.n(n-1)/2 n(n-1)
9.（12，40） （ ） （74） （23,55，63）
10. Adaugă 1
11.O(log2n) O(nlog2n)
12. Consolidare
Răspunsurile la alte întrebări de test pot fi văzute:
Turiști, dacă vreți să vedeți conținutul ascuns al acestei postări, vă rog Răspunde
|
Postat pe 25.11.2014 12:46:30
|
|
|
Postat pe 30.12.2014 00:10:55