中六 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 题) 基础冒泡排序 [4, 2, 7, 1] 升序,第一轮之后的阵列是什么? 基础在 1000 笔已排序资料中二分搜寻,最多比较几次? 基础在 1,000,000 笔已排序资料中二分搜寻,最多比较几次? 进阶插入排序(insertion sort)处理 6 笔逆序资料,最坏比较多少次? 进阶合并排序(merge sort)处理 8 笔资料,会分成几层(levels)? 进阶1000 笔资料,线性搜寻与二分搜寻最坏比较次数相差多少倍? 挑战同样 1000 笔资料,选择排序与冒泡排序的最坏比较次数相比如何? 挑战已排序的 [2, 5, 8, 11, 14, 17] 用二分搜寻找 11,第二次比较的是哪个元素? 挑战资料已排序,但要在 1 000 笔中找“第一个符合条件的值”,为何线性搜寻仍然合理? 错题重练错题:二分搜寻取中点时把 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 团队原创编写,并非任何学校、出版社或考试局的试题;数值与答案均以程式核算。
中六 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 题) 基础冒泡排序 [4, 2, 7, 1] 升序,第一轮之后的阵列是什么? 基础在 1000 笔已排序资料中二分搜寻,最多比较几次? 基础在 1,000,000 笔已排序资料中二分搜寻,最多比较几次? 进阶插入排序(insertion sort)处理 6 笔逆序资料,最坏比较多少次? 进阶合并排序(merge sort)处理 8 笔资料,会分成几层(levels)? 进阶1000 笔资料,线性搜寻与二分搜寻最坏比较次数相差多少倍? 挑战同样 1000 笔资料,选择排序与冒泡排序的最坏比较次数相比如何? 挑战已排序的 [2, 5, 8, 11, 14, 17] 用二分搜寻找 11,第二次比较的是哪个元素? 挑战资料已排序,但要在 1 000 笔中找“第一个符合条件的值”,为何线性搜寻仍然合理? 错题重练错题:二分搜寻取中点时把 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 团队原创编写,并非任何学校、出版社或考试局的试题;数值与答案均以程式核算。