108 地方特考三等 資訊處理 資料結構 考古題詳解

核心觀念

本題考查迴圈的執行次數與漸近時間複雜度。若每次迴圈執行固定時間的片段 $S$，總時間便與迴圈次數同階；題目已說明 $S$ 沒有與 $n$ 相關的迴圈，因此可視為 $O(1)$。

分析時，先由迴圈條件求出控制變數的範圍，再估計迴圈執行次數。Big-O 表示執行時間的漸近上界；本題的迴圈次數也都能得到對應的緊確階數。

解題方法與推導

（一）

for (int i = 0; i*i < n; i++)
 S

迴圈從 $i=0$ 開始，每次增加 $1$，持續到 $i^2\ge n$ 為止。條件 $i^2<n$ 等價於：

因此迴圈執行約 $\sqrt{n}$ 次。每次執行的 $S$ 為 $O(1)$，所以：

（二）

for (int i = 0; Math.sqrt(i) < n; i++)
 S

條件是 $\sqrt{i}<n$。由於 $i,n\ge 0$，兩邊平方可得：

核心觀念

本題比較三種優先佇列實作方式。數值越小，優先權越高，因此優先佇列的取出端應是最小值。

• 雙向鏈結串列：每個節點有前、後指標，可將元素依優先權排序後串接。
• 紅黑樹：依二元搜尋樹規則插入，並按紅黑樹規則重新著色、旋轉；每次插入後根節點為黑色。
• 最小堆積：完全二元樹，且每個節點的值不大於其子節點。以陣列表示時，索引由左至右、由上而下排列。

以下均依序插入 $90,10,80,20,70,50,40,30$。

解題方法

(一) 雙向鏈結串列

將節點依數值由小到大排列，使優先權最高的元素位於串列前端。如此可由頭端取得最小值；插入時將新節點放在符合排序的位置。

依序插入後，串列為：

頭 ⇄ 10 ⇄ 20 ⇄ 30 ⇄ 40 ⇄ 50 ⇄ 70 ⇄ 80 ⇄ 90 ⇄ 尾

每一組相鄰節點間均有雙向連結；頭、尾端未連向其他節點的指標為空。

(二) 紅黑樹

依序以二元搜尋樹規則插入各值；新節點先著紅色，再依紅黑樹規則修正。修正時需維持根為黑色、紅節點不得有紅色子節點，且每條由節點通往空葉的路徑具有相同黑節點數。

逐步插入的主要結構變化如下：

1. 插入 $90$：成為根，著黑。
2. 插入 $10$：成為 $90$ 的左子節點，著紅。
3. 插入 $80$：形成左右交錯的紅紅違規，經旋轉與重新著色後，$80$ 成為黑根，$10$、$90$ 為紅。
4. 插入 $20$：父節點與叔節點皆紅，重新著色。
5. 插入 $70$：經旋轉與重新著色修正。
6. 插入 $50$：父節點與叔節點皆紅，重新著色。
7. 插入 $40$：經旋轉與重新著色修正。
8. 插入 $30$：父節點與叔節點皆紅，重新著色；根維持黑色。

最後的紅黑樹如下：

 50B
 / \
 20R 80R
 / \ / \
 10B 40B 70B 90B
 /
 30R

(三) 最小堆積

核心觀念

2-3-4 樹的每個節點可包含 1 至 3 個鍵值。轉換成紅黑樹時：

• 1 個鍵值的節點對應一個黑色節點。
• 2 個鍵值的節點以較大的鍵值作黑色節點、較小的鍵值作其紅色左子節點。
• 3 個鍵值的節點以中間鍵值作黑色節點，較小與較大的鍵值分別作紅色左、右子節點。

以下以「鍵值（顏色）」標示紅黑樹節點。每個 2-3-4 樹節點對應的黑色節點及其紅色子節點，合起來就是原節點。

解題方法

先依 2-3-4 樹的節點鍵值及子樹區間，轉成對應的紅黑樹。插入與刪除則先在 2-3-4 樹上完成，再用相同規則轉成紅黑樹。

（一）原樹對應的紅黑樹

根節點 [40, 62, 83] 是三鍵值節點，因此以 62 為黑色節點，40、83 為紅色子節點。其餘節點依同一規則轉換：

62（黑）
├─L：40（紅）
│ ├─L：20（黑）
│ │ ├─L：10（紅）
│ │ └─R：31（紅）
│ └─R：55（黑）
│ └─L：45（紅）
└─R：83（紅）
 ├─L：78（黑）
 │ └─L：70（紅）
 └─R：92（黑）
 └─L：90（紅）

例如，葉節點 [10, 20, 31] 轉成以 20 為黑色節點、10 與 31 為紅色子節點。

（二）插入 33，再刪除 78

先插入 33

從根節點 [40, 62, 83] 開始，該節點已滿，先將 62 分裂提升為新根。接著往左搜尋，遇到滿節點 [10, 20, 31]，將 20 提升到父節點；此時父節點成為 [20, 40]，原節點分成 [10] 與 [31]。最後將 33 插入 [31]，形成 [31, 33]。

插入後的 2-3-4 樹為：

核心觀念

廣度優先搜尋（BFS）使用佇列，依「先進先出」逐層走訪；深度優先搜尋（DFS）使用堆疊，沿著尚未走訪的相鄰節點深入，再回溯。走訪時將已走訪的人標記，避免重複處理。

依圖中的連線，鄰接關係為：

• 張三（CS）：李四（LS）、趙六（CL）
• 李四（LS）：張三（CS）、王五（WW）、趙六（CL）
• 王五（WW）：李四（LS）、趙六（CL）
• 趙六（CL）：張三（CS）、李四（LS）、王五（WW）

同時有多個可選人名時，依縮寫字母順序先處理較小者。

解題方法

(一) BFS：使用佇列

從張三（CS）出發。張三尚未走訪的鄰居為 CL、LS，依字母順序將趙六、李四加入佇列。

核心觀念

本題考查雜湊函數與開放定址法中的線性探測。鍵值的初始位置為

若初始位置已被占用，便依指定的探測間隔逐格尋找空位。探測位置超出索引範圍時，以模數 $19$ 繞回表格開頭。

「間隔為 1」每次往後移一格；「間隔為商」則將鍵值除以表格大小所得的商作為探測間隔，也就是探測位置依序為 $h(k)+i\lfloor k/19\rfloor \pmod{19}$，其中 $i=0,1,2,\ldots$。

解題方法

先依題目給定的鍵值順序計算初始位置，再依各方法的探測規則，將每個鍵值放入第一個空位。

（一）間隔為 1

每次碰撞後，索引加 $1$，並以 $19$ 為模數：

因此，雜湊表如下：

（二）間隔為商

探測間隔為 $\lfloor k/19\rfloor$。每次碰撞後，索引依此間隔前進，並以 $19$ 為模數。