数据结构与算法（仲恺农业工程学院）第三章测试_智慧树知到答案2021年

第三章 栈和队列：栈和队列是两个重要的数据结构。从数据结构的角度看，栈和队列也是操作受限的线性表：栈按“后进先出”的规则进行操作,队列按“先进先出”的规则进行操作，在软件设计中常用到这两种数据结构。本章讨论栈和队列的定义、表示方法和实现。通过本章学习，要求掌握的内容有：栈和队列地逻辑结构和存储结构、基本运算以及实现算法。3.1栈和队列的定义和特点:本节系统的介绍了栈和队列的定义和特点。通过本节学习，要求掌握栈与队列的定义，理解栈与队列的特点。
3.2栈的表示和操作实现:本节介绍了栈的抽象类型定义、顺序栈与链栈的表示和实现。通过本节学习，应掌握顺序栈与链栈的表示和实现。
3.3栈与递归:递归是计算机科学中的一个重要概念，对递归的研究是计算机科学领域中的一个重要课题。本节介绍了采用递归算法解决的问题、递归过程与递归工作栈、递归算法的效率分析及将递归转换为非递归的方法。通过本节学习，应该理解递归过程，掌握递归算法的效率分析及递归转换为非递归的方法。
3.4队列的表示和操作实现:本节介绍了队列的抽象类型定义、循环队列及链队的表示和实现。通过本节学习，应掌握循环队列及链队的表示和实现，了解限定性数据结构的其它队列。
3.5典型栈和队列案例分析与实现:本节通过迷宫探索求解、表达式求值案例展示了用栈来处理具有递归结构问题的求解过程；通过迷宫的最短路径求解案例展示了队列做为辅助数据结构，用来暂时存储需要按照一定次序依次处理但尚未处理的元素的应用过程。通过本节学习，应掌握栈与队列在问题求解过程中的应用。

[单选题]设有一顺序栈S，元素s1,s2,s3,s4,s5,s6 依次进栈，如果6个元素出栈的顺序是s2,s4,s3,s6,s5,s1，则栈的容量至少应该是
2
5
4
3
答案：3
[单选题]一个栈的入栈序列是1，2，3，4，5，则栈的不可能输出序列是
5,4,3,1,2
1,2,3,4,5
3,2,4,5,1
3,5,4,2,1[单选题]一个队列的入队序列是1，3，5，7，9，则出队的输出序列只能是
1,5,9,3,7
9,5,1,7,3
1,3,5,7,9
9,7,5,3,1[单选题]设循环队列中数组的下标范围是1～n，其头尾指针分别为f和r，则其元素个数为
r-f
(r-f+n)%n
(r-f)%n+1
r-f+1[单选题]设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行入队操作后其尾指针rear值为
rear=(rear+1)%m
rear=rear+1
rear=(rear-1)%m
rear=(rear+1)%(m-1)[单选题]递归过程或函数调用时，处理参数及返回地址，使用的数据结构是
多维数组
栈
线性表
队列[单选题]栈中元素的进出原则是
先进先出
栈空则进
后进先出
栈满则出[单选题]判定一个栈ST（最多元素为m0）为空的条件是
ST->top==m0
ST->top0
ST->topm0
ST->top==0[单选题]判定一个队列QU（最多元素为m0）为满队列的条件是
QU->rear － QU->front －1= = m0 
QU->front = = QU->rear 
QU->front = = QU->rear +1
QU->rear － QU->front = = m0 [单选题]在一个链式队列中.假设f和r分别为队头和队尾指针,则插入s所指的结点运算是
r->next=s;r=s; 
s->next=s;r=s; 
f->next=s;f=s; 
s->next=f;f=s; [单选题]向一个栈指针为HS的链式栈中插入一个s所指的结点时,则执行
 S->NEXT=HS;HS=HS->NEXT; 
HS->NEXT=S; 
S->NEXT=HS->NEXT;HS->NEXT=S;[单选题]设一个栈的输入序列是1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（ ）。
43 1 25
3 2 15 4 
5 1 23 4 
45 1 32[单选题]进栈序列为a，b，c，则通过入、出栈可能得到的a，b，c的不同排列个数是（）。
4
6
5
7[单选题]表达式a*(b+c)-d 的后缀表达式是( )。
abc+*d- 
-+*abcd 
abc*+d- 
abcd*+-[单选题]设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。
栈
线性表的顺序存储结构
队列
线性表的链式存储结构 [单选题]用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( )。
队头、队尾指针都可能要修改
仅修改队尾指针
队头、队尾指针都要修改
仅修改队头指针[单选题]假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（）。
(rear-front)%m 
(rear-front+m)%m 
(front-rear+m)%m 
rear-front+1  [单选题]循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是(  )。 
rear-front 
rear-front+1  
(rear-front+m)%m 
rear-front-1  [单选题]若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？() 
4和2
2和4
5 和1 
1 和5[单选题]栈和队都是（）。 
限制存取点的线性结构
限制存取点的非线性结构
链式存储的非线性结构 
顺序存储的线性结构 [单选题]栈的操作原则是（ ）。 
顺序进出 
后进先出
后进后出 
先进先出[单选题]下面术语中，与数据的存储结构无关的是（ ）。 
循环队列 
顺序栈 
顺序表
栈[单选题]栈和队列具有相同的（ ）。 
存储结构
逻辑结构 
运算
抽象数据类型[单选题]递归算法必须包括（ ）。 
终止条件和迭代部分 
终止条件和递归部分  
递归部分
迭代部分