數(shù)據(jù)結構練習題及參考答案

1、數(shù)據(jù)結構練習題第一部分 緒 論 一、單選題 1. 一個數(shù)組元素ai與_的表示等價。 A、 *(a+i) B、 a+i C、 *a+i D、 &a+i 2. 對于兩個函數(shù)，若函數(shù)名相同，但只是_不同則不是重載函數(shù)。 A、 參數(shù)類型 B、 參數(shù)個數(shù) C、 函數(shù)類型 3. 若需要利用形參直接訪問實參，則應把形參變量說明為_參數(shù) A、 指針 B、 引用 C、 值 4. 下面程序段的時間復雜度為_。 for(int i=0; im; i+) for(int j=0; jn; j+) aij=i*j; A、 O(m2) B、 O(n2) C、 O(m*n) D、 O(m+n) 5. 執(zhí)行下面程序段時，執(zhí)行

2、S語句的次數(shù)為_。 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. 數(shù)據(jù)的邏輯結構被分為_、_、_和_四種。 2. 數(shù)據(jù)的存儲結構被分為_、_、_和_四種。 3. 在線性結構、樹形結構和圖形結構中，前驅和后繼結點之間

3、分別存在著_、_和_的聯(lián)系。 4. 一種抽象數(shù)據(jù)類型包括_和_兩個部分。 5. 當一個形參類型的長度較大時，應最好說明為_，以節(jié)省參數(shù)值的傳輸時間和存儲參數(shù)的空間。 6. 當需要用一個形參訪問對應的實參時，則該形參應說明為_。 7. 在函數(shù)中對引用形參的修改就是對相應_的修改，對_形參的修改只局限在該函數(shù)的內(nèi)部，不會反映到對應的實參上。 8. 當需要進行標準I/O操作時，則應在程序文件中包含_頭文件，當需要進行文件I/O操作時，則應在程序文件中包含_頭文件。 9. 在包含有_頭文件的程序文件中，使用_能夠產(chǎn)生出020之間的一個隨機整數(shù)。 10. 一個數(shù)組a所占有的存儲空間的大小即數(shù)組長度為_，

