下列那一個不是圖形的表示方法?
-
A. 相鄰矩陣(adjacency matrix)5.9% (1)
-
B. 相鄰串列(adjacency list)0% (0)
-
C. 相鄰複合串列(adjacency multi list)5.9% (1)
-
D. 相鄰堆積(adjacency heap)88.2% (15)
解說:
以下是各選項的解釋:
(A) 相鄰矩陣(adjacency matrix):這是一種圖形的表示方法,使用矩陣來表示圖中各個節點之間的連接關係。
(B) 相鄰串列(adjacency list):這也是圖形的表示方法,使用每個節點對應的鏈節串列表來儲存與其相鄰的節點。
(C) 相鄰複合串列(adjacency multi list):這是一種圖的表示方法,是相鄰串列的一種擴展形式,對應每個節點有多個鏈節串列表。
(D) 相鄰堆積(adjacency heap):這並不是圖的標準表示方法。堆積(heap)通常用來表示優先佇列等結構,與圖形的直接表示關係不大,因此這不是圖形的表示方法。
因此,選項 (D) 相鄰堆積不屬於圖形的表示方法。
(A) 相鄰矩陣(adjacency matrix):這是一種圖形的表示方法,使用矩陣來表示圖中各個節點之間的連接關係。
(B) 相鄰串列(adjacency list):這也是圖形的表示方法,使用每個節點對應的鏈節串列表來儲存與其相鄰的節點。
(C) 相鄰複合串列(adjacency multi list):這是一種圖的表示方法,是相鄰串列的一種擴展形式,對應每個節點有多個鏈節串列表。
(D) 相鄰堆積(adjacency heap):這並不是圖的標準表示方法。堆積(heap)通常用來表示優先佇列等結構,與圖形的直接表示關係不大,因此這不是圖形的表示方法。
因此,選項 (D) 相鄰堆積不屬於圖形的表示方法。
答對率 : 88.2 %
欲求取某地區任二個城市間的最短路徑時,所使用的演算法通常被歸類為下列何種資料型態的相關操作?
-
A. 樹狀結構11.8% (2)
-
B. 優先佇列23.5% (4)
-
C. 圖形64.7% (11)
-
D. 符號表0% (0)
解說:
答案是 (C) 圖形。
解釋如下:
(A) 樹狀結構:樹是一種特定類型的圖,它是無循環的且連通。雖然樹與圖有某些相似之處,但最短路徑算法通常用於處理的是一般圖,而非單純的樹。因此,樹狀結構並不是最適合的答案。
(B) 優先佇列:優先佇列是一種特殊的排隊結構,通常用於在最短路徑算法中進行節點的選擇,例如在 Dijkstra 算法中會用到優先佇列來選擇距離最短的節點,但優先佇列本身並不是一種圖形結構。
(C) 圖形:最短路徑問題正是圖形(Graph)問題,因為城市和路徑可以表示為圖中的節點和邊。常見的最短路徑算法(如 Dijkstra 算法)正是用來解決圖形中的最短路徑問題。因此,圖形是最合適的資料結構。
(D) 符號表:符號表是一種儲存關聯數據的資料結構,例如鍵值對,常用於搜尋、插入等動作。符號表與最短路徑算法的關聯較小,因此不是正確答案。
因此,解決兩個城市間最短路徑的演算法屬於 圖形(Graph)相關的操作。
解釋如下:
(A) 樹狀結構:樹是一種特定類型的圖,它是無循環的且連通。雖然樹與圖有某些相似之處,但最短路徑算法通常用於處理的是一般圖,而非單純的樹。因此,樹狀結構並不是最適合的答案。
(B) 優先佇列:優先佇列是一種特殊的排隊結構,通常用於在最短路徑算法中進行節點的選擇,例如在 Dijkstra 算法中會用到優先佇列來選擇距離最短的節點,但優先佇列本身並不是一種圖形結構。
(C) 圖形:最短路徑問題正是圖形(Graph)問題,因為城市和路徑可以表示為圖中的節點和邊。常見的最短路徑算法(如 Dijkstra 算法)正是用來解決圖形中的最短路徑問題。因此,圖形是最合適的資料結構。
(D) 符號表:符號表是一種儲存關聯數據的資料結構,例如鍵值對,常用於搜尋、插入等動作。符號表與最短路徑算法的關聯較小,因此不是正確答案。
因此,解決兩個城市間最短路徑的演算法屬於 圖形(Graph)相關的操作。
答對率 : 64.7 %
從任何一個頂點開始,經過所有的邊一次,再最後回到原頂點的路徑稱之為?
-
A. 二元樹( binary tree)0% (0)
-
B. 相連路徑(connected path)17.6% (3)
-
C. 尤拉循環(Eulerian tour)82.4% (14)
-
D. 平衡路徑(balance path)0% (0)
解說:
答案是 (C) 尤拉循環 (Eulerian tour)。
解釋如下:
(A) 二元樹 (binary tree):二元樹是一種樹結構,其中每個節點最多有兩個子節點。這與題目中的路徑問題無關,因此不是正確答案。
(B) 相連路徑 (connected path):相連路徑指的是圖中兩個節點之間存在一條從一個節點到另一個節點的路徑。這並不特指經過所有邊一次並回到起點的路徑,因此也不是正確答案。
(C) 尤拉循環 (Eulerian tour):這是正確答案。尤拉循環是一條從某個頂點出發,經過圖中的每一條邊恰好一次,並最終回到原始頂點的路徑。只有當圖滿足一定的條件(例如每個頂點的度數為偶數且圖是連通的),才存在尤拉循環。
(D) 平衡路徑 (balance path):這個概念並不是圖論中的標準術語,因此與題目中的描述不符。
解釋如下:
(A) 二元樹 (binary tree):二元樹是一種樹結構,其中每個節點最多有兩個子節點。這與題目中的路徑問題無關,因此不是正確答案。
(B) 相連路徑 (connected path):相連路徑指的是圖中兩個節點之間存在一條從一個節點到另一個節點的路徑。這並不特指經過所有邊一次並回到起點的路徑,因此也不是正確答案。
(C) 尤拉循環 (Eulerian tour):這是正確答案。尤拉循環是一條從某個頂點出發,經過圖中的每一條邊恰好一次,並最終回到原始頂點的路徑。只有當圖滿足一定的條件(例如每個頂點的度數為偶數且圖是連通的),才存在尤拉循環。
(D) 平衡路徑 (balance path):這個概念並不是圖論中的標準術語,因此與題目中的描述不符。
因此,從任何一個頂點開始,經過所有邊一次,並回到原頂點的路徑稱為 尤拉循環 (Eulerian tour)。
答對率 : 82.4 %
有關資料結構中的一個圖形G和它的展開樹(spanning tree)T之間關聯性,下列敘述何者正確?
-
A. G和T必定不相同17.6% (3)
-
B. 存在於G的邊,必定存在於T0% (0)
-
C. 存在於T的邊,必定存在於G76.5% (13)
-
D. 存在於T的邊和存在於G的邊交集必定為空集合5.9% (1)
解說:
答案是 (C) 存在於T的邊,必定存在於G。
解釋如下:
(A) G和T必定不相同:這是不正確的。事實上,圖形G 和它的展開樹 T 的結構可能有很多相同之處,尤其是當 G 本身是樹時,展開樹就是圖本身。展開樹是一個圖的子圖,包含圖中所有節點,並且是一棵樹,因此有可能是與 G 相同(如果 G 本身就是一棵樹)。
(B) 存在於G的邊,必定存在於T:這是不正確的。展開樹 T 是從 G 中選出的一組邊,旨在保持圖的連通性並且沒有環。這意味著並非 G 中的所有邊都會出現在 T 中,只有能保持圖的連通性並且不形成環的邊才會包含在展開樹中。
(C) 存在於T的邊,必定存在於G:這是正確的。展開樹T 是圖 G 的子圖,這意味著展開樹中的所有邊必定是在 G 中的邊。因為 T 是由 G 的部分邊組成,且每個節點都必須在 G 中存在。
(D) 存在於T的邊和存在於G的邊交集必定為空集合:這是不正確的。事實上,展開樹 T 的邊集就是圖
G 邊集的一個子集,因此它們的交集必然不為空。展開樹中的邊來自於圖 G 中的邊,所以交集至少包含展開樹中的邊。
G 邊集的一個子集,因此它們的交集必然不為空。展開樹中的邊來自於圖 G 中的邊,所以交集至少包含展開樹中的邊。
因此,正確答案是 (C) 存在於T的邊,必定存在於G。
答對率 : 76.5 %
若以相鄰矩陣來表達圖形,則該矩陣第2列上所有元素數值的總和等於?
-
A. 圖形上所有節點的個數0% (0)
-
B. 圖形上所有節點個數的一半23.5% (4)
-
C. 節點2 之所有相鄰節點個數58.8% (10)
-
D. 節點2 之所有相鄰節點個數的一半17.6% (3)
解說:
答案是 (C) 節點2之所有相鄰節點個數。
解釋如下:
在圖的相鄰矩陣表示法中,每個矩陣元素 A[i][j] 表示節點 i 和節點 j 之間是否存在邊。如果圖是無向圖,則相鄰矩陣是對稱的,即 A[i][j]=A[j][i]。如果圖是有向圖,則矩陣的對稱性可能不成立。
對於相鄰矩陣的第二列,所有元素的總和實際上等於與節點 2 相連接的節點數量。具體來說,第 2 列上的每個元素 A[i][2] 表示節點 2 是否與節點 i 相連(若有邊,則為 1,否則為 0)。因此,該列上所有元素的總和等於與節點 2 相鄰的所有節點數量,即節點 2 的度數。
如果是無向圖,這個度數是節點 2 的所有相鄰節點的個數;如果是有向圖,則可能需要根據具體情況進一步分析,例如考慮入分支度(indegree)和出分支度(outdegree)的區別。
因此,第 2 列上所有元素數值的總和等於節點 2 之所有相鄰節點的個數。
答對率 : 58.8 %