Artykuł o strukturach danych (1)
1. Pytania wielokrotnego wyboru (2 punkty za pytanie, łącznie 20 punktów)
1. Typowe cechy stosów i kolejek to ( ).
A. Zezwalać na wstawianie i usuwanie elementów tylko na końcu końcowym
B. Wszyscy pierwsi wchodzący, ostatni wychodzący
C. To wszystko jest pierwszy wszedł, ten pierwszy wyszedł
D. Nie ma wspólnej płaszczyzny
2. Kolejka przechowywana w sposób powiązany jest wstawiana podczas wykonywania operacji wstawiania ( ).
A. Tylko wskaźnik głowy jest modyfikowany B. Wskaźniki głowy i ogon muszą być modyfikowane
C. Zmodyfikuj tylko wskaźnik ogonowy D. Wskaźniki głowy i ogona mogą wymagać modyfikacji
3. Która z poniższych struktur danych jest strukturą nieliniową? ( )
A. Kolejka B. Stos C. Tabela liniowa D. Drzewo binarne
4. Jeśli istnieje dwuwymiarowa tablica A[m][n], zakładając, że A[0][0] jest przechowywana w 644 (10), a A[2][2] w 676 (10), każdy element zajmuje przestrzeń, gdzie przechowywane jest A[3][3][3][3](10)? Przypis (10) wskazuje, że jest wyrażony w systemie dziesiętnym.
A.688 B.678 C.692 D.696
5. Drzewa najlepiej używać do reprezentowania ( ).
A. Uporządkowane elementy danych B. Nieuporządkowane elementy danych
C. Dane z rozgałęziającymi się relacjami hierarchicznymi między elementami D. Dane bez połączenia między elementami
6. Maksymalna liczba węzłów w k-tej warstwie drzewa binarnego wynosi ( ).
A.2K-1 B.2K+1 C.2K-1 D. 2K-1
7. Jeśli w jednowymiarowej tablicy A[19] jest przechowywana uporządkowana tabela 18 elementów, pierwszy element umieszcza się w A[1], a następnie przeprowadzane jest wyszukiwanie binarne, to indeks sekwencji porównawczej do znalezienia A[3] wynosi ( )
A. 1,2,3 B. 9,5,2,3
C. 9,5,3 D. 9,4,2,3
8. Szybko sortuj pliki n rekordów, a potrzebna przestrzeń pomocnicza jest mniej więcej taka sama
A. O(1) B. O(n) C. O(1og2n) D. O(n2)
9. Dla tabel liniowych (7, 34, 55, 25, 64, 46, 20, 10) do przechowywania skrótów, jeśli jako funkcja skrótu wybrano H(K)=K %9, istnieją elementy ( ) z adresem skrótu równym 1.
A.1 B.2 C.3 D.4
10. Graf nieskierowany z 6 węzłami, a graf powinien mieć co najmniej ( ), aby zapewnić spójność grafu.
A.5 B.6 C.7 D.8
2. Uzupełnij luki (1 punkt za każde puste miejsce, łącznie 26 punktów)
1. Jakość algorytmu jest zwykle oceniana z czterech aspektów: _________, _________, _________ i _________.
2. Złożoność czasowa algorytmu wynosi (n3+n2log2n+14n)/n2, a jego rząd wielkości wyraża się jako ________.
3. Zakładając, że uogólniona tabela drzewa jest reprezentowana jako A(C,D(E,F,G),H(I,J)), to liczba węzłów zawartych w drzewie wynosi __________, głębokość drzewa jest ___________, a stopień drzewa _________.
4. Wartość formuły przyrostka 9 2 3 +- 10 2 / - wynosi __________. Formuła na sufiks odpowiadająca środkowemu wzorowi (3+4X)-2Y/3 to _______________________________.
5. Jeśli drzewo binarne jest przechowywane z listą powiązaną, każdy węzeł ma dwa wskaźniki do lewego dziecka i prawego dziecka oprócz pola danych. W tej strukturze pamięci drzewo binarne z n węzłami ma łącznie ________ pól wskaźników, z których ________ pola wskaźnika przechowują adresy, a ________________ wskaźniki to puste wskaźniki.
6. Dla grafu skierowanego i nieskierowanego z n wierzchołkami i krawędziami E-bar, w odpowiadającej mu tabeli sąsiedniej znajdują się odpowiednio _______ i ________ węzłów krawędzi.
7. Sieć AOV to graf ___________________.
8. W nieskierowanym pełnym grafie z n wierzchołkami występuje ________ krawędzi, a w skierowanym pełnym grafie z n wierzchołkami jest ________ krawędzi.
9. Zakładając, że tabela liniowa to (12,23,74,55,63,40), jeśli elementy tej samej reszty stają się podtabelą zgodnie z warunkiem Key % 4, otrzymane cztery podtabele to ____________________________, ___________________, _______________________ i __________________________.
10. W procesie wstawiania elementów do drzewa B_, jeśli węzeł korzeniowy drzewa zostanie ostatecznie rozdzielony, wysokość nowego drzewa jest ___________ niż oryginalnego drzewa.
11. W procesie sortowania sterty złożoność czasowa przesiewania dowolnego węzła bocznego wynosi ________, a złożoność czasowa całego procesu sortowania kopicy jest ________.
12. W szybkim sortowaniu, sortowaniu sterpowym i sortowaniu przez fuzję sortowanie _________ jest stabilne.
Artykuł o strukturach danych (2)
1. Pytania wielokrotnego wyboru (24 punkty)
1. Poniższy opis tabel liniowych jest nieprawidłowy ().
(A) Tabele liniowe są przechowywane sekwencyjnie i muszą zajmować ciągły fragment przestrzeni pamięci
(B) Tabele liniowe są połączone w łańcuch i nie zajmują ciągłej przestrzeni magazynowej
(C) Tabele liniowe są implementowane z łańcuchową pamięcią masową, aby ułatwić operacje wstawiania i usuwania
(d) Tabele liniowe są implementowane z pamięcią sekwencyjną, aby ułatwić operacje wstawiania i usuwania
2. Załóżmy, że łączna liczba węzłów liściowych w drzewie Huffmana wynosi m, a jeśli jako struktura pamięci używa się binarnej listy powiązanej, w drzewie Huffmana znajduje się łącznie ( ) pustych pól wskaźników.
(A) 2m-1 (B)2m (C)2m+1 (D)4m
3. Jeśli wskaźniki głowy i ogona kolejki pętli sekwencyjnej Q[0:M-1] to odpowiednio F i R, wskaźnik głowy F zawsze wskazuje na poprzednią pozycję elementu głównego, a wskaźnik ogonowy R zawsze wskazuje na aktualną pozycję elementu ogonowego, to liczba elementów w kolejce pętli wynosi ( ).
(A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M
4. Jeśli sekwencja przechodzenia środkowego rzędu drzewa binarnego to ABCD, a poprzednia sekwencja przeszukiwania to CABD, to ciąg uzyskany przez przejście przez drzewo binarne w kolejnym kolejności to ().
(A) BADC (B)BCDA (C) CDAB (D) CBDA
5. Załóżmy, że w całkowicie nieskierowanym grafie jest n wierzchołków, to w całkowicie nieskierowanym grafie występuje ( ) krawędzi.
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
6. Załóżmy, że w drzewie binarnym jest 2000 węzłów, to minimalna wysokość drzewa binarnego wynosi ( ).
(A) 9 (B) 10 (C) 11 (D) 12
7. Załóżmy, że w grafie skierowanym jest n wierzchołków, to w tabeli sąsiedztwa odpowiadających grafowi skierowanemu są węzły nagłówkowe ( ).
(A) n-1 (B) n (C) n+1 (D) 2n-1
8. Ustaw zestaw początkowych sekwencji słów kluczowych rekordu (5, 2, 6, 3, 8), a wynik szybkiego sortowania na podstawie pierwszego słowa kluczowego rekordu 5 to ( ).
(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. Uzupełnij luki (24 punkty)
1. Aby skutecznie zastosować technologię wyszukiwania HASH, należy rozwiązać dwa problemy: ____________________ i __________________________.
2. Funkcja następującego segmentu programu realizuje dane x do stosu i wymaga wypełnienia poprawnego potwierdzenia w podkreśleniu.
typedefstruct {int s[100]; int top; } sqstack;
Void Push(sqstack&stack, int x)
{
if (stack.top==m-1) printf("przepełnienie");
w przeciwnym razie {____________________; _________________; }
}
3. Ciąg uzyskany przez przejście przez binarne drzewo sortujące w środkowym rzędzie jest sekwencją ___________ (wypełnioną w uporządkowanym lub nieuporządkowanym).
4. Najgorsza złożoność czasowa szybkiego sortowania to ___________, a średnia złożoność czasu to __________.
5. Jeśli liczba węzłów o stopniu 0 w drzewie binarnym wynosi N0, a liczba węzłów o stopniu 1 to N1, to liczba węzłów o stopniu 2 w drzewie binarnym wynosi _________; Jeśli jako struktura pamięci drzewa binarnego jest używana binarna lista sprzężona, w drzewie binarnym pozostaje _______ pustych pól wskaźnika.
6. Załóżmy, że liczba wierzchołków i krawędzi w danym grafie nieskierowanym wynosi odpowiednio n i e, a suma stopni wszystkich wierzchołków wynosi d, wtedy e = _______.
7. Jeśli początkowa sekwencja słów kluczowych rekordu to (55, 63, 44, 38, 75, 80, 31, 56), to początkowy stos ustanowiony metodą przesiewania jest ___________________________.
8. Wiadomo, że struktura tabeli sąsiedztwa grafu skierowanego wygląda następująco: Z wierzchołka 1 sekwencja wyjściowa przejścia DFS wygląda następująco:
, ciąg wyjściowy przejścia BFS to
Artykuł o strukturach danych (3)
1. Pytania wielokrotnego wyboru (1 punkt za pytanie, łącznie 20 punktów)
1. Jeśli binarna forma struktury danych wyraża się jako 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>}, to struktura danych A to ( ).
(A) Struktura liniowa (B) Struktura drzewa (C) Struktura fizyczna (D) Struktura graficzna
2. Kompleks czasowy następującego programu to ()
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. Ustaw zmienną wskaźnika p tak, aby wskazywała na węzeł A w pojedynczej liście powiązanej, jeśli usuniesz węzeł A w jednej liście powiązanej, musisz zmienić sekwencję operacji wskaźnika na ().
(A) q=p->następny; p->data=q->data; p->następne=q->następne; free(q);
(B) q=p->następny; q->data=p->dane; p->następne=q->następne; free(q);
(C) q=p->następny; p->następne=q->następne; free(q);
(D) q=p->następny; p->data=q->data; free(q);
4. Jeśli jest n słów kluczowych rekordów do sortowania, ( ) jednostki rekordów pomocniczych są wymagane w sortowaniu kopicy.
(A) 1 (B) n (C) nlog2n (D) n2
5. Jeśli początkowe słowa kluczowe w rekordzie słów kluczowych to (20, 15, 14, 18, 21, 36, 40, 10), to wynik po zakończeniu szybkiego sortowania z 20 jako benchmarkiem to ( ).
(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. Załóżmy, że w drzewie sortowania binarnego jest n węzłów, to średnia długość wyszukiwania w drzewie sortowania binarnego wynosi ( ).
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7. Załóżmy, że w grafie nieskierowanym G jest n krawędzi wierzchołków e, to liczba węzłów nagłówkowych i tabeli tabeli w odpowiadającej mu tablicy sąsiedniej wynosi ( ).
(A) n,e (B) e,n (C) 2n,e (D) n,2e
8. Załóżmy, że w grafie silnych połączeń jest n wierzchołków, to w grafie silnych połączeń występuje co najmniej ( ) krawędzi.
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9. Do posortowania jest 5000 słów kluczowych dla rekordów, jeśli chcesz użyć najszybszej metody wyboru najmniejszych 10 rekordowych słów, możesz użyć następującej ( ), aby osiągnąć ten cel.
(A) Szybkie sortowanie (B) Sortowanie kopca (C) Łączenie sortowania (D) Wstaw sortowanie
10. Następujące cztery rodzaje ( ) mają największą złożoność przestrzenną.
(A) Sortowanie wstawiane (B) Sortowanie bąbelkowe (C) Sortowanie na kopcach (D) Sortowanie przez łączenie
2. Uzupełnij luki (1 punkt na pustkę, łącznie 20 punktów)
1. Fizyczna struktura danych obejmuje głównie dwie sytuacje: _____________ i ______________.
2. Jeśli w kompletnym drzewie binarnym jest 500 węzłów, głębokość drzewa binarnego wynosi __________; Jeśli użyjesz binarnej listy powiązanej jako struktury pamięci dla w pełni binarnego drzewa, jest ___________ pustych pól wskaźnika.
3. Jeśli sekwencja wejściowa to 1, 2, 3, to po akcji stosu można uzyskać ___________ różne sekwencje wyjściowe.
4. Jeśli macierz sąsiedztwa A[n][n] jest użyta jako struktura pamięci dla grafu G, to suma wszystkich elementów w wierszu i macierzy sąsiedztwa jest równa ________ wierzchołka i, a suma wszystkich elementów w kolumnie i jest równa ________ wierzchołka i.
5. Jeśli w drzewie Huffmana jest n węzłów, to w drzewie Huffmana jest ________ węzłów o stopniu 1.
6. Jeśli w grafie kierunkowym G z krawędziami kierunkowymi jest n wierzchołków e, a suma wszystkich wierzchołków wpisujących stopnie wynosi d, to relacja między e a d jest _________.
7. __________ przechodzenie przez węzły w drzewie sortowania binarnego może uzyskać stopniową sekwencję słów kluczowych (wypełnionych, środkowych lub tylnych).
8. Jeśli w tabeli wyszukiwania jest 100 elementów, jeśli użyjesz metody wyszukiwania dychotomicznego, aby znaleźć element danych X, musisz porównać go do ________ razy, aby określić, czy element X znajduje się w tabeli wyszukiwania.
9. Niezależnie od tego, czy jest to stos z sekwencyjną strukturą magazynową, czy stos ze strukturą łańcuchową, złożoność czasowa operacji stosu wewnątrz i wychodzącego stosu jest ____________.
10. Kompletne drzewo binarne z n węzłami, jeśli ponumerowane są od góry do dołu i od lewej do prawej zaczynając od 1, węzeł nadrzędny węzła i-tego jest oznaczony ____________, a numer prawego węzła potomnego to ___________.
11. Jeśli początkowy zestaw zarejestrowanych słów kluczowych to (72, 73, 71, 23, 94, 16, 5), to wynik szybkiego sortowania na podstawie zapisu słowa kluczowego 72 jest ___________________________.
12. Jeśli w grafie kierunkowym G E istnieje zbiór skierowanych krawędzi, to ciąg topologiczny grafu jest ____________________ {<1,2,2><2,3>,<1,4>,<4,2>,<4,3>}, to sekwencja topologiczna grafu jest .
13. Następujący algorytm implementuje słowo kluczowe o wartości x w kolejnej liście skrótów, prosimy o poprawne wpisanie w podkreśleniu.
struct record{int key; inni; };
inthashsqsearch(hashtable zapisu strukturalnego[ ],int k)
{
inti,j; j=i=k % p;
podczas gdy (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; jeśli (i==j) return(-1); }
jeśli (_______________________ ) return(j); else return(-1);
}
14. Następujący algorytm implementuje wartość klucza k w drzewie sortowania binarnego, proszę wpisać poprawne zdanie w podkreśleniu.
typedefstruct node{int key; węzeł strukturalny *lchild; węzeł strukturalny *rchild; }bitree;
Bitree *bstsearch(bitree *t, int k)
{
jeśli (t==0 ) return(0); W przeciwnym razie (t!=0)
jeśli (t->klucz==k)_____________; w przeciwnym razie jeśli (t->key>k) t=t->lchild; else_____________;
}
Praca testowa na strukturę danych (1) Odniesienie do odpowiedzi
1. Pytania wielokrotnego wyboru (2 punkty za pytanie, łącznie 20 punktów)
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
2. Uzupełnij luki (1 punkt za każde puste miejsce, łącznie 26 punktów)
1. Poprawność, czytelność, wytrzymałość i wysoka wydajność
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. Kierunkowe i nieobwodowe
8.n(n-1)/2 n(n-1)
9.（12，40） （ ） （74） （23,55，63）
10. Dodaj 1
11.O(log2n) O(nlog2n)
12. Konsolidacja
Odpowiedzi na inne pytania testowe można zobaczyć:
Turyści, jeśli chcecie zobaczyć ukrytą zawartość tego wpisu, proszę Odpowiedź
|
Opublikowano 25.11.2014 12:46:30
|
|
|
Opublikowano 30.12.2014 00:10:55