4、下標為i的元素ai的存儲地址為_，或者為_。 11. 函數(shù)重載要求_、_或_有所不同。 12. 對于雙目操作符，其重載函數(shù)帶有_個參數(shù)，其中至少有一個為_的類型。 13. 若對象ra和rb中至少有一個是屬于用戶定義的類型，則執(zhí)行ra=rb時，需要調(diào)用_重載函數(shù)，該函數(shù)的第一個參數(shù)應與_的類型相同，第二個參數(shù)應與_的類型相同。 14. 從一維數(shù)組an中順序查找出一個最大值元素的時間復雜度為_，輸出一個二維數(shù)組bmn中所有元素值的時間復雜度為_。 15. 在下面程序段中，s=s+p語句的執(zhí)行次數(shù)為_，p*=j語句的執(zhí)行次數(shù)為_，該程序段的時間復雜度為_。 int i=0,s=0; while(+i

5、=n) int p=1; for(int j=1;jnext = HL; B、p-next = HL; HL = p; C、p-next = HL; p = HL; D、p-next = HL-next; HL-next = p; 5在一個單鏈表HL中，若要在指針q所指的結點的后面插入一個由指針p所指的結點，則執(zhí)行 。 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中，若要刪除由指針

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

7、性表，在表頭插入元素的時間復雜度為 ，在表尾插入元素的時間復雜度為 。5在線性表的順序存儲中，若一個元素的下標為i，則它的前驅元素的下標為 ，后繼元素的下標為 。 6在線性表的單鏈接存儲中，若一個元素所在結點的地址為p，則其后繼結點的地址為 ，若假定p為一個數(shù)組a中的下標，則其后繼結點的下標為 。 7在循環(huán)單鏈表中，最后一個結點的指針指向 結點。 8在雙向鏈表中每個結點包含有兩個指針域，一個指向其 結點，另一個指向其 結點。 9在循環(huán)雙向鏈表中表頭結點的左指針域指向 結點，最后一個結點的右指針域指向 結點。 10在以HL為表頭指針的帶表頭附加結點的單鏈表和循環(huán)單鏈表中，鏈表為空的條件分別為 和

8、 。 三、應用題 1在下面的每個程序段中，假定線性表La的類型為List，元素類型ElemType為int，并假定每個程序段是連續(xù)執(zhí)行的，試寫出每個程序段執(zhí)行后所得到的線性表La。 (1) InitList(La); int a=48,26,57,34,62,79; for(i=0; i6; i+) InsertFront(La,ai); TraverseList(La); (2) InitList(La); for(i=0; i6; i+) Insert(La,ai); TraverseList(La); (3) ClearList(La); for(i=0; i6; i+) InsertR

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

10、出的位置由最后一個元素填補，若線性表為空則顯示出錯信息并退出運行。 (2) 從線性表中刪除第i個元素并由函數(shù)返回。 (3) 向線性表中第i個元素位置插入一個元素。 (4) 從線性表中刪除具有給定值x的所有元素。 4對于結點類型為LNode的單鏈表，編寫出下列每個算法。(1) 刪除單鏈表中的第i個結點。 (2) 在有序單鏈表中插入一個元素x的結點。 (3) 從單鏈表中查找出所有元素的最大值，該值由函數(shù)返回，若單鏈表為空，則顯示出錯信息并停止運行。(4) 統(tǒng)計出單鏈表中結點的值等于給定值x的結點數(shù)。第三部分 棧和隊列一、單選題 1棧的插入與刪除操作在 進行。 A、棧頂 B、棧底 C、任意位置 D、

11、指定位置 2當利用大小為N的一維數(shù)組順序存儲一個棧時，假定用top=N表示?？眨瑒t向這個棧插入一個元素時，首先應執(zhí)行 語句修改top指針。 A、top+ B、top- C、top=0 D、top 3若讓元素1，2，3依次進棧，則出棧次序不可能出現(xiàn) 種情況。 A、3，2，1 B、2，1，3 C、3，1，2 D、1，3，2 4在一個循環(huán)順序隊列中，隊首指針指向隊首元素的 位置。 A、前一個 B、后一個 C、當前 D、后面 5當利用大小為N的一維數(shù)組順序存儲一個循環(huán)隊列時，該隊列的最大長度為 。 A、N-2 B、N-1 C、N D、N+1 6從一個循環(huán)順序隊列刪除元素時，首先需要 。 A、前移一位隊

12、首指針 B、后移一位隊首指針 C、取出隊首指針所指位置上的元素 D、取出隊尾指針所指位置上的元素7假定一個循環(huán)順序隊列的隊首和隊尾指針分別為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向一個順序棧插入一個元素時，首先使 后移一個位置，然后把待插入元素 到這個位置上。 4從一個

13、棧中刪除元素時，首先取出 ，然后再前移一位 。 5在一個循環(huán)順序隊列Q中，判斷隊空的條件為 ，判斷隊滿的條件為 。 6在一個順序棧中，若棧頂指針等于 ，則為空棧；若棧頂指針等于 ，則為滿棧。 7在一個鏈棧中，若棧頂指針等于NULL，則為 ；在一個鏈隊中，若隊首指針與隊尾指針的值相同，則表示該隊列為 或該隊列為 。 8向一個鏈棧插入一個新結點時，首先把棧頂指針的值賦給 ，然后把新結點的存儲位置賦給 。 9從一個鏈棧中刪除一個結點時，需要把棧頂結點 的值賦給 。 10向一個順序隊列插入元素時，需要首先移動 ，然后再向所指位置 新插入的元素。 11、當用長度為N的一維數(shù)組順序存儲一個棧時，假定用to

14、p=N表示?？?，則表示棧滿的條件為 。 12向一個棧頂指針為HS的鏈棧中插入一個新結點*P果，應執(zhí)行 和 操作。 13從一個棧頂指針為HS的非空鏈棧中刪除結點并不需要返回棧頂結點的值和回收結點時，應執(zhí)行 操作。 14假定front和rear分別為一個鏈隊的隊首和隊尾指針，則該鏈隊中只有一個結點的條件為 。 15. 中綴算術表達式3+4/(25-(6+15)*8 所對應的后綴算術表達式為 。 16. 后綴算術表達式24 8 + 3 * 4 10 7 - * / 所對應的中綴算術表達式為 ，其值為 。三、應用題執(zhí)行下面函數(shù)調(diào)用后得到的輸出結果是什么？void AF(Queue & Q) InitQ

15、ueue(Q); int a4 = 5,8,12,15 ; for ( int i=0; i4; i+ ) QInsert(Q,ai); QInsert(Q,QDelete(Q); QInsert(Q,30); QInsert(Q,QDelete(Q)+10); while ( ! QueueEmpty(Q) ) cout QDelete(Q)=2)試編寫出計算Fib(n)的遞歸算法和非遞歸算法，并分析它們的時間復雜度和空間復雜度。第四部分 稀疏矩陣和廣義表 一、單選題 1. 在稀疏矩陣的帶行指針向量的鏈接存儲中，每個行單鏈表中的結點都具有相同的_。 A、 行號 B、 列號 C、 元素值 D、

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

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

18、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對于一棵具有n個結點的樹，該樹中所有結點的度數(shù)之和為_。 2. 假定

19、一棵三叉樹的結點個數(shù)為50，則它的最小深度為_，最大深度為_。 3在一棵三叉樹中，度為3的結點數(shù)有2個，度為2的結點數(shù)有1個，度為1的結點數(shù)為2個，那么度為0的結點數(shù)有_個。 4一棵深度為5的滿二叉樹中的結點數(shù)為_個，一棵深度為3的滿三叉樹中的結點數(shù)為_個。 5假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)，則樹中所含的結點數(shù)為_個，樹的深度為_，樹的度為_。 6假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)，則度為3、2、1、0的結點數(shù)分別為_、_、_和_個。 7. 假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)，則結點H的雙親結點

