數(shù)據(jù)結(jié)構(gòu)練習(xí)題及參考答案

1、數(shù)據(jù)結(jié)構(gòu)練習(xí)題第一部分 緒 論 一、單選題 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. 若需要利用形參直接訪問實參，則應(yīng)把形參變量說明為_參數(shù) A、 指針 B、 引用 C、 值 4. 下面程序段的時間復(fù)雜度為_。 for(int i=0; i<m; i+) for(int j=0; j<n; j+) aij=i*j; A、 O(m2) B、 O(n2) C、 O(m*n) D、 O(m+n) 5.

2、 執(zhí)行下面程序段時，執(zhí)行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. 下面算法的時間復(fù)雜度為_。 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ù)的邏輯結(jié)構(gòu)被分為_、_、_和_四種。 2. 數(shù)據(jù)的存儲結(jié)構(gòu)被分為_、_、_和_四種。 3. 在線性結(jié)構(gòu)、

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

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

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

6、個長度為n的線性表中順序查找值為x的元素時，查找時的平均查找長度（即x同元素的平均比較次數(shù)，假定查找每個元素的概率都相等）為 。 A、n B、n/2 C、(n+1)/2 D、(n-1)/2 4在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)行 。 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在一個單鏈表HL中，若要在指針q所指的結(jié)點的后面插入一個由指針p所指的結(jié)點，則執(zhí)行

7、。 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所指向結(jié)點的后繼結(jié)點，則執(zhí)行 。 A、p = q->next ; p->next = q->next; B、p = q->next ; q->next = p; C、p = q->next ;

8、 q->next = p->next; D、q->next = q->next->next; q->next = q; 二、填空題1在線性表的單鏈接存儲結(jié)構(gòu)中，每個結(jié)點包含有兩個域，一個叫 域，另一個叫 域。 2在下面數(shù)組a中鏈接存儲著一個線性表，表頭指針為a0.next，則該線性表為 。 3對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復(fù)雜度為 ，在表尾插入元素的時間復(fù)雜度為 。 4對于一個長度為n的單鏈接存儲的線性表，在表頭插入元素的時間復(fù)雜度為 ，在表尾插入元素的時間復(fù)雜度為 。5在線性表的順序存儲中，若一個元素的下標(biāo)為i，則它的前驅(qū)元素的下

9、標(biāo)為 ，后繼元素的下標(biāo)為 。 6在線性表的單鏈接存儲中，若一個元素所在結(jié)點的地址為p，則其后繼結(jié)點的地址為 ，若假定p為一個數(shù)組a中的下標(biāo)，則其后繼結(jié)點的下標(biāo)為 。 7在循環(huán)單鏈表中，最后一個結(jié)點的指針指向 結(jié)點。 8在雙向鏈表中每個結(jié)點包含有兩個指針域，一個指向其 結(jié)點，另一個指向其 結(jié)點。 9在循環(huán)雙向鏈表中表頭結(jié)點的左指針域指向 結(jié)點，最后一個結(jié)點的右指針域指向 結(jié)點。 10在以HL為表頭指針的帶表頭附加結(jié)點的單鏈表和循環(huán)單鏈表中，鏈表為空的條件分別為 和 。 三、應(yīng)用題 1在下面的每個程序段中，假定線性表La的類型為List，元素類型ElemType為int，并假定每個程序段是連續(xù)執(zhí)行

10、的，試寫出每個程序段執(zhí)行后所得到的線性表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); Delete(La, a5); Sort(La); Insert(La,a5/2);

11、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; i<5; i+ ) InsertFront(HL,ai); 3對于List類型的線性表，編寫出下列每個算法。(1) 從線性表中刪除具有最小值的元素并由函數(shù)返回，空出的位置由最后一個元素填補，若線性表為空則顯示出錯信息并退出運行。 (2) 從線性表中刪除第i

