數(shù)據(jù)結(jié)構(gòu)復習資料-資料下載頁
2025-06-07 19:56本頁面
【正文】 點都有k棵非空子樹。如果按層次順序從1開始對全部結(jié)點編號，問：(1)各層結(jié)點數(shù)目是多少？(2)編號為p的結(jié)點的父結(jié)點（若存在）的編號是多少？(3)編號為p的結(jié)點的第i個兒子結(jié)點（若存在）的編號是多少？(4)編號為p的結(jié)點有有右兄弟的條件是什么？其右兄弟的編號是多少？答案：(1)第i層有ki1個結(jié)點；(2)p=1時，該結(jié)點為根，無父結(jié)點；否則其父結(jié)點編號為（k=2）(3)其第k1個兒子的編號為pk。所以，如果他有兒子，則其第i個兒子的編號為pk+（i（k1））；(4)(p1)%k≠0時，該結(jié)點有右兄弟，其右兄弟的編號為p+1。第七章 圖復習要求：掌握圖的有關(guān)概念、存儲結(jié)構(gòu)、遍歷算法、生成樹的求法以及拓撲排序的概念及求法。復習內(nèi)容：(1) 圖的定義和術(shù)語(2) 圖的存儲結(jié)構(gòu)(3) 圖的遍歷(4) 圖的連通性問題(5) 有向無回圖及其應用(6) 最短路徑復習題：1. 對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應的鄰接表中，所含邊結(jié)點分別有___e___個和___2e__個。2. 設有6個結(jié)點的無向圖，該圖至少應有( A )條邊才能確保是一個連通圖。 1234563. 已知如右圖所示的有向圖，請給出該圖的(1) 每個頂點的入/出度；(2) 鄰接矩陣(3) 鄰接表(4) 逆鄰接表(5) 強連通分量答案：(1) 每個頂點的入/出度；頂點123456入度321122出度022313(2) 鄰接矩陣000000100100010001001011100000110010(3) 鄰接表(4) 逆鄰接表152346(5) 有3個強連通分量？答：鄰接矩陣：有向圖和無向圖鄰接表（逆鄰接表）：有向圖和無向圖十字鏈表：有向圖鄰接多重表：無向圖5. 已知一個圖的頂點集V和邊集E分別為：V={1,2,3,4,5,6,7}。E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}。用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。
答：用克魯斯卡爾算法得到的最小生成樹為：(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)206. AOV網(wǎng)是一種___有向無回路_的圖。
，(1) 寫出它的鄰接矩陣，并按普里姆算法求其最小生成樹；6412436213576555(2) 寫出它的鄰接表，并按克魯斯卡算法求其最小生成樹。8
教學教案相關(guān)推薦
鄂ICP備17016276號-1