數(shù)據(jù)結(jié)構(gòu)第章習(xí)題答案-展示頁(yè)
2025-06-16 19:56本頁(yè)面
【正文】 d—4—h (a,b,c) (e,f,g) (d,h) 取b—5—d, g—5d 就把三個(gè)連通分量連接起來(lái)了。 答案： 2. 【②】請(qǐng)對(duì)下圖的無(wú)向帶權(quán)圖：（1） 寫(xiě)出它的鄰接矩陣，并按普里姆算法求其最小生成樹(shù)；（2） 寫(xiě)出它的鄰接表，并按克魯斯卡爾算法求其最小生成樹(shù)。18. 拓?fù)渑判蛩惴ㄊ峭ㄟ^(guò)重復(fù)選擇具有 0 個(gè)前驅(qū)頂點(diǎn)的過(guò)程來(lái)完成的。16. 若要求一個(gè)稠密圖G的最小生成樹(shù)，最好用 普里姆(Prim) 算法來(lái)求解。14. 用普里姆(Prim)算法求具有n個(gè)頂點(diǎn)e條邊的圖的最小生成樹(shù)的時(shí)間復(fù)雜度為 O(n2) ；用克魯斯卡爾(Kruskal)算法的時(shí)間復(fù)雜度是 O(elog2e) 。12. n個(gè)頂點(diǎn)e條邊的圖采用鄰接矩陣存儲(chǔ)，廣度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為 O(n2) ；若采用鄰接表存儲(chǔ)，該算法的時(shí)間復(fù)雜度為 O(n+e) 。10. 圖的深度優(yōu)先遍歷序列 不是 惟一的。8. 圖的逆鄰接表存儲(chǔ)結(jié)構(gòu)只適用于 有向 圖。6. 設(shè)有一稀疏圖G，則G采用 鄰接表 存儲(chǔ)較省空間。 （以任意一頂點(diǎn)為起點(diǎn)，得到n1條邊）4. n個(gè)頂點(diǎn)e條邊的圖，若采用鄰接矩陣存儲(chǔ)，則空間復(fù)雜度為 O(n2) 。2. 有向圖G用鄰接表矩陣存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)i的 出度 。A．棧 B. 隊(duì)列 C. 樹(shù) D. 圖 （ A ）7. 用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常是采用 來(lái)實(shí)現(xiàn)算法的。 A．5 B. 6 C. 7 D. 8 （ C ）5. 有8個(gè)結(jié)點(diǎn)的有向完全圖有 條邊。 A．1/2 B. 1 C. 2 D. 4 （ B ）3. 有8個(gè)結(jié)點(diǎn)的無(wú)向圖最多有 條邊。第7章 《圖》習(xí)題參考答案一、單選題（每題1分，共16分） （ C ）1. 在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的 倍。 A．1/2 B. 1 C. 2 D. 4 （ B ）2. 在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 倍。 A．14 B. 28 C. 56 D. 112 （ C ）4. 有8個(gè)結(jié)點(diǎn)的無(wú)向連通圖最少有 條邊。 A．14 B. 28 C. 56 D. 112 （ B ）6. 用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常是采用 來(lái)實(shí)現(xiàn)算法的。A．棧 B. 隊(duì)列 C. 樹(shù) D. 圖 A．0 2 4 3 1 5 6B. 0 1 3 6 5 4 2C. 0 1 3 4 2 5 6D. 0 3 6 1 5 4 2（ C ）8. 已知圖的鄰接矩陣，根據(jù)算法思想，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是（ D ）9. 已知圖的鄰接矩陣同上題8，根據(jù)算法，則從頂點(diǎn)0出發(fā)，按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是A． 0 2 4 3 1 5 6 B. 0
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1