數(shù)據(jù)結(jié)構(gòu)經(jīng)典復(fù)習(xí)題(僅供參考)

千里之行，始于足下讓知識帶有溫度。第第2頁/共2頁精品文檔推薦數(shù)據(jù)結(jié)構(gòu)經(jīng)典復(fù)習(xí)題(僅供參考)一、挑選題(20分)

1．下面關(guān)于線性表的講述錯誤的是（D）。

(A)線性表采納挨次存儲必需占用一片延續(xù)的存儲空間

(B)線性表采納鏈式存儲不必占用一片延續(xù)的存儲空間

(C)線性表采納鏈式存儲便于插入和刪除操作的實現(xiàn)

(D)線性表采納挨次存儲便于插入和刪除操作的實現(xiàn)

2．設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（A）。

(A)BADC(B)BCDA(C)CDAB(D)CBDA

3．設(shè)某棵二叉樹中有2000個結(jié)點，則該二叉樹的最小高度為（C）。

(A)9(B)10(C)11(D)12

4．設(shè)二叉排序樹中有n個結(jié)點，則在二叉排序樹的平均平均查找長度為（B）。

(A)O(1)(B)O(log2n)(C)(D)O(n2)

5．設(shè)有5000個待排序的記錄關(guān)鍵字，假如需要用最快的辦法選出其中最小的10個記錄關(guān)鍵字，則用下列（B）辦法可以達到此目的。

(A)迅速排序(B)堆排序(C)歸并排序(D)插入排序

第9小題分析：9迅速排序、歸并排序和插入排序必需等到囫圇排序結(jié)束后才干夠求出最小的10個數(shù)，而堆排序只需要在初始堆的基礎(chǔ)上再舉行10次篩選即可，每次篩選的時光復(fù)雜度為O(log2n)。

6.下列四種排序中（D）的空間復(fù)雜度最大。

(A)插入排序(B)冒泡排序(C)堆排序(D)歸并排序

7．設(shè)一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時光復(fù)雜度為（C）。

(A)O(n)(B)O(nlog2n)(C)O(1)(D)O(n2)

8．設(shè)一棵二叉樹的深度為k，則該二叉樹中最多有（D）個結(jié)點。

(A)2k-1(B)2k(C)2k-1(D)2k-1

9．在二叉排序樹中插入一個結(jié)點的時光復(fù)雜度為（B）。

(A)O(1)(B)O(n)(C)O(log2n)(D)O(n2)

10．設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作（B）。

(A)必需判別棧是否為滿(B)必需判別棧是否為空

(C)判別棧元素的類型(D)對棧不作任何判別

11．下列四種排序中（A）的空間復(fù)雜度最大。

(A)迅速排序(B)冒泡排序(C)希爾排序(D)堆

12．設(shè)某二叉樹中度數(shù)為0的結(jié)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為Nl，度數(shù)為2的結(jié)點數(shù)為N2，則下列等式成立的是（C）。

(A)N0=N1+1(B)N0=Nl+N2(C)N0=N2+1(D)N0=2N1+l

13.設(shè)有序挨次表中有n個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不

超過（A）。

(A)log2n+1(B)log2n-1(C)log2n(D)log2(n+1)

14．數(shù)據(jù)的最小單位是（A）。

