数据结构：栈和队列期末单元测试与答案.pdf

一、单选题

1、经过以下栈运算后，x的值是（）。

InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s,x);

A.b

B.0

C.1

D.a

正确答案：D

2、若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）

种情况。

A.2，3，5，4，1

B.5，4，3，2，1

C.2，1，5，4，3

D.4，3，1，2，5

正确答案：D

3、若链栈采用无头结点的单链表存储，top指向栈顶。若想摘除栈顶

结点，并将删除结点的值保存到x中,则应执行操作（）。

A.x=top-data;top=top-next；

B.top=top-link;x=top-next；

C.x=top-next；

D.x=top;top=top-next；

正确答案：A

4、数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前

一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算

队列中元素个数的公式为（）。

A.n+r-f

B.n+r-f)%n

C.r-f

D.(n+f-r)%n

正确答案：B

5、设有一个递归算法如下

intfact(intn){//n大于等于0

if(n=0)

return1;

else

returnn*fact(n-1);

}

则计算fact(n)需要调用该函数的次数为（）。

A.n+2

B.n

C.n-1

D.n+1

正确答案：D

6、栈在（）中有所应用。

A.表达式求值

B.递归调用

C.其他三个选项

D.函数调用

正确答案：C

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.2

C.4

D.3

正确答案：D

9、若一个栈以一维数组V[1..n]存储，初始栈顶指针top设为n+1，则

元素x进栈的正确操作是()。

A.V[top]=x;top++;

B.top++;V[top]=x;

C.V[top]=x;top--;

D.top--;V[top]=x;

正确答案：D

10、设计一个判别表达式中左，右括号是否配对出现的算法，采用（）

数据结构最佳。

A.线性表的顺序存储结构

B.队列

C.线性表的链式存储结构

D.栈

正确答案：D

11、用链式方式存储的队列，在进行删除运算时（）。

A.头、尾指针可能都要修改

B.仅修改头指针

C.仅修改尾指针

D.头、尾指针都要修改

正确答案：A

12、循环队列存储在数组A[0..m]中，则入队时的操作为（）。

A.rear=(rear+1)%(m+1)

B.rear=rear+1

C.rear=(rear+1)%m

D.rear=(rear+1)%(m-1)

正确答案：A

13、最大容量为n的循环队列，队尾指针是rear，队头是front，则

队空的条件是（）。

A.(rear-l)%n==front

B.rear+1==front

C.rear==front

D.(rear+1)%n==front

正确答案：C

14、栈和队列的共同点是（）。

A.只允许在端点处插入和删除元素

B.都是先进先出

C.都是先进后出

D.