中文（繁體）
中文（简体）
English
中六ICT：数据结构 — 练习第二份（进阶，10 题）
中六ICT：数据结构 — 练习第二份（进阶，10 题）
第二份练操作与成本分析：二元搜寻树中序遍历得升序、满二元树 4 层共 15 个节点、连结串列头部插入 O(1) 对阵列中间 O(n)、环形伫列 4 个元素，十题附答案与一句解说。
快速答案 中序遍历 20~80；搜寻 40 比较 3 次；树高 3；第 3 层 4 个节点；4 层满树 15 个；连结串列插入 O(1)、阵列 O(n)；环形伫列 front 2 rear 5 共 4 个；1 000 节点平均 500 次；BFS 用伫列、DFS 用堆叠。
01 本卷资料（做完才看答案）
| 项目 | 内容 |
|---|---|
| 题数 | 10 题 |
| 建议时间 | 约 20 分钟 |
| 难度分布 | 基础 2 · 进阶 3 · 挑战 3 · 错题重练 2 |
| 对应章节 | 所属章节：中六ICT｜数据结构：阵列、连结串列、堆叠、伫列、树与图 |
| 适用年级 | 进阶 |
02 题目（10 题）
- 基础把 50、30、70、20、40、60、80 依次插入二元搜寻树，中序遍历的次序是什么？
- 基础在同一棵树搜寻 40，需要比较多少个节点？
- 进阶这棵 7 节点的树高度（以节点层数计）是多少？
- 进阶一棵满二元树最深一层有 4 个节点，该层是第几层？
- 进阶一棵有 4 层的满二元树，节点总数是多少？
- 挑战在连结串列的头部插入一个节点，时间复杂度是多少？在阵列中间插入又如何？
- 挑战环形伫列大小为 8，front 索引 2、rear 索引 5，现有元素多少个？
- 挑战在 1 000 个节点的连结串列做线性搜寻，平均需要比较多少个节点？
- 错题重练错题重练：有同学答“广度优先搜寻（BFS）用堆叠实作”。正确做法是什么？
- 错题重练错题重练：有同学答“在阵列中间插入元素是 O(1)”。正确复杂度是什么？
03 答案与一句解说
| 题号 | 答案 | 一句解说 |
|---|---|---|
| 1 | 20、30、40、50、60、70、80 | 二元搜寻树的中序遍历必定由小到大。 |
| 2 | 3 个 | 路径是 50 → 30 → 40，共比较 3 次。 |
| 3 | 3 | 根在上一层，第二层有 30 与 70，第三层是 20、40、60、80。 |
| 4 | 第 3 层 | 第 n 层最多 2 的 n−1 次方个节点，2 的 2 次方等于 4。 |
| 5 | 15 个 | 2 的 4 次方减 1 等于 15，即 1+2+4+8。 |
| 6 | 连结串列 O(1)，阵列 O(n) | 连结串列改一条指标即可；阵列要搬移后面所有元素。 |
| 7 | 4 个 | 由 2 数到 5 共 4 个位置：2、3、4、5。 |
| 8 | 500 个 | 平均在串列中段找到，1 000 除以 2 得 500。 |
| 9 | BFS 用伫列，用堆叠的是深度优先搜寻（DFS） | BFS 要按层次先进先出，所以用伫列；DFS 靠后进先出回溯，所以用堆叠。 |
| 10 | O(n) | 插入位置之后的元素全部要向右移一格，最坏要搬 n 个。 |
04 做完之后怎样跟进
- 对完答案，只重做错的那几题，并在错题旁写出错在哪一步（公式、单位还是抄错数）。
- 同一题隔两日再做一次；两次都对才可以移到下一份练习。
- 家长只需看答案栏与解说栏，不必逐题讲解。
本卷题目与答案由 TutorZone 团队原创编写，并非任何学校、出版社或考试局的试题；数值与答案均以程式核算。