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

1、數(shù)據(jù)結(jié)構(gòu)練習(xí)題第一部分 緒 論 一、單選題 1. 一個(gè)數(shù)組元素ai與_的表示等價(jià)。 A、 *(a+i) B、 a+i C、 *a+i D、 &a+i 2. 對(duì)于兩個(gè)函數(shù)，若函數(shù)名相同，但只是_不同則不是重載函數(shù)。 A、 參數(shù)類型 B、 參數(shù)個(gè)數(shù) C、 函數(shù)類型 3. 若需要利用形參直接訪問實(shí)參，則應(yīng)把形參變量說明為_參數(shù) A、 指針 B、 引用 C、 值 4. 下面程序段的時(shí)間復(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í)行下面程序段時(shí)，執(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. 下面算法的時(shí)間復(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ù)的存儲(chǔ)結(jié)構(gòu)被分為_、_、_和_四種。 3. 在線性結(jié)構(gòu)、

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

4、a所占有的存儲(chǔ)空間的大小即數(shù)組長度為_，下標(biāo)為i的元素ai的存儲(chǔ)地址為_，或者為_。 11. 函數(shù)重載要求_、_或_有所不同。 12. 對(duì)于雙目操作符，其重載函數(shù)帶有_個(gè)參數(shù)，其中至少有一個(gè)為_的類型。 13. 若對(duì)象ra和rb中至少有一個(gè)是屬于用戶定義的類型，則執(zhí)行ra=rb時(shí)，需要調(diào)用_重載函數(shù)，該函數(shù)的第一個(gè)參數(shù)應(yīng)與_的類型相同，第二個(gè)參數(shù)應(yīng)與_的類型相同。 14. 從一維數(shù)組an中順序查找出一個(gè)最大值元素的時(shí)間復(fù)雜度為_，輸出一個(gè)二維數(shù)組bmn中所有元素值的時(shí)間復(fù)雜度為_。 15. 在下面程序段中，s=s+p語句的執(zhí)行次數(shù)為_，p*=j語句的執(zhí)行次數(shù)為_，該程序段的時(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. 一個(gè)算法的時(shí)間復(fù)雜度為(3n2+2nlog2n+4n-7)/(5n)，其數(shù)量級(jí)表示為_。第二部分 線性表 一、單選題 1在一個(gè)長度為n的順序存儲(chǔ)線性表中，向第i個(gè)元素(1in+1)之前插入一個(gè)新元素時(shí)，需要從后向前依次后移 個(gè)元素。 A、n-i B、n-i+1 C、n-i-1 D、i 2在一個(gè)長度為n的順序存儲(chǔ)線性表中，刪除第i個(gè)元素(1in+1)時(shí)，需要從前向后依次前移 個(gè)元素。 A、n-i B、n-i+1 C、n-i-1 D、i 3在一

6、個(gè)長度為n的線性表中順序查找值為x的元素時(shí)，查找時(shí)的平均查找長度（即x同元素的平均比較次數(shù)，假定查找每個(gè)元素的概率都相等）為 。 A、n B、n/2 C、(n+1)/2 D、(n-1)/2 4在一個(gè)單鏈表HL中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(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在一個(gè)單鏈表HL中，若要在指針q所指的結(jié)點(diǎn)的后面插入一個(gè)由指針p所指的結(jié)點(diǎn)，則執(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在一個(gè)單鏈表HL中，若要?jiǎng)h除由指針q所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(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在線性表的單鏈接存儲(chǔ)結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)包含有兩個(gè)域，一個(gè)叫 域，另一個(gè)叫 域。 2在下面數(shù)組a中鏈接存儲(chǔ)著一個(gè)線性表，表頭指針為a0.next，則該線性表為 。 3對(duì)于一個(gè)長度為n的順序存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為 ，在表尾插入元素的時(shí)間復(fù)雜度為 。 4對(duì)于一個(gè)長度為n的單鏈接存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為 ，在表尾插入元素的時(shí)間復(fù)雜度為 。5在線性表的順序存儲(chǔ)中，若一個(gè)元素的下標(biāo)為i，則它的前驅(qū)元素的下

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

10、的，試寫出每個(gè)程序段執(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對(duì)于List類型的線性表，編寫出下列每個(gè)算法。(1) 從線性表中刪除具有最小值的元素并由函數(shù)返回，空出的位置由最后一個(gè)元素填補(bǔ)，若線性表為空則顯示出錯(cuò)信息并退出運(yùn)行。 (2) 從線性表中刪除第i

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

13、一個(gè)元素時(shí)，首先應(yīng)執(zhí)行 語句修改top指針。 A、top+ B、top- C、top=0 D、top 3若讓元素1，2，3依次進(jìn)棧，則出棧次序不可能出現(xiàn) 種情況。 A、3，2，1 B、2，1，3 C、3，1，2 D、1，3，2 4在一個(gè)循環(huán)順序隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的 位置。 A、前一個(gè) B、后一個(gè) C、當(dāng)前 D、后面 5當(dāng)利用大小為N的一維數(shù)組順序存儲(chǔ)一個(gè)循環(huán)隊(duì)列時(shí)，該隊(duì)列的最大長度為 。 A、N-2 B、N-1 C、N D、N+1 6從一個(gè)循環(huán)順序隊(duì)列刪除元素時(shí)，首先需要 。 A、前移一位隊(duì)首指針 B、后移一位隊(duì)首指針 C、取出隊(duì)首指針?biāo)肝恢蒙系脑?D、取出隊(duì)尾指針?biāo)肝恢蒙系脑?/p>

14、素7假定一個(gè)循環(huán)順序隊(duì)列的隊(duì)首和隊(duì)尾指針分別為f和r，則判斷隊(duì)空的條件是 。 A、f+1=r B、r+1=f C、f=0 D、f=r 8假定一個(gè)鏈隊(duì)的隊(duì)首和隊(duì)尾指針分別為front和rear，則判斷隊(duì)空的條件是 。 A、front=rear B、front!=NULL C、rear!=NULL D、front=NULL二、填空題 1隊(duì)列的插入操作在 進(jìn)行，刪除操作在 進(jìn)行。 2棧又稱為 表，隊(duì)列又稱為 表。 3向一個(gè)順序棧插入一個(gè)元素時(shí)，首先使 后移一個(gè)位置，然后把待插入元素 到這個(gè)位置上。 4從一個(gè)棧中刪除元素時(shí)，首先取出 ，然后再前移一位 。 5在一個(gè)循環(huán)順序隊(duì)列Q中，判斷隊(duì)空的條件為 ，

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

16、應(yīng)執(zhí)行 和 操作。 13從一個(gè)棧頂指針為HS的非空鏈棧中刪除結(jié)點(diǎn)并不需要返回棧頂結(jié)點(diǎn)的值和回收結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行 操作。 14假定front和rear分別為一個(gè)鏈隊(duì)的隊(duì)首和隊(duì)尾指針，則該鏈隊(duì)中只有一個(gè)結(jié)點(diǎn)的條件為 。 15. 中綴算術(shù)表達(dá)式3+4/(25-(6+15)*8 所對(duì)應(yīng)的后綴算術(shù)表達(dá)式為 。 16. 后綴算術(shù)表達(dá)式24 8 + 3 * 4 10 7 - * / 所對(duì)應(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項(xiàng)和第2項(xiàng)均為1，以后各項(xiàng)為其前兩項(xiàng)之和。若裴波那契數(shù)列中的第n項(xiàng)用Fib(n)表示，則計(jì)算公式為： ì 1 (n=1或2) Fib(n)=í î Fib(n-1)+Fib(n-2) (n>=2

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

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

20、和_域。 11若把整個(gè)廣義表也看為一個(gè)表結(jié)點(diǎn)，則該結(jié)點(diǎn)的tag域的值為_，next域的值為_。 三、應(yīng)用題 1. 已知一個(gè)稀疏矩陣如下圖所示： 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列的一個(gè)稀疏矩陣(1) 寫出它的三元組線性表； (2) 給出它的順序存儲(chǔ)表示； (3) 給出它的轉(zhuǎn)置矩陣的三元組線性表和順序存儲(chǔ)表示； 2. 畫出下列每個(gè)廣義表的帶表頭附加結(jié)點(diǎn)的鏈接存儲(chǔ)結(jié)構(gòu)圖并分別計(jì)算出它們的長度和深度。 (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對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹，該樹中所有結(jié)點(diǎn)的度數(shù)之和為_。 2. 假定一棵三叉樹的結(jié)點(diǎn)個(gè)數(shù)為50，則它的最小深度為_，最大深度為_。 3在一棵三叉樹中，度為3的結(jié)點(diǎn)數(shù)有2個(gè)，度為2的結(jié)點(diǎn)數(shù)有1個(gè)，度為1的結(jié)點(diǎn)數(shù)為2個(gè)，那么度為0的結(jié)點(diǎn)數(shù)有_個(gè)。 4一棵深度為5的滿二叉樹中的結(jié)點(diǎn)數(shù)為_個(gè)，一棵深度為3的滿三叉樹中的結(jié)點(diǎn)數(shù)為_個(gè)。 5假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)，則樹中所

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

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

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

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

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

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

28、點(diǎn)的值是所有結(jié)點(diǎn)中的_，在一個(gè)大根堆中，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的_。 6當(dāng)從一個(gè)小根堆中刪除一個(gè)元素時(shí)，需要把_元素填補(bǔ)到_位置，然后再按條件把它逐層_調(diào)整。三、應(yīng)用題1. 已知一組元素為(46,25,78,62,12,37,70,29)，畫出按元素排列順序輸入生成的一棵二叉搜索樹。 2. 空堆開始依次向堆中插入線性表（38,64,52,15,73,40,48,55,26,12）中的每個(gè)元素，請(qǐng)以線性表的形式給出每插入一個(gè)元素后堆的狀態(tài)。 3. 已知一個(gè)堆為（12,15,40,38,26,52,48,64），若需要從堆中依次刪除四個(gè)元素，請(qǐng)給出每刪除一個(gè)元素后堆的狀態(tài)。4. 有七個(gè)帶權(quán)結(jié)點(diǎn)，

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

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

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

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

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

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

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

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

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

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

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

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

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

42、結(jié)果。 三、算法設(shè)計(jì)完成從一維數(shù)組An上進(jìn)行快速排序的遞歸算法。void QuickSort( ElemType A , int s , int t ) int i = s, j = t+1; ElemType x = As; do do i+; while ( ) ; / 填寫一個(gè)循環(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