數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）（第三版）（微課版） 習(xí)題參考答案 梁海英 第6-8章

?PAGE294?數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言)微課版?PAGE293?附錄習(xí)題參考答案附錄習(xí)題參考答案第6章習(xí)題參考答案一、選擇題1.D2.A3.D4.B5.A6.C7.B8.A9.B10.C11.B12.A13.D14.C15.D16.C17.D18.A19.C20.D21.D二、填空題1.鄰接矩陣、鄰接表 2.深度優(yōu)先遍歷、廣度優(yōu)先遍歷3.n(n-1)n-1 4.鄰接表、廣度優(yōu)先遍歷5.有向?qū)⑧徑泳仃嚨牡趇行全部置06.鄰接表鄰接矩陣7.出度n 8.O(n2),O(n+e)9.n,2e 10.克魯斯卡爾(Kruskal)普里姆(Prim)11.O(n2)O(n+e) 12.某一頂點(diǎn)遞增13.出度入度 14.相等權(quán)15.O(n2)、O(n+e) 16.O(n2)、O(n+e)三、判斷題1.×2.×3.×4.×5.√6.×7.√8.√9.×10.√11.×四、簡(jiǎn)答題1.用克魯斯卡爾算法得到的最小生成樹為：(1,2)3，(4,6)4，(1,3)5，(1,4)8，(2,5)10，(4,7)202.（1）DFS：????… （2）BFS：???…?3.鄰接矩陣和鄰接表：4.根據(jù)克魯斯卡爾算法思想畫圖表示最小生成樹的生成過(guò)程如下：5.(1)是有向圖，因?yàn)槠溧徑泳仃囀遣粚?duì)稱的(2)頂點(diǎn)1的入度為1，出度為2頂點(diǎn)2的入度為2，出度為2頂點(diǎn)3的入度為1，出度為2頂點(diǎn)4的入度為3，出度為26.頂點(diǎn)1的入度為2，出度為2頂點(diǎn)2的入度為2，出度為2頂點(diǎn)3的入度為2，出度為1頂點(diǎn)4的入度為1，出度為27.(1)│012∞∞7∞∞∞││1202∞∞10∞∞││∞205∞∞15∞││∞∞50∞∞∞3││7∞∞∞08∞∞││∞10∞∞8011∞││∞∞15∞∞1106││∞∞∞3∞∞60│(2)8.319.（1）深度優(yōu)先搜索頂點(diǎn)序列：1-2-3-4-5-6邊的序列：（1，2）（2，3）（3，4）（4，5）（5，6）（2）廣度優(yōu)先搜索頂點(diǎn)序列：1-2-3-6-5-4邊的序列：（1，2）（1，3）（1，6）（1，5）（5，4）注：本題中所求深度優(yōu)先序列和廣度優(yōu)先序列有多種，以上為其中一種。10.(1)頂點(diǎn)1的入度為3，出度為0頂點(diǎn)2的入度為2，出度為2頂點(diǎn)3的入度為1，出度為2頂點(diǎn)4的入度為1，出度為3頂點(diǎn)5的入度為2，出度為1頂點(diǎn)6的入度為2，出度為3(2)鄰接矩陣為：(3)鄰接表為：(4)逆鄰接表為：11.(1)鄰接矩陣為：(2)鄰接表為：12.解答：根據(jù)普里姆算法的基本思想，構(gòu)造最小生成樹，在此，由于邊的權(quán)值出現(xiàn)了相同值，因此，在構(gòu)造實(shí)際的最小生成樹時(shí)結(jié)果是不唯一的，下圖給出了其中的一種構(gòu)造過(guò)程：13.解：(1)最小生成樹可直接畫出，如下圖所示。(2)可用鄰接矩陣和鄰接表來(lái)描述：14.拓?fù)湫蛄袨椋?40257368915.解：終點(diǎn)vi從a頂點(diǎn)出發(fā)到其余各頂點(diǎn)的最短路徑path[i]的變化情況i=0i=1i=2i=3i=4i=5i=6dist[a]path[a]0dist[b]path[b]15<a,b>15<a,b>15<a,b>15<a,b>15<a,b>15<a,b>dist[c]path[c]2<a,c>dist[d]path[d]12<a,d>12<a,d>11<a,c,f,d>11<a,c,f,d>dist[e]path[e]∞10<a,c,e>10<a,c,e>dist[f]path[f]∞6<a,c,f>dist[g]path[g]∞∞16<a,c,f,g>16<a,c,f,g>15<a,d,g>vjcfedgbS{a}{a,c}{a,c,f}{a,c,f,e}{a,c,f,e,d}{a,c,f,e,d,g}{a,c,f,e,d,g,b}最短路徑為：（a,c,f,e,d,g,b）或者（a,c,f,e,d,b,g）16.求頂點(diǎn)0其余各頂點(diǎn)的最短路徑終點(diǎn)vi從0頂點(diǎn)出發(fā)到其余各頂點(diǎn)的最短路徑path[i]的變化情況i=0i=1i=2i=3i=4dist[0]path[0]0dist[1]path[1]10<0,1>dist[2]path[2]∞60<0,1,2>50<0,3,2>dist[3]path[3]30<0,3>30<0,3>dist[4]path[4]100<0,4>100<0,4>90<0,3,4>60<0,3,2,4>vj1324S{0}{0,1}{0,1,3}{0,1,3,2}{0,1,3,2,4}五、編程題1./*利用鄰接矩陣實(shí)現(xiàn)圖的遍歷*//*從第i個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G*/voidDFS(GraphG,inti){intj;printf("%3c",G.V[i]); /*訪問(wèn)第i個(gè)頂點(diǎn)*/visited[i]=1;for(j=0;j<G.n;j++)if((G.arcs[i][j]==1)&&(visited[j]==0))DFS(G,j); /*對(duì)頂點(diǎn)i的尚未訪問(wèn)的鄰接頂點(diǎn)j遞歸調(diào)用DFS*/}/*【算法6.10對(duì)圖G進(jìn)行深度優(yōu)先遍歷】*/2./*【算法6.13用鄰接表實(shí)現(xiàn)圖的廣度優(yōu)先搜索遍歷】*/voidBFS(ALGraphG,intk){inti;ArcNode*p;InitQueue(&Q); /*初始化隊(duì)列*/printf("%3c",G.adjList[k].data); /*訪問(wèn)第k個(gè)頂點(diǎn)*/visited[k]=1; EnQueue(&Q,k); /*第k個(gè)頂點(diǎn)進(jìn)隊(duì)*/while(!QueueEmpty(&Q)){ /*隊(duì)列非空*/DelQueue(&Q,&i);p=G.adjList[i].firstArc; /*獲取第1個(gè)鄰接點(diǎn)*/while(p!=NULL){if(visited[p->adjVex]==0) /*訪問(wèn)第i個(gè)頂點(diǎn)的末曾訪問(wèn)的鄰接頂點(diǎn)*/{printf("%3c",G.adjList[p->adjVex].data);visited[p->adjVex]=1;EnQueue(&Q,p->adjVex); /*第k個(gè)頂點(diǎn)進(jìn)隊(duì)*/}p=p->nextArc;} }}3.intvisited[MAXSIZE];//指示頂點(diǎn)是否在當(dāng)前路徑上intlevel＝1;//遞歸進(jìn)行的層數(shù)intexist_path_DFS(ALGraphG,inti,intj)//深度優(yōu)先判斷有向圖G中頂點(diǎn)i到頂點(diǎn)j是否有路徑,是則返回1,否則返回0{if(i==j)return1;//i就是jelse{visited[i]=1;for(p=G.vertices[i].firstarc;p;p=p->nextarc,level--){level++;k=p->adjvex;if(!visited[k]&&exist_path(k,j))return1;//i下游的頂點(diǎn)到j(luò)有路徑}//for}//elseif(level==1)return0;}//exist_path_DFS4.intvisited[MAXSIZE];intexist_path_len(ALGraphG,inti,intj,intk)//判斷鄰接表方式存儲(chǔ)的有向圖G的頂點(diǎn)i到j(luò)是否存在長(zhǎng)度為k的簡(jiǎn)單路徑{if(i==j&&k==0)return1;//找到了一條路徑,且長(zhǎng)度符合要求elseif(k>0){visited[i]=1;for(p=G.vertices[i].firstarc;p;p=p->nextarc){l=p->adjvex;if(!visited[l])if(exist_path_len(G,l,j,k-1))return1;//剩余路徑長(zhǎng)度減一}//forvisited[i]=0;//本題允許曾經(jīng)被訪問(wèn)過(guò)的結(jié)點(diǎn)出現(xiàn)在另一條路徑中}//elsereturn0;//沒找到}//exist_path_len5.解：//本題中的圖G均為有向無(wú)權(quán)圖。StatusDelete_Arc(MGraph&G,charv,charw)//在鄰接矩陣表示的圖G上刪除邊(v,w){if((i=LocateVex(G,v))<0)returnERROR;if((j=LocateVex(G,w))<0)returnERROR;if(G.arcs[i][j].adj){G.arcs[i][j].adj=0;G.arcnum--;}returnOK;}//Delete_Arc第7章習(xí)題參考答案一、選擇題1.B2.A3.A4.C5.C6.A7.C8.B9.A二、填空題1.散列法關(guān)鍵字 2.253.構(gòu)造一個(gè)好的HASH函數(shù)確定解決沖突的方法 4.975.順序查找（線性查找）28，6，12，20 6.7/68/67.1,3三、簡(jiǎn)答題1.(1)查找不成功時(shí)，需進(jìn)行n+1次比較才能確定查找失敗。因此平均查找長(zhǎng)度為n+1，這時(shí)有序表和無(wú)序表是一樣的。(2)查找成功時(shí)，平均查找長(zhǎng)度為(n+1)/2,有序表和無(wú)序表也是一樣的。因?yàn)轫樞虿檎遗c表的初始序列狀態(tài)無(wú)關(guān)。2.n的查找過(guò)程如下(其中方括號(hào)表示當(dāng)前查找區(qū)間，圓括號(hào)表示當(dāng)前比較的關(guān)鍵字)下標(biāo)：1

