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

1、習(xí)題B一、填空題1. 在二叉樹的二叉鏈表表示中，指針p所指結(jié)點為葉子結(jié)點的條件2. 在有序表A1.12中，采用二分查找算法查等于A12的元素，所比較的元素下標(biāo)依次為。3. 個棧的輸入序列為1,2,3,n，若輸出序列的第一個元素是n,輸出第i (1<=i<=n )個元素是。4. n個頂點的連通圖的生成樹含有 條邊。5. 有100個結(jié)點的完全二叉樹的葉子個數(shù)為 。6. 一個帶頭結(jié)點的單鏈表L的結(jié)點結(jié)構(gòu)為(data , next)，該單鏈表為空的判斷條件7順序查找n個元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為 次。8. 數(shù)據(jù)元素在計算機(jī)中有兩種基本存儲結(jié)構(gòu)，分別是存儲結(jié)構(gòu)和存儲結(jié)

2、構(gòu)。9假定一棵樹的廣義表表示為A ( C, D (E, F, G), H ( I, J),則樹中所含的結(jié)點數(shù)為個，樹的深度為 ，樹的度為。10.冒泡排序在最好的情況下的元素交換次數(shù)為 次。11.6個頂點的連通圖至少有 條邊。12. 設(shè)哈夫曼樹中共有 n個結(jié)點，則該哈夫曼樹中共有 個度數(shù)為1的結(jié)點。1、單選題1. 對一個算法的評價，不包括如下_B方面的內(nèi)容。A. 健壯性和可讀性B. 并行性 C. 正確性 D. 時空復(fù)雜度2. 一組記錄的關(guān)鍵字為(46, 79, 56 , 38, 40, 84),則利用快速排序的方法，以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果為C。A.(38,40,46,56,79,8

3、4)B.(40,38,46,79,56,84)C.(40,38,46,56,79,84)D.(40,38,46,84,56,79)3. 輸入序列為ABC輸出序列為ACB時，經(jīng)過的棧操作為D。A.push,push,push,pop,pop,popB.push,pop,push,pop,push,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop4. 設(shè)有兩個串p和q,其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為C 。A.求子串 B .聯(lián)接 C .匹配 D .求串長5. 若使用某個數(shù)組 Q1.1OO存儲一棵完全二叉樹，則

4、Q13的左右孩子的下標(biāo)分別是 (A)。A. 26 和 27 B.25 和 26 C.25 和 28 D.26 和 286. 廣義表(a,b,c,d)的表尾是_C。A. aB. (a,b,c,d) C. ( )D. (b,c,d)7. 下述幾種排序方法中，_B是不穩(wěn)定的排序方法。A.歸并排序 B快速排序C冒泡排序D直接插入排序8. 設(shè)有一個10階的對稱矩陣 A,采用僅存儲下三角的壓縮存儲方式，以行序為主存儲，a00為第一元素，其存儲地址為1，每個元素占一個地址空間，則a74的地址為（B ）。A. 13B. 33C. 18D. 409. 采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長

5、度是C 。A.nB. n/2C. （n+1）/2D. （n-1）/210. 執(zhí)行一趟快速排序能夠得到的序列是C 。A. 63, 12, 34, 45, 27 55 41 , 72B. 45 , 34, 12, 41 55 72 , 63, 27C. 41 , 12, 34, 45, 27 55 72 , 63D. 12 , 27, 45, 41 55 34 , 63, 7211. 設(shè)某無向圖有n個頂點，則該無向圖的鄰接表中有D個表頭結(jié)點。A.2 nB. n（n-1）C. n/2D. n12. 設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ棧瑒t刪除棧項元素的操作為D 。A. top=top+1;B. to

6、p=top+1 ;C. top->n ext=top;D. top=top->n ext;13. 具有10個葉結(jié)點的二叉樹中有B 個度為2的結(jié)點，A.8B.9C.10D.ll14. 某棧的輸入序列為 a, b,c,d,下面的四個序列中，不可能是它的輸出序列的是D 。A. a, c, b, dB. b, c , d, a C. c, d , b, aD. d, c , a , b15. 數(shù)組A05,06的每個元素占5個字節(jié)，將其按列優(yōu)先次序存儲在起始地址為1000的內(nèi)存單元中，則元素 A5,5的地址是B 。A. 1180B. 1175C. 1205D. 1210三、判斷題1. 無向圖

7、中所有頂點的度數(shù)之和等于所有邊數(shù)的2倍。（t ）2. 折半查找中要求表必須有序，表可以順序方式存儲，也可以鏈表方式存儲。（f ）3. 在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存取的存儲結(jié)構(gòu)。（f ）4. 通過拓?fù)渑判蚩梢耘袛嘤邢驁D中是否有環(huán)的存在。（t）5. 二叉樹是指度為2的有序樹。（f）6. 線性表的順序存儲結(jié)構(gòu)比鏈?zhǔn)酱鎯Y(jié)構(gòu)更好。（f）7. 由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。（f）8順序表查找指的是在順序存儲結(jié)構(gòu)上進(jìn)行查找。（f ）9. 當(dāng)向二叉排序樹中插入一個結(jié)點，則該結(jié)點一定成為葉子結(jié)點。（t ）10. 非空的雙向循環(huán)鏈表中任何結(jié)點的前驅(qū)指

