数据结构 第三章练习题

第1题

一个栈的入栈序列是1、2、3、4、5，则栈的不可能的输出序列是（ ）。

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

答案：C

解析：

栈的特点是“后进先出”（LIFO）。这意味着一个元素要出栈，它之前所有入栈的元素要么已经出栈，要么还在它下面。

• A: 入栈1,2,3,4,5，然后依次出栈5,4,3,2,1。可能。
• B: 入栈1,2,3,4，出栈4；入栈5，出栈5；然后依次出栈3,2,1。可能。
• D: 入栈1，出栈1；入栈2，出栈2；…。可能。
• C: 为了让1出栈，它上面的2,3,4,5必须先出栈。但在序列C中，5在1之前出栈，但2却在1之后出栈，这是不可能的。因为要让1出栈，2必须先出栈。

第2题

若一个栈的输入序列是1, 2, 3, …, n，输出序列的第一个元素是n，则第i个输出元素是（ ）。

• A. 不确定
• B. n-i
• C. n-i-1
• D. n-i+1

答案：D

解析：

输出序列的第一个元素是n，意味着元素1, 2, …, n必须全部入栈，然后n才作为第一个元素出栈。此时栈内自顶向下为 n-1, n-2, …, 1。接下来出栈的元素必然是n-1, n-2, …。

• 第1个输出元素是 n (即 n-1+1)
• 第2个输出元素是 n-1 (即 n-2+1)
• 第i个输出元素是 n-(i-1)，即 n-i+1。

*第3题

若一个栈的输入序列是1, 2, 3, …, n，其输出序列是p1, p2, …, pn，若p1=3，则p2的值（ ）。

• A. 一定是2
• B. 一定是1
• C. 不可能是1
• D. 以上都不对

答案：A

解析：

p1=3意味着操作序列为：入栈(1)，入栈(2)，入栈(3)，出栈(3)。此时，栈中元素为[1, 2]，其中2在栈顶。下一个出栈的元素可能是2（如果直接出栈），也可能是后面入栈的元素（如入栈(4)再出栈(4)）。但在典型的题目设定中，如果没有其他入栈操作，下一个出栈的元素必然是栈顶元素。因此，p2最直接的可能就是2。选项A “一定是2” 在这种简化场景下是正确的。而选项C “不可能是1” 也是正确的，因为2在1的上面，必须先出栈。但A是更确切的描述。

第4题

设计一个判别表达式中左右括号是否配对的算法，采用（ ）数据结构最佳。

• A. 顺序表
• B. 栈
• C. 队列
• D. 链表

答案：B

解析：

括号配对问题具有“后遇到的左括号，先匹配”的特点，这完全符合栈的“后进先出”特性。遇到左括号就入栈，遇到右括号就将栈顶的左括号出栈，如果栈为空或栈顶不是对应的左括号则匹配失败。

第5题

在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（ ）结构。

• A. 栈
• B. 数组
• C. 队列
• D. 线性表

答案：C

解析：

打印任务应该遵循“先到先服务”的原则，这正是队列“先进先出”（FIFO）的特性。主机将打印任务依次放入缓冲区（入队），打印机再从缓冲区依次取出任务进行打印（出队）。

第6题

一个队列的入队顺序是1, 2, 3, 4，则队列的输出顺序是（ ）。

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

答案：B

解析：

队列的特性是“先进先出”（FIFO）。入队顺序是1, 2, 3, 4，那么出队顺序也必然是1, 2, 3, 4。

第7题

栈和队列的主要区别是（ ）。

• A. 它们的逻辑结构不一样
• B. 它们的存储结构不一样
• C. 所包含的运算不一样
• D. 插入、删除运算的限定不一样

答案：D

解析：

栈和队列在逻辑上都属于线性结构。它们的存储结构都可以是顺序存储或链式存储。它们的主要区别在于对插入和删除操作的限制不同：栈只允许在表的一端（栈顶）进行插入和删除，而队列允许在表的一端（队尾）进行插入，在另一端（队头）进行删除。

第8题

设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（ ）。

• A. 6
• B. 4
• C. 3
• D. 2

答案：C

解析：

分析操作过程并追踪栈内元素数量的最大值：

1. 要输出e2，必须先入栈e1, e2。S: [e1, e2]。然后e2出栈。S: [e1]。栈大小最大为2。

2. 要输出e4，必须在e1的基础上入栈e3, e4。S: [e1, e3, e4]。然后e4出栈。S: [e1, e3]。栈大小最大为3。

3. 要输出e3，e3直接出栈。S: [e1]。

4. 要输出e6，必须在e1的基础上入栈e5, e6。S: [e1, e5, e6]。然后e6出栈。S: [e1, e5]。栈大小最大为3。

5. 后续e5, e1依次出栈，栈大小减小。

   整个过程中，栈内元素数量最多时达到了3个。所以容量至少为3。

第9题

在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)后，栈顶元素是（ ）。

• A. 1
• B. 5
• C. 2
• D. 6

答案：D

解析：

• push(1): 栈 [1]

• push(2): 栈 [1, 2]

• pop: 弹出2，栈 [1]

• push(5): 栈 [1, 5]

• push(7): 栈 [1, 5, 7]

• pop: 弹出7，栈 [1, 5]

• push(6): 栈 [1, 5, 6]

  最后栈顶元素是6。

第10题

在操作序列EnQueue(1)、EnQueue(3)、DeQueue、EnQueue(5)、EnQueue(7)、DeQueue、EnQueue(9)之后，队头元素是（ ）。

