#线性表与栈队列 章节测

范围：线性表（顺序表/链表）、栈、队列和数组（含特殊矩阵压缩存储）。说明：本卷共 20 题，全部单选，全部为模拟题（非真题），细节题为主，风格对齐 408 统考选择题。限时 40 分钟。答案与解析见文末，做完前不要下翻。

#第 1 题

设顺序表长度为 $$，在各位置等概率插入一个新元素，平均需要移动的元素个数为（ ）

A. $$ B. $$ C. $$ D. $$

#第 2 题

用头插法建立单链表（带头结点），依次读入数据 1、2、3、4，建表完成后从首元结点开始的数据序列为（ ）

A. 1 2 3 4 B. 4 3 2 1 C. 1 4 3 2 D. 2 1 4 3

#第 3 题

在双链表中结点 p 之后插入结点 s，下列语句序列正确的是（ ）

A. p->next = s; s->next = p->next; s->prior = p; p->next->prior = s; B. s->next = p->next; p->next->prior = s; s->prior = p; p->next = s; C. s->prior = p; p->next = s; s->next = p->next; p->next->prior = s; D. s->next = p->next; p->next = s; s->prior = p; p->next->prior = s;

#第 4 题

对只设尾指针 r（不设头指针）的带头结点循环单链表，下列操作中时间复杂度仍为 $$ 的是（ ）

A. 在表头插入结点 B. 在表尾插入结点 C. 删除表头结点 D. 删除表尾结点

#第 5 题

下列关于顺序表和单链表的说法中，错误的是（ ）

A. 顺序表支持随机存取，单链表只能顺序存取 B. 单链表插入、删除结点的时间复杂度为 $$ C. 顺序表的存储密度为 1，单链表的存储密度小于 1 D. 单链表逻辑相邻的元素物理上不一定相邻

#第 6 题

下列关于静态链表的说法中，正确的是（ ）

A. 插入和删除元素不需要移动元素，仅修改游标 B. 支持随机存取，按位查找为 $$ C. 存储密度高于顺序表 D. 指针域存储的是结点的物理内存地址

#第 7 题

设顺序表长度为 $$，删除第 $$ 个元素需要向前移动的元素个数为（ ）

A. $$ B. $$ C. $$ D. $$

#第 8 题

元素 1、2、3、4、5 依次进栈（进栈和出栈操作可以交替进行），下列出栈序列中不可能的是（ ）

A. 2 1 4 3 5 B. 3 2 5 4 1 C. 4 3 5 1 2 D. 1 5 4 3 2

#第 9 题

4 个不同元素依次进栈，可能的出栈序列个数为（ ）

A. 24 B. 17 C. 14 D. 10

#第 10 题

两个栈共享一个数组空间 S[0..m-1]，栈 1 栈底在下标 0 处，栈 2 栈底在下标 m-1 处，top1 初值 -1，top2 初值 m。判断共享栈已满的条件是（ ）

A. top1 == top2 B. top1 + 1 == top2 C. top1 + top2 == m D. top2 - top1 == 0

#第 11 题

循环队列存储于数组 Q[0..m-1]，采用牺牲一个存储单元的方法（front == rear 为空，(rear+1) % m == front 为满），该队列最多能存放的元素个数为（ ）

A. $$ B. $$ C. $$ D. 与入队出队顺序有关

#第 12 题

循环队列采用带 tag 标记的方案区分队空与队满，tag 为 0 表示最近一次操作为出队，tag 为 1 表示最近一次操作为入队。判断队满的条件是（ ）

A. front == rear && tag == 0 B. front == rear && tag == 1 C. (rear + 1) % MaxSize == front D. front == rear 即可，无需 tag

#第 13 题

循环队列存储于数组 Q[0..7]（MaxSize = 8），牺牲一格方案，rear 指向队尾元素的下一位置。当前 front = 6，rear = 2，队列中元素个数为（ ）

A. 3 B. 4 C. 5 D. 6

#第 14 题

中缀表达式 A + B * (C - D) - E / F 对应的后缀表达式是（ ）

A. A B C D - * + E F / - B. A B + C D - * E F / - C. A B C D - * E F / - + D. A B + C - D * E F / -

#第 15 题

对长度为 $$ 的有序表进行折半查找（递归实现），递归调用的最大深度为（ ）

A. $$ B. $$ C. $$ D. $$

#第 16 题

下列应用场景中，最适合采用队列作为核心数据结构的是（ ）

A. 括号匹配检验 B. 中缀表达式转后缀表达式 C. 操作系统设备缓冲区的先来先服务处理 D. 函数递归调用的实现

#第 17 题