12、個元素并由函數(shù)返回。 (3) 向線性表中第i個元素位置插入一個元素。 (4) 從線性表中刪除具有給定值x的所有元素。 4對于結(jié)點類型為LNode的單鏈表，編寫出下列每個算法。(1) 刪除單鏈表中的第i個結(jié)點。 (2) 在有序單鏈表中插入一個元素x的結(jié)點。 (3) 從單鏈表中查找出所有元素的最大值，該值由函數(shù)返回，若單鏈表為空，則顯示出錯信息并停止運行。(4) 統(tǒng)計出單鏈表中結(jié)點的值等于給定值x的結(jié)點數(shù)。第三部分 棧和隊列一、單選題 1棧的插入與刪除操作在 進行。 A、棧頂 B、棧底 C、任意位置 D、指定位置 2當(dāng)利用大小為N的一維數(shù)組順序存儲一個棧時，假定用top=N表示?？?，則向這個棧插入

13、一個元素時，首先應(yīng)執(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āng)前 D、后面 5當(dāng)利用大小為N的一維數(shù)組順序存儲一個循環(huán)隊列時，該隊列的最大長度為 。 A、N-2 B、N-1 C、N D、N+1 6從一個循環(huán)順序隊列刪除元素時，首先需要 。 A、前移一位隊首指針 B、后移一位隊首指針 C、取出隊首指針?biāo)肝恢蒙系脑?D、取出隊尾指針?biāo)肝恢蒙系脑?/p>

14、素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從一個棧中刪除元素時，首先取出 ，然后再前移一位 。 5在一個循環(huán)順序隊列Q中，判斷隊空的條件為 ，

15、判斷隊滿的條件為 。 6在一個順序棧中，若棧頂指針等于 ，則為空棧；若棧頂指針等于 ，則為滿棧。 7在一個鏈棧中，若棧頂指針等于NULL，則為 ；在一個鏈隊中，若隊首指針與隊尾指針的值相同，則表示該隊列為 或該隊列為 。 8向一個鏈棧插入一個新結(jié)點時，首先把棧頂指針的值賦給 ，然后把新結(jié)點的存儲位置賦給 。 9從一個鏈棧中刪除一個結(jié)點時，需要把棧頂結(jié)點 的值賦給 。 10向一個順序隊列插入元素時，需要首先移動 ，然后再向所指位置 新插入的元素。 11、當(dāng)用長度為N的一維數(shù)組順序存儲一個棧時，假定用top=N表示?？眨瑒t表示棧滿的條件為 。 12向一個棧頂指針為HS的鏈棧中插入一個新結(jié)點*P果，

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

17、; 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)數(shù)列的定義為：它的第1項和第2項均為1，以后各項為其前兩項之和。若裴波那契數(shù)列中的第n項用Fib(n)表示，則計算公式為： ì 1 (n=1或2) Fib(n)=í î Fib(n-1)+Fib(n-2) (n>=2

18、)試編寫出計算Fib(n)的遞歸算法和非遞歸算法，并分析它們的時間復(fù)雜度和空間復(fù)雜度。第四部分 稀疏矩陣和廣義表 一、單選題 1. 在稀疏矩陣的帶行指針向量的鏈接存儲中，每個行單鏈表中的結(jié)點都具有相同的_。 A、 行號 B、 列號 C、 元素值 D、 地址 2. 設(shè)一個廣義表中結(jié)點的個數(shù)為n，則求廣義表深度算法的時間復(fù)雜度為_。 A、 O(1) B、 O(n) C、 O(n2) D、 O(log2n) 二、填空題 1. 在一個稀疏矩陣中，每個非零元素所對應(yīng)的三元組包括該元素的_、_和_三項。 2. 在稀疏矩陣所對應(yīng)的三元組線性表中，每個三元組元素按_為主序、_為輔序的次序排列。 3. 在初始化

