🏷️ 知识点：栈

栈和队列具有相同的()。

A. 抽象数据类型 B. 逻辑结构 C. 存储结构 D. 运算

[tag_link]

正确答案：B

已知一个栈的进栈序列是 1、2、3、…、n，其输出序列为 p₁、p₂、p₃、…、pₙ，若 p₁=3，则 p₂ 为（ ）。

A. 2 或 4、5、…、n 都有可能 B. 可能是 1 C. 一定是 2 D. 只可能是 2 或 4

栈 入栈出栈序列

[tag_link]

正确答案：A

已知进栈序列为1,2,3,…,n，且第一个出栈元素p₁=3。 根据栈的后进先出特性，为了使得3第一个出栈，操作序列必须是：先将1和2依次进栈，然后将3进栈并立即出栈。 此时栈中剩余元素为1和2（2在栈顶），且后续元素4,5,…,n尚未进栈。

对于第二个出栈元素p₂，存在两种可能：一是直接出栈当前栈顶元素2，则p₂=2； 二是暂不出栈2，而是将后续元素4,5,…,n依次进栈，并在进栈过程中或进栈后出栈某个元素，此时p₂可以是4,5,…,n中的任意一个。 需要注意的是，p₂不可能是1，因为1位于栈底，必须等待其上方所有元素出栈后才能出栈，而p₂是第二个出栈元素，若不出栈2则无法触及1。 因此，p₂可能是2或4,5,…,n中的任意值，与选项A相符。

假设栈的容量为 3，入栈的序列为 1,2,3,4,5，则出栈的序列可能为（ ）。

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

栈 入栈出栈序列

[tag_link]

正确答案：A

栈的容量为 3，入栈序列固定为 1,2,3,4,5。

出栈序列必须符合栈的后进先出规则，且受容量限制。

对于选项 A（3,2,1,5,4）：

• 先入栈 1,2,3（栈满），出栈 3,2,1，栈空。 >
• 再入栈 4，入栈 5，出栈 5,4。 > 操作过程中栈内元素数始终不超过 3，且符合出栈序列，因此可能。 >

对于选项 B（1,5,4,3,2）：

• 出栈 1 后，需出栈 5，但 5 尚未入栈。 > 入栈 2,3,4 后栈满，无法直接入栈 5； > 若先出栈元素则破坏序列顺序。 >
• 要使 5 先出栈，需在 5 入栈时栈中包含 4,3,2，但容量仅为 3，无法同时容纳 4 个元素，因此不可能。 >

对于选项 C（5,4,3,2,1）：

• 需先出栈 5，但 5 最后入栈。 > 入栈 1,2,3 后栈满，入栈 4 需先出栈元素，而出栈会破坏序列以 5 开始，因此不可能。 >

对于选项 D（4,3,2,1,5）：

• 需先出栈 4，但入栈 1,2,3 后栈满，入栈 4 需先出栈元素，而出栈会导致序列首元素不为 4，因此不可能。 >

综上，只有选项 A 可能。 >

设有一个递归算法如下：

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

栈

[tag_link]

正确答案：B

【解析】

计算 X(5) 时，首先调用 X(5) 一次。

由于参数 n=5 大于 3，执行 else 分支，需要递归调用 X(n-2) 即 X(3) 和 X(n-4) 即 X(1)。

调用 X(3) 时，因为 3≤3，直接返回 1，不再递归，此次调用计一次。 调用 X(1) 时，同样因为 1≤3，直接返回 1，也不再递归，此次调用也计一次。

因此，总共调用了三次 X 函数：分别是 X(5)、X(3) 和 X(1)。 对应选项为 B.3。

6 个元素以 6、5、4、3、2、1 的顺序进栈，下列不合法的出栈序列是（ ）。

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

栈 入栈出栈序列

[tag_link]

正确答案：C

栈是后进先出（LIFO）的数据结构，元素以固定顺序 6、5、4、3、2、1 依次进栈。

