計概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鐵路員級]

留言

張貼留言

這個網誌中的熱門文章

計概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-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
閱讀完整內容