数据结构习题汇编03第三章栈和队列试题.pdf

《数据结构习题汇编03第三章栈和队列试题.pdf》由会员分享，可在线阅读，更多相关《数据结构习题汇编03第三章栈和队列试题.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、先天下之忧而忧，后天下之乐而乐。范仲淹以家为家，以乡为乡，以国为国，以天下为天下。管子牧民第三章 栈和队列 试题 一、单项选择题 1.栈的插入和删除操作在（）进行。A.栈顶 B.栈底 C.任意位置 D.指定位置 2.当利用大小为 n 的数组顺序存储一个栈时，假定用 top=n 表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改 top 指针。A.top+;B.top-;C.top=0;D.top;3.若让元素 1,2,3 依次进栈，则出栈次序不可能出现（）种情况。A.3,2,1 B.2,1,3 C.3,1,2 D.1,3,2 4.在一个顺序存储的循环队列中，队头指针指向队头元素的（）位

2、置。A.前一个 B.后一个 C.当前 D.后面 5.当利用大小为 n 的数组顺序存储一个队列时，该队列的最大长度为（）。A.n-2 B.n-1 C.n D.n+1 6.从一个顺序存储的循环队列中删除一个元素时，需要（）。A.队头指针加一 B.队头指针减一 C.取出队头指针所指的元素 D.取出队尾指针所指的元素 7.假定一个顺序存储的循环队列的队头和队尾指针分别为 front 和 rear，则判断队空的条件为（）。A.front+1=rear B.rear+1=front C.front=0 D.front=rear 8.假定一个链式队列的队头和队尾指针分别为 front 和 rear，则判断队

3、空的条件为（）。A.front=rear B.front!=NULL C.rear!=NULL D.front=NULL 9.设链式栈中结点的结构为（data,link），且 top 是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针 s 所指的结点，则应执行操作（）。A.top-link=s;B.s-link=top-link;top-link=s;C.s-link=top;top=s;D.s-link=top;top=top-link;10.设链式栈中结点的结构为（data,link），且 top 是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到 x 中，则应执行操作（

4、）。A.x=top-data;top=top-link;B.top=top-link;x=top-data;C.x=top;top=top-link;D.x=top-data;11.设循环队列的结构是#define MaxSize 100 typedef int ElemType;typedef struct 人之为学，不日进则日退，独学无友，则孤陋而难成；久处一方，则习染而不自觉。顾炎武宠辱不惊，看庭前花开花落；去留无意，望天上云卷云舒。洪应明 ElemType baseMaxSize;int front,rear;Queue;若有一个 Queue 类型的队列 Q，则判断队列满的条件应是语句

5、（）。A.=;B.-=MaxSize;C.+=MaxSize;D.=+1)%MaxSize;12.设循环队列的结构是#define MaxSize 100 typedef int ElemType;typedef struct ElemType baseMaxSize;int front,rear;Queue;若有一个 Queue 类型的队列 Q，则应用语句（）计算队列元素个数。A.-+MaxSize)%MaxSize;B.-+1;C.-1;D.-Qfront;13.在做进栈运算时,应先判断栈是否（）A.空 B.满 C.上溢 D.下溢 14.为增加内存空间的利用率和减少溢出的可能性，由两个栈共

6、享一片连续的内存空间时,应将两栈的（）分别设在这片内存空间的两端。A.长度 B.深度 C.栈顶 D.栈底 15.使用两个栈共享一片内存空间时，当（）时，才产生上溢。A.两个栈的栈顶同时到达这片内存空间的中心点 B.其中一个栈的栈顶到达这片内存空间的中心点 C.两个栈的栈顶在这片内存空间的某一位置相遇 D.两个栈均不空,且一个栈的栈顶到达另一个栈的栈底 二、填空题 1.栈是一种限定在表的一端插入和删除的线性表，它的特点是_。2.队列是一种限定在表的一端插入，在另一端删除的线性表，它的特点是_。3.队列的插入操作在_进行，删除操作在_进行。4.向一个顺序栈插入一个元素时，首先使_后移一个位置，然后

