數(shù)據(jù)結構第章習題答案-在線瀏覽
2025-07-25 19:56本頁面
【正文】 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 1 2 34 6 5（ D ）10. 已知圖的鄰接表如下所示，根據(jù)算法，則從頂點0出發(fā)按深度優(yōu)先遍歷的結點序列是A．0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3（ A ）11. 已知圖的鄰接表如下所示，根據(jù)算法，則從頂點0出發(fā)按廣度優(yōu)先遍歷的結點序列是A．0 3 2 1 B. 0 1 2 3 C. 0 1 3 2 D. 0 3 1 2（ A ）12. 深度優(yōu)先遍歷類似于二叉樹的A．先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 層次遍歷（ D ）13. 廣度優(yōu)先遍歷類似于二叉樹的A．先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 層次遍歷（ A ）14. 任何一個無向連通圖的最小生成樹A．只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在（注，生成樹不唯一，但最小生成樹唯一，即邊權之和或樹權最小的情況唯一）二、填空題（每空1分，共20分）1. 圖有 鄰接矩陣 、 鄰接表 等存儲結構，遍歷圖有 深度優(yōu)先遍歷 、 廣度優(yōu)先遍歷 等方法。3. 如果n個頂點的圖是一個環(huán)，則它有 n 棵生成樹。5. n個頂點e條邊的圖，若采用鄰接表存儲，則空間復雜度為 O(n+e) 。7. 設有一稠密圖G，則G采用 鄰接矩陣 存儲較省空間。9. 已知一個圖的鄰接矩陣表示，刪除所有從第i個頂點出發(fā)的方法是 將鄰接矩陣的第i行全部置0 。11. n個頂點e條邊的圖采用鄰接矩陣存儲，深度優(yōu)先遍歷算法的時間復雜度為 O(n2) ；若采用鄰接表存儲時，該算法的時間復雜度為 O(n+e) 。13. 圖的BFS生成樹的樹高比DFS生成樹的樹高 小或相等 。15. 若要求一個稀疏圖G的最小生成樹，最好用 克魯斯卡爾(Kruskal) 算法來求解。17. 用Dijkstra算法求某一頂點到其余各頂點間的最短路徑是按路徑長度 遞增 的次序來得到最短路徑的。三、簡答題（每題6分，共24分）1. 【①】已知如圖所示的有向圖，請給出該圖的:頂點123456入度出度（1） 每個頂點的入/出度；（2） 鄰接矩陣；（3） 鄰接表；（4） 逆鄰接表。 解：設起點為a。3. 【②】已知二維數(shù)組表示的圖的鄰接矩陣如下圖所示。4. 【②】試利用Dijkstra算法求圖中從頂點a到其他各頂點間的最短路徑，寫出執(zhí)行算法過程中各步的狀態(tài)。A B———————C E————F G————D解：1. 最小生成樹可直接畫出，如右圖所示。 //有向/無向圖，有向/無向網(wǎng)Typedef struct ArcCell{ //?。ㄟ叄┙Y點的定義 VRType adj。 //該弧相關信息的指針}ArcCell, AdjMatrix [ MAX_VERTEX_NUM ] [MAX_VERTEX_NUM ]。 //頂點表，用一維向量即可AdjMatrix arcs。 //頂點總數(shù)（7），?。ㄟ叄┛倲?shù)（9）GraphKind kind。
教學教案相關推薦
鄂ICP備17016276號-1