将 $$ 阶对称矩阵 $$ 按行优先压缩存储下三角部分（含对角线）到一维数组 $$（下标从 0 起），矩阵下标从 1 起，则 $$ 在 $$ 中的下标为（ ）

A. 7 B. 8 C. 9 D. 10

#第 18 题

6 阶三对角矩阵（带状矩阵）按行优先压缩存储（仅存非零元，下标从 0 起，矩阵下标从 1 起），则 $$ 的存储下标为（ ）

A. 10 B. 11 C. 12 D. 13

#第 19 题

C 语言二维数组 int A[8][10]（行优先存储，A 首地址为 1000，sizeof(int) = 4），元素 A[3][5] 的地址为（ ）

A. 1120 B. 1132 C. 1140 D. 1156

#第 20 题

稀疏矩阵采用三元组顺序表（行、列、值）压缩存储后，下列说法错误的是（ ）

A. 节省了存储空间（非零元很少时） B. 失去了随机存取特性，取任意元素需在三元组中查找 C. 任意两个非零元的三元组按行优先排列 D. 按行求和的效率一定高于原二维数组存储方式

#答案与解析

#第 1 题：B

• 考点标签：顺序表插入移动次数
• 难度：易
• 解析：第 $$ 位插入移动 $$ 个，等概率下 $$。
• 错因提醒：分母是 $$（有 $$ 个可插入位置），误用 $$ 得 $$ 选 A；混淆插入与删除（删除是 $$）。

#第 2 题：B

• 考点标签：单链表头插法建表
• 难度：易
• 解析：头插法每读一个数就插在头结点之后，先读的被不断后推，最终序列与读入顺序相反。
• 错因提醒：把头插法与尾插法弄混选 A；头插法逆序这一结论同时是"就地逆置链表"算法的原理，注意迁移。

#第 3 题：B

• 考点标签：双链表插入的指针操作顺序
• 难度：中
• 解析：必须先让 s->next 挂上 p 的后继，再让后继的 prior 回指 s，然后接 s 与 p 的双向关系，最后才改 p->next（改早了 p->next 就不再是原后继）。
• 错因提醒：A 的第一步就覆盖 p->next，原后继失联；D 在第 2 步覆盖 p->next 后，第 4 步 p->next->prior 已是 s->prior 方向错误；C 的 p->next = s 先执行导致 s->next = p->next 变成自指。判断口诀：先连新结点与两侧，最后改原链断点。

#第 4 题：D

• 考点标签：循环单链表尾指针的复杂度
• 难度：中
• 解析：头结点为 r->next，表头插入/删除都是 $$；表尾插入（在 r 后接新结点，新结点成为尾）$$；删除表尾结点需修改其前驱的 next 与尾指针，单链表找不到前驱，只能从 r->next 绕一圈遍历，$$。
• 错因提醒：误以为"设了尾指针"就一切尾操作 $$——删除尾必须拿前驱，这正是双链表/循环双链表存在的理由。

#第 5 题：B

• 考点标签：顺序表与链表的复杂度对比
• 难度：易
• 解析：$$ 的前提是插入删除位置已确定（已持有指向前驱的指针）；若含按位查找定位过程，总体仍是 $$。
• 错因提醒：这是 408 高频陷阱表述，"链表插删 O(1)"默认不含查找成本，选项故意省略前提，审题时要识别绝对化表述。

#第 6 题：A

• 考点标签：静态链表特性
• 难度：易
• 解析：静态链表用数组下标（游标）代替指针，插入删除只改游标不搬数据；但按位查找仍需沿游标链走 $$，且游标开销使存储密度低于顺序表。
• 错因提醒：B/D 是把"链表"特征（顺序存取、逻辑指针）与"数组"特征（随机存取、物理地址）错误拼接的干扰项。

#第 7 题：A

• 考点标签：顺序表删除移动次数
• 难度：易
• 解析：删除第 $$ 个元素后，第 $$ 到第 $$ 个元素整体前移一格，共 $$ 个。
• 错因提醒：插入是 $$、删除是 $$，选择题常把两个公式放进同一组选项；代入特例（$$ 时删除移动 0 个）快速排除。

#第 8 题：C

• 考点标签：出栈序列合法性
• 难度：中
• 解析：模拟法。4 3 5 1 2：压 1、2、3、4，弹 4、3，压 5，弹 5，此时栈内从底到顶为 1、2，下一个出栈必须是 2，不可能是 1，故 C 不可能。A/B/D 均可模拟通过。
• 错因提醒：判断标准可记为"出栈序列中，某数之后所有比它小的数必须降序排列"；C 中 5 之后的 1、2 是升序，直接判定非法。

#第 9 题：C

