文档介绍：《数据结构》期末复****题及参考答案- 第3章栈和队列
一、选择题
1、对于栈,操作数据的原则是( )。
A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序
2、要求数据遵循FIFO(先进先出)原则的数据结构是( )。
A. 线性表 B. 链表 C. 队列 D. 栈
3、若进栈的序列为1,2,3,4,则以下哪一个不可能是一个出栈序列。
,2,4,1 ,2,1,4 ,2,3,1 ,3,2,4
4、有六个元素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
5、设栈的输入序列是1,2,3,4, 则( )不可能是其出栈序列。
A. 1,2,4,3, B. 2,1,3,4, C. 1,4,3,2, D. 4,3,1,2,
6、在一个链队列中,若f,r分别为队首、队尾指针,则插入s所指结点的操作为( )
(A) f->next=c;f=s (B) r->next=s;r=s
(C) s->next=r;r=s (D) s->next=f;f=s
7、一个栈的输入序列为1 2 3 4 5,则下列序列中不可能是栈的输出序列的是( )。
A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2
8、数字1、2依次入栈,则出栈的顺序可能有( )种情况;数字1、2依次进入队列,则出队列的顺序可能有( )种情况。
A. 1 , 2 B. 2 , 1 C. 2 , 2 D. 1 , 1
9、设一个栈的输入序列是 1,2,3,4,5,则下列序列中,是栈的合法输出序列的是( )。A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4
10、某堆栈的输入序列为a, b,c ,d,下面的四个序列中,不可能是它的输出序列的是( )。
A. a,c,b,d B. b, c,d,a C. c, d,b, a D. d, c,a,b
11、顺序存储的栈和队列中已经各有N个结点,要删除一个结点分别需要移动数据( )次和( )次。
A. N/2 , N B. N , N/2 C. 0 , N D. N , 0
12、设有三个元素X,Y,Z顺序进栈(进的过程中允许出栈),下列得不到的出栈排列是( )。
B. YZX C. ZXY D. ZYX
13、一个递归算法必须包括( )。
A. 递归部分 B. 终止条件和递归部分 C. 迭代部分
14、如下四个选项中,那个选项是能够正确判断循环队列是否排满元素的操作(其中MAXQSIZE表示队列的容量) ( ):
( == ) …
( == ( + MAXQSIZE))
( == ( + 1) % MAXQSIZE)
( == ( + 1) % MAXQSIZE)
15、假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear,则当前队列中的元素个数为( )。
A.(rear-front+m)%m -front+1
C.(front-rear+m)%m D.(rear-front)%m
16、若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0和3,当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为多少?( )
A. 1和 5 B. 2和4 C. 4和2 D. 5和1
17、利用栈进行十进制数1348转换成八进制数,则入栈的数依次是( )。
A. 1 , 3 , 4 , 8 B. 8 , 4 , 3 , 1 C. 2 , 5 , 0 , 4 D. 4 , 0 , 5 , 2
18、最大容量为n的循环队列,队尾指针是rear,队头是front,则队空的条件是( )。
A. (rear+1) MOD n=front B. rear=front
+1=front D. (rear-l) MOD n=front
19、栈和队列的共同点是( )。
A. 都是先进先出 B. 都是先进后出
C. 只允许在端点处插入和删除元素 D. 没有共同点
二、填空题
1、栈是___操作受限(或限定仅在表尾进行插入和删除操作) 的线性表,其运算遵循___后进先出____的原则。
2、队列的插入操作在_ 队尾__进行,删除