《《数据结构》习题集：第3章栈和队列》由会员分享，可在线阅读，更多相关《《数据结构》习题集：第3章栈和队列（15页珍藏版）》请在金锄头文库上搜索。
1、1/15第第 3 章章 栈和队列栈和队列一、一、选择题选择题1.栈结构通常采用的两种存储结构是（A ）。 A、顺序存储结构和链表存储结构 B、散列和索引方式 C、链表存储结构和数组 D、线性链表结构和非线性存储结构 2.设栈ST 用顺序存储结构表示，则栈ST 为空的条件是（ B ） A、ST.top-ST.basen D、ST.top-ST.base=n 3.向一个栈顶指针为HS 的链栈中插入一个s 结点时，则执行（ C ） A、HS-next=s; B、s-next=HS-next；HS-next=s; C、s-next=HS；HS=s; D、s-next=HS；HS=HS-next; 4.
2、从一个栈顶指针为HS 的链栈中删除一个结点，用x 保存被删除结点的值，则执行（ C） A 、x=HS；HS=HS-next; B 、HS=HS-next；x=HS-data; C 、x=HS-data；HS=HS-next; D 、s-next=Hs；Hs=HS-next; 5.表达式a*(b+c)-d 的后缀表达式为（ B ） A、abcdd+- B、abc+*d- C、abc*+d- D、-+*abcd 6.中缀表达式A-（B+C/D）*E 的后缀形式是（ D ） A、AB-C+D/E* B、ABC+D/E* C、ABCD/E*+- D、ABCD/+E*- 7.一个队列的入列序列是1，2，
3、3，4， 则队列的输出序列是（ B ） A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 8.循环队列SQ 采用数组空间SQ.base0,n-1存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队 列为空的条件是（ ） A、Q.rear-Q.front=n B、Q.rear-Q.front-1=n C、Q.front=Q.rear D、Q.front=Q.rear+1 9.循环队列SQ 采用数组空间SQ.base0,n-1存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队 列为满的条件是（ ） A、Q.front=Q.re
4、ar B、Q.front!=Q.rear C、Q.front=(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 10. 若在一个大小为6 的数组上实现循环队列，且当前rear 和front 的值分别为0 和3，当从队列中删除一个元素， 再加入两个元素后，rear 和front 的值分别为（ ） A、1，5 B、2, 4 C、4，2 D、5，1 11. 用单链表表示的链式队列的队头在链表的（ ）位置 A、链头 B、链尾 C、链中 12. 判定一个链队列Q（最多元素为n 个）为空的条件是（ ） A、Q.front=Q.rear B、Q.front!=Q.rear C、Q.f
5、ront=(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 13. 在链队列Q 中，插入s 所指结点需顺序执行的指令是（ ） A 、Q.front-next=s；f=s; B 、Q.rear-next=s；Q.rear=s; C 、s-next=Q.rear；Q.rear=s; D 、s-next=Q.front；Q.front=s; 14. 在一个链队列Q 中，删除一个结点需要执行的指令是（ ） A、Q.rear=Q.front-next; B、Q.rear-next=Q.rear-next-next; C、Q.front-next=Q.front-next-next
6、; D、Q.front=Q.rear-next;2/1515. 用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时 （ ） A、仅修改队头指针 B、仅修改队尾指针 C、队头尾指针都要修改 D、队头尾指针都可能要修改。 16. 栈和队列的共同点是（ ） A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点 17. 消除递归（ ）需要使用栈。 A、一定 B、不一定 18. 设有一顺序栈S，元素s1，s2，s3，s4，s5，s6 依次进栈，如果6 个元素出栈的顺序是 s2，s3，s4，s6，s5，s1，则栈的容量至少应该是（
7、 ） A、2 B、3 C、 5 D、 6 19. 若一个栈的输入序列是a，b，c，则通过入、出栈操作可能得到a,b,c 的不同排列个数为（ ） A、 4 B、 5 C、 6 D、 7 20. 设有一顺序栈已经含有3 个元素，如图3.1 所示元素a4 正等待进栈。下列不可能出现的出栈序列是（ ） A、a3,a1,a4,a2 B、 a3,a2,a4,a1 C、 a3,a4,a2,a1 D、 a4,a3,a2,a1图3.121. 链栈和顺序栈相比，有一个比较明显的优势是（ ） A、通常不会出现栈满的情况 B、通常不会出现栈空的情况 C、插入操作更容易实现 D、删除操作更加容易实现 22. 若一个栈的
8、输入序列是1，2，3，4，n，输出序列的第一个元素是n，则第i 个输出元素是（ C ） A、不确定 B、 n-i C、 n-i+1 D、n-i-1 23. 以下说法正确的是( ) A、因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 B、因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 C、对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢” D、对于顺序栈而言在栈满状态下如果此时再作进栈运算，则会发生“下溢”。二、二、判断题判断题1.在顺序栈栈满情况下，不能做进栈运算，否则会产生“上溢”。 2.链栈与顺序栈相比的一个优点是链栈插入和删除操作更加
9、方便。 3.若一个栈的输入序列为 1，2，3，n，其输出序列的第一个元素为 n，则其输出序列的每个元素一定满足ai=i+1(i=1,2, ,n)。 4.在链队列中，即使不设置尾指针也能进行入队操作。 5.在对链队列（带头指针）做出队操作时，不会改变 front 指针的值。 6.循环队列中元素个数为 rear-front。 7.一个栈的输入序列是 1,2,3,4，则在栈的输出序列中可以得到 4,3,1,2。 8.一个栈的输入序列是 1,2,3,4，则在栈的输出序列中可以得到 1,2,3,4。 9.若以链表作为栈的存储结构，则进栈需要判断栈是否满。3/1510. 若以链表作为栈的存储结构，则出栈需
10、要判断栈是否空。三、三、填空题填空题1.栈的特点是（先进后出 ），队列的特点是（ 先进先出 ）。 2.线性表、栈、队列都是（ ）结构，可以在线性表的（ ）位置插入和删除元素；对于栈只能在（ ）插 入和删除元素；对于队列只能在（ ）插入元素和在（ ）位置删除元素。 3.有程序如下，则此程序的输出结果（栈的元素类型是 SelemType 为 char）是（ ）。 void main() stack s; char x,y; initstack (s); x=c; y=k; push(s,x); push(s,a); push(s,y); pop(s,x); push(s,t); push(s,x)
11、; pop(s,x); push(s,s); while(!stackempty(s) pop(s,y); printf(y); printf(x); 4.在栈顶指针为 HS 的链栈中，判定栈空的条件是（ ）。 5.向栈中压入元素的操作是先（ ）后（ ）。 6.对栈进行退栈操作是先（ ）后（ ）。 7.用循环链表表示的队列长度为 n，若只设头指针，则出队和入队的时间复杂度分别是（ ）和（ ）；若只 设尾指针，则出队和入队的时间复杂度分别是（ ）和（ ）。 8.从循环队列中删除一个元素时，其操作是（ ）。 9.在一个循环队列中，队首指针指向队首元素的（ ）。 10. 在具有 n 个单元的循环队列
12、中，队满时共有（ ）个元素。 11. 在 HQ 的链队列中，判断只有一个结点的条件是（ ）。 12. 设栈 S 和队列 Q 的初始状态为空，元素 a、b、c、d、e、f 依次通过栈 S，一个元素出栈后即进入队列 Q。若 这 6 个元素出队列的顺序是 b、d、c、f、e、a 则栈 S 的容量至少应该是（ ）。 13. 有程序如下，则此程序的输出结果（队列的元素类型是 QSelemType 为 char）是（ ）。 void main() char x=e,y=c; enqueue(q,h);enqueue(q,r);enqueue(q,y);dequeue(q,x);enqueue(q,x);d
13、egueue(q,x); enqueue(q,a); while(!queueempty(q) dequeue(q,y);printf(y);4/15 printf(x); 14. 有如下递归函数： int dunno(int m) int value; if(m=0) value=3; else value=dunno(m-1)+5; return(value); 执行语句 printf(“%dn”,dunno(3);的结果是（ ）。四、四、简答题简答题1.对于堆栈，给出三个输入项 A，B，C，如果输入项序列为 ABC，试给出全部可能的输出序列，并写 出每种序列对应的操作。例如：A 进 B
14、进 C 进 C 出 B 出 A 出，产生的序列为 CBA。 2.简述以下算法的功能（栈的元素类型是 SelemType 为 int）。 （1） status algo1(stack s) int I,n,a255; n=0; while(!stackempty(s) n+; pop(s,an); for(I=1;I=0 i+; /不论 Ai是I或O ，指针 i 均后移。ifif(j!=k) printf(“序列非法n”)；returnreturn(false);elseelse printf(“序列合法n”)；returnreturn(true);/算法结束。算法讨论在入栈出栈序列（即由I和O
15、组成的字符串）的任一位置，入栈次数（I的个数）都 必须大于等于出栈次数（即O的个数） ，否则视作非法序列，立即给出信息，退出算法。整个序列（即读到字 符数组中字符串的结束标记0 ） ，入栈次数必须等于出栈次数（题目中要求栈的初态和终态都为空） ，否则视 为非法序列。(6）假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空 、入队和出队等算法。 算法如下：/先定义链队结构:typedef struct queuenodeDatatype data;struct queuenode *next;QueueNode; /以上是结点类型的定义10/15typedef structqueuenode *rear;LinkQueue; /只设一个指向队尾元素的指针(1)置空队void InitQueue( LinkQueue *Q) /置空队：就是使头结点成为队尾元素QueueNode *s;Q-rear = Q-rear-next;/将队尾指针指向头结点while (Q-rear!=Q-rear-next)/当队列非空，将队中元素逐个出队s=Q-rear-next;Q-rear-next=s-next;free(s);/回收结点空
