計概17-02無向圖－公職試題

【選擇題】

【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)記錄一個有V個點E個邊的無向圖之空間複雜度為何？ (A)O(VE) (B)O(V2) (C)O(E) (D)O(V+E)。[111普考電子]

 

【B】07.一個無向連通圖(Undirected connected graph)G，若具有下列何項條件則成為一棵樹？ (A)每個頂點的分支度(Degree)都是偶數 (B)不包含迴路(Cycles) (C)有一個分支度(Degree)是奇數的頂點 (D)非完全連通(Completely connected)。[111普考電子]

<維基百科>樹具有以下的特點：

•每個節點都只有有限個子節點或無子節點；

•沒有父節點的節點，稱為根節點；

•每一個非根節點有且只有一個父節點；

•除了根節點外，每個子節點可以分為多個不相交的子樹；

•樹裡面沒有迴路(cycle)

 

【A】08.在一n個節點的連通無向圖(Connected Undirected Graph)中，找出一展開樹(Spanning Tree)，則此展開樹中有幾個邊(edge)？ (A)n-1 (B)n (C)n或n+1 (D)n-1或n。[111鐵路員級]

無向圖的展開樹，連結所有節點的邊數，為節點數減1。

 

【D】09.有n個節點的連通無向圖(Connected Undirected Graph)G，假設其中每個邊(Edge)都有不同的加權(Weight)，今要在G中找出一最小展開樹(Minimum Spanning Tree)T，下列敘述何者錯誤？ (A)T中會有n-1個邊 (B)Kruskal's Algorithm是一種常用來找最小展開樹的演算法 (C)T中一定包含圖G中加權最小的邊 (D)此問題最適合用Divide and Conquer的演算法來解。[112地方四等電子]

最小展開樹演算法採用：Borůvka's algorithm、Kruskal's algorithm、Prim's algorithm

分治法(Divide and conquer)：將問題分成多個子問題，把子問題逐個解決，再組合成大問題的答案。

 

【C】10.在一個連通加權無向圖(Connected weighted undirected graph)中，關於最小生成樹(minimum spanning tree)的敘述何者錯誤？ (A)最小生成樹是連通圖中權值最小的生成樹 (B)如果圖的每一條邊的權值都互不相同，那麼最小生成樹將只有一個 (C)最小生成樹不一定存在 (D)一個連通圖可能有多個生成樹。[112國安五等]

在一個連通加權無向圖中，最小生成樹是指權值最小的生成樹，最小生成樹一定存在。

留言

張貼留言

這個網誌中的熱門文章

計概17-01圖形理論－公職試題

圖片
【選擇題】 【 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
閱讀完整內容

計概17-03有向圖－公職試題

圖片
【選擇題】 【 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 鐵路員級 ]
閱讀完整內容