中六 ICT:排序與搜尋演算法(挑戰) 2026-11-20 導師備課指引 · 小學數學 中六 ICT:排序與搜尋演算法(挑戰) 第三份處理複雜度與資訊理論下限:為何 3 個元素最少要 3 次比較,n² 與 n log n 差幾倍。 挑戰:複雜度與比較下限 10 筆冒泡最壞比較 45 次;16 筆合併排序 4 層、上限 64 次;1000 筆時 O(n²) 約 499500 次對 O(n log n) 約 10000 次,相差約 50 倍。3 個元素有 6 種排列,2 次比較只能分辨 4 種,所以最少要 3 次(2³ = 8)。選擇排序 10 筆比較 45 次但只換 9 次。 01 本卷資料(做完才看答案) 項目 內容 題數 10 建議時間 25 難度分佈 基礎 3 · 進階 3 · 挑戰 3 · 錯題重練 1 對應章節 所屬章節:中六 ICT:排序與搜尋演算法 適用年級 挑戰 10 題 02 題目(10 題) 基礎冒泡排序處理 10 筆資料,最壞情況總共比較多少次? 基礎為何以 2 的次方說明二分搜尋只需 10 次就能處理 1000 筆? 基礎合併排序處理 16 筆資料,分割出 4 層,若每層最多比較 16 次,總比較上限是多少? 進階排序 3 個元素時,為何「最少 2 次比較」不足以保證排好? 進階1000 筆已排序資料,二分搜尋一個不存在的值,最壞比較幾次?與線性搜尋比較如何? 進階選擇排序處理 10 筆資料,比較次數與交換次數各是多少(最壞)? 挑戰1000 筆資料用 O(n²) 與 O(n log n) 演算法,運算量相差約多少倍? 挑戰把 [9, 4, 6, 2] 用選擇排序升序,第一輪之後的陣列是什麼? 挑戰為何說線性搜尋的 2 倍優勢只是「單次」?資料要搜 100 次時情況如何? 錯題重練錯題:有人以為排序後「原本的位置」仍是同一個索引。為何會出錯? 03 答案與一句解說 題號 答案 一句解說 1 45 次 = 10×9/2。 每輪少一次比較:9+8+…+1 = 45,代入公式 n(n−1)/2 一致。 2 因為 2^10 = 1024 ≥ 1000,10 次減半後範圍必定只剩 1 筆。 每次比較令候選數目減半,k 次比較最多處理 2^k 筆。 3 64 次,即 16 × 4。 4 層 × 每層 16 = 64,正是 n log n 的量級。 4 3 個元素有 6 種排列,2 次比較只分辨 2² = 4 種結果,資訊不足。 比較結果只有二元,k 次比較最多分辨 2^k 種情況,故至少需 3 次(2³ = 8 ≥ 6)。 5 二分仍是最多 10 次;線性要 1000 次,相差 100 倍。 找不到時二分一樣每次減半,最終 low > high 才停,次數不變。 6 比較 45 次,交換最多 9 次。 比較固定是 n(n−1)/2 = 45;交換每次最多把一個元素放好,故 9 次。 7 O(n²) 約 499500 次,O(n log n) 約 10000 次,相差約 50 倍。 499500 ÷ 10000 ≈ 50,規模再大差距會繼續擴大。 8 [2, 4, 6, 9]:最小 2 與首位 9 交換。 選擇排序每輪找最小值放到已排序區末端,第一輪後首個元素已確定。 9 單次差 2 倍不大;但排序一次後搜 100 次,二分總成本遠低於 100 次全掃。 8 筆時 8 對 3 只差 2 倍,規模細時排序成本(約 20 次比較)可能不划算,所以要看 n 與搜尋次數。 10 排序會改變元素的位置,索引隨之改變;要保留原位置須另存一欄(如學號)。 常見錯誤是用排序後的索引去對應原資料,結果配錯人。 04 做完之後怎樣跟進 對完答案,只重做錯的那幾題,並在錯題旁寫出錯在哪一步(公式、單位還是抄錯數)。 同一題隔兩日再做一次;兩次都對才可以移到下一份練習。 家長只需看答案欄與解說欄,不必逐題講解。 想分清冒泡、選擇、插入與合併排序,並用二分搜尋取代逐個掃?預約 TutorZone 導師,二十五分鐘用十題把每一步比較數算清楚。導師登記 → 本卷題目與答案由 TutorZone 團隊原創編寫,並非任何學校、出版社或考試局的試題;數值與答案均以程式核算。
中六 ICT:排序與搜尋演算法(挑戰) 2026-11-20 導師備課指引 · 小學數學 中六 ICT:排序與搜尋演算法(挑戰) 第三份處理複雜度與資訊理論下限:為何 3 個元素最少要 3 次比較,n² 與 n log n 差幾倍。 挑戰:複雜度與比較下限 10 筆冒泡最壞比較 45 次;16 筆合併排序 4 層、上限 64 次;1000 筆時 O(n²) 約 499500 次對 O(n log n) 約 10000 次,相差約 50 倍。3 個元素有 6 種排列,2 次比較只能分辨 4 種,所以最少要 3 次(2³ = 8)。選擇排序 10 筆比較 45 次但只換 9 次。 01 本卷資料(做完才看答案) 項目 內容 題數 10 建議時間 25 難度分佈 基礎 3 · 進階 3 · 挑戰 3 · 錯題重練 1 對應章節 所屬章節:中六 ICT:排序與搜尋演算法 適用年級 挑戰 10 題 02 題目(10 題) 基礎冒泡排序處理 10 筆資料,最壞情況總共比較多少次? 基礎為何以 2 的次方說明二分搜尋只需 10 次就能處理 1000 筆? 基礎合併排序處理 16 筆資料,分割出 4 層,若每層最多比較 16 次,總比較上限是多少? 進階排序 3 個元素時,為何「最少 2 次比較」不足以保證排好? 進階1000 筆已排序資料,二分搜尋一個不存在的值,最壞比較幾次?與線性搜尋比較如何? 進階選擇排序處理 10 筆資料,比較次數與交換次數各是多少(最壞)? 挑戰1000 筆資料用 O(n²) 與 O(n log n) 演算法,運算量相差約多少倍? 挑戰把 [9, 4, 6, 2] 用選擇排序升序,第一輪之後的陣列是什麼? 挑戰為何說線性搜尋的 2 倍優勢只是「單次」?資料要搜 100 次時情況如何? 錯題重練錯題:有人以為排序後「原本的位置」仍是同一個索引。為何會出錯? 03 答案與一句解說 題號 答案 一句解說 1 45 次 = 10×9/2。 每輪少一次比較:9+8+…+1 = 45,代入公式 n(n−1)/2 一致。 2 因為 2^10 = 1024 ≥ 1000,10 次減半後範圍必定只剩 1 筆。 每次比較令候選數目減半,k 次比較最多處理 2^k 筆。 3 64 次,即 16 × 4。 4 層 × 每層 16 = 64,正是 n log n 的量級。 4 3 個元素有 6 種排列,2 次比較只分辨 2² = 4 種結果,資訊不足。 比較結果只有二元,k 次比較最多分辨 2^k 種情況,故至少需 3 次(2³ = 8 ≥ 6)。 5 二分仍是最多 10 次;線性要 1000 次,相差 100 倍。 找不到時二分一樣每次減半,最終 low > high 才停,次數不變。 6 比較 45 次,交換最多 9 次。 比較固定是 n(n−1)/2 = 45;交換每次最多把一個元素放好,故 9 次。 7 O(n²) 約 499500 次,O(n log n) 約 10000 次,相差約 50 倍。 499500 ÷ 10000 ≈ 50,規模再大差距會繼續擴大。 8 [2, 4, 6, 9]:最小 2 與首位 9 交換。 選擇排序每輪找最小值放到已排序區末端,第一輪後首個元素已確定。 9 單次差 2 倍不大;但排序一次後搜 100 次,二分總成本遠低於 100 次全掃。 8 筆時 8 對 3 只差 2 倍,規模細時排序成本(約 20 次比較)可能不划算,所以要看 n 與搜尋次數。 10 排序會改變元素的位置,索引隨之改變;要保留原位置須另存一欄(如學號)。 常見錯誤是用排序後的索引去對應原資料,結果配錯人。 04 做完之後怎樣跟進 對完答案,只重做錯的那幾題,並在錯題旁寫出錯在哪一步(公式、單位還是抄錯數)。 同一題隔兩日再做一次;兩次都對才可以移到下一份練習。 家長只需看答案欄與解說欄,不必逐題講解。 想分清冒泡、選擇、插入與合併排序,並用二分搜尋取代逐個掃?預約 TutorZone 導師,二十五分鐘用十題把每一步比較數算清楚。導師登記 → 本卷題目與答案由 TutorZone 團隊原創編寫,並非任何學校、出版社或考試局的試題;數值與答案均以程式核算。