中文（繁體）
中文（簡體）
English
中六ICT：數據結構 — 練習第二份（進階，10 題）
中六ICT：數據結構 — 練習第二份（進階，10 題）
第二份練操作與成本分析：二元搜尋樹中序遍歷得升序、滿二元樹 4 層共 15 個節點、連結串列頭部插入 O(1) 對陣列中間 O(n)、環形佇列 4 個元素，十題附答案與一句解說。
快速答案 中序遍歷 20~80；搜尋 40 比較 3 次；樹高 3；第 3 層 4 個節點；4 層滿樹 15 個；連結串列插入 O(1)、陣列 O(n)；環形佇列 front 2 rear 5 共 4 個；1 000 節點平均 500 次；BFS 用佇列、DFS 用堆疊。
01 本卷資料（做完才看答案）
| 項目 | 內容 |
|---|---|
| 題數 | 10 題 |
| 建議時間 | 約 20 分鐘 |
| 難度分佈 | 基礎 2 · 進階 3 · 挑戰 3 · 錯題重練 2 |
| 對應章節 | 所屬章節：中六ICT｜數據結構：陣列、連結串列、堆疊、佇列、樹與圖 |
| 適用年級 | 進階 |
02 題目（10 題）
- 基礎把 50、30、70、20、40、60、80 依次插入二元搜尋樹，中序遍歷的次序是甚麼？
- 基礎在同一棵樹搜尋 40，需要比較多少個節點？
- 進階這棵 7 節點的樹高度（以節點層數計）是多少？
- 進階一棵滿二元樹最深一層有 4 個節點，該層是第幾層？
- 進階一棵有 4 層的滿二元樹，節點總數是多少？
- 挑戰在連結串列的頭部插入一個節點，時間複雜度是多少？在陣列中間插入又如何？
- 挑戰環形佇列大小為 8，front 索引 2、rear 索引 5，現有元素多少個？
- 挑戰在 1 000 個節點的連結串列做線性搜尋，平均需要比較多少個節點？
- 錯題重練錯題重練：有同學答「廣度優先搜尋（BFS）用堆疊實作」。正確做法是甚麼？
- 錯題重練錯題重練：有同學答「在陣列中間插入元素是 O(1)」。正確複雜度是甚麼？
03 答案與一句解說
| 題號 | 答案 | 一句解說 |
|---|---|---|
| 1 | 20、30、40、50、60、70、80 | 二元搜尋樹的中序遍歷必定由小到大。 |
| 2 | 3 個 | 路徑是 50 → 30 → 40，共比較 3 次。 |
| 3 | 3 | 根在上一層，第二層有 30 與 70，第三層是 20、40、60、80。 |
| 4 | 第 3 層 | 第 n 層最多 2 的 n−1 次方個節點，2 的 2 次方等於 4。 |
| 5 | 15 個 | 2 的 4 次方減 1 等於 15，即 1+2+4+8。 |
| 6 | 連結串列 O(1)，陣列 O(n) | 連結串列改一條指標即可；陣列要搬移後面所有元素。 |
| 7 | 4 個 | 由 2 數到 5 共 4 個位置：2、3、4、5。 |
| 8 | 500 個 | 平均在串列中段找到，1 000 除以 2 得 500。 |
| 9 | BFS 用佇列，用堆疊的是深度優先搜尋（DFS） | BFS 要按層次先進先出，所以用佇列；DFS 靠後進先出回溯，所以用堆疊。 |
| 10 | O(n) | 插入位置之後的元素全部要向右移一格，最壞要搬 n 個。 |
04 做完之後怎樣跟進
- 對完答案，只重做錯的那幾題，並在錯題旁寫出錯在哪一步（公式、單位還是抄錯數）。
- 同一題隔兩日再做一次；兩次都對才可以移到下一份練習。
- 家長只需看答案欄與解說欄，不必逐題講解。
本卷題目與答案由 TutorZone 團隊原創編寫，並非任何學校、出版社或考試局的試題；數值與答案均以程式核算。