8、針均不為空。（t）四、應(yīng)用題1. 已知無向網(wǎng)G,如右圖所示，完成如下要求：（1）寫出無向網(wǎng)G的鄰接矩陣；（2）畫出無向網(wǎng)G的最小生成樹。2. 請根據(jù)給出的關(guān)鍵字序列：43, 12, 72，8，16，50, 80，完成如下要求：（1）畫出相應(yīng)的二叉排序樹；（2）若要查找50需和哪些關(guān)鍵字進(jìn)行比較。3.Seve n with weight no de, weights are 4,7,5,2,8,9,14, try to structure a tree leaf no des Hoffma n tree, try draw ing out gen erated Hoffma n tree, an

9、d calculated withweight WPL path len gth. （ 10 poi nts ）4.某無向圖的頂點表為（1,2,3,4），下圖為其鄰接矩陣表，請畫出該無向圖。0 1 1 0_10 1111 C 00 10 05 在如下數(shù)組 A中鏈接存儲了一個線性表， A0為頭結(jié)點，試寫出該線性表。A 0123 4567data605078903440n ext3572041，哈希函數(shù)為：H（key）=key MOD6.已知一組關(guān)鍵字 （19,14,23,1,68,20,84,27,55,11,10,79）13, 用鏈地址法處理沖突，要求：（1） 試構(gòu)造這組關(guān)鍵字的散列表；（8分

10、）答案在課件上。（2） 試求出查找成功的平均查找長度。（2分）五、算法分析與設(shè)計題1. 已知循環(huán)隊列Q的結(jié)構(gòu)如下所示：struct QueueElemType baseMAXSIZE; /ElemType為元素類型int front,rear;/front為隊頭指針，rear為隊尾指針試寫出以下內(nèi)容：共4頁第5頁(1) 判空條件；(2分)(2) 判滿條件；(2分)(3) 入隊時的指針變化情況；(2分)(4) 出隊時的指針變化情況；(2分)(5) 隊長。(2分)2. 已知待排序的關(guān)鍵字序列為12，2，16，30，28，10，16*，20，6，18，完成如下要求：(1) 寫出折半插入排序算法；(2

11、) 寫出使用折半插入排序方法每趟排序結(jié)束后關(guān)鍵字序列的狀態(tài)；3. Please write dow n the code of the pivot positi on of the sub table rlow.highin quick sort.4. 假定電文字符集為A,B,C,D,E,F,G ,H,它們在電文中出現(xiàn)的次數(shù)分別為 19,6,12,5,38,3,13,4 )，為這8個字符設(shè)計哈夫曼編碼。 畫出哈夫曼樹并給出編碼。 要求在構(gòu) 造哈夫曼樹的過程中，權(quán)值較小結(jié)點放在左側(cè)，編碼時左分支生成代碼 0,右分支生成代碼1。4.共6頁第9頁習(xí)題B答案、填空題1. p->lchild=NU

12、LL&&p->rchild=NULL(或者!p->lchild&&!p->rchild，或者 p 指針?biāo)附Y(jié)點的左右孩子指針均為空)2.6,9,11,123. n-i+14. n-15. 506. L->next=NULL(或者!L->next) 7. n_ & 順序 鏈?zhǔn)?不論先后順序) 9.9_ 3 310. 011. 512. 0二、單選題1-5 BCDCA 6-10CBBCC 11-15 DDBDB三、判斷題四、應(yīng)用題1.（ 1）（2）QQ615gW531)1(46OOCOOOJ15CO564585882836886

13、88426OD2.（ 1）(4?)（2）/A43,72，501(50)3（ 1）（2）WPL=9*2+5*3+2*4+4*4+14*2+7*3+8*3兒=130（)© ®5. 線性表(78, 50, 40, 60, 34, 90)6.(2) ASL=(1*6+2*4+3+4)/12=1.75五、算法分析與設(shè)計題1. (1) Q.front=Q.rear(2) (Q.rear+1)%MAXSIZE=Q.front(3) Q.rear=(Q.rea葉1)%MAXSIZE(4) Q.front=(Q.front+1)%MAXSIZE(5) (Q.rear-Q.front+MAXSIZE)%MAXSIZE2. (1)答案在書上。(2)初始序列：12221630281016*20618第1趟排序結(jié)果12221630281016*20618第2趟排序結(jié)果12162230281016*20618第3趟排序結(jié)果12162230281016*20618第4趟排序結(jié)果12162228301016*20618第5