Adatszerkezeti dolgozat (1)
1. Feleletválasztós kérdések (2 pont kérdésenként, összesen 20 pont)
1. A stackek és sorok közös jellemzői a ( ).
A. Csak az elemek behelyezése és törlése a végponton engedélyezett
B. Minden első, be, utoljára ki,
C. Minden első, első, első, ki,
D. Nincs közös alap
2. A láncolt módon tárolt sort a beillesztési művelet ( ) végrehajtása során kerül be.
A. Csak a fejmutatót módosítják B. A fej- és farokmutatókat módosítani kell
C. Csak a farokmutatót módosítsd D. A fej- és farokmutatókat módosítani kell
3. Az alábbi adatstruktúrák közül melyik nemlineáris struktúra? ( )
A. Sor B. Stack C. Lineáris tábla D. Bináris fa
4. Ha létezik egy kétdimenziós tömb A[m][n], feltételezve, hogy A[0][0] 644 (10)-en, és A[2][2] 676 (10)-nél van tárolva, minden elem egy teret foglal el, hol tárolja A[3][3][3](10)? A lábjegyzet (10) azt jelzi, hogy tizedesben van kifejezve.
A.688 B.678 C.692 D.696
5. A fák leginkább az ( ).
A. Rendezett adatelemek B. Sorrend nélküli adatelemek
C. Adat, amelyek elágazó hierarchikus viszonyokkal rendelkeznek az elemek között D. Adat, amely nem kapcsolódik az elemek közötti kapcsolatokhoz
6. A bináris fa k-edik rétegében a maximális csomópontok száma ( ).
A.2k-1 B.2K+1 C.2K-1 D. 2k-1
7. Ha egy egydimenziós tömbben tárolt 18 elemből álló rendezett táblázat van egy A[19]-ben, az első elem az A[1]-be kerül, és most bináris keresést végeznek, akkor az összehasonlító sorozat indexindexe A[3] megtalálásához a ( )
A. 1,2,3 B. 9,5,2,3
C. 9,5,3 D. 9,4,2,3
8. Gyorsan rendezd n rekord fájljait, és a szükséges kiegészítő tárolóhely nagyjából ugyanannyi lesz
A. O(1) B. O(n) C. O(1og2n) D. O(n2)
9. Lineáris táblázatok esetén (7, 34, 55, 25, 64, 46, 20, 10) hash tárolásra, ha H(K)=K %9 van kiválasztva hash függvényként, akkor vannak ( ) elemek, amelyek hash címe 1.
A.1 B.2 C.3 D.4
10. Egy irányítatlan gráf, 6 csomóponttal, és a gráfnak legalább ( ) élekkel kell rendelkeznie, hogy biztosítsa a kapcsolt gráfot.
A.5 B.6 C.7 D.8
2. Töltsd ki a hiányzó helyeket (1 pont egy üres helyen, összesen 26 pont)
1. Az algoritmus minőségét általában négy szempontból értékelik: _________, _________, _________ és _________.
2. Egy algoritmus időkomplexitása (n3+n2log2n+14n)/n2, és nagyságrendje ________-ként fejezzük ki.
3. Feltételezve, hogy egy fa általánosított táblázata A(C,D(E,F,G),H(I,J)) formátumban van ábrázolva), akkor a fa csomópontjainak száma __________, a fa mélysége ___________, a fa foka pedig _________.
4. A 9 2 3 +- 10 2 / - utótag értéke __________. A középső (3+4X)-2Y/3 képlethez tartozó póttag _______________________________.
5. Ha egy bináris fa egy összekapcsolt listával van tárolva, minden csomópontnak két mutatója van a bal és jobb gyermek felé az adatmező mellett. Ebben a tárolószerkezetben a bináris fa n csomóponttal összesen ________ mutatómezővel rendelkezik, amelyek közül ________ mutatómező címeket tárol, ________________ pedig üres mutatók.
6. Egy irányított és egy n csúcsú és E-sáv élű gráf esetén _______ és ________ élcsomópont található a megfelelő szomszédsági táblában.
7. Az AOV hálózat egy ___________________ gráf.
8. Egy n csúcsú irányítatlan teljes gráfban ________ él van, míg egy n csúcsú irányított teljes gráfban ________ él van.
9. Feltételezve, hogy egy lineáris tábla (12,23,74,55,63,40), ha ugyanannak a maradványnak az elemei a Key % 4 feltétel szerint altáblává válnak, akkor a kapott négy altáblázat a ____________________________, ___________________, _______________________ és __________________________.
10. Az elemek beillesztése során egy B_ fa gyökércsomópontját végül szétválasztják, az új fa magassága ___________ az eredeti fa magassága.
11. A halomrendezés során bármely ágcsomópont szitálásának időkomplexitása ________, és az egész halom rendezési folyamat időkomplexitása ________.
12. Gyors rendezésben, halomrendezésben és összevonásban _________ rendezés stabil.
Adatszerkezeti dolgozat (2)
1. Feleletválasztós kérdések (24 pont)
1. A következő lineáris táblázatleírás helytelen ().
(A) A lineáris táblákat egymás után tárolják, és egy egymás melletti tárolóhelyet kell elfoglalniuk
(B) A lineáris táblák láncolóak, és nem foglalnak el folyamatos tárolóhelyet
(C) A lineáris táblák láncos tárolással vannak megvalósítva, hogy megkönnyítsék a behelyezési és törlési műveleteket
(d) Lineáris táblázatokat szekvenciális tárolással valósítanak meg, hogy megkönnyítsék a behelyezési és törlési műveleteket
2. Tegyük fel, hogy a Huffman-fa levélcsomópontjainak összesített száma m, és ha egy bináris összekapcsolt listát használnak tárolási struktúráként, akkor a Huffman-fában összesen ( ) üres mutatómező van.
(A) 2m-1 (B)2m (C)2m+1 (D)4m
3. Ha a sorozatos hurok Q[0:M-1] fej- és farokmutatói F és R, akkor a fejmutató F mindig a fejelem korábbi pozíciójára mutat, a farokjelző R pedig mindig a farokelem aktuális pozíciójára mutat, akkor a huroksorban lévő elemek száma ( ).
(A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M
4. Ha egy bináris fa középső rendű áthaladási sorozata ABCD, az előző sorozat áthaladási sorozata pedig CABD, akkor a bináris fa következő sorrendjében történő áthaladásával kapható sorozat ().
(A) BADC (B) BCDA (C) CDAB (D) CBDA
5. Tegyük fel, hogy egy teljesen irányítatlan gráfban n csúcs van, akkor a teljesen irányítatlan gráfban is vannak ( ) élek.
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
6. Tegyük fel, hogy egy bináris fában 2000 csomópont van, akkor a bináris fa minimális magassága ( ).
(A) 9 (B) 10 (C) 11 (D) 12
7. Tegyük fel, hogy n csúcs van egy irányított gráfban, akkor vannak ( ) fejlécpontok a szomszédsági táblában, amelyek megfelelnek az irányított gráfnak.
(A) n-1 (B) n (C) n+1 (D) 2n-1
8. Állítsunk be egy kezdeti rekordkulcsszekvenciákat (5, 2, 6, 3, 8), és az első 5 kulcsszavara alapuló gyors rendezés eredménye ( ).
(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. Töltsd ki a hiányzó részeket (24 pont)
1. A HASH kereső technológia hatékony alkalmazásához két problémát kell megoldani: ____________________ és __________________________.
2. A következő programszegmens funkciója az x adatot a verembe valósítja, és a helyes állítást kell kitölteni az aláhúzóban.
typedefstruct {int s[100]; int top; } sqstack;
void push(sqstack&stack,int x)
{
if (stack.top==m-1) printf("overflow");
else {____________________; _________________; }
}
3. A bináris rendezési fa középső sorrendbeli áthaladásával elért sorozat egy ___________ sorozat (rendezett vagy sorrend nélküli formában van kitöltve).
4. A gyors rendezés legrosszabb időbonyolultsága ___________, az átlagos időkomplexitás pedig __________.
5. Ha a bináris fában a 0 fokú csomópontok száma N0, és az 1 fokú csomópontszám N1, akkor a bináris fában a 2 fokú csomópontok száma _________; Ha egy bináris összekapcsolt listát használnak a bináris fa tárolási struktúrájaként, akkor _______ üres mutatómező található a bináris fában.
6. Tegyük fel, hogy egy bizonyos irányítatlan gráfban a csúcsok és élek száma n, illetve e, és az összes csúcs fokának összege d, akkor e = _______.
7. Ha az első rekordkulcsszekvencia (55, 63, 44, 38, 75, 80, 31, 56), akkor a szűrési módszer által létrehozott kezdeti halom ___________________________.
8. Ismert, hogy egy irányított gráf szomszédsági táblatároló szerkezete a következő: Az 1-es csúcstól a DFS áthaladásának kimeneti sorozata:
, a BFS áthaladásának kimeneti sorozata a következő
Adatszerkezeti dolgozat (3)
1. Feleletválasztós kérdések (1 pont kérdésenként, összesen 20 pont)
1. Ha egy adatszerkezet bináris formája 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>}, akkor az adatstruktúra A ( ).
(A) Lineáris szerkezet (B) Faszerkezet (C) Fizikai szerkezet (D) Grafikai szerkezet
2. A következő program időkomplexuma ()
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. Állítsd be a p mutató változót, hogy egyetlen összekapcsolt listában A csomópontra mutass, ha törlöd az A csomópontot egyetlen összekapcsolt listából, akkor a mutató műveleti sorrendjét ().
(A) q=p->next; p->data=q->data; p->next=q->next; free(q);
(B) q=p->next; q->data=p->data; p->next=q->next; free(q);
(C) q=p->next; p->next=q->next; free(q);
(D) q=p->next; p->data=q->data; free(q);
4. Ha n rekordkulcsszót kell rendezni, () segéd rekordegységekre van szükség a halom rendezésben.
(A) 1 (B) n (C) nlog2n (D) n2
5. Ha az eredeti kulcsszavarekord kulcsszavak (20, 15, 14, 18, 21, 36, 40, 10), akkor a gyors rendezés utáni eredmény, amelyet 20-as benchmarkként rögzítenek, az ( ).
(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. Tegyük fel, hogy n csomópont van a bináris rendezési fában, akkor a bináris rendezési fa átlagos keresési hossza ( ).
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7. Tegyük fel, hogy a G irányítatlan gráfban n csúcs e él van, akkor a megfelelő szomszédsági táblában a fejlécpontok és táblacsomópontok száma ( ).
(A) n,e (B) e,n (C) 2n,e (D) n,2e
8. Tegyük fel, hogy egy erős kapcsolatgráfban n csúcs van, akkor az erős kapcsolat gráfjában legalább ( ) élek vannak.
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9. 5000 bejegyzéskulcsszót kell rendezni, ha a leggyorsabb módszerrel kell kiválasztani a legkisebb 10 bejegyzéses kulcsszót, akkor a következő ( ) módszerrel lehet ezt elérni.
(A) Gyors rendezés (B) Halom rendezés (C) Összevonás rendezése (D) Szelekedés
10. A következő négy típusú ( ) a legnagyobb térbeli összetettséggel rendelkezik.
(A) Beépítési rendezés (B) Buborékolás rendezés (C) Halom rendezés (D) Egyesítés rendezés
2. Töltsd ki az üres helyeket (1 pont minden üres helyen, összesen 20 pont)
1. Az adatok fizikai szerkezete főként két helyzetet foglal magában: _____________ és ______________.
2. Ha egy teljes bináris fában 500 csomópont van, a bináris fa mélysége __________; Ha egy bináris linkelt listát használsz a teljes bináris fa tárolási struktúrájaként, akkor ___________ üres mutatómező van.
3. Ha a bemeneti sorozat 1, 2, 3, akkor a stack működése után ___________ különböző kimeneti sorozat érhető el.
4. Ha az A[n][n] szomszédsági mátrix tárolószerkezetként a G gráf tárolási szerkezeteként szolgál, akkor az i sor összes elemének összege az i csúcs ________-jával egyenlő, az i oszlop összes elemének összege pedig az i csúcs ________-jával.
5. Ha a Huffman-fában n csomópont van, akkor a Huffman-fában ________ csomópont van, amelynek foka 1.
6. Ha a G iránygráfban n e csúcs van irányszélekkel, és az összes fokba belépő csúcs összege d, akkor az e és d közötti kapcsolat _________.
7. __________ a bináris rendezési fa csomópontjai között haladva egy inkrementális kulcsszekvenciát (kitöltött, középső vagy hátra) kaphatunk.
8. Ha a keresőtáblában 100 elem van, ha a dichotomous keresési módszerrel megtalálod az X adatelemet, akkor akár ________ alkalommal kell összehasonlítanod, hogy megállapítsd, az adatelem X benne van-e a keresőtáblában.
9. Legyen szó egy veremről sorozatos tárolószerkezettel, vagy lánctároló szerkezettel, a stack belső és kimenő műveletek időbonyolultsága ____________.
10. Egy teljes bináris fa n csomóponttal, ha felülről lefelé és balról jobbra sorrendben van számozva, az 1-től kezdve, az i-edik csomópont szülőcsomópontja ____________-es számot kap, a jobb gyermekcsomópont száma pedig ___________.
11. Ha a rögzített kulcsszavak kezdeti halmaza (72, 73, 71, 23, 94, 16, 5), akkor a 72-es kulcsszó alapján gyors válogatás eredménye ___________________________.
12. Ha az iránygráfban van egy irányított élek halmaza G E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>}, akkor a gráf topológiai sorozata ____________________.
13. A következő algoritmus valósítja meg a kulcsszót x értékével a sorozatos hash listában, kérjük, töltse ki a helyes állítást az aláhúzótáblában.
struct record{int key; mások int };
inthashsqsearch(struct record hashtable[ ],int k)
{
inti,j; j=i=k % p;
while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; ha (i==j) return(-1); }
ha (_______________________ ) return(j); else return(-1);
}
14. Az alábbi algoritmus megvalósítja a k kulcsértéket a bináris rendezésfában, kérjük, töltse ki a helyes állítást az aláhúzótáblában.
typedefstruct node{int key; struct csomópont *lchild; struct csomópont *rchild; }bitree;
bitree *bstsearch(bitree *t, int k)
{
ha (t==0) return(0); másként, miközben (t!=0)
if (t->kulcs==k)_____________; más ha (t->kulcs>k) t=t->lchild; else_____________;
}
Adatszerkezeti tesztdolgozat (1) Lásd a választ
1. Feleletválasztós kérdések (2 pont kérdésenként, összesen 20 pont)
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
2. Töltsd ki a hiányzó helyeket (1 pont egy üres helyen, összesen 26 pont)
1. Pontosság, olvashatóság, erő és magas hatékonyság
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. Irányított és nem áramkörű
8.n(n-1)/2 n(n-1)
9.（12，40） （ ） （74） （23,55，63）
10. Add ki 1
11.O(log2n) O(nlog2n)
12. Konszolidáció
A többi tesztkérdésre adott válaszok megtalálhatók:
Turisták, ha szeretnétek megnézni ennek a bejegyzésnek a rejtett tartalmát, kérlek Válasz
|
Közzétéve 2014. 11. 25. 12:46:30
|
|
|
Közzétéve 2014. 12. 30. 0:10:55
|