合法的出栈序列必须满足：在模拟进栈和出栈过程中，每次出栈的元素要么是栈顶元素，要么可以通过压入剩余进栈元素后成为栈顶元素。

对于选项 A（5、4、3、6、1、2）：模拟过程可行，例如先压入 6、5，出栈 5； 压入 4，出栈 4； 压入 3，出栈 3； 出栈 6； 压入 2、1，出栈 1，出栈 2。 序列合法。

对于选项 B（4、5、3、1、2、6）：模拟过程可行，例如压入 6、5、4，出栈 4； 出栈 5； 压入 3，出栈 3； 压入 2、1，出栈 1； 出栈 2； 出栈 6。 序列合法。

对于选项 C（3、4、6、5、2、1）：模拟时，先压入 6、5、4、3，出栈 3； 出栈 4； 此时栈顶为 5，但下一个出栈元素是 6。 由于 6 在栈底，被 5 压住，必须先出栈 5 才能出栈 6，但序列中 6 在 5 之前，无法实现。 因此序列不合法。

对于选项 D（2、3、4、1、5、6）：模拟过程可行，例如压入 6、5、4、3、2，出栈 2； 出栈 3； 出栈 4； 压入 1，出栈 1； 出栈 5； 出栈 6。 序列合法。

综上，不合法的出栈序列是选项 C。

已知程序如下：

int S(int n) {
    return (n <= 0) ? 0 : S(n - 1) + n;
}

void main() {
    cout << S(1);
}

程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息依次对应的是（ ）。

栈

A. main() → S(1) → S(0) B. S(0) → S(1) → main() C. main() → S(0) → S(1) D. S(1) → S(0) → main()

[tag_link] 正确答案：A递归调用函数时，在系统栈里保存的函数信息需满足先进后出的特点，依次调用了main()，S(1)，S(0)，故栈底到栈顶的信息依次是main()，S(1)，S(O)。

栈是 一种()。

A. 顺序存储的线性结构 B. 链式存储的非线性结构 C. 限制存取点的线性结构 D. 限制存取点的非线性结构

[tag_link]

正确答案：C

利用栈求表达式的值时，设立运算数栈 OPEN。假设 OPEN 只有两个存储单元，则在下列表达式中，不会发生溢出的是（ ）。

A. A-B*(C-D) B. (A-B)C-D C. (A-BC)-D D. (A-B)*(C-D)

栈

[tag_link]

正确答案：B

在利用栈求表达式值时，运算数栈 OPEN 用于存储运算数和中间计算结果。 > 由于 OPEN 只有两个存储单元，栈最多能同时容纳两个运算数，若在求值过程中尝试压入第三个运算数，就会发生溢出。 > 因此，需要分析每个表达式在求值过程中运算数栈的最大深度是否超过2。 >

通过将中缀表达式转换为后缀表达式并模拟求值过程，可以计算栈的最大深度：

• 表达式 A: A-B*(C-D)，后缀为 A B C D - * -。 > 求值时，压入 A、B、C 后栈深度达到3，发生溢出。 >
• 表达式 B: (A-B)*C-D，后缀为 A B - C * D -。 > 求值时，栈中最多同时存在两个运算数（如中间结果和 C 或最终结果和 D），最大深度为2，不会溢出。 >
• 表达式 C: (A-B*C)-D，后缀为 A B C * - D -。 > 求值时，压入 A、B、C 后栈深度达到3，发生溢出。 >
• 表达式 D: (A-B)*(C-D)，后缀为 A B - C D - *。 > 求值时，压入中间结果、C、D 后栈深度达到3，发生溢出。 >

因此，只有表达式 B 在求值过程中运算数栈的最大深度不超过2，不会发生溢出。 >

当字符序列 t3_ 作为栈的输入时，则输出长度为 3，且可用 C 语言标识符的序列有（ ）个。

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

栈

[tag_link]

正确答案：C