7、把待插入元素写入到这个位置上。5.从一个顺序栈中删除元素时，需要将_前移一位位置。6.若设顺序栈的最大容量为 MaxSize，则判断栈满的条件是_。以家为家，以乡为乡，以国为国，以天下为天下。管子牧民海纳百川，有容乃大；壁立千仞，无欲则刚。林则徐7.当用长度为 MaxSize 的数组顺序存储一个栈时，若用 top=MaxSize 表示栈空，则表示栈满的条件为_。8.在一个链式栈中，若栈顶指针等于 NULL 则为_。9.在向一个链式栈插入一个新结点时，首先把栈顶指针中存放的结点地址赋给新结点的指针域，然后把新结点的存储位置赋给_。10.向一个栈顶指针为 top 的链式栈中插入一个新结点*p 时，

8、应执行_和_操作。11.从一个栈顶指针为 top 的非空链式栈中删除结点并不需要返回栈顶结点的值和回收结点时，应执行_操作。12.设循环队列 Q 的队头和队尾指针分别为 front 和 rear，则判断队空的条件为_。13.设循环队列 Q 的队头和队尾指针分别为 front 和 rear，队列的最大容量为 MaxSize，且规定判断队空的条件为=，则判断队满的条件为_。14.向一个循环队列中插入元素时，需要首先移动_，然后再向所指位置写入新插入的元素。15.在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列为_或该队列_。16.假定 front 和 rear 分别为链式队列的队头和队

9、尾指针，则该队列中只有一个结点的条件为_。17.双端队列是限定插入和删除操作在表的_进行的线性表。18.中缀表达式 3*(x+2)-5 所对应的后缀表达式为_。19.后缀表达式“4 5*3 2+-”的值为_。20.设有一个顺序栈 S，元素 s1,s2,s3,s4,s5,s6依次进栈，如果 6 个元素的出栈顺序为 s2,s3,s4,s6,s5,s1，则顺序栈的容量至少应为_。三、判断题 1.每次从队列中取出的应是具有最高优先权的元素，这种队列就是优先级队列。2.链式栈与顺序栈相比，一个明显的优点是通常不会出现栈满的情况。3.在一个顺序存储的循环队列中，队头指针指向队头元素的后一个位置。4.栈和队

10、列都是顺序存取的线性表，但它们对存取位置的限制不同。5.在使用后缀表示实现计算器类时使用了一个栈的实例，它起的作用是暂存运算对象和计算结果。6.在向顺序栈压入新元素时，要先按栈顶指针指示的位置存入新元素再移动栈顶指针。穷则独善其身，达则兼善天下。孟子云路鹏程九万里，雪窗萤火二十年。王实甫7.在用单链表表示的链式队列中，队头在链表的链尾位置。8.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。9.在一个循环队列 Q 中，判断队满的条件为%MaxSize+1=。10.在一个循环队列 Q 中，判断队空的条件为+1=。11.若让元素 1,2,3 依次进栈，则出栈次序 1,3,2

11、 是不可能出现的情况。12.若让元素 1,2,3 依次进栈，则出栈次序 3,1,2 是不可能出现的情况。13.在循环队列中，进队时队尾指针进一，出队时队头指针减一。14.在循环队列中，进队时队尾指针进一，出队时队头指针进一。15.在用单链表表示的链式队列 Q 中，队空条件为 Q-front=Q-rear。16.如果进栈序列是 1,2,3,4,5,6,7,8。则可能的出栈序列有 8！种。四、运算题 1.试利用运算符优先数法，画出对中缀算术表达式 a+b*c-d/e 求值时运算符栈 OPTR 和运算对象栈 OPND 的变化。运算符优先数如下表所示：运算符#(*,/,%+,-)isp（栈顶运算符优先

