数据结构考研试题精选及答案第三章 栈和队列答案

1、第三章 栈和队列答案一、选择题1.B2.1B2.2A2.3B2.4D2.5.C3.B4.D5.D6.C7.D&B9.D10.D11.D12.C13.B14.C15.B16.D17.B18.B19.B20.D21.D22.D23.D24.C25.A26.A27.D28.B29.BD30.C31.B32.C33.1B33.2A33.3C33.4C33.5F34.C35.C36.A37.AD、判断题1. V2.73. 74. 75.x6.77.78. 79. 710.x11. 712.x13. x14.x15. 716.x17.718.x19.720. 7部分答案解释如下。1、尾递归的消除就不需用栈2、这个数是前序序列为l,2,3,.,n,所能得到的不相似的二叉树的数目。三、填空题1、操作受限(或限定仅在表尾进行插入和删除操作) 后进先出2、栈3、 3 1 24、 23 100CH5、 0 n+1 top1+1=top26、两栈顶指针值相减的绝对值为1(或两栈顶指针相邻)。7、(1)满 (2)空 (3)n (4)栈底 (5)两栈顶指针相邻(即值之差的绝对值为1)8、 链式存储结构 9、SXS

2、SXSXX10、data+top=x；11、23.12.3*2-4/34.5*7/+108.9/+(注：表达式中的点(.)表示将数隔开,如 23.12.3 是三个数)12、假溢出时大量移动数据元素。13、 (M+1) MOD N (M+1)% N；14、队列 15、先进先出16、先进先出17、s=(LinkedList)malloc(sizeof(LNode)； s-data=x;s-next=r-next； r-next=s； r=s；18、牺牲一个存储单元 设标记19、(TAIL+1) MOD M=FRONT (数组下标0到M-1,若一定使用1到M,则取模为0者，值 改取 M20、sq.front=(sq.front+1)%(M+1)； return(sq.data(sq.front)；(sq.rear+1)%(M+1)=sq.front；21、栈22、(rear-front+m) % m；23、( R-P+N) % N；24、 (1) ai或 a1 (2) ai (3) pop (s)或 s1；25、(1) PUSH(OPTR, w)(2) POP(OPTR)(3) PUSH(O

3、PND, operate(a, theta, b)26、( 1) T0( 2) i0( 4) topn( 5) top+1( 6) true( 7) i-1( 8) top-1( 9) T+wi( 10) false四、应用题1、栈是只准在一端进行插入和删除操作的线性表,允许插入和删除的一端叫栈顶,另一 端叫栈底。最后插入的元素最先删除，故栈也称后进先出(LIFO)表。2、队列是允许在一端插入而在另一端删除的线性表,允许插入的一端叫队尾,允许删 除的一端叫队头。最先插入队的元素最先离开(删除)，故队列也常称先进先出(FIFO)表。3、用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质(队尾插入和队 头删除)，容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而 队中元素个数小于队列的长度(容量)。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法 解决“队满”和“队空”的判定问题。4、(1)通常有两条规则。第一是给定序列中S的个数和X的个数相等；第二是从给定 序列的开始，到给定序列中的任

4、一位置，S的个数要大于或等于X的个数。(2) 可以得到相同的输出元素序列。例如，输入元素为A，B，C，则两个输入的合 法序列ABC和BAC均可得到输出兀素序列ABC。对于合法序列ABC，我们使用本题约定 的SxSxSx操作序列；对于合法序列BAC,我们使用SSxxSx操作序列。5、三个:CDEBA，CDBEA，CDBAE6、输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面 4个元素(4356)得到后，栈中元素剩12，且2 在栈顶，不可能栈底元素1 在栈顶元素2 之前出栈。得到135426的过程如下: 1入栈并出栈，得到部分输出序列1；然后2和3入栈， 3出 栈，部分输出序列变为:13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542； 最后 6 入栈并退栈，得最终结果135426。7、能得到出栈序列B、C、A、E、D,不能得到出栈序列D、B、A、C、E。其理由为：若 出栈序列以D开头，说明在D之前的入栈元素是A、B和C,三个元素中C是栈顶元素，B 和A不可能早于C出栈，故不可能得到D、B、A、C、E出栈序列。8、借助栈结构，n个入栈元

5、素可得到l/(n+l)(2n)! / (n!*n!)种出栈序列。本题4 个元素，可有14种出栈序列，abed和deba就是其中两种。但dabc和adbc是不可能得到 的两种。9、不能得到序列2， 5， 3， 4， 6。栈可以用单链表实现，这就是链栈。由于栈只在栈顶 操作，所以链栈通常不设头结点。10、如果ij，则对于pp.情况，说明P.在P.入栈前先出栈。而对于PP.的情况，则i jiji j说明要将P.压到P.之上,也就是在P.出栈之后P. 才能出栈。这就说明，对于ijk，不可 jiji能出现PM.的输出序列。换句话说，对于输入序列】，2, 3,不可能出现3, 1，2的输 出序列。11、(1)能得到325641。在123依次进栈后，3和2出栈，得部分输出序列32；然后4， 5入栈， 5出栈，得部分出栈序列325； 6入栈并出栈，得部分输出序列3256；最后退栈， 直到栈空。得输出序列325641。其操作序列为AAADDAADADDD。(2)不能得到输出顺序为154623的序列。部分合法操作序列为ADAAAADDAD，得到 部分输出序列1546后，栈中元素为23，3在栈顶，故不可能2先

6、出栈，得不到输出序列154623。12、(1)一个函数在结束本函数之前，直接或间接调用函数自身，称为递归。例如，函 数f在执行中，又调用函数f自身，这称为直接递归；若函数f在执行中，调用函数g,而 g在执行中，又调用函数f,这称为间接递归。在实际应用中，多为直接递归，也常简称为 递归。(2) 递归程序的优点是程序结构简单、清晰，易证明其正确性。缺点是执行中占内 存空间较多，运行效率低。(3) 递归程序执行中需借助栈这种数据结构来实现。(4) 递归程序的入口语句和出口语句一般用条件判断语句来实现。递归程序由基本 项和归纳项组成。基本项是递归程序出口，即不再递归即可求出结果的部分；归纳项是将原 来问题化成简单的且与原来形式一样的问题，即向着“基本项”发展，最终“到达”基本项。vol (4)13、函数调用结束时vol=14。执行过程图示如下：vol(4)=vol(3)+5=vol(2)+3+5vol(3)+5=vol(1)+4+3+5=vol(0)+2+4+3+5=0+2+4+3+5=14vol(0)+214、过程p递归调用自身时，过程p由内部定义的局部变量在p的2次调用期间，不占同一数据区

7、。每次调用都保留其数据区，这是递归定义所决定，用“递归工作栈”来实现15、 设H为n个盘子的Hanoi塔的移动次数。（假定n个盘子从钢针X移到钢针Z,可n借助钢针 Y）则 H =2H户1 先将n-1个盘子从X移到Y,第n个盘子移到Z,再将那n-1个n n-1移到 Z=2（ 2H +1 ）+1n-2=22 H +2+1n-2=22（ 2H +1 ）+2+1n-3=23 H +22+2+1n-3=2k H +2k-1 +2k-2 +21 +2 n-k=2n-1 H1+2n-2+2n-3+21+20因为 H = 1，所以原式 H =2n-1+2n-2+21+2=2n-1 1n故总盘数为 n 的 Hanoi 塔的移动次数是 2n-1。16、运行结果为：1 2 1 3 1 2 1（注：运行结果是每行一个数，为节省篇幅，放 到一行。）17、两栈共享一向量空间（一维数组），栈底设在数组的两端，两栈顶相邻时为栈满。 设共享数组为S MAX，则一个栈顶指针为-1，另一个栈顶指针为MAX时，栈为空。用C写的入栈操作push（i，x）如下：cons t MAX=共享栈可能达到的最大容量typedef str

8、uct nodeelemtype sMAX ；int top2；anode；anode ds;intpush（inti,elemtype x）/ds为容量有MAX个类型为elemtype的元素的一维数组，由两个栈共享其空间。i的值为0或1，x为类型为elemtype的元素。本算法将x压入栈中。如压栈成功，返回1；否则，返回 0。if (ds. topl-ds. top0=l) printf “栈满n”)； return (0)； switch(i)case 0：ds.s+ds.topi=x； break；case 1：ds.s-ds.topi=x；return( 1)； /入栈成功。18、本程序段查找栈S中有无整数为k的元素，如有，则删除。采用的办法使用另一个 栈T。在S栈元素退栈时，若退栈元素不是整数k,则压入T栈。遇整数k，k不入T栈， 然后将T栈元素全部退栈，并依次压入栈S中，实现了在S中删除整数k的目的。若S中 无整数k,则在S退成空栈后，再将T栈元素退栈，并依次压入S栈。直至T栈空。这后 一种情况下S栈内容操作前后不变。19、中缀表达式8-(3+5)*(5-6/2)的后缀表达式是： 8 3 5 + 5 6 2 / - * - 栈的变化过程图略(请参见22 题)，表达式生成过程为：1)8 3 5)+(#3)8 3 5 + 5 6 2 / -#4)8 3 5 + 5 6 2 / - * -中缀表达式 exp1 转为后缀表达式 exp2 的规则如下：设操作符栈s,初始为空栈后，压入优先级最低的操作符#对中缀表达式从左向右 扫描，遇操作数，直接写入exp2；若是操作符(记为w),分如下情况处理，直至表达式expl 扫描完毕。(1) w为一般操作符(+, -，*，/等)，要与栈顶操作符比较优先级，若w优先 级高于栈顶操作符，则入栈；否则，栈顶运算符退栈到exp2, w再与新栈顶操作符作上述 比较处理，直至w入栈。(2) w为左括号(),w入栈。(3) w为右括号()，操作符栈退栈并进入exp2，直到碰到左括号为止，左括号退 栈(不能进入exp2),右括号也丢掉，达到exp2中消除括号的目的。(4) w为#表示中缀表达式expl结束，操作符栈退栈到exp2，直至碰到, 退栈，整个操作结束。这里，再介绍一种简单方

《数据结构考研试题精选及答案第三章 栈和队列答案》由会员M****1分享，可在线阅读，更多相关《数据结构考研试题精选及答案第三章 栈和队列答案》请在金锄头文库上搜索。