Relax1000 数据结构 · 第3、4章 栈、队列、数组、字符串 · 解析

题号查询 · 同章题目

第3、4章 栈、队列、数组、字符串

本章 64 题；解析册印刷页 15–26。

速对答案（原书）： B D B B B C B B C A B B B A B A D B D C C D D C A D C D B A C A D A A C C D C A B C C A B A C A C B C C C C D B C B D C C D C B

Q1

速对表原值： B

详细解析标注： B

对于链队，进队操作是在队尾插入节点，出队操作是删除队首节点。对于带队首指针 f 和队尾指针 r 的非循环单链表，这两种操作的时间复杂度均为 0(1)，所以本题答案为 B。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q2

速对表原值： D

详细解析标注： D

根据题意，push 后，栈顶指针+1，pop 后指针-1，而 push 操作 6 次，pop 操作 2次，相差 4 次，所以操作完成后，指针净增+4，由于是 16 进制，结果指针为 100AH，答案选 D。

返回题目

Q3

速对表原值： B

详细解析标注： B

A 选项得到的出栈序列是“2341”，C 选项得到的是“3214”，D 选项得到的是“1342”。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q4

速对表原值： B

详细解析标注： B

sp 指向栈顶元素，栈往高地址增长，所以要入栈需使 sp 先加 1，指向空的位置在进行插入。符合逻辑的是 B。如果 sp 指向栈顶元素的下一个空闲位置，那么答案就是 A。此外，如果给出空栈的栈顶指针是-1，等价于栈顶指针指向栈顶元素。初始为 0，等价指向栈顶元素的下一个空闲位置。

返回题目

Q5

速对表原值： B

详细解析标注： B

第k个出栈元素是“1”，那么前面k个元素一定是1～k，也就是1～k-1个位置包括2～k 一共 k-1 个元素，否则元素超过 k 个，栈底的“1”在位置 k 一定出不来。剩余的 k+1～n 一共 n-k 个元素进行入栈和出栈，k+1 个位置的不同元素可能个数也就变成了，k+1～n 依次入栈，第一个出栈的元素可能个数，易知任何一个都可能在第一个出栈，都有其对应的合法操作，答案选 B。

返回题目

Q6

速对表原值： C

详细解析标注： C

容易推得当〔公式/符号见原页版面片段〕 = 1 时，入栈顺序可以是 i, i-1, ..., 1；然后，依次从栈顶出栈。这样可以推得 1 能够在任意位置。反过来思考这道题，当〔公式/符号见原页版面片段〕 = 1 时，〔公式/符号见原页版面片段〕1, 〔公式/符号见原页版面片段〕2, ..., 〔公式/符号见原页版面片段〕−1的所有可能，一定是由 2，3，...，i-1，i 共计 i-1个元素构成的不同的出栈序列状态，i 的位置右边刚好是 i+1, i+2, ..., n 共 n-i-2 个元素构成的不同出栈序列个数，那我们设 n 个元素的出栈序列个数为 H(n)。当 1 在 i=1 的位置上时，左边 0 个元素，右边 2～n 共 n-1 个元素，出栈序列有 H(0)H(n-1)当 1 在 i=2 的位置上时，左边一定是 2，共 1 个元素，右边 3～n 共 n-2 个元素，出栈序列有 H(1)H(n-2) ...当 1 在 i=n 的位置上时，左边 2～n 共 n-1 个元素，右边 0 个元素，出栈序列有 H(n-1)*H(0)所以 n 个元素的不同出栈序列个数总数〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕 0 ∗ 〔公式/符号见原页版面片段〕 − 1 + 〔公式/符号见原页版面片段〕 1 ∗ 〔公式/符号见原页版面片段〕 − 2 + ... + 〔公式/符号见原页版面片段〕 − 1 ∗ 〔公式/符号见原页版面片段〕 0 =〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕+1这就是我们的卡特兰数，上述就是他的递推过程。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q7

速对表原值： B

详细解析标注： B

I 正确，P1=1，P2=3，此时栈里还有元素 2，P3 的取值可以是 2,4,5,...,n 共 n-2 种。II 正确，P1=2，P2=3，此时栈里还有元素 1，P3 的取值可以是 1,4,5,...,n 共 n-2 种。III 错误，P1=4，P2=3，此时栈里还有元素 1，2；P3 的取值可以是 2,5,...,n 共 n-3 种。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q8