2

3

4

5

6

7

8

9101112

13

第一次比較：[a

b

c

d

e

f(g)

h

i

j

k

p

q]第二次比較：

a

b

c

d

e

f

g

[h

i(j)k

p

q]第三次比較：

a

b

c

d

e

f

g

h

i

j[k(p)q]第四次比較：

a

b

c

d

e

f

g

h

i

j[(k)]p

q]經(jīng)過(guò)四次比較，查找失敗。3.解答：查找b的過(guò)程如下(其中方括號(hào)表示當(dāng)前查找區(qū)間，圓括號(hào)表示當(dāng)前比較的關(guān)鍵字)下標(biāo)：1

2

3

4

5

6

7

8

910111213

第一次比較：[a

b

c

d

e

f

(g)

h

i

j

k

p

q]第二次比較：[a

b(c)d

e

f]

g

h

i

j

k

p

q第三次比較：[a(b)]c

d

e

f

g

h

i

j

k

p

q經(jīng)過(guò)三次比較，查找成功。

4.5.(1)判定樹如下（注：mid=?(1+12)/2?=6）：(2)查找元素54，需依次與30,63,42,54等元素比較；(3)查找元素90，需依次與30,63,87,95等元素比較；(4)求ASL之前，需要統(tǒng)計(jì)每個(gè)元素的查找次數(shù)。判定樹的前3層共查找1＋2×2＋4×3=17次；但最后一層未滿，不能用8×4，只能用5×4=20次，所以ASL＝1/12（17＋20）＝37/12≈3.086.不適合！雖然有序的單鏈表的結(jié)點(diǎn)是按從小到大（或從大到?。╉樞蚺帕校蚱浯鎯?chǔ)結(jié)構(gòu)為單鏈表，查找結(jié)點(diǎn)時(shí)只能從頭指針開始逐步搜索，故不能進(jìn)行折半查找。二分查找的速度在一般情況下是快些，但在特殊情況下未必快。例如所查數(shù)據(jù)位于首位時(shí)，則線性查找快；而二分查找則慢得多。7.解答：根據(jù)哈希函數(shù)和處理沖突的方法為二次探測(cè)再散列，構(gòu)造哈希表如圖所示：8.查找某個(gè)元素的時(shí)間復(fù)雜度下限，如果理解為最短查找時(shí)間，則當(dāng)關(guān)鍵字值與表頭元素相同時(shí)，比較1次即可。要想降低時(shí)間復(fù)雜度，可以改用Hash查找法。此方法對(duì)表內(nèi)每個(gè)元素的比較次數(shù)都是O（1）。9.判定樹應(yīng)當(dāng)描述每次查找的位置：10解：由題意知，m=11(剛好為素?cái)?shù))則(22*3)%11=6……0 (41*3)%11=11……2(53*3)%11=14……5 (08*3)%11=2……2(08*3+1)%11=3(46*3)%11=12……6 (30*3)%11=8……2(30*3+2)%11=4(01*3)%11=0……3(01*3+6)%11=7 (31*3)%11=8……5(31*3+3)%11=8(66*3)%11=9……0(66*3+1)%11=111.等概率情況下，查找成功的平均查找長(zhǎng)度為：ASL=(1+2*2+3*4+4*8+5*3)/18=3.556