(A)數(shù)據(jù)項(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量

15．設(shè)一個有序的單鏈表中有n個結(jié)點，現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持有序，則該操作的時光復(fù)雜度為（D）。

(A)O(log2n)(B)O(1)(C)O(n2)(D)O(n)

16．設(shè)一棵m叉樹中度數(shù)為0的結(jié)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為Nl，……，度數(shù)為m的結(jié)點數(shù)為Nm，則N0=（B）。

(A)Nl+N2+……+Nm(B)l+N2+2N3+3N4+……+(m-1)Nm

(C)N2+2N3+3N4+……+(m-1)Nm(D)2Nl+3N2+……+(m+1)Nm

17．設(shè)輸入序列是1、2、3、……、n，經(jīng)過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是（C）。

(A)n-i(B)n-1-i(C)n+1-i(D)不能確定

18．時光復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是（A）。

(A)堆排序(B)冒泡排序(C)希爾排序(D)迅速排序

19．設(shè)二叉樹的先序遍歷序列和后序遍歷序列正巧相反，則該二叉樹滿足的條件是（D）。

(A)空或惟獨一個結(jié)點(B)高度等于其結(jié)點數(shù)

(C)任一結(jié)點無左孩子(D)任一結(jié)點無右孩子

20．挨次查找不論在挨次線性表中還是在鏈式線性表中的時光復(fù)雜度為（A）。

(A)O(n)(B)O(n2)(C)O(n1/2)(D)O(1og2n)

21．二路歸并排序的時光復(fù)雜度為（C）。

(A)O(n)(B)O(n2)(C)O(nlog2n)(D)O(1og2n)

22.深度為k的徹低二叉樹中最少有（B）個結(jié)點。

(A)2k-1-1(B)2k-1(C)2k-1+1(D)2k-1

23.設(shè)二叉排序樹上有n個結(jié)點，則在二叉排序樹上查找結(jié)點的平均時光復(fù)雜度為（D）。

(A)O(n)(B)O(n2)(C)O(nlog2n)(D)O(1og2n)

24．（B）二叉排序樹可以得到一個從小到大的有序序列。

(A)先序遍歷(B)中序遍歷(C)后序遍歷(D)層次遍歷

25．設(shè)根據(jù)從上到下、從左到右的挨次從1開頭對徹低二叉樹舉行挨次編號，則編號為i結(jié)點的左孩子結(jié)點的編號為（B）。

(A)2i+1(B)2i(C)i/2(D)2i-1

26．程序段s=i=0；do{i=i+1；s=s+i；}while(inext=top;(D)top=top->next;

28.建立一個長度為n的有序單鏈表的時光復(fù)雜度為（C）

(A)O(n)(B)O(1)(C)O(n2)(D)O(log2n)

29.在二叉排序樹中插入一個關(guān)鍵字值的平均時光復(fù)雜度為（B）。

(A)O(n)(B)O(1og2n)(C)O(nlog2n)(D)O(n2)

30.設(shè)一棵徹低二叉樹中有65個結(jié)點，則該徹低二叉樹的深度為（B）。

(A)8(B)7(C)6(D)5

31.隊列是一種（A）的線性表。

(A)先進先出(B)先進后出(C)只能插入(D)只能刪除

32.利用直接插入排序法的思想建立一個有序線性表的時光復(fù)雜度為（C）。

(A)O(n)(B)O(nlog2n)(C)O(n2)(D)O(1og2n)

33．設(shè)指針變量p指向雙向鏈表中結(jié)點A，指針變量s指向被插入的結(jié)點X，則在結(jié)點A的后面插入結(jié)點X的操作序列為（D）。

(A)p->right=s；s->left=p；p->right->left=s；s->right=p->right；

(B)s->left=p；s->right=p->right；p->right=s；p->right->left=s；

(C)p->right=s；p->right->left=s；s->left=p；s->right=p->right；

(D)s->left=p；s->right=p->right；p->right->left=s；p->right=s；

34.一個棧的進棧序列是a，b，c，d，e，則棧的不行能的輸出序列是C。

A．edcbaB．decbaC．dceabD．Abcde

A：a,b,c,d,e進，之后依次出棧

B：a,b,c,d,進，d出，e進，e,c,b,a出

D：a進a出，b進b出……e進e出

C：的話dce都好辦，之后的ab做不到

這道題就是沒告知你進棧的同時可以隨時出棧==

二、填空題

1.數(shù)據(jù)的物理結(jié)構(gòu)主要包括挨次存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)兩種狀況。

2.數(shù)據(jù)結(jié)構(gòu)從規(guī)律上劃分為三種基本類型：線性結(jié)構(gòu)、樹型結(jié)構(gòu)和圖型結(jié)構(gòu)。

3.

4.公式：二維數(shù)組A中任一元素aij的存儲位置：（LOC（0，0）是a00的存儲位置）

LOC(i，j)=LOC（0，0）+（b2*i+j）L

5.迅速排序的時光性能分析

最好狀況：

每一次劃分對一個記錄定位后，該記錄的左側(cè)子表與右側(cè)子表的長度相同，為O(nlog2n)。

最壞狀況：

每次劃分只得到一個比上一次劃分少一個記錄的子序列（另一個子序列為空），為O(n2)。

平均狀況：為O(nlog2n)。

6.在迅速排序、堆排序、歸并排序中，___歸并______排序是穩(wěn)定的。

7.在堆排序的過程中，對任一分支結(jié)點舉行篩運算的時光復(fù)雜度為_O(log2n)_____，囫圇堆

排序過程的時光復(fù)雜度為___O(nlog2n)_____。

8.迅速排序的最壞時光復(fù)雜度為O(n2)，平均時光復(fù)雜度為O(nlog2n)。

9.散列表中解決矛盾的兩種辦法是開放定址法和鏈地址法。

10.在堆排序和迅速排序中，假如從平均狀況下排序的速度最快的角度來考慮應(yīng)最好挑選___

迅速_____排序，假如從節(jié)約存儲空間的角度來考慮則最好挑選__堆______排序。

三、推斷題

全對或全錯得5分

1．調(diào)用一次深度優(yōu)先遍歷可以拜訪到圖中的全部頂點。（×）

2．分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。（√）3．冒泡排序在初始關(guān)鍵字序列為逆序的狀況下執(zhí)行的交換次數(shù)最多。（√）

4．滿二叉樹一定是徹低二叉樹，徹低二叉樹不一定是滿二叉樹。（√）

5．設(shè)一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的外形。（×）6．層次遍歷初始堆可以得到一個有序的序列。（×）

7．設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT，則二叉樹BT中一定沒有右子樹。（√）

8．線性表的挨次存儲結(jié)構(gòu)比鏈式存儲結(jié)構(gòu)更好。（×）

9．中序遍歷二叉排序樹可以得到一個有序的序列。（√）

10.迅速排序是排序算法中平均性能最好的一種排序。（√）

11．不論是入隊列操作還是入棧操作，在挨次存儲結(jié)構(gòu)上都需要考慮“溢出”狀況。（√）12．當向二叉排序樹中插入一個結(jié)點，則該結(jié)點一定成為葉子結(jié)點。（√）

13．設(shè)某堆中有n個結(jié)點，則在該堆中插入一個新結(jié)點的時光復(fù)雜度為O(log2n)。（√）14．徹低二叉樹中的葉子結(jié)點只可能在最后兩層中浮現(xiàn)。（√）

15．哈夫曼樹中沒有度數(shù)為1的結(jié)點。（√）

16．對連通圖舉行深度優(yōu)先遍歷可以拜訪到該圖中的全部頂點。（√）

17．先序遍歷一棵二叉排序樹得到的結(jié)點序列不一定是有序的序列。（√）

18．由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。（×）

19．線性表中的全部元素都有一個前驅(qū)元素和后繼元素。（×）

20.帶權(quán)無向圖的最小生成樹是唯一的。（×）

21.假如兩個關(guān)鍵字的值不等但哈希函數(shù)值相等，則稱這兩個關(guān)鍵字為同義詞。（√）

22.設(shè)初始記錄關(guān)鍵字基本有序，則迅速排序算法的時光復(fù)雜度為O(nlog2n)。（×）

23.分塊查找的基本思想是首先在索引表中舉行查找，以便確定給定的關(guān)鍵字可能存在的塊號，然后再在相應(yīng)的塊內(nèi)舉行挨次查找。（√）

24.二維數(shù)組和多維數(shù)組均不是特別的線性結(jié)構(gòu)。（×）

25.向二叉排序樹中插入一個結(jié)點需要比較的次數(shù)可能大于該二叉樹的高度。（×）

26.假如某個有向圖的鄰接表中第i條單鏈表為空，則第i個頂點的出度為零。（√）

27.非空的雙向循環(huán)鏈表中任何結(jié)點的前驅(qū)指針均不為空。（√）

28.不論線性表采納挨次存儲結(jié)構(gòu)還是鏈式存儲結(jié)構(gòu)，刪除值為X的結(jié)點的時光復(fù)雜度均為O(n)。（√）

29.圖的深度優(yōu)先遍歷算法中需要設(shè)置一個標志數(shù)組，以便區(qū)別圖中的每個頂點是否被拜訪過。（√）

30.稀疏矩陣的壓縮存儲可以用一個三元組表來表示稀疏矩陣中的非0元素。（√）

31.有向圖的鄰接表和逆鄰接表中表結(jié)點的個數(shù)不一定相等。(×)

32.對鏈表舉行插入和刪除操作時不必移動鏈表中結(jié)點。(√)

33.子串“ABC”在主串“AABCABCD”中的位置為2。(√)

34.若一個葉子結(jié)點是某二叉樹的中序遍歷序列的最后一個結(jié)點，則它必是該二叉樹的先序遍歷序列中的最后一個結(jié)點。(√)

35.希爾排序算法的時光復(fù)雜度為O(n2)。(×)

36.用鄰接矩陣作為圖的存儲結(jié)構(gòu)時，則其所占用的存儲空間與圖中頂點數(shù)無關(guān)而與圖中邊數(shù)有關(guān)。(×)

37.中序遍歷一棵二叉排序樹可以得到一個有序的序列。(√)

38.入棧操作和入隊列操作在鏈式存儲結(jié)構(gòu)上實現(xiàn)時不需要考慮棧溢出的狀況。(√)

39.挨次表查找指的是在挨次存儲結(jié)構(gòu)上舉行查找。（×）

40.堆是徹低二叉樹，徹低二叉樹不一定是堆。（√）

四、簡答題

1、四類數(shù)據(jù)結(jié)構(gòu)

答；Ⅰ、集合；結(jié)構(gòu)中的數(shù)據(jù)元素之間除了“同屬于一個集合”的關(guān)系外，別無其他關(guān)系。

Ⅱ、線性結(jié)構(gòu)：結(jié)構(gòu)中數(shù)據(jù)元素之間存在一個對一個的關(guān)系。

Ⅲ、樹形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個對多個的關(guān)系。

Ⅳ、圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多個對多個的關(guān)系。

2、什么叫穩(wěn)定的排序？列出基本穩(wěn)定排序的算法。

答：假定在Ki=Kj（1≤i≤n，1≤j≤n，i≠j）,且在排序前的序列中Ri率先于Rj（即inext==0)return;

elsefor(q=head,p=head->next;p!=0;p=q->next)

{

for(s=head;s!=q->next;s=s->next)if(s->dat