【解析】考查栈的操作。 标识符只能以字母或下划线开头，即由 t、3、_ 能够组成的合法标识符只有：t3_、t_3、_3t、_t3，而当用 t3_ 作为栈的输入时，_t3 无法作为输出序列，所以输出的合法标识符有 t3_； t_3； _3t，因此选 C。

若一个栈以向量 V[1..n] 存储，初始栈顶指针 top 为 n+1，则 x 进栈的正确操作是（ ）。

A. top=top+1; V[top]=x B. V[top]=x; top=top+1 C. top=top-1; V[top]=x D. V[top]=x; top=top-1

栈

[tag_link]

正确答案：C

栈以向量 V[1..n] 存储，初始栈顶指针 top 为 n+1，这表示栈为空且栈从数组末端向开头方向增长。

因为向量有效索引是 1 到 n，top 初始值 n+1 是一个无效位置，意味着栈底在索引 n 附近，栈顶指针向索引 1 方向移动。

进栈操作需要将元素 `x` 存入向量的有效位置，并更新栈顶指针指向新栈顶。 正确步骤应是先减小 `top` 指针，使其指向一个有效索引（如从 `n+1` 减到 `n`），然后将 `x` 存入该位置。 这样，栈顶元素位于 `V[top]`，`top` 指向当前栈顶。

分析选项：

• **A** 和 **B** 中 `top` 增加会导致越界访问； >
• **D** 先存入 `x` 但初始 `top` 为 `n+1`，直接访问 `V[n+1]` 越界； >
• 只有 **C** 先执行 `top = top - 1` 使指针有效，再执行 `V[top] = x`，符合栈的操作逻辑。 >

因此，**C** 是正确操作。 >

若已知一个栈的入栈序列是 1,2,3,4。其出栈序列为 p1,p2,p3,p4，则 p2,p4 不可能是（ ）。

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

入栈出栈序列 栈

[tag_link]

正确答案：C

栈的入栈序列为 1,2,3,4，出栈序列需符合栈的后进先出规则。 通过分析所有可能的出栈序列（共 14 种），并检查各选项中 p2（第二个出栈元素）和 p4（第四个出栈元素）的组合是否存在合法的序列对应。

• 选项 A（2、4）：存在合法序列如 1,2,3,4，其中 p2=2、p4=4，故可能。
• 选项 B（2、1）：存在合法序列如 3,2,4,1，其中 p2=2、p4=1，故可能。
• 选项 C（4、3）：不存在任何合法出栈序列同时满足 p2=4 且 p4=3。 例如，序列 1,4,2,3 看似满足，但实际上不合法，因为在出栈 4 后，栈中剩余 2 和 3 且 3 在栈顶，必须优先出栈 3，无法直接出栈 2，因此无法实现 p4=3。
• 选项 D（3、4）：存在合法序列如 1,3,2,4，其中 p2=3、p4=4，故可能。

综上，p2、p4 不可能是 4、3，对应选项 C。

下列关于栈的叙述中，错误的是（ ）。

I. 采用非递归方式重写递归程序时必须使用栈

II. 函数调用时，系统要用栈保存必要信息

III. 只要确定了入栈次序，即可确定出栈次序

IV. 栈是一种受限的线性表，允许在其两端进行操作

栈 入栈出栈序列

A. 仅 I B. 仅 I、II、III C. 仅 I、III、IV D. 仅 II、III、IV

[tag_link]

正确答案：C

I 的反例：计算斐波拉契数列迭代实现只需要一个循环即可实现。 III 的反例：入栈序列为 1、2, 进行如下操作 PUSH、PUSH、POP、POP，出栈次序为 2、1；进行如下操作 PUSH、POP、PUSH、POP，出栈次序为 1、2。 IV，栈是一种受限的线性表，只允许在一端进行操作。 因此 II 正确。

对于括号匹配问题，符号栈初始为空，容量为 3，下列表达式不能实现的是（ ）。

栈

A. (a+[b+(c+d)e]+f)+g-h B. [a*((b+c)/(d-e)+f/g)]-h C. [a*(b-(c-d)*e/(f+g))-h] D. [a-(b+[c*(d+e)-f]+g+h)]

