114 身心障礙特考三等 資訊處理類科 資料結構 考古題詳解
第 一 題25 分
請就「記憶體空間使用」與「存取方式」兩個主題，詳細申論陣列（array）與鏈結串列（linked list）兩種不同的資料結構的作法。
登入後即可作答並保存紀錄。
核心觀念
本題比較陣列（array）與鏈結串列（linked list）在記憶體配置方式及資料存取方式上的差異。作答時應掌握兩個核心：
- 陣列的元素通常配置在一段連續的記憶體空間，可由索引計算元素位置。
- 鏈結串列的節點可分散配置在記憶體中，各節點透過指標連結，通常須沿鏈逐一走訪。
解題方法
依「記憶體空間使用」與「存取方式」分別比較，並補充插入、刪除與空間成本，讓兩種結構的取捨完整明確。
| 比較項目 | 陣列（array） | 鏈結串列（linked list） |
|---|---|---|
| 記憶體配置 | 元素通常存放在連續的記憶體位置。若每個元素占 位元組，起始位址為 ，則索引為 的元素位址可計算為 （以零起始索引為例）。 | 節點通常不必連續配置。每個節點除資料外，還須儲存一個或多個指標，例如單向鏈結串列需儲存指向下一節點的指標。 |
| 空間使用 | 固定大小陣列會預先配置容量；若實際元素少於容量，未使用部分仍占空間。動態陣列可擴充，但擴充時常須配置較大空間並搬移元素。 | 可依需求逐一配置節點，不必預留連續空間；但每個節點都須額外負擔指標欄位，也有節點配置與管理成本。 |
| 依索引存取 | 可由索引直接計算位置，因此隨機存取通常為 。 | 一般須從首節點沿指標走訪至目標節點；存取第 個節點通常為 。 |
| 搜尋 | 若未排序，依值搜尋通常為 ；若已排序且可依索引存取，可使用二分搜尋，時間為 。 | 依值搜尋通常須逐節點比較，時間為 ；即使資料有序，也無法像陣列一樣直接跳到中間節點進行二分搜尋。 |
| 插入與刪除 | 在中間位置插入或刪除元素，通常須搬移後續元素，時間為 ；在尾端操作則依實作方式而定。 | 已知插入或刪除位置的節點，且能取得其前驅節點時，修改指標即可完成連結調整，通常為 ；但若須先搜尋位置，整體仍可能需要 。 |
解題要點
一、陣列的記憶體空間使用
第 二 題25 分
請詳述利用快速排序法（quick sort）來排序下列資料，經過第一回合（pass）的處理後，輸出的資料結果為何？
請注意：需列出詳細的處理步驟。
登入後即可作答並保存紀錄。
核心觀念
快速排序會先選定一個基準值（pivot），再將資料分成兩側：一側的值不大於基準值，另一側的值不小於基準值。完成一次分割後，基準值已位於其最終排序位置；左右兩側再分別遞迴排序。
題目只問「第一回合（pass）」的結果。不過快速排序教材對 pivot 的選取方式及分割程序有不同約定，因此結果會因實作而異。本題以下採用常見的 以第一個元素為 pivot，並以左右指標交換分割 的方法。
解題方法與處理步驟
原始資料為：
選第一個元素 為基準值。左指標由左向右尋找大於 的值；右指標由右向左尋找小於 的值。找到一對後交換，直到兩指標交錯，再將 pivot 放到兩指標相遇處。
- 初始時，左指標從 開始，找到大於 的 ；右指標從右端往左，找到小於 的 。交換兩者：
- 左指標繼續向右，找到大於 的 ；右指標向左找到小於 的 。交換兩者：
第 三 題10 分
下列的無向圖（undirected graph）表示點與點之間的關係，如 A 與 B 有關係，代表 A 與 B 之間有邊（edge）相連，則可走訪。若以英文字母順序作為走訪的先後順序。
🖼️【此處有附圖，請對照原卷】
（一）由 A 出發，做廣度優先搜尋（breadth-first search）走訪所有節點，請依序寫出走訪的節點內容。（10 分）
（二）由 A 出發，做深度優先搜尋（depth-first search）走訪所有節點，請依序寫出走訪的節點內容。（15 分）
登入後即可作答並保存紀錄。
核心觀念
本題考查無向圖的兩種基本走訪：
- 廣度優先搜尋（BFS）：使用佇列（queue），按照距離起點由近到遠的層次走訪。
- 深度優先搜尋（DFS）：使用堆疊（stack）或遞迴，沿著一條路徑深入到底，再回溯走訪其他分支。
- 當同一節點有多個尚未走訪的相鄰節點時，依英文字母順序處理。
由圖可得各節點的相鄰關係如下：
- A：B、C
- B：A、D、E
- C：A、F、G
- D：B、H
- E：B、H
- F：C、H
- G：C、H
- H：D、E、F、G
（一）廣度優先搜尋 BFS
BFS 使用佇列，先處理距離 A 較近的節點。
走訪步驟
- 從 A 出發，走訪 A，將相鄰節點 B、C 依序加入佇列。
- 取出 B，走訪 B，將尚未走訪的 D、E 加入佇列。
- 取出 C，走訪 C，將尚未走訪的 F、G 加入佇列。
- 取出 D，走訪 D，發現 H 尚未走訪，將 H 加入佇列。
- 取出 E、F、G 時，H 已經走訪或已加入佇列，不重複加入。
- 最後走訪 H。
因此 BFS 的走訪順序為：
（二）深度優先搜尋 DFS
DFS 依英文字母順序沿路徑深入，無法繼續時再回溯。
走訪步驟
第 四 題15 分
（一）假設對堆疊（stack）依照順序將 A、B、C 三筆資料執行 PUSH 的動作。
當執行 PUSH 動作的過程中，如果堆疊中有資料，便可對堆疊執行 POP 動作，若共執行三次 PUSH 動作與三次 POP 動作；三次 PUSH 與三次 POP 動作之前後關聯性，只要合理均為可能，請寫出所有可能的輸出結果。（15 分）
（二）請詳述副程式呼叫（subroutine call）實作的過程是採用佇列（queue）或是堆疊（stack）來做為使用的資料結構之理由。（10 分）
登入後即可作答並保存紀錄。
（一）堆疊的可能輸出結果
核心觀念
堆疊遵循「後進先出」（Last In, First Out，LIFO）：資料從頂端進入，也只能從頂端取出。題目規定依序 PUSH B、，每筆資料各 PUSH 一次，且共 POP 三次；每次 POP 都必須在堆疊非空時進行。輸出結果是三次 POP 依序取出的資料。
解題方法
依 PUSH 順序，能被 POP 的先後順序必須符合堆疊的 LIFO 規則。逐一安排 POP 的時機，可列出全部可能的輸出：
| POP 時機與順序 | 輸出結果 |
|---|---|
| PUSH 後立即 POP；再 PUSH、POP ；最後 PUSH、POP | |
| PUSH 後先 POP ；再 PUSH、POP ；最後 POP | |
| PUSH 後先 POP ；接著 POP ；再 PUSH、POP | |
| PUSH 後依序 POP | |
| PUSH 後先 POP ；再 POP ；最後 POP |
最後兩種時機安排雖不同，輸出相同，因此不重複計為不同結果。其餘兩個 開頭的時序亦可分別得到 與 ：先 PUSH ，再 PUSH ，依序 POP ，得到 ；若要得到 ，則先 PUSH 並 POP ，再 PUSH ，依序 POP ，得到 。整理後的所有不同輸出為：