速对表原值： B

详细解析标注： B

此题答案是 n=4 的卡特兰数证 明 方 法 一 ： 利 用 卡 特 兰 数 的 递 推 式 ： 〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕 0 〔公式/符号见原页版面片段〕 − 1 + 〔公式/符号见原页版面片段〕 1 〔公式/符号见原页版面片段〕 − 2 + ... + 〔公式/符号见原页版面片段〕 − 1 〔公式/符号见原页版面片段〕 0 =〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕+1当元素 1 放在出栈序列第 k 个位置时，前面 k-1 个位置一定是 2～k 共计 k-1 个元素的出栈排列个数H(k-1)，右边位置是 k+1～n 共计 n-k 个元素的出栈序列排列个数 H(n-k)，由此得到上述递推式。证明方法二：网格法，〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕+1 = 〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕 − 〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕−1入栈操作为横坐标，出栈操作为纵坐标，n 次入栈+n 次出栈操作即从原点出发到(n,n)的路径个数，即 2n 次操作里面选择 n 次入栈（剩下的是出栈）的可能数，即〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕，但是每个时刻，出栈次数不能比入栈次数多，否则就是不合法。如下图，我们可以知道，不合法的操作路径，一定会触碰 y=x+1 到达(n, n)，而这样的路径经过 y=x+1 反射都会到达点（n-1, n+1），所以所有不合法的路径即从原点出发到点(n-1, n+1)的所有路径数量。综合以上，合法操作路径条数=〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕 − 〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕−1 =〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕+1（只要触碰到 y=x+1 说明当前状态出栈比入栈次数多，非法序列），补充：出栈序列为 12...n 的入栈序列个数？逆向思维，根据上述网格法，其实合法序列就是不同的路径的条数，每一条路径的出栈出栈次序有差异，得到的出栈序列也有差异，那么我们固定出栈序列，通过路径还原成入栈序列，肯定也是不同的。所以结果还是卡特兰数。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q9

速对表原值： C

详细解析标注： C

若栈容量为 4，则不同出栈序列数为卡特兰数〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕+1，n=4 时经计算为 14。但题目容量限制为 3，则仅 4, 3, 2, 1 出栈序列需要栈的容量为 4，无法实现，故不同的出栈序列数量为 14-1=13。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q10

速对表原值： A

详细解析标注： A

当 Pn=1 时，进栈序列是 P1, P2, P3, …, 1，由输出序列可知，P1, P2, P3, …, Pn 依次进栈，然后依次出栈，即 P(n-1)=2, P(n-2)=3, …, P1=n，也就是说 Pi=n - i + 1。所以本题答案为 A。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q11

速对表原值： B

详细解析标注： B

可以模拟各个选项，对于 B，必须先将 1.2.3 入栈，然后先后出栈 3.2，栈中剩1，下一个出栈元素为 5，所以需要将 4.5 先后入栈，此时栈中元素有 1, 4, 5，出栈 5，栈内元素有1，4，下一个出栈元素为 4，但是选项中是 1，所以无法实现，故选 B。

返回题目

Q12

速对表原值： B

详细解析标注： B

本题要求出栈序列以 d 开头，则 a，b，c，d4 个元素需要依次进行入栈操作，然后 d 出栈，栈中元素还剩 a，b，c，且 a，b，c 三个元素的出栈序列固定为 c，b，a，所以只有 e 元素的出栈序列位置没有固定，即可以在 d 出栈后、e 进栈后直接出栈，出栈序列为 d，e，c，b，a；也可以在 d 出栈后，c 出栈，e 再进栈后直接出栈，出栈序列为 d，c，e，b，a；同理可得 e 元素可以在 b 或 a出栈之后再进行入栈和出栈操作，所以本题以元素 d 开头的序列个数是 4。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q13

速对表原值： B

详细解析标注： B

上溢是指存储器满，还往里写；下溢是指存储器空，还往外读。为了解决上溢，可给栈分配很大的存储空间，但这样又会造成存储空间的浪费。共享栈的提出就是为了在解决上溢的基础上节省存储空间，将两个栈放在同一段更大的存储空间内，这样，当一个栈的元素增加时，可使用另一个栈的空闲空间，从而降低发生上溢的可能性。

