數(shù)據(jù)結(jié)構(gòu)第章習(xí)題答案(已修改)
2025-06-19 19:56 本頁面
【正文】 第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．1/2 B. 1 C. 2 D. 4 （ B ）3. 有8個(gè)結(jié)點(diǎn)的無向圖最多有 條邊。 A．14 B. 28 C. 56 D. 112 （ C ）4. 有8個(gè)結(jié)點(diǎn)的無向連通圖最少有 條邊。 A．5 B. 6 C. 7 D. 8 （ C ）5. 有8個(gè)結(jié)點(diǎn)的有向完全圖有 條邊。 A．14 B. 28 C. 56 D. 112 （ B ）6. 用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常是采用 來實(shí)現(xiàn)算法的。A．棧 B. 隊(duì)列 C. 樹 D. 圖 （ A ）7. 用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常是采用 來實(shí)現(xiàn)算法的。A．棧 B. 隊(duì)列 C. 樹 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 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 1 2 34 6 5（ D ）10. 已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是A．0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3（ A ）11. 已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是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. 任何一個(gè)無向連通圖的最小生成樹A．只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在（注，生成樹不唯一，但最小生成樹唯一，即邊權(quán)之和或樹權(quán)最小的情況唯一）二、填空題（每空1分，共20分）1. 圖有 鄰接矩陣 、 鄰接表 等存儲結(jié)構(gòu)，遍歷圖有 深度優(yōu)先遍歷 、 廣度優(yōu)先遍歷 等方法。2. 有向圖G用鄰接表矩陣存儲，其第i行的所有元素之和等于頂點(diǎn)i的 出度 。
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1