19、一個稀疏矩陣的函數(shù)定義中，矩陣形參應(yīng)說明為_參數(shù)。 4. 在稀疏矩陣的順序存儲中，利用一個數(shù)組來存儲非零元素，該數(shù)組的長度應(yīng)_對應(yīng)三元組線性表的長度。 5在稀疏矩陣的帶行指針向量的鏈接存儲中，每個結(jié)點包含有_個域，在相應(yīng)的十字鏈接存儲中，每個結(jié)點包含有_個域。 6在稀疏矩陣的十字鏈接存儲中，每個結(jié)點的down指針域指向_相同的下一個結(jié)點，right指針域指向_相同的下一個結(jié)點。 7一個廣義表中的元素分為_元素和_元素兩類。 8一個廣義表的深度等于_嵌套的最大層數(shù)。 9在廣義表的存儲結(jié)構(gòu)中，每個結(jié)點均包含有_個域。 10在廣義表的存儲結(jié)構(gòu)中，單元素結(jié)點與表元素結(jié)點有一個域?qū)?yīng)不同，各自分別為_域

20、和_域。 11若把整個廣義表也看為一個表結(jié)點，則該結(jié)點的tag域的值為_，next域的值為_。 三、應(yīng)用題 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 0 0 0 -7 0 0 0 2 0 0 0 0 6 0 0 0 具有6行×7列的一個稀疏矩陣(1) 寫出它的三元組線性表； (2) 給出它的順序存儲表示； (3) 給出它的轉(zhuǎn)置矩陣的三元組線性表和順序存儲表示； 2. 畫出下列每個廣義表的帶表頭附加結(jié)點的鏈接存儲結(jié)構(gòu)圖并分別計算出它們的長度和深度。 (1) A=()(2) B=(a,b,

21、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個結(jié)點的樹，該樹中所有結(jié)點的度數(shù)之和為_。 2. 假定一棵三叉樹的結(jié)點個數(shù)為50，則它的最小深度為_，最大深度為_。 3在一棵三叉樹中，度為3的結(jié)點數(shù)有2個，度為2的結(jié)點數(shù)有1個，度為1的結(jié)點數(shù)為2個，那么度為0的結(jié)點數(shù)有_個。 4一棵深度為5的滿二叉樹中的結(jié)點數(shù)為_個，一棵深度為3的滿三叉樹中的結(jié)點數(shù)為_個。 5假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)，則樹中所

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

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

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

25、,c(f(h,i,j),g),d)，則先根遍歷結(jié)果為_，按層遍歷結(jié)果為_。 二、應(yīng)用題 1. 已知一棵具有n個結(jié)點的完全二叉樹被順序存儲于一維數(shù)組的A1An元素中，試編寫一個算法打印出編號為i的結(jié)點的雙親和所有孩子。 2. 編寫一算法，求出一棵二叉樹中所有結(jié)點數(shù)和葉子結(jié)點數(shù)，假定分別用變參C1和C2統(tǒng)計所有結(jié)點數(shù)和葉子結(jié)點數(shù)，初值均為0。 3. 對于右圖所示的樹： (1) 寫出先根遍歷得到的結(jié)點序列； (2) 寫出按層遍歷得到的結(jié)點序列； (3) 畫出轉(zhuǎn)換后得到的二叉樹和二叉鏈表。二叉樹的應(yīng)用 一、單選題 1. 從二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為_。 A、 O(n) B、 O(1

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

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

28、點的值是所有結(jié)點中的_，在一個大根堆中，堆頂結(jié)點的值是所有結(jié)點中的_。 6當(dāng)從一個小根堆中刪除一個元素時，需要把_元素填補到_位置，然后再按條件把它逐層_調(diào)整。三、應(yīng)用題1. 已知一組元素為(46,25,78,62,12,37,70,29)，畫出按元素排列順序輸入生成的一棵二叉搜索樹。 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. 有七個帶權(quán)結(jié)點，

29、其權(quán)值分別為3,7,8,2,6,10,14，試以它們?yōu)槿~子結(jié)點構(gòu)造一棵哈夫曼樹，并計算出帶權(quán)路徑長度WPL。四、算法設(shè)計1編寫在以BST為樹根指針的二叉搜索樹上進行查找值為item的結(jié)點的非遞歸算法，若查找成功則由item帶回整個結(jié)點的值并返回true，否則返回false。 bool Find( BTreeNode * BST , ElemType & item )2下面的算法功能是向HBT堆中插入一個值為item的元素，使得插入后仍是一個堆。請在畫有橫線的地方填上合適的語句，完成其功能。void AH(Heap & HBT , const ElemType item) / 形

