中文（繁體）
中文（簡體）
English
中六ICT：數據結構 — 練習第三份（挑戰，10 題）
中六ICT：數據結構 — 練習第三份（挑戰，10 題）
第三份練規模與效率：100 個頂點鄰接矩陣 10 000 格、300 條邊鄰接表 600 條記錄、退化成鏈的二元搜尋樹最差 10 次、合併 500 與 300 條串列最差 799 次比較，十題附答案與一句解說。
快速答案 鄰接矩陣 100×100=10 000；無向圖 300 條邊 600 條記錄；退化樹高 10 最差 10 次；平衡 1 000 節點最差 10 次；31 節點 5 層；合併 799 次；負載因子 1.0；8−3+2=7；n² 一百萬對 n log n 約 9 966；二分 10 次對線性 999 次。
01 本卷資料（做完才看答案）
| 項目 | 內容 |
|---|---|
| 題數 | 10 題 |
| 建議時間 | 約 25 分鐘 |
| 難度分佈 | 基礎 1 · 進階 2 · 挑戰 3 · 錯題重練 4 |
| 對應章節 | 所屬章節：中六ICT｜數據結構：陣列、連結串列、堆疊、佇列、樹與圖 |
| 適用年級 | 挑戰 |
02 題目（10 題）
- 基礎一個有 100 個頂點的圖用鄰接矩陣儲存，共需要多少格？
- 進階一個有 100 個頂點、300 條邊的無向圖用鄰接表儲存，共需多少條記錄？
- 進階把 10、20、30…100 依次插入二元搜尋樹，樹高是多少？最差搜尋要比較多少次？
- 挑戰一棵平衡的二元搜尋樹有 1 000 個節點，最差搜尋需要比較多少次？
- 挑戰一棵有 31 個節點的滿二元樹，高度（層數）是多少？
- 挑戰合併兩個已排序的串列，長度分別為 500 與 300，最多需要比較多少次？
- 錯題重練錯題重練：1 000 筆記錄存入 1 000 個桶的雜湊表，負載因子是多少？
- 錯題重練錯題重練：連續 push 8 個元素，再 pop 3 個，再 push 2 個，堆疊內有多少個元素？
- 錯題重練錯題重練：有同學答「O(n²) 演算法在 1 000 筆資料上比 O(n log n) 快」。用數字說明為何錯。
- 錯題重練錯題重練：有同學答「在已排序陣列上線性搜尋與二分搜索同為 O(n)」。正確是甚麼？
03 答案與一句解說
| 題號 | 答案 | 一句解說 |
|---|---|---|
| 1 | 10 000 格 | 鄰接矩陣是 n × n，100 × 100 等於 10 000。 |
| 2 | 600 條 | 無向圖每條邊在兩端各記一次，300 × 2 等於 600。 |
| 3 | 高度 10，最差 10 次 | 每次插入都只往右走，樹退化成單邊鏈，等同線性搜尋。 |
| 4 | 10 次 | 平衡樹高度約 log2(1001)，向上取整得 10。 |
| 5 | 5 層 | 2 的 5 次方減 1 等於 31，所以共 5 層。 |
| 6 | 799 次 | 最壞情況每次只取一個，取完 799 個後最後一個直接接上。 |
| 7 | 1.0 | 負載因子等於記錄數除以桶數，1 000 ÷ 1 000 等於 1.0。 |
| 8 | 7 個 | 8 減 3 加 2 等於 7，push 與 pop 各自只改動一個元素。 |
| 9 | O(n²) 約 1 000 000 次，O(n log n) 約 9 966 次，慢約 100 倍 | 1 000 的平方是一百萬，1 000 × log2(1 000) 約 9 966，相差約 100 倍。 |
| 10 | 線性搜尋 O(n) 最差 999 次，二分搜索 O(log n) 最差 10 次 | 二分搜索每步減半，1 000 筆只需約 10 次比較。 |
04 做完之後怎樣跟進
- 對完答案，只重做錯的那幾題，並在錯題旁寫出錯在哪一步（公式、單位還是抄錯數）。
- 同一題隔兩日再做一次；兩次都對才可以移到下一份練習。
- 家長只需看答案欄與解說欄，不必逐題講解。
本卷題目與答案由 TutorZone 團隊原創編寫，並非任何學校、出版社或考試局的試題；數值與答案均以程式核算。