數(shù)據(jù)結(jié)構(gòu)C語言版章節(jié)練習試題(1-6章)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)章節(jié)練習題第一章 緒 論一、單選題1.一個數(shù)組元素ai與_的表示等價。 A、 *(a+i) B、 a+i C、 *a+i D、 &a+i 2.下面程序段的時間復(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)3.執(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(

2、n+1) D、 n(n+1)/24.下面算法的時間復(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)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)中，前驅(qū)和后繼結(jié)點之間分別存在著_、_和_的聯(lián)系。4.一種抽象數(shù)據(jù)類型包括_和_兩個部分。5.當一個形參類型的長度較大時，應(yīng)最好說明為_，以節(jié)省參數(shù)值的傳輸時間和存儲參數(shù)的空間。6.當需要用一個形參

3、訪問對應(yīng)的實參時，則該形參應(yīng)說明為_。7.在函數(shù)中對引用形參的修改就是對相應(yīng)_的修改，對_形參的修改只局限在該函數(shù)的內(nèi)部，不會反映到對應(yīng)的實參上。8.當需要進行標準I/O操作時，則應(yīng)在程序文件中包含_頭文件，當需要進行文件I/O操作時，則應(yīng)在程序文件中包含_頭文件。9.在包含有_頭文件的程序文件中，使用_能夠產(chǎn)生出020之間的一個隨機整數(shù)。10.一個數(shù)組a所占有的存儲空間的大小即數(shù)組長度為_，下標為i的元素ai的存儲地址為_，或者為_。14.從一維數(shù)組an中順序查找出一個最大值元素的時間復(fù)雜度為_，輸出一個二維數(shù)組bmn中所有元素值的時間復(fù)雜度為_。15.在下面程序段中，s=s+p語句的執(zhí)行次

4、數(shù)為_，p*=j語句的執(zhí)行次數(shù)為_，該程序段的時間復(fù)雜度為_。 int 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、i2在一個長度為n的順序存儲線性表中，刪除第i個元素(1in+1)時，需要從前向后依次前移 元素。 A、n

5、-i B、n-i+1 C、n-i-1 D、i3在一個長度為n的線性表中順序查找值為x的元素時，查找時的平均查找長度（即x同元素的平均比較次數(shù)，假定查找每個元素的概率都相等）為 。 A、n B、n/2 C、(n+1)/2 D、(n-1)/24在一個單鏈表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所指的

