1、一、選擇題(20分)1下面關于線性表的敘述錯誤的是（ D ）。(A) 線性表采用順序存儲必須占用一片連續的存儲空間(B) 線性表采用鏈式存儲不必占用一片連續的存儲空間(C) 線性表采用鏈式存儲便于插入和刪除操作的實現(D) 線性表采用順序存儲便于插入和刪除操作的實現2設某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（ A ）。(A) BADC(B) BCDA(C) CDAB(D) CBDA3設某棵二叉樹中有2000個結點，則該二叉樹的最小高度為（ C ）。(A) 9(B) 10(C) 11(D) 124設二叉排序樹中有n個結點，則在二叉排序樹的平均平均

2、查找長度為（ B ）。(A) O(1)(B) O(log2n)(C)(D) O(n2)5設有5000個待排序的記錄關鍵字，如果需要用最快的方法選出其中最小的10個記錄關鍵字，則用下列（ B ）方法可以達到此目的。(A) 快速排序(B) 堆排序(C) 歸并排序(D) 插入排序第9小題分析：9快速排序、歸并排序和插入排序必須等到整個排序結束后才能夠求出最小的10個數，而堆排序只需要在初始堆的基礎上再進行10次篩選即可，每次篩選的時間復雜度為O(log2n)。6.下列四種排序中（ D ）的空間復雜度最大。(A) 插入排序(B) 冒泡排序(C) 堆排序(D) 歸并排序7設一維數組中有n個數組元素，則讀

3、取第i個數組元素的平均時間復雜度為（C ）。(A) O(n)(B) O(nlog2n)(C) O(1)(D) O(n2)8設一棵二叉樹的深度為k，則該二叉樹中最多有（D ）個結點。(A) 2k-1(B) 2k(C) 2k-1(D) 2k-19在二叉排序樹中插入一個結點的時間復雜度為（B ）。(A) O(1)(B) O(n)(C) O(log2n)(D) O(n2)10設用鏈表作為棧的存儲結構則退棧操作（ B ）。(A) 必須判別棧是否為滿(B) 必須判別棧是否為空(C) 判別棧元素的類型(D) 對棧不作任何判別11下列四種排序中（A ）的空間復雜度最大。(A) 快速排序(B) 冒泡排序(C)

4、希爾排序(D) 堆12設某二叉樹中度數為0的結點數為N0，度數為1的結點數為Nl，度數為2的結點數為N2，則下列等式成立的是（ C ）。(A) N0=N1+1(B) N0=Nl+N2(C) N0=N2+1(D) N0=2N1+l13.設有序順序表中有n個數據元素，則利用二分查找法查找數據元素X的最多比較次數不超過（A ）。(A) log2n+1(B) log2n-1(C) log2n(D) log2(n+1)14數據的最小單位是（ A ）。(A) 數據項(B) 數據類型(C) 數據元素(D) 數據變量15設一個有序的單鏈表中有n個結點，現要求插入一個新結點后使得單鏈表仍然保持有序，則該操作的時

5、間復雜度為（ D ）。(A) O(log2n)(B) O(1)(C) O(n2)(D) O(n)16設一棵m叉樹中度數為0的結點數為N0，度數為1的結點數為Nl，度數為m的結點數為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)Nm17設輸入序列是1、2、3、n，經過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是（C ）。(A) n-i(B) n-1-i(C) n+1-i(D) 不能確定18時間復雜度不受數據初始狀態影響而恒為O(nlog2n)的是（

6、A ）。(A) 堆排序(B) 冒泡排序(C) 希爾排序(D) 快速排序19設二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（D ）。(A) 空或只有一個結點(B) 高度等于其結點數(C) 任一結點無左孩子(D) 任一結點無右孩子20順序查找不論在順序線性表中還是在鏈式線性表中的時間復雜度為（A ）。(A) O(n)(B) O(n2)(C) O(n1/2)(D) O(1og2n)21二路歸并排序的時間復雜度為（ C ）。(A) O(n)(B) O(n2)(C) O(nlog2n)(D) O(1og2n)22. 深度為k的完全二叉樹中最少有（B ）個結點。(A) 2k-1-1(

7、B) 2k-1(C) 2k-1+1(D) 2k-123.設二叉排序樹上有n個結點，則在二叉排序樹上查找結點的平均時間復雜度為（D ）。(A) O(n)(B) O(n2)(C) O(nlog2n)(D) O(1og2n)24（ B ）二叉排序樹可以得到一個從小到大的有序序列。(A) 先序遍歷(B) 中序遍歷(C) 后序遍歷(D) 層次遍歷25設按照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號，則編號為i結點的左孩子結點的編號為（B ）。(A) 2i+1(B) 2i(C) i/2(D) 2i-126程序段s=i=0；do i=i+1； s=s+i；while(i<=n)；的時間復

