數(shù)據(jù)結(jié)構(gòu)(c語言版)習(xí)題指導(dǎo)與解答(參考版)
2025-03-29 00:52本頁面
【正文】 （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。這種解決方法中數(shù)據(jù)元素個(gè)數(shù)不受表長限制，插入和刪除操作方便，但增加了指針的空間開銷。（3）鏈表法 將關(guān)鍵字為同義詞的記錄存儲在同一鏈表中，散列表地址區(qū)間用H[0..m1]表示，分量初始值為空指針。（2）二次探測再散列法 Hi=RHi（key） i=1，2，…，k，是不同的散列函數(shù)，即在同義詞產(chǎn)生碰撞時(shí)，用另一散列函數(shù)計(jì)算散列地址，直到解決碰撞。k2（k≤m/2） 稱為二次探測再散列，它減少了聚集，但不容易探測到全部表空間，只有當(dāng)表長為形如4j+3（j為整數(shù)）的素?cái)?shù)時(shí)才有可能。根據(jù)di取法不同，又分為三種：a．di =1，2，…，m1 稱為線性探測再散列，其特點(diǎn)是逐個(gè)探測表空間，只要散列表中有空閑空間，就可解決碰撞，缺點(diǎn)是容易造成“聚集”，即不是同義詞的關(guān)鍵字爭奪同一散列地址。（6）比數(shù)據(jù)元素個(gè)數(shù)稍大的質(zhì)數(shù) （7）235。p1=p1next。 p2next=[j].firstedge。 p2=new ArcNode。 i++) { p1=[i].firstedge。 for (i=0。 i。=。void NiList(AdjList G, AdjList amp。 }return count。 break。 j 。 i++) { flag=0。 for (i=0。據(jù)此，從第一列開始，查找每列的非零元素個(gè)數(shù)是否為零，若是則計(jì)數(shù)器加1。}⑷在有向圖的鄰接矩陣中，一列對應(yīng)一個(gè)頂點(diǎn)，每列的非零元素的個(gè)數(shù)等于對應(yīng)頂點(diǎn)的入度。 } if (flag==0) count++。 j++) if (arcs[i][j]!=0) { flag=1。 for (j=0。 i。具體算法如下：int CountODZero(AdiMatrix G){ count=0。因此，當(dāng)某行非零元素的個(gè)數(shù)為零時(shí)，則對應(yīng)頂點(diǎn)的出度為零。 p=pnext。while(p) { j=padjvex。 i 。 j++) [i][j]=0。 i++) for (j=0。for (i=0。A){ =。具體算法如下：void ListToMat(AdjMatrix amp。 } }⑵在鄰接表上順序地取每個(gè)邊表中的結(jié)點(diǎn)，將鄰接矩陣中對應(yīng)單元的值置為1。 pnext=[i].firstedge。 j++) if ([i][j]!=0) { p=new ArcNode。 i++) for (j=0。for (i=0。 i 。=。G, AdjList amp。 //圖的頂點(diǎn)數(shù)和邊數(shù)}。struct AdjList{VertexNode adjlist[MaxSize]。ArcNode *firstedge。}。struct ArcNode //定義邊表結(jié)點(diǎn){int adjvex。 //圖的頂點(diǎn)數(shù)和邊數(shù)}。 //存放圖中頂點(diǎn)的數(shù)組int arc[MaxSize][MaxSize]。鄰接矩陣存儲結(jié)構(gòu)定義如下：const int MaxSize=10。v2v5 a1=3 a5= 6 a11=8v7v3v1 a8= 8 （6）注：從V0到其余點(diǎn)的最短路徑10060V5 ∞ ∞ 10 ∞ 30 100 ∞ ∞ 5 ∞ ∞ ∞30V4V0 ∞ ∞ ∞ 50 ∞ ∞201010 ∞ ∞ ∞ ∞ ∞ 10V3V1 ∞ ∞ ∞ 20 ∞ 60505V2 ∞ ∞ ∞ ∞ ∞ ∞終點(diǎn) 從V0到各終點(diǎn)的Dist值和最短路徑的求解過程 i=1 i=2 i=3 i=4 i=5 V1 ∞ ∞ ∞ ∞ ∞無 V2 10 (V0,V2) V3 ∞ 60 (V0,V2,V3) 50 (V0,V4,V3) V4 30 (V0,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)所對應(yīng)的邊表中所含結(jié)點(diǎn)個(gè)數(shù)。鄰接表：⑴ 邊表中的結(jié)點(diǎn)個(gè)數(shù)之和除以2。⑵ 當(dāng)鄰接矩陣A中A[i][j]=1（或A[j][i]=1）時(shí)，表示兩頂點(diǎn)之間有邊相連。只有在仍舊保持關(guān)鍵活動(dòng)所在路徑仍是關(guān)鍵路徑的前提下才可以。只能說明從頂點(diǎn)a到頂點(diǎn)b有一條路徑。只有連通圖從某頂點(diǎn)出發(fā)進(jìn)行一次遍歷，可訪問圖的所有頂點(diǎn)。有向圖的鄰接矩陣不一定不對稱，例如有向完全圖的鄰接矩陣就是對稱的。鄰接矩陣的空間復(fù)雜度為Ｏ(n2)，與邊的個(gè)數(shù)無關(guān)。鄰接表和逆鄰接表的區(qū)別僅在于出邊和入邊，邊表中的結(jié)點(diǎn)個(gè)數(shù)都等于有向圖中邊的個(gè)數(shù)。⑸D⑹D 當(dāng)有向圖中無回路時(shí)，從某頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷時(shí)，出棧的順序（退出DFSTraverse算法）即為逆向的拓?fù)湫蛄?。⑵D⑶C 若超過n1，則路徑中必存在重復(fù)的頂點(diǎn)。⑶Ｏ(n+e) 在無向圖的鄰接表中，頂點(diǎn)表有n個(gè)結(jié)點(diǎn)，邊表有2e個(gè)結(jié)點(diǎn)，共有n+2e個(gè)結(jié)點(diǎn)，其空間復(fù)雜度為Ｏ(n+2e)=Ｏ(n+e)。}習(xí)題七解答1. 填空題 ⑴0，n(n1)/2，0，n(n1) 圖的頂點(diǎn)集合是有窮非空的，而邊集可以是空集；邊數(shù)達(dá)到最多的圖稱為完全圖，在完全圖中，任意兩個(gè)頂點(diǎn)之間都存在邊。 if(prtag==1) /*右子樹為空，左孩子就是前驅(qū)*/ q=plchild。 if(pltag==1) /*左子樹為空，lchild 域指的就是前驅(qū)*/ q=plchild。 } return(q)。 if(prtag==1) /*右子樹為空，rchild 域指的就是后繼*/q=prchild。 } }} return b。 if (!prchild) a=0。 } else { b=a。 if (!plchild) { a=0。amp。 if (root) {Q[++rear]=root。 a=1。 } }}(7) 在一棵完全二叉樹中，若某結(jié)點(diǎn)無左孩子的話，那么它一定也沒有右孩子；若某結(jié)點(diǎn)沒有右孩子的話，那么按層序編號比它大的結(jié)點(diǎn)一定沒有孩子。 Delete(rootlchild,a)。 else prchild=NULL。具體算法如下：void Delete(BiNode *root, ElemType a){ if (root) { if (rootdata==a)
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1