計概17.圖形理論

【選擇題】 【 B 】 01. 下方之有向圖 (directed graph) 中，從節點 i 至節點 a 的最短路徑 (shortest path) 其長度為何？ (A)11 (B)12 (C)13 (D)14 。 [109 鐵路員級 ] i-h-c-b-a=3+5+3+1=12   【 B 】 02. 給定下列有向圖 (Directed graph) ，若自節點 A 出發進行優先走訪 (Breadth-first search) ，則下列何者是可能的走訪順序？ (A)ABCDEFG (B)ABDGCEF (C)AGFDECB (D)ABCDEGFABCDEFG 。 [110 地方四等電子 ] level 0 ： A 。 level 1 ： BDG 。 level 2 ： CE 。 level 3 ： F   【 B 】 03. 有 8 個頂點且沒有自成迴路 (Self loop) 的有向圖 (Directed graph) ，最多具有多少個邊？ (A)28 (B)56 (C)64 (D)256 。 [110 普考電子 ] 有向圖具有 n 個頂點，應有邊數 =n*(n-1)/2=8*(8-1)=56   【 B 】 04. 給予一個加權有向圖 (weighted directed graph)G = (V, E) ，其中 V 代表頂點集合， E 代表邊集合。若以 |V| 代表頂點的數量、 |E| 代表邊的數量且假設邊的權值皆大於 0 ，在最差狀況下使用 Bellman-Ford 演算法尋找某一個頂點到其他頂點的最短路徑的時間複雜度，則下列何者正確？ (A)O(|E|) (B)O(|V||E|) (C)O(|V| 2 ) (D)O(|E| 2 ) 。 [110 關務 四等 ] 假設加權有向圖有 V 個頂點， E 個邊，最多會進行 V 次更新的循環，而每次循環會針對每個邊進行一次檢查，所以每循環的執行時間是 O(E) ，總執行時間為 O(VE) 。 【 C 】 05. 如果圖中不存在迴路 (Cycles) ，那麼在具有 7 個頂點的簡單有向圖 (Simple directed graph) 中，最多有多少個邊？ (A)12 (B)7 (C)6 (D)14 。 [110 鐵路員級 ]

【選擇題】 【 B 】 01. 下圖表示一個具有權重 (weight) 的無向圖 (undirected graph) 。假設我們針對該圖求取最小生成樹 (minimum spanning tree) ，則該樹的權重總和為下列何者？ (A)1 (B)6 (C)8 (D)10 。 [109 鐵路員級 ] 1 + 2 + 3 = 6   【 B 】 02. 關於無向圖 (Undirected graph) 頂點的分支度 (Degree) ，下列敘述何者正確？ (A) 具有奇數分支度的頂點個數是奇數 (B) 所有頂點的分支度的總和是偶數 (C) 具有偶數分支度的頂點個數是奇數 (D) 偶數分支度的頂點個數多於奇數分支度的頂點個數。 [110 地方四等電子 ] (A)(D) 線段不是。 (C) 正方形不是。   【 B 】 03. 若一個無向圖 (Undirected Graph)G 由 n 個點 (Vertices) 與 m 條邊 (Edges) 所組成，且 G 為一個樹 (Tree) ，則有關點與邊的敘述，下列何者正確？ (A)m = n - 2 (B)m = n - 1 (C)m = n (D)m = n + 1 。 [110 身心四等 ] 生成樹 (Spanning Tree) 的邊為節點數 - 1   【 C 】 04. 一個具有 6 個頂點 (Vertices) 的無向完整圖形 (Undirected Complete Graph) ，應有多少個邊 (Edges) ？ (A)36 (B)18 (C)15 (D)6 。 [110 普考電子 ] 無向圖具有 n 個頂點，應有邊數 =n*(n-1)/2=6*(6-1)/2=15   【 C 】 05. 樹 (Tree) 的定義為一個不包含簡單迴路 (Simple circuit) 的無向連結圖 (undirected connected graph) ，而葉子 (Leaves) 的定義為次數 (Degrees) 為 1 的節點 (Nodes) 。一棵樹若有 2 個以上的節點，最少會有幾個節點是葉子？ (A)0 (B)1 (C)2 (D)3 。 [111 地方四等電子 ]   【 B 】 06. 使用相鄰矩陣 (Adjacency matrix

【四技試題】 【 B 】 01. 考量旅遊時最少成本路徑規劃問題，其模型如圖的圖 (Graph) 資料結構所示，邊 (Edge) 所標數值為其成本 (Cost) ，節點 1 到節點 6 間最少成本路徑之總成本為何？ (A)8 (B)10 (C)11 (D)18 。 [112 管理 ] 最少成本路徑： ①→③→④→⑤→⑥ 總成本 = 4+2+1+3=10

【選擇題】 【 B 】 01. 給定 {v1, v2, v3, v4, v5} 鄰接矩陣 (adjacency matrix) 如下，則 v1 到其他各點 ( 可以經過別的點 ) 的最短路徑距離何者正確？ (A)v1→v3 ，最短路徑距離 =3 (B)v1→v4 ，最短路徑距離 =3 (C)v1→v5 ，最短路徑距離 =∞ (D)v1→v2 ，最短路徑距離 =4 。 [110 身心五 等 ] (A)v1 → v2 → v3 ，最短路徑距離 =1+1=2 (B)v1 → v2 → v3 → v4 ，最短路徑距離 =1+1+1=3 (C)v1 → v2 → v4 ，最短路徑距離 =1+2+1=4 (D)v1 → v2 ，最短路徑距離 =1   【 C 】 02. 如下圖有一位老師從學校 A 出發要對 3 名學生進行家庭訪問，而一條路只能經過一次，請問老師最少需多少時間，才能訪問完 3 位學生並回到學校？ (A)13 (B)14 (C)15 (D)16 。 [110 初考資處 ] A-B-C-D-A → 3 + 9 + 2 + 8 = 22 A-B-D-C-A → 3 + 4 + 2 + 6 = 15 A-C-B-D-A → 6 + 9 + 4 + 8 = 27 A-C-D-B-A → 6 + 2 + 4 + 3 = 15 A-D-B-C-A → 8 + 4 + 9 + 6 = 27 A-D-C-B-A → 8 + 2 + 9 + 3 = 22   【 B 】 03. 下圖所示之 AOE(Activities on Edge) 網路 ， 其關鍵路徑 (Critical Path) 包含下列何者 ？ ( 表示由 X 到 Y 的有向邊 ) (A)<F,G> (B)<E,G> (C)<E,H> (D)<A,D> 。 [110 普考 電子 ] 關鍵路徑： A → B → C → E → G → J = 4+3+1+7+5=20     【 B 】 04. 一圖 (Graph)G 有 n 個節點 (Vertices) 以及 e 個邊 (Edges) ， 若用相鄰矩陣 (Adjacency matrix)A 來表示 G ， 則 A 中的元素 (Ele