數(shù)據(jù)結(jié)構(gòu)(c語言版)習(xí)題指導(dǎo)與解答-資料下載頁(yè)
2025-03-26 00:52本頁(yè)面
【正文】 ,V4) 30 (V0,V4) V5 100 (V0,V5) 100 (V0,V5) 90 (V0,V4,V5) 60 (V0,V4,V3,V5) Vj V2 V4 V3 V5 S {V0,V2} {V0,V2,V4}{V0,V2,V3,V4}{V0,V2,V3,V4,V5} 從源點(diǎn)v0到其他各頂點(diǎn)的最短路徑如下表所示。源點(diǎn) 終點(diǎn) 最短路徑 最短路徑長(zhǎng)度V0 V2 V0 V2 10V0 V4 V0 V4 30V0 V3 V0 V4 V3 50V0 V5 V0 V4 V3 V5 60V0 V1 無 ∞5．算法設(shè)計(jì)⑴先設(shè)置一個(gè)空的鄰接表，然后在鄰接矩陣上查找值不為零的元素，找到后在鄰接表的對(duì)應(yīng)單鏈表中插入相應(yīng)的邊表結(jié)點(diǎn)。鄰接矩陣存儲(chǔ)結(jié)構(gòu)定義如下：const int MaxSize=10。template struct AdjMatrix{ T vertex[MaxSize]。 //存放圖中頂點(diǎn)的數(shù)組int arc[MaxSize][MaxSize]。 //存放圖中邊的數(shù)組int vertexNum, arcNum。 //圖的頂點(diǎn)數(shù)和邊數(shù)}。鄰接表存儲(chǔ)結(jié)構(gòu)定義如下：const int MaxSize=10。struct ArcNode //定義邊表結(jié)點(diǎn){int adjvex。 //鄰接點(diǎn)域ArcNode *next。}。template struct VertexNode //定義頂點(diǎn)表結(jié)點(diǎn){T vertex。ArcNode *firstedge。}。struct AdjList{VertexNode adjlist[MaxSize]。int vertexNum, arcNum。 //圖的頂點(diǎn)數(shù)和邊數(shù)}。具體算法如下：void MatToList(AdjMatrix amp。G, AdjList amp。A){ =。=。for (i=0。 i 。 i++)[i].firstedge=NULL。for (i=0。 i 。 i++) for (j=0。 ji。 j++) if ([i][j]!=0) { p=new ArcNode。 padjvex=j。 pnext=[i].firstedge。 [i].firstedge=p。 } }⑵在鄰接表上順序地取每個(gè)邊表中的結(jié)點(diǎn)，將鄰接矩陣中對(duì)應(yīng)單元的值置為1。鄰接矩陣和鄰接表的存儲(chǔ)結(jié)構(gòu)定義與上題相同。具體算法如下：void ListToMat(AdjMatrix amp。G, AdjList amp。A){ =。=。for (i=0。 i 。 i++) for (j=0。j 。 j++) [i][j]=0。for (i=0。 i 。 i++) { p=[i].firstedge。while(p) { j=padjvex。 a[i][j]=1。 p=pnext。 }}}⑶在有向圖的鄰接矩陣中，一行對(duì)應(yīng)一個(gè)頂點(diǎn)，每行的非零元素的個(gè)數(shù)等于對(duì)應(yīng)頂點(diǎn)的出度。因此，當(dāng)某行非零元素的個(gè)數(shù)為零時(shí)，則對(duì)應(yīng)頂點(diǎn)的出度為零。據(jù)此，從第一行開始，查找每行的非零元素個(gè)數(shù)是否為零，若是則計(jì)數(shù)器加1。具體算法如下：int CountODZero(AdiMatrix G){ count=0。 for (i=0。 i。 i++) { flag=0。 for (j=0。 j 。 j++) if (arcs[i][j]!=0) { flag=1。 break。 } if (flag==0) count++。 }return count。}⑷在有向圖的鄰接矩陣中，一列對(duì)應(yīng)一個(gè)頂點(diǎn)，每列的非零元素的個(gè)數(shù)等于對(duì)應(yīng)頂點(diǎn)的入度。因此，當(dāng)某列非零元素的個(gè)數(shù)為零時(shí)，則對(duì)應(yīng)頂點(diǎn)的入度為零。據(jù)此，從第一列開始，查找每列的非零元素個(gè)數(shù)是否為零，若是則計(jì)數(shù)器加1。具體算法如下：int CountIDZero(AdiMatrix G){ count=0。 for (i=0。 i。 i++) { flag=0。 for (j=0。 j 。 j++) if (arcs[j][i]!=0) { flag=1。 break。 } if (flag==0) count++。 }return count。}(5)在有向圖中，若鄰接表中頂點(diǎn)vi有鄰接點(diǎn)vj，在逆鄰接表中vj一定有鄰接點(diǎn)vi，由此得到本題算法思路：首先將逆鄰接表的表頭結(jié)點(diǎn)firstedge域置空，然后逐行將表頭結(jié)點(diǎn)的鄰接點(diǎn)進(jìn)行轉(zhuǎn)化。void NiList(AdjList G, AdjList amp。A){ =。=。for (i=0。 i。 i++)[i].firstedge=NULL。 for (i=0。i。 i++) { p1=[i].firstedge。 while (p1) { j=p1adjlist。 p2=new ArcNode。 p2adjlist=I。 p2next=[j].firstedge。[j].firstedge=p2。p1=p1next。 } } }習(xí)題八解答填空題（1）主關(guān)鍵字（2）3（4）(1)哈希函數(shù)(2)解決沖突的方法 (3)選擇好的哈希函數(shù) (4)處理沖突的方法 (5)均勻(6)簡(jiǎn)單（5）AVL樹（高度平衡樹，高度平衡的二叉排序樹），或?yàn)榭斩鏄洌蚨鏄渲腥我饨Y(jié)點(diǎn)左子樹高度與右子樹高度差的絕對(duì)值小于等于1。（6）比數(shù)據(jù)元素個(gè)數(shù)稍大的質(zhì)數(shù) （7）235。㏒2n」+1（8）k(k+1)/2（9）(1)順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ) (2)順序存儲(chǔ)且有序 (3)塊間有序 (4) 散列存儲(chǔ)（10）結(jié)點(diǎn)的左子樹的高度減去結(jié)點(diǎn)的右子樹的高度（11）直接定址法（12）54 計(jì)算公式：A(n+2)=A(n+1)+A(n)+1（14）4選擇題（1）C（2）D（3）C（4）D（5）C（6）C（8）C（9）D（10）D、C（11）B（12）D、C3．(1)散列表存儲(chǔ)的基本思想是用關(guān)鍵字的值決定數(shù)據(jù)元素的存儲(chǔ)地址（2）散列表存儲(chǔ)中解決沖突的基本方法：（1）開放定址法 形成地址序列的公式是：Hi=（H（key）+di）% m，其中m是表長(zhǎng)，di是增量。根據(jù)di取法不同，又分為三種：a．di =1，2，…，m1 稱為線性探測(cè)再散列，其特點(diǎn)是逐個(gè)探測(cè)表空間，只要散列表中有空閑空間，就可解決碰撞，缺點(diǎn)是容易造成“聚集”，即不是同義詞的關(guān)鍵字爭(zhēng)奪同一散列地址。b．di =12，12，22，22，… ，177。k2（k≤m/2） 稱為二次探測(cè)再散列，它減少了聚集，但不容易探測(cè)到全部表空間，只有當(dāng)表長(zhǎng)為形如4j+3（j為整數(shù)）的素?cái)?shù)時(shí)才有可能。c．di =偽隨機(jī)數(shù)序列，稱為隨機(jī)探測(cè)再散列。（2）二次探測(cè)再散列法 Hi=RHi（key） i=1，2，…，k，是不同的散列函數(shù)，即在同義詞產(chǎn)生碰撞時(shí)，用另一散列函數(shù)計(jì)算散列地址，直到解決碰撞。該方法不易產(chǎn)生“聚集”，但增加了計(jì)算時(shí)間。（3）鏈表法 將關(guān)鍵字為同義詞的記錄存儲(chǔ)在同一鏈表中，散列表地址區(qū)間用H[0..m1]表示，分量初始值為空指針。凡散列地址為i（0≤i≤m1）的記錄均插在以H[i]為頭指針的鏈表中。這種解決方法中數(shù)據(jù)元素個(gè)數(shù)不受表長(zhǎng)限制，插入和刪除操作方便，但增加了指針的空間開銷。4 （1）.散列地址0123456789關(guān)鍵字140192384275520比較次數(shù)1112 3 412平均查找長(zhǎng)度：ASLsucc=（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+32）%10=5 所以比較了4次。（2）散列地址0123456789101112關(guān)鍵字13225314167465130比較次數(shù)111212111裝填因子=9/13= （4）ASLsucc=（1+2*2+3*3+4*2+5*2）/10=32/10（5）1）2）10,12,15,20,24,28,30,35,46,50,55,683） ASLsucc=（1+2*2+3*4+4*5）/12=37/12習(xí)題九解答填空題（1）n1，nj（2）n1（3）4,8（4）冒泡排序，快速排序（5）希爾排序、快速排序、堆排序（6）插入排序，選擇排序（7）堆排序，快速排序，歸并排序，歸并排序，快速排序，堆排序（8）快速排序，歸并排序選擇題（1）C（2）A（3）C（4）C（5）D（6）C（7）A（8）D（9）C（10）D
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1