《3栈和队列.pdf》由会员分享，可在线阅读，更多相关《3栈和队列.pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章 栈和队列 一 选择题 1.对于栈操作数据的原则是（）。A.先进先出 B.后进先出 C.后进后出 D.不分顺序 2.在作进栈运算时,应先判别栈是否(),在作退栈运算时应先判别栈是否()。当栈中元素为 n 个,作进栈运算时发生上溢,则说明该栈的最大容量为()。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的()分别设在这片内存空间的两端,这样,当()时，才产生上溢。,:A.空 B.满 C.上溢 D.下溢 :A.n-1 B.n C.n+1 D.n/2 :A.长度 B.深度 C.栈顶 D.栈底 :A.两个栈的栈顶同时到达栈空间的中心点.B.其中一个栈的栈
2、顶到达栈空间的中心点.C.两个栈的栈顶在栈空间的某一位置相遇.D.两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.3.若一个栈的输入序列为 1,2,3,n，输出序列的第一个元素是 i，则第 j 个输出元素是（）。A.i-j-1 B.i-j C.j-i+1 D.不确定的 4.某堆栈的输入序列为 a,b，c，d,下面的四个序列中，不可能是它的输出序列的是（）。A.a，c，b，d B.b,c，d，a C.c,d，b,a D.d,c，a，b 5.输入序列为 ABC，可以变为 CBA 时，经过的栈操作为（）A.push,pop,push,pop,push,pop B.push,push,push,pop
3、,pop,pop C.push,push,pop,pop,push,pop D.push,pop,push,push,pop,pop 6.若一个栈以向量 V1.n存储，初始栈顶指针 top 为 n+1，则下面 x 进栈的正确操作是()。Atop=top+1;V top=x B.V top=x;top=top+1 C.top=top-1;V top=x D.V top=x;top=top-1 7.若栈采用顺序存储方式存储，现两栈共享空间 V1.m，topi代表第 i 个栈(i=1,2)栈顶，栈 1 的底在 v1，栈 2 的底在 Vm，则栈满的条件是（）。A.|top2-top1|=0 B.top
4、1+1=top2 C.top1+top2=m D.top1=top2 8.栈在（）中应用。A.递归调用 B.子程序调用 C.表达式求值 D.A，9.一个递归算法必须包括（）。A.递归部分 B.终止条件和递归部分 C.迭代部分 D.终止条件和迭代部分 10.执行完下列语句段后，i 值为：（）int f(int x)return (x0)?x*f(x-1):2);int i ;i=f(f(1);A2 B.4 C.8 D.无限递归 11.表达式 a*(b+c)-d 的后缀表达式是()。Aabcd*+-B.abc+*d-C.abc*+d-D.-+*abcd 12.设计一个判别表达式中左，右括号是否配对
5、出现的算法，采用（）数据结构最佳。A线性表的顺序存储结构 B.队列 C.线性表的链式存储结构 D.栈 13.用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时()。A仅修改队头指针 B.仅修改队尾指针 C.队头、队尾指针都要修改 D.队头,队尾指针都可能要修改 14.递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。A队列 B多维数组 C栈 D.线性表 15.假设以数组 Am存放循环队列的元素,其头尾指针分别为 front 和 rear，则当前队列中的元素个数为（）。A(rear-front+m)%m Brear-front+
6、1 C(front-rear+m)%m D(rear-front)%m 16.若用一个大小为 6 的数组来实现循环队列，且当前 rear 和 front 的值分别为 0和 3，当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为多少？()A.1 和 5 B.2 和 4 C.4 和 2 D.5 和 1 17.已知输入序列为 abcd 经过输出受限的双向队列后能得到的输出序列有（）。A.dacb B.cadb C.dbca D.bdac E.以上答案都不对 分析：A d 第一个出，说明 abc 已经在队中，而 a 在 b 之前出，说明队列中 a和 b 的次序（从出口）ab
7、，c 不管从哪个方向进队都不可能在 ab 之间出队。B c 第一个出队，说明 ab 在队中，而 a 在 b 之前出，说明队列中 a 和 b的次序（从出口）ab，这样我们只要出 a，进 d 出 d，再出 b 即可。C d 第一个出，说明 abc 已经在队中，而 b 在 a 之前出，说明队列中 a和 b 的次序（从出口）ba，c 不管从哪个方向进队都不可能在 ab 之间出队。D b 第一个出，说明 a 已经在队中，再从非出口处进 c，出口处进 d 出 d，出 a 出 c。18.最大容量为 n 的循环队列，队尾指针是 rear，队头是 front，则队空的条件是 （）。A.(rear+1)MOD n
8、=front B.rear=front Crear+1=front D.(rear-l)MOD n=front 19.栈和队列的共同点是（）。A.都是先进先出 B.都是先进后出 C.只允许在端点处插入和删除元素 D.没有共同点 20.栈和队都是（）A顺序存储的线性结构 B.链式存储的非线性结构 C.限制存取点的线性结构 D.限制存取点的非线性结构 21.设栈 S 和队列 Q 的初始状态为空，元素 e1，e2，e3，e4,e5 和 e6 依次通过栈S，一个元素出栈后即进队列 Q，若 6 个元素出队的序列是 e2，e4，e3,e6,e5,e1则栈 S 的容量至少应该是()。A 6 B.4 C.3
9、D.2 三 填空题 1栈是_的线性表，其运算遵循_的原则。访问受限 后进先出 2_是限定仅在表尾进行插入或删除操作的线性表。栈 3.设有一个空栈，栈顶指针为 1000H(十六进制)，现有输入序列为 1，2，3，4，5，经过 PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_，而栈顶指针值是_H。设栈为顺序栈，每个元素占 4 个字节。2、3 100c 4.当两个栈共享一存储区时，栈利用一维数组stack(1,n)表示，两栈顶指针为top1与 top2，则当栈 1 空时，top1为_，栈 2 空时，top2为_，栈满时为_。1 n top2+1=top1 5两个栈共
10、享空间时栈满的条件_。一个栈的栈顶越过另一个栈的栈顶 6在作进栈运算时应先判别栈是否_(1)_;在作退栈运算时应先判别栈是否_(2)_；当栈中元素为 n 个，作进栈运算时发生上溢，则说明该栈的最大容量为_(3)_。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_(4)_分别设在内存空间的两端，这样只有当_(5)_时才产生溢出。满 空 n 栈底 一个栈的栈顶越过另一个栈的栈顶 7.多个栈共存时，最好用_作为存储结构。顺序结构 8表达式 23+(12*3-2)/4+34*5/7)+108/9 的后缀表达式是_。23 12 3*2-4/34 5*7/+108 9
11、/+9.循环队列的引入，目的是为了克服_。假溢出 10.已知链队列的头尾指针分别是 f 和 r，则将值 x 入队的操作序列是_。P=new LNode;p-next=NULL;p-data=x;r-next=p;r=p;11区分循环队列的满与空，只有两种方法，它们是_和_。加标记 少用一个存储单元 12.设循环队列存放在向量 sq.data0:M中，则队头指针 sq.front 在循环意义下的出队操作可表示为_，若用牺牲一个单元的办法来区分队满和队空（设队尾指针 sq.rear）,则队满的条件为_。（Sq.front+1）mod（M+1）(sq.rear-sq.front+M+1)MOD(M+
12、1)13表达式求值是_应用的一个典型例子。栈 四 应用与算法设计题 应用题:1.（1）什么是递归程序？（2）递归程序的优、缺点是什么？（3）递归程序在执行时，应借助于什么来完成？（4）递归程序的入口语句、出口语句一般用什么语句实现？2.当过程 P 递归调用自身时，过程 P 内部定义的局部变量在 P 的 2 次调用期间是否占用同一数据区？为什么？3.试推导出当总盘数为 n 的 Hanoi 塔的移动次数。12 n 4.用栈实现将中缀表达式 8-(3+5)*(5-6/2)转换成后缀表达式，画出栈的变化过程图。5.在一个算法中需要建立多个堆栈时可以选用下列三种方案之一，试问：这三种方案之 间相比较各有
13、什么优缺点？（1）分别用多个顺序存储空间建立多个独立的堆栈；（2）多个堆栈共享一个顺序存储空间；（3）分别建立多个独立的链接堆栈。6.举例说明顺序队的“假溢出”现象，并给出解决方案。算法设计题:1.设有两个栈 S1,S2 都采用顺序栈方式，并且共享一个存储区0.maxsize-1,为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计 S1,S2 有关入栈和出栈的操作算法。typedef struct DoubleQueue ElemType queuemaxsize;int top1,top2;DoubleQueue;Push(s1,e)2.设从键盘输入一整数的序列：a
14、1,a2,a3，an,试编写算法实现：用栈结构存储输入的整数，当 ai-1 时，将 ai 进栈；当 ai=-1 时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。3.设表达式以字符形式已存入数组 En中，#为表达式的结束符，试写出判断表达式中括号（和）是否配对的 C 语言描述算法：EXYX(E);(注：算法中可调用栈操作的基本算法。)4.如果允许在循环队列的两端都可以进行插入和删除操作。要求：（1）写出循环队列的类型定义；（2）写出“从队尾删除”和“从队头插入”的算法。5线性表中元素存放在向量 A（1,n）中，元素是整型数。试写出递归算法求出 A 中的最大和最小元素。int
15、FindMaxMin(int a,int m,int n,int&max,int&min)if(mn)return 0;if(m=n)max=min=am;return 1;FindMaxMin(a,m+1,n,max,min);max=ammax?am:max;min=ammin?am:min;return 1;6.已知求两个正整数 m 与 n 的最大公因子的过程用自然语言可以表述为反复执行如下动作：第一步：若 n 等于零，则返回 m；第二步：若 m 小于 n，则 m与 n 相互交换；否则，保存 m，然后将 n 送 m，将保存的 m 除以 n 的余数送n。（1）将上述过程用递归函数表达出来（设求 x 除以 y 的余数可以用 x MOD y 形式表示）。int GCD(int m,int n)if(n=0)return m;if(mn)int t=m;m=n;n=t;return GCD(n,m%n);（2）写出求解该递归函数的非递归算法。7设计算法以求解从集合1.n中选取 k（k=n）个元素的所有组合。例如，从集合1.4中选取 2 个元素的所有组合的输出结果为：1 2，1 3，1 4，2 3，2 4，3 4。