計概17-03有向圖－統測試題
【四技試題】 【 C 】 01 . 完全有向圖 (Complete Directed Graph) 是一個有向圖 (Directed Graph) ，其中每一頂點 (Vertex) 均有一個單向的邊 (Edge) 連接至所有其他頂點，所以有 4 個頂點的完全有向圖會有幾個單向的邊？ (A)4 (B)8 (C)12 (D)16 。 [112 管理 ] 有向圖具有 n 個頂點，應有邊數 =n*(n-1)/2=4*(4-1)=12
發表文章
計概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 鐵路員級 ]