數據結構c語言版課后習題答案完整版

1、5 .選擇題：CCBDCA6 .試分析下面各程序段的時間復雜度。(1) O(1)(2) O(m*n)2(3) O(n2)(4) O(log3n)(5)因為x+共執(zhí)行了n-1+n-2+1=n(n-1)/2,所以執(zhí)行時間為O(n2)(6) O(.n)第2章線性表1 .選擇題babadbcabdcddac2 .算法設計題(6)設計一個算法，通過一趟遍歷在單鏈表中確定值最大的結點。ElemTypeMax(LinkListL)if(L->next=NULL)returnNULL;pmax=L->next;法設計題(2)回文是指正讀反讀均相同的字符序列，如"abba"和&q

2、uot;abdba”均是回文，但"good"不是回文。試寫一個算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)?根據提示，算法可設計為：合應用題(1)已知模式串t='abcaabbabcab'寫出用KMP法求得的每個字符對應的next和nextval函數值。模式串t的next和nextval值如下:j123456789101112t串abcaabbabcabnextj011122312345nextvalj011021301105(3)數組A中，每個元素Ai,j的長度均為32個二進位，行下標從-1到9,列下標從1到11,從首地址S開始連續(xù)存放主存儲

3、器中，主存儲器字長為16位。求：存放該數組所需多少單元存放數組第4列所有元素至少需多少單元數組按行存放時，元素A7,4的起始地址是多少數組按列存放時，元素A4,7的起始地址是多少每個元素32個二進制位，主存字長16位，故每個元素占2個字長，行下標可平移至1到11。(1) 242(2)22(3)s+182(4)s+142(4)請將香蕉banana用工具H()Head(),T()-Tail()從L中取出。L=(apple,(orange,(strawberry,(banana),peach),pear)H(H(T(H(T(H(T(L)(5)寫一個算法統(tǒng)計在輸入字符串中各個不同字符出現的頻度并將結果

4、存入文件(字符串中的合法字符為A-Z這26個字母和0-9這10個數字)。voidCount()/統(tǒng)計輸入字符串中數字字符和字母字符的個數。inti,num36;charch;for(i=0;i<36;i+)numi=0;/初始化while(ch=getchar()!=#')/'#'表示輸入字符串結束。if('0'<=ch<='9')i=ch48;numi+;/數字字符elseif('A'<=ch<='Z')i=ch-65+10;numi+;/字母字符for(i=0;i<1

5、0;i+)/輸出數字字符的個數printf("數字%d的個數=%dn”,i,numi);for(i=10;i<36;i+)/求出字母字符的個數printf("字母字符c的個數=%dn”,i+55,numi);/算法結束。第5章樹和二叉樹1 .選擇題ADDCACCBDCCCACC2 .應用題(2)設一棵二叉樹的先序序列：ABDFCEGH,中序序列：BFDAGEHC畫出這棵二叉樹。畫出這棵二叉樹的后序線索樹。FGH)(1)(2)(3)假設用于通信白電文僅由8個字母組成，字母在電文中出現的頻率分別為，°試為這8個字母設計赫夫曼編碼。試設計另一種由二進制表示的等長編

6、碼方案。對于上述實例，比較兩種方案的優(yōu)缺點。解：方案1;哈夫曼編碼先將概率放大100倍，以方便構造哈夫曼樹。w=7,19,2,6,32,3,21,10，按哈夫曼規(guī)則：(2,3),6,(7,10),19,21,32(100)(401'60)19，21、2/(28)>17<7-106字母編R對應編碼出現頻率1110020031111041110510方案比較:方案1的WP2+4+5+=+=方案2的WP3+=3結論：哈夫曼編碼優(yōu)于等長二進制編碼?3.算法設計題以二叉鏈表作為二叉樹的存儲結構，編寫以下算法:(1)統(tǒng)計二叉樹的葉結點個數。intLeafNodeCount(BiTree

7、T)字母編R對應編碼出現頻率10002001301040115100610if(T=NULL)return0;/如果是空樹，則葉子結點個數為02elseif(T->lchild=NULL&&T->rchild=NULL)return1;/判斷該結點是否是葉子結點(左孩子右孩子都為空)，若是則返回1elsereturnLeafNodeCount(T->lchild)+LeafNodeCount(T->rchild);(3)交換二叉樹每個結點的左孩子和右孩子。voidChangeLR(BiTree&T)BiTreetemp;if(T->lchi

8、ld=NULL&&T->rchild=NULL)return;elsetemp=T->lchild;T->lchild=T->rchild;T->rchild=temp;ChangeLR(T->lchild);ChangeLR(T->rchild);1 .選擇題CBBBCBABAADCCDDB2 .應用題(1)已知如圖所示的有向圖，請給出:每個頂點的入度和出度；鄰接矩陣；鄰接表；逆鄰接表。便亙1I3in5631tt出生Q3（，）足鞠皋(2)已知如圖所示的無向網，鄰接矩陣；鄰接表；最小生成樹圖無向網1(13(2)邪援建降10010尊J00

9、0fl00110000JL001三*S3-4H44IE4345535555976554957654332266ab4c3ba4c5ca3b5db5c5eb9d7fd6e3gd5f2hc5d4d5d5e7f3g2h6g6e9h5f6g5/h4A(3)已知圖的鄰接矩陣如所示。試分別畫出臼頂點1出發(fā)進行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。深度優(yōu)先生成樹DOOooiocaDOO000110001io100DOOIoa00D000I001aoIo1091qooa廣度優(yōu)先生成樹a到其他各頂點間的最短路徑,圖鄰接矩陣(4)有向網如圖所示，試用迪杰斯特拉算法求出從頂點V'、飛點、i=1i=2i=

10、3i=4i=5i=6b15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)t5(a,b)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)14(a,c,f,d,g)S終點集a,ca,c,fa,c,f,ea,c,f,e,da,c,f,e,d,ga,c,f,e,d,g,b第7章查找1 .選擇題CDCABCCCDCBCADA2 .應用題(1)假定對有序表：(3,4,5,7,24,30,42,54,63,72,87,95)進行

11、折半查找,試回答下列問題：畫出描述折半查找過程的判定樹；若查找元素54,需依次與哪些元素比較若查找元素90,需依次與哪些元素比較假定每個元素的查找概率相等，求查找成功時的平均查找長度。先畫出判定樹如下(注：mid=?(1+12)/2?=6):30查找元素54,需依次與查找元素90,需依次與30,63,42,54元素比較;30,63,87,95元素比較；3層共查找1+2X2+4X3=17求ASL之前，需要統(tǒng)計每個元素的查找次數。判定樹的前次；但最后一層未滿，不能用8X4,只能用5X4=20次,所以ASL=1/12(17+20)=37/12"(2)在一棵空的二叉排序樹中依次插入關鍵字序列

12、為12,7,17,11,16,2,13,9,21,4,請畫出所得到的二叉排序樹。12/、71八2111621/4913驗算方法：用中序遍歷應得到排序結果：2,4,7,9,11,12,13,16,17,21(5)設哈希表的地址范圍為017,哈希函數為：H(key)=key%1&用線性探測法處理沖突，輸入關鍵字序列：(10,24,32,17,31,30,46,47,40,63,49),構造哈希表，試回答下列問題：畫出哈希表的示意圖；若查找關鍵字63,需要依次與哪些關鍵字進行比較若查找關鍵字60,需要依次與哪些關鍵字比較假定每個關鍵字的查找概率相等，求查找成功時的平均查找長度。畫表如下：01

13、2345678910111213141516173217634924401030314647查找63,首先要與H(63)=63%16=15號單元內容比較，即63vs31,no;然后順移，與46,47,32,17,63相比，一共比較了6次！查找60,首先要與H(60)=60%16=12號單元內容比較，但因為12號單元為空(應當有空標記)，所以應當只比較這一次即可。對于黑色數據元素，各比較1次；共6次；對紅色元素則各不相同，要統(tǒng)計移位的位數。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11(6+2+3X3+6)=23/11(6)設有一組

14、關鍵字(9,01,23,14,55,20,84,27),采用哈希函數：H(key)=key%7,表長為10,用開放地址法的二次探測法處理沖突。要求：對該關鍵字序列構造哈希表，并計算查找成功的平均查找長度。散列地址0123456789關鍵字140192384275520?比較次數11123412?平均查找長度：ASLcc=(1+1+1+2+3+4+1+2)/8=15/8以關鍵字27為例：H(27)=27%7=6(沖突)H1=(6+1)%10=7(沖突)H2=(6+22)%10=0(沖突)H3=(6+33)%10=5所以比較了4次。第8章排序1 .選擇題CDBDCBCDBCBCCCA2 .應用題(

15、1)設待排序的關鍵字序列為12,2,16,30,28,10,16*,20,6,18,試分別寫出使用以下排序方法，每趟排序結束后關鍵字序列的狀態(tài)。直接插入排序折半插入排序希爾排序(增量選取冒泡排序快速排序簡單選擇排序堆排序二路歸并排序5,3,1)直接插入排序2121630281016*206182121630281016*206182121630281016*206182121628301016*206182101216283016*20618210121616*283020618210121616*202830618261012161618202830折

16、半插入排序排序過程同希爾排序（增量選取5,3,1）102166181216*203028（增量選取5）621210181616*203028（增量選取3）2610121616*18202830（增量選取1）冒泡排序21216281016*2061830212161016*206182830212101616*6182028302101216616*182028302101261616*182028302106121616*182028302610121616*182028302610121616*18202830快速排序12621012283016*2016186261012283016*20

17、161828261012181616*2028301826101216*161820283016*26101216*1618202830左子序列遞歸深度為1,右子序列遞歸深度為3簡單選擇排序2121630281016*20618261630281016*201218261030281616*201218261012281616*203018261012162816*2030182610121616182030282610121616*182028302610121616*18202830二路歸并排序2121630102816*20618212163010

18、16*2028618210121616*2028306182 610121616*18202830堆排序第一步，形成初始大根堆（詳細過程略），第二步做堆排序。初始排序不是大根堆交換1與10對象交換1與9對象從1到8重新形成堆16*16*121612162610182610183030交換1到6重新形成堆1016121612102616*182616*1820283030交換1到5重新形成堆612121061021616*1821616*1820283030交換121061062121616*181216164重新形成堆202820282028202820282610121616*18202830交換1與3對象6210121616*18202830從1到2重新形成堆交換1與2對象得到結果3 .算法設計題(1)試以單鏈表為存