數(shù)據(jù)結(jié)構(gòu)(c語言版)習(xí)題解答-資料下載頁
2025-08-05 07:30本頁面
【正文】 。T2==Null) return 1。else if(T1==Null || T2==Null) return 0。 else return (BiTreeSilimar(T1lchild,T2lchild)amp。amp。BiTreeSimilar(T1rchild,T2rchild))。} 寫出統(tǒng)計樹中葉子結(jié)點個數(shù)的算法，樹用孩子兄弟鏈表表示。思路：在孩子兄弟鏈表中，若結(jié)點的firstchild為Null，則為葉子結(jié)點；采用遞歸方法。 int CountLeaves(Tree T，int amp。num)//num傳遞的初值為0{ if(Tnextsibling!=Null) num+=CountLeaves (Tnextsibling)。 if(Tfirstchild!=Null) num+=CountLeaves(T firstchild)。 else num+=1。//firstchild域為空，則為葉子結(jié)點return num。}圖71V5V4V2V3V1V6第七章 圖 已知有向圖如圖71所示，請給出該圖的 (1)鄰接矩陣示意圖 (2)鄰接表示意圖 (3)逆鄰接表 (4)所有強連通分量(1) 鄰接矩陣 （2）鄰接表 （3）逆鄰接表V5V4V2V3V1V6 （4）強連通分量 已知圖G的鄰接矩陣如圖72所示。寫出該圖從頂點1出發(fā)的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列，并畫出相應(yīng)的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。12345678910100000010102001000100030001000100400001000105000001000161100000000700100000018100100001090000101001101000010000圖72深度優(yōu)先序列：1 7 3 4 5 6 2 10 9 8深度優(yōu)先生成樹：廣度優(yōu)先序列：1 7 9 3 10 5 4 8 6 2廣度優(yōu)先生成樹：，試在下列三種情況下分別討論兩者在等概率時平均查找長度是否相同？（1）查找不成功，即表中沒有關(guān)鍵字等于給定的值K的記錄；（2）查找成功，且表中只有一個關(guān)鍵字等于給定值K的記錄；（3）查找成功，且表中有若干個關(guān)鍵字等于給定值K的記錄，要求找出所有這些記錄。解：對有序順序表：1. （將該項看作一項混入原有序列中，問題轉(zhuǎn)變成 n+1個元素序列的成功查找問題）2． 3. 將此K項看作一項對無序順序表：1. n2.3. 考慮最后一個記錄的出現(xiàn)位置 畫出對長度為17的有序表進行折半查找的判定樹，并分別求其等概率時查找長度和查找失敗的ASL。解： 增加虛結(jié)點：（Jan，F(xiàn)eb，Mar，Apr，May，Jun，July，Aug，Sept，Oct，Nov，Dec）表中，每一個元素的查找概率分別為：（, , , , , , , , , , , ）（1）若對該表進行順序查找，求查找成功的平均查找長度；（2）畫出從初態(tài)為空開始，依次插入結(jié)點，生成的二叉排序樹；（3）計算該二叉排序樹查找成功的平均查找長度；（4）將二叉排序樹中的結(jié)點Mar刪除，畫出經(jīng)過刪除處理后的二叉排序樹。解：（1） （2）與初始輸入序列有關(guān) （3） （4）找到Mar的直接后繼，將Mar的左子樹移動到最左孩子的左孩子處，然后用直接后繼取代當(dāng)前結(jié)點。 已知關(guān)鍵字序列{10，25，33，19，06，49，37，76，60}，哈希地址空間為010，哈希函數(shù)為H(key)=Key%11，求：（1）用開放定址線性探測法處理沖突，構(gòu)造哈希表HT1，分別計算在等概率情況下HT1查找成功和查找失敗的ASL；（2）用開放定址二次探測法處理沖突，構(gòu)造哈希表HT2，計算在等概率下HT2查找成功的ASL；（3）用拉鏈法解決沖突，構(gòu)造哈希表HT3，計算HT3在等概率情況查找成功的ASL。解：這9個數(shù)的hash值為： 10,3,0,8,6,5,4,10,5沖突有2個。012345678910337625374906601910 遇到空還沒有，則算失敗。（2）d=0,1,1,4,4……0123456789103360254906197610(3)
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1