1、數據結構期末復習練習題( 適用范圍：廣西電大開放專科計算機類專業 )廣西電大理工教學部計算中心第一章 緒 論 一、單選題 1. 一個數組元素ai與_的表示等價。 A、 *(a+i) B、 a+i C、 *a+i D、 &a+i 2. 對于兩個函數，若函數名相同，但只是_不同則不是重載函數。 A、 參數類型 B、 參數個數 C、 函數類型 3. 若需要利用形參直接訪問實參，則應把形參變量說明為_參數 A、 指針 B、 引用 C、 值 4. 下面程序段的時間復雜度為_。 for(int i=0; i<m; i+) for(int j=0; j<n; j+) aij=i*j; A

2、、 O(m2) B、 O(n2) C、 O(m*n) D、 O(m+n) 5. 執行下面程序段時，執行S語句的次數為_。 for(int i=1; i<=n; i+) for(int j=1; j<=i; j+) S; A、 n2 B、 n2/2 C、 n(n+1) D、 n(n+1)/2 6. 下面算法的時間復雜度為_。 int f( unsigned int n ) if ( n=0 | n=1 ) return 1; else return n*f(n-1); A、 O(1) B、 O(n) C、 O(n2) D、 O(n!) 二、填空題 1. 數據的邏輯結構被分為_、_、_

3、和_四種。 2. 數據的存儲結構被分為_、_、_和_四種。 3. 在線性結構、樹形結構和圖形結構中，前驅和后繼結點之間分別存在著_、_和_的聯系。 4. 一種抽象數據類型包括_和_兩個部分。 5. 當一個形參類型的長度較大時，應最好說明為_，以節省參數值的傳輸時間和存儲參數的空間。 6. 當需要用一個形參訪問對應的實參時，則該形參應說明為_。 7. 在函數中對引用形參的修改就是對相應_的修改，對_形參的修改只局限在該函數的內部，不會反映到對應的實參上。 8. 當需要進行標準I/O操作時，則應在程序文件中包含_頭文件，當需要進行文件I/O操作時，則應在程序文件中包含_頭文件。 9. 在包含有_頭

4、文件的程序文件中，使用_能夠產生出020之間的一個隨機整數。 10. 一個數組a所占有的存儲空間的大小即數組長度為_，下標為i的元素ai的存儲地址為_，或者為_。 11. 函數重載要求_、_或_有所不同。 12. 對于雙目操作符，其重載函數帶有_個參數，其中至少有一個為_的類型。 13. 若對象ra和rb中至少有一個是屬于用戶定義的類型，則執行ra=rb時，需要調用_重載函數，該函數的第一個參數應與_的類型相同，第二個參數應與_的類型相同。 14. 從一維數組an中順序查找出一個最大值元素的時間復雜度為_，輸出一個二維數組bmn中所有元素值的時間復雜度為_。 15. 在下面程序段中，s=s+p

5、語句的執行次數為_，p*=j語句的執行次數為_，該程序段的時間復雜度為_。 int i=0,s=0; while(+i<=n) int p=1; for(int j=1;j<=i;j+) p*=j; s=s+p; 16. 一個算法的時間復雜度為(3n2+2nlog2n+4n-7)/(5n)，其數量級表示為_。第二章 線性表 一、單選題 1在一個長度為n的順序存儲線性表中，向第i個元素(1in+1)之前插入一個新元素時，需要從后向前依次后移 個元素。 A、n-i B、n-i+1 C、n-i-1 D、i 2在一個長度為n的順序存儲線性表中，刪除第i個元素(1in+1)時，需要從前向后依

6、次前移 個元素。 A、n-i B、n-i+1 C、n-i-1 D、i 3在一個長度為n的線性表中順序查找值為x的元素時，查找時的平均查找長度（即x同元素的平均比較次數，假定查找每個元素的概率都相等）為 。 A、n B、n/2 C、(n+1)/2 D、(n-1)/2 4在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結點，則執行 。 A、HL = p; p->next = HL; B、p->next = HL; HL = p; C、p->next = HL; p = HL; D、p->next = HL->next; HL->next = p; 5在一個單

7、鏈表HL中，若要在指針q所指的結點的后面插入一個由指針p所指的結點，則執行 。 A、q->next = p->next ; p->next = q; B、p->next = q->next; q = p; C、q->next = p->next; p->next = q; D、p->next = q->next ; q->next = p; 6在一個單鏈表HL中，若要刪除由指針q所指向結點的后繼結點，則執行 。 A、p = q->next ; p->next = q->next; B、p = q->nex