返回题目

Q14

速对表原值： A

详细解析标注： A

可举例子自行模拟。读者可以思考若 top1 的初值为 0，top2 的初值为 n-1 时栈满的条件。

注意：栈顶、队头与队尾的指针的定义是不唯一的，做题时务必仔细审题和思考

返回题目

Q15

速对表原值： B

详细解析标注： B

通过一个运算符栈将中缀表达式转换为后缀表达式。本题答案为 B。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q16

速对表原值： A

详细解析标注： A

ABCD+-E+ ---> (AB * CD+-)+E ---> (AB-(C+D))+E ---> (A*B-(C+D))+E ---> 40-(6+4)+15 = 45。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q17

速对表原值： D

详细解析标注： D

题干的后缀表达式转换成中缀表达式为：((58)((27)-4))+8=4010+8=408，答案选 D。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q18

速对表原值： B

详细解析标注： B

利用栈求表达式的值时，可以分别设立运算符栈和运算数栈，其原理不变。选项B 中 A 入栈，B 入栈，计算得 R1，C 入栈，计算得 R2，D 入栈，计算得 R3，由此得深为 2。A、C、D 依次计算得栈深为 4、3、3。因此选 B。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q19

速对表原值： D

详细解析标注： D

四个选项的出入栈如图所示。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q20

速对表原值： C

详细解析标注： C

我们要知道一个原则，在中缀表达式里面，操作符的优先级在同级情况下，左边的比右边的优先级高，而前缀用栈模拟过程中：

• 操作数直接输出（从右往左输出）

• 右括号直接入栈

• 其他运算符入栈前，要比较和栈顶运算符的优先级，只有比栈顶优先级大，才入栈，否则出栈到栈顶运算符优先级比当前小，或者栈空为止，再入栈当前操作符。

• 若是左括号，那就出栈到对应右括号为止。输入符号 栈 输出c c - - c b - bc + + - bc a + - abc结束 -+abc

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q21

速对表原值： C

详细解析标注： C

【方法一】括号法按运算顺序添加括号：((a * ( b + c )) - d)，按计算顺序依次把括号内的运算符提到括号外，再去掉括号

① 括号先算：(b + c) → 前缀是 + b c

② 然后：(a * (b + c)) → 前缀是 * a + b c

③ 最后：* a + b c - d → 前缀是 - * a + b c d【方法二】栈模拟，参考上题。

返回题目

Q22

速对表原值： D

详细解析标注： D

A 错误，在实现函数调用和递归过程中，通常使用栈来存储局部变量和返回地址；

B 错误，BFS 中用队列作为辅助数据结构；

C 错误，括号匹配通常采用栈作为辅助数据结构

返回题目

Q23

速对表原值： D

详细解析标注： D

删除操作虽然发生在队头，但是若当前队列只有一个数据元素时，则队头也是队尾。考虑到这种特殊情况，删除操作也会带来队尾的改变。

返回题目

Q24

速对表原值： C

详细解析标注： C

初始状态为 front=rear=NULL 说明是不带头结点的链队列：入队列，rear+1，front 不变；出队列，front+1，rear不变（第一次入队列除外，rear+1，front+1）。因为不带头结点的队列，第一个元素入队时需要特别处理，所以只有当队列为空时，或者只有一个元素时，rear 才会等于 front。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q25

速对表原值： A

详细解析标注： A

注意题目中这里 Queue MaxSize 等于 M+1。题目里 f 作为队头指针指向队头元素的前一个位置，r 作为队尾指针指向队尾元素，用(r+1)%(M+1)==f 作为队满的标志，说明牺牲一个单元来区分队空和队满，队列中最多可以有 M 个元素，注意王道书 79 页（循环队列那里）的是 f 作为队头指针指向队头元素，r 作为队尾指针指向队尾元素的后一个位置（下一次要插入元素的位置），但判空判满的条件本质还是不变的。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q26

速对表原值： D

详细解析标注： D