30、參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在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的_倍。 2在一個具有n個頂點的無向完全圖中，包含有_條邊，在一個具有n個頂點的有向完全圖中，包含有_條邊。 3. 在一個具有n個頂點的無向圖中，要連通所有頂點則至少需要_條邊。 4表示圖的三種存儲結(jié)構(gòu)為_、_和_。 5. 對于

31、一個具有n個頂點的圖，若采用鄰接矩陣表示，則矩陣大小為_。 6對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié)點分別為_和_條。 7. 在有向圖的鄰接表和逆鄰接表表示中，每個頂點鄰接表分別鏈接著該頂點的所有_和_結(jié)點。 8對于一個具有n個頂點和e條邊的有向圖和無向圖，若采用邊集數(shù)組表示，則存于數(shù)組中的邊數(shù)分別為_和_條。 9對于一個具有n個頂點和e條邊的無向圖，當(dāng)分別采用鄰接矩陣、鄰接表和邊集數(shù)組表示時，求任一頂點度數(shù)的時間復(fù)雜度依次為_、_和_。 10. 假定一個圖具有n個頂點和e條邊，則采用鄰接矩陣、鄰接表和邊集數(shù)組表示時，其相應(yīng)的空間復(fù)雜度分別為_、_和_。 1

32、1. 對用鄰接矩陣表示的圖進行任一種遍歷時，其時間復(fù)雜度為_，對用鄰接表表示的圖進行任一種遍歷時，其時間復(fù)雜度為_。12對于下面的無向圖G1，假定用鄰接矩陣表示，則從頂點v0開始進行深度優(yōu)先搜索遍歷得到的頂點序列為_，從頂點v0開始進行廣度優(yōu)先搜索遍歷得到的頂點序列為_。13. 對于下面的有向圖G2，假定用鄰接矩陣表示，則從頂點v0開始進行深度優(yōu)先搜索遍歷得到的頂點序列為_，從頂點v0開始進行廣度優(yōu)先搜索遍歷得到的頂點序列為_。 14. 對于下面的帶權(quán)圖G3，其最小生成樹的權(quán)為_。 15對于下面的帶權(quán)圖G3，若從頂點v0出發(fā)，則按照普里姆算法生成的最小生成樹中，依次得到的各條邊為_。 16.

33、對于下面的帶權(quán)圖G3，若按照克魯斯卡爾算法產(chǎn)生最小生成樹，則得到的各條邊依次為_。 17假定用一維數(shù)組dn存儲一個AOV網(wǎng)中用于拓?fù)渑判虻捻旤c入度，則值為0的元素被鏈接成為一個_。 18. 對于一個具有n個頂點和e條邊的連通圖，其生成樹中的頂點數(shù)和邊數(shù)分別為_和_。 二、應(yīng)用題 1. 對于下圖G4和G5，按下列條件試分別寫出從頂點v0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點序列和按廣度優(yōu)先搜索遍歷得到的頂點序列。 (1) 假定它們均采用鄰接矩陣表示; (2) 假定它們均采用鄰接表表示，并且假定每個頂點鄰接表中的結(jié)點是按頂點序號從大到小的次序鏈接的。 2. 對于下圖G6，試給出一種拓?fù)湫蛄?，若在它的鄰?/p>

