圖形結構：表示法、搜尋演算法與應用

📝 歷屆考古題

• 114年 高考申論題 第三題
  三、假設 G 為一個無方向連通加權圖（Undirected connected weighted graph），包含五個節點：A、B、C、D、E。各節點間相連情形如下，邊權（邊的權重）為正整數，代表邊…
  查看 AI 詳解 →
• 114年 高考申論題 第四題
  請說明若一個圖 G（V, E）的頂點數|V|為 n，而邊數|E|接近 n²，則相鄰串列（adjacency list）、相鄰矩陣（adjacency matrix）、或邊列表（edge list）中，…
  查看 AI 詳解 →
• 114年 高考申論題 第五題
  下列那幾項演算法可用於找出圖的最小生成樹（Minimum Spanning Tree）：Dijkstra 演算法、Floyd-Warshall 演算法、Prim 演算法、Bellman-Ford 演算…
  查看 AI 詳解 →
• 112年 高考申論題 第四題
  針對如下的有向圖（節點為走訪對象，連線上的數字為走訪的 cost），依如下 BFS（配合 queue）與 DFS（配合 stack）演算法，進行所有節點的走訪，多個節點可以走訪時，以連線上 cost…
  查看 AI 詳解 →
• 111年 高考申論題 第一題
  請使用相鄰矩陣（Adjacency Matrix）表示法來表示加權圖 G。（5 分）
  查看 AI 詳解 →
• 111年 高考申論題 第二題
  不考慮權重，從節點 g 開始並按照字母順序對 G 進行廣度優先尋訪（Breadth-First Search, BFS），請繪出尋訪完後所產生的 BFS 樹（BFS Tree）。（5 分）
  查看 AI 詳解 →
• 111年 高考申論題 第三題
  請利用 Prim's 演算法，從節點 d 起始，找出一個最小擴張樹（Minimum Spanning tree），請以圖示方式一步步畫出過程與結果，並說明 Prim's 演算法的時間複雜度。（10 分…
  查看 AI 詳解 →
• 111年 高考申論題 第四題
  用 G = (V, E)表示一個無方向性圖形，其中 V 是點的集合，E 是一組節點（Vertices）形成邊及對應權重（Weights）所組成的集合。今有一圖形 G = (V, E)，V = {0,…
  查看 AI 詳解 →
• 109年 高考申論題 第 一題
  對於無向圖G = (V, E)：（12分） ⑴請給出對應的相鄰矩陣M。 ⑵以字母順序為考量進行深度優先搜尋（Depth-First Search, DFS），請由節點a開始，描述此深度優先搜尋所產生的…
  查看 AI 詳解 →
• 109年 高考申論題 第 三題
  若將圖一無向圖G = (V, E)中的邊給予方向成為如圖二中的有向圖（Directed Graph）G’：（10分） 圖二、有向圖G’ ⑴有向圖G’沒有迴圈（Cycle），是一個無迴圈有向圖（Dire…
  查看 AI 詳解 →
• 109年 高考申論題 第 二題
  請說明在用相鄰矩陣（Adjacency Matrix）表示的無向圖上，進行深度優先搜尋的時間複雜度，其中節點與邊的數量分別為|V| = n與|E| = m。（8分）
  查看 AI 詳解 →
• 108年 高考申論題 第一題
  由張三（CS）出發，用佇列（queue）做廣度優先搜尋（breadth-first search）走訪所有人，請寫出走訪順序的中文人名。（10 分）
  查看 AI 詳解 →
• 108年 高考申論題 第二題
  由張三（CS）出發，用堆疊（stack）做深度優先搜尋（depth-first search）走訪所有人，請寫出走訪順序的中文人名。（10 分）
  查看 AI 詳解 →
• 108年 高考申論題 第四題
  四、用 G = (V, E)表示一個無方向性圖形，其中 V 是點的集合，E 是一組節點（Vertices）形成一個邊及對應權重（Weights）所組成的集合，例如：(0, 1, 28)表示節點 0 至…
  查看 AI 詳解 →
• 107年 高考申論題 第三題
  三、一無向圖 G 之節點集合為 G(V)={0,1,2,3,4,5,6,7,8,9}，邊集合為 G(E)={(0,1), (1,2), (1,3), (2,4), (3,4), (3,5), (5,6…
  查看 AI 詳解 →
• 106年 高考申論題 第一題
  若要節省開發預算，在可到達所有遊樂設施的前提下，所建置的商店街道總長度需越短越好，請問可以用那一個演算法來選擇應建置的街道？請給演算法名稱並簡單說明該演算法特性。（5 分）
  查看 AI 詳解 →
• 106年 高考申論題 第二題
  請計算符合上述（一）小題條件下，所應建置的商店街道總長度，並由小到大列舉所有應該建置街道的長度。（10 分）
  查看 AI 詳解 →
• 106年 高考申論題 第三題
  但若要規劃一條路徑，使得遊客可以從任一遊樂設施開始玩，且只要依照該路徑行走，就可以玩遍 9 項遊樂設施並回到起始的遊樂設施，遊客所需走過的商店街道總長度需越短越好且每項遊樂設施只能到達一次。請問此問題…
  查看 AI 詳解 →
• 105年 高考申論題 第一題
  使用堆疊（stack），從 S 開始，進行深度優先走訪（depth-first traversal），請寫出走訪結果。（10 分）
  查看 AI 詳解 →
• 105年 高考申論題 第二題
  使用佇列（queue），從 S 開始，進行廣度優先走訪（breadth-first traversal），請寫出走訪結果。（10 分）
  查看 AI 詳解 →