查找失敗時(shí)，最多的關(guān)鍵字比較次樹不超過(guò)判定樹的深度，此處為5。12.（1）畫表如下：012345678910111213141516173217634924401030314647（2）查找63,首先要與H(63)=63%16=15號(hào)單元內(nèi)容31比較，即63vs31,no;然后順移，與46,47,32,17,63相比，一共比較了6次?。?）查找60,首先要與H(60)=60%16=12號(hào)單元內(nèi)容比較，但因?yàn)?2號(hào)單元為空（應(yīng)當(dāng)有空標(biāo)記），所以應(yīng)當(dāng)只比較這一次即可。（4）對(duì)于黑色數(shù)據(jù)元素10，24，32，17，31，30，各比較1次；共6次；對(duì)紅色元素則各不相同，要統(tǒng)計(jì)移位的位數(shù)。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11×（6+6+2+3×3）=23/11=2.0913.等概率情況下，平均查找長(zhǎng)度為：（5*2+4*2+3*3+2*2+1*1）/10=3.2114.等概率情況下，該哈希表的平均查找長(zhǎng)度:(1*10+2*3)/13=16/13。四、編程題1.voidPrintWord(HashTableht){//按第一個(gè)字母的順序輸出哈希表ht中的標(biāo)識(shí)符。哈希函數(shù)為表示符的第一個(gè)字母在字母表中的序號(hào)，處理沖突的方法是線性探測(cè)開放定址法。for(i=1;i<=26;i++){j=i;while(ht.elem[j].key){if(Hash(ht.elem[j].key==i)printf(ht.elem[j].key);j=(j+1)%m;}}}//PrintWord2.intSearch_Bin_Recursive(SSTableST,intkey,intlow,inthigh)//折半查找的遞歸算法{if(low>high)return-1;//查找不到時(shí)返回-1mid=(low+high)/2;if(ST.elem[mid].key==key)returnmid;elseif(ST.elem[mid].key>key)returnSearch_Bin_Recursive(ST,key,low,mid-1);elsereturnSearch_Bin_Recursive(ST,key,mid+1,high);}}//Search_Bin_Recursive3.intSearch_Bin_Recursive(SSTableST,intkey,intlow,inthigh)//折半查找的遞歸算法{if(low>high)return0;//查找不到時(shí)返回0mid=(low+high)/2;if(ST.elem[mid].key==key)returnmid;elseif(ST.elem[mid].key>key)returnSearch_Bin_Recursive(ST,key,low,mid-1);elsereturnSearch_Bin_Recursive(ST,key,mid+1,high);}//Search_Bin_Recursive第8章習(xí)題參考答案一、選擇題一、選擇題1.B2.D3.A4.C5.C6.C7.B8.D9.C10.D11.A二、填空題1.比較、移動(dòng) 2.插入、選擇3.log2nHQCYAPMSDRFX 4.堆排序、快速排序5.直接插入,選擇排序 6.快速歸并7.歸并排序快速排序 8.69.HCQPAMSRDFXY PACSQDFXRHMY三、簡(jiǎn)答題1.直接選擇排序：(方括號(hào)為無(wú)序區(qū))初始態(tài)[265301751129937863742694076438]第一趟：076[301751129937863742694265438]第二趟：076129[751301937863742694265438]第三趟：076129265[301937863742694751438]第四趟：076129265301[937863742694751438]第五趟：076129265301438[863742694751937]第六趟：076129265301438694[742863751937]第七趟：076129265301438694742[863751937]第八趟：076129265301438694742751[863937]第九趟：0761292653014386947427518639372.冒泡排序(方括號(hào)為無(wú)序區(qū))初始態(tài)：[265301751129937863742694076438]第一趟：[265301129751863742694076438]937第二趟：[265129301751742694076438]863937第三趟：[129265301742694076438]751863937第四趟：[129265301694076438]742751863937第五趟：[129265301076438]694742751863937第六趟：[129265076301]438694742751863937第七趟：[129076265]301438694742751863937第八趟：[076129]265301438694742751863937第九趟：[076]1292653014386947427518639373.劃分次序劃分結(jié)果初始態(tài)4679563840809524第一次[244038]46[56809579]第二次24[3840]46[56809579]第三次24384046[56809579]第四次2438404656[809579]第五次243840465679[8095]第六次24384046567980954.歸并排序（為了表示方便，采用自底向上的歸并，方括號(hào)為有序區(qū)）初始態(tài)：[265][301][751][129][937][863][742][694][076][438]第一趟：[265301][129751][863937][694742][076438]第二趟：[129265301751][694742863937][076438]第三趟：[129265301694742751863937][076438]第四趟：[076129265301438694742751863937]5.直接插入排序:(方括號(hào)表示無(wú)序區(qū))初始態(tài):265[301751129937863742694076438]第一趟：265301[751129937863742694076438]第二趟：265301751[129937863742694076438]第三趟：129265301751[937863742694076438]第四趟：129265301751937[863742694076438]第五趟：129265301751863937[742694076438]第六趟：129265301742751863937[694076438]第七趟：129265301694742751863937[076438]第八趟：076129265301694742751863937[438]第九趟：076129265301438694742751863937

6.7.二叉排序樹或者是一棵空樹,或者是具有如下性質(zhì)的二叉樹:(1)若它的左子樹不空,則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；(2)若它的右子樹不空,則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；(3)左右子樹又各是一棵二義排序樹。8.解答：堆的性質(zhì)是：任一非葉結(jié)點(diǎn)上的關(guān)鍵字均不大于(或不小于)其孩子結(jié)點(diǎn)上的關(guān)鍵字。據(jù)此我們可以通過(guò)畫二叉樹來(lái)進(jìn)行判斷和調(diào)整：(1)此序列不是堆，經(jīng)調(diào)整后成為大根堆：(100，86，73，66，39，42，57，35，21)(2)此序列不是堆，經(jīng)調(diào)整后成為小根堆：(12，24，33，65，33，56，48，92，86，70)9.希爾排序(增量為5，3，1)初始態(tài):