• 考点标签：卡特兰数
• 难度：中
• 解析：$$ 个元素依次进栈的出栈序列数为卡特兰数 $$，$$ 时 $$。
• 错因提醒：24（全排列 $$）是不考虑合法性的干扰项；42 是 $$ 的卡特兰数；记住 1、2、5、14、42 这个数列，考场上直接引用。

#第 10 题：B

• 考点标签：共享栈判满
• 难度：中
• 解析：两栈顶相邻（top1 + 1 == top2）时数组无空位，判满。
• 错因提醒：top1 == top2 时两栈顶已指向同一单元、发生重叠，是"晚一步"的判断；top1 + top2 == m - 2 才是与 B 等价的写法，选项 C 的 == m 不对。

#第 11 题：B

• 考点标签：循环队列牺牲一格方案
• 难度：易
• 解析：留出 rear 指向的单元不用以区分队空与队满，容量为 $$。
• 错因提醒："数组大小 m 存 m-1 个"是固定结论；若题面改为 tag 方案或计数器方案，答案就是 $$，注意看清方案再答。

#第 12 题：B

• 考点标签：循环队列 tag 方案
• 难度：中
• 解析：入队导致 front == rear 只可能是从非满状态又压入一格，即队满；出队导致 front == rear 只可能是队空。tag 记录"最近一次操作方向"。
• 错因提醒：C 是牺牲一格方案的判满条件，不能与 tag 方案混用；tag 方案下队列可存满 MaxSize 个元素，与第 11 题对照记忆。

#第 13 题：B

• 考点标签：循环队列元素个数计算
• 难度：中
• 解析：$$。
• 错因提醒：rear < front 时直接相减得负数，忘记加 MaxSize 再取模是高频计算失误；也可用"从 front 走到 rear"数格子验证：6→7→0→1→2 共 4 个元素。

#第 14 题：A

• 考点标签：中缀转后缀
• 难度：中
• 解析：C - D 先成 C D -，B * (C D -) 得 B C D - *，A + 上述 得 A B C D - * +，E / F 得 E F /，最后减法按同级左结合拼接为 A B C D - * + E F / -。
• 错因提醒：减法、除法不满足交换律，操作数顺序绝不能颠倒；B 错在把 A + 也提前结合；C 错在最后的 - 抢在 + 之前。

#第 15 题：B

• 考点标签：递归栈深度
• 难度：易
• 解析：折半查找每层规模减半，递归深度为 $$ 量级，即 $$；递归空间复杂度等于最大递归深度。
• 错因提醒：递归空间看深度不看调用总次数；对比记忆：对链表顺序查找的递归深度是 $$。

#第 16 题：C

• 考点标签：队列应用场景
• 难度：易
• 解析：先来先服务/公平排队是队列的典型语义；A、D 依赖后进先出/回溯用栈；B 的运算符管理用栈（操作数输出）。
• 错因提醒：B 具有迷惑性——转后缀时输出操作数像流水线，但核心控制结构是运算符栈；判断时抓"元素出结构的顺序"。

#第 17 题：B

• 考点标签：对称矩阵压缩存储下标
• 难度：中
• 解析：$$。
• 错因提醒：前 $$ 行共 $$ 个元素（$$），部分同学代成 $$（前 $$ 行）得 9 选 C；先用存序 a11, a21, a22, a31, a32, a33, a41, a43 数格子验证：a43 前有 8 个元素，下标 8。

#第 18 题：B

• 考点标签：三对角矩阵压缩存储
• 难度：难
• 解析：公式 $$。推导：前 4 行非零元 $$ 个（$$），$$ 是第 5 行第 1 个，$$。
• 错因提醒：第 1 行只有 2 个非零元（没有 $$），算前若干行总数时容易漏减；遇到反向问题（给 $$ 求元素）用 $$ 加 $$ 联立验证。

#第 19 题：C

• 考点标签：二维数组地址计算
• 难度：中
• 解析：行优先，偏移 $$，地址 $$。
• 错因提醒：列数是第二维大小 10，误用 8 算得 $$（不在选项）或错按列优先计算；C 语言行优先且下标从 0 起，若题面给 Fortran 或下标从 1 起的数组要先归一化。

#第 20 题：D

• 考点标签：稀疏矩阵三元组存储
• 难度：中
• 解析：按行求和时，行内非零元在三元组中连续存放，但整行扫描仍需遍历三元组，且要判断行号是否切换；零元素多时总遍历量小于 $$，但"一定高于原数组"的绝对化说法不成立（非零元接近 $$ 时三元组反而更长）。
• 错因提醒：A/B/C 均为三元组存储的正确性质；选择题问"错误"时，优先扫绝对化措辞（"一定""必然""任何情况下"）。

#订正记录

做完后，将错题按规范登记到 00-错题本，错因分类必须四选一：概念不清 / 计算失误 / 审题偏差 / 技巧缺失。