/cn-tutor-prep-s6-ict-sorting-searching-algorithms-practice-3/
/cn-tutor-prep-s6-ict-sorting-searching-algorithms-practice-3/
一般查询: info@TutorZone.com.hk
办公时间: 星期一至六 - 上午 9 时至下午 6 时
WhatsApp 星期一至日 - 24 小时
人手接听: +852 6828 1809
实时客服: +852 9061 3106

中六 ICT:排序与搜寻算法(挑战)

中六 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 题)

  1. 基础冒泡排序处理 10 笔资料,最坏情况总共比较多少次?
  2. 基础为何以 2 的次方说明二分搜寻只需 10 次就能处理 1000 笔?
  3. 基础合并排序处理 16 笔资料,分割出 4 层,若每层最多比较 16 次,总比较上限是多少?
  4. 进阶排序 3 个元素时,为何“最少 2 次比较”不足以保证排好?
  5. 进阶1000 笔已排序资料,二分搜寻一个不存在的值,最坏比较几次?与线性搜寻比较如何?
  6. 进阶选择排序处理 10 笔资料,比较次数与交换次数各是多少(最坏)?
  7. 挑战1000 笔资料用 O(n²) 与 O(n log n) 算法,运算量相差约多少倍?
  8. 挑战把 [9, 4, 6, 2] 用选择排序升序,第一轮之后的阵列是什么?
  9. 挑战为何说线性搜寻的 2 倍优势只是“单次”?资料要搜 100 次时情况如何?
  10. 错题重练错题:有人以为排序后“原本的位置”仍是同一个索引。为何会出错?

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 团队原创编写,并非任何学校、出版社或考试局的试题;数值与答案均以程式核算。

招募导师及兴趣班教练|学术、乐器、体育、艺术、STEM,免费登记,招生与配对交给平台。 了解详情 →