手机扫描二维码答题
00:00:00
第4章-栈、队列（常规课版）
录音中...
*
您的姓名：
*
1.
给定一个足够大的空栈，有4个元素的进栈次序为A、B、C、D，则以CD开头的出栈序列的个数为（）?
3
2
1
4
若出栈序列为CD…，则A、B、C进栈，C出栈，D进栈，D出栈，此后只有B出栈和A出栈一种情况，所以这样的出栈序列只有CDBA一个。
*
2.
设循环队列qu中数组data的下标是0~N-1，其队头、队尾指针分别为f和r（f指向队首元素的前一位置，r指向队尾元素），元素x进队的操作是（）?
qu.rear++
qu.front++;
qu.rear=(qu.rear+1)%N
qu.front=(qu.front+1)%N
对于循环队列，进队操作仅移动队尾指针，元素x进队的操作是:qu.rear=(qu.rear+1)%N; qu.data[qu.rear]=x。
*
3.
若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）?
1和5
2和4
4和2
5和1
rear=0，进队2个元素后，rear循环递增2，rear=2;front=3，出队一个元素后，front循环递增1，front=4。
*
4.
栈和队列的不同点是（）?
都不是线性表
没有不同点
都是线性表
栈只能在同一端进行插入删除操作，而队列在不同端进行插入删除操作
栈和队列的不同点是，栈在同一端进行插入和删除操作，而队列在不同端进行插入和删除操作。
*
5.
在设计链栈时，通常采用单链表作为链栈，而不采用双链表作为链栈，其准确的原因是（）?
双链表存储密度较单链表低
栈中元素是顺序存取的，用单链表就足够了
双链表运算较单链表更复杂
栈中元素是随机存取的，用单链表就足够了
因为栈中元素是顺序存取的（指逐个存或取结构中的元素），而不是随机存取的，用单链表就足够了。
*
6.
假设用一个不带头节点的单链表表示队列，队头在链表的（）位置?
链头
链尾
以上都可以
链中
在用单链表表示的链队中，以单链表的链头作为队头，以单链表的链尾作为队尾。
*
7.
设循环队列qu中数组data的下标是0~N-1，其队头、队尾指针分别为f和r（f指向队首元素的前一位置，r指向队尾元素），元素x出队的操作是（）?
qu.front++;
qu.rear++
qu.front=(qu.front+1)%N
qu.rear=(qu.rear+1)%N
对于循环队列，出队操作仅移动队头指针，元素x出队的操作是:qu.front=(qu.front+1)%N; x=qu.data[qu.front]。
*
8.
若元素a、b、c、d、e、f依次进栈，允许进栈、退栈的操作交替进行，但不允许连续3次退栈工作，则不可能得到的出栈序列是（）?
afedcb
bcaefd
dcebfa
cbdaef
选项D操作:a进，a出，b进，c进，d进，e进，f进，f出，e出，d出，c出，b出。从中看到，选项D中最后连续出栈5次，不符合要求。
*
9.
若元素3、7、1、9、4依次入栈，允许进栈、退栈的操作交替进行，则下列哪些是可能的出栈序列?
【多选题】
3、7、1、9、4
3、1、7、9、4
9、4、1、7、3
7、3、1、9、4
1、7、3、9、4
4、9、1、7、3
*
10.
已知循环队列存储在一维数组A[0..n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列空，且要求第一个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是（）?
0,0
0,n-1
n-1,n-1
n-1,0
在循环队列中，进队操作是队尾指针rear循环加1，再在该处放置进队的元素，本题要求第一个进入队列的元素存储在A[0]处，则rear应为n-1，因为这样(rear+1)%n=0。而队头指向队头元素，此时队头位置为0，所以front的初值为0。
*
11.
若用链式存储实现栈，则出栈操作的时间复杂度为（ ）
O(n log n)
O(log n)
O(1)
O(n)
链式栈出栈在头节点，时间复杂度为 O(1)。
*
12.
设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是（）?
6
3
2
4
根据出队序列分析，栈S的容量至少需要3个位置才能完成相应的操作。
*
13.
用带头结点的单链表用链接方式存储的队列，在进行出队操作时（）?
头、尾指针都不修改
仅修改尾指针
头、尾指针都要修改
仅修改头指针
用带头结点的单链表存储队列时，出队操作只需要修改头结点的next指针，不需要修改头尾指针。
*
14.
在顺序栈中，判断栈是否已满的条件是（ ）
top == rear
top == MaxSize
top == 0
top == MaxSize - 1
数组从下标 0 开始，最后一个合法位置是 MaxSize - 1。
*
15.
一个栈的进栈序列是a、b、c、d、e，则栈的不可能的输出序列是（）?
decba
edcba
dceab
abcde
对于选项C，a、b、c、d进栈，d出栈，c出栈，e进栈，e出栈，此时栈中从栈底到栈顶为a、b，不可能a先出栈，所以C是不可能的输出序列。
*
16.
若一个栈用数组data[1..n]存储，初始栈顶指针top为n+1，则以下元素x进栈的正确操作是（）?
top++; data[top]=x;
data[top]=x; top++;
top--; data[top]=x;
data[top]=x; top--;
初始栈顶指针top为n+1，说明data[n]端作为栈底，在进栈时top应递减。
*
17.
栈的"先进后出"特性是指（）?
每当有出栈操作时，总要先进行一次进栈操作
每次出栈的元素总是最先进栈的元素
同时进行进栈和出栈操作时，总是进栈优先
最后进栈的元素总是最先出栈
栈的"先进后出"特性是指最后进栈的元素总是最先出栈，这是栈的基本特性。
*
18.
若一个循环队列初始 `front=0`、`rear=0`，插入两个元素后的状态是（ ）
front = 0, rear = 1
front = 1, rear = 2
front = 2, rear = 2
front = 0, rear = 2
循环队列入队后 `rear` 向后移动，`front` 不变。
*
19.
下列操作序列中，不可能是合法的栈操作顺序的是（ ）
Push(1), Push(2), Pop(), Push(3), Pop()
Push(1), Push(2), Pop(), Pop()
Push(1), Pop(), Pop()
Push(1), Push(2), Push(3), Pop()
连续两次 Pop，元素只有一个，不合法。
*
20.
下列关于循环队列的描述，错误的是（ ）
队满条件是 (rear+1)%MaxSize == front
空队列的条件是 front == rear
入队时 rear = (rear + 1) % MaxSize
出队时 front = (rear + 1) % MaxSize
出队应该是 front = (front + 1) % MaxSize。
*
21.
栈和队列的共同点是（）?
没有共同点
都是先进后出
都是先进先出
只允许在端点处插入和删除元素
栈和队列都是限制存取点的线性结构，只允许在端点处插入和删除元素。
*
22.
一个循环队列中用data[0..n-1]数组保存队中元素，另设置一个队尾指针rear和一个记录队中实际元素个数的变量count，则该队中最多可以存放的元素个数是（）?
(rear+n)%n
n-1
(n-rear)%n
n
队满的条件为count==n。
*
23.
栈是一种特殊的线性表，它所有的插入和删除都限制在表的同一端进行。（）
错
对
栈的特性是后进先出。
*
24.
用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行出队操作时（）?
队头、队尾指针都要修改
仅修改队头指针
队头、队尾指针都可能要修改
仅修改队尾指针
用不带头结点的单链表存储队列时，出队操作只需要修改队头指针，指向下一个结点。
*
25.
若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少（）?
5和1
2和4
1和5
4和2
删除一个元素后front=4，加入两个元素后rear=2。
*
26.
循环队列存储在数组A[0..m]中，则入队时的操作为（）?
rear=(rear+1)mod(m-1)
rear=rear+1
rear=(rear+1)mod m
rear=(rear+1)mod(m+1)
数组A[0..m]的大小为m+1，所以入队时rear=(rear+1)mod(m+1)。
*
27.
在循环队列中，元素的排列顺序（）?
由元素进队的先后顺序确定
与队头和队尾指针的取值有关
与元素值的大小有关
与队中数组大小有关
在循环队列中，元素的排列顺序仅与元素进队的先后顺序有关。
*
28.
顺序栈的判空条件为（ ）
top == front
top == MaxSize
top == -1
top == 0
顺序栈通常从下标 0 开始，top 为 -1 表示空栈。
*
29.
栈和队列都是（）?
限制存取点的线性结构
限制存取点的非线性结构
链式存储的非线性结构
顺序存储的线性结构
栈和队列都是限制存取点的线性结构，它们都是线性表，但限制了插入和删除的位置。
*
30.
若元素5、2、8、6、1依次入栈，允许进栈、退栈的操作交替进行，则下列哪些是可能的出栈序列?（多选题）
【多选题】
5、2、8、6、1
1、6、8、2、5
8、6、2、5、1
2、5、8、6、1
6、8、2、5、1
*
31.
若元素9、3、7、2、8依次入栈，允许进栈、退栈的操作交替进行，但不允许连续3次退栈工作，则下列哪些是不可能的出栈序列?（多选题）
【多选题】
8、2、7、3、9
2、8、7、3、9
7、3、9、2、8
3、9、7、2、8
9、3、7、2、8
9、7、3、2、8
*
32.
假设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（）?
(rear-front)%m
rear-front+1
(rear-front+m)%m
(front-rear+m)%m
循环队列中元素个数的计算公式为(rear-front+m)%m，其中m为数组大小。
*
33.
与顺序队相比，链队（）?
缺点是不能根据队首和队尾指针计算队的长度
优点是进队和出队时间性能更好
缺点是不能进行顺序访问
优点是可以实现无限长队列
尽管链队总是采用动态分配方式，其长度也受内存大小的限制，也不可能实现无限长队列。顺序队和链队的进队和出队操作时间均为O(1)。顺序队和链队都可以进行顺序访问。在顺序队中可以通过队头和队尾指针计算队中元素个数，而链队不能。
*
34.
设循环队列的存储空间为a[0..20]，且当前队头指针（f指向队首元素的前一位置）和队尾指针（r指向队尾元素）的值分别为8和3，则该队列中元素个数为（）?
5
16
17
6
这里MaxSize=21，其中的元素个数=(r-f+MaxSize)%MaxSize=16。
*
35.
当用一个数组data[0..n-1]存放栈中元素时，栈底最好（）?
设置在data[n-1]处
设置在data数组的任何位置
设置在data[0]处
设置在data[0]或data[n-1]处
栈中元素的逻辑关系呈现线性关系，这样有两个端点，最好将栈底设置在某个端点data[0]或data[n-1]处，从而方便栈运算算法的设计。
*
36.
若采用链式存储实现队列，则入队操作应插入在（ ）
表头
表尾
中间节点后
任意位置
队列是先进先出，入队应在尾部插入。
*
37.
用单链表表示的链式队列的队头在链表的（）位置?
链尾
链头
链中
第一个真实节点
用单链表表示的链式队列，队头在第一个真实节点位置。
*
38.
最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）?
rear+1=front
(rear-1)MOD n=front
(rear+1)MOD n=front
rear=front
循环队列队空的条件是rear=front。
*
39.
在栈中，插入和删除操作发生在（ ）
中间位置
任意位置
栈顶
栈底
栈是后进先出（LIFO）结构，插入和删除都在栈顶进行。
*
40.
若一个栈执行操作:Push（A），Push(B)，Pop()，Push(C)，则栈顶元素为（ ）
B
空栈
C
A
出栈的是 B，C 入栈后在栈顶。
*
41.
若某循环队列有队首指针front和队尾指针rear，在队不空时出队操作仅会改变（）?
front
rear
front和rear
以上都不对
当循环队列不空时，出队操作只能改变队头指针front。
*
42.
通常设置循环队列qu的队空条件（front队首指针指向队首元素的前一位置，rear队尾指针指向队尾元素）是（）?
(qu.rear+1)%MaxSize==(qu.front+1)%MaxSize
qu.rear==qu.front
(qu.rear+1)%MaxSize==qu.front
(qu.rear+1)%MaxSize==qu.front+1
在循环队列中，通常设置队头等于队尾时表示队空。
*
43.
队列的存储结构通常采用（ ）
只能链式存储
只能顺序存储
树形存储
顺序存储或链式存储
队列既可以用数组实现顺序存储，也可以用链表实现链式存储。
*
44.
若一个栈用数组data[1..n]存储，初始栈顶指针top为0，则以下元素x进栈的正确操作是（）?
top++; data[top]=x;
top--; data[top]=x;
data[top]=x; top--;
data[top]=x; top++;
初始栈顶指针top为0，说明data[1]端作为栈底，在进栈时top应递增，由于不存在data[0]的元素，所以在进栈时应先将top递增，再将x放在top处。
*
45.
以下哪一项不是栈的应用场景?（ ）
表达式求值
函数调用实现
括号匹配
图的广度优先遍历
广度优先遍历使用队列实现。
*
自己名字签名
请在以下矩形区域内绘制
清空
撤销
橡皮擦
确定并上传
评价对象得分
字体大小
第4章-栈、队列（常规课版）
复制
