中文（繁體）
中文（简体）
English
中六ICT：数据结构 — 练习第三份（挑战，10 题）
中六ICT：数据结构 — 练习第三份（挑战，10 题）
第三份练规模与效率：100 个顶点邻接矩阵 10 000 格、300 条边邻接表 600 条记录、退化成链的二元搜寻树最差 10 次、合并 500 与 300 条串列最差 799 次比较，十题附答案与一句解说。
快速答案 邻接矩阵 100×100=10 000；无向图 300 条边 600 条记录；退化树高 10 最差 10 次；平衡 1 000 节点最差 10 次；31 节点 5 层；合并 799 次；负载因子 1.0；8−3+2=7；n² 一百万对 n log n 约 9 966；二分 10 次对线性 999 次。
01 本卷资料（做完才看答案）
| 项目 | 内容 |
|---|---|
| 题数 | 10 题 |
| 建议时间 | 约 25 分钟 |
| 难度分布 | 基础 1 · 进阶 2 · 挑战 3 · 错题重练 4 |
| 对应章节 | 所属章节：中六ICT｜数据结构：阵列、连结串列、堆叠、伫列、树与图 |
| 适用年级 | 挑战 |
02 题目（10 题）
- 基础一个有 100 个顶点的图用邻接矩阵储存，共需要多少格？
- 进阶一个有 100 个顶点、300 条边的无向图用邻接表储存，共需多少条记录？
- 进阶把 10、20、30…100 依次插入二元搜寻树，树高是多少？最差搜寻要比较多少次？
- 挑战一棵平衡的二元搜寻树有 1 000 个节点，最差搜寻需要比较多少次？
- 挑战一棵有 31 个节点的满二元树，高度（层数）是多少？
- 挑战合并两个已排序的串列，长度分别为 500 与 300，最多需要比较多少次？
- 错题重练错题重练：1 000 笔记录存入 1 000 个桶的杂凑表，负载因子是多少？
- 错题重练错题重练：连续 push 8 个元素，再 pop 3 个，再 push 2 个，堆叠内有多少个元素？
- 错题重练错题重练：有同学答“O(n²) 算法在 1 000 笔资料上比 O(n log n) 快”。用数字说明为何错。
- 错题重练错题重练：有同学答“在已排序阵列上线性搜寻与二分搜索同为 O(n)”。正确是什么？
03 答案与一句解说
| 题号 | 答案 | 一句解说 |
|---|---|---|
| 1 | 10 000 格 | 邻接矩阵是 n × n，100 × 100 等于 10 000。 |
| 2 | 600 条 | 无向图每条边在两端各记一次，300 × 2 等于 600。 |
| 3 | 高度 10，最差 10 次 | 每次插入都只往右走，树退化成单边链，等同线性搜寻。 |
| 4 | 10 次 | 平衡树高度约 log2(1001)，向上取整得 10。 |
| 5 | 5 层 | 2 的 5 次方减 1 等于 31，所以共 5 层。 |
| 6 | 799 次 | 最坏情况每次只取一个，取完 799 个后最后一个直接接上。 |
| 7 | 1.0 | 负载因子等于记录数除以桶数，1 000 ÷ 1 000 等于 1.0。 |
| 8 | 7 个 | 8 减 3 加 2 等于 7，push 与 pop 各自只改动一个元素。 |
| 9 | O(n²) 约 1 000 000 次，O(n log n) 约 9 966 次，慢约 100 倍 | 1 000 的平方是一百万，1 000 × log2(1 000) 约 9 966，相差约 100 倍。 |
| 10 | 线性搜寻 O(n) 最差 999 次，二分搜索 O(log n) 最差 10 次 | 二分搜索每步减半，1 000 笔只需约 10 次比较。 |
04 做完之后怎样跟进
- 对完答案，只重做错的那几题，并在错题旁写出错在哪一步（公式、单位还是抄错数）。
- 同一题隔两日再做一次；两次都对才可以移到下一份练习。
- 家长只需看答案栏与解说栏，不必逐题讲解。
本卷题目与答案由 TutorZone 团队原创编写，并非任何学校、出版社或考试局的试题；数值与答案均以程式核算。