Datu struktūras dokuments (1)
1. Jautājumi ar atbilžu variantiem (2 punkti par jautājumu, kopā 20 punkti)
1. Skursteņu un rindu kopīgās īpašības ir ( ).
A. Atļaut ievietot un dzēst elementus tikai galapunktā
B. Visi pirmie iekšā, pēdējie
C. Tas viss ir pirmais iekšā, pirmais ārā
D. Nav kopīga pamata
2. Saistītā veidā saglabātā rinda tiek ievietota, veicot ievietošanas darbību ( ).
A. Tiek modificēts tikai galvas rādītājs B. Jāmaina galvas un astes rādītāji
C. Modificējiet tikai astes rādītāju D. Galvas un astes rādītāji var būt jāmaina
3. Kura no šīm datu struktūrām ir nelineāra struktūra? ( )
A. Rinda B. Kaudze C. Lineārā tabula D. Binārais koks
4. Ja ir divdimensiju masīvs A[m][n], pieņemot, ka A[0][0] tiek glabāts 644 (10) un A[2][2] tiek glabāts 676 (10), katrs elements aizņem vietu, kur tiek glabāts A[3][3][3](10)? 10. zemsvītras piezīmē norādīts, ka tas ir izteikts decimāldaļā.
A.688 B.678 C.692 D.696
5. Kokus vislabāk izmantot, lai attēlotu ( ).
A. Sakārtoti datu elementi B. Nesakārtoti datu elementi
C. Dati ar sazarotām hierarhiskām attiecībām starp elementiem D. Dati bez savienojuma starp elementiem
6. Maksimālais mezglu skaits binārā koka k-tajā slānī ir ( ).
A.2k-1 B.2K+1 C.2K-1 D. 2k-1
7. Ja viendimensiju masīvā A[19] ir sakārtota tabula ar 18 elementiem, pirmais elements tiek ievietots A[1], un tagad tiek veikta binārā meklēšana, tad salīdzināšanas secības apakšraksts, lai atrastu A[3], ir ( )
A. 1,2,3 B. 9,5,2,3
C. 9,5,3 D. 9,4,2,3
8. Ātri kārtojiet n ierakstu failus, un nepieciešamā papildu krātuves vieta ir aptuveni tāda pati
A. O(1) B. O(n) C. O(1og2n) D. O(n2)
9. Lineārajām tabulām (7, 34, 55, 25, 64, 46, 20, 10) jaucējfunkcijai, ja H(K)=K %9 ir atlasīta kā jaucējfunkcija, ir ( ) elementi ar jaucējkodu adresi 1.
A.1 B.2 C.3 D.4
10. Nevirzīts grafiks ar 6 mezgliem, un grafikam jābūt vismaz ( ) malām, lai nodrošinātu savienotu grafiku.
A.5 B.6 C.7 D.8
2. Aizpildiet tukšās vietas (1 punkts par tukšo vietu, kopā 26 punkti)
1. Algoritma kvalitāte parasti tiek novērtēta no četriem aspektiem: _________, _________, _________ un _________.
2. Algoritma laika sarežģītība ir (n3+n2log2n+14n)/n2, un tā lieluma secība ir izteikta kā ________.
3. Pieņemot, ka koka vispārinātā tabula ir attēlota kā A(C,D(E,F,G),H(I,J)), tad kokā esošo mezglu skaits ir __________, koka dziļums ir ___________ un koka pakāpe ir _________.
4. Sufiksa formulas 9 2 3 +- 10 2 / - vērtība ir __________. Sufiksa formula, kas atbilst vidējai formulai (3+4X)-2Y/3, ir _______________________________.
5. Ja binārais koks tiek glabāts ar saistītu sarakstu, katram mezglam papildus datu laukam ir divi rādītāji uz kreiso un labo bērnu. Šajā krātuves struktūrā binārajam kokam ar n mezgliem ir ________ rādītāju lauki, no kuriem ________ rādītāju lauki glabā adreses un ________________ rādītāji ir tukši rādītāji.
6. Virzītam grafikam un nevirzītam grafikam ar n virsotnēm un E-joslas malām attiecīgajā blakus tabulā ir attiecīgi _______ un ________ malu mezgli.
7. AOV tīkls ir ___________________ grafiks.
8. Nevirzītā pilnīgā grafikā ar n virsotnēm ir ________ malas, un virzītā pilnīgā grafikā ar n virsotnēm ir ________ malas.
9. Pieņemot, ka lineārā tabula ir (12,23,74,55,63,40), ja viena un tā paša atlikuma elementi kļūst par apakštabulu saskaņā ar nosacījumu Key % 4, iegūtās četras apakštabulas ir ____________________________, ___________________, _______________________ un __________________________.
10. Ievietojot elementus B_ kokā, ja koka saknes mezgls beidzot tiek sadalīts, jaunā koka augstums ir ___________ nekā sākotnējā koka.
11. Kaudzes šķirošanas procesā tiek ________ jebkura filiāles mezgla sijāšanas laika sarežģītība, un visa kaudzes šķirošanas procesa laika sarežģītība ir ________.
12. Ātrā šķirošanā, kaudzes šķirošanā un sapludināšanas kārtošanā _________ kārtošana ir stabila.
Datu struktūras dokuments (2)
1. Jautājumi ar atbilžu variantiem (24 punkti)
1. Šāds lineāro tabulu apraksts ir nepareizs ().
(A) Lineārās tabulas tiek glabātas secīgi, un tām jāaizņem blakus esoša glabāšanas vieta
(B) Lineārie galdi ir saķēdēti un neaizņem nepārtrauktu uzglabāšanas vietu
(C) Lineārās tabulas tiek ieviestas ar ķēdes glabāšanu, lai atvieglotu ievietošanas un dzēšanas operācijas
(d) Lineārās tabulas tiek ieviestas ar secīgu glabāšanu, lai atvieglotu ievietošanas un dzēšanas operācijas
2. Pieņemsim, ka kopējais lapu mezglu skaits Huffman kokā ir m, un, ja binārais saistītais saraksts tiek izmantots kā glabāšanas struktūra, Huffman kokā ir kopumā ( ) tukši rādītāja lauki.
(A) 2m-1 (B)2m (C)2m+1 (D)4m
3. Ja secīgās cilpas rindas Q[0:M-1] galvas un astes rādītāji ir attiecīgi F un R, galvas rādītājs F vienmēr norāda uz galvas elementa iepriekšējo pozīciju, un astes rādītājs R vienmēr norāda uz astes elementa pašreizējo pozīciju, tad elementu skaits cilpas rindā ir ( ).
A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M
4. Ja binārā koka vidējās kārtas šķērsošanas secība ir ABCD un iepriekšējā secības šķērsošanas secība ir CABD, tad secība, kas iegūta, šķērsojot bināro koku nākamajā secībā, ir ().
(A) BADC (B) BCDA (C) CDAB (D) CBDA
5. Pieņemsim, ka pilnīgi nevirzītā grafikā ir n virsotnes, tad pilnīgi nevirzītajā grafikā ir ( ) malas.
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
6. Pieņemsim, ka binārajā kokā ir 2000 mezglu, tad binārā koka minimālais augstums ir ( ).
(A) 9 (B) 10 (C) 11 (D) 12
7. Pieņemsim, ka virzītā grafikā ir n virsotnes, tad blakus esošajā tabulā ir ( ) galvenes mezgli, kas atbilst virzītajam grafikam.
(A) n-1 (B) n (C) n+1 (D) 2n-1
8. Iestatiet sākotnējo ierakstu atslēgvārdu secību kopu (5, 2, 6, 3, 8), un ātrās kārtošanas rezultāts, pamatojoties uz pirmo ieraksta atslēgvārdu 5, ir ( ).
(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. Aizpildiet tukšās vietas (24 punkti)
1. Lai efektīvi izmantotu HASH meklēšanas tehnoloģiju, divas problēmas, kas jāatrisina, ir ____________________ un __________________________.
2. Nākamā programmas segmenta funkcija realizē datus x kaudzē un prasa pareizu paziņojumu aizpildīt pasvītrojumā.
typedefstruct {int s[100]; int augšpusē; } kvadrātmetru kaudze;
void push(sqstack&stack,int x)
{
if (stack.top==m-1) printf("pārplūde");
citādi {____________________; _________________; }
}
3. Secība, kas iegūta, šķērsojot bināro šķirošanas koku vidējā secībā, ir ___________ secība (aizpildīta pasūtīta vai nesakārtota).
4. Ātrākās šķirošanas laika sarežģītība ir ___________, un vidējā laika sarežģītība ir __________.
5. Ja mezglu skaits ar pakāpi 0 binārā kokā ir N0 un mezgla numurs ar pakāpi 1 ir N1, tad mezglu skaits ar pakāpi 2 binārajā kokā ir _________; Ja binārais saistītais saraksts tiek izmantots kā binārā koka krātuves struktūra, binārajā kokā ir _______ tukši rādītāja lauki.
6. Pieņemsim, ka virsotņu un malu skaits noteiktā nevirzītā grafikā ir attiecīgi n un e, un visu virsotņu pakāpju summa ir d, tad e = _______.
7. Ja sākotnējā ieraksta atslēgvārdu secība ir (55, 63, 44, 38, 75, 80, 31, 56), tad sākotnējā kaudze, kas izveidota ar skrīninga metodi, ir ___________________________.
8. Ir zināms, ka virzītā grafika blakus tabulas glabāšanas struktūra ir šāda: No 1. virsotnes DFS šķērsošanas izejas secība ir:
, BFS šķērsošanas izejas secība ir
Datu struktūras dokuments (3)
1. Jautājumi ar atbilžu variantiem (1 punkts par jautājumu, kopā 20 punkti)
1. Ja datu struktūras binārā forma ir izteikta kā 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>}, tad datu struktūra A ir ( ).
(A) Lineārā struktūra (B) Koka struktūra (C) Fiziskā struktūra (D) Grafiskā struktūra
2. Šīs programmas laika komplekss ir ()
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. Iestatiet rādītāja mainīgo p, lai norādītu uz mezglu A vienā saistītajā sarakstā, ja izdzēšat mezglu A vienā saistītajā sarakstā, jums jāmaina rādītāja darbības secība uz ().
(A) q = p->nākamais; p->data=q->data; p->next=q->next; brīvs (q);
(B) q=p->nākamais; q->data=p->data; p->next=q->next; brīvs (q);
(C) q = p->nākamais; p->next=q->next; brīvs (q);
(D) q = p->nākamais; p->data=q->data; brīvs (q);
4. Ja ir kārtojami n ierakstu atslēgvārdi, kaudzes kārtošanā ir nepieciešamas papildu ierakstu vienības.
(A) 1 (B) n (C) nlog2n (D) n2
5. Ja sākotnējie atslēgvārdu ieraksta atslēgvārdi ir (20, 15, 14, 18, 21, 36, 40, 10), tad rezultāts pēc ātrās kārtošanas beigām, kas reģistrēts ar 20 kā etalonu, ir ( ).
(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. Pieņemsim, ka binārajā kārtošanas kokā ir n mezgli, tad vidējais uzmeklēšanas garums binārajā kārtošanas kokā ir ( ).
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7. Pieņemsim, ka nevirzītajā grafikā G ir n virsotnes e malas, tad galvenes mezglu un tabulas mezglu skaits atbilstošajā blakus tabulā ir ( ).
(A) n,e (B) e,n (C) 2n,e (D) n,2e
8. Pieņemsim, ka spēcīgā savienojuma grafikā ir n virsotnes, tad spēcīgā savienojuma grafikā ir vismaz ( ) malas.
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9. Ir jākārto 5000 ierakstu atslēgvārdi, ja jums ir jāizmanto ātrākā metode, lai atlasītu mazākos 10 ierakstu atslēgvārdus, varat izmantot šādu ( ) metodi, lai sasniegtu šo mērķi.
(A) Ātrā kārtošana (B) Kaudzes kārtošana (C) Sapludināšanas kārtošana (D) Ievietošana kārtot
10. Šādiem četriem veidiem ( ) ir vislielākā telpiskā sarežģītība.
(A) Ievietošanas kārtošana (B) Burbuļojošā kārtošana (C) Kaudzes kārtošana (D) Sapludināšanas kārtošana
2. Aizpildiet tukšās vietas (1 punkts par tukšo vietu, kopā 20 punkti)
1. Datu fiziskā struktūra galvenokārt ietver divas situācijas: _____________ un ______________.
2. Ja pilnīgā binārajā kokā ir 500 mezgli, binārā koka dziļums ir __________; Ja bināro saistīto sarakstu izmantojat kā pilnībā binārā koka krātuves struktūru, ir ___________ tukši rādītāja lauki.
3. Ja ievades secība ir 1, 2, 3, tad pēc kaudzes darbības var iegūt ___________ dažādas izejas secības.
4. Ja blakus matrica A[n][n] tiek izmantota kā G grafika glabāšanas struktūra, tad visu blakus matricas i rindas elementu summa ir vienāda ar i virsotnes ________, un visu elementu summa i kolonnā ir vienāda ar i virsotnes ________.
5. Ja Huffman kokā ir n mezgli, Huffman kokā ir ________ mezgli ar pakāpi 1.
6. Ja virziena grafikā G ar virziena malām ir n virsotnes e un visu grādu virsotņu summa ir d, tad attiecība starp e un d ir _________.
7. __________ šķērsojot mezglus binārā šķirošanas kokā, var iegūt pakāpenisku atslēgvārdu secību (aizpildīts, vidējais vai aizmugurējais).
8. Ja uzmeklēšanas tabulā ir 100 elementi, ja datu elementa X atrašanai izmantojat dihotomisko meklēšanas metodi, tas ir jāsalīdzina līdz ________ reizēm, lai noteiktu, vai datu elements X ir uzmeklēšanas tabulā.
9. Neatkarīgi no tā, vai tas ir kaudze ar secīgu krātuves struktūru vai kaudze ar ķēdes krātuves struktūru, in-stack un out-stack operāciju laika sarežģītība ir ____________.
10. Pilnīgs binārais koks ar n mezgliem, ja tas numurēts secībā no augšas uz leju un no kreisās uz labo pusi, sākot no 1, i-tā mezgla vecākmezgls ir numurēts ____________, un labā bērna mezgla numurs ir ___________.
11. Ja sākotnējā ierakstīto atslēgvārdu kopa ir (72, 73, 71, 23, 94, 16, 5), tad ātrās kārtošanas rezultāts, pamatojoties uz ieraksta atslēgvārdu 72, ir ___________________________.
12. Ja virziena grafikā G E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>} ir vērstu malu kopa, tad tiek ____________________ grafika topoloģiskā secība.
13. Šis algoritms ievieš atslēgvārdu ar vērtību x secīgajā jaucējsarakstā, lūdzu, aizpildiet pareizo paziņojumu pasvītrojumā.
struct record{int key; citi; };
inthashsqsearch(struct record hashtable[ ],int k)
{
inti, j; j=i=k % p;
kamēr (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; if (i==j) return(-1); }
ja (_______________________) atgriežas(j); citādi atgriezties(-1);
}
14. Šis algoritms ievieš galveno vērtību k binārajā kārtošanas kokā, lūdzu, aizpildiet pareizo paziņojumu pasvītrojumā.
typedefstruct node{int key; struct mezgls *lchild; struct mezgls *rchild; }bitree;
bitree *bstsearch(bitree *t, int k)
{
ja (t==0 ) atgriežas(0); citādi, kamēr (t!=0)
if (t->key==k)_____________; citādi, ja (t->taustiņš>k) t=t->lchild; else_____________;
}
Datu struktūras pārbaudes darbs (1) Skatīt atbildi
1. Jautājumi ar atbilžu variantiem (2 punkti par jautājumu, kopā 20 punkti)
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
2. Aizpildiet tukšās vietas (1 punkts par tukšo vietu, kopā 26 punkti)
1. Pareizība, salasāmība, izturība un augsta efektivitāte
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. Virziena un bez ķēdes
8.n(n-1)/2 n(n-1)
9.（12，40） （ ） （74） （23,55，63）
10. Pievienot 1
11.O(log2n) O(nlog2n)
12. Konsolidācija
Atbildes uz citiem testa jautājumiem var redzēt:
Tūristi, ja vēlaties redzēt šīs ziņas slēpto saturu, lūdzu Atbildi
|
Publicēts 25.11.2014 12:46:30
|
|
|
Publicēts 30.12.2014 00:10:55