8、t ; q->next = p; C、p = q->next ; q->next = p->next; D、q->next = q->next->next; q->next = q; 二、填空題1在線性表的單鏈接存儲結構中，每個結點包含有兩個域，一個叫 域，另一個叫 域。 2在下面數組a中鏈接存儲著一個線性表，表頭指針為a0.next，則該線性表為 。 3對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復雜度為 ，在表尾插入元素的時間復雜度為 。 4對于一個長度為n的單鏈接存儲的線性表，在表頭插入元素的時間復雜度為 ，在表尾插入元素的時間

9、復雜度為 。5在線性表的順序存儲中，若一個元素的下標為i，則它的前驅元素的下標為 ，后繼元素的下標為 。 6在線性表的單鏈接存儲中，若一個元素所在結點的地址為p，則其后繼結點的地址為 ，若假定p為一個數組a中的下標，則其后繼結點的下標為 。 7在循環單鏈表中，最后一個結點的指針指向 結點。 8在雙向鏈表中每個結點包含有兩個指針域，一個指向其 結點，另一個指向其 結點。 9在循環雙向鏈表中表頭結點的左指針域指向 結點，最后一個結點的右指針域指向 結點。 10在以HL為表頭指針的帶表頭附加結點的單鏈表和循環單鏈表中，鏈表為空的條件分別為 和 。 三、應用題 1在下面的每個程序段中，假定線性表La的

10、類型為List，元素類型ElemType為int，并假定每個程序段是連續執行的，試寫出每個程序段執行后所得到的線性表La。 (1) InitList(La); int a=48,26,57,34,62,79; for(i=0; i<6; i+) InsertFront(La,ai); TraverseList(La); (2) InitList(La); for(i=0; i<6; i+) Insert(La,ai); TraverseList(La); (3) ClearList(La); for(i=0; i<6; i+) InsertRear(La,ai); Delet

11、e(La, a5); Sort(La); Insert(La,a5/2); TraverseList(La);2寫出下面函數被調用執行后，得到的以HL為表頭指針的單鏈表中的數據元素序列。void AA(LNode * & HL) InitList(HL); InsertRear(HL,30); InsertRear(HL,50);int a5 = 15,8,9,26,12;for ( int i=0; i<5; i+ ) InsertFront(HL,ai); 3對于List類型的線性表，編寫出下列每個算法。(1) 從線性表中刪除具有最小值的元素并由函數返回，空出的位置由最后一個

12、元素填補，若線性表為空則顯示出錯信息并退出運行。 (2) 從線性表中刪除第i個元素并由函數返回。 (3) 向線性表中第i個元素位置插入一個元素。 (4) 從線性表中刪除具有給定值x的所有元素。 4對于結點類型為LNode的單鏈表，編寫出下列每個算法。(1) 刪除單鏈表中的第i個結點。 (2) 在有序單鏈表中插入一個元素x的結點。 (3) 從單鏈表中查找出所有元素的最大值，該值由函數返回，若單鏈表為空，則顯示出錯信息并停止運行。(4) 統計出單鏈表中結點的值等于給定值x的結點數。第三章 稀疏矩陣和廣義表 一、單選題 1. 在稀疏矩陣的帶行指針向量的鏈接存儲中，每個行單鏈表中的結點都具有相同的_。

13、 A、 行號 B、 列號 C、 元素值 D、 地址 2. 設一個廣義表中結點的個數為n，則求廣義表深度算法的時間復雜度為_。 A、 O(1) B、 O(n) C、 O(n2) D、 O(log2n) 二、填空題 1. 在一個稀疏矩陣中，每個非零元素所對應的三元組包括該元素的_、_和_三項。 2. 在稀疏矩陣所對應的三元組線性表中，每個三元組元素按_為主序、_為輔序的次序排列。 3. 在初始化一個稀疏矩陣的函數定義中，矩陣形參應說明為_參數。 4. 在稀疏矩陣的順序存儲中，利用一個數組來存儲非零元素，該數組的長度應_對應三元組線性表的長度。 5在稀疏矩陣的帶行指針向量的鏈接存儲中，每個結點包含有

