中文（繁體）
中文（简体）
English
中六ICT：数据结构 — 练习第四份（错题重练，10 题）
中六ICT：数据结构 — 练习第四份（错题重练，10 题）
第四份集中处理最常见的六个误解：阵列最大索引写成元素个数、把堆叠说成先进先出、环形伫列忘记加 1、合并串列多算一次比较，全部用具体数字改正。
快速答案 最大索引 5 对错误的 6；push 3、7、1 的 pop 次序为 1、7、3；环形伫列 size 8、front 2、rear 5 得 4 个；合并 8 与 5 上限 12 次；1 400 节点平衡树 11 次对线性 1 400 次；50 顶点 120 边邻接表 240 条节省 90.4%。
01 本卷资料（做完才看答案）
| 项目 | 内容 |
|---|---|
| 题数 | 10 题 |
| 建议时间 | 约 18 分钟 |
| 难度分布 | 基础 2 · 进阶 2 · 挑战 2 · 错题重练 4 |
| 对应章节 | 所属章节：中六ICT｜数据结构：阵列、连结串列、堆叠、伫列、树与图 |
| 适用年级 | 错题重练 |
02 题目（10 题）
- 基础阵列 D = [24, 6, 18, 91, 7, 45]，D[4] 是多少？这个阵列的最大索引是多少？
- 基础堆叠依次 push 12、5、9，然后 pop 一次。pop 得到什么？堆叠顶部变成什么？
- 进阶把 60、40、80、30、50、70、90 依次插入空的二元搜寻树，中序遍历结果是什么？搜寻 50 要比较几次？
- 进阶大小为 10 的环形伫列，front 索引 7、rear 索引 2，现有元素多少个？
- 挑战一棵平衡的二元搜寻树有 1 400 个节点，最差要比较多少次？同一批资料改用线性搜寻最差要多少次？
- 挑战一个有 50 个顶点、120 条边的无向图，用邻接矩阵要 2 500 格；用邻接表要多少条记录？邻接表节省多少百分比？
- 错题重练错题重练：有同学答“6 个元素的阵列最大索引是 6”。正确是什么？差多少？
- 错题重练错题重练：有同学答“堆叠是先进先出”。以 push 3、7、1 为例，正确的 pop 次序是什么？
- 错题重练错题重练：有同学用 rear 减 front 计环形伫列元素数，大小 8、front 2、rear 5 时答 3 个。正确是多少？
- 错题重练错题重练：有同学答“合并长度 8 与 5 的两条已排序串列，最多比较 13 次”。正确上限是多少？
03 答案与一句解说
| 题号 | 答案 | 一句解说 |
|---|---|---|
| 1 | D[4] = 7，最大索引是 5 | 索引由 0 起，第 5 个元素在索引 4，6 个元素的最大索引是 6 减 1 即 5。 |
| 2 | pop 得 9，顶部变成 5 | 堆叠后进先出，最后入的 9 最先出，之后 5 成为顶部，堆叠内只剩 2 个元素。 |
| 3 | 中序为 30、40、50、60、70、80、90；搜寻 50 比较 3 次 | 中序遍历必得升序；搜寻路径是 60、40、50，共三次比较。 |
| 4 | 6 个 | 由 7 数到 2 要跨过环形边界，共 6 个位置：7、8、9、0、1、2。 |
| 5 | 平衡树 11 次，线性搜寻 1 400 次 | log2(1 401) 约 10.45，向上取整得 11；线性搜寻最差要逐一比较全部 1 400 个，慢约 127 倍。 |
| 6 | 240 条记录，节省 90.4% | 无向图每条边在两端各记一次，120 × 2 得 240；(2 500 − 240) ÷ 2 500 得 90.4%。 |
| 7 | 最大索引是 5，答案大了 1 | 索引由 0 起，6 个元素的索引是 0 至 5，写成 6 就会越界。 |
| 8 | 后进先出，pop 次序为 1、7、3 | 堆叠只有一个出口，最后入的 1 先出，所以次序与入栈次序完全相反。 |
| 9 | 4 个 | front 与 rear 所指的位置本身都存放元素，要加 1，由 2 至 5 共 4 个。 |
| 10 | 12 次 | 每次比较取走一个元素，取完 12 个后最后余下的一个直接接上，故上限是 m 加 n 减 1。 |
04 做完之后怎样跟进
- 对完答案，只重做错的那几题，并在错题旁写出错在哪一步（公式、单位还是抄错数）。
- 同一题隔两日再做一次；两次都对才可以移到下一份练习。
- 家长只需看答案栏与解说栏，不必逐题讲解。
本卷题目与答案由 TutorZone 团队原创编写，并非任何学校、出版社或考试局的试题；数值与答案均以程式核算。