中六ICT｜数据结构：阵列、连结串列、堆叠、伫列、树与图

数据结构是中六 ICT 把“资料怎样放”与“程式怎样跑得快”连起来的一章。同一个问题，用阵列与用连结串列去解，写法可以一样，但执行时间与内存相差几十倍。这一章考的不是背名称，而是用操作次数说明为什么某个结构在某个情境较快。

这一章考什么

• 线性结构：阵列索引由 0 起、内存连续；连结串列以指标串连，随机存取要逐个走，但头部插入只需改一条指标。
• 受限线性结构：堆叠后进先出，用于撤销、括号配对与深度优先搜寻；伫列先进先出，用于打印机排队与广度优先搜寻。
• 树：二元搜寻树的左子树全部小于根、右子树全部大于根，所以中序遍历必得升序；第 n 层最多 2 的 n−1 次方个节点，n 层满树共 2 的 n 次方减 1 个。
• 图：邻接矩阵占 n × n 格，查询快但稀疏图浪费；邻接表占 2E 条记录（无向图），省内存但要逐条找。

三条主线

第一条是次序：LIFO 与 FIFO 不是习惯，而是由出入口数目决定——堆叠只有一个口，所以后入先出；伫列一进一出，所以先入先出。第二条是成本：任何操作都问三个数字——要搬几多个元素、要走几多个节点、要比较几多次。第三条是退化：有序资料插入二元搜寻树会退化成链，高度由 log n 变成 n，1 000 个节点的最差搜寻由 10 次变成 1 000 次。

做题时养成三个动作：先写出资料的实际状态（push、pop 之后剩下什么），再把 Big-O 换成具体次数（n = 1 000 时 O(n²) 是一百万、O(n log n) 约一万），最后检查单位——矩阵问“格”、邻接表问“条记录”、伫列问“个元素”，三者不能混。

常见失分

• 把阵列索引当由 1 起，于是把 5 个元素的最大索引写成 5。
• 混淆 LIFO 与 FIFO，把堆叠说成先进先出。
• 以为环形伫列的元素数是 rear 减 front，忘记加 1。
• 只写“连结串列较快”而没有说明是头部插入 O(1)、随机存取 O(n)。

练习与答案

下面三份练习按难度递进，每份 10 题，附答案与一句解说，数值全部由程式计算核对，适合作为课堂后的独立练习或导师备课材料。

想找导师跟进这一章？按此登记，我们会按学生的学校进度配对导师。

常见问题

问：为什么二分搜索一定要已排序？
答：二分搜索靠“中间值大于目标就丢右半”这个判断，若资料未排序，被丢的一半可能含有答案，结果会漏找。

问：邻接矩阵与邻接表应该怎样选？
答：看图的稠密程度。100 个顶点、300 条边的图，矩阵要 10 000 格而邻接表只需 600 条记录，稀疏图用邻接表明显省位。