20、為_，孩子結點為_。 8在一棵二叉樹中，假定雙分支結點數(shù)為5個，單分支結點數(shù)為6個，則葉子結點數(shù)為_個。 9對于一棵二叉樹，若一個結點的編號為i，則它的左孩子結點的編號為_，右孩子結點的編號為_，雙親結點的編號為_。 10在一棵二叉樹中，第5層上的結點數(shù)最多為_。 11假定一棵二叉樹的結點數(shù)為18，則它的最小深度為_，最大深度為_。 12一棵二叉樹的廣義表表示為a(b(c,d),e(f(,g)，則e結點的雙親結點為_，左孩子結點為_，右孩子結點為_。 13. 一棵二叉樹的廣義表表示為a(b(c,d),e(f(,g)，它含有雙親結點_個，單分支結點_個，葉子結點_個。 14. 假定一棵二叉樹順序

21、存儲在一維數(shù)組a中，則ai元素的左孩子元素為_，右孩子元素為_，雙親元素(i1)為_。 15假定一棵二叉樹順序存儲在一維數(shù)組a中，但讓編號為1的結點存入a0元素中，讓編號為2的結點存入a1元素中，其余類推，則編號為i結點的左孩子結點對應的存儲位置為_，若編號為i結點的存儲位置用j表示，則其左孩子結點對應的存儲位置為_。 16.若對一棵二叉樹從0開始進行結點編號，并按此編號把它順序存儲到一維數(shù)組a中，即編號為0的結點存儲到a0中，其余類推，則ai元素的左孩子元素為_，右孩子元素為_，雙親元素(i0)為_。 17對于一棵具有n個結點的二叉樹，對應二叉鏈表中指針總數(shù)為_個，其中_個用于指向孩子結點，

22、_個指針空閑著。 18. 一棵二叉樹廣義表表示為a(b(d(,h),c(e,f(g,i(k)，該樹的結點數(shù)為_個，深度為_。 19. 假定一棵二叉樹廣義表表示為a(b(c),d(e,f)，則對它進行的先序遍歷結果為_，中序遍歷結果為_，后序遍歷結果為_，按層遍歷結果為_。 20. 假定一棵普通樹的廣義表表示為a(b(e),c(f(h,i,j),g),d)，則先根遍歷結果為_，按層遍歷結果為_。 二、應用題 1. 已知一棵具有n個結點的完全二叉樹被順序存儲于一維數(shù)組的A1An元素中，試編寫一個算法打印出編號為i的結點的雙親和所有孩子。 2. 編寫一算法，求出一棵二叉樹中所有結點數(shù)和葉子結點數(shù)，假

23、定分別用變參C1和C2統(tǒng)計所有結點數(shù)和葉子結點數(shù)，初值均為0。 3. 對于右圖所示的樹： (1) 寫出先根遍歷得到的結點序列； (2) 寫出按層遍歷得到的結點序列； (3) 畫出轉換后得到的二叉樹和二叉鏈表。二叉樹的應用 一、單選題 1. 從二叉搜索樹中查找一個元素時，其時間復雜度大致為_。 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. 根據(jù)n個元素建立一棵二叉搜索樹時，其時間復雜度大致為_。 A、 O(n) B、 O

24、(log2n ) C、 O(n2) D、 O(nlog2n) 4. 從堆中刪除一個元素的時間復雜度為_。 A、 O(1) B、 O(n) C、 O(log2n) D、 O(nlog2n) 5. 向堆中插入一個元素的時間復雜度為_。 A、 O(log2n) 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對一棵二叉搜索樹進

25、行中序遍歷時，得到的結點序列是一個_。 3從一棵二叉搜索樹中查找一個元素時，若元素的值等于根結點的值，則表明_，若元素的值小于根結點的值，則繼續(xù)向_查找，若元素的大于根結點的值，則繼續(xù)向_查找。 4在一個堆的順序存儲中，若一個元素的下標為i，則它的左孩子元素的下標為_，右孩子元素的下標為_。 5. 在一個小根堆中，堆頂結點的值是所有結點中的_，在一個大根堆中，堆頂結點的值是所有結點中的_。 6當從一個小根堆中刪除一個元素時，需要把_元素填補到_位置，然后再按條件把它逐層_調(diào)整。三、應用題1. 已知一組元素為(46,25,78,62,12,37,70,29)，畫出按元素排列順序輸入生成的一棵二叉

26、搜索樹。 2. 空堆開始依次向堆中插入線性表（38,64,52,15,73,40,48,55,26,12）中的每個元素，請以線性表的形式給出每插入一個元素后堆的狀態(tài)。 3. 已知一個堆為（12,15,40,38,26,52,48,64），若需要從堆中依次刪除四個元素，請給出每刪除一個元素后堆的狀態(tài)。4. 有七個帶權結點，其權值分別為3,7,8,2,6,10,14，試以它們?yōu)槿~子結點構造一棵哈夫曼樹，并計算出帶權路徑長度WPL。四、算法設計1編寫在以BST為樹根指針的二叉搜索樹上進行查找值為item的結點的非遞歸算法，若查找成功則由item帶回整個結點的值并返回true，否則返回false。 b

27、ool Find( BTreeNode * BST , ElemType & item )2下面的算法功能是向HBT堆中插入一個值為item的元素，使得插入后仍是一個堆。請在畫有橫線的地方填上合適的語句，完成其功能。void AH(Heap & 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;

28、第六部分 圖 一、填空題 1在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的_倍。 2在一個具有n個頂點的無向完全圖中，包含有_條邊，在一個具有n個頂點的有向完全圖中，包含有_條邊。 3. 在一個具有n個頂點的無向圖中，要連通所有頂點則至少需要_條邊。 4表示圖的三種存儲結構為_、_和_。 5. 對于一個具有n個頂點的圖，若采用鄰接矩陣表示，則矩陣大小為_。 6對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應的鄰接表中，所含邊結點分別為_和_條。 7. 在有向圖的鄰接表和逆鄰接表表示中，每個頂點鄰接表分別鏈接著該頂點的所有_和_結點。 8對于一個具有n個頂點和e條邊的有向圖和無向圖，若采用邊

29、集數(shù)組表示，則存于數(shù)組中的邊數(shù)分別為_和_條。 9對于一個具有n個頂點和e條邊的無向圖，當分別采用鄰接矩陣、鄰接表和邊集數(shù)組表示時，求任一頂點度數(shù)的時間復雜度依次為_、_和_。 10. 假定一個圖具有n個頂點和e條邊，則采用鄰接矩陣、鄰接表和邊集數(shù)組表示時，其相應的空間復雜度分別為_、_和_。 11. 對用鄰接矩陣表示的圖進行任一種遍歷時，其時間復雜度為_，對用鄰接表表示的圖進行任一種遍歷時，其時間復雜度為_。12對于下面的無向圖G1，假定用鄰接矩陣表示，則從頂點v0開始進行深度優(yōu)先搜索遍歷得到的頂點序列為_，從頂點v0開始進行廣度優(yōu)先搜索遍歷得到的頂點序列為_。13. 對于下面的有向圖G2，

30、假定用鄰接矩陣表示，則從頂點v0開始進行深度優(yōu)先搜索遍歷得到的頂點序列為_，從頂點v0開始進行廣度優(yōu)先搜索遍歷得到的頂點序列為_。 14. 對于下面的帶權圖G3，其最小生成樹的權為_。 15對于下面的帶權圖G3，若從頂點v0出發(fā)，則按照普里姆算法生成的最小生成樹中，依次得到的各條邊為_。 16. 對于下面的帶權圖G3，若按照克魯斯卡爾算法產(chǎn)生最小生成樹，則得到的各條邊依次為_。 17假定用一維數(shù)組dn存儲一個AOV網(wǎng)中用于拓撲排序的頂點入度，則值為0的元素被鏈接成為一個_。 18. 對于一個具有n個頂點和e條邊的連通圖，其生成樹中的頂點數(shù)和邊數(shù)分別為_和_。 二、應用題 1. 對于下圖G4和G

31、5，按下列條件試分別寫出從頂點v0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點序列和按廣度優(yōu)先搜索遍歷得到的頂點序列。 (1) 假定它們均采用鄰接矩陣表示; (2) 假定它們均采用鄰接表表示，并且假定每個頂點鄰接表中的結點是按頂點序號從大到小的次序鏈接的。 2. 對于下圖G6，試給出一種拓撲序列，若在它的鄰接表存儲結構中，每個頂點鄰接表中的邊結點都是按照終點序號從大到小鏈接的，則按此給出唯一一種拓撲序列。第七部分 查找 一、填空題 1以順序查找方法從長度為n的線性表中查找一個元素時，平均查找長度為_，時間復雜度為_。 2以二分查找方法從長度為n的線性有序表中查找一個元素時，平均查找長度小于等于_，時間復雜

32、度為_。 3以二分查找方法從長度為12的有序表中查找一個元素時，平均查找長度為_。 4以二分查找方法查找一個線性表時，此線性表必須是_存儲的_表。 5從有序表(12,18,30,43,56,78,82,95)中依次二分查找43和56元素時，其查找長度分別為_和_。 6對于二分查找所對應的判定樹，它既是一棵_，又是一棵_。 7假定對長度n=50的有序表進行二分查找，則對應的判定樹高度為_，判定樹中前5層的結點數(shù)為_，最后一層的結點數(shù)為_。 8在索引表中，每個索引項至少包含有_域和_域這兩項。 9假定一個線性表為(12,23,74,55,63,40,82,36)，若按Key % 3條件進行劃分，使

33、得同一余數(shù)的元素成為一個子表，則得到的三個子表分別為_、_和_。10. 假定一個線性表為(”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”)，若按照字符串的第一個字母進行劃分，使得同一個字母被劃分在一個子表中，則得到的a,b,c三個子表的長度分別為_、_和_。 11在線性表的_存儲中，無法查找到一個元素的前驅或后繼元素。 12在線性表的_存儲中，對每一個元素只能采用順序查找。 13假定對線性表(38,25,74,52,48)進行散列存儲，采用H(K)=K % 7作為散列函數(shù)，若分別采用線性探查法和鏈接法處理沖突，則對各自散列表進行

34、查找的平均查找長度分別為_和_。 14假定要對長度n=100的線性表進行散列存儲，并采用鏈接法處理沖突，則對于長度m=20的散列表，每個散列地址的單鏈表的長度平均為_。 15. 在線性表的散列存儲中，處理沖突有_和_兩種方法。 16對于線性表(18,25,63,50,42,32,90)進行散列存儲時，若選用H(K)=K % 9作為散列函數(shù)，則散列地址為0的元素有_個，散列地址為5的元素有_個。 二、應用題 1. 假定查找有序表A25中每一元素的概率相等，試分別求出進行順序、二分查找每一元素時的平均查找長度。 2. 假定一個待散列存儲的線性表為(32,75,29,63,48,94,25,46,1

35、8,70)，散列地址空間為HT13，若采用除留余數(shù)法構造散列函數(shù)和線性探查法處理沖突，試求出每一元素的散列地址，畫出最后得到的散列表，求出平均查找長度。 3. 假定一個待散列存儲的線性表為(32,75,29,63,48,94,25,46,18,70)，散列地址空間為HT11，若采用除留余數(shù)法構造散列函數(shù)和鏈接法處理沖突，試求出每一元素的散列地址，畫出最后得到的散列表，求出平均查找長度。三、算法設計 設計在有序表An中按二分查找關鍵字為K的遞歸和非遞歸算法。第八部分 排序 一、填空題 1每次從無序表中取出一個元素，把它插入到有序表中的適當位置，此種排序方法叫做_排序；每次從無序表中挑選出一個最小

36、或最大元素，把它交換到有序表的一端，此種排序方法叫做_排序。 2每次直接或通過基準元素間接比較兩個元素，若出現(xiàn)逆序排列時就交換它們的位置，此種排序方法叫做_排序；每次使兩個相鄰的有序表合并成一個有序表的排序方法叫做_排序。 3在直接選擇排序中，記錄比較次數(shù)的時間復雜度為_，記錄移動次數(shù)的時間復雜度為_。 4. 在堆排序的過程中，對n個記錄建立初始堆需要進行_次篩運算，由初始堆到堆排序結束，需要對樹根結點進行_次篩運算。 5在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為_，整個堆排序過程的時間復雜度為_。 6假定一組記錄的排序碼為(46,79,56,38,40,84)，則利用堆排序方法

37、建立的初始堆為_。 7. 快速排序在平均情況下的時間復雜度為_，在最壞情況下的時間復雜度為_。 8快速排序在平均情況下的空間復雜度為_，在最壞情況下的空間復雜度為_。 9在快速排序方法中，進行每次劃分時，是從當前待排序區(qū)間的_向_依次查找出處于逆序的元素并交換之，最后將基準元素交換到一個確定位置，從而以該位置把當前區(qū)間劃分為前后兩個子區(qū)間。 10. 假定一組記錄的排序碼為(46,79,56,38,40,80)，對其進行快速排序的一次劃分的結果為_。 11. 假定一組記錄的排序碼為(46,79,56,38,40,80)，對其進行快速排序的過程中，對應二叉搜索樹的深度為_，分支結點數(shù)為_。 12在

38、二路歸并排序中，對n個記錄進行歸并的趟數(shù)為_。 13. 在歸并排序中，進行每趟歸并的時間復雜度為_，整個排序過程的時間復雜度為_，空間復雜度為_。 14對20個記錄進行歸并排序時，共需要進行_趟歸并，在第三趟歸并時是把長度為_的有序表兩兩歸并為長度為_的有序表。 15假定一組記錄的排序碼為(46,79,56,38,40,80)，對其進行歸并排序的過程中，第二趟歸并后的結果為_。 二、應用題 已知一組元素的排序碼為 (46，74，16，53，14，26，40，38，86，65，27，34) (1) 利用直接插入排序的方法寫出每次向前面有序表插入一個元素后的排列結果。 (2) 利用直接選擇排序方法寫出每次選擇和交換后的排列結果。 (3) 利用堆