数据结构第3章栈与队列习题

1、精选优质文档-倾情为你奉上第 3 章 栈与队列习题一、单选1、有 6 个元素 6、5、4、3、2、1 顺序进栈，（ C ）是非法的出栈序列。A、5 4 3 6 1 2B、4 5 3 1 2 6C、3 4 6 5 1 2D、2 3 4 1 5 62、设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（D ）。A、5 1 2 3 4B、4 5 1 3 2C、4 3 1 2 5D、3 2 1 5 43、进栈序列为 a，b，c，则通过入、出栈可能得到的 a，b，c 的不同排列个数是（ B ）。 A、4B、5C、6D、7 4、栈在（D ）中应用。A、递归调用B、子程序调用C、

2、表达式求值D、以上全对 5、表达式 a*(b+c)-d 的后缀表达式是( B)。A、abcd*+-B、abc+*d-C、abc*+d-D、-+*abcd 6、设计一个判别表达式中左，右括号是否配对出现的算法，采用（ D ）数据结构最佳。 A、线性表的顺序存储结构 B、队列 C、线性表的链式存储结构 D、栈 7、用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点， 则在进行删除操作时(D )。A、仅修改队头指针B、仅修改队尾指针 C、队头、队尾指针都要修改D、队头、队尾指针都可能要修改 8、递归过程或函数调用时，处理参数及返回地址，要用一种称为（ C ）的数据结构。

3、A、队列B、多维数组C、栈D、线性表9、假设以数组 Am存放循环队列的元素,其头尾指针分别为 front 和 rear，则当前队列中 的元素个数为（ A ）。 A、(rear-front+m)%mB、rear-front+1C、(front-rear+m)%mD、(rear-front)%m10、循环队列 A0.m-1存放其元素值，用 front 和 rear 分别表示队头和队尾，则当前队 列中的元素数是( A )。 A、(rear-front+m)%mB、rear-front+1C、rear-front-1D、rear-front 11、循环队列存储在数组 A0.m中，则入队时的操作为（ D

4、 ）。 A、rear = rear+1B、rear = (rear+1) mod (m-1)专心-专注-专业C、rear = (rear+1) mod mD、rear = (rear+1) mod (m+1)12、若用一个大小为 6 的数组来实现循环队列，且当前 rear 和 front 的值分别为 0 和 3， 当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为多少？( A) A、1 和 5B、2 和 4C、4 和 2D、5 和 1 13、栈和队列的共同点是（ C ）。 A、都是先进先出B、都是先进后出 C、只允许在端点处插入和删除元素D、没有共同点14、栈和队都

5、是（ C ）。 A、顺序存储的线性结构B、链式存储的非线性结构C、限制存取点的线性结构D、限制存取点的非线性结构 15、栈的操作原则是（ C）。A、顺序进出B、后进后出C、后进先出D、先进先出 16、下面术语中，与数据的存储结构无关的是（B ）。A、循环队列B、栈C、顺序栈D、顺序表 17、栈和队列具有相同的（ B ）。A、抽象数据类型B、逻辑结构C、存储结构D、运算 18、（B ）不是栈的基本运算。A、删除栈顶元素B、删除栈底元素C、入栈D、栈置空 19、递归算法必须包括（B）。A、递归部分B、终止条件和递归部分C、迭代部分D、终止条件和迭代部分20、表达式 3*2(4+2*2 6*3) 5

6、 在求值过程在，当扫描到 6 时，数字栈中内容为（ B ）。A、3,2,4,1,1B、3,2,8C、3,2,4,2,2D、以上都不对21、设栈 S 和队列 Q 初始状态为空，元素 a1，a2，a3，a4，a5 和 a6 依次通过栈 S，一个元素 出栈后即进入队列 Q，若 6 个元素的出队序列是 a2，a4，a3，a6，a5 和 a1，则栈 S 的容量至 少是（ C ）。A、6B、4C、3D、2二、算法阅读与设计1、简述下面算法的功能（假设栈中元素类型为整数类型）。 假设从键盘上输入一批整数， 依次为：78 63 45 30 91 34 1，写出下面算法的输出结果。struct stackele

7、mtype stackstackmaxsize; int top;void main( )stack a; initstack(a); int x; scanf(x);while(x!= 1)push(a,x);scanf(x); while(!stackempty(a)printf(“%dn”,pop(a);功能：把整数依次输入栈，再输出，实现逆序排列结果：-1,34,91,30,45,63,782、L 为带头结点的单链表，表中元素为整数。利用栈判断 L 是否是对称的。struct stackelemtype stackstackmaxsize; int top;void main( )st

8、ack a; initstack(a); int *P; p=h-next;while(p!= 0)push(a,*p);p=p-next; while(!stackempty(a)if (pop(a) != *p)printf (“No”);break;p=p-next;3、假设将循环队列定义为：以 rear 和 length 分别指示循环队列中队尾元素的位置和内含元 素的个数。给出此循环队列的队满条件，并给出相应的入队和出队算法。typedef char QElemType; typedef struct QElemType elemMAXQSIZE; int length; int rear; Queue; Status EnCQueue(Queue &Q, QElemType x) if(Q.length = MAXQSIZE) return ERROR; if(MAXQSIZE - 1 != Q.rear) +Q.rear; Q.elemQ.rear = x; else Q.rear = 0; Q.elemQ.rear = x; +Q.length; return OK; Status DeCQueue(Queue &Q, QElemType &x) if(!Q.length) retur