• A. 1
• B. 3
• C. 5
• D. 7

答案：C

解析：

• EnQueue(1): 队 [1]

• EnQueue(3): 队 [1, 3]

• DeQueue: 1出队，队 [3]

• EnQueue(5): 队 [3, 5]

• EnQueue(7): 队 [3, 5, 7]

• DeQueue: 3出队，队 [5, 7]

• EnQueue(9): 队 [5, 7, 9]

  最后队头元素是5。

第11题

将数组称为随机存取结构是因为（ ）。

• A. 数组元素是随机的
• B. 对数组元素的存取时间相等
• C. 随时可以对数组进行访问
• D. 数组的存储结构是不定的

答案：B

解析：

随机存取（Random Access）是指可以直接通过下标访问任意位置的元素，并且访问任何一个元素所需的时间都是常数，与元素在数组中的位置无关。

第12题

对特殊矩阵采用压缩存储的目的主要是为了（ ）。

• A. 表达变得简单
• B. 对矩阵元素的存取变得简单
• C. 去掉矩阵中的多余元素
• D. 减少不必要的存储空间

答案：D

解析：

像对称矩阵、三角矩阵、稀疏矩阵等特殊矩阵，存在大量值相同（如0）或有规律分布的元素。压缩存储通过只存储非零元素或非重复元素来大大减少存储空间。

第13题

二维数组A的行下标范围是从0～8，列下标范围是从0～9，若A按行优先方式存储，元素A[8][5]的起始地址与当A按列优先方式存储时的（ ）元素的起始地址一致。

• A. A[8][5]
• B. A[3][10]
• C. A[5][8]
• D. A[4][9]

答案：D

解析：

数组共有9行10列。设元素大小为size，基地址为Base。

• 按行优先，A[8][5]的地址为：Base + (8 * 10 + 5) * size = Base + 85 * size。

• 按列优先，A[i][j]的地址为：Base + (j * 9 + i) * size。

  我们需要找到 j * 9 + i = 85。

• 检验D选项 A[4][9]：i=4, j=9，9 * 9 + 4 = 81 + 4 = 85。地址相符。

第14题

设有一个空栈，栈顶指针为1000H，每个元素需要1个单位的存储空间，则执行push, push, pop, push, pop, push, push后，栈顶指针为 [ 1003H ]。

解析：

共有5次push和2次pop。栈中元素净增加 5 - 2 = 3 个。

如果栈向上增长，栈顶指针会增加3个单位。

1000H + 3H = 1003H。

第15题

引入循环队列是为了克服顺序队列的 [ 假溢出 ] 问题。

解析：

在顺序队列中，当队尾指针rear到达数组末端后，即使数组前端因为出队操作已经有了空闲空间，也无法再进行入队操作，这种情况称为“假溢出”。循环队列通过将数组头尾相连，解决了这个问题。

*第16题

数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为 [ (rear - front + n) % n ]。

解析：

这是计算循环队列元素个数的标准公式。+n是为了防止rear < front时计算结果为负数，%n是为了处理环形结构。

*第17题

用循环链表表示的队列长度为n，若只设头指针，则出队的时间复杂度是 [ O(n) ]。

解析：

只设头指针H，H指向队头元素。出队操作需要删除H所指的节点。要删除H，需要找到它的前驱节点（即队尾节点），然后让队尾节点指向新的队头（H->next）。在单向循环链表中，从头指针开始找到尾节点需要遍历整个链表，因此时间复杂度为O(n)。

第18题

用循环链表表示的队列长度为n，若只设头指针，则入队的时间复杂度是 [ O(n) ]。

解析：

只设头指针H，H指向队头元素。入队操作是在队尾进行。要找到队尾节点（即H的前驱），需要从H开始遍历整个链表，时间复杂度为O(n)。

(注：此题和上一题在很多考试中存在争议，标准的循环链表队列实现是只设一个指向队尾的指针，这样入队和出队都是O(1)。若严格按“只设头指针”的题意，入队和出队都需要遍历，均为O(n)。)

第19题

二维数组A中行下标从10到20，列下标从5到10，按行优先存储，每个元素占4个存储单元，A[10][5]的存储地址是1000，则元素A[15][10]的存储地址是 [ 1140 ]。

解析：

• 每行有 10 - 5 + 1 = 6 个元素。
• A[15][10]相对于A[10][5]的位置：
  • 跨过了 15 - 10 = 5 个完整的行。
  • 在目标行中，列偏移量为 10 - 5 = 5 个元素。
• 总的元素偏移量 = (5 * 6) + 5 = 30 + 5 = 35 个元素。
• 地址偏移量 = 35 * 4 = 140 个存储单元。
• 目标地址 = 1000 + 140 = 1140。

第20题

设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址为d，每个元素占1个地址空间，则元素A[8][5]的存储地址为 [ d + 41 ]。

解析：

对称矩阵压缩存储通常只存储下三角（或上三角）。按行优先存储下三角部分（i >= j）。

• 元素A[i][j]之前有i行（从第0行到第i-1行）。
• 第k行有k+1个元素。
• A[8][5]之前有8行（第0到7行），这些行共有 1+2+3+4+5+6+7+8 = 8 * 9 / 2 = 36 个元素。
• 在第8行，A[8][5]是该行的第6个元素（下标从0到5），所以它前面有5个元素。
• 因此，A[8][5]是第 36 + 5 = 41 个元素（从0开始计数）。
• 存储地址为 d + 41。