8、雜度為（A ）。(A) O(n)(B) O(nlog2n)(C) O(n2)(D) O(n3/2)27.設指針變量top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為（ D ）。(A) top=top+1;(B) top=top-1;(C) top->next=top;(D) top=top->next;28.建立一個長度為n的有序單鏈表的時間復雜度為（ C ）(A) O(n)(B) O(1)(C) O(n2)(D) O(log2n)29.在二叉排序樹中插入一個關鍵字值的平均時間復雜度為（ B ）。(A) O(n)(B) O(1og2n)(C) O(nlog2n)(D) O(n2

9、)30.設一棵完全二叉樹中有65個結點，則該完全二叉樹的深度為（ B ）。(A) 8(B) 7(C) 6(D) 531.隊列是一種（A ）的線性表。(A) 先進先出(B) 先進后出(C) 只能插入(D) 只能刪除 32.利用直接插入排序法的思想建立一個有序線性表的時間復雜度為（ C ）。 (A) O(n)(B) O(nlog2n)(C) O(n2)(D) O(1og2n)33設指針變量p指向雙向鏈表中結點A，指針變量s指向被插入的結點X，則在結點A的后面插入結點X的操作序列為（D ）。(A) p->right=s； s->left=p； p->right->left=s

10、； 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，則棧的不可能的輸出序列是

11、 C 。Aedcba Bdecba Cdceab DAbcdeA：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. 數據的物理結構主要包括順序存儲結構和鏈式存儲結構兩種情況。2. 數據結構從邏輯上劃分為三種基本類型：線性結構、樹型結構和圖型結構。3.4. 公式：二維數組A中任一元素aij的存儲位置：（LOC（0，0）是a00的存儲位置） LOC(i，j)=LOC（0，0）+（b2*i+j）L5.快速排序的時間性能分析最好情況：每一次劃

12、分對一個記錄定位后，該記錄的左側子表與右側子表的長度相同，為O(nlog2n)。最壞情況：每次劃分只得到一個比上一次劃分少一個記錄的子序列（另一個子序列為空），為 O(n2)。 平均情況：為O(nlog2n)。6. 在快速排序、堆排序、歸并排序中，_歸并_排序是穩定的。7.在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為_O(log2n)_，整個堆排序過程的時間復雜度為_ O(nlog2n)_。8.快速排序的最壞時間復雜度為O(n2)，平均時間復雜度為O(nlog2n)。9.散列表中解決沖突的兩種方法是開放定址法和鏈地址法。10.在堆排序和快速排序中，如果從平均情況下排序的速度最快的角

13、度來考慮應最好選擇_快速_排序，如果從節省存儲空間的角度來考慮則最好選擇_堆_排序。3、 判斷題全對或全錯得5分1調用一次深度優先遍歷可以訪問到圖中的所有頂點。（× ）2分塊查找的平均查找長度不僅與索引表的長度有關，而且與塊的長度有關。（ ）3冒泡排序在初始關鍵字序列為逆序的情況下執行的交換次數最多。（ ）4滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（ ）5設一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（ × ）6層次遍歷初始堆可以得到一個有序的序列。（× ）7設一棵樹T可以轉化成二叉樹BT，則二叉樹BT中一定沒有右子樹。（ ）8線

14、性表的順序存儲結構比鏈式存儲結構更好。（ × ）9中序遍歷二叉排序樹可以得到一個有序的序列。（ ）10.快速排序是排序算法中平均性能最好的一種排序。（ ）11不論是入隊列操作還是入棧操作，在順序存儲結構上都需要考慮“溢出”情況。（ ）12當向二叉排序樹中插入一個結點，則該結點一定成為葉子結點。（ ）13設某堆中有n個結點，則在該堆中插入一個新結點的時間復雜度為O(log2n)。（ ）14完全二叉樹中的葉子結點只可能在最后兩層中出現。（ ）15哈夫曼樹中沒有度數為1的結點。（ ）16對連通圖進行深度優先遍歷可以訪問到該圖中的所有頂點。（ ）17先序遍歷一棵二叉排序樹得到的結點序列不一定

