數(shù)據(jù)結(jié)構(gòu)課后習(xí)題參考答案資料

1、.選擇題：CCBDCA.試分析下面各程序段的時(shí)間復(fù)雜度。O (1)O (m*n)O (n2)O (log 3n)(5)因?yàn)閤+共執(zhí)行了 n-1+n-2+1= n(n-1)/2 ,所以執(zhí)行時(shí)間為 O ( n2)(6) O( . n )第2章線性表.選擇題babadbcabdcddac.算法設(shè)計(jì)題(6)設(shè)計(jì)一個(gè)算法，通過一趟遍歷在單鏈表中確定值最大的結(jié)點(diǎn)。ElemType Max (LinkList L )if(L-next=NULL) return NULL;pmax=L-next;法設(shè)計(jì)題(2)回文是指正讀反讀均相同的字符序列，如“abba”和“ abdba”均是回文，但“ good”不是回文

2、。試寫一個(gè)算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)?根據(jù)提示，算法可設(shè)計(jì)為：合應(yīng)用題(1)已知模式串t= abcaabbabcab 寫出用KM附求得的每個(gè)字符對(duì)應(yīng)的next和nextval函數(shù)值。存放該數(shù)組所需多少單元？存放數(shù)組第4列所有元素至少需多少單元？數(shù)組按行存放時(shí)，元素 A7,4的起始地址是多少？數(shù)組按列存放時(shí)，元素 A4,7的起始地址是多少？每個(gè)元素32個(gè)二進(jìn)制位，主存字長(zhǎng)16位，故每個(gè)元素占2個(gè)字長(zhǎng)，行下標(biāo)可平移至 1到11。(1) 242(2) 22(3) s+182(4) s+142(4)請(qǐng)將香蕉banana用工具H( ) Head( ) , T( ) Tai

