數(shù)據(jù)結(jié)構(gòu)c語言版課后習(xí)題答案

1、第1章緒論5 .選擇題：CCBDCA6 .試分析下面各程序段的時(shí)間復(fù)雜度。(1) O(1)(2) O(m*n)(3) O(n2)(4) O(log/)(5)因?yàn)閤+共執(zhí)行了n-1+n-2+,+1=n(n-1)/2,所以執(zhí)行時(shí)間為O(n2)(6) O(,n)第2章線性表1 .選擇題babadbcabdcddac2 .算法設(shè)計(jì)題(6)設(shè)計(jì)一個(gè)算法，通過一趟遍歷在單鏈表中確定值最大的結(jié)點(diǎn)。ElemTypeMax(LinkListL)if(L-next=NULL)returnNULL;pmax=L-next;/假定第一個(gè)結(jié)點(diǎn)中數(shù)據(jù)具有最大值p=L-next-next;while(p!=NULL)/如果

2、下一個(gè)結(jié)點(diǎn)存在if(p-datapmax-data)pmax=p;p=p-next;returnpmax-data;(7)設(shè)計(jì)一個(gè)算法，通過遍歷一趟，將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)，仍利用原表的存儲空間。voidinverse(LinkList&L)/逆置帶頭結(jié)點(diǎn)的單鏈表Lp=L-next;L-next=NULL;while(p)q=p-next;/q指向*p的后繼p-next=L-next;L-next=p;/*p插入在頭結(jié)點(diǎn)之后p=q;(10)已知長度為n的線性表A采用順序存儲結(jié)構(gòu)，請寫一時(shí)間復(fù)雜度為O(n)、空間復(fù)雜度為0(1)的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素。題目分

3、析在順序存儲的線性表上刪除元素，通常要涉及到一系列元素的移動(dòng)(刪第i個(gè)元素，第i+1至第n個(gè)元素要依次前移)。本題要求刪除線性表中所有值為item的數(shù)據(jù)元素，并未要求元素間的相對位置不變。因此可以考慮設(shè)頭尾兩個(gè)指針(i=1,j=n),從兩端向中間移動(dòng)，凡遇到值item的數(shù)據(jù)元素時(shí)，直接將右端元素左移至值為item的數(shù)據(jù)元素位置。voidDelete(ElemTypeA,intn)/A是有n個(gè)元素的一維數(shù)組，本算法刪除A中所有值為item的元素。i=1;j=n;/設(shè)置數(shù)組低、高端指針(下標(biāo))。while(ij)while(ij&Ai!=item)i+;/若值不為item,左移指針。if(ij)w

4、hile(ij&Aj=item)j-；/若右端元素值為item,指針左移if(ij)Ai+=Aj-;)算法討論因元素只掃描一趟，算法時(shí)間復(fù)雜度為0(n)。刪除元素未使用其它輔助空間，最后線性表中的元素個(gè)數(shù)是jo第3章棧和隊(duì)列1 .選擇題CCDAADABCDDDBCB2 .算法設(shè)計(jì)題(2)回文是指正讀反讀均相同的字符序列，如abba和abdba”均是回文，但good不是回文。試寫一個(gè)算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)根據(jù)提示，算法可設(shè)計(jì)為：/以下為順序棧的存儲結(jié)構(gòu)定義#defineStackSize100/假定預(yù)分配的?？臻g最多為100個(gè)元素typedefcharData

5、Type;/假定棧元素的數(shù)據(jù)類型為字符typedefstructDataTypedataStackSize;inttop;SeqStack;intIsHuiwen(char*t)/判斷t字符向量是否為回文，若是，返回1,否則返回0SeqStacks;inti,len;chartemp;InitStack(&s);len=strlen(t);/求向量長度for(i=0;ilen/2;i+)/將一半字符入棧Push(&s,ti);while(!EmptyStack(&s)/每彈出一個(gè)字符與相應(yīng)字符比較temp=Pop(&s);if(temp!=Si)return0;/不等則返回0elsei+;re

6、turn1;/比較完畢均相等則返回1(7)假設(shè)以數(shù)組Qm存放循環(huán)隊(duì)列中的元素，同時(shí)設(shè)置一個(gè)標(biāo)志tag,以tag=0和tag=1來區(qū)別在隊(duì)頭指針(front)和隊(duì)尾指針(rear)相等時(shí)，隊(duì)列狀態(tài)為空還是滿”。試編寫與此結(jié)構(gòu)相應(yīng)的插入(enqueue)和刪除(dlqueue)算法?！窘獯稹垦h(huán)隊(duì)列類定義#includetemplateclassQueue循環(huán)隊(duì)列的類定義public:Queue(int=10);Queue()deleteQ;voidEnQueue(Type&item);TypeDeQueue();TypeGetFront();voidMakeEmpty()front=rear=t

7、ag=0;/置空隊(duì)列intIsEmpty()constreturnfront=rear&tag=0;判隊(duì)歹U空否intIsFull()constreturnfront=rear&tag=1;判隊(duì)列滿否private:intrear,front,tag;Type*Q;隊(duì)尾指針、隊(duì)頭指針和隊(duì)滿標(biāo)志/存放隊(duì)列元素的數(shù)組intm;隊(duì)列最大可容納元素個(gè)數(shù))構(gòu)造函數(shù)templateQueue:Queue(intsz):rear(0),front(0),tag(0),m(sz)建立一個(gè)最大具有m個(gè)元素的空隊(duì)列。Q=newTypem;/創(chuàng)建隊(duì)列空間assert(Q!=0);/斷言：動(dòng)態(tài)存儲分配成功與否)插入函

8、數(shù)template判隊(duì)列是否不滿，滿則出錯(cuò)處理隊(duì)尾位置進(jìn)1,隊(duì)尾指針指示實(shí)際隊(duì)尾位置/進(jìn)隊(duì)列標(biāo)志改1,表示隊(duì)列不空voidQueue:EnQueue(Type&item)assert(!IsFull();rear=(rear+1)%m;Qrear=item;tag=1;)刪除函數(shù)template判斷隊(duì)列是否不空，空則出錯(cuò)處理隊(duì)頭位置進(jìn)1,隊(duì)頭指針指示實(shí)際隊(duì)頭的前一位置標(biāo)志改0,表小棧不滿/返回原隊(duì)頭元素的值判斷隊(duì)列是否不空，空則出錯(cuò)處理/返回隊(duì)頭元素的值TypeQueue:DeQueue()assert(!IsEmpty();front=(front+1)%m;tag=0;returnQfro

9、nt;)讀取隊(duì)頭元素函數(shù)templateTypeQueue:GetFront()assert(!IsEmpty();returnQ(front+1)%m;)第4章串、數(shù)組和廣義表1 .選擇題BBCABBBCBBABDCBC2 .綜合應(yīng)用題(1)已知模式串t=abcaabbabcab寫出用KMP法求得的每個(gè)字符對應(yīng)的next和nextval函數(shù)值。模式串t的next和nextval值如下：j123456789101112t串a(chǎn)bcaabbabcabnextj011122312345nextvalj011021301105(3)數(shù)組A中，每個(gè)元素Ai,j的長度均為32個(gè)二進(jìn)位，行下標(biāo)從-1到9,列

10、下標(biāo)從1到11,從首地址S開始連續(xù)存放主存儲器中，主存儲器字長為16位。求：存放該數(shù)組所需多少單元？存放數(shù)組第4列所有元素至少需多少單元？數(shù)組按行存放時(shí)，元素A7,4的起始地址是多少？數(shù)組按列存放時(shí)，元素A4,7的起始地址是多少？每個(gè)元素32個(gè)二進(jìn)制位，主存字長16位，故每個(gè)元素占2個(gè)字長，行下標(biāo)可平移至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)寫一個(gè)

11、算法統(tǒng)計(jì)在輸入字符串中各個(gè)不同字符出現(xiàn)的頻度并將結(jié)果存入文件(字符串中的合法字符為A-Z這26個(gè)字母和0-9這10個(gè)數(shù)字)。voidCount()/統(tǒng)計(jì)輸入字符串中數(shù)字字符和字母字符的個(gè)數(shù)。inti,num36;charch;for(i=0;i36;i+)numi=0;/初始化while(ch=getchar()!=#)/#表示輸入字符串結(jié)束。if(0=ch=9)i=ch48;numi+;/數(shù)字字符elseif(A=ch=Z)i=ch-65+10;numi+;/字母字符for(i=0;i10;i+)/輸出數(shù)字字符的個(gè)數(shù)printf(數(shù)字%d的個(gè)數(shù)=%dn”,i,numi);for(i=10;i

12、lchild=NULL&T-rchild=NULL)return1;/判斷該結(jié)點(diǎn)是否是葉子結(jié)點(diǎn)(左孩子右孩子都為空)，若是則返回1elsereturnLeafNodeCount(T-lchild)+LeafNodeCount(T-rchild);(3)交換二叉樹每個(gè)結(jié)點(diǎn)的左孩子和右孩子。voidChangeLR(BiTree&T)(BiTreetemp;if(T-lchild=NULL&T-rchild=NULL)return;else(temp=T-lchild;T-lchild=T-rchild;T-rchild=temp;ChangeLR(T-lchild);ChangeLR(T-rch

13、ild);1 .選擇題CBBBCBABAADCCDDB2 .應(yīng)用題(1)已知如圖6.27所示的有向圖，請給出:每個(gè)頂點(diǎn)的入度和出度；鄰接矩陣；鄰接表；逆鄰接表。10010001000001011100000J10010.圖6.28無(2)已知如圖6.28所示的無向網(wǎng)，請給出:鄰接矩陣；鄰接表；最小生成樹H454二5二6二75735553d5d5e7f3g2h6g6AAAAc3c5b5c5d7e3f2d4b4a4a3b5b9d6d5c5abcdefgh(3)已知圖的鄰接矩陣如6.29所示。試分別畫出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。度Y成由a到其他各頂點(diǎn)間的最短(4)有向

14、網(wǎng)如圖6.29所示，試用迪杰斯特拉算法求出從頂點(diǎn)路徑，完成表6.9。圖6.29鄰接矩陣V弋點(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)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終點(diǎn)集a,ca,c,fa,c,f,ea,c,f,e,da,c,f,e,d,ga,c,f,e,d,g,b第7章查找1 .選擇題CDCABCCCDCBCAD

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

16、0)=37/12=3.083層共查找1+2X2+4X3=17(2)在一棵空的二叉排序樹中依次插入關(guān)鍵字序列為12,7,17,11,16,2,13,9,21,4,請畫出所得到的二叉排序樹。12/J次2；1/16214913驗(yàn)算方法：用中序遍歷應(yīng)得到排序結(jié)果：2,4,7,9,11,12,13,16,17,21(5)設(shè)哈希表的地址范圍為017,哈希函數(shù)為：H(key)=key%16。用線性探測法處理沖突，輸入關(guān)鍵字序列：(10,24,32,17,31,30,46,47,40,63,49),構(gòu)造哈希表，試回答下列問題：畫出哈希表的示意圖； 若查找關(guān)鍵字63,需要依次與哪些關(guān)鍵字進(jìn)行比較？ 若查找關(guān)鍵字

17、60,需要依次與哪些關(guān)鍵字比較？假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長度。畫表如下：012345678910111213141516173217634924401030314647查找63,首先要與H(63)=63%16=15號單元內(nèi)容比較，即63vs31,no;然后順移，與46,47,32,17,63相比，一共比較了6次！查找60,首先要與H(60)=60%16=12號單元內(nèi)容比較，但因?yàn)?2號單元為空(應(yīng)當(dāng)有空標(biāo)記)，所以應(yīng)當(dāng)只比較這一次即可。對于黑色數(shù)據(jù)元素，各比較1次；共6次；對紅色元素則各不相同，要統(tǒng)計(jì)移位的位數(shù)?！?3”需要6次，“49”需要3次，“40”需要2次，

18、“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,表長為10,用開放地址法的二次探測法處理沖突。要求：對該關(guān)鍵字序列構(gòu)造哈希表，并計(jì)算查找成功的平均查找長度。散列地址0123456789關(guān)鍵字140192384275520比較次數(shù)11123412平均查找長度：ASLcc=(1+1+1+2+3+4+1+2)/8=15/8以關(guān)鍵字27為例：H(27)=27%7=6(沖突)H1=(6+1)%10=7(沖突)H2=(6+22)%10=0(沖突)H3=(6

19、+33)%10=5所以比較了4次。第8章排序1 .選擇題CDBDCBCDBCBCCCA2 .應(yīng)用題(1)設(shè)待排序的關(guān)鍵字序列為12,2,16,30,28,10,16*,20,6,18,試分別寫出使用以下排序方法，每趟排序結(jié)束后關(guān)鍵字序列的狀態(tài)。直接插入排序折半插入排序希爾排序(增量選取5,3,1)冒泡排序快速排序簡單選擇排序堆排序二路歸并排序直接插入排序2121630281016*206182121630281016*206182121630281016*206182121628301016*206182101216283016*20618210121616*28302061821012161

20、6*202830618102610121616*2610121616*折半插入排序排序過程同希爾排序(增量選取5,3,1)2166181216*2018202820303028281830（增量選取5)621210181616*203028（增量選取3)2610121616*18202830（增量選取1）冒泡排序21216281016*2061830212161016*206182830212101616*6182028302101216616*182028302101261616*182028302106121616*182028302610121616*182028302610121616*18202830快速排序12621012283016*2016186261012283016*20161828261012181616*2028301826101216*161820283016*26101216*1618202830左子序列遞歸深度為1,右子序列遞歸深度為3簡單選擇排序2121630281016*20618261630281016*201218261030281616*201218261012281616*203018261012162816*203018261012