front 指向队头，说明 front 的位置就是出队元素的位置，所以应该是先出队，再front 自增。rear 指向队尾元素的下一个位置，说明这个位置是空的也就是下一个要入队元素的位置，所以是先入队，再 rear 自增。由于是循环队列，所以自增后都要取模，因此答案选 D。这道题改编自真题，真题问的是判空盘满的条件，大家可以不看选项的情况下自己写出来队空：front == rear; 队满：front == (rear + 1) mod M其次，要是改成 rear 指向队尾元素位置，大家也要会自己分析。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q27

速对表原值： C

详细解析标注： C

模 M-1 的范围是[0，m-2]，会导致数组下标为 m-1 的结果缺失，所以必须模 M，直接排除 B。队列为空时，当 end1 指向队头元素，end2 指向队尾元素时，rear 在 front 前面一格，由于要牺牲一个位置区分循环队列判空判满，所以队满时 end2 和 end1 相差 2，因此答案按选 C。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q28

速对表原值： D

详细解析标注： D

循环队列由固定大小 M 的数组 A 实现，队列必须空出一个单元来区别队空和队满的判断。也可以用其他方法，但是都需要标志信息的额外开销，比如用 count 来记录队列元素个数，使用标记位（入队置 true，出队置false，若 rear和 front 无法区分队满还是队空，用标记位true 表示满，false 表示空）等，但都需要额外的开销，所以必须牺牲一个队列空间，故队满情况下元素个数为 M-1。(rear - front) % M 为当前队列的元素个数，因此答案选 D。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q29

速对表原值： B

详细解析标注： B

删除一个元素时 front 循环增 1，加入两个元素时 rear 循环增 2。本题答案为 B。

返回题目

Q30

速对表原值： A

详细解析标注： A

因为是循环队列，所以 rear 可能会从 m-1 回到 0，导致比 front 小，所以要采取取模来计算元素个数，答案选 A。这类题目可以举例来快速得出答案。

返回题目

Q31

速对表原值： C

详细解析标注： C

由题给出条件可得队首在 rear-(length-1)的位置(因为 rear 占一个位置)，由于减法可能结果为负数，考虑到循环特性，需要加上 m 再对 m 取模。或特殊值法：取 m=3，length=2，rear=0，则此时 front 在 2 的位置，带入计算，C 满足条件。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q32

速对表原值： A

详细解析标注： A

在栈中，栈底指针保持不变，有元素入栈，栈顶指名增加，有元素出栈，栈顶指针减少。在循环队列中，队头指针和队尾指针的动态变化决定队列的长度。在循环链表中，前一个结点指向后一个结点，而最后一个结点指向头结点，只有头结点是固定的。线性链表中，由于前一个结点包含下一个结点的指针，尾结点指针为空，要插入或删除元素，只需要改变相应位置的结点指针即可，头指针和尾指针无法决定链表长度。故本题答案为 A 选项。

返回题目

Q33

速对表原值： D

详细解析标注： D

选项 A 可以进一个出一个，右侧入队，左侧或右侧出队，Ka、Kb、Kc、Kd、Ke每个进出完再继续下一个入队。选项 B 可以所有的进去之后再依次出去，Ka，Kb，Kc，Kd，Ke 依次右侧进入，再依次右侧出来，类似于栈。选项 C 可以先 Ka，Kb 都右侧进，左或右侧出； Kc，Kd，Ke 依次进，Ke 右侧出，Kc 左侧出，Kd 左右均可出选项 D 无法得出这个序列。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q34

速对表原值： A

详细解析标注： A

如果题目改成所有元素依次入队后再进行入队操作（一次性出队）（10 年真题），则 III、IV 不可能得到。但是本题是可以中间出队的，I、II、III 比较好判断。对于 IV（假设只能右侧出队）：

①a 左入，b 右入得 ab，b 出队（b）

②c 右入得 ac，c 出 a 出（bca）

③d 左入，e 右入，e 出 d 出（bcade）

返回题目

Q35

速对表原值： A

详细解析标注： A

A 选项错误，d 第一个输出，那么此时队列里面还剩 abc，由于输入在两端都可以进行，且三个元素是按 abc 依次输入，那么 a、b 一定相邻，即 acb 一定不可能出现，A 错误。

