数据结构第3章栈和队列自测题答案

二i.向・、««队列gaatt廉，可以在向■的曲位・《a和■除元素；对莉只能在 插入和;对于队列只teaBUIMA和队曹■Kt7uK.桟是一种特蛛的线性衰，允许插入和■除运算的TH9为业叫_.不允许插入和■除B*»-W3%_SS_.限定为只能在表的Tffi行插入运鼻，在表的另一岫州I除运鼻的线性 表.在f砌队列中，队首齡懾向队首元素的卫二》—位■.在具有n个单元的《駢队列中，队满时共有上以元1L雌中压入元素的操作是先存入同,后移aroas针.从aw队列中■除fai时，具操作JI先移动队W8tt,后取出元素.点的解：,I> ‘JI而土群（1「头结|R=head| 」二判断正误（判断下列II念的正備性，并作出唳的说明.）三（x 结g能*-MB单#S!,而嗣错,线性表是逻辑结构概念，可以Ji序存储或链式存储,与元素數据类型无关.（X）2.在褰结构中■常用的是线性裏,株和队列不太常用.fll,不一定吧？调用子宣序或函散常用，CPU中也用队列。

(v )3.栈是一种对所有插入、HMM作限于在哀的一行的线性获，是一种后进先出型结构.(v)4.对于不同的使用者，一个表结构既可以是杨，也可以是队列，也可以是线牲表.正确，都是线牲球结构，株和队列其实是特殊的线牲表，对运算的定义略有不同而已•(x)5.株和链表是两种不同的数据结构.错，栈gi结构的幡念，是特殊殊线性表，而链表是存储结枷念，二者不是同类项。(x)6.期队列崩错，他们都是线性逻辑结构，栈和队列其实g*的线性表，对运鼻的定义IHJ不同而巳。(V )7.栈和队列的存ft方式既可M序方式,也可験接方式.(V )8.两个栈共専一片连续内存空间时,为提高内存利用率，减少溢出机会，成把两个株的株底分别设在这片内砂间的两虬(x)9.队是一种插入与■啣作分别在哀的两岫行的线性S,是一种先进后出型结构。错，后半句不对.(x)10.f株的输入序列是12345,则栈的输出序列不可能是12345.错，有可能。三、单项选择题(毎小题1分，共20分)(B)1.棧中元素的诳出應曜A.A.先进先岀 B.后诳先出 C.棧空则诳D.栈满则出(c)2.若已知f桟的入桟序列是1,2,3，…，n,其输出序列为pl,p2,p3，…，pn,若pl=n,MpiftA.iB.n=iC.n-i+1D.不确解釋：当pl=n,即nJM先出栈的，根据桟的原理,n必定是■后入栈的(«%上题目巳经那么辎入岫｛淀是1,2,3，…，n,则出栈的序列是n，…，3,2,1.(若不要求顺序出橫，则输出序列不确定)(B)3.對定一个栈ST(■多元素为mO)为空的条件是A.ST->top<>0B.ST->top=0C・ST->topomOD.ST->top=mO(A)4,判定列QU(最多元素为mO)为満队列的条件JKA・QU->rear-QU->front==mOB.QU->rear-QU->front-1==mOC•QU->front==QU->rear D・QU->front==QU->rear+l解：队満条件］■元素个数为mO.由于约定満队时队首指针与队甩指针相差1,所以不必再械1了选A.当然，KE确隣砲，即:QU->front==(QU->rear+l)%mO(D)5.ttfflQ［n］用 队列，f为当削队列 ,r为队Ji元素的位■，假定队列中元素的个數小于n,计鼻队列中元素的公式为(A)r-f;(B)(n+f-r)%n;(C)n+r-fi(D)(n+r-f)%n6.

a2、a3和a4,对他们朝齣成•作.Si&ffisKm.酬时，按al酬时，按al、a2、a3.a4 假瞳队啣始现要进行的栈操作两次，出株一次，再瞄两次，出株一次；这时，第一次出栈得到的Tawa,Mzaaaas»7aKaba；类旳,夸痫这四1««^«遊行的队操作是进队两次,出队一次，再诳队两次,出队一次；这时,第一次出队御到的元素»c,第二《出队得到的同是d・经操作后，最后在株中或队中的无素还有E个.A~D:®al®a2 ③a3©a4E：®1 ®2 @3 ®0答:ABCDE=2f 4,1,2,2从供选择的答案中，选岀成91入下面叙述 ？ 内的H切的解答，把相应鑼号写在答卷的对成栏内.栈是T*栈是T*线性表，它的特点J_.1A[L...,n]来裏示f栈，A[n]为isettJS,用«SBE・T指示当IN栈顶位■,AE排諏元素。住桟中推入（PUSH）fWSSise素时，变从梯中强出（POP）fMW,变・T的«L£_・ WHAHWa,b,c,经HPUSH,POP,PUSH,PUSH,POP"后,从栈中弹出标素的序列是D,3UT的（ME.答案：A:③先进先出②后进先出④出优铀⑤B,C:①加1®»o⑤加2®W2D:®a,b®bfc®c,a④b,a ⑤cfb⑥a(cE:®n+1 ®n+2③n④n-1 ⑤n-2答案：ABCDE=2,2,1,6,4注意,向地址的高繩生长，称为向上生成堆栈；向地址低it生长叫向下生成堆栈，本题中底部为n,旳地址的低嶼诚生成，称为向下生成堆株.8.从供痫的答案中，选出成塩入下闡叙述?内的■熾切的解答，把相皿■号写在答««对雎内.在时，转判别CM否A ；在旳»3»时，别敝否B当栈中元素为n个，例进棧运算时发生上温，則说明该棧的阳濬岫C为了増加内存蝕的利用軻I减少谥岀的可能性，由两个梯共専一片连续的内存空何时，瞄两栈的D分别设在这片内存空间的两■，这样，只有当E时，才产生上3L爵：③上溢C:®n-l®SK③臉®OS®SK③臉®OSe：①两个snajie：①两个snaji同时的中心点栈空间的中心点③两个的集④两个aw不空且f栈诵一答案：ABCDE=2,1,2,4f3四.筒答题（毎小题4分，共20分）说明线牲表、栈与队的鼻同点.答:相同点：都是线性结构，都是圜1结构的«（念.都可以用顺序存储或链表存储；株和队列是两种特殊的线性哀，即受限的线性哀，只是对插入.■除运剛a以限制.

不同点：不同，线性寰为ia机存取，而榭1只允许在插人■除运算，因而是后进先出«UFO;队列是只允许在TK^B入、另Tl^jOI除运H,因而是先进先出表FIFO.®用途不同,堆栈用于子程厦用和保护现场，队列用于多道作业处珥掲令将存及其他运算99.设■■号为1,2,3,4的四辆列车，诳入f聞结构的车站，具体写出这四辆列车开出车站的所有可能的《«・答：至少有14种.®全进之后再出®全进之后再出111况，只有1种：4,3,2,1遊3个之后再出的情况，有3种，3,4,2,1遊2个之后再出的慵况，有5种，2,4,3丄遊1个之后再出的It况，有5种，1,4,3,2324,13,2,1,423A12,1,3,42,1,432,3,1,41,3,2,41.3A2L2,3,41,2,433.假设正读和反读都相同龄符序列労'回文”例如，’abba'和'abcba'是回文，’abcde'和'ababab'则不H回文.假设一字符序列巳存入计鼻机，it分析用线性表、瞄和队列等方式正琳输出其回文的可能性？答:线性表是随《存箱,可以实现，1KS环变■(j-)从表尾开始打印.出；雄栈是后进先岀，也可以实现，IKEWAS.逆序岀栈两；队列是先进先出，不易实现.0R4■方式•好，要具体備况具体分析.若正文在机内已是1■序存储，別用线性裝从后往前溯8即可，或捋堆栈検顶开到瞄末用,然后車接用POP动作实風(但堆栈是先减后..•・..)若正文JK单链哀形式存储，则等同于队列，lit开辅助空间，可以从链■开始入栈，全部压入后再依次輸岀.队的“假溢出”是怎样产生的？如何知i«aw队列jk还是満？答：一»的一sas组队列的是掲针已也了瞄的上界，不能再有入队操作，但其®敬爼中还有空位■,这就叫"假溢出采用編环队列出的曜另外，解决队満队空的办法有三:®设・f布尔变■以区别队满还是队空；浪费1版»的空间，用于区别队满图■队空.使用f+«器记录队列中元察个数(即队列长an翔们常采用法②，即队头指针、队n擂针中有—mb向实元素，而另—M8向空闲元素。判断循环队列建：f=rear ：f=(r+l)%N设«|环队列的容■为40(序号从。到39),现经过一系列的入队和出队运鼻后，有®front=ll,rear=19;②front=19,rear=ll; ,il环队列中各有?》^少？答：用队列长度计鼻公式：(N+r-f)%N®L=(40+19-ll)%40=8 ②L=(40+11-19)%40=32瓦阅读理解(毎小H5分，共20分.至少要写出思踣)1.写岀下列程序段跳出结果(栈的元素类型SEIemType*char'voidmain(){StackS;Charx,y;InitStack(S);X='c'妙；Push(S,x);Push(S/a');Push(S,y);Pop(S,x);Push(S/t);Push(S,x);Pop(S,x);Push(S/s');while(!StackEmpty(S))(Pop(S,y);printf(y);}；Printf(x);}答：输出为"stack”.2.®］导岀下列程序股的输岀结果(队列中的元素类型QEIemType为char\voidmain()(QueueQ;InitQueue(Q);Charx=fe';y='c';EnQueue(Q/h');EnQueue(Q/f);EnQueue(Q,y);DeQueue(Q,x);EnQueue(Qx);DeQueue(Q,x);EnQueue(Q,*a*);while(!QueueEmpty(Q))(DeQueue(Qy)；printf(y);};Printf(x);答：输出为"char”.3.IB述以下II法的功IB(株和队列的元素类型均为gvoidalgo3(Queue&Q)(StackS;intd;InitStack(S);while(!QueueEmpty(Q)){DeQueue(Qd);Push(S,d);}；while(!StackEmpty(S))(Pop(S,d);EnQueue(Qd);})答：该鼻法的功能建:利用瞄瞄助，捋队列中的数据元素诳行逆六.鼻法设计(毎小題5分，共15分.至少要写出思路)1.假设fttfflsqMm］存放備环队列的元為若妻使这m个分到利用,则需另f标志tag，以tag为。或1来区分IHitt和头微HK相同时队列的状态是"空”还是*试疆写相应的入队和出队的鼻法.解:这就是解决队満队空的三种办法之①设布尔变■以区别队満还黑队空(其他兩*见简SH)；思路:TH&队空,设tag=O,若从rearTMO到与front指针相同时,表示入队巳満，M令tag=l;S/Afront-MfinSJ与rear指针相同时,M$tag=O,表示岀队已空.2.试写fU法判别读入的f以@枷R符的字符序列是否是“回文”.答：编程如下:intPalindrom.Test。/冽别輸入的字符串是否回文序列,M返回L否则返回0(InitStack(S);InitQueue(Q)；while((c=getcharO)!=,@*)(Push(S,c);EnQueue(Q,c);//raB®用株和队列两种结构}while(!StackEmpty(S))(Pop(Sfa);DeQueue(Q,b));if(a!=b)returnERROR;}returnOK;}//Palindrome_Test第三章特殊线表习题一、选择题1、若用单链表来表示队列，则应该选用A、带尾指针的非循环链表B、带尾指针的循环链表C、带头指针的非循环链表D、带头指针的循环链表2、若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是 。A、1和5 B、2和4C、4和2 D、5和13、 设栈的输入序列为1、2、3、4,则不可能是其出栈序列。A、1243B、2134C、1432D、4312E、32144、 已知一算术表达式的中缀形式为A+B*C-D/E,后缀形式为ABC*+DE/-,其前缀形式为oA、-A+B*C/DEB、-A+B*CD/EC、-+*ABC/DE D、-+A*BC/DE5、 设栈的输入序列是1、2、…、n,若输出序列的第一个元素是n,则第i个输出元素是。A、不确定 B、n-i+1 C、iD、n-i6、 假定一个顺序循环队列的队首和队尾指针分别用front和rear表示，则判队空的条件是。A、front+l==rearB>front==rear+lC、front==0D、front=rear7、假定一个顺序循环队列存储于数组A[n]中，其队首和队尾指针分别用front和rear表示，则判断队满的条件是oA^(rear-1)%n~frontB、(rear+1)%n=frontC^rear==(front-1)%nD、rear==(front+l)%n

8、 一个栈的的输入序列为12345,则下列序列中不可能是栈的输出序列的是 。A、23415B、54132C、23145D、154329、 若一个栈的输入序列是1、2、3、…、n,输出序列的第一个元素是i,则第i个输出元素是。A、i-j-1 B、i-jC、j-i+1 D、不确定10、用单链表表示的链式队列的队头在链表的 位置。A、链头 B、链尾C、链中11、设计一个判别表达式中左、右括号是否配对出现的算法，釆用数据结构最佳。A、线性表的顺序存储结构B、队列C、线性表的链式存储结构D、栈12、在下列算法描述中，涉及到队运算的算法是DA、表达式求值算法B、深度优先搜索C、二叉树遍历D、广度优先搜索13、栈的插入和删除操作在进行。A、栈顶 B、栈底C、任意位置 D、指定位置14、在一个顺序循环队列中，队首指针指向队首元素的 位置。A、前一个 B、后一个C、当前 D、最后15、当利用大小为N的数组存储顺序循环队列时，该队列的最大长度为A、N-2 B