15、是有序的序列。（ ）18由樹轉化成二叉樹，該二叉樹的右子樹不一定為空。（× ）19線性表中的所有元素都有一個前驅元素和后繼元素。（ × ）20.帶權無向圖的最小生成樹是唯一的。（ × ）21.如果兩個關鍵字的值不等但哈希函數值相等，則稱這兩個關鍵字為同義詞。（ ）22.設初始記錄關鍵字基本有序，則快速排序算法的時間復雜度為O(nlog2n)。（ × ）23.分塊查找的基本思想是首先在索引表中進行查找，以便確定給定的關鍵字可能存在的塊號，然后再在相應的塊內進行順序查找。（ ）24.二維數組和多維數組均不是特殊的線性結構。（× ）25.向二叉排序樹

16、中插入一個結點需要比較的次數可能大于該二叉樹的高度。（ × ）26.如果某個有向圖的鄰接表中第i條單鏈表為空，則第i個頂點的出度為零。（ ）27.非空的雙向循環鏈表中任何結點的前驅指針均不為空。（ ）28.不論線性表采用順序存儲結構還是鏈式存儲結構，刪除值為X的結點的時間復雜度均為O(n)。（ ）29.圖的深度優先遍歷算法中需要設置一個標志數組，以便區分圖中的每個頂點是否被訪問過。（ ）30.稀疏矩陣的壓縮存儲可以用一個三元組表來表示稀疏矩陣中的非0元素。（ ）31.有向圖的鄰接表和逆鄰接表中表結點的個數不一定相等。(× )32.對鏈表進行插入和刪除操作時不必移動鏈表中結點

17、。( )33.子串“ABC”在主串“AABCABCD”中的位置為2。( )34.若一個葉子結點是某二叉樹的中序遍歷序列的最后一個結點，則它必是該二叉樹的先序遍歷序列中的最后一個結點。( )35.希爾排序算法的時間復雜度為O(n2)。(× )36.用鄰接矩陣作為圖的存儲結構時，則其所占用的存儲空間與圖中頂點數無關而與圖中邊數有關。(× )37.中序遍歷一棵二叉排序樹可以得到一個有序的序列。()38.入棧操作和入隊列操作在鏈式存儲結構上實現時不需要考慮棧溢出的情況。( )39.順序表查找指的是在順序存儲結構上進行查找。（ × ）40.堆是完全二叉樹，完全二叉樹不一定是

18、堆。（ ）4、 簡答題1、 四類數據結構答；、集合；結構中的數據元素之間除了“同屬于一個集合”的關系外，別無其他關系。、線性結構：結構中數據元素之間存在一個對一個的關系。、樹形結構：結構中的數據元素之間存在一個對多個的關系。、圖形結構或網狀結構：結構中的數據元素之間存在多個對多個的關系。2、什么叫穩定的排序？列出基本穩定排序的算法。答：假定在Ki=Kj（1in，1jn，ij）,且在排序前的序列中Ri領先于Rj（即i<j）。若在排序后的序列中Ri仍領先于Rj，則稱所用的排序方法是穩定的；反之，若可能使排序后的序列中Rj仍領先于Ri，則稱所用的排序方法是不穩定的。基本穩定的排序方法：直接插入

19、排序、冒泡排序、歸并排序、基數排序。不穩定的排序方法：直接選擇排序、希爾排序、快速排序和堆排序。3、 散列函數的基本概念、設計原則。 答：基本概念：在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關系f，使每個關鍵字和結構中一個唯一的存儲位置相對應，我們稱這種對應關系為f的散列函數。 設計原則：根據散列函數的思想建立一個散列表，在建立一個散列表之前需要解決兩個主要問題。（1） 構造一個合適的散列表。常用方法有：直接定址法、數字分析法、平方取和法、折疊法、保留余數法、隨機數法。（2） 處理沖突的方法：開放定址法、鏈地址法、建立一個公共溢出區。4、 （給出一個時間復雜度或一種表示方法，分析每一個字母的含義）略5、 在一個雙向循環鏈表中，我們要實現數據元素的插入所對應基本的操作。略五、綜合題1.已知二叉樹的前序遍歷序列是AEFBGCDHIKJ，中序遍歷序列是EFAGBCHKIJD，畫出此二叉樹，并畫出它的后序線索二叉樹。解：2、在鏈式存儲結構上設計直接插入排序算法解：void straightinsertsort(lklist *&head) lklist *s,*p,*q; int t; if (he