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

中六 ICT:排序与搜寻算法(进阶)

中六 ICT:排序与搜寻算法(进阶)

  • 2026-11-20

中六 ICT:排序与搜寻算法(进阶)

第二份做逐轮追踪与规模推算:每轮之后阵列变成怎样,规模放大到一千、一百万时比较几次。

进阶:逐轮追踪与规模推算 冒泡排序 [4, 2, 7, 1] 一轮后是 [2, 4, 1, 7];二分搜寻 1000 笔最多 10 次(2^10 = 1024),1,000,000 笔只需 20 次。插入排序 6 笔逆序比较 15 次,合并排序 8 笔分 3 层。1000 笔时线性比二分多 100 倍比较,而选择与冒泡比较次数同为 499500。

01 本卷资料(做完才看答案)

项目 内容
题数 10
建议时间 25
难度分布 基础 3 · 进阶 3 · 挑战 3 · 错题重练 1
对应章节 所属章节:中六 ICT:排序与搜寻算法
适用年级 进阶 10 题

02 题目(10 题)

  1. 基础冒泡排序 [4, 2, 7, 1] 升序,第一轮之后的阵列是什么?
  2. 基础在 1000 笔已排序资料中二分搜寻,最多比较几次?
  3. 基础在 1,000,000 笔已排序资料中二分搜寻,最多比较几次?
  4. 进阶插入排序(insertion sort)处理 6 笔逆序资料,最坏比较多少次?
  5. 进阶合并排序(merge sort)处理 8 笔资料,会分成几层(levels)?
  6. 进阶1000 笔资料,线性搜寻与二分搜寻最坏比较次数相差多少倍?
  7. 挑战同样 1000 笔资料,选择排序与冒泡排序的最坏比较次数相比如何?
  8. 挑战已排序的 [2, 5, 8, 11, 14, 17] 用二分搜寻找 11,第二次比较的是哪个元素?
  9. 挑战资料已排序,但要在 1 000 笔中找“第一个符合条件的值”,为何线性搜寻仍然合理?
  10. 错题重练错题:二分搜寻取中点时把 mid 写成 (low + high) / 2。有何问题?

03 答案与一句解说

题号 答案 一句解说
1 [2, 4, 1, 7]:4 与 2 换、7 不动、7 与 1 换。 第一轮只保证最大值 7 到位,前面三个仍未排好。
2 10 次,因为 2^10 = 1024 ≥ 1000。 只要 2 的次方覆盖 1000,就可把范围缩到单一元素。
3 20 次(2^20 = 1,048,576)。 每加一次比较,可处理的资料量翻倍,所以百万笔只需廿次。
4 15 次,即 6×5/2。 逆序时每个新元素都要比到最前,总数是 1+2+3+4+5 = 15。
5 3 层,因为每次对半分,2^3 = 8。 由 8 对半到 4、2、1,共 3 次分割,所以是 O(n log n)。
6 1000 次对 10 次,相差 100 倍。 1000/10 = 100,规模越大差距越大。
7 相同,都是 499500 次 = 1000×999/2。 两者都要两两比较找出次序,差别只在交换次数:选择排序最多 n−1 次。
8 先比 8(中点偏左),范围缩到 [11, 14, 17],第二次比 11,命中。 六个元素中点取索引 2 的 8;11 大于 8,改搜右半。
9 因为要找的是第一个符合的项目,逐个由前向后扫最直接,找到即停,不必比较大小跳跃。 二分搜寻适合“等于某值”,找第一个符合条件(如大于某门槛且最早出现)时线性扫更易写对。
10 整数索引要向下取整,正确写法是 (low + high) // 2。 用真除法会得到小数索引,多数语言会报错或截断成不可预期行为。

04 做完之后怎样跟进

  • 对完答案,只重做错的那几题,并在错题旁写出错在哪一步(公式、单位还是抄错数)。
  • 同一题隔两日再做一次;两次都对才可以移到下一份练习。
  • 家长只需看答案栏与解说栏,不必逐题讲解。

想分清冒泡、选择、插入与合并排序,并用二分搜寻取代逐个扫?预约 TutorZone 导师,二十五分钟用十题把每一步比较数算清楚。导师登记 →

本卷题目与答案由 TutorZone 团队原创编写,并非任何学校、出版社或考试局的试题;数值与答案均以程式核算。

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