12、级）0 1 5 3 7 icp（栈外运算符优先级）0 7 4 2 1 2.试利用运算符优先数法，画出将中缀算术表达式 a+b*c-d/e 改为后缀表达式时运算符栈 OPTR的变化。运算符优先数如下表所示：运算符#(*,/,%+,-)isp（栈顶运算符优先级）0 1 5 3 7 icp（栈外运算符优先级）0 7 4 2 1 3.试画出对后缀算术表达式 a b c*+d e/-求值时运算对象栈 OPND 的变化。4.将二项式(a+b)i 展开,其系数构成杨辉三角形。若想按行将展开式系数的前 n 行打印出来，需要用到一个队列，存放各行展开式的系数。试画出当 n=3 的情况下，在打印过程中队列的变化。

13、#include /在里定义了链栈的抽象数据类型 void YANGVI(int n)SqQueue q;InitQueue(&q);(1);(1);int i,j,t,s=0;for(i=1;i=n;i+)cout endl;古之立大事者，不惟有超世之才，亦必有坚忍不拔之志。苏轼志不强者智不达，言不信者行不果。墨翟 (0);for(j=1;j=i+2;j+)(t);(s+t);s=t;if(j!=i+2)cout s ;5.写出下列程序段的输出结果:void main()stack S;char x,y;x=c;y=k;(x);(a);(y);(x);(t);(x);(x);(s);whil

14、e(!()(y);cout y;cout y endl;输出结果：_ 6.写出下列程序段的输出结果:void main()queue Q;char x=e,y=c;(h);(r);(y);(Q,x);(x);(x);(a);while(!()(y);cout y;cout y endl;输出结果：_ 7.简述下述算法功能 void unknown(Queue&Q)Stack S;int d;while(!()(d);(d);while(!()(d);(d);大丈夫处世，不能立功建业，几与草木同腐乎？罗贯中海纳百川，有容乃大；壁立千仞，无欲则刚。林则徐 功能是：_ 五、算法分析题 1.下面的算法

15、中使用了一个栈 st，阅读该算法，回答下列问题：(1)算法的功能是：_(2)若字符数组 A =m,a,d,a,m,i,m,a,d,a,m，执行这个算法，跟踪栈的变化。#include“”int unknown(char A,int n)stack st(n+1);int yes=1,i=0;char ch;while(Ai!=“0”)(Ai);i+;i=0;while(Ai!=“0”)(ch);if(Ai=ch)i+;else yes=0;break;return yes;2.下面的算法中使用了一个栈 st，阅读该算法，回答下列问题：(1)算法的功能是：_(2)若单链表中各结点中数据的逻辑顺序

16、为 u,n,i,v,e,r,s,i,t,y，执行这个算法，跟踪栈的变化。#include#include template void LinkList:unknown()/此单链表带有表头结点，它的表头指针为 first。StackListNode*S;ListNode*p=first-link,*q;while(p!=NULL)(p);p=p-link;p=first;p-link=NULL;while(!()/将栈中保存的结点依次出栈 (q);q-link=p-link;p-link=q;p=q;六、算法设计题 忍一句，息一怒，饶一着，退一步。增广贤文志不强者智不达，言不信者行不果。墨翟1

17、.假设以数组 Qm存放循环队列中的元素,同时设置一个标志 tag，以 tag=0 和 tag=1 来区别在队头指针（front）和队尾指针（rear）相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入（enqueue）和删除（dlqueue）算法。2.若使用循环链表来表示队列，p 是链表中的一个指针。试基于此结构给出队列的插入（enqueue）和删除（dequeue）算法，并给出 p 为何值时队列空。3.假设以数组 Qm存放循环队列中的元素,同时以 rear 和 length 分别指示循环队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件,并写出相应的插入（enqueue）和删除（dequeue）元素的操作。4.双端队列（deque）是两端都可以插入与删除的顺序表。若将一个双端队列存放于一维数组 Qm中，两个端点设为 end1 和 end2，并让该数组首尾相接。试写出双端队列所用指针 end1 和 end2 的初始化条件及队空与队满条件，并编写基于此结构的相应的插入（enqueue）新元素和删除（dequeue）算法。