B 选项正确，假设只能左边出，进出队列如下：a 左边入队得到 a；b 右边入队得到 ab；c 左边入队得到 cab；c 出队，得到 ab；a 出队，得到 bc；d 左边入队，得到 db，再依次出队 d，b，得到答案 B；C 选项显然正确；对于 D 选项：a 左入队，得 a；b 左边入队得 ba；b 出队，得 a；c 右边入队，得 ac；d 左边入队，得 dac；再依次出 dac，D 选项正确；

返回题目

Q36

速对表原值： C

详细解析标注： C

输入受限的双端队列，当〔公式/符号见原页版面片段〕1 = 〔公式/符号见原页版面片段〕, 〔公式/符号见原页版面片段〕2的可能取值只可能是 1 和 n-1 两种情况。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q37

速对表原值： C

详细解析标注： C

入队顺序和出队顺序一定一样，所以 A 正确。第一个出栈是 n-2，说明此时 1 到n-2 都已经入栈，只需要再入栈 n-1 和 n 再出栈 n 即可满足 B 的情况。第一个出栈是 n-3，则 1 到 n-3 都已经出栈，此时 n-3 出栈后，再入栈 n-2 再出栈，随后出栈 n-4 即可满足 D 的情况，但是无论如何都不可能使 n-6 第三个出栈，C 错误。

返回题目

Q38

速对表原值： D

详细解析标注： D

A 正确，使用两个队列实现栈时，一个用于存储栈内的元素，一个用于出栈操作的辅助队列 push（）时，新元素在非空队列中入队；pop（）时，将元素逐个出队再入队到另一个队列，至原队列只剩最后一个元素时，将该元素出队，完成 pop（）操作。

B 正确，使用一个队列模拟栈，需要满足队列 前端元素是最后入栈的元素。push（）时，首先将新元素入队，再将队列其他元素逐个出队再入队，这样可以使得新元素处于队首，模拟栈的功能。

C 正确，将栈 stack1 当作输入栈，存储 push（）传入的数据；栈 stack2 当作输出栈，用于 pop（）和 push（）操作。每次 pop（）或 push（）时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

D 错误，不能够实现该要求。

返回题目

Q39

速对表原值： C

详细解析标注： C

操作过程如下：e1 进栈，e2 进栈，e2 出栈后进队，e3 进栈，e4 进栈，e4 出栈后进队，e3 出栈后进队，e5 进栈，e6 进栈，e6 出栈后进队，e5 出栈后进队，e1 出栈后进队，栈中最多元素时为 3 个。本题答案为 C。

返回题目

Q40

速对表原值： A

详细解析标注： A

a[ 5 ] [ 5 ] 的地址＝ 1000+ (5 * 6+5) * 5=1175。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q41

速对表原值： B

详细解析标注： B

M 为 5 行 6 列，在按行存储时，元素 M[3, 5] 的起始地址为((3-0)6+(5-0))4=92。在按列存储时，元素 M[2, 4] 的起始地址为((4-0) * 5+(2-0)) * 4=88，元素 M[3, 4] 的起始地址为((4-0)* 5+(3 -0)) * 4=92，元素 M[3, 5]的起始地址为((5-0) * 5+(3-0)) * 4=112，元素 M[4, 4]的起始地址为((4-0) * 5+(4-0)) * 4=96。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q42

速对表原值： C

详细解析标注： C

存的的下三角，元素〔公式/符号见原页版面片段〕6, 10是上三角部分的元素，因此要按〔公式/符号见原页版面片段〕10, 6来求地址。列优先，则〔公式/符号见原页版面片段〕10, 6是第 10+9+8+7+6+5=45 个元素。结构体需要考虑对齐，结构体整体按内部最大空间的类型对齐，int 类型 4B 为最大，所以一个结构体占 12B，44*12+4=532，首地址是 1000，因此答案是 C。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q43

速对表原值： C

详细解析标注： C

第一行到第 7 行分别存放 1 到 7 个元素，A8 是第 8 行第 5 个元素，是所有元素中的第 1+2+...+7+5=33 个元素，答案选 C。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q44

速对表原值： A

详细解析标注： A

