Duomenų struktūros dokumentas (1)
1. Klausimai su atsakymų variantais (2 taškai už klausimą, iš viso 20 balų)
1. Bendros rietuvių ir eilių savybės yra ( ).
A. Leisti įterpti ir ištrinti elementus tik galiniame taške
B. Visi pirmas į, paskutinis išeina
C. Viskas pirmas į, pirmas išeina
D. Nėra bendro pagrindo
2. Susietu būdu saugoma eilė įterpiama atliekant įterpimo operaciją ( ).
A. Modifikuotas tik galvos rodyklė B. Galvos ir uodegos rodyklės turi būti modifikuotos
C. Pakeiskite tik uodegos rodyklę D. Gali tekti keisti galvos ir uodegos rodykles
3. Kuri iš šių duomenų struktūrų yra netiesinė struktūra? ( )
A. Eilė B. Rietuvė C. Linijinė lentelė D. Dvejetainis medis
4. Jei yra dvimatis masyvas A[m][n], darant prielaidą, kad A[0][0] saugomas 644 (10), o A[2][2] saugomas 676 (10), kiekvienas elementas užima erdvę, kur saugomas A[3][3][3][3](10)? 10 išnašoje nurodyta, kad jis išreiškiamas dešimtainiu skaičiumi.
A.688 B.678 C.692 D.696
5. Medžiai geriausiai naudojami vaizduoti ( ).
A. Sutvarkyti duomenų elementai B. Netvarkingi duomenų elementai
C. Duomenys su šakotais hierarchiniais ryšiais tarp elementų D. Duomenys be ryšio tarp elementų
6. Didžiausias mazgų skaičius dvejetainio medžio k-ajame sluoksnyje yra ( ).
A.2k-1 B.2K+1 C.2K-1 D. 2k-1
7. Jei yra sutvarkyta 18 elementų lentelė, saugoma vienmatiame masyve A[19], pirmasis elementas dedamas į A[1], o dabar atliekama dvejetainė paieška, tada palyginimo sekos A[3] apatinis indeksas yra ( )
A. 1,2,3 B. 9,5,2,3
C. 9,5,3 D. 9,4,2,3
8. Greitai rūšiuokite n įrašų failus, o reikalinga papildoma saugyklos vieta yra maždaug tokia pati
A. O(1) B. O(n) C. O(1og2n) D. O(n2)
9. Linijinėms lentelėms (7, 34, 55, 25, 64, 46, 20, 10) maišos saugojimui, jei H(K)=K %9 pasirinkta kaip maišos funkcija, yra ( ) elementų, kurių maišos adresas yra 1.
A.1 B.2 C.3 D.4
10. Nenukreiptas grafikas su 6 mazgais, o grafikas turi turėti bent ( ) kraštus, kad būtų užtikrintas sujungtas grafikas.
A.5 B.6 C.7 D.8
2. Užpildykite tuščias vietas (1 taškas už tuščią vietą, iš viso 26 taškai)
1. Algoritmo kokybė paprastai vertinama keturiais aspektais: _________, _________, _________ ir _________.
2. Algoritmo laiko sudėtingumas yra (n3+n2log2n+14n)/n2, o jo dydžio tvarka išreiškiama ________.
3. Darant prielaidą, kad apibendrinta medžio lentelė vaizduojama kaip A(C,D(E,F,G),H(I,J)), tada medyje esančių mazgų skaičius yra __________, medžio gylis yra ___________, o medžio laipsnis yra _________.
4. Priesagos formulės 9 2 3 +- 10 2 / - vertė yra __________. Priesagos formulė, atitinkanti vidurinę formulę (3+4X)-2Y/3, yra _______________________________.
5. Jei dvejetainis medis saugomas su susietu sąrašu, kiekvienas mazgas, be duomenų lauko, turi dvi nuorodas į kairįjį ir dešinįjį. Šioje saugyklos struktūroje dvejetainis medis su n mazgais iš viso turi ________ rodyklių laukus, iš kurių ________ rodyklės laukai saugo adresus, o ________________ rodyklės yra tuščios rodyklės.
6. Nukreiptam grafikui ir nenukreiptam grafikui su n viršūnėmis ir E juostos kraštais atitinkamoje gretimumo lentelėje yra atitinkamai _______ ir ________ kraštų mazgai.
7. AOV tinklas yra ___________________ grafikas.
8. Nenukreiptame pilname grafike su n viršūnėmis yra ________ kraštų, o nukreiptame pilname grafike su n viršūnėmis yra ________ kraštų.
9. Darant prielaidą, kad linijinė lentelė yra (12,23,74,55,63,40), jei tos pačios liekanos elementai tampa antrine lentele pagal pagrindinę % 4 sąlygą, gautos keturios sublentelės yra ____________________________, ___________________, _______________________ ir __________________________.
10. Įterpiant elementus į B_ medį, jei medžio šaknies mazgas galutinai suskaidomas, naujo medžio aukštis yra ___________ nei pradinio medžio.
11. Krūvos rūšiavimo procese ________ bet kurio šakos mazgo sijojimo laiko sudėtingumas, o viso krūvos rūšiavimo proceso laiko sudėtingumas yra ________.
12. Greito rūšiavimo, krūvos rūšiavimo ir sujungimo rūšiavimo metu _________ rūšiavimas yra stabilus.
Duomenų struktūros dokumentas (2)
1. Klausimai su atsakymų variantais (24 balai)
1. Toliau pateiktas linijinių lentelių aprašymas yra neteisingas ().
(A) Linijinės lentelės saugomos nuosekliai ir turi užimti gretimą saugojimo vietą
(B) Linijiniai stalai yra sujungti grandinėmis ir neužima ištisinės saugojimo vietos
(C) Linijinės lentelės yra įdiegtos su grandinine saugykla, kad būtų lengviau įterpti ir ištrinti operacijas
d) Linijinės lentelės įdiegtos su nuosekliu saugojimu, kad būtų lengviau įterpti ir ištrinti
2. Tarkime, kad bendras lapų mazgų skaičius Huffman medyje yra m, o jei dvejetainis susietas sąrašas naudojamas kaip saugojimo struktūra, Huffman medyje iš viso yra ( ) tuščių žymeklio laukų.
(A) 2m-1 (B)2m (C)2m+1 (D)4m
3. Jei nuoseklios kilpos eilės Q[0:M-1] galvos ir uodegos rodyklės yra atitinkamai F ir R, galvos rodyklė F visada nurodo ankstesnę galvos elemento padėtį, o uodegos rodyklė R visada nurodo dabartinę uodegos elemento padėtį, tada elementų skaičius kilpos eilėje yra ( ).
(A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M
4. Jei dvejetainio medžio vidurinės eilės perėjimo seka yra ABCD, o ankstesnė sekos perėjimo seka yra CABD, tada seka, gauta kertant dvejetainį medį vėlesne tvarka, yra ().
(A) BADC (B)BCDA (C) CDAB (D) CBDA
5. Tarkime, kad visiškai nenukreiptame grafike yra n viršūnių, tada visiškai nenukreiptame grafike yra ( ) kraštai.
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
6. Tarkime, kad dvejetainiame medyje yra 2000 mazgų, tada mažiausias dvejetainio medžio aukštis yra ( ).
(A) 9 (B) 10 (C) 11 (D) 12
7. Tarkime, kad nukreiptame grafike yra n viršūnių, tada gretimumo lentelėje yra ( ) antraštės mazgai, atitinkantys nukreiptą grafiką.
(A) n-1 (B) n (C) n+1 (D) 2n-1
8. Nustatykite pradinių įrašų raktažodžių sekų rinkinį (5, 2, 6, 3, 8), o greito rūšiavimo pagal pirmąjį įrašo raktažodį 5 rezultatas yra ( ).
(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. Užpildykite tuščias vietas (24 balai)
1. Norint efektyviai pritaikyti HASH paieškos technologiją, reikia išspręsti dvi problemas ____________________ ir __________________________.
2. Šio programos segmento funkcija realizuoja duomenis x į rietuvę ir reikalauja, kad pabraukime būtų užpildytas teisingas teiginys.
typedefstruct {int s[100]; int viršuje; } kv.;
void push(sqstack&stack,int x)
{
if (stack.top==m-1) printf("perpildymas");
else {____________________; _________________; }
}
3. Seka, gauta kertant dvejetainį rūšiavimo medį vidurine tvarka, yra ___________ seka (užpildyta užsakyta arba netvarkinga).
4. Blogiausias greito rūšiavimo laiko sudėtingumas yra ___________, o vidutinis laiko sudėtingumas yra __________.
5. Jei mazgų, kurių laipsnis yra 0, skaičius dvejetainiame medyje yra N0, o mazgo numeris, kurio laipsnis yra 1, yra N1, tada mazgų, kurių laipsnis yra 2, skaičius dvejetainiame medyje yra _________; Jei dvejetainis susietas sąrašas naudojamas kaip dvejetainio medžio saugojimo struktūra, dvejetainiame medyje yra _______ tuščių žymeklio laukų.
6. Tarkime, kad viršūnių ir briaunų skaičius tam tikrame nenukreiptame grafike yra atitinkamai n ir e, o visų viršūnių laipsnių suma yra d, tada e = _______.
7. Jei pradinė įrašo raktinių žodžių seka yra (55, 63, 44, 38, 75, 80, 31, 56), tada pradinė krūva, nustatyta atrankos metodu, yra ___________________________.
8. Yra žinoma, kad nukreipto grafiko gretimumo lentelės saugojimo struktūra yra tokia: Nuo 1 viršūnės DFS perėjimo išvesties seka yra:
, BFS perėjimo išvesties seka yra
Duomenų struktūros dokumentas (3)
1. Klausimai su atsakymų variantais (1 balas už klausimą, iš viso 20 balų)
1. Jei dvejetainė duomenų struktūros forma išreiškiama taip: 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>}, tada duomenų struktūra A yra ( ).
(A) Linijinė struktūra (B) Medžio struktūra (C) Fizinė struktūra (D) Grafinė struktūra
2. Šios programos laiko kompleksas yra ()
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. Nustatykite žymeklio kintamąjį p, kad jis nukreiptų į mazgą A viename susietame sąraše, jei ištrinsite mazgą A viename susietame sąraše, turite pakeisti žymeklio operacijų seką į ().
(A) q=p->toliau; p->data=q->data; p->next=q->next; laisvas (q);
(B) q = p->toliau; q->data=p->duomenys; p->next=q->next; laisvas (q);
(C) q = p->toliau; p->next=q->next; laisvas (q);
(D) q = p->toliau; p->data=q->data; laisvas (q);
4. Jei yra n įrašų raktažodžių, kuriuos reikia rūšiuoti, ( ) krūvos rūšiavime reikalingi pagalbiniai įrašų vienetai.
(A) 1 (B) n (C) nlog2n (D) n2
5. Jei pradinis raktažodis įrašo raktažodžiai yra (20, 15, 14, 18, 21, 36, 40, 10), tada rezultatas po greito rūšiavimo pabaigos įrašytas su 20 kaip etalonas yra ( ).
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. Tarkime, kad dvejetainiame rūšiavimo medyje yra n mazgų, tada vidutinis peržvalgos ilgis dvejetainiame rūšiavimo medyje yra ( ).
(A) O (1) (B) O(log2n) (C) (D) O(n2)
7. Tarkime, kad nenukreiptame grafike G yra n viršūnių e kraštų, tada antraštės mazgų ir lentelės mazgų skaičius atitinkamoje gretimumo lentelėje yra ( ).
(A) n,e (B) e,n (C) 2n,e (D) n,2e
8. Tarkime, kad stiprios jungties grafike yra n viršūnių, tada stiprios jungties grafike yra bent ( ) kraštai.
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9. Reikia rūšiuoti 5000 įrašų raktažodžių, jei jums reikia naudoti greičiausią metodą, kad pasirinktumėte mažiausius 10 įrašų raktažodžių, šiam tikslui pasiekti galite naudoti šį ( ) metodą.
(A) Greitas rūšiavimas (B) Krūvos rūšiavimas (C) Suliejimo rūšiavimas (D) Įterpti rūšiavimą
10. Šios keturios ( ) rūšys turi didžiausią erdvinį sudėtingumą.
(A) Įterpimo rūšiavimas (B) Burbuliuojantis rūšiavimas (C) Krūvos rūšiavimas (D) Suliejimo rūšiavimas
2. Užpildykite tuščias vietas (1 taškas už tuščią vietą, iš viso 20 taškų)
1. Fizinė duomenų struktūra daugiausia apima dvi situacijas: _____________ ir ______________.
2. Jei visame dvejetainiame medyje yra 500 mazgų, dvejetainio medžio gylis yra __________; Jei naudojate dvejetainį susietą sąrašą kaip visiškai dvejetainio medžio saugojimo struktūrą, yra ___________ tuščių žymeklio laukų.
3. Jei įvesties seka yra 1, 2, 3, tada po rietuvės veiksmo galima gauti ___________ skirtingas išvesties sekas.
4. Jei gretimumo matrica A[n][n] naudojama kaip G grafiko saugojimo struktūra, tada visų gretimumo matricos i eilutės elementų suma yra lygi i viršūnės ________, o visų i stulpelio elementų suma yra lygi i viršūnės ________.
5. Jei Huffman medyje yra n mazgų, Huffman medyje yra ________ mazgų, kurių laipsnis yra 1.
6. Jei krypties grafike G su krypties kraštais yra n viršūnių e, o visų viršūnių, įeinančių į laipsnius, suma yra d, tada santykis tarp e ir d yra _________.
7. __________ kirsdami dvejetainio rūšiavimo medžio mazgus, galite gauti laipsnišką raktinių žodžių seką (užpildytą, vidurinį arba užpakalinį).
8. Jei peržvalgos lentelėje yra 100 elementų, jei duomenų elementui X rasti naudojate dichotominį paieškos metodą, turite jį palyginti iki ________ kartų, kad nustatytumėte, ar duomenų elementas X yra peržvalgos lentelėje.
9. Nesvarbu, ar tai rietuvė su nuoseklia saugojimo struktūra, ar rietuvė su grandinės saugojimo struktūra, "in-stack" ir "out-stack" operacijų sudėtingumas yra ____________.
10. Visas dvejetainis medis su n mazgais, jei sunumeruotas eilės tvarka iš viršaus į apačią ir iš kairės į dešinę, pradedant nuo 1, i-ojo mazgo pirminis mazgas numeruojamas ____________, o dešiniojo antrinio mazgo numeris yra ___________.
11. Jei pradinis įrašytų raktinių žodžių rinkinys yra (72, 73, 71, 23, 94, 16, 5), greito rūšiavimo pagal įrašo raktažodį 72 rezultatas yra ___________________________.
12. Jei krypties grafike G E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>} yra nukreiptų briaunų rinkinys, tada ____________________ grafiko topologinė seka.
13. Šis algoritmas įgyvendina raktinį žodį su x reikšme nuosekliame maišos sąraše, apatiniame brūkšnyje užpildykite teisingą teiginį.
struct record{int raktas; int kiti; };
inthashsqsearch(struct record hashtable[ ],int k)
{
inti, j; j=i=k % p;
while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; if (i==j) return(-1); }
jei (_______________________ ) grąžinti (j); else return(-1);
}
14. Šis algoritmas įgyvendina pagrindinę reikšmę k dvejetainiame rūšiavimo medyje, apatiniame brūkšnyje užpildykite teisingą teiginį.
typedefstruct node{int raktas; struct mazgas *lchild; struct mazgas *rchild; }bitree;
bitree *bstsearch(bitree *t, int k)
{
if (t==0 ) return(0); kitaip, o (t!=0)
if (t->key==k)_____________; else if (t->key>k) t=t->lchild; else_____________;
}
Duomenų struktūros bandymo dokumentas (1) Žiūrėkite atsakymą
1. Klausimai su atsakymų variantais (2 balai už klausimą, iš viso 20 balų)
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
2. Užpildykite tuščias vietas (1 taškas už tuščią vietą, iš viso 26 taškai)
1. Teisingumas, įskaitomumas, stiprumas ir didelis efektyvumas
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. Kryptinis ir ne grandinės
8.n(n-1)/2 n(n-1)
9.（12，40） （ ） （74） （23,55，63）
10. Pridėti 1
11.O(log2n) O(nlog2n)
12. Konsolidavimas
Atsakymus į kitus testo klausimus galima pamatyti:
Turistai, jei norite pamatyti paslėptą šio įrašo turinį, prašome Atsakyti
|
Paskelbta 2014-11-25 12:46:30
|
|
|
Paskelbta 2014-12-30 00:10:55