數據結構（C語言版）（第三版）（微課版） 習題參考答案 梁海英 第6-8章

?PAGE294?數據結構(C語言)微課版?PAGE293?附錄習題參考答案附錄習題參考答案第6章習題參考答案一、選擇題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.有向將鄰接矩陣的第i行全部置06.鄰接表鄰接矩陣7.出度n 8.O(n2),O(n+e)9.n,2e 10.克魯斯卡爾(Kruskal)普里姆(Prim)11.O(n2)O(n+e) 12.某一頂點遞增13.出度入度 14.相等權15.O(n2)、O(n+e) 16.O(n2)、O(n+e)三、判斷題1.×2.×3.×4.×5.√6.×7.√8.√9.×10.√11.×四、簡答題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.根據克魯斯卡爾算法思想畫圖表示最小生成樹的生成過程如下：5.(1)是有向圖，因為其鄰接矩陣是不對稱的(2)頂點1的入度為1，出度為2頂點2的入度為2，出度為2頂點3的入度為1，出度為2頂點4的入度為3，出度為26.頂點1的入度為2，出度為2頂點2的入度為2，出度為2頂點3的入度為2，出度為1頂點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)先搜索頂點序列：1-2-3-4-5-6邊的序列：（1，2）（2，3）（3，4）（4，5）（5，6）（2）廣度優(yōu)先搜索頂點序列：1-2-3-6-5-4邊的序列：（1，2）（1，3）（1，6）（1，5）（5，4）注：本題中所求深度優(yōu)先序列和廣度優(yōu)先序列有多種，以上為其中一種。10.(1)頂點1的入度為3，出度為0頂點2的入度為2，出度為2頂點3的入度為1，出度為2頂點4的入度為1，出度為3頂點5的入度為2，出度為1頂點6的入度為2，出度為3(2)鄰接矩陣為：(3)鄰接表為：(4)逆鄰接表為：11.(1)鄰接矩陣為：(2)鄰接表為：12.解答：根據普里姆算法的基本思想，構造最小生成樹，在此，由于邊的權值出現了相同值，因此，在構造實際的最小生成樹時結果是不唯一的，下圖給出了其中的一種構造過程：13.解：(1)最小生成樹可直接畫出，如下圖所示。(2)可用鄰接矩陣和鄰接表來描述：14.拓撲序列為：140257368915.解：終點vi從a頂點出發(fā)到其余各頂點的最短路徑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.求頂點0其余各頂點的最短路徑終點vi從0頂點出發(fā)到其余各頂點的最短路徑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./*利用鄰接矩陣實現圖的遍歷*//*從第i個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖G*/voidDFS(GraphG,inti){intj;printf("%3c",G.V[i]); /*訪問第i個頂點*/visited[i]=1;for(j=0;j<G.n;j++)if((G.arcs[i][j]==1)&&(visited[j]==0))DFS(G,j); /*對頂點i的尚未訪問的鄰接頂點j遞歸調用DFS*/}/*【算法6.10對圖G進行深度優(yōu)先遍歷】*/2./*【算法6.13用鄰接表實現圖的廣度優(yōu)先搜索遍歷】*/voidBFS(ALGraphG,intk){inti;ArcNode*p;InitQueue(&Q); /*初始化隊列*/printf("%3c",G.adjList[k].data); /*訪問第k個頂點*/visited[k]=1; EnQueue(&Q,k); /*第k個頂點進隊*/while(!QueueEmpty(&Q)){ /*隊列非空*/DelQueue(&Q,&i);p=G.adjList[i].firstArc; /*獲取第1個鄰接點*/while(p!=NULL){if(visited[p->adjVex]==0) /*訪問第i個頂點的末曾訪問的鄰接頂點*/{printf("%3c",G.adjList[p->adjVex].data);visited[p->adjVex]=1;EnQueue(&Q,p->adjVex); /*第k個頂點進隊*/}p=p->nextArc;} }}3.intvisited[MAXSIZE];//指示頂點是否在當前路徑上intlevel＝1;//遞歸進行的層數intexist_path_DFS(ALGraphG,inti,intj)//深度優(yōu)先判斷有向圖G中頂點i到頂點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下游的頂點到j有路徑}//for}//elseif(level==1)return0;}//exist_path_DFS4.intvisited[MAXSIZE];intexist_path_len(ALGraphG,inti,intj,intk)//判斷鄰接表方式存儲的有向圖G的頂點i到j是否存在長度為k的簡單路徑{if(i==j&&k==0)return1;//找到了一條路徑,且長度符合要求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;//剩余路徑長度減一}//forvisited[i]=0;//本題允許曾經被訪問過的結點出現在另一條路徑中}//elsereturn0;//沒找到}//exist_path_len5.解：//本題中的圖G均為有向無權圖。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章習題參考答案一、選擇題1.B2.A3.A4.C5.C6.A7.C8.B9.A二、填空題1.散列法關鍵字 2.253.構造一個好的HASH函數確定解決沖突的方法 4.975.順序查找（線性查找）28，6，12，20 6.7/68/67.1,3三、簡答題1.(1)查找不成功時，需進行n+1次比較才能確定查找失敗。因此平均查找長度為n+1，這時有序表和無序表是一樣的。(2)查找成功時，平均查找長度為(n+1)/2,有序表和無序表也是一樣的。因為順序查找與表的初始序列狀態(tài)無關。2.n的查找過程如下(其中方括號表示當前查找區(qū)間，圓括號表示當前比較的關鍵字)下標：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]經過四次比較，查找失敗。3.解答：查找b的過程如下(其中方括號表示當前查找區(qū)間，圓括號表示當前比較的關鍵字)下標：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經過三次比較，查找成功。

4.5.(1)判定樹如下（注：mid=?(1+12)/2?=6）：(2)查找元素54，需依次與30,63,42,54等元素比較；(3)查找元素90，需依次與30,63,87,95等元素比較；(4)求ASL之前，需要統(tǒng)計每個元素的查找次數。判定樹的前3層共查找1＋2×2＋4×3=17次；但最后一層未滿，不能用8×4，只能用5×4=20次，所以ASL＝1/12（17＋20）＝37/12≈3.086.不適合！雖然有序的單鏈表的結點是按從小到大（或從大到小）順序排列，但因其存儲結構為單鏈表，查找結點時只能從頭指針開始逐步搜索，故不能進行折半查找。二分查找的速度在一般情況下是快些，但在特殊情況下未必快。例如所查數據位于首位時，則線性查找快；而二分查找則慢得多。7.解答：根據哈希函數和處理沖突的方法為二次探測再散列，構造哈希表如圖所示：8.查找某個元素的時間復雜度下限，如果理解為最短查找時間，則當關鍵字值與表頭元素相同時，比較1次即可。要想降低時間復雜度，可以改用Hash查找法。此方法對表內每個元素的比較次數都是O（1）。9.判定樹應當描述每次查找的位置：10解：由題意知，m=11(剛好為素數)則(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.等概率情況下，查找成功的平均查找長度為：ASL=(1+2*2+3*4+4*8+5*3)/18=3.556

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

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