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