Datenstrukturarbeit (1)
1. Multiple-Choice-Fragen (2 Punkte pro Frage, insgesamt 20 Punkte)
1. Die gemeinsamen Merkmale von Stacks und Warteschlangen sind ( ).
A. Nur das Einfügen und Löschen von Elementen am Endpunkt erlauben
B. Alle zuerst rein, zuletzt draußen
C. Es ist alles zuerst rein, zuerst raus
D. Es gibt keinen gemeinsamen Nenner
2. Die in einer verknüpfte Weise gespeicherte Warteschlange wird beim Einfügen der Einfügungsoperation eingefügt ( ).
A. Nur der Kopfzeiger wird modifiziert B. Der Kopf- und Schwanzzeiger müssen modifiziert werden
C. Nur den Schwanzzeiger D modifizieren. Der Kopf- und Schwanzzeiger müssen möglicherweise modifiziert werden
3. Welche der folgenden Datenstrukturen ist eine nichtlineare Struktur? ( )
A. Warteschlange B. Stapel C. Lineare Tabelle D. Binärer Baum
4. Wenn es ein zweidimensionales Array A[m][n] gibt, unter der Annahme, dass A[0][0] bei 644 (10) gespeichert wird und A[2][2] bei 676 (10), dann nimmt jedes Element einen Raum ein, wobei A[3][3][3](10) gespeichert ist? Fußnote (10) gibt an, dass sie in Dezimalform angegeben ist.
A.688 B.678 C.692 D.696
5. Bäume werden am besten verwendet, um ( ) darzustellen.
A. Geordnete Datenelemente B. Ungeordnete Datenelemente
C. Daten mit verzweigten hierarchischen Beziehungen zwischen den Elementen D. Daten ohne Verbindung zwischen den Elementen
6. Die maximale Anzahl von Knoten in der k-ten Schicht des Binärbaums beträgt ( ).
A.2k-1 B.2K+1 C.2K-1 D. 2k-1
7. Wenn eine geordnete Tabelle mit 18 Elementen in einem eindimensionalen Array A[19] gespeichert ist, wird das erste Element in A[1] gesetzt und nun eine binäre Suche durchgeführt, dann ist der Index der Vergleichssequenz zur Findung von A[3] ( )
A. 1,2,3 B. 9,5,2,3
C. 9,5,3 D. 9,4,2,3
8. Sortiere schnell die Dateien von n Datensätzen, und der benötigte Hilfsspeicherplatz ist ungefähr derselbe
A. O(1) B. O(n) C. O(1og2n) D. O(n2)
9. Für lineare Tabellen (7, 34, 55, 25, 64, 46, 20, 10) für die Hashspeicherung gilt: Wenn H(K)=K %9 als Hashfunktion ausgewählt wird, gibt es ( ) Elemente mit einer Hashadresse von 1.
A.1 B.2 C.3 D.4
10. Ein ungerichteter Graph mit 6 Knoten, und der Graph sollte mindestens ( ) Kanten besitzen, um einen zusammenhängenden Graphen zu gewährleisten.
A.5 B.6 C.7 D.8
2. Fülle die Lücken aus (1 Punkt pro Leer, insgesamt 26 Punkte)
1. Die Qualität des Algorithmus wird üblicherweise aus vier Aspekten bewertet: _________, _________, _________ und _________.
2. Die Zeitkomplexität eines Algorithmus beträgt (n3+n2log2n+14n)/n2, und seine Größenordnung wird als ________ angegeben.
3. Angenommen, die verallgemeinerte Tabelle eines Baumes wird als A(C,D(E,F,G),H(I,J)) dargestellt, dann ist die Anzahl der im Baum enthaltenen Knoten __________, die Tiefe des Baumes ___________ und der Grad des Baumes _________.
4. Der Wert der Suffixformel 9 2 3 +- 10 2 / - ist __________. Die Suffixformel, die der mittleren Formel (3+4X)-2Y/3 entspricht, ist _______________________________.
5. Wenn ein Binärbaum mit einer verketteten Liste gespeichert wird, hat jeder Knoten zusätzlich zum Datenfeld zwei Zeiger auf das linke und das rechte Kind. In dieser Speicherstruktur hat der Binärbaum mit n Knoten insgesamt ________ Zeigerfelder, von denen ________ Zeigerfelder Adressen speichern und ________________ Zeiger leere Zeiger sind.
6. Für einen gerichteten Graphen und einen ungerichteten Graphen mit n Knoten und E-Bar-Kanten gibt es _______ bzw. ________ Kantenknoten in der entsprechenden Adjazenztabelle.
7. AOV-Netzwerk ist ein ___________________ Graph.
8. In einem ungerichteten vollständigen Graphen mit n Knoten gibt es ________ Kanten, und in einem gerichteten vollständigen Graphen mit n Knoten ________ Kanten.
9. Angenommen, eine lineare Tabelle ist (12,23,74,55,63,40), und wenn die Elemente desselben Rests gemäß der Schlüssel-%-4-Bedingung zu einer Teiltabelle werden, sind die vier erhaltenen Untertabellen ____________________________, ___________________, _______________________ und __________________________.
10. Beim Einfügen der Elemente in einen B_ Baum gilt: Wenn der Wurzelknoten des Baumes schließlich gespalten wird, ist die Höhe des neuen Baumes ___________ als die des ursprünglichen Baums.
11. Im Prozess der Heap-Sortierung ist die Zeitkomplexität des Siebens eines Zweigknotens ________, und die Zeitkomplexität des gesamten Heap-Sortierprozesses ist ________.
12. Bei Schnellsortierung, Heap-Sortierung und Merge-Sortierung ist _________ Sortierung stabil.
Datenstrukturarbeit (2)
1. Multiple-Choice-Fragen (24 Punkte)
1. Die folgende Beschreibung linearer Tabellen ist falsch ().
(A) Lineare Tabellen werden sequentiell gespeichert und müssen einen zusammenhängenden Speicherplatz einnehmen
(B) Lineare Tabellen sind verkettet und nehmen keinen durchgehenden Speicherplatz ein
(C) Lineare Tabellen werden mit verkettetem Speicher implementiert, um Einfügungs- und Löschoperationen zu erleichtern
(d) Lineare Tabellen werden mit sequentiellem Speicher implementiert, um Einfügungs- und Löschoperationen zu erleichtern
2. Angenommen, die Gesamtzahl der Blattknoten im Huffman-Baum beträgt m, und wenn eine binäre verkettete Liste als Speicherstruktur verwendet wird, gibt es im Huffman-Baum insgesamt ( ) leere Zeigerfelder.
(A) 2m-1 (B)2m (C)2m+1 (D)4m
3. Wenn die Kopf- und Schwanzzeiger der sequentiellen Schleifen-Warteschlange Q[0:M-1] jeweils F und R sind, der Kopfzeiger F immer auf die vorherige Position des Kopfelements zeigt und der Schwanzzeiger R immer auf die aktuelle Position des Schwanzelements, dann beträgt die Anzahl der Elemente in der Schleifenwarteschlange ( ).
(A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M
4. Wenn die mittlere Durchlaufssequenz eines Binärbaums ABCD ist und die vorherige Sequenzdurchlaufsequenz CABD, dann ist die durch Durchlaufen des Binärbaums in der folgende Reihenfolge erhaltene Folge ().
(A) BADC (B)BCDA (C) CDAB (D) CBDA
5. Angenommen, es gibt n Knoten in einem völlig ungerichteten Graphen, dann gibt es ( ) Kanten im völlig ungerichteten Graphen.
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
6. Angenommen, es gibt 2000 Knoten in einem binären Baum, dann ist die minimale Höhe des binären Baumes ( ).
(A) 9 (B) 10 (C) 11 (D) 12
7. Angenommen, es gibt n Knoten in einem gerichteten Graphen, dann gibt es ( ) Header-Knoten in der Adjazenztabelle, die dem gerichteten Graphen entsprechen.
(A) n-1 (B) n (C) n+1 (D) 2n-1
8. Setzen Sie eine Reihe von Startdatensatz-Schlüsselwortfolgen (5, 2, 6, 3, 8), und das Ergebnis einer schnellen Sortierung basierend auf dem ersten Datensatz-Schlüsselwort 5 ist ( ).
(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. Fülle die Lücken aus (24 Punkte)
1. Um die HASH-Nachschlagtechnologie effektiv anzuwenden, müssen zwei Probleme gelöst werden: ____________________ und __________________________.
2. Die Funktion des folgenden Programmsegments realisiert die Daten x in den Stack und erfordert, dass die korrekte Anweisung in der Unterstreichung ausgefüllt wird.
typedefstruct {int s[100]; Int Top; } sqstack;
Void Push(sqstack&stack,int x)
{
wenn (stack.top==m-1) printf("overflow");
else {____________________; _________________; }
}
3. Die durch das Durchlaufen des binären Sortierbaums in mittlerer Ordnung erhaltene Folge ist eine ___________ Folge (ausgefüllt in geordneter oder ungeordneter Reihenfolge).
4. Die schlimmste Zeitkomplexität des schnellen Sortierens ist ___________, und die durchschnittliche Zeitkomplexität ist __________.
5. Wenn die Anzahl der Knoten mit Grad 0 in einem binären Baum N0 beträgt und die Knotenzahl mit Grad 1 N1, dann beträgt die Anzahl der Knoten mit Grad 2 im Binärbaum _________; Wenn eine binäre verkettete Liste als Speicherstruktur des binären Baums verwendet wird, gibt es im Binärbaum _______ leere Zeigerfelder.
6. Angenommen, die Anzahl der Knoten und Kanten in einem bestimmten ungerichteten Graphen beträgt n bzw. e, und die Summe der Grade aller Knoten ist d, dann gilt e = _______.
7. Wenn die anfängliche Keyword-Sequenz des Datensatzes (55, 63, 44, 38, 75, 80, 31, 56) ist, dann ist der durch die Screening-Methode ermittelte initiale Heap ___________________________.
8. Es ist bekannt, dass die Speicherstruktur der Adjazenztabelle eines gerichteten Graphen wie folgt ist: Von Knoten 1 aus ist die Ausgabesequenz der DFS-Durchlauf:
, die Ausgabesequenz der BFS-Durchlauf ist
Datenstruktur-Papier (3)
1. Multiple-Choice-Fragen (1 Punkt pro Frage, insgesamt 20 Punkte)
1. Wenn die binäre Form einer Datenstruktur 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>} ausgedrückt wird, dann ist die Datenstruktur A ( ).
(A) Lineare Struktur (B) Baumstruktur (C) Physikalische Struktur (D) Grafische Struktur
2. Der Zeitkomplex des folgenden Programms ist ()
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. Setze die Zeigervariable p so, dass sie in einer einzelnen verketteten Liste auf Knoten A zeigt; wenn du Knoten A in einer einzelnen verketteten Liste löschst, musst du die Operationssequenz des Zeigers auf () ändern.
(A) q=p->nächste; p->data=q->data; p->next=q->next; free(q);
(B) q=p->nächstes; q->data=p->data; p->next=q->next; free(q);
(C) q=p->next; p->next=q->next; free(q);
(D) q=p->nächste; p->data=q->data; free(q);
4. Wenn n Schlüsselwörter für Datensätze sortiert werden müssen, ( ) werden in der Heap-Sortierung zusätzliche Datensatzeinheiten benötigt.
(A) 1 (B) n (C) nlog2n (D) n2
5. Wenn die Schlüsselwörter für den ursprünglichen Keyword-Datensatz (20, 15, 14, 18, 21, 36, 40, 10) sind, dann ist das Ergebnis nach dem Ende einer Schnellsortierung mit 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. Angenommen, es gibt n Knoten im binären Sortierbaum, dann ist die durchschnittliche Nachschlaglänge im binären Sortierbaum ( ).
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7. Angenommen, es gibt n Knoten e Kanten im ungerichteten Graphen G, dann beträgt die Anzahl der Kopf- und Tabellenknoten in der entsprechenden Adjazenztabelle ( ).
(A) n,e (B) e,n (C) 2n,e (D) n,2e
8. Angenommen, es gibt n Knoten in einem starken Verbindungsgraphen, dann gibt es mindestens ( ) Kanten im starken Verbindungsgraphen.
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9. Es gibt 5000 Eintrags-Schlüsselwörter zu sortieren; wenn Sie die schnellste Methode zur Auswahl der kleinsten 10-Datensatz-Schlüsselwörter verwenden möchten, können Sie folgende ( ) Methode verwenden, um diesen Zweck zu erreichen.
(A) Schnellsortierung (B) Heap-Sortierung (C) Zusammenführen (D) Sortieren einfügen (D) Sortieren einfügen
10. Die folgenden vier Arten von ( ) haben die größte räumliche Komplexität.
(A) Einfügungssortierung (B) Blasensortierung (C) Heap-Sortierung (D) Zusammenführende Sortierung
2. Fülle die Lücken aus (1 Punkt pro Leer, insgesamt 20 Punkte)
1. Die physikalische Struktur von Daten umfasst hauptsächlich zwei Situationen: _____________ und ______________.
2. Wenn es 500 Knoten in einem vollständigen Binärbaum gibt, beträgt die Tiefe des Binärbaums __________; Wenn du eine binäre verkettete Liste als Speicherstruktur für den vollständig binären Baum verwendest, gibt es ___________ leere Zeigerfelder.
3. Wenn die Eingabesequenz 1, 2, 3 ist, können nach der Wirkung des Stacks ___________ verschiedene Ausgabesequenzen erhalten werden.
4. Wenn die Adjazenzmatrix A[n][n] als Speicherstruktur für den Graphen G verwendet wird, dann ist die Summe aller Elemente in Zeile i in der Adjazenzmatrix gleich dem ________ von Knoten i, und die Summe aller Elemente in Spalte i entspricht dem ________ von Knoten i.
5. Wenn es n Knoten im Huffman-Baum gibt, gibt es ________ Knoten mit dem Grad 1 im Huffman-Baum.
6. Wenn es n Knoten e im Richtungsgraphen G mit Richtungskanten gibt und die Summe aller Knoten, die in Grade eintreten, d beträgt, dann ist die Beziehung zwischen e und d _________.
7. __________ Durchqueren der Knoten im binären Sortierbaum kann eine inkrementelle Folge von Schlüsselwörtern (gefüllt, mittig oder posterior) erhalten.
8. Wenn es 100 Elemente in der Nachschlagetabelle gibt, müssen Sie mit der dichotomen Suchmethode das Datenelement X bis zu ________ Mal vergleichen, um festzustellen, ob Datenelement X in der Nachschlagetabelle ist.
9. Ob es sich um einen Stack mit sequentieller Speicherstruktur oder einen Stack mit einer Kettenspeicherstruktur handelt, die Zeitkomplexität von In- und Out-Stack-Operationen ist ____________.
10. Ein vollständiger Binärbaum mit n Knoten, wenn er von oben nach unten und von links nach rechts ab 1 nummeriert wird, wird der Elternknoten des i-ten Knotens mit ____________ nummeriert, und die Nummer des rechten Kindknotens ist ___________.
11. Wenn der Anfangssatz der aufgezeichneten Schlüsselwörter (72, 73, 71, 23, 94, 16, 5) ist, dann ist das Ergebnis einer schnellen Sortierung basierend auf dem Datensatz-Schlüsselwort 72 ___________________________.
12. Gibt es eine Menge gerichteter Kanten im Richtungsgraphen G E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>}, dann ist eine topologische Folge des Graphen ____________________.
13. Der folgende Algorithmus implementiert das Schlüsselwort mit dem Wert x in der sequentiellen Hashliste, bitte geben Sie die korrekte Aussage im Unterstrich ein.
struct record{int key; andere; };
inthashsqsearch(struct record hashtable[ ],int k)
{
inti,j; j=i=k % p;
während (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; wenn (i==j) (-1) zurückgibt; }
wenn (_______________________ ) zurück (j); sonst zurück (-1);
}
14. Der folgende Algorithmus implementiert den Schlüsselwert k im binären Sortierbaum, bitte füllen Sie die korrekte Aussage im Unterstrich aus.
typedefstruct node{int key; Struct Node *lchild; Struct Node *rchild; }bitree;
Bitree *bstsearch(bitree *t, int k)
{
wenn (t==0) zurückgeben(0); sonst während (t!=0)
wenn (t->schlüssel==k)_____________; sonst, wenn (t->schlüssel>k) t=t->lchild; oder_____________;
}
Datenstruktur-Testpapier (1) Siehe die Antwort
1. Multiple-Choice-Fragen (2 Punkte pro Frage, insgesamt 20 Punkte)
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
2. Fülle die Lücken aus (1 Punkt pro Leer, insgesamt 26 Punkte)
1. Korrektheit, Lesbarkeit, Festigkeit und hohe Effizienz
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. Richtungsabhängig und Nicht-Schaltung
8.n(n-1)/2 n(n-1)
9.（12，40） （ ） （74） （23,55，63）
10. Addiere 1
11.O(log2n) O(nlog2n)
12. Konsolidierung
Die Antworten auf weitere Testfragen sind zu sehen:
Touristen, wenn ihr den versteckten Inhalt dieses Beitrags sehen wollt, bitte Antwort
|
Veröffentlicht am 25.11.2014 12:46:30
|
|
|
Veröffentlicht am 30.12.2014 00:10:55
|