6、結(jié)點的后面插入一個由指針p所指的結(jié)點，則執(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中，若要刪除由指針q所指向結(jié)點的后繼結(jié)點，則執(zhí)行 。 A、p = q->next ; p->next = q->next; B、p = q->next ; q->next =

7、 p; C、p = q->next ; 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在線性表的順序存儲中，若一

8、個元素的下標為i，則它的前驅(qū)元素的下標為_，后繼元素的下標為_。6在線性表的單鏈式存儲中，若一個元素所在結(jié)點的地址為p，則其后繼結(jié)點的地址為_，若假定p為一個數(shù)組a中的下標，則其后繼結(jié)點的下標為_。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，并假定每

9、個程序段是連續(xù)執(zhí)行的，試寫出每個程序段執(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

10、,a5/2); TraverseList(La);3對于List類型的線性表，編寫出下列每個算法。(1)從線性表中刪除具有最小值的元素并由函數(shù)返回，空出的位置由最后一個元素填補，若線性表為空則顯示出錯信息并退出運行。(2)從線性表中刪除第i個元素并由函數(shù)返回。(3)向線性表中第i個元素位置插入一個元素。(4)從線性表中刪除具有給定值x的所有元素。4對于結(jié)點類型為LNode的單鏈表，編寫出下列每個算法。(1)刪除單鏈表中的第i個結(jié)點。(2)在有序單鏈表中插入一個元素x的結(jié)點。 (3)從單鏈表中查找出所有元素的最大值，該值由函數(shù)返回，若單鏈表為空，則顯示出錯信息并停止運行。(4)統(tǒng)計出單鏈表中結(jié)點

11、的值等于給定值x的結(jié)點數(shù)。第三章 棧和隊列一、單選題1棧的插入與刪除操作在 進行。 A、棧頂 B、棧底 C、任意位置 D、指定位置2當利用大小為N的一維數(shù)組順序存儲一個棧時，假定用top=0表示?？眨瑒t向這個棧插入一個元素時，需要執(zhí)行 語句修改top指針。 A、top+ B、top- C、top=0 D、top3若讓元素1，2，3依次進棧，則出棧次序不可能出現(xiàn) 種情況。 A、3，2，1 B、2，1，3 C、3，1，2 D、1，3，24在一個循環(huán)順序隊列中，隊首指針指向隊首元素的 位置。 A、前一個 B、后一個 C、當前 D、后面5當利用大小為N的一維數(shù)組順序存儲一個循環(huán)隊列時，該隊列的最大長度

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

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

14、_。11當用長度為N的一維數(shù)組順序存儲一個棧時，假定用top=0表示?？?，則表示棧滿的條件為_。12向一個棧頂指針為HS的鏈棧中插入一個新結(jié)點*P果，應(yīng)執(zhí)行_和_操作。13從一個棧頂指針為HS的非空鏈棧中刪除結(jié)點并不需要返回棧頂結(jié)點的值和回收結(jié)點時，應(yīng)執(zhí)行_操作。14假定front和rear分別為一個鏈隊的隊首和隊尾指針，則該鏈隊中只有一個結(jié)點的條件為_。三、應(yīng)用題執(zhí)行下面函數(shù)調(diào)用后得到的輸出結(jié)果是什么？void AF(Queue & Q) InitQueue(Q); int a4 = 5,8,12,15 ; for ( int i=0; i<4; i+ ) QInsert(Q,

15、ai); QInsert(Q,QDelete(Q); QInsert(Q,30); QInsert(Q,QDelete(Q)+10); while (!QueueEmpty(Q) printf ( “%d ”,QDelete(Q); 第四章 稀疏矩陣和廣義表一、單選題1.在稀疏矩陣的帶行指針向量的鏈接存儲中，每個行單鏈表中的結(jié)點都具有相同的_。 A、 行號 B、 列號 C、 元素值 D、 地址二、填空題1.在一個稀疏矩陣中，每個非零元素所對應(yīng)的三元組包括該元素的_、_和_三項。2.在稀疏矩陣所對應(yīng)的三元組線性表中，每個三元組元素按_為主序、_為輔序的次序排列。3.在初始化一個稀疏矩陣的函數(shù)定義

16、中，矩陣形參應(yīng)說明為_參數(shù)。4.在稀疏矩陣的順序存儲中，利用一個數(shù)組來存儲非零元素，該數(shù)組的長度應(yīng)_對應(yīng)三元組線性表的長度。第五章 樹和二叉樹（一）一、填空題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)，則樹中所含的結(jié)點數(shù)為_個，樹的深度為_，樹的度為_。6

17、假定一棵樹的廣義表表示為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，則它的最小深度為_，最大深度為_。12一棵二叉樹的廣義表表示為a(b(c,d),e(f(,g)，則e

18、結(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若對一棵二叉樹從0開始進行結(jié)點編號，并按此編號把它順序存儲到一維數(shù)組a中，即編號為0

19、的結(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),c(f(h,i,j),g),d)，則先根遍歷結(jié)果為_，按層遍歷結(jié)果為_。二、應(yīng)用題1已知一棵具有n個

20、結(jié)點的完全二叉樹被順序存儲于一維數(shù)組的A1An元素中，試編寫一個算法打印出編號為i的結(jié)點的雙親和所有孩子。2編寫一算法，求出一棵二叉樹中所有結(jié)點數(shù)和葉子結(jié)點數(shù)，假定分別用變參C1和C2統(tǒng)計所有結(jié)點數(shù)和葉子結(jié)點數(shù)，初值均為0。第六章 二叉樹的應(yīng)用（二）一、單選題1. 從二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為_。A、 O(n) B、 O(1) 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、

21、 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. 由權(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對一棵二

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

23、叉搜索樹。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é)點，其權(quán)值分別為3,7,8,2,6,10,14，試以它們?yōu)槿~子結(jié)點構(gòu)造一棵哈夫曼樹，并計算出帶權(quán)路徑長度WPL。數(shù)據(jù)結(jié)構(gòu)期末復(fù)習練習題答案（僅供參考）第一章 緒 論一、單選題1. A 2. C 3. B 4. C 5. D 6. B 二、填空題1. 集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖形

24、結(jié)構(gòu) 2.順序、鏈式 3. 1:1、1:N、M:N 4.數(shù)據(jù)定義、操作聲明 5.引用形參(或指針形參 ) 6.引用類型 ( 或 指針類型 ) 7.實參、值 8.stdio.h、file.h 9.stdlib.h、rand( ) %21 10. sizeof(a)、a+i*sizeof(a0)、a+i11. 參數(shù)類型、數(shù)量、次序 12. 2、用戶自定義 13. = = 、ra 、rb 14. O(n)、O(m*n)15. n、n(n+1)/2、O(n2) 16. O(n)第二章 線性表 一、單選題1. B 2. A 3. C 4. B 5. D 6. C二、填空題1.元素值、指針 2.( 38,

25、56,25,60,42,74) 3. O(n)、O(1) 4.(1)、O(n) 5.i-1、i+1p->next 、ap.next 7.表頭 8.前驅(qū)、后繼 9.表尾、表頭 10HL->next = = NULL 、HL->next = = HL三、應(yīng)用題1.(1) ( 79 , 62 , 34 , 57 , 26 , 48 ) (2) ( 26 , 34 , 48 , 57 , 62 , 79 ) (3) ( 26, 34 , 39 , 48 , 57 , 62 )212，26，9，8，15，30，50）3(1) ElemType DMValue( List & L

26、 ) if ( ListEmpty(L) ) / 空線性表 cerr <<"List is Empty!"<<endl; exit(1);ElemType x; / x存放最小元素x = L.list0;int k = 0; / k存放最小元素的下標for ( int i = 1; i<L.size; i+ ) / 查找最小元素 if ( L.listi < x ) x = L.listi ; k = i; L.listk = L.listL.size-1; / 最后一個元素填補最小元素位置L.size-; / 線性表長度減1return

27、 x; / 返回最小元素 2)ElemType Delete( List & L, int i ) if ( i<1 | i>L.size ) / 判斷i的合法性printf("Index is out range!n”);exit(1); ElemType x = L.listi-1; / 保存被刪除元素 for ( int j = i-1; j<L.size-1; j+ ) / 元素向前移動 L.listj = L.listj+1; L.size-; / 長度減1 return x; / 返回被刪元素 (3)void Insert( List &

28、 L, int i, ElemType x ) if ( i<1 | i>L.size+1 ) / 判斷i的合法性printf("Index is out range!n");exit(1); if ( L.size = MaxSize ) / 判斷線性表滿 printf("List overflow!n");exit(1); for ( int j = L.size-1 ; j>=i-1 ; j- ) / 元素后移，產(chǎn)生插入位置L.listj+1 = L.listj; L.listi-1 = x; / 元素插入 L.size+; /

29、長度加1 (4) void Delete( List & L, ElemType x ) int i = 0; while ( i<L.size ) if ( L.listi = x ) / 刪除x元素for ( int j = i+1; j<L.size; j+ ) L.listj-1 = L.listj;L.size-; else i+; / 尋找下一個x元素的位置 4(1)void Delete( LNode * & HL, int i ) if ( i<1 | HL=NULL ) / 判斷i的合法性或空鏈表cerr <<"inde

30、x is out range!"<<endl;exit(1); LNode * ap , * cp; ap = NULL ; cp = HL ; / cp指向當前結(jié)點，ap指向其前驅(qū)結(jié)點 int j = 1; while ( cp != NULL ) / 查找第i個結(jié)點 if ( j = i ) / 找到第i個結(jié)點break; / cp指向的結(jié)點即為第i個結(jié)點 else / 繼續(xù)向后尋找ap = cp;cp = cp->next;j+; if ( cp = NULL ) / 沒有找到第i個結(jié)點cerr <<"Index is out range

31、!"<<endl;exit(1); if ( ap = NULL ) / 刪除第1個結(jié)點（即i=1） HL = HL->nextl else ap->next = cp->next; / 刪除第i個結(jié)點 delete cp; / 釋放被刪除結(jié)點的空間 (2)void Insert( LNode * & HL, const ElemType & x ) LNode * newptr = new LNode; / 申請一個新結(jié)點 if ( newptr = NULL ) / 分配失敗cerr <<"Memory allo

32、cation failare!"<<endl;exit(1); newptr->data = x; if ( HL = NULL | x<HL->data ) / 空表 或 x小于表頭結(jié)點，newptr->next = HL; / 作為新表頭結(jié)點插入HL = newptr;return; / 查找插入位置 LNode * cp = HL->next; / 用cp指向當前結(jié)點（即待查結(jié)點） LNode * ap = HL; / 用ap作為指向當前結(jié)點的前驅(qū)結(jié)點指針 while ( cp != NULL ) if ( x<cp->da

33、ta) break; / 找到插入位置 else ap = cp; cp = cp->next; / 繼續(xù)查找插入位置 newptr->next = cp; ap->next = newptr; / 插入新結(jié)點 (3)ElemType MaxValue( LNode * HL ) if ( HL = NULL ) / 空表 cerr <<"Linked list is empty!"<<endl; exit(1);ElemType max = HL->data;LNode * p = HL->next;while ( p

34、 != NULL ) / 尋找最大值 if ( max < p->data ) max = p->data; p = p->next;return max; (4)int Count( LNode * HL , ElemType x ) int n = 0; LNode * p = HL; while ( p != NULL ) if ( p->data = x ) n+; p = p->next; return n; 第三章 稀疏矩陣和廣義表 一、單選題1. A 2. B二、填空題1.行號、列號、元素值 2.行號、列號 3.引用 (或指針) 4.等于 5.

35、4 、5 6.列號、行號 7. 單、表 8. 括號 9. 3 10. 元素值、子表指針 11. true、NULL三、應(yīng)用題1(1) ( (1,2,4),(2,4,-3),(2,7,1),(3,1,8),(4,4,5),(5,2,-7),(5,6,2),(6,4,6) )12234556247142644-3185-726 (2) (3) (1,3,8),(2,1,4),(2,5,-7),(4,2,-3),(4,4,5), (4,6,6),(6,5, 2),(7,2,1)122444673152465284-7-356212(1) A：長度：1 深度：2 (2) B：長度：3 深度：1 (3)

36、 C：長度：2 深度：3 (4) D：長度：2 深度：2 (5) E：長度：3 深度：3 (6) F：長度：1 深度：4第四章 棧和隊列 一、單選題1. A 2. B 3. C 4. A 5. B 6. B 7. D 8. D二、填空題1.隊尾、隊首 2.后進先出(LIFO)、先進先出(FIFO) 3.棧頂指針、存儲 4.棧頂元素、棧頂指針5. front = = rear 、(rear+1)%QueueMaxSize = = front 6. -1 、StackMaxSize-17. 棧空、空隊、隊列只有一個元素 8.新結(jié)點的指針域、棧頂指針 9.指針域、棧頂指針 10.隊尾指針、存儲 11

37、.top = = 0 12.p->next = HS 、HS = p 13. HS = HS->next14. ( front = = rear ) && ( front <>NULL ) 15. 3 4 25 6 15 + - / 8 * +16. (24+8)*3/(4*(10-7) 、8三、應(yīng)用題 12 15 5 30 18四、編程題遞歸算法：long Fib( int n ) if ( n=1 | n=2 ) / 終止遞歸條件 return 1;else return Fib(n-1)+Fib(n-2);非遞歸算法：long Fib( int n

38、 ) int a , b , c; / c代表當前項，a和b分別代表當前項前面的第2項和第1項a = b = 1;if ( n = 1 | n = 2 ) return 1;else for ( int i = 3 ; i<=n ; i+ ) c = a+b; / 求當前項 a = b; / 產(chǎn)生第2項 b = c; / 產(chǎn)生第1項 return c; / 返回所求的第n項 遞歸算法的時間復(fù)雜度為 O(2n)，空間復(fù)雜度為 O(n)；非遞歸算法的時間復(fù)雜度為 O(n)，空間復(fù)雜度為 O(1)。第五章 樹和二叉樹一、填空題1.n-1 2.5 、50 3. 6 4.31、21 5.10、4、

39、3 6.2、1、1、6 7.B、I和J 8.6 9. 2i、2i+1、? i/2? 10.16 11.5、18 12.a、f、空結(jié)點(即無右孩子結(jié)點) 13. 4、2、314. a2*i、a2*i+1、ai/2 15. 2i-1、2j+1 16. A2*i+1、a2*i+2、ai/2 17.2n、n-1、n+1 18.10、5 19. abcdef、cbaedf、cbefda、abdcef 20. abecfhijgd、abcdefghij二、應(yīng)用題1void Request( int A , int n , int i ) if ( i>n ) cerr <<"編

40、號為"<<i<<"的結(jié)點不存在！"<<endl; exit(1);cout <<"當前結(jié)點為"<<Ai<<endl;int j = i/2; / 下標為j的結(jié)點是下標為i結(jié)點的雙親if ( j>0 ) cout <<"雙親："<<Aj<<endl;else cout <<"樹根沒有雙親結(jié)點！"<<endl;if ( 2*i < n ) cout <<"左孩子："<<A2*i<<