只考虑下三角，第 i 行有 i+1 个元素，设 B[i]的索引为 S[i]，则 S[i] = S[i-1] + i + 1，初始条件 S[0] = 0，S[1] = 2，S[2] = 5，S[i] = S[i-1] + i + 1 = S[0] + 2 + 3 + 4 + ... + i + i+1 = (i+1)(i+2)/2 - 1 = i(i+3)/2。即 B[i]的索引为 i(i+3)/2。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q45

速对表原值： B

详细解析标注： B

按列优先顺序，数组到第j 列之前存放了n+(n-1)+..+(n-j+1)=(2n-j+1)*j/2 个元素，然后再加上 i-j 可得答案。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q46

速对表原值： A

详细解析标注： A

指定的元素 aij，满足 i>=j，则该元素位于主对角线的下方，是未被直接存储的元素。由于是对称矩阵，它的存储位置和 aji 一致。对在对角线上方的 aji 而言，它之前共有（i-1）列元素，在第 1 列上有 1 个元素，在第 2 列上有 2 个元素……在第（i-1）列上共有（i-1）个元素。这若干列上的元素个数总和为 1+2+…+（i-1）=i（i-1）/ 2，而在第 i 列上，aji 是第 j 个元素，所以在整个存储排列中 a 是第 i（i-1）／2+j 个元素，B 的下标从 1 起始，也就是说它在 B 中的位置为 i（i-1）／2+j。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q47

速对表原值： C

详细解析标注： C

A 错误，三元组的内容为（行，列，值），其次还要存储稀疏矩阵的行列总数（否则无法分辨矩阵规格）和非零元素个数（三元组表的大小）。交换每个三元组的行列之外，还要交换总行和总列才可以实现转置。

B 错误，稀疏矩阵存储方式有三元组法和十字链表法，三元组存储是顺序存储方式，十字链表法是链式存储方式。

D 错误，十字链表适合频繁插入删除和快速定位行列元素，三元组存储效率一般低于十字链表，同理 C 正确。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q48

速对表原值： A

详细解析标注： A

用三元组存放矩阵中的元素，形式为( i，j，e) 其中 i 表示行号，j 表示列号，e表示元素值该题矩阵形式为：0 0 5 0 −3 3 0 −1 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 1 0 0 0 0

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q49

速对表原值： C

详细解析标注： C

稀疏矩阵采用二维数组存储时，它具有随机存取特性，而采用压缩存储后不再具有随机存取特性，本题答案为 C。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q50

速对表原值： B

详细解析标注： B

广义表是线性表的推广，408 还未考过，但是教材有相关介绍，这题作为防出题老头 gank。广义表是元素的有序集合，其中每个元素可以是：

• 原子（Atom）：即普通的数据元素，如整数、字符等；

• 也可以是另一个广义表（即子表）。相关术语：表头（Head）：广义表的第一个元素；表尾（Tail）：去掉表头后剩下的子广义表；深度（Depth）：广义表中最长嵌套层数；长度（Length）：广义表中顶层元素个数。回到本题：(a, (b, c), ((d, e), f))，表头是 a，A 正确。表尾是（(b, c), ((d, e), f)），B 不正确。顶层一共有三项，所以长度为 3，C 正确。深度为广义表的嵌套层数，第三个子表中还嵌套了一个子表，所以深度为 3 正确，D 正确。

返回题目

Q51

速对表原值： C

详细解析标注： C

这道题采用手工求 next 数组的方法。先求串 s='ababaaababaa'的部分匹配值：'a'的前后缀都为空，最长相等前后缀长度为 0。'ab'的前缀{a}∩后缀{b}=Ø，最长相等前后缀长度为 0。'aba'的前缀{a, ab}∩后缀(a, ba}={a}，最长相等前后缀长度为 1。'abab'的前缀{a, ab, aba}∩后缀{b, ab, bab}={ab}，最长相等前后缀长度为 2。依次求出的部分匹配值见下表第 3 行，将其整体右移一位，低位用-1 填充，见下表第 4 行。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q52

速对表原值： C

详细解析标注： C

见上题，在实际 KMP 算法中，为了使公式更简洁、计算简单，若串的位序是从1 开始的，则 next 数组才需要整体加 1；若串的位序是从 0 开始的，则 next 数组不需要整体加 1。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q53

速对表原值： C

详细解析标注： C

