Data Structure Paper (1)
1. Meerkeuzevragen (2 punten per vraag, in totaal 20 punten)
1. De gemeenschappelijke kenmerken van stapels en wachtrijen zijn ( ).
A. Alleen invoegen en verwijderen van elementen aan het eindpunt toestaan
B. Allemaal eerst binnen, als laatste eruit
C. Het is allemaal eerst binnen, eerst eruit
D. Er is geen gemeenschappelijke grond
2. De wachtrij die op een gekoppelde manier is opgeslagen, wordt ingevoegd bij het uitvoeren van de invoegoperatie ( ).
A. Alleen de kopwijzer wordt aangepast B. De kop- en staartwijzers moeten worden aangepast
C. Alleen de staartwijs aanpassen D. De kop- en staartwijzers moeten mogelijk worden aangepast
3. Welke van de volgende datastructuren is een niet-lineaire structuur? ( )
A. Wachtrij B. Stapel C. Lineaire tabel D. Binaire boom
4. Als er een tweedimensionale array A[m][n] is, ervan uitgaande dat A[0][0] wordt opgeslagen op 644 (10), en A[2][2] op 676 (10), dan neemt elk element een ruimte in, waar wordt A[3][3][3](10) opgeslagen? Voetnoot (10) geeft aan dat het in decimale taal wordt uitgedrukt.
A.688 B.678 C.692 D.696
5. Bomen worden het beste gebruikt om ( ) weer te geven.
A. Geordende data-elementen B. Ongeordende data-elementen
C. Data met vertakkende hiërarchische relaties tussen elementen D. Data zonder verbinding tussen elementen
6. Het maximale aantal knopen in de k-de laag van de binaire boom is ( ).
A.2k-1 B.2K+1 C.2K-1 D. 2k-1
7. Als er een geordende tabel van 18 elementen is opgeslagen in een eendimensionale array A[19], het eerste element wordt geplaatst in A[1], en wordt er nu een binaire zoekopdracht uitgevoerd, dan is het subscript van de vergelijkingsreeks om A[3] te vinden ( )
A. 1,2,3 B. 9,5,2,3
C. 9,5,3 D. 9,4,2,3
8. Sorteer snel de bestanden van n records, en de benodigde hulpopbergruimte is ongeveer gelijk
A. O(1) B. O(n) C. O(1og2n) D. O(n2)
9. Voor lineaire tabellen (7, 34, 55, 25, 64, 46, 20, 10) voor hashopslag, als H(K)=K %9 als hashfunctie wordt gekozen, zijn er ( ) elementen met een hashadres van 1.
A.1 B.2 C.3 D.4
10. Een niet-gerichte graaf met 6 knooppunten, en de graaf moet minstens ( ) zijden hebben om een verbonden graaf te garanderen.
A.5 B.6 C.7 D.8
2. Vul de leegtes in (1 punt per leeg lege plek, in totaal 26 punten)
1. De kwaliteit van het algoritme wordt meestal beoordeeld vanuit vier aspecten: _________, _________, _________ en _________.
2. De tijdscomplexiteit van een algoritme is (n3+n2log2n+14n)/n2, en de orde van grootte wordt uitgedrukt als ________.
3. Aangenomen dat de gegeneraliseerde tabel van een boom wordt weergegeven als A(C,D(E,F,G),H(I,J)), dan is het aantal knopen in de boom __________, de diepte van de boom ___________, en de graad van de boom is _________.
4. De waarde van de suffixformule 9 2 3 +- 10 2 / - is __________. De achtervoegselformule die overeenkomt met de middelste formule (3+4X)-2Y/3 is _______________________________.
5. Als een binaire boom wordt opgeslagen met een gekoppelde lijst, heeft elke knoop twee verwijzingen naar het linker kind en het rechter kind naast het dataveld. In deze opslagstructuur heeft de binaire boom met n knopen in totaal ________ pointervelden, waarvan ________ pointervelden adressen opslaan en ________________ pointers lege pointers zijn.
6. Voor een gerichte graaf en een niet-gerichte graaf met n knopen en E-balk zijden zijn er respectievelijk _______ en ________ randknopen in de bijbehorende nabijgelegen tabel.
7. AOV-netwerk is een ___________________ grafiek.
8. In een niet-gerichte volledige graaf met n knopen zijn er ________ zijden, en in een gerichte volledige graaf met n knopen zijn er ________ zijden.
9. Aangenomen dat een lineaire tabel (12,23,74,55,63,40) is, als de elementen van dezelfde rest een subtabel worden volgens de Key % 4-voorwaarde, zijn de vier verkregen deeltabellen ____________________________, ___________________, _______________________ en __________________________.
10. Bij het invoegen van elementen in een B_ boom, als de wortelknoop van de boom uiteindelijk wordt gesplitst, is de hoogte van de nieuwe boom ___________ dan die van de oorspronkelijke boom.
11. Bij het proces van heap-sortering is de tijdscomplexiteit van het zeven van een branch-knoop ________, en de tijdscomplexiteit van het hele heap-sorteerproces is ________.
12. Bij snel sorteren, heap-sortering en merge-sortering is _________ sorteren stabiel.
Datastructuur-artikel (2)
1. Meerkeuzevragen (24 punten)
1. De volgende beschrijving van lineaire tabellen is onjuist ().
(A) Lineaire tabellen worden sequentieel opgeslagen en moeten een aaneengesloten stuk opslagruimte innemen
(B) Lineaire tabellen zijn gekoppeld en nemen geen aaneengesloten opslagruimte in beslag
(C) Lineaire tabellen worden geïmplementeerd met gekoppelde opslag om invoeg- en verwijderingsoperaties te vergemakkelijken
(d) Lineaire tabellen worden geïmplementeerd met sequentiële opslag om invoeg- en verwijderingsoperaties te vergemakkelijken
2. Stel dat het totale aantal bladknopen in de Huffman-boom m is, en als een binaire gekoppelde lijst als opslagstructuur wordt gebruikt, zijn er in totaal ( ) lege pointervelden in de Huffman-boom.
(A) 2m-1 (B)2m (C)2m+1 (D)4m
3. Als de kop- en staartaanwijzers van de sequentiële luswachtrij Q[0:M-1] respectievelijk F en R zijn, de kopaanwijzer F altijd naar de vorige positie van het kopelement wijst, en de staartaanwijzer R altijd naar de huidige positie van het staartelement, dan is het aantal elementen in de luswachtrij ( ).
(A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M
4. Als de middenorde doorloopvolgorde van een binaire boom ABCD is en de vorige volgorde doorloopvolgorde CABD is, dan is de reeks die wordt verkregen door de binaire boom in de volgende volgorde te doorlopen ().
(A) BADC (B)BCDA (C) CDAB (D) CBDA
5. Stel dat er n knopen zijn in een volledig ongerigte graaf, dan zijn er ( ) zijden in de volledig ongerichte graaf.
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
6. Stel dat er 2000 knopen in een binaire boom zijn, dan is de minimale hoogte van de binaire boom ( ).
(A) 9 (B) 10 (C) 11 (D) 12
7. Stel dat er n knopen zijn in een gerichte graaf, dan zijn er ( ) headerknopen in de adjacentietabel die overeenkomen met de gerichte graaf.
(A) n-1 (B) n (C) n+1 (D) 2n-1
8. Stel een set van initiële sleutelwoordreeksen in het record in (5, 2, 6, 3, 8), en het resultaat van een snelle sortering op basis van het eerste record sleutelwoord 5 is ( ).
(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. Vul de lege plekken in (24 punten)
1. Om HASH-zoektechnologie effectief toe te passen, moeten twee problemen worden opgelost: ____________________ en __________________________.
2. De functie van het volgende programmasegment realiseert de data x in de stack en vereist dat de juiste instructie wordt ingevuld in de onderstreep.
typedefstruct {int s[100]; Int Top; } sqstack;
Void Push (Sqstack&Stack,Int X)
{
if (stack.top==m-1) printf("overflow");
else {____________________; _________________; }
}
3. De reeks die wordt verkregen door de binaire sorteerboom in de middenorde te doorlopen, is een ___________ reeks (ingevuld in geordend of ongeordend).
4. De ergste tijdcomplexiteit van snel sorteren is ___________, en de gemiddelde tijdscomplexiteit is __________.
5. Als het aantal knopen met een graad 0 in een binaire boom N0 is en het knooppuntnummer met graad 1 N1, dan is het aantal knopen met graad 2 in de binaire boom _________; Als een binaire gekoppelde lijst wordt gebruikt als opslagstructuur van de binaire boom, zijn er _______ lege pointervelden in de binaire boom.
6. Stel dat het aantal knopen en zijden in een bepaalde niet-gerichte graaf respectievelijk n en e is, en de som van de graden van alle knopen d is, dan is e = _______.
7. Als de initiële zoekwoordvolgorde van het record (55, 63, 44, 38, 75, 80, 31, 56) is, dan is de initiële heap die door de screeningsmethode is vastgesteld ___________________________.
8. Het is bekend dat de opslagstructuur van een adjacentietabel van een gerichte graaf als volgt is: Vanaf knoop 1 is de uitvoersequentie van DFS-doorloop:
, de uitvoersequentie van BFS-doorloops is
Data Structuur Paper (3)
1. Meerkeuzevragen (1 punt per vraag, in totaal 20 punten)
1. Als de binaire vorm van een datastructuur wordt uitgedrukt als 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>}, dan is de datastructuur A ( ).
(A) Lineaire structuur (B) Boomstructuur (C) Fysieke structuur (D) Grafische structuur
2. Het tijdcomplex van het volgende programma is ()
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. Stel de pointervariabele p in om te wijzen op knoop A in een enkele gekoppelde lijst; als je knoop A verwijdert in een enkele gekoppelde lijst, moet je de bewerkingsvolgorde van de pointer veranderen naar ().
(A) q=p->volgende; p->data=q->data; p->next=q->next; free(q);
(B) q=p->volgende; q->data=p->data; p->next=q->next; free(q);
(C) q=p->volgende; p->next=q->next; free(q);
(D) q=p->volgende; p->data=q->data; free(q);
4. Als er n recordzoekwoorden zijn die gesorteerd moeten worden, ( ) zijn aanvullende record-eenheden vereist in de heap-sortering.
(A) 1 (B) n (C) nlog2n (D) n2
5. Als de sleutelwoorden van de initiële zoekwoordregistratie (20, 15, 14, 18, 21, 36, 40, 10) zijn, dan is het resultaat na het einde van een snelle sortering met 20 als benchmark ( ).
(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. Stel dat er n knopen zijn in de binaire sorteerboom, dan is de gemiddelde zoeklengte in de binaire sorteerboom ( ).
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7. Stel dat er n knooppunten e zijden zijn in de niet-gerichte graaf G, dan is het aantal headerknopen en tabelknopen in de bijbehorende nabijheidstabel ( ).
(A) n,e (B) e,n (C) 2n,e (D) n,2e
8. Stel dat er n knopen zijn in een sterke verbindingsgraaf, dan zijn er minstens ( ) zijden in de sterke verbindingsgraaf.
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9. Er zijn 5000 record-zoekwoorden te sorteren; als je de snelste methode wilt gebruiken om de kleinste 10-record-zoekwoorden te selecteren, kun je de volgende ( ) methode gebruiken om dit doel te bereiken.
(A) Snel sorteren (B) Heap sorteren (C) Samenvoegen sorteren (D) Sorteren invoegen
10. De volgende vier soorten ( ) hebben de grootste ruimtelijke complexiteit.
(A) Invoegsortering (B) Bubbling sorteren (C) Heap sorteren (D) Samenvoegen sorteren
2. Vul de lege plekken in (1 punt per leeg punt, in totaal 20 punten)
1. De fysieke structuur van data omvat voornamelijk twee situaties: _____________ en ______________.
2. Als er 500 knopen zijn in een volledige binaire boom, is de diepte van de binaire boom __________; Als je een binaire gekoppelde lijst gebruikt als opslagstructuur voor de volledig binaire boom, zijn er ___________ lege pointervelden.
3. Als de invoervolgorde 1, 2, 3 is, kunnen ___________ verschillende uitvoerreeksen worden verkregen na de werking van de stack.
4. Als de adjacentiematrix A[n][n] wordt gebruikt als opslagstructuur voor graaf G, dan is de som van alle elementen op rij i in de adjacentiematrix gelijk aan de ________ van knoop i, en is de som van alle elementen in kolom i gelijk aan de ________ van knoop i.
5. Als er n knopen in de Huffman-boom zijn, zijn er ________ knopen met een graad van 1 in de Huffman-boom.
6. Als er n knopen e zijn in de richtingsgraaf G met richtingsribben, en de som van alle knopen die graden binnengaan d is, dan is de relatie tussen e en d _________.
7. __________ doorlopen van de knopen in de binaire sorteerboom kan een incrementele reeks trefwoorden (gevuld, midden of posterior) worden verkregen.
8. Als er 100 elementen in de opzoektabel staan, moet je met de dichotome zoekmethode dataelement X tot ________ keer vergelijken om te bepalen of dataelement X in de opzoektabel zit.
9. Of het nu gaat om een stack met een sequentiële opslagstructuur of een stack met een ketenopslagstructuur, de tijdscomplexiteit van in- en outstack-operaties is ____________.
10. Een volledige binaire boom met n knopen, als deze van boven naar beneden en van links naar rechts wordt genummerd vanaf 1, wordt de ouderknoop van de i-de knoop genummerd als ____________, en het nummer van de rechter kindknoop is ___________.
11. Als de initiële set opgenomen trefwoorden (72, 73, 71, 23, 94, 16, 5) is, dan is het resultaat van een snelle sortering op basis van het recordsleutelwoord 72 ___________________________.
12. Als er een verzameling gerichte zijden is in de richtingsgraaf G E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>}, dan is een topologische rij van de graaf ____________________.
13. Het volgende algoritme implementeert het trefwoord met de waarde x in de sequentiële hashlijst, vul de juiste uitspraak in de onderscore.
struct record{int key; int andere; };
inthashsqsearch(struct record hashtable[ ],int k)
{
inti,j; j=i=k % p;
terwijl (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; als (i==j) terugkeert(-1); }
als (_______________________ ) retourneren(j); else return (-1);
}
14. Het volgende algoritme implementeert de sleutelwaarde k in de binaire sorteerboom, vul alstublieft de juiste uitspraak in de onderscore in.
typedefstruct node{int key; struct node *lchild; struct node *rchild; }bitree;
Bitree *bstsearch(bitree *t, int k)
{
als (t==0) return(0); anders terwijl (t!=0)
als (t->key==k)_____________; anders als (t->sleutel>k) t=t->lchild; else_____________;
}
Datastructuurtoetspaper (1) Raadpleeg het antwoord
1. Meerkeuzevragen (2 punten per vraag, in totaal 20 punten)
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
2. Vul de leegtes in (1 punt per leeg lege plek, in totaal 26 punten)
1. Correctheid, leesbaarheid, sterkte en hoge efficiëntie
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. Directioneel en niet-circuit
8.n(n-1)/2 n(n-1)
9.（12，40） （ ） （74） （23,55，63）
10. Voeg 1 op
11.O(log2n) O(nlog2n)
12. Consolidatie
De antwoorden op andere toetsvragen zijn te zien:
Toeristen, als jullie de verborgen inhoud van dit bericht willen zien, alsjeblieft Antwoord
|
Geplaatst op 25-11-2014 12:46:30
|
|
|
Geplaatst op 30-12-2014 00:10:55
|