3、l() 從L中取出。L=(apple,(orange,(strawberry,(banana),peach),pear)H (H (T (H (T (H (T (L)(5)寫一個(gè)算法統(tǒng)計(jì)在輸入字符串中各個(gè)不同字符出現(xiàn)的頻度并將結(jié)果存入文件(字符串中的合法字符為 A-Z這26個(gè)字母和0-9這10個(gè)數(shù)字)。void Count ()/統(tǒng)計(jì)輸入字符串中數(shù)字字符和字母字符的個(gè)數(shù)。int i , num36char ch ;/初始化表示輸入字符串結(jié)束。 /算法結(jié)束。if (0 =ch= 9) i=ch 48;numi+else ifforfor；(，A，=ch=，Z，) i=ch-65+10;numi+

4、printf/ 數(shù)字字符; /字母字符(i=0； i10 ； i+) / 輸出數(shù)字字符的個(gè)數(shù)printf (數(shù)字% d 的個(gè)數(shù)=% dn”, i , numi);(i =10; i36 ; i+ ) /求出字母字符的個(gè)數(shù)(“字母字符% c 的個(gè)數(shù)=% dn，i +55, numi);第5章樹和二叉樹.選擇題ADDCA CCBDC CCACC.應(yīng)用題(2)設(shè)一棵二叉樹的先序序列：A B D F C E G H ,中序序列：B F D A G E H C畫出這棵二叉樹。畫出這棵二叉樹的后序線索樹。將這棵二叉樹轉(zhuǎn)換成對(duì)應(yīng)的樹(或森林)O(2)試設(shè)計(jì)另一種由二進(jìn)制表示的編碼萬(wàn)暮(3)假設(shè)用于通信白電文

5、僅由 8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為, 試為這8個(gè)字母設(shè)計(jì)赫夫曼對(duì)于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)解：方案1;哈夫曼編碼先將概率放大100倍，以方便構(gòu)造哈夫曼樹。w=7,19,2,6,32,3,21,10,按哈夫曼規(guī)則：(2,3), 6, (7,10)1 ,19, 21,32197(40)2111字母 編P對(duì)應(yīng) 編碼出現(xiàn)頻率1110042001、1 一端餡三三作為-11a標(biāo)存儲(chǔ)4土杓鋁41110510萬(wàn)案萬(wàn)案J wpl夕+4+5+=+= 2的物Pl編碼3+=3123出現(xiàn)頻率吉論：哈夫.3.算一設(shè)I*題寫以下算法 3(1)統(tǒng)int Lea001010計(jì)二叉杈他葉結(jié)點(diǎn)個(gè)011fNode

6、CoUnt(BiTree T)00-6 if(T=NULL)101for (i =0; ilchild=NULL&T-rchild=NULL) return 1; /判斷該結(jié)點(diǎn)是否是葉子結(jié)點(diǎn)(左孩子右孩子都為空)，若是則返回1elsereturn LeafNodeCount(T-lchild)+LeafNodeCount(T-rchild);(3)交換二叉樹每個(gè)結(jié)點(diǎn)的左孩子和右孩子。void ChangeLR(BiTree &T) BiTree temp;if(T-lchild=NULL&T-rchild=NULL) return;elsetemp = T-lchild;T-lchild =

7、T-rchild;T-rchild = temp;ChangeLR(T-lchild);ChangeLR(T-rchild);1.選擇題CBBBCBABAADCCDDB2.應(yīng)用題(1)已知如圖所示的有向圖，請(qǐng)給出: 每個(gè)頂點(diǎn)的入度和出度；鄰接矩陣；鄰接表；逆鄰接表。(2)已知如圖所示的無(wú)向網(wǎng)，請(qǐng)給出：鄰接矩陣；鄰接表；ab4c3ba4c5d5ca3b5d5db5c5e7eb9d7f3Afd6e3g2Agd5f2h6Ahc5d4g6Ae9h5f6圖無(wú)向網(wǎng)4A最小生成樹D、弋 點(diǎn)i=1i=2i=3i=4i=5i=6b15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)15(a,b

8、)c2(a,c)d12(a,d)12(a,d)11(a,c,f,d)11(a,c,f,d)eoo10(a,c,e)10(a,c,e)foo6(a,c,f)gooOO16(a,c,f,g)16(a,c,f,g)衛(wèi)(acf.d.g)S終 點(diǎn)集a,ca,c,fa,c,f,ea,c,f,e,da,c,f,e,d,ga,c,f,e,d,g,b(3)已知圖的鄰接矩陣如所示。試分別畫出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。(4)有向網(wǎng)如圖所示，試用迪杰深度優(yōu)先生成樹廣度優(yōu)先生成樹斯特拉算法求出從頂 點(diǎn)a到其他各頂點(diǎn)間 的最短路徑，完成表。第7章查找.選擇題CDCABCCCDCBCADA.

9、應(yīng)用題(1)假定對(duì)有序表：(3,4,5,7, 24, 30, 42,54,63,72,87,95)進(jìn)行折半查找，試回答下列問題:畫出描述折半查找過程的判定樹；若查找元素54,需依次與哪些元素比較？若查找元素90,需依次與哪些元素比較？假定每個(gè)元素的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。先畫出判定樹如下(注：mid= (1+12)/2 =6):30634 2454 7295查找元素54,需依次與 30, 63, 42, 54元素比較；查找元素90,需依次與 30, 63,87, 95元素比較；求ASL之前，需要統(tǒng)計(jì)每個(gè)元素的查找次數(shù)。判定樹的前3層共查找1+2X 2 + 4X3=17次；但最

10、后一層未滿,不能用8X4,只能用5X4=20次，所以 ASL = 1/12 ( 17+20) = 37/12 (2)在一棵空的二叉排序樹中依次插入關(guān)鍵字序列為12 , 7, 17, 11 ,16, 2, 13, 9, 21, 4,請(qǐng)畫出所得到的二叉排序樹。12 、2111621 / /4913驗(yàn)算方法：用中序遍歷應(yīng)得到排序結(jié)果：2,4,7,9,11,12,13,16,17, 21(5)設(shè)哈希表的地址范圍為017,哈希函數(shù)為：H (key) =key%16。用線性探測(cè)法處理沖突，輸入關(guān)鍵字序列：(10, 24, 32, 17, 31 , 30, 46, 47, 40, 63, 49),構(gòu)造哈希表

11、，試回答下列問題：畫出哈希表的示意圖；若查找關(guān)鍵字63,需要依次與哪些關(guān)鍵字進(jìn)行比較？若查找關(guān)鍵字60,需要依次與哪些關(guān)鍵字比較？假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。畫表如下：012345678910111213141516173217634924401030314647查找63,首先要與 H(63)=63%16=15號(hào)單元內(nèi)容比較，即 63 vs 31 ,no;然后順移，與46,47,32,17,63 相比，一共比較了 6次！查找60,首先要與H(60)=60%16=12號(hào)單元內(nèi)容比較，但因?yàn)?12號(hào)單元為空(應(yīng)當(dāng)有空標(biāo)記)，所以應(yīng)當(dāng)只比較這一次即可。對(duì)于黑色數(shù)據(jù)元素，

12、各比較1次；共6次；對(duì)紅色元素則各不相同，要統(tǒng)計(jì)移位的位數(shù)?！?3”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以 ASL=1/11 (6 + 2+3X3+6) = 23/11(6)設(shè)有一組關(guān)鍵字(9, 01, 23, 14, 55, 20, 84, 27),采用哈希函數(shù)：H (key) =key %7 ,表長(zhǎng)為10,用開放地址法的二次探測(cè)法處理沖突。要求：對(duì)該關(guān)鍵字序列構(gòu)造哈希表，并計(jì)算查找成功的平均查找長(zhǎng)度。散列地址0123456789關(guān)鍵字140192384275520比較次數(shù)11123412平均查找長(zhǎng)度： ASLucc= (1+1 + 1+2+3

13、+4+1+2) /8=15/8以關(guān)鍵字 27為例：H (27) =27%7=6(沖突)H產(chǎn)(6+1) %10=7(沖突)H2= (6+22) %10=0(沖突) H 3= (6+33) %10=5 所以比較了 4 次。第8章排序.選擇題CDBDCBCDBCBCCCA.應(yīng)用題(1)設(shè)待排序的關(guān)鍵字序列為 12, 2, 16, 30, 28, 10, 16*, 20, 6, 18,試分別寫出使用以下排序方法,每趟排序結(jié)束后關(guān)鍵字序列的狀態(tài)。222222222102166212261022222222126281816*直接插入排序折半插入排序希爾排序（增量選取 5, 3, 1）冒泡排序快速排序簡(jiǎn)單

14、選擇排序堆排序二路歸并排序直接插入排序121630281016*20121630281016*20121630281016*20121628301016*20101216283016*2010121616*28302010121616*202830610121616*20286101216 16*1820折半插入排序排序過程同希爾排序（增量選取 5, 3, 1）6181216*20302810181616*203028121616* 1820 2830冒泡排序1216281016*20612161016*2061812101616* 61820101216616*1820101261616*1

15、820106121616*1820610121616*1820610121616*1820快速排序62 10 12 28 30 16* 202610122830 16*20261012 18 16 16* 20 ：2610 1216*16 18202610 1216* 1618 2061861861861861861861830182830（增量選?。ㄔ隽窟x?。ㄔ隽窟x取1830283028302830283028302830283016 1816 18 28 30 28 3028 305）3）1）22222222兒J廳列處IV律皮刃I）后廳列處IV律皮7簡(jiǎn)單選擇排序121630281016*2

16、061630281016*2061030281616*2061012281616*2061012162816*20610121616*28 20610121616*1820610121616*182036121230303030281818181818182830 TOC o 1-5 h z 2610121616*18202830二路歸并排序2 1216 3010 2816 * 206 182 12 16 3010 16* 20 286 182 10 12 16 16* 20 28 306 182 6 10 12 16 16* 18 20 28 30堆排序第一步，形成初始大根堆（詳細(xì)過程略），第二步做堆排序。交換1與9對(duì)象從1到8重新形成堆218181612161261016*2121016*303016*16*1216121626101826101830301016121612102616*182616*18202830202830612121061021616*18216167重新形成堆1到6重新形成堆1到5重新形成堆20282028202820282830交換1與5對(duì)象從1到4重新形成堆12610121616*18202830交換1與4對(duì)象1062121616*18202830從1到3重新形成堆交換1與3對(duì)象從1到2重新形成堆交換1與2對(duì)象得到