[tag_link]

正确答案：D

栈的容量为 3，意味着在任何时候，栈中的元素数量不能超过 3。需要选择一个在某些时刻栈的深度超过 3 的表达式。通过分析各个选项的嵌套深度，可以发现：

• A. (a+[b+(c+d)e]+f)+g-h
• 最深嵌套：([(+)])，最多 3 个未匹配括号，正确。
• B. [a*((b+c)/(d-e)+f/g)]-h
• 最深嵌套：[(())]，最多 3 个未匹配括号，正确。
• C. [a*(b-(c-d)*e/(f+g))-h]
• 最深嵌套：[()()]，最多 3 个未匹配括号，正确。
• D. [a-(b+[c*(d+e)-f]+g+h)]
• 最深嵌套：[([])]，最多 4 个未匹配括号，错误。

下列选项中，()不是栈的基本操作。

A. 删除栈顶元素 B. 删除栈底元素 C. 判断栈是否为空 D. 将栈置为空栈

[tag_link]

正确答案：B

将 5 个字母 “ooops” 按此顺序进栈，则有（　）种不同的出栈顺序可以仍然得到 “ooops”。

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

栈 入栈出栈序列

[tag_link]

正确答案：C

将5个字母“ooops”按顺序进栈，即进栈序列为o、o、o、p、s。 要求出栈序列仍然为“ooops”，即出栈顺序为o、o、o、p、s。 由于三个o相同，不同的出栈顺序指的是三个o的个体出栈顺序不同，但最终输出的字符串相同。

设三个o分别为A、B、C（按进栈顺序），p为D，s为E。 出栈序列必须满足前三个为A、B、C的某种排列，第四个为D，第五个为E。 三个o的排列共有6种：ABC、ACB、BAC、BCA、CAB、CBA。 需要检查每种排列是否满足栈的合法性（即能否通过合理的进栈和出栈操作实现）。

1. ABCDE：合法，可每进栈一个元素后立即出栈。
2. ACBDE：合法，A进栈后出栈，B进栈后不出，C进栈后出栈C，再出栈B。
3. BACDE：合法，A进栈后不出，B进栈后出栈B，再出栈A，然后C、D、E依次进栈出栈。
4. BCADE：合法，A进栈后不出，B进栈后出栈B，C进栈后出栈C，再出栈A。
5. CABDE：不合法，因为C首先出栈后，栈中剩余A和B（B为栈顶），下一个需要出栈A，但A不在栈顶，无法直接出栈。
6. CBADE：合法，A进栈后不出，B进栈后不出，C进栈后出栈C，再出栈B，最后出栈A。

因此，只有5种合法的出栈顺序，对应选项C。

将中缀表达式转换为等价的后缀表达式的过程中要利用堆栈保存运算符。对于中缀表达式 $A-(B+C)\times E$ ，当扫描到操作数 $E$ 时，堆栈中保存的运算符依次是（ ）。

