數(shù)據(jù)結(jié)構(gòu)(c語言版)習(xí)題指導(dǎo)與解答-wenkub.com
2025-03-23 00:52 本頁面
【正文】 4 （1）.散列地址0123456789關(guān)鍵字140192384275520比較次數(shù)1112 3 412平均查找長度：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次。該方法不易產(chǎn)生“聚集”，但增加了計算時間。b．di =12，12，22，22，… ，177。 } } }習(xí)題八解答填空題（1）主關(guān)鍵字（2）3（4）(1)哈希函數(shù)(2)解決沖突的方法 (3)選擇好的哈希函數(shù) (4)處理沖突的方法 (5)均勻(6)簡單（5）AVL樹（高度平衡樹，高度平衡的二叉排序樹），或為空二叉樹，或二叉樹中任意結(jié)點左子樹高度與右子樹高度差的絕對值小于等于1。 p2adjlist=I。i。for (i=0。}(5)在有向圖中，若鄰接表中頂點vi有鄰接點vj，在逆鄰接表中vj一定有鄰接點vi，由此得到本題算法思路：首先將逆鄰接表的表頭結(jié)點firstedge域置空，然后逐行將表頭結(jié)點的鄰接點進(jìn)行轉(zhuǎn)化。 j++) if (arcs[j][i]!=0) { flag=1。 i。因此，當(dāng)某列非零元素的個數(shù)為零時，則對應(yīng)頂點的入度為零。 break。 i++) { flag=0。據(jù)此，從第一行開始，查找每行的非零元素個數(shù)是否為零，若是則計數(shù)器加1。 a[i][j]=1。for (i=0。 i 。G, AdjList amp。 [i].firstedge=p。 ji。 i++)[i].firstedge=NULL。A){ =。int vertexNum, arcNum。template struct VertexNode //定義頂點表結(jié)點{T vertex。鄰接表存儲結(jié)構(gòu)定義如下：const int MaxSize=10。template struct AdjMatrix{ T vertex[MaxSize]。（2）鄰接矩陣表示如下：鄰接表表示如下： 各頂點的度：TD(v1)=3 TD(v2)=4 TD(v3)=2 TD(v4)=4 TD(v5)=3 TD(v6)=2深度優(yōu)先遍歷序列為：v1 v2 v3 v5 v4 v6廣度優(yōu)先遍歷序列為：v1 v2 v4 v6 v3 v5（3）按Prim算法求最小生成樹的過程如下：按Kruskal算法求最小生成樹的過程如下：（4）拓?fù)湫蛄袨椋簐0 v1 v5 v2 v3 v6 v v0 v1 v5 v2 v6 v3 v v0 v1 v5 v6 v2 v3 vv0 v5 v1 v2 v3 v6 v v0 v5 v1 v2 v6 v3 vv0 v5 v1 v6 v2 v3 v v1 v0 v5 v2 v3 v6 vv1 v0 v5 v2 v6 v3 v v1 v0 v5 v6 v2 v3 vv1 v5 v0 v2 v3 v6 v v1 v5 v0 v2 v6 v3 v v1 v5 v0 v6 v2 v3 vv5 v0 v1 v2 v3 v6 vv5 v0 v1 v2 v6 v3 vv5 v0 v1 v6 v2 v3 vv5 v1 v0 v2 v3 v6 v v5 v1 v0 v2 v6 v3 v v5 v1 v0 v6 v2 v3 v4（5）所有事件的最早發(fā)生時間ve[k]： ve (1)=0 ve (2)=3 ve (3)= max{ve(1)+2,ve(2)+6,ve(4)+2}=9 ve (4)=5 ve (5)=max{ve(2)+5,ve(3)+8}=17 ve (6)= max{ve(3)+4,ve(4)+8}=13 ve (7)=max{ve(3)+9,ve(5)+8,ve(6)+7}=25 所有事件的最晚發(fā)生時間vl[k]： vl (7)= ve(7) =25 vl (6)= vl (7)7=18 vl (5)= vl (7) 8=17 vl (4)= min{ vl (3)2, vl (6)8}=7 vl (3)=min{ vl (7)9, vl (5)8, vl (6)4}=9 vl (2)=min{ vl (5)5, vl (3)6}=3 vl (1)= min{ vl (4)5, vl (3)2, vl (2)3}=0 所有活動ai的最早開始時間e[i]和最晚開始時間l[i]： 活動a1 e (1)=ve (1)=0 l (1)=vl (2) 3 =0 活動a2 e (2)=ve (1)=0 l (2)=vl (3) 2=7 活動a3 e (3)=ve (2)=0 l (3)=vl (4) 5=2 活動a4 e (4)=ve (2)=3 l (4)=vl (5) 5=12 活動a5 e (5)=ve (3)=3 l (5)=vl (3) 6=3 活動a6 e (6)=ve (3)=5 l (6)=vl (3) 2=7 活動a7 e (7)=ve (4)=5 l (7)=vl (6) 8=10 活動a8 e (8)=ve (5)=9 l (8)=vl (5) 8=9 活動a9 e (9)=ve (5)=9 l (9)=vl (7) 9=16 活動a10 e (10)=ve (6)=9 l (10)=vl (6) 4=14 活動a11 e (11)=ve (7)=17 l (11)=vl (7) 8=17 活動a12 e (12)=ve (8)=13 l (12)=vl (7) 7=18 最后，比較e[i]和l[i]的值可判斷出a1,a5,a8,a11這些活動的e[i]和l[i]的值相等，沒有時間余量，所以它們是關(guān)鍵活動，關(guān)鍵路徑如下圖所示。⑶ 計算鄰接矩陣上該頂點對應(yīng)的行上非零元素的個數(shù)。⑹錯。⑷錯。⑵對。⑷D n個頂點的無向圖中，邊數(shù)e≤n(n1)/2，將e=41，有n≥9，現(xiàn)已知無向圖非連通，則n=10。⑵鄰接矩陣，鄰接表 這是最常用的兩種存儲結(jié)構(gòu)，此外，還有十字鏈表、鄰接多重表等。 else /*左子樹非空*/ { if(prtag==0) /*右子樹非空，右孩子就是前驅(qū)*/ q=prchild。 else /*右子樹非空*/ { if(pltag==0) /*左子樹非空，左孩子就是后繼*/ q=plchild； if(pltag==1) /*左子樹為空，右孩子就是后繼*/ q=prchild。 else Q[++rear]=prchild。 if (prchild) b=0。while (front!=rear amp。bool ComBiTree(BiNode *root){ front=rear=1。 else { p=root。 } } ⑹對二叉鏈表進(jìn)行遍歷，在遍歷的過程中查找結(jié)點a并記載其雙親，然后將結(jié)點x的雙親結(jié)點中指向結(jié)點x的指針置空。具體算法如下： void Exchange(BiNode *root){ if (root) { Exchange(rootlchild)。注意和前序遍歷的區(qū)別，具體算法如下：void PostPrder(BiNode *root){ if (root) { printf(“%d “,rootdata)。 else { Dl=Dep th(rootlchild)。 printleaf(rootlchild)。為此，將前序遍歷算法中的訪問操作改為條件打印即可。 n++。3） 由2）得單支結(jié)點數(shù)為14） 對于n個結(jié)點的完全二叉樹，最后一個樹葉結(jié)點，即序號為n的葉結(jié)點其雙親結(jié)點，即為最后一個非終端結(jié)點，序號為892/2=446。(11)C 因為有n+1個空鏈
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1