nextval 从 0 开始，可知串的位序从 1 开始。第一步，令 nextval[1]=next[1]=0。从 j=2 开始，依次判断 s[j]是否等于 s[ next[j] ]?若是则将 next[j]修正为 next[next[j]]，直至两者不相等为止。答案选 C。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q54

速对表原值： C

详细解析标注： C

先求 next 数组为-1, 0, 1, 0, 1, 0, 1, 2, 3, 4。再求 nextval 数组，假设模式串为 S，规则如下：

• nextval[0]直接写-1

• 从第二个开始，判断第 i 个字符 S[i]是否等于 S[next[i]]  如果不等，直接 nextval[i] = next[i];  相等，nextval[i] = nextval[ next[i] ];根据以上规则答案选 C。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q55

速对表原值： D

详细解析标注： D

next 数组本质是反映模式串自身的特性，在求它的值时，跟此后会与哪个主串进行匹配操作完全无关。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q56

速对表原值： B

详细解析标注： B

首先要计算模式串(P = "aada")的(nextval)数组：

• j = 0，默认(next[0] = -1)，(nextval[1] = -1)；

• j = 1，前面字符串为"a"，(next[1] = 0)，(nextval[1] = -1)；

• j = 2，前面字符串为"aa"，(next[2] = 1)，(nextval[1] = 1)；

• j = 3，前面字符串为"aad"，(next[3] = 0)，(nextval[3] = -1)。匹配过程：

• 第一次匹配，前两位字符匹配上，失配发生在(S[2])和(P[2])，此时已经比较了三次；

• 查(nextval)数组知，下次对比(S[2])和(P[1])，比较一次