A. -× B. -(× C. -+ D. -(+

栈

[tag_link]

正确答案：A

中缀表达式转换为后缀表达式时，使用堆栈暂存运算符。 对于表达式

$A-(B+C)\times E$ ，从左到右扫描：

• 扫描到操作数 $A$ ：直接输出，堆栈为空。 >
• 扫描到运算符 $-$ ：堆栈为空，将 $-$ 压栈。 >
• 扫描到左括号 $($ ：直接压栈，堆栈为 $-,($ （栈底到栈顶，下同）。 >
• 扫描到操作数 $B$ ：输出，堆栈不变。 >
• 扫描到运算符 $+$ ：栈顶为左括号，直接压栈，堆栈为 $-,(,+$ 。 >
• 扫描到操作数 $C$ ：输出，堆栈不变。 >
• 扫描到右括号 $)$ ：弹出栈顶运算符 $+$ 并输出，接着弹出左括号 $($ 丢弃，堆栈变为 $-$ 。 >
• 扫描到运算符 $\times$ ：比较优先级， $\times$ 高于栈顶 $-$ ，因此压栈，堆栈变为 $-,\times$ 。 >
• 扫描到操作数 $E$ ：此时堆栈保持不变，运算符依次为 $-$ 和 $\times$ 。 >

对应选项，A 为 $-\times$ ，符合结果。 > 其他选项中，B、C、D 的运算符组合与扫描过程中的实际堆栈状态不符。 >

执行完下列语句段后，i 值为（ ）。

A. 2 B. 4 C. 8 D. 无限递归

栈

[tag_link]

正确答案：B

首先，函数 f 是递归函数，其定义为：当参数 x 大于 0 时，返回 x 乘以 f(x-1)； 当 x 不大于 0（即 x ≤ 0）时，返回 2。 语句 `i = f(f(1));` 的执行过程分为两步：先计算内层 `f(1)`，再将结果作为参数计算外层 f。

计算 `f(1)`：由于 1 > 0，返回 `1 * f(0)`。 计算 `f(0)`：0 不大于 0，因此返回 2。 所以 `f(1) = 1 * 2 = 2`。

然后计算外层 `f(f(1))` 即 `f(2)`。 对于 `f(2)`：2 > 0，返回 `2 * f(1)`。 而 `f(1)` 已计算为 2，因此 `f(2) = 2 * 2 = 4`。 最终 i 的值为 4。

递归过程有限，因为对于正整数参数，递归总是递减到 0 后终止，不会无限递归。 因此正确答案为 B。

设用数组a[n] 存储一个栈，初始栈顶指针top=-1, 则元素x 入栈的操作是()。

A. a[–top]=x B.a[top–]=x C.a[++top]=x D.a[top++]=x

[tag_link]

正确答案：C

设用数组data[1….n] 存储一个栈，初始栈顶指针 top=1, 则元素x 入栈的操作是()。 A . data[top–] =x B.data[top++]=x

C. data[–top]=x D.data[++top]=x

[tag_link]

正确答案：B

设用数组 data[1….n] 存储一个栈，初始栈顶指针 top=n+1, 则元素x 入栈的操作是()。

A. data[–top]=x B.data[top++]=x C. data[top–]=x D.data[++top]=x

[tag_link]

正确答案：A

设有一个空栈，栈顶指针为1000H, 栈向高地址方向增长，每个元素占一个存储单元， 执行Push 、Push 、Pop 、Push 、Pop 、Push 、Pop 、Push 操作后，栈顶指针为()。 A.1002H B.1003H C.1004H D.1005H

[tag_link]

正确答案：A

和顺序栈相比，链栈有一个比较明显的优势，即()。

A. 通常不会出现栈满的情况 B. 通常不会出现栈空的情况 C. 插入操作更容易实现 D. 删除操作更容易实现

[tag_link]

正确答案：A

设链表不带头结点且所有操作均在表头进行，则下列最不适合作为链栈的是()。

A. 只有表头结点指针，没有表尾指针的双向循环链表 B. 只有表尾结点指针，没有表头指针的双向循环链表 C. 只有表头结点指针，没有表尾指针的单向循环链表 D. 只有表尾结点指针，没有表头指针的单向循环链表

[tag_link]

正确答案：C

向一个栈顶指针为 top 的链栈(不带头结点)中插入一个x 结点，则执行()。

A. top->next=x B.x->next=top->next;top->next=x C. x->next=top;top=x D. x->next=top;top=top->next

[tag_link]

正确答案：C

链栈(不带头结点)执行Pop 操作，并将出栈的元素存在x 中，应该执行()。

A. x=top;top=top->next B.x=top->data C. top=top->next;x=top->data D. x=top->data;top=top->next

[tag_link]

正确答案：D

经过以下栈的操作后，变量x 的 值 为 ( ) 。 InitStack(st);Push(st ,a); Push(st,b); Pop(st ,x);GetTop(st,x);

A. a B.b C. NULL D.false

[tag_link]

正确答案：A

3个不同元素依次入栈，能得到()种不同的出栈序列。

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

[tag_link]

正确答案：B

设a,b,c,d,e, f以所给的次序入栈，若在入栈操作时，允许出栈操作，则下面不会出现 的出栈序列为()。

A. fedcba B.bcafed C.dcefba D.cabdef

[tag_link]

正确答案：D

4个元素依次入栈的次序为abcd, 则以cd 开头的出栈序列的个数为()。

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

[tag_link]

正确答案：A

用 S 表示入栈操作，用X表示出栈操作，若元素的入栈顺序是1234,为了得到1342的 出栈顺序，相应的S 和 X的操作序列为()。

A. SXSXSSXX B.SSSXXSXX C.SXSSXXSX D.SXSSXSXX

[tag_link]

正确答案：D

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

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

[tag_link]

正确答案：D

在运算类的零地址指令中，它的操作数来自（　）。

A. 暂存器和总线 B. 寄存器 C. 暂存器和 ALU D. 栈顶和次栈顶

栈

[tag_link]

正确答案：D

零地址指令在指令格式中没有显式的地址字段，操作数的来源是隐含的。

对于运算类的零地址指令，通常用于堆栈型计算机架构。 在这种架构中，操作数存储在堆栈的顶部，执行运算时，指令会从堆栈中弹出所需操作数。 例如，加法指令会弹出栈顶和次栈顶的两个操作数进行相加，然后将结果压回堆栈。 因此，运算类零地址指令的操作数直接来自栈顶和次栈顶。

选项A、B、C均不符合零地址指令的特点：A中的暂存器和总线常见于其他寻址方式； B中的寄存器通常对应一地址或二地址指令； C中的ALU是运算单元，而非操作数来源。 只有D正确描述了零地址指令在堆栈架构下的操作数来源。

若栈的输入序列是1,2,3, …,n, 输出序列的第一个元素是 i, 则第j 个输出元素是()。

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

[tag_link]

正确答案：

一条双字长直接寻址的子程序调用 CALL 指令，其第一个字节是操作码和寻址特征，第二个字节是地址码 5000H。假设 PC 当前值为 1000H，SP 的内容为 0100H，栈顶内容为 1234H，存储器按字编址，而且进栈操作是先 (SP) ← (SP)，后存入数据。则 CALL 指令执行后，SP 及栈顶的内容分别为（ ）。

A. 00FFH, 1000H B. 0101H, 1000H C. 00FEH, 1002H D. 00FFH, 1002H

栈

[tag_link]

正确答案：D

首先，`CALL` 指令为双字长直接寻址，且存储器按字编址，因此指令占用两个字：第一个字包含操作码和寻址特征，第二个字为地址码 `5000H`。 程序计数器当前值为 `1000H`，即指令起始地址，故指令占地址 `1000H` 和 `1001H`，下一条指令地址为 `1002H`，此即返回地址。

其次，执行 `CALL` 指令时需将返回地址压栈。 初始栈指针 `SP=0100H`，栈顶内容（地址 `0100H` 处）为 `1234H`。 进栈操作描述“先 `(SP) ← (SP)`，后存入数据”应理解为栈向下增长，压栈前 `SP` 先减 `1`（因按字编址，压入一个字占用一个地址单位），即

$$SP\leftarrow SP-1=00FFH,$$

然后将返回地址 1002H 存入新 SP 指向的地址 00FFH。

因此，执行后 `SP=00FFH`，栈顶内容（地址 `00FFH` 处）`=1002H`。 选项 D 符合。

某栈的输入序列为a,b,c,d, 下面的4个序列中，不可能为其输出序列的是()。

A. a,b,c,d B.c,b,d,a C.d,c,a,b D.a,c,b,d

[tag_link]

正确答案：C

若栈的输入序列是P₁,P₂, … ,Pn, 输出序列是1,2,3, …,n, 若 P₃=1, 则 P₁ 的 值 ( ) 。

A. 可能是2 B. 一 定是2 C. 不可能是2 D. 不可能是3

[tag_link]

正确答案：C

若栈的输入序列是P₁,P₂, … ,Pn, 输出序列是1,2,3, …,n, 若P₃=3, 则 P₁ 的 值 ( ) 。

A. 可能是2 B. 不可能是1 C. 一 定 是1 D. 一 定是2

[tag_link]

正确答案：A

已知栈的入栈序列是1,2,3,4,其出栈序列为P₁,P₂,P₃,P₄, 则 P₂,P₄ 不 可 能 是 ( ) 。 A.2,4 B.2,1 C.4,3 D.3,4

[tag_link]

正确答案：C

设栈的初始状态为空，当字符序列“n1_” 作为栈的输入时，输出长度为3,且可用作C 语言标识符的序列有()个。

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

[tag_link]

正确答案：C

采用共享栈的好处是()。

A. 减少存取时间，降低发生上溢的可能 B. 节省存储空间，降低发生上溢的可能 C. 减少存取时间，降低发生下溢的可能 D. 节省存储空间，降低发生下溢的可能

[tag_link]

正确答案：B

设有一个顺序共享栈 Share[0:n-1], 其中第一个栈顶指针 top1 的初值为-1,第二 个栈顶指针top2 的初值为n, 则判断共享栈满的条件是()。

A. top2-top1==1 B.top1-top2==1 C. top1 ==top2 D. 都不对

[tag_link]

正确答案：A

有5个元素，其入栈次序为A,B,C,D,E, 在各种可能的出栈次序中，第一个出栈元素 为C 且第二个出栈元素为D 的出栈序列有哪几个?

[tag_link]

B

若元素的入栈序列为A,B,C,D,E, 运用栈操作，能否得到出栈序列B,C,A,E,D 和 D,B, A,C,E? 为什么?

[tag_link]

C

栈的初态和终态均为空，以 I 和0分别表示入栈和出栈，则出入栈的操作序列可表 示为由I 和 O 组成的序列，可以操作的序列称为合法序列，否则称为非法序列。 1)下面所示的序列中哪些是合法的? 2)通过对1)的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回 true, 否则返回false ( 假定被判定的操作序列已存入一维数组中)。

A. IOIIOIOO B.IOOIOIIO C.IIOIOIO D.ⅢOOIOO

[tag_link]

B

总体上说，“按需调页”（Demand-paging）是一个很好的虚拟内存管理策略。但是，有些程序设计技术并不适合于这种环境。例如，（ ）。

A. 堆栈 B. 线性搜索 C. 矢量运算 D. 二分搜索

操作系统概念 栈

[tag_link]

正确答案：D

按需调页（Demand-paging）是一种虚拟内存管理策略，它在页面被实际访问时才将其加载到内存中，依赖于程序的局部性原理来减少页面错误和提高性能。 适合该环境的程序通常具有良好时间或空间局部性，即访问模式集中或连续。

堆栈操作集中在栈顶，具有高度局部性； 线性搜索顺序访问元素，连续内存访问利于页面重用； 矢量运算通常涉及顺序或规律数据访问，也能有效利用页面。 这些技术都能较好适应按需调页。

然而，二分搜索需要在有序数组中反复跳跃访问中间元素，访问模式非连续且不可预测，导致频繁跨页面访问。 这种低局部性会引发大量页面错误，显著降低系统效率，因此不适合按需调页环境。

设单链表的表头指针为L, 结点结构由data 和next 两个域构成，其中data 域为字符型。 设计算法判断该链表的全部n个字符是否中心对称。例如，xyx 、xyyx 都是中心对称的。

[tag_link]

C

设有两个栈 S1 、S2 都采用顺序栈方式，并共享一个存储区[0, …,maxsize-1], 为了 尽量利用空间，减少溢出的可能，可采用栈顶相向、迎面增长的存储方式。试设计S1、 S2 有关入栈和出栈的操作算法。

[tag_link]

B