已知一連通圖（connected graph），圖中一個子樹、一個生成圖（spanning graph，即含原圖中所有節點的連通子圖）與一個最小生成樹（spanning tree），下列敘述何者正確？
A子樹邊數 ≦ 生成圖的邊數 ≦ 最小生成樹的邊數
B子樹邊數 ≦ 最小生成樹的邊數 ≦ 生成圖的邊數正確答案
C最小生成樹的邊數 ≦ 生成圖的邊數 ≦ 子樹邊數
D最小生成樹的邊數 ≦ 子樹邊數 ≦ 生成圖的邊數
答案與詳解
逐選項解析
A子樹邊數 ≦ 生成圖的邊數 ≦ 最小生成樹的邊數✕ 錯誤
生成圖邊數≥n-1，最小生成樹邊數=n-1，故生成圖邊數不可能≤最小生成樹邊數。
B子樹邊數 ≦ 最小生成樹的邊數 ≦ 生成圖的邊數✓ 正確
C最小生成樹的邊數 ≦ 生成圖的邊數 ≦ 子樹邊數✕ 錯誤
子樹邊數不可能大於等於生成圖邊數，因子樹僅為部分節點構成之樹，邊數較少。
D最小生成樹的邊數 ≦ 子樹邊數 ≦ 生成圖的邊數✕ 錯誤
立即註冊,看完整詳解
這題的完整詳解,註冊就能看 · 每天 2 題免費
- 完整逐選項解析
- 秒殺解題技巧與破題關鍵
- 關鍵知識表整理
- 陷阱與易錯提醒
- 同考點歷屆題庫連續刷題與錯題本
立即註冊觀看完整詳解 已有帳號?登入
同科目歷年考卷
計算機概要 相關題目
從圖中的節點 a 開始進行廣度優先搜尋（Breadth first search…
計算機概要 · 111 年 · 第 20 題
依據下圖的特性，滿足那一種樹狀結構？
計算機概要 · 115 年 · 第 17 題
下圖為何種資料結構？
計算機概要 · 109 年 · 第 18 題
下圖所示為連接 a 到 g 共 7 個觀光景點的快速道路分布圖。若小明想請你幫忙…
計算機概要 · 113 年 · 第 18 題
對一個有九個節點的二元搜尋樹（Binary Search Tree）作前序訪問（…
計算機概要 · 109 年 · 第 20 題
下列那一種資料結構，最適合用來表示地圖上各城市間的道路連接狀況？
計算機概要 · 115 年 · 第 18 題
如下圖，由節點 1 開始進行廣度優先搜尋（Breadth-First Searc…
計算機概要 · 115 年 · 第 19 題
某二元搜尋樹（Binary Search Tree）內存有一些數目，且任一節點所…
計算機概要 · 113 年 · 第 17 題