• 发现不同(〔公式/符号见原页版面片段〕 2 ≠ 〔公式/符号见原页版面片段〕 1 ），(nextval[1])是(-1)，下次比较时主串向后移动一位，模式串回到首位，即对比(S[3])和(P[0])，这次依次向后比较三次，在(S[5])和(P[2])失配

• 查(nextval)数组知，下次对比(S[5])和(P[1])，比较一次

• 同样发现不同，主串后移一位，模式串(P)回到首位，依次比较四次发现匹配上。共匹配(3 + 1 + 3 + 1 + 4 = 12 次。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q57

速对表原值： C

详细解析标注： C

I 正确，普通匹配算法的时间复杂度为 O（mn），kmp 算法时间复杂度为 O（m+n），如果每次匹配部分匹配都接近模式串长度 n，那么普通匹配算法达到最坏时间复杂度 O（mn），相反普通匹配算法和 kmp 接近。II 错误，主串指针在 j=0 失配时，i 最后会+1。III 错误，正确 next 数组为'-1，0，1，2'，部分前缀和后缀长度应小于总长度。IV 错误，和 II 一样，在 j=0 失配时，j 置为-1，还需要 i, j 都+1

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q58

速对表原值： B

详细解析标注： B

A 错误，在 j 位置失配，说明主串 T[i]≠S[j]，那么当 S[j]==S[next[j]]的时候，下一次匹配仍然会失配，这也是为什么要引入 nextval 数组的原因，可以消除这种冗余的比较。

B 正确，在计算 nextval 数组时，当 S[j]≠S[next[j]]时，令 nextval[j]和 next[j]相等；否则，当 S[j]=S[next[j]]时，nextval[j]=nextval[next[j]]，而不是 nextval[j]=next[next[j]]，D 错误。C 同样错误，当下标从 0 开始时，nextval[0]=-1，但 nextval[1]不一定为 0，也有可能是-1，比如模式串“aa”，nextval={-1,-1}。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q59

速对表原值： D

详细解析标注： D

假设 T、S 的下标都从 0 开始，首先计算出 S 的 next 数组为‘-1, 0, 0, 1, 1, 2’，失配情况如下：

• i=5, j=5，失配修改后，i=5, j=2 (右移 5-2=3)

• i=8, j=5，失配修改后，i=8, j=2 (右移 5-2=3)

• i=9, j=3，失配修改后，i=9, j=1 (右移 3-1=2)

• i=9, j=1，失配修改后，i=9, j=0 (右移 1-0=1)

• i=9, j=0，失配后，修改为 i=9, j=-1，然后两者同时+1，变为 i=10, j=0 (首个失配右移1)

• i=11, j=1，失配修改后，i=11, j=0 (右移 1-0=1)

• i=11, j=0，失配后，修改为 i=11, j=-1，然后两者同时+1，变为 i=12, j=0 (首个失配右移 1)

• i=13, j=1，失配修改后，i=13, j=0 (右移 1-0=1)

• 匹配成功总计右移距离 3+3+2+1+1+1+1+1=13。这题也可以用更快速的思路：设模式串长度为 m（本题是 6），正常我们一次性匹配成功，比较的次数为m次即可。但是由于我们中间会失配，失配后模式串右滑，我们要从某个位置和主串接着比较，主串 i 是不回退的，所以右滑的距离就是我们要多比较的次数。设匹配的位置是 x（本题是 19），那么原本 m 次比较现在变成了 x 次比较，多比较的次数就是模式串的右滑总距离，即 x-m=19-6=13。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q60

速对表原值： C

详细解析标注： C

A 错误，n 至少是 4，利用贪心的思想，每次入队如果有某个队列的队尾元素比自己小，那就选择一个和自己最相近的元素所在队列插入，没有的话就重新开辟一个队列。4 个队列分别入队[8,9] [4,5,6,7][2,3][1]时，所用队列数最少。

B 错误，k 尽可能小，队列大小 k 最小为 1，至少需要 9个队列，C 正确，D 错误；n 尽可能小(n=4)，k 最小为 3，4 个队列分别入队[8,9] [4,5,6][2,3,7][1]。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q61

速对表原值： C

详细解析标注： C

本题是栈的应用考察。左括号视为入栈，右括号视为出栈，本题就变成了问 3 个元素入栈有多少种不同的出栈序列个数。答案是卡特兰数，n=3 的卡特兰数是 5。也可自己枚举：((()))、(()())、(())()、()(())、()()()。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q62

速对表原值： D

详细解析标注： D

A 正确，所有元素依次入队，再从左端依次出队。

B 正确，所有元素依次入队，再从右端依次出队。

C 正确，1、2 入队，右边出 2，左边出 1，3、4、5 依次入队，右侧依次出队 5、4、3，正确。

D 错误，5 第一个出队，说明所有元素都依次入队了，此时队列还剩 1、2、3、4。无论左右都无法出 3。

返回题目

Q63

速对表原值： C

详细解析标注： C

下标从 0 开始编号，先求 next 数组=[-1,0,1,0,1,2]，再求 nextval 数组=[-1,-1,1,-1,-1,1]。用下标 i 表示主串 T 位置，j 表示模式串 S 位置，每次失配时，根据 nextval 来修改 j 的回溯位置。当 i=j=1 时，T[1]=’b’≠S[1]=’a’，一共比较 2 次，第一次失配后，i=2,j=0;当 i=4，j=2 时，T[4]=’a’≠S[2]=’b’，一共 比较 3 次，第二次失配后，i=4,j=1;当 i=6，j=3 时，T[6]=’c’≠S[3]=’a’，一共比较 3 次，第三次失配后，i=7,j=0;当 i=12，j=5 时，匹配成功，一共比较 6 次。总计比较 2+3+3+6=14 次，答案选 C。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目

Q64

速对表原值： B

详细解析标注： B

I 正确，普通顺序队列（数组实现、非循环）中，元素不断出队导致队头 front后移，数组前部出现大量空闲空间；但队尾指针 rear 已到达数组最大下标，无法继续入队。数组明明未满，却判定为 “溢出”，这就是假溢出。循环队列将一维数组在逻辑上首尾相连，利用取模运算(rear+1) % MaxSize 让队尾指针走到数组末尾后回到数组头部，复用前部空闲空间，彻底解决假溢出。II 正确，教材上队列的两种存储结构分别为循环队列和链式队列，所以说循环队列本身也是一种存储结构。III 错误，链式队列，队头一般设置在链表头部，出队涉及到删除操作，如果设置在链表尾部，删除单链表尾部元素的时间复杂度为 O(n)；IV 错误，逻辑上连续的两个结点的指针在物理上不一定连续，链式存储是动态申请结点空间，在内存是不连续的，所以无法通过指针做差计算队列长度。答案选 B。

原页版面片段（用于核对图表、公式、矩阵或代码）

返回题目