14、_個域，在相應的十字鏈接存儲中，每個結點包含有_個域。 6在稀疏矩陣的十字鏈接存儲中，每個結點的down指針域指向_相同的下一個結點，right指針域指向_相同的下一個結點。 7一個廣義表中的元素分為_元素和_元素兩類。 8一個廣義表的深度等于_嵌套的最大層數。 9在廣義表的存儲結構中，每個結點均包含有_個域。 10在廣義表的存儲結構中，單元素結點與表元素結點有一個域對應不同，各自分別為_域和_域。 11若把整個廣義表也看為一個表結點，則該結點的tag域的值為_，next域的值為_。 三、應用題 1. 已知一個稀疏矩陣如下圖所示： 0 4 0 0 0 0 0 0 0 0 -3 0 0 1 8

15、0 0 0 0 0 0 0 0 0 5 0 0 0 0 -7 0 0 0 2 0 0 0 0 6 0 0 0 具有6行×7列的一個稀疏矩陣(1) 寫出它的三元組線性表； (2) 給出它的順序存儲表示； (3) 給出它的轉置矩陣的三元組線性表和順序存儲表示； 2. 畫出下列每個廣義表的帶表頭附加結點的鏈接存儲結構圖并分別計算出它們的長度和深度。 (1) A=()(2) B=(a,b,c)(3) C=(a,(b,(c)(4) D=(a,b),(c,d)(5) E=(a,(b,(c,d),(e)(6) F=(a,(b,(),c),(d),e)第四章 棧和隊列一、單選題 1棧的插入與刪除操作

16、在 進行。 A、棧頂 B、棧底 C、任意位置 D、指定位置 2當利用大小為N的一維數組順序存儲一個棧時，假定用top=N表示棧空，則向這個棧插入一個元素時，首先應執行 語句修改top指針。 A、top+ B、top- C、top=0 D、top 3若讓元素1，2，3依次進棧，則出棧次序不可能出現 種情況。 A、3，2，1 B、2，1，3 C、3，1，2 D、1，3，2 4在一個循環順序隊列中，隊首指針指向隊首元素的 位置。 A、前一個 B、后一個 C、當前 D、后面 5當利用大小為N的一維數組順序存儲一個循環隊列時，該隊列的最大長度為 。 A、N-2 B、N-1 C、N D、N+1 6從一個循

17、環順序隊列刪除元素時，首先需要 。 A、前移一位隊首指針 B、后移一位隊首指針 C、取出隊首指針所指位置上的元素 D、取出隊尾指針所指位置上的元素7假定一個循環順序隊列的隊首和隊尾指針分別為f和r，則判斷隊空的條件是 。 A、f+1=r B、r+1=f C、f=0 D、f=r 8假定一個鏈隊的隊首和隊尾指針分別為front和rear，則判斷隊空的條件是 。 A、front=rear B、front!=NULL C、rear!=NULL D、front=NULL二、填空題 1隊列的插入操作在 進行，刪除操作在 進行。 2棧又稱為 表，隊列又稱為 表。 3向一個順序棧插入一個元素時，首先使 后移一

18、個位置，然后把待插入元素 到這個位置上。 4從一個棧中刪除元素時，首先取出 ，然后再前移一位 。 5在一個循環順序隊列Q中，判斷隊空的條件為 ，判斷隊滿的條件為 。 6在一個順序棧中，若棧頂指針等于 ，則為空棧；若棧頂指針等于 ，則為滿棧。 7在一個鏈棧中，若棧頂指針等于NULL，則為 ；在一個鏈隊中，若隊首指針與隊尾指針的值相同，則表示該隊列為 或該隊列為 。 8向一個鏈棧插入一個新結點時，首先把棧頂指針的值賦給 ，然后把新結點的存儲位置賦給 。 9從一個鏈棧中刪除一個結點時，需要把棧頂結點 的值賦給 。 10向一個順序隊列插入元素時，需要首先移動 ，然后再向所指位置 新插入的元素。 11、

19、當用長度為N的一維數組順序存儲一個棧時，假定用top=N表示棧空，則表示棧滿的條件為 。 12向一個棧頂指針為HS的鏈棧中插入一個新結點*P果，應執行 和 操作。 13從一個棧頂指針為HS的非空鏈棧中刪除結點并不需要返回棧頂結點的值和回收結點時，應執行 操作。 14假定front和rear分別為一個鏈隊的隊首和隊尾指針，則該鏈隊中只有一個結點的條件為 。 15. 中綴算術表達式3+4/(25-(6+15)*8 所對應的后綴算術表達式為 。 16. 后綴算術表達式24 8 + 3 * 4 10 7 - * / 所對應的中綴算術表達式為 ，其值為 。三、應用題執行下面函數調用后得到的輸出結果是什么

20、？void AF(Queue & Q) InitQueue(Q); int a4 = 5,8,12,15 ; for ( int i=0; i<4; i+ ) QInsert(Q,ai); QInsert(Q,QDelete(Q); QInsert(Q,30); QInsert(Q,QDelete(Q)+10); while ( ! QueueEmpty(Q) ) cout <<QDelete(Q)<< ; 四、編程題 裴波那契(Fibonacci)數列的定義為：它的第1項和第2項均為1，以后各項為其前兩項之和。若裴波那契數列中的第n項用Fib(n)表示，

21、則計算公式為： ì 1 (n=1或2) Fib(n)=í î Fib(n-1)+Fib(n-2) (n>=2)試編寫出計算Fib(n)的遞歸算法和非遞歸算法，并分析它們的時間復雜度和空間復雜度。第五章 樹和二叉樹 一、填空題 1對于一棵具有n個結點的樹，該樹中所有結點的度數之和為_。 2. 假定一棵三叉樹的結點個數為50，則它的最小深度為_，最大深度為_。 3在一棵三叉樹中，度為3的結點數有2個，度為2的結點數有1個，度為1的結點數為2個，那么度為0的結點數有_個。 4一棵深度為5的滿二叉樹中的結點數為_個，一棵深度為3的滿三叉樹中的結點數為_個。 5假定一

22、棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)，則樹中所含的結點數為_個，樹的深度為_，樹的度為_。 6假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)，則度為3、2、1、0的結點數分別為_、_、_和_個。 7. 假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)，則結點H的雙親結點為_，孩子結點為_。 8在一棵二叉樹中，假定雙分支結點數為5個，單分支結點數為6個，則葉子結點數為_個。 9對于一棵二叉樹，若一個結點的編號為i，則它的左孩子結點的編號為_，右孩子結點的編號為_，雙親結點的編號為_。 10在一棵二叉樹中，第5層上的結點數最多為_。 1

23、1假定一棵二叉樹的結點數為18，則它的最小深度為_，最大深度為_。 12一棵二叉樹的廣義表表示為a(b(c,d),e(f(,g)，則e結點的雙親結點為_，左孩子結點為_，右孩子結點為_。 13. 一棵二叉樹的廣義表表示為a(b(c,d),e(f(,g)，它含有雙親結點_個，單分支結點_個，葉子結點_個。 14. 假定一棵二叉樹順序存儲在一維數組a中，則ai元素的左孩子元素為_，右孩子元素為_，雙親元素(i>1)為_。 15假定一棵二叉樹順序存儲在一維數組a中，但讓編號為1的結點存入a0元素中，讓編號為2的結點存入a1元素中，其余類推，則編號為i結點的左孩子結點對應的存儲位置為_，若編號為

24、i結點的存儲位置用j表示，則其左孩子結點對應的存儲位置為_。 16.若對一棵二叉樹從0開始進行結點編號，并按此編號把它順序存儲到一維數組a中，即編號為0的結點存儲到a0中，其余類推，則ai元素的左孩子元素為_，右孩子元素為_，雙親元素(i>0)為_。 17對于一棵具有n個結點的二叉樹，對應二叉鏈表中指針總數為_個，其中_個用于指向孩子結點，_個指針空閑著。 18. 一棵二叉樹廣義表表示為a(b(d(,h),c(e,f(g,i(k)，該樹的結點數為_個，深度為_。 19. 假定一棵二叉樹廣義表表示為a(b(c),d(e,f)，則對它進行的先序遍歷結果為_，中序遍歷結果為_，后序遍歷結果為_

25、，按層遍歷結果為_。 20. 假定一棵普通樹的廣義表表示為a(b(e),c(f(h,i,j),g),d)，則先根遍歷結果為_，按層遍歷結果為_。 二、應用題 1. 已知一棵具有n個結點的完全二叉樹被順序存儲于一維數組的A1An元素中，試編寫一個算法打印出編號為i的結點的雙親和所有孩子。 2. 編寫一算法，求出一棵二叉樹中所有結點數和葉子結點數，假定分別用變參C1和C2統計所有結點數和葉子結點數，初值均為0。 3. 對于右圖所示的樹： (1) 寫出先根遍歷得到的結點序列； (2) 寫出按層遍歷得到的結點序列； (3) 畫出轉換后得到的二叉樹和二叉鏈表。第六章 二叉樹的應用 一、單選題 1. 從二

26、叉搜索樹中查找一個元素時，其時間復雜度大致為_。 A、 O(n) B、 O(1) C、 O(log2n) D、 O(n2) 2. 向二叉搜索樹中插入一個元素時，其時間復雜度大致為_。 A、 O(1) B、 O(log2n ) C、 O(n) D、 O(nlog2n) 3. 根據n個元素建立一棵二叉搜索樹時，其時間復雜度大致為_。 A、 O(n) B、 O(log2n ) C、 O(n2) D、 O(nlog2n) 4. 從堆中刪除一個元素的時間復雜度為_。 A、 O(1) B、 O(n) C、 O(log2n) D、 O(nlog2n) 5. 向堆中插入一個元素的時間復雜度為_。 A、 O(l

27、og2n) B、 O(n) C、 O(1) D、 O(nlog2n) 6. 由權值分別為3,8,6,2,5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為_。 A、 24 B、 48 C、 72 D、 53 二、填空題 1. 在一棵二叉搜索樹中，每個分支結點的左子樹上所有結點的值一定_該結點的值，右子樹上所有結點的值一定_該結點的值。 2對一棵二叉搜索樹進行中序遍歷時，得到的結點序列是一個_。 3從一棵二叉搜索樹中查找一個元素時，若元素的值等于根結點的值，則表明_，若元素的值小于根結點的值，則繼續向_查找，若元素的大于根結點的值，則繼續向_查找。 4在一個堆的順序存儲中，若一個元素的下標為i，則

28、它的左孩子元素的下標為_，右孩子元素的下標為_。 5. 在一個小根堆中，堆頂結點的值是所有結點中的_，在一個大根堆中，堆頂結點的值是所有結點中的_。 6當從一個小根堆中刪除一個元素時，需要把_元素填補到_位置，然后再按條件把它逐層_調整。三、應用題1. 已知一組元素為(46,25,78,62,12,37,70,29)，畫出按元素排列順序輸入生成的一棵二叉搜索樹。 2. 空堆開始依次向堆中插入線性表（38,64,52,15,73,40,48,55,26,12）中的每個元素，請以線性表的形式給出每插入一個元素后堆的狀態。 3. 已知一個堆為（12,15,40,38,26,52,48,64），若需要

29、從堆中依次刪除四個元素，請給出每刪除一個元素后堆的狀態。4. 有七個帶權結點，其權值分別為3,7,8,2,6,10,14，試以它們為葉子結點構造一棵哈夫曼樹，并計算出帶權路徑長度WPL。四、算法設計1編寫在以BST為樹根指針的二叉搜索樹上進行查找值為item的結點的非遞歸算法，若查找成功則由item帶回整個結點的值并返回true，否則返回false。 bool Find( BTreeNode * BST , ElemType & item )2下面的算法功能是向HBT堆中插入一個值為item的元素，使得插入后仍是一個堆。請在畫有橫線的地方填上合適的語句，完成其功能。void AH(He

30、ap & HBT , const ElemType item) / 形參HBT為一個小根堆 HBT.heapHBT.size=item; HBT.size+; ElemType x=item int i=HBT.size-1; while ( i != 0 ) int j= ; if ( x>=HBT.heapj) break; ; ; HBT.heapi=x; 第七章 圖 一、填空題 1在一個圖中，所有頂點的度數之和等于所有邊數的_倍。 2在一個具有n個頂點的無向完全圖中，包含有_條邊，在一個具有n個頂點的有向完全圖中，包含有_條邊。 3. 在一個具有n個頂點的無向圖中，要連通

31、所有頂點則至少需要_條邊。 4表示圖的三種存儲結構為_、_和_。 5. 對于一個具有n個頂點的圖，若采用鄰接矩陣表示，則矩陣大小為_。 6對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應的鄰接表中，所含邊結點分別為_和_條。 7. 在有向圖的鄰接表和逆鄰接表表示中，每個頂點鄰接表分別鏈接著該頂點的所有_和_結點。 8對于一個具有n個頂點和e條邊的有向圖和無向圖，若采用邊集數組表示，則存于數組中的邊數分別為_和_條。 9對于一個具有n個頂點和e條邊的無向圖，當分別采用鄰接矩陣、鄰接表和邊集數組表示時，求任一頂點度數的時間復雜度依次為_、_和_。 10. 假定一個圖具有n個頂點和e條邊，則采

32、用鄰接矩陣、鄰接表和邊集數組表示時，其相應的空間復雜度分別為_、_和_。 11. 對用鄰接矩陣表示的圖進行任一種遍歷時，其時間復雜度為_，對用鄰接表表示的圖進行任一種遍歷時，其時間復雜度為_。12對于下面的無向圖G1，假定用鄰接矩陣表示，則從頂點v0開始進行深度優先搜索遍歷得到的頂點序列為_，從頂點v0開始進行廣度優先搜索遍歷得到的頂點序列為_。13. 對于下面的有向圖G2，假定用鄰接矩陣表示，則從頂點v0開始進行深度優先搜索遍歷得到的頂點序列為_，從頂點v0開始進行廣度優先搜索遍歷得到的頂點序列為_。 14. 對于下面的帶權圖G3，其最小生成樹的權為_。 15對于下面的帶權圖G3，若從頂點v

33、0出發，則按照普里姆算法生成的最小生成樹中，依次得到的各條邊為_。 16. 對于下面的帶權圖G3，若按照克魯斯卡爾算法產生最小生成樹，則得到的各條邊依次為_。 17假定用一維數組dn存儲一個AOV網中用于拓撲排序的頂點入度，則值為0的元素被鏈接成為一個_。 18. 對于一個具有n個頂點和e條邊的連通圖，其生成樹中的頂點數和邊數分別為_和_。 二、應用題 1. 對于下圖G4和G5，按下列條件試分別寫出從頂點v0出發按深度優先搜索遍歷得到的頂點序列和按廣度優先搜索遍歷得到的頂點序列。 (1) 假定它們均采用鄰接矩陣表示; (2) 假定它們均采用鄰接表表示，并且假定每個頂點鄰接表中的結點是按頂點序號

34、從大到小的次序鏈接的。 2. 對于下圖G6，試給出一種拓撲序列，若在它的鄰接表存儲結構中，每個頂點鄰接表中的邊結點都是按照終點序號從大到小鏈接的，則按此給出唯一一種拓撲序列。第八章 查找 一、填空題 1以順序查找方法從長度為n的線性表中查找一個元素時，平均查找長度為_，時間復雜度為_。 2以二分查找方法從長度為n的線性有序表中查找一個元素時，平均查找長度小于等于_，時間復雜度為_。 3以二分查找方法從長度為12的有序表中查找一個元素時，平均查找長度為_。 4以二分查找方法查找一個線性表時，此線性表必須是_存儲的_表。 5從有序表(12,18,30,43,56,78,82,95)中依次二分查找4

35、3和56元素時，其查找長度分別為_和_。 6對于二分查找所對應的判定樹，它既是一棵_，又是一棵_。 7假定對長度n=50的有序表進行二分查找，則對應的判定樹高度為_，判定樹中前5層的結點數為_，最后一層的結點數為_。 8在索引表中，每個索引項至少包含有_域和_域這兩項。 9假定一個線性表為(12,23,74,55,63,40,82,36)，若按Key % 3條件進行劃分，使得同一余數的元素成為一個子表，則得到的三個子表分別為_、_和_。10. 假定一個線性表為(”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”)，若按照字符串的第一

36、個字母進行劃分，使得同一個字母被劃分在一個子表中，則得到的a,b,c三個子表的長度分別為_、_和_。 11在線性表的_存儲中，無法查找到一個元素的前驅或后繼元素。 12在線性表的_存儲中，對每一個元素只能采用順序查找。 13假定對線性表(38,25,74,52,48)進行散列存儲，采用H(K)=K % 7作為散列函數，若分別采用線性探查法和鏈接法處理沖突，則對各自散列表進行查找的平均查找長度分別為_和_。 14假定要對長度n=100的線性表進行散列存儲，并采用鏈接法處理沖突，則對于長度m=20的散列表，每個散列地址的單鏈表的長度平均為_。 15. 在線性表的散列存儲中，處理沖突有_和_兩種方法

37、。 16對于線性表(18,25,63,50,42,32,90)進行散列存儲時，若選用H(K)=K % 9作為散列函數，則散列地址為0的元素有_個，散列地址為5的元素有_個。 二、應用題 1. 假定查找有序表A25中每一元素的概率相等，試分別求出進行順序、二分查找每一元素時的平均查找長度。 2. 假定一個待散列存儲的線性表為(32,75,29,63,48,94,25,46,18,70)，散列地址空間為HT13，若采用除留余數法構造散列函數和線性探查法處理沖突，試求出每一元素的散列地址，畫出最后得到的散列表，求出平均查找長度。 3. 假定一個待散列存儲的線性表為(32,75,29,63,48,94

38、,25,46,18,70)，散列地址空間為HT11，若采用除留余數法構造散列函數和鏈接法處理沖突，試求出每一元素的散列地址，畫出最后得到的散列表，求出平均查找長度。三、算法設計 設計在有序表An中按二分查找關鍵字為K的遞歸和非遞歸算法。第九章 排序 一、填空題 1每次從無序表中取出一個元素，把它插入到有序表中的適當位置，此種排序方法叫做_排序；每次從無序表中挑選出一個最小或最大元素，把它交換到有序表的一端，此種排序方法叫做_排序。 2每次直接或通過基準元素間接比較兩個元素，若出現逆序排列時就交換它們的位置，此種排序方法叫做_排序；每次使兩個相鄰的有序表合并成一個有序表的排序方法叫做_排序。 3

39、在直接選擇排序中，記錄比較次數的時間復雜度為_，記錄移動次數的時間復雜度為_。 4. 在堆排序的過程中，對n個記錄建立初始堆需要進行_次篩運算，由初始堆到堆排序結束，需要對樹根結點進行_次篩運算。 5在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為_，整個堆排序過程的時間復雜度為_。 6假定一組記錄的排序碼為(46,79,56,38,40,84)，則利用堆排序方法建立的初始堆為_。 7. 快速排序在平均情況下的時間復雜度為_，在最壞情況下的時間復雜度為_。 8快速排序在平均情況下的空間復雜度為_，在最壞情況下的空間復雜度為_。 9在快速排序方法中，進行每次劃分時，是從當前待排序區間的_

40、向_依次查找出處于逆序的元素并交換之，最后將基準元素交換到一個確定位置，從而以該位置把當前區間劃分為前后兩個子區間。 10. 假定一組記錄的排序碼為(46,79,56,38,40,80)，對其進行快速排序的一次劃分的結果為_。 11. 假定一組記錄的排序碼為(46,79,56,38,40,80)，對其進行快速排序的過程中，對應二叉搜索樹的深度為_，分支結點數為_。 12在二路歸并排序中，對n個記錄進行歸并的趟數為_。 13. 在歸并排序中，進行每趟歸并的時間復雜度為_，整個排序過程的時間復雜度為_，空間復雜度為_。 14對20個記錄進行歸并排序時，共需要進行_趟歸并，在第三趟歸并時是把長度為_

41、的有序表兩兩歸并為長度為_的有序表。 15假定一組記錄的排序碼為(46,79,56,38,40,80)，對其進行歸并排序的過程中，第二趟歸并后的結果為_。 二、應用題 已知一組元素的排序碼為 (46，74，16，53，14，26，40，38，86，65，27，34) (1) 利用直接插入排序的方法寫出每次向前面有序表插入一個元素后的排列結果。 (2) 利用直接選擇排序方法寫出每次選擇和交換后的排列結果。 (3) 利用堆排序的方法寫出在構成初始堆和利用堆排序的過程中，每次篩運算后的排列結果，并畫出初始堆所對應的完全二叉樹。 (4) 利用快速排序的方法寫出每一層劃分后的排列結果，并畫出由此快速排序

42、得到的二叉搜索樹。 (5) 利用歸并排序的方法寫出每一趟二路歸并排序后的結果。 三、算法設計完成從一維數組An上進行快速排序的遞歸算法。void QuickSort( ElemType A , int s , int t ) int i = s, j = t+1; ElemType x = As; do do i+; while ( ) ; / 填寫一個循環條件do j-; while ( Aj.stn > x.stn );if ( i<j ) ElemType temp = Ai ; Ai = Aj ; Aj = temp; while ( i<j ); As = Aj; Aj = x; if ( s<j-1 ) ; if ( j+1<t ) ; 數據結構期末復習練習題答案