数据结构第三章考试题库.doc

第3章栈和队列一选择题1.对于栈操作数据的原则是（）。【青岛大学2001五、2（2分）】A。先进先出B.后进先出C。后进后出D。不分顺序2。在作进栈运算时,应先判别栈是否（),在作退栈运算时应先判别栈是否(）。当栈中元素为n个，作进栈运算时发生上溢,则说明该栈的最大容量为（)。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时,应将两栈的(）分别设在这片内存空间的两端,这样，当(）时,才产生上溢。,： A.空B。满C.上溢D.下溢： A. n-1B. nC。 n+1D.n/2： A.长度B.深度C.栈顶D.栈底： A。两个栈的栈顶同时到达栈空间的中心点.B。其中一个栈的栈顶到达栈空间的中心点.C。两个栈的栈顶在栈空间的某一位置相遇.D。两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.【上海海运学院1997二、1（5分)】【上海海运学院1999二、1(5分)】3。一个栈的输入序列为123n,若输出序列的第一个元素是n，输出第i（1=i0) ? x* f（x-1）：2)；int i;i =f（f（1)）；A2B。 4C。 8D.无限递归19。表达式a*（b+c）d的后缀表达式是()。【南京理工大学2001一、2（1.5分）】Aabcd*+-B。 abc+*dC。 abc*+dD. +abcd20。表达式3* 2（4+22-6*3)-5求值过程中当扫描到6时,对象栈和算符栈为()，其中为乘幂 .A. 3，2，4，1,1；(（+B. 3，2,8；（C。 3，2,4,2，2;(*（-D. 3，2，8;（*(-【青岛大学2000五、5(2分）】21。设计一个判别表达式中左，右括号是否配对出现的算法,采用（)数据结构最佳。A线性表的顺序存储结构B.队列C.线性表的链式存储结构D。栈【西安电子科技大学1996一、6（2分）】22。用链接方式存储的队列，在进行删除运算时（）。【北方交通大学2001一、12（2分）】A。仅修改头指针B。仅修改尾指针C。头、尾指针都要修改D.头、尾指针可能都要修改23.用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时()。【北京理工大学2001六、3（2分）】A仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都要修改D.队头,队尾指针都可能要修改24。递归过程或函数调用时,处理参数及返回地址，要用一种称为（)的数据结构。A队列B多维数组C栈D.线性表【福州大学1998一、1（2分)】25.假设以数组Am存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（）.【北京工商大学2001一、2（3分）】A(rearfront+m)mBrear-front+1C(front-rear+m)mD（rearfront)m26.循环队列A0.m1存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是()。【南京理工大学2001一、5(1.5分）】A。 （rearfront+m)%mB。 rearfront+1C。rear-front-1D。rear-front27.循环队列存储在数组A0。.m中，则入队时的操作为()。【中山大学1999一、6（1分）】A。 rear=rear+1B。 rear=(rear+1) mod (m-1)C. rear=（rear+1) mod mD。 rear=(rear+1)mod（m+1）28。若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少?()【浙江大学1999四、1(4分）】A。1和5B.2和4C。4和2D。5和129。已知输入序列为abcd经过输出受限的双向队列后能得到的输出序列有（）。A. dacbB. cadbC. dbcaD。 bdacE。以上答案都不对【西安交通大学1996三、3 (3分)】30.若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是().【西安电子科技大学1996一、5（2分)】A. 1234B. 4132C. 4231D。 421331。最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）.A. （rear+1) MOD n=frontB. rear=frontCrear+1=frontD。 （rear-l) MOD n=front【南京理工大学1999一、16(2分）】32。栈和队列的共同点是（）。【燕山大学2001一、1（2分)】A。都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D。没有共同点33.栈的特点是（），队列的特点是（），栈和队列都是(）。若进栈序列为1，2，3，4则（）不可能是一个出栈序列（不一定全部进栈后再出栈）;若进队列的序列为1，2,3，4则（）是一个出队列序列。【北方交通大学1999一、1（5分）】，: A。先进先出B.后进先出C。进优于出D。出优于进: A.顺序存储的线性结构B。链式存储的线性结构C.限制存取点的线性结构D。限制存取点的非线性结构，: A. 3,2，1,4B. 3，2,4，1C。 4，2,3，1D。 4，3,2,1F。 1,2,3,4G。 1,3,2,434。栈和队都是（）【南京理工大学1997一、3（2分）】A顺序存储的线性结构B。链式存储的非线性结构C。限制存取点的线性结构D。限制存取点的非线性结构35。设栈S和队列Q的初始状态为空，元素e1，e2，e3,e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5，e1则栈S的容量至少应该是(）。A6B。 4C. 3D。 2【南京理工大学2000一、6（1.5分）】36.用单链表表示的链式队列的队头在链表的（)位置。【清华大学1998一、1（2分）】A链头B链尾C链中37.依次读入数据元素序列a,b，c，d,e，f,g进栈，每进一个元素,机器可要求下一个元素进栈或弹栈，如此进行,则栈空时弹出的元素构成的序列是以下哪些序列？ 【哈尔滨工业大学2000七（8分）】Ad，e，c，f，b，g，aB。 f,e,g，d,a，c，bC. e，f，d，g，b，c,aD。 c，d，b,e，f,a，g二判断题1。消除递归不一定需要使用栈，此说法()【中科院计算所1998二、2(2分）】【中国科技大学1998二、2（2分）】2.栈是实现过程和函数等子程序所必需的结构。（)【合肥工业大学2000二、2(1分）】3.两个栈共用静态存储空间，对头使用也存在空间溢出问题。(）【青岛大学2000四、2（1分）】4两个栈共享一片连续内存空间时,为提高内存利用率,减少溢出机会,应把两个栈的栈底分别设在这片内存空间的两端。（)【上海海运学院1998一、4(1分）】5。即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。（）【北京邮电大学1999二、4（2分）】6。有n个数顺序(依次）进栈,出栈序列有Cn种，Cn=1/（n+1）（2n）！/(n!)*(n!)。（）【北京邮电大学1998一、3（2分）】7。栈与队列是一种特殊操作的线性表。（）【青岛大学2001四、3（1分）】8.若输入序列为1，2，3,4，5，6，则通过一个栈可以输出序列3，2，5,6,4,1。（)【上海海运学院1995一、2(1分）1997一、3（1分)】9.栈和队列都是限制存取点的线性结构。（）【中科院软件所1999六、(5）（2分）】10若输入序列为1，2，3,4，5，6，则通过一个栈可以输出序列1，5,4，6，2，3。（)【上海海运学院1999一、3（1分)】11.任何一个递归过程都可以转换成非递归过程。()【上海交通大学1998一、3（1分）】12.只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。(）【上海交通大学1998一、4（1分)】13。队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。(）【上海海运学院1998一、3(1分）】14。通常使用队列来处理函数或过程的调用.（）【南京航空航天大学1997一、5(1分）】15。队列逻辑上是一个下端和上端既能增加又能减少的线性表。(）【上海交通大学1998一、2】16。循环队列通常用指针来实现队列的头尾相接。（）【南京航空航天大学1996六、1（1分）】17。循环队列也存在空间溢出问题。(）【青岛大学2002一、2（1分)】18.队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（ ）【长沙铁道学院1997一、5（1分）】19.栈和队列都是线性表，只是在插入和删除时受到了一些限制.（）【北京邮电大学2002一、3(1分)】20.栈和队列的存储方式,既可以是顺序方式，又可以是链式方式。（）【上海海运学院1996一、2（1分）1999一、2（1分)】三填空题1栈是_的线性表，其运算遵循_的原则.【北京科技大学1997一、3】2_是限定仅在表尾进行插入或删除操作的线性表。【燕山大学1998一、3(1分）】3。一个栈的输入序列是：1，2，3则不可能的栈输出序列是_.【中国人民大学2001一、1（2分)】4.设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH，POP,PUSH,POP，PUSH，PUSH之后，输出序列是_，而栈顶指针值是_H.设栈为顺序栈，每个元素占4个字节。【西安电子科技大学1998二、1（4分）】5。当两个栈共享一存储区时，栈利用一维数组stack(1，n）表示，两栈顶指针为top1与top2，则当栈1空时,top1为_，栈2空时 ,top2为_,栈满时为_。【南京理工大学1997三、1(3分）】6两个栈共享空间时栈满的条件_。【中山大学1998一、3(1分）】7在作进栈运算时应先判别栈是否_（1)_；在作退栈运算时应先判别栈是否_(2)_；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_(3)_。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的空间时，应将两栈的_(4）_分别设在内存空间的两端，这样只有当_（5）_时才产生溢出。【山东工业大学1994一、1（5分）】8。多个栈共存时，最好用_作为存储结构。【南京理工大学2001二、7（2分）】9用S表示入栈操作，X表示出栈操作,若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_.【西南交通大学2000一、5】10。顺序栈用data1。n存储数据，栈顶指针是top，则值为x的元素入栈的操作是_.【合肥工业大学2001三、2(2分）】11表达式23+（123-2)/4+34*5/7)+108/9的后缀表达式是_.【中山大学1998一、4（1分）】12。循环队列的引入,目的是为了克服_。【厦门大学2001一、1（14/8分)】13用下标0开始的N元数组实现循环队列时，为实现下标变量M加1后在数组有效下标范围内循环，可采用的表达式是：M：=_（填PASCAL语言，C语言的考生不填)；M= _（填C语言，PASCAL语言的考生不填）。【西南交通大学2000一、7】14_又称作先进先出表。【重庆大学2000一、7】15。队列的特点是_。【北京理工大学2000二、2（2分)】16队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表,其特点是_。【北方交通大学2001二、5】17。已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_.【合肥工业大学2000三、3（2分)】18区分循环队列的满与空,只有两种方法，它们是_和_.【北京邮电大学2001二、2（4分）】19设循环队列用数组A1.M表示，队首、队尾指针分别是FRONT和TAIL，判定队满的条件为_。【山东工业大学1995一、1（1分）】20。设循环队列存放在向量sq.data0：M中，则队头指针sq.front在循环意义下的出队操作可表示为_,若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq。rear），则队满的条件为_。【长沙铁道学院1997二、4 （4分）】21表达式求值是_应用的一个典型例子.【重庆大学2000一、10】22循环队列用数组A0。m1存放其元素值，已知其头尾指针分别是front和rear,则当前队列的元素个数是_。【厦门大学2000六、1（16/3分)】23设Q0.N1为循环队列,其头、尾指针分别为P和R，则队Q中当前所含元素个数为_。【北京科技大学1997一、4】24完善下面算法。【中山大学1998四、2（6分）】后缀表达式求值，表达式13/25+61的后缀表达式格式为：13, 25/61， +FUNCcompute(a）：real;后缀表达式存储在数组a1.m中。BEGINsetnull（s）；i：=1;ch:=(1）_；WHILE ch DOBEGINCASE ch OF0。9：x：=0；WHILE ch,DOBEGINx：=x*10+ord(ch)ord(0）；i：=i+1；ch:=（2）_；END+： x：=pop(s）+pop（s）；-： x:=pop(s)；x：=pop(s)x;: x:=pop(s)*pop（s);/： x：=pop（s);x:=pop（s)/x；ENDCASEpush（s，x)；i:=i+1；ch:=ai；END;comput：=(3)_；END;25。算术表达式求值的流程，其中OPTR为算术符栈，OPND为操作数栈，precede(oper1，oper2)是比较运算符优先级别的函数,operate（opnd1,oper,opnd2）为两操作数的运算结果函数。（表示运算起始和终止符号）【西北工业大学1999六、2 （7分)】FUNCTIONexp_reduced:operandtype;INITSTACK(OPTR）;PUSH（OPTR#)；INITSTACK（OPND)；read(w）;WHILENOT（w=#） AND (GETTOP(OPTR)=）) DOIF NOT w in op THEN PUSH(OPND，w）；ELSE CASE precede（GETTOP（OPTR），w)OF：(1)_； read(w）;=:(2）_； read(w);；:theta:=POP(OPTR）；b：=POP(OPND）;a:=POP(OPND）;（3）_；ENDC;RETURN(GETTOP(OPND）；ENDF;26根据需要,用适当的语句填入下面算法的_中:问题:设有n件物品，重量分别为w1，w2,w3,wn和一个能装载总重量为T的背包。能否从n件物品中选择若干件恰好使它们的重量之和等于T。若能,则背包问题有解，否则无解。解此问题的算法如下:FUNCTION kanp_stack(VAR stack，w:ARRAY1。.n OF real; VAR top:integer； T：real)：boolean;w1：n存放n件物品的重量,依次从中取出物品放入背包中，检查背包重量，若不超过T，则装入,否则弃之，取下一个物品试之。若有解则返回函数值true，否则返回falseBEGINtop：=0;i:=1; i指示待选物品WHILE（1)_ AND(2）_DOIF(3)_ OR（4)_ AND （in)THENtop :=(5)_ ；stacktop :=i;第i件物品装入背包T:=T-wi；IF T=0 THEN RETURN (（6)_)背包问题有解ELSEIF(i=n )AND（top0)THENi：=（7）_;取出栈顶物品top：=（8）_；T:=（9）_ ;恢复T值i：=i+1准备挑选下一件物品;；RETURN(10）_） 背包无解END;【北京邮电大学1996四（10分）】四应用题1.名词解释:栈.【燕山大学1999一、1（2分）】【吉林工业大学1999一、3（2分）】2.名词解释:队列【大连海事大学1996一、6 （ 1分)】3。什么是循环队列？【哈尔滨工业大学2001三、2（3分)】【河南大学1998一、4(3分）】4。假设以S和X分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S和X组成的序列表示（如SXSX）。（1）试指出判别给定序列是否合法的一般规则。（2）两个不同合法序列(对同一输入序列）能否得到相同的输出元素序列？如能得到,请举列说明。【东南大学1992二 （10分）】5.有5个元素,其入栈次序为：A，B,C，D，E,在各种可能的出栈次序中,以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个?【西南交通大学2000二、1】6.如果输入序列为1 2 3 4 5 6,试问能否通过栈结构得到以下两个序列：4 3 5 6 1 2和1 3 5 4 2 6；请说明为什么不能或如何才能得到。【武汉交通科技大学1996二、3 （3分)】7。若元素的进栈序列为：A、B、C、D、E，运用栈操作，能否得到出栈序列B、C、A、E、D和D、B、A、C、E?为什么？【北京科技大学1998一、2】8。设输入序列为a，b,c,d,试写出借助一个栈可得到的两个输出序列和两个不能得到的输出序列。【北京科技大学2001一、4（2分）】9。设输入序列为2，3,4，5，6，利用一个栈能得到序列2，5，3,4，6吗?栈可以用单链表实现吗？【山东师范大学1996五、4(2分）】10。试证明：若借助栈由输入序列1，2，n得到输出序列为P1,P2，Pn(它是输入序列的一个排列），则在输出序列中不可能出现这样的情形:存在着ijk,使PjPkPi。【上海交通大学1998二（15分）】11.设一数列的输入顺序为123456,若采用堆栈结构,并以A和D分别表示入栈和出栈操作，试问通过入出栈操作的合法序列.（1） 能否得到输出顺序为325641的序列.（5分)（2） 能否得到输出顺序为154623的序列。（5分） 【北方交通大学1995一（10分)】12。（1） 什么是递归程序？（2） 递归程序的优、缺点是什么？（3） 递归程序在执行时，应借助于什么来完成?（4） 递归程序的入口语句、出口语句一般用什么语句实现？【大连海事大学1996二、4（4分）】13。设有下列递归算法：FUNCTIONvol（n：integer）：integer；VARx :integer:BEGIN IF n=0 THENvol：=0ELSEBEGIN read(x)；vol:=vol(n1）+x；END；END；如该函数被调用时，参数n值为4,读入的x值依次为5，3，4，2,函数调用结束时返回值vol为多少?用图示描述函数执行过程中，递归工作栈的变化过程.【北京工业大学1998四（10分)】14.当过程P递归调用自身时，过程P内部定义的局部变量在P的2次调用期间是否占用同一数据区？为什么?【山东师范大学1999一、4（4分）】15。试推导出当总盘数为n的Hanoi塔的移动次数. 【北京邮电大学2001四、3（5分）】16。对下面过程写出调用P（3）的运行结果。PROCEDURE p（w:integer）;BEGINIF w0 THENBEGINp(w1);writeln（w)；输出Wp（w1）END;END；【西北大学2001三、7】17。用一个数组S（设大小为MAX）作为两个堆栈的共享空间。请说明共享方法，栈满/栈空的判断条件，并用C或PASCAL设计公用的入栈操作push（i,x），其中i为0或1，用于表示栈号，x为入栈值。【浙江大学1998五、2 (7分)】18。简述下列程序段的功能.PROCalgo(VAR S ： stack;k:integer)；VART: stack; temp： integer；WHILE NOTempty(S） DOtemp：=POP（S); IF tempkTHEN PUSH(T，temp）；WHILE NOTempty（T）DOtemp:=POP（T）；PUSH（S,temp)；【山东科技大学2002一、1（4分)】19.用栈实现将中缀表达式8-（3+5)*（56/2)转换成后缀表达式，画出栈的变化过程图。【南京航空航天大学2001五 (10分）】20。在表达式中,有的运算符要求从右到左计算，如A*B*C的计算次序应为(A*(B*C）)，这在由中缀生成后缀的算法中是怎样实现的?(以*为例说明）【东南大学1993一、2（6分）1997一、1（8分)】21.有递归算法如下：FUNCTIONsum （n：integer):intger；BEGINIF n=0 THEN sum:=0ELSE BEGIN read（x)；sum:=sum（n1）+x END；END；设初值n=4，读入x=4,9,6,2问：(1）若x为局部变量时；该函数递归结束后返回调用程序的sum=？并画出在递归过程中栈状态的变化过程；(2)若x为全程变量递归结束时返回调用程序的sum=？【北京邮电大学1997一 （10分）】22。画出对算术表达式A-B*C/DEF求值时操作数栈和运算符栈的变化过程.【东南大学2000一、3（6分）】23.计算算术表达式的值时，可用两个栈作辅助工具.对于给出的一个表达式，从左向右扫描它的字符，并将操作数放入栈S1中,运算符放入栈S2中，但每次扫描到运算符时，要把它同S2的栈顶运算符进行优先级比较，当扫描到的运算符的优先级不高于栈顶运算符的优先级时，取出栈S1的栈顶和次栈顶的两个元素，以及栈S2的栈顶运算符进行运算将结果放入栈S1中（得到的结果依次用T1、T2等表示）。为方便比较，假设栈S2的初始栈顶为(运算符的优先级低于加、减、乘、除中任何一种运算）。现假设要计算表达式:A-BC/D+E/F。写出栈S1和S2的变化过程。 【山东科技大学2001一、4(7分)】24。有字符串次序为3y-a/y2,利用栈，给出将次序改为3yay2/的操作步骤。(可用X代表扫描该字符串过程中顺序取一个字符进栈的操作，用S代表从栈中取出一个字符加入到新字符串尾的出栈操作.例如，ABC变为BCA的操作步骤为XXSXSS） 【东北大学2001一、4 ( 4分）】25.内存中一片连续空间（不妨假设地址从1到m）提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。【东北大学2000一、1 (3分）】26。将两个栈存入数组V1。.m应如何安排最好？这时栈空、栈满的条件是什么？【东南大学1998一、5】27.在一个算法中需要建立多个堆栈时可以选用下列三种方案之一，试问：这三种方案之间相比较各有什么优缺点？（1）分别用多个顺序存储空间建立多个独立的堆栈;（2）多个堆栈共享一个顺序存储空间;（3）分别建立多个独立的链接堆栈。【北京航空航天大学1998一、6（4分）】28在某程序中,有两个栈共享一个一维数组空间SPACEN、SPACE0、SPACEN1分别是两个栈的栈底。（1)对栈1、栈2，试分别写出（元素x）入栈的主要语句和出栈的主要语句.（2）对栈1、栈2，试分别写出栈满、栈空的条件。【北京理工大学1999二、2（8分）】29。简述顺序存储队列的假溢出的避免方法及队列满和空的条件.【山东大学2000一、2 （4分)】30。举例说明顺序队的“假溢出”现象,并给出解决方案.【福州大学1998三、5 (6分)】31.怎样判定循