【数据结构】第三章 栈和队列

1.单选(2分) ‏下列关于队列的叙述正确的是（ ）。 A.在队列中只能删除数据 B.队列是先进先出的线性表 C.队列是后进先出的线性表 D.在队列中只能插入数据 正确答案：B

2.单选(2分) 一个栈的输入序列为1，2，3，…，n，若输出的第一个元素是n，则输出的第i个元素是( )。 A.不确定 B.i C.n-i D.n-i+1 正确答案：D

3.单选(2分) ‎用链接方式存储的队列，在进行出队（删除）操作时（ ）。 A.可能需要同时修改队头和队尾指针 B.必须同时修改队头和队尾指针 C.仅需修改队尾指针 D.仅需修改队头指针 正确答案：A

4.单选(2分) ‏栈和队列的共同点是（ ）。 A.只允许在端点处插入或删除元素 B.没有共同点 C.都是先进先出 D.都是后进先出 正确答案：A

5.单选(2分) ‎在具有n个单元的循环队列中，设front和rear为队头和队尾指针，则判断队满的条件是（ ）。 A.(rear+1)%n==front B.(rear-1)%n==front C.(rear-front+n)%n D.rear%n==front 正确答案：A

6.单选(2分) 用不带头结点的单链表存储队列时，在进行删除运算时（ ）。 A.头、尾指针都要修改 B.仅修改头指针 C.仅修改尾指针 D.头、尾指针可能都要修改 正确答案：D

7.单选(2分) ‎一个循环队列包含60个单元，若队尾指针rear=32，队头指针front=15 ，则当前队列中的元素个数为（ ）。 A.17 B.42 C.16 D.41 正确答案：A

8.单选(2分) 判断一个顺序栈ST（最多元素为m0）为空的条件是（ ）。 A.ST->top==m0 B.ST->top<>0 C.ST->top<>m0 D.ST->top==0 正确答案：D

9.单选(2分) 设栈的输入序列为{1,2,3,4,5,6}，则正确的输出序列为（ ）。 A.5,3,4,6,1,2 B.3,2,5,6,4,1 C.3,1,2,5,4,6 D.1,5,4,6,2,3 正确答案：B

10.单选(2分) 循环队列Q[m]存放各队列元素，已知其头尾指针front和rear，则当前队列的元素个数是( )。 A.rear-front B.rear-front-1 C.rear-front+1 D.(rear-front+m)%m 正确答案：D

11.判断(2分) 栈和队列的存储方式既可以是顺序存储，也可以是链式存储。 A.√ B.× 正确答案：A

12.判断(2分) 若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列3，2，5，6，4，1。 A.√ B.× 正确答案：B

13.填空(2分) 假设以S和X分别表示入栈和出栈操作，对输入序列1,2,3,4,5进行SXSSXSSXXX操作后，可得到序列（ ）。 正确答案：13542

14.填空(2分) 表达式求值是（ ）应用的一个典型例子。 正确答案：栈

15.填空(2分) 用单循环链表表示的队列，长度为n，若只设头指针，则入队的时间复杂度为（ ）。 正确答案：O(n) 或 O(n)

16.单选(2分) 向一个栈顶指针为top的链栈中插入一个p所指的结点时，其操作步骤是（ ）。 A.P->next=top->next;top->next=p; B.P->next=top;top=top->next; C.p->next=top;top=p; D.top->next=p; 正确答案：C

17.单选(2分) 一般情况下，将递归算法转换成等价的非递归算法应该设置( )。 A.广义表 B.堆栈 C.队列 D.数组 正确答案：B

18.填空(2分) ‏设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈的容量至少应该是（ ）。 正确答案：3

19.填空(2分) ‎用单循环链表表示的队列，长度为n，若只设头指针，则出队时间复杂度为（ ）。 正确答案：O(1)