栈的类型定义
栈的应用举例
栈类型的实现
队列的类型定义
队列类型的实现
第三章栈和队列
队列的应用
(window.slotbydup=window.slotbydup || []).push({
id: '4090793',
container: s,
size: '920,90',
display: 'inlay-fix'
计算机资料
工厂管理者读物，充电必备。
王圻—续文献通考
王圻—续文献通考
marx and foucault
在此可输入您对该资料的评论~
资料评价：
所需积分：21.栈和队列都是限制存取点的线性结构（TRUE） .._IT教育论坛
&>&&>&&>&&>&大家一起学习数据结构，数据结构习题集：栈和队列
大家一起学习数据结构，数据结构习题集：栈和队列
1.栈和队列都是限制存取点的线性结构（TRUE）
2.栈和队列是两种重要的线性结构。（ TRUE ）
3.带头结点的单链表形式的队列，头指针F指向队列的头结点，尾指针R指向队列的最后一个结点（FALSE）
4.在对不带头结点的链队列作出队操作时，不会改变头指针的值。（FALSE）
单项选择题：
5.若已知一个栈的入栈序列是1，2，3，&，n，其输出序列为p1，p2，p3，&，pn，若p1=n，则pi为( )。
A．i B．n=i C．n-i+1 D．不确定
[当p1=n，即n是最先出栈的，根据栈的原理，n必定是最后入栈的，那么输入顺序必定是1，2，3，&，n，则出栈的序列是n，&，3，2，1，所以答案是C。]
6．栈和队列的共同点是( )。
A．都是先进后出 B．都是先进先出
C．只允许在端点处插入和删除元素 D．没有共同点
7．若依次输入数据元素序列{a，b，c，d，e，f，g}进栈，出栈操作可以和入栈操作间隔进行，则下列哪个元素序列可以由出栈序列得到？( )
A．{d，e，c，f，b，g，a} B．{ f，e，g，d，a，c，b}
C．{e，f，d，g，b，c，a} D．{ c，d，b，e，g，a，f}
8.一个栈的入栈序列是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
9. 队列操作的原则是( )
A. 先进先出 B. 后进先出 C. 只能进行插入 D. 只能进行删除
10. 栈的插入与删除是在( )进行。
A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置
11.假设顺序栈的定义为：
typedef struct {
selemtype * /* 栈底指针*/
selemtype * /* 栈顶指针*/
/* 当前已分配的存储空间,以元素为单位*/
变量st为sqstack型，则栈st为空的判断条件为（ ）。
A． st.base == NULL B． st.top == st.stacksize
C． st.top-st.base&= st.stacksize D． st.top == st.base
12.假设顺序栈的定义同上题，变量st为sqstack型，则栈st为满的判断条件为（ ）。
A． st.base == NULL B． st.top == st.stacksize
C． st.top-st.base&= st.stacksize D． st.top == st.base
13．判断一个循环队列QU ( m0为最大队列长度(以元素为单位)，front和rear分别为队列的队头指针和队尾指针 ) 为空队列的条件是( )。
A．QU-&front == QU-&rear B．QU-&front != QU-& rear
C．QU-&front == (QU-&rear+1) % m0 D．QU-&front != (QU-&rear+1) % m0
14．判断一个循环队列QU ( m0为最大队列长度(以元素为单位)，front和rear分别为队列的队头指针和队尾指针 )为满队列的条件是( )。
A．QU-&front==QU-&rear B．QU-&front!=QU-& rear
C．QU-&front==(QU-&rear+1) % m0 D．QU-&front!=(QU-&rear+1) % m0
15．在少用一个元素空间的循环队列QU ( m0为最大队列长度(以元素为单位)，front和rear分别为队列的队头指针和队尾指针 ) 中，当队列非空时，若插入一个新的数据元素，则其队尾指针rear的变化是( )。
A．QU-&rear==(QU-&front+1) % m0 B．QU-&rear==(QU-&rear+1) % m0
C．QU-&rear==(QU-&front+1) D．QU-&rear==(QU-&rear+1)
16．在少用一个元素空间的循环队列QU ( m0为最大队列长度(以元素为单位)，front和rear分别为队列的队头指针和队尾指针 ) 中，当队列非满时，若删除一个数据元素，则其队头指针front的变化是( )。
A．QU-&front==(QU-&rear+1) % m0 B．QU-&front==(QU-&front+1)
C．QU-&front==(QU-&rear+1) D．QU-&front==(QU-&front+1) % m0
17. 线性表、栈、队列都是线性结构，可以在线性表的_________位置插入和删除元素，对于栈只能在_________位置插入和删除元素，对于队只能在________位置插入和只能在_________位置删除元素。
答：任何、 栈顶、 队尾、 队头
18．用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1,2,3,4, 为了得到1,3,4,2出栈顺序相应的S和X操作串为______________________。
答：SXSSXSXX
19. 用下标0开始的N元数组实现循环队列时，为实现下标变量m加1后在数组有效下标范围内循环，可采用的表达式是：m =____________________。
答：（m+1）% N
20. 在一个链栈中，若栈顶指针等于NULL则为_______________，在一个链队中，若队首指针与队尾指针的值相同，则表示该队列为____________或该队列______________。
答： 栈空、空队、只有一个元素
21. 向一个栈顶指针为HS的链栈中插入一个新结点*P，应执行 和
答：P-&next=HS、 HS=P
22. 从一个栈顶指针为HS的非空链栈中删除结点并不需要返回栈顶结点的值和回收结点时，应执行 操作。
答：HS=HS-&next
23．设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳 个元素。
[提示：栈和队列分别是后进先出表和先进先出表，6个元素入栈的顺序是按a1、a2、a3、a4、a5、a6，元素出栈后随即进入队列Q且出队列的顺序为a3、a5、a4、a6、a2、a1也就是在栈S中第一个出栈的元素是a3，那么a1、a2必须在栈S中此时栈S至少要有容纳3个元素的容量，第二个出栈的元素是a5，因此a4必在栈S中，这时栈S的容量至少容纳4个元素，依此类推，可算出栈S的容量至少容纳4个元素。]
24．栈的顺序存储结构即顺序栈，是利用 来依次存放自栈底至栈顶的数据元素；当栈为非空时，栈顶指针top始终指向 。
答：一组地址连续的存储单元 栈顶元素的下一位置
25．带有头结点的链队列，当其为空的链队列的判断条件为 。
答：头指针和尾指针均指向头结点
26．从数据结构的角度看，栈和队列是 两类线性表，但从数据类型角度看，它们是 两类重要的抽象数据类型。
答：受限制的 与线性表大不相同的
算法设计题：
27．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写相应的队列初始化、入队列和出队列的算法。
解：void InitCiQueue(CiQueue &Q)//初始化循环链表表示的队列Q
Q=(CiLNode*)malloc(sizeof(CiLNode));
Q-&next=Q;
}//InitCiQueue
void EnCiQueue(CiQueue &Q,int x)//把元素x插入循环链表表示的队列Q，Q指向队尾元素，Q-&next指向头结点，Q-&next-&next指向队头元素
p=(CiLNode*)malloc(sizeof(CiLNode));
p-&data=x;
p-&next=Q-&//直接把p加在Q的后面
Q-&next=p;
Q=p;//修改尾指针
Status DeCiQueue(CiQueue &Q,int x) //从循环链表表示的队列Q头部删除元素x
if(Q==Q-&next) return INFEASIBLE;//队列已空
p=Q-&next-&
Q-&next-&next=p-&
return OK;
}//DeCiQueue
28．利用两个栈s1，s2模拟一个队列时，如何用栈的运算来实现该队列的运算：
enqueue:插入一个元素；
dequeue:删除一个元素；
queue_empty:判定队列为空。
解：由于栈的特点是先进后出，为了模拟先进先出的队列，必须用两个栈，一个栈s1用于插入元素，另下栈s2用于删除元素，每次删除元素时应将前一个栈的所有元素读出然后进入第二个栈中，这样才能达到模拟队列的效果，这里使用栈的一些基本操作如下：
push(ST,x):栈的压入
ptop(ST,x):退出栈顶元素赋给x
sempty(ST):判定栈是否为空
void enqueue(stack &s1,int x) /* 本函数功能：向队列插入一个元素 */
if(s1.top== m0) printf(&队列上溢出！\n&);
else push(s1,x);
void dequeue(stack &s1,stack &s2,int x) /* 本函数功能：删除一个元素 */
s2.top=s1.
while(!sempty(s1)){
pop(s1,y);
push(s2,y);
ptop(s2,x);
while(!sempty(s2)){
pop(s2,y);
push(s1,y);
int queue_empty(stack s1) /* 本函数功能：判断队列是否为空 */
if sempty(s1) return(1);
else return(0);
29．假设称正读和反读都相同的字符序列为&回文& (即回文是指一个字符序列以中间字符为基准两边字符完全相同)，例如，&abba&和&abcba&是回文，&ababab&则不是回文。试编写一个判断读入的一个以&@&为结束符的字符序列是否&回文&的算法。
解：[解题思路：判断回文算法Palindrome_Test()的思想是：把字符串中的字符逐个分别存入队列和堆栈，然后逐个出队列和退栈并比较出队列的数据元素和退栈的数据元素是否相等，若全部相等则该字符序列是回文，否则就不是回文。]
实现本题功能的函数如下(类C编写)：
int Palindrome_Test() //判别输入的字符串是否是回文序列，是则返回1，否则返回0
Initstack(S); InitQueue(Q);
while ( (c =getchar()) !=&@&)
Push(S,c); EnQueue(Q,c); //同时使用栈和队列两种结构
while(!StackEmpty(S))
Pop(S,a); DeQueue(Q,b);
if(a!=b) return ERROR;
return OK;
}//Palindrome_Test
数据结构是一名基础课。要好好学习。
要得,一起学学.
一起学习好啊.
CDCDCDDDDDDDDDDDDDDCCCCCCCCC
本帖标题：
本帖地址：
注意：本论坛的任何言论仅代表发言者个人的观点，与希赛网立场无关。请对您的言论负责，遵守中华人民共和国有关法律、法规。如果您的帖子违反希赛网论坛规则，将立即删除。
&&&&&&&&&&&&
希赛网 版权所有 & &&《程序设计基础》形成性作业（3）参考答案；一、选择题（每空一分）；1、（数据）是所有能输入到计算机中被计算机加工处；2、用链表表示线性的优点是：便于插入和删除操作；3、下述哪一条是顺序存储方式的优点？存储密度大；4、线性表的顺序存储结构是一种（顺序存储）的相信；5、在一个长度为n的顺序表中删除第i(0&；6、线性表L=(a1,a2…an)，下列说法正确
《程序设计基础》形成性作业（3）参考答案
一、选择题（每空一分）
1、（数据）是所有能输入到计算机中被计算机加工处理的信息集合，（数据元素）是的基本单位，它可以由基本单位，它可以由若干个（数据项）和（数据结构）是性质相同的（数据元素）集合。
2、用链表表示线性的优点是：便于插入和删除操作
3、下述哪一条是顺序存储方式的优点？存储密度大
4、线性表的顺序存储结构是一种（顺序存储）的相信结构，线性表的链式存储结构是一种（随机存储）的存储结构。
5、在一个长度为n的顺序表中删除第i(0&i&=n)个元素时，需向前移动（n-i）个元素。
6、线性表L=(a1,a2…an)，下列说法正确的是：除第一个元素和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。
7、一个队列的人队序是1，2，3，4，则队列的输出序列是：1，2，3，4.
8、若进栈序列为1，2，3，4，进栈过程中可以出栈，则（3，1，4，2）不可能是一个出栈序列
9、队列是限制插入只能在表的一端，而删除在表的另一商进行的线性表，其特点是：先进先出
10、以下哪一个不是队列的基本运算？从队列中删除第I个元素
11、栈和队列是一种限制了插入和删除操作位置的线性表。栈插入操作只能在栈（顶）进行，删除操作只能在栈（顶）进行：队列的插入操作只能在队（尾）进行，删除操作只能在队（首）进行。
12、某二叉权的前序编历结点的访问顺序是ABCDEFG，中序编历结点的访问顺序是CBDAFGE，则其后序编历结点的访问顺序是：CDBGFEA
13、有关二叉树的下列说法正确的是：一颗二叉树的度可以小于2
14、在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序：完全相同
15、在一棵二叉树上第5层的结点数最多为：16
16、在一个图中，所有顶点的度数之和等于所有边数的（2）倍，在一个有
向图中，所有的顶点入度之和等于所有顶点的出度之和的（1）倍。
17、一个具有n个顶点的无向图中，要连通全部顶点至少需要（n-1）条边。
18、对一个具有n个顶点的图，采用邻接接矩阵表示则该矩阵的大小为：n2
19、已知一个图如下所示，则从顶点a出发按深度优先搜索遍历可以等到的一种顶点序列为：a，e，d，f，b，c
20、从未排序的序列中依次取出元素与已排序列中的元素作比较，将其放已入排序序列中的正确位置上，此方法称为：直接插入排序
二、填空题：（每空1分）
1、数据结构包括的三个方面的内容是：数据的（逻辑结构），数据的（存储结构），数据的（运算）。
2、当向一个顺序表插入一个元素时，从插入位置开始后的所有元素均需（向后移动）一个位置，移动过程是从（最后一个元素开始）向（后）依次移动每一个元素。
3、要从一个顺序表删除一个元素时，被删除之后的所有元素均需（向前移动）一个位置，移动过程是从（删除元素后的第一个元素开始）向（前）依次移动每一个元素。
4、在线性表的顺序存储中，元素之间的逻辑关系是通过（相对位置）决定的。顺序表中逻辑上相邻的元素，物理位置（也）相邻。
5、线性表、栈和队列是（线性）结构，可以在线性表的（任意）位置插入和删除元素，而栈只能在（栈顶）插入和删除元素；对于队列只能在（队尾）插入元素，在（队首）删除元素。
6、栈的插入和删除只能在栈的（栈顶）进行，队列的插入和删除分别在（两）端进行，进行插入的一端叫做（队尾），进行删除的一端叫做（队首）。
7、对于一个具有n个结点的二叉树，当它为一棵（完全）二叉树时具有最小高度，当它为一棵单支树时具有（最大）高度。
8、设无向图G的顶点数为n，图G最少有（n-1）条边，最多有（n（n-1）/2）
三、简答题：
1、假定有四个元素依次进栈，进栈过程中允许出栈，试写出所有可能的出
答：假设ABCD四元素依次进栈：（20分）
1)A进栈-&B进栈-&C进栈-&D进栈-&出栈-&出栈-&出栈-&出栈
结果：D-&C-&B-&A
2)A进栈-&B进栈-&C进栈-&出栈-&D进栈-&出栈-&出栈-&出栈
结果：C-&D-&B-&A
3)A进栈-&B进栈-&C进栈-&出栈-&出栈-&D进栈-&出栈-&出栈
结果：C-&B-&D-&A
4)A进栈-&B进栈-&C进栈-&出栈-&出栈-&出栈-&D进栈-&出栈
结果：C-&B-&A-&D
5)A进栈-&B进栈-&出栈-&C进栈-&D进栈-&出栈-&出栈-&出栈
结果：B-&D-&C-&A
6)A进栈-&B进栈-&出栈-&出栈-&C进栈-&D进栈-&出栈-&出栈
结果：B-&A-&D-&C
7)A进栈-&B进栈-&出栈-&C进栈-&出栈-&D进栈-&出栈-&出栈
结果：B-&C-&D-&A
8)A进栈-&B进栈-&出栈-&出栈-&C进栈-&出栈-&D进栈-&出栈
结果：B-&A-&C-&D
9)A进栈-&出栈-&B进栈-&C进栈-&D进栈-&出栈-&出栈-&出栈
结果：A-&D-&C-&B
10)A进栈-&出栈-&B进栈-&C进栈-&出栈-&D进栈-&出栈-&出栈 结果：A-&C-&D-&B
11)A进栈-&出栈-&B进栈-&C进栈-&出栈-&出栈-&D进栈-&出栈 结果：A-&C-&B-&D
12)A进栈-&出栈-&B进栈-&出栈-&C进栈-&D进栈-&出栈-&出栈 结果：A-&B-&D-&C
13)A进栈-&出栈-&B进栈-&出栈-&C进栈-&出栈-&D进栈-&出栈 结果：A-&B-&C-&D
2、二叉树与树之间有什么区别？一棵度为2的树与二叉树有什么区别？
答：二叉树的度最大为2，而树的度无此限制。（4分）
在二叉树中，一个结点的子树有左、右之分，不能互换位置。而度为2的树则无此限制。（5分）
3、写出对如图所示二叉树进行先序遍历、中序遍历、后序遍历时得到的顶点序列。
答：先序遍历序列：ABDEC（5分）
中序遍历序列：DEBAC（5分）
后序遍历序列：EDBCA（5分）
三亿文库包含各类专业文献、中学教育、行业资料、生活休闲娱乐、外语学习资料、各类资格考试、幼儿教育、小学教育、文学作品欣赏、16电大程序设计 作业册习题和答案3等内容。　
　电大程序设计基础实验作业答案(3)_工学_高等教育_教育专区。循环结构程序设计 [实验目的] 1、 2、 3、 熟练掌握循环流程控制语句的使用。 掌握 break 和 continu... 　电大VB程序设计形成性考核3答案_计算机软件及应用_IT/计算机_专业资料。判断题:...开放英语3形成性考核册答... 12页 2下载券 喜欢此文档的还喜欢 2012... 　2014电大《Visual Basic程序设计》形成性考核册答案_工学_高等教育_教育专区。今日...科目三实际道路驾驶考试注意事项 驾考新题抢先版+申请认证 文档贡献者 高江辉 ... 　电大程序设计基础实验作业答案(2)_工学_高等教育_教育专区。分支结构程序设计 [实验目的] 1、 2、 3、 进一步理解逻辑量的表示方法。 掌握 C 语言的逻辑运算符... 　2014 电大《VisualBasic 程序设计》形成性考核作业 答案 Visual Basic 程序设计作业答案 作业 1 一、选择题 1.D .C 2.B 3.C 4.C 5.B 6.D 7.A 8.B... 　搜 试试 3 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高等教育 ...电大程序设计基础实验作业答案(1)_教育学_高等教育_教育专区。1.#include&stdio... 　[j]; 提示: p 为指针数组,此题中 a[i][j]、p[i][j]、*(p[i]+j...程序设计基础(C)作业答案... 36页 免费
电大在线作业3:小学数学... 5页 ... 　电大《Visual Basic程序设计》形成性考核册参考答案_电大_成人教育_教育专区。《Visual Basic 程序设计》 形成性 考核册作业及答案 作业 1 一、选择题 1 、在... 　电大程序设计基础实验作业答案(4)_教育学_高等教育_教育专区。简单函数编写 [实验...#include &stdio.h& void main() { void swap(int, int); int x=3,y=...}