34、表存儲結(jié)構(gòu)中，每個頂點鄰接表中的邊結(jié)點都是按照終點序號從大到小鏈接的，則按此給出唯一一種拓?fù)湫蛄小５谄卟糠?查找 一、填空題 1以順序查找方法從長度為n的線性表中查找一個元素時，平均查找長度為_，時間復(fù)雜度為_。 2以二分查找方法從長度為n的線性有序表中查找一個元素時，平均查找長度小于等于_，時間復(fù)雜度為_。 3以二分查找方法從長度為12的有序表中查找一個元素時，平均查找長度為_。 4以二分查找方法查找一個線性表時，此線性表必須是_存儲的_表。 5從有序表(12,18,30,43,56,78,82,95)中依次二分查找43和56元素時，其查找長度分別為_和_。 6對于二分查找所對應(yīng)的判定樹，它

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

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

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

38、列函數(shù)和鏈接法處理沖突，試求出每一元素的散列地址，畫出最后得到的散列表，求出平均查找長度。三、算法設(shè)計 設(shè)計在有序表An中按二分查找關(guān)鍵字為K的遞歸和非遞歸算法。第八部分 排序 一、填空題 1每次從無序表中取出一個元素，把它插入到有序表中的適當(dāng)位置，此種排序方法叫做_排序；每次從無序表中挑選出一個最小或最大元素，把它交換到有序表的一端，此種排序方法叫做_排序。 2每次直接或通過基準(zhǔn)元素間接比較兩個元素，若出現(xiàn)逆序排列時就交換它們的位置，此種排序方法叫做_排序；每次使兩個相鄰的有序表合并成一個有序表的排序方法叫做_排序。 3在直接選擇排序中，記錄比較次數(shù)的時間復(fù)雜度為_，記錄移動次數(shù)的時間復(fù)雜度

39、為_。 4. 在堆排序的過程中，對n個記錄建立初始堆需要進行_次篩運算，由初始堆到堆排序結(jié)束，需要對樹根結(jié)點進行_次篩運算。 5在堆排序的過程中，對任一分支結(jié)點進行篩運算的時間復(fù)雜度為_，整個堆排序過程的時間復(fù)雜度為_。 6假定一組記錄的排序碼為(46,79,56,38,40,84)，則利用堆排序方法建立的初始堆為_。 7. 快速排序在平均情況下的時間復(fù)雜度為_，在最壞情況下的時間復(fù)雜度為_。 8快速排序在平均情況下的空間復(fù)雜度為_，在最壞情況下的空間復(fù)雜度為_。 9在快速排序方法中，進行每次劃分時，是從當(dāng)前待排序區(qū)間的_向_依次查找出處于逆序的元素并交換之，最后將基準(zhǔn)元素交換到一個確定位置，

40、從而以該位置把當(dāng)前區(qū)間劃分為前后兩個子區(qū)間。 10. 假定一組記錄的排序碼為(46,79,56,38,40,80)，對其進行快速排序的一次劃分的結(jié)果為_。 11. 假定一組記錄的排序碼為(46,79,56,38,40,80)，對其進行快速排序的過程中，對應(yīng)二叉搜索樹的深度為_，分支結(jié)點數(shù)為_。 12在二路歸并排序中，對n個記錄進行歸并的趟數(shù)為_。 13. 在歸并排序中，進行每趟歸并的時間復(fù)雜度為_，整個排序過程的時間復(fù)雜度為_，空間復(fù)雜度為_。 14對20個記錄進行歸并排序時，共需要進行_趟歸并，在第三趟歸并時是把長度為_的有序表兩兩歸并為長度為_的有序表。 15假定一組記錄的排序碼為(46,

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

42、結(jié)果。 三、算法設(shè)計完成從一維數(shù)組An上進行快速排序的遞歸算法。void QuickSort( ElemType A , int s , int t ) int i = s, j = t+1; ElemType x = As; do do i+; while ( ) ; / 填寫一個循環(huán)條件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 ) ; 數(shù)據(jù)結(jié)構(gòu)練習(xí)題參考答案第一部分 緒 論一、單選題1. A 2. C