1、计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编 6 及答案与解析一、综合题1 将两个栈 S1 和 S2 存入数组 V1m应如何安排最好?请写出栈顶指针 top 的初始值和判断栈空、栈满的条件是什么?【东南大学 1998 一、5(6 分)】【烟台大学2007 四、1(5 分) 】2 若有一个一维数组 A，它的元素下标从 1 开始到 MAX。要在数组 A 中建立两个栈共享同一空间，栈 S1 的栈顶指针为 top1，栈 S2 的栈顶指针为 top2，为了最大限度地利用数组 A 的空间，则应该如何共享?栈满和栈空的条件是什么?【北京理工大学 2006 十一、3(5 分)】3 设输入序列为 a，
2、b，c ， d，试写出借助一个栈可得到的两个输出序列和两个不能得到的输出序列。【北京科技大学 2001 一、4(2 分)】4 试证明：若借助栈由输入序列 1，2，n 得到输出序列为 P1，P 2，P n(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着Pfki。【上海交通大学 1998 二(15 分) 】5 什么是递归程序?6 递归程序的优、缺点是什么?7 递归程序在执行时，应借助于什么来完成?8 递归程序的入口语句、出口语句一般用什么语句实现?【大连海事大学 1996 二、4(4 分)】9 试推导出总盘数为 n 的 Hanoi 塔的移动次数。【北京邮电大学 2001 四、
3、3(5 分)】10 用一个数组 S(设大小为 MAX)作为两个堆栈的共享空间。请说明共享方法，栈满栈空的判断条件，并用 C 或 Pascal 设计公用的入栈操作 push(i，x)，其中 i 为0 或 1，用于表示栈号，x 为入栈值。【浙江大学 1998 五、2(7 分)】10 在一个算法中需要建立多个堆栈时可以选用下列三种方案之一，试问：这三种方案之间相比较各有什么优缺点?11 分别用多个顺序存储空间建立多个独立的堆栈；12 多个堆栈共享一个顺序存储空间；13 分别建立多个独立的链接堆栈。【北京航空航天大学 1998 一、6(4 分)】13 在某程序中，有两个栈共享一个一维数组空间 SPAC
4、EN、SPACE0、SPACN-1分别是两个栈的栈底。14 对栈 1、栈 2，试分别写出(元素 x)入栈的主要语句和出栈的主要语句。15 对栈 1、栈 2，试分别写出栈满、栈空的条件。【北京理工大学 1999 二、2(8分)】16 用栈实现将中缀表达式 8 一(3+5)*(562)转换成后缀表达式，画出栈的变化过程图。【南京航空航天大学 2001 五(10 分)】17 将表达式 a+b)*c+d-(e+g)*h 改写成后缀表达式。 【吉林大学 2007 二、4(3 分)】18 在表达式中，有的运算符要求从右到左计算，如 A*B*C 的计算次序应为(A*(B*C)，这在由中缀生成后缀的算法中是怎
5、样实现的?( 以*为例说明)【东南大学 1993 一、2(6 分)1997 一、1(8 分) 】19 有字符串次序为 3*-y-a/y2，利用栈，给出将次序改为 3y-*ay2的操作步骤。(可用 X 代表扫描该字符串过程中顺序取一个字符进栈的操作，用 S 代表从栈中取出一个字符加入到新字符串尾的出栈操作。例如，ABC 变为 BCA 的操作步骤为XXSXSS。)【东北大学 2001 一、4(4 分)】20 用栈作工具，将十进制数 9027 转换为八进制数，试列出运算过程和栈中元素的变化过程。【华中科技大学 2006 四、1(10 分)】21 画出对算术表达式 A-B*CD-EF 求值时，操作数栈
6、和运算符栈的变化过程。【东南大学 2000 一、3(6 分)】22 设输入元素为 1、2、3、P 和 A，输入次序为 123PA，如图(编者略)。元素经过栈后到达输出序列，当所有元素均到达输出序列后，有哪些序列可以作为高级语言的变量名?【 中山大学 1997】23 简述顺序存储队列的假溢出的避免方法及队列满和空的条件。【山东大学 2000一、2(4 分) 】24 简要叙述循环队列的数据结构，并写出其初始状态、队列空、队列满时的队首指针与队尾指针的值。【南京航空航天大学 1995 七(5 分)】25 队列可以用循环单链表来实现，故可以只设置一个头指针或者只设置一个尾指针。请你分析对于循环单链表实
7、现的队列，用哪种方案更合适。【北京大学 2003五、1(5 分) 】26 利用两个栈 s1、s2 模拟一个队列时，如何用栈的运算实现队列的插入、删除以及判队空运算。请简述这些运算的算法思想。【北京邮电大学 1992 一、1】【东南大学 1999 一、1(7 分) 】26 如果用一个循环数组 q0 一 m 一 1表示队列时，该队列只有一个队列头指针front，不设队列尾指针 rear，而改置计数器 count 用以记录队列中结点的个数。27 编写实现队列的三个基本运算：判空、入队、出队。(3 分)28 队列中能容纳元素的最多个数是多少? (1 分) 【东北大学 2002 一、1】计算机专业基础综
8、合数据结构（栈和队列）历年真题试卷汇编 6 答案与解析一、综合题1 【正确答案】 设栈 S1 和栈 S2 共享向量 V1 一 m，初始时，栈 S1 的栈顶指针top0=0，栈 S2 的栈顶指针 top1=m+1，当 top0=0 时为左栈空，top1=m+1 时为右栈空；当 top0=0 并且 top1=m+1 时为全栈空。当 top1-top0=1 时为栈满。2 【正确答案】 两栈共享数组 A，top1=0 时 S1 栈空， top2=MAX+1 时，S2 栈空；top2 一 top1=1 时栈满。3 【正确答案】 n 个元素的排列有 n!种，但借助栈结构，n 个入栈元素只可得到1(n+1)
9、(2n)!(n!*n!)种出栈序列，这个数小于，l!。本题 4 个元素，可有 14 种出栈序列，abcd 和 dcba 就是其中两种；有 10(4114=10)种排列得不到，其中，dabc 和 adbc 是不可能得到的两种。4 【正确答案】 如果 ii 在 pj 入栈前先出栈。而对于 pip j 的情况，则说明要将 pi 压到 pj 之上，也就是在 pj 出栈之后 pi 才能出栈。这就说明，对于 ijk，不可能出现 Pjki 的输出序列。换句话说，对于输入序列 1， 2，3，不可能出现 3，1，2 的输出序列。5 【正确答案】 (1)一个函数在结束本函数运行之前，直接或间接调用函数自身，称为递
10、归。例如，函数 f 在执行中，又调用函数 f 自身，称为直接递归；若函数 f执行中，调用函数 g，而 g 执行中，又调用函数 f,这称为间接递归。在实际应用中，多为直接递归，也常简称为递归。6 【正确答案】 递归程序的优点是程序结构简单、易读、清晰，易证明其正确性。缺点是执行中占内存空间较多，运行效率低，不易优化。7 【正确答案】 递归程序执行中需借助栈这种数据结构来实现。8 【正确答案】 递归程序的入口语句和出口语句一般用条件判断语句来实现。9 【正确答案】 设 Hn 为 n 个盘子的 Hanoi 塔的移动次数(假定 n 个盘子从钢针 X 移到钢针 z，可借助钢针 Y)，则 Hn=2Hn-1
11、+1先将 n 一 1 个盘子从 X 移到 Y，第n 个盘子移到 z，再将那 n 一 1 个移到 Z=2(2Hn-2+1)+1=22Hn-2+2+1=22(2n-3+1)+2+1=23Hn-3+22+2+1=2Hn-k+2k-1+2k-2+21+20=2n-1H1+2n-2+2n-3+21+20 因为H1=1，所以 H1=2n-1+2n-2+21+20=2n 一 1。故总盘数为 n 的 Hanoi 塔的移动次数是2n1。10 【正确答案】 设栈 S1 和栈 S2 共享向量 V1 一 m，初始时，栈 S1 的栈顶指针top0=0，栈 S2 的栈顶指针 top1=m+1，当 top0=0 时为左栈空
12、，top1=m+1 时为右栈空；当 top0=0 并且 top1=m+1 时为全栈空。当 top1一 top0=1 时为栈满。入栈核心语句段如下：if(ds top1一 dstop0=1)cout“栈满”； return(0)；)switch(i)case 0：dss+ds topi=x；break；case 1：dss-一 dstopi=x；)return(1)； 入栈成功11 【正确答案】 每个栈用一个顺序存储空间时，操作简便，但分配存储空间小了，容易产生溢出，分配空间大了，容易造成浪费，各栈不能共享空间。12 【正确答案】 多个栈共享一个顺序存储空间，充分利用了存储空间，只有在整个存储空
13、间都用完时才能产生溢出，其缺点是当一个栈满时要向左、右栈查询有无空闲单元。如果有，则要移动元素和修改相关的栈底和栈顶指针。当接近栈满时，查询空闲单元、移动元素和修改栈底栈顶指针的操作频繁，计算复杂并且耗费时间。13 【正确答案】 多个链栈一般不考虑栈的溢出(仅受用户内存空间限制)，缺点是栈中元素要以指针相链接，比顺序存储多占用了指针所用的存储空间。14 【正确答案】 设 topl 和 top2 分别为栈 1 和栈 2 的栈顶指针(1)入栈主要语句：if(top2 一 topl=1)(cout“栈满”； exit(0)；)casel：topl+； SPACEtopl=x ； 设 X 为入栈元素C
14、ase2：top2 一一； SPACEtop2=x ；出栈主要语句：casel：if(topl=一 1)(cout”栈空“；exit(0)；topl 一一；return(SPACEtopl+1)； 返回出栈元素Case2：if(top2=N)cout“栈空”；exit(0) ；top2+；return(SPACEtop2 1)； 返回出栈元素15 【正确答案】 栈满条件：top2 一 top1=1栈空条件：topl=一 1top2=N topl= 一 1 为左栈空，top2=N 为右栈空16 【正确答案】 中缀表达式 8-(3+5)*(562)的后缀表达式是：8 3 5+5 6 2一*一表达式
15、生成过程为： 中缀表达式 expl 转为后缀表达式 exp2 的规则如下：设操作符栈 S，初始化为空栈，压入优先级最低的操作符#。对中缀表达式从左向右扫描，遇操作数，直接写入exp2；若是操作符 (记为 W)，分如下情况处理，直至表达式 exp1 扫描完毕。(1)w为一般操作符(+，-，*。等)，要与栈顶操作符比较优先级，若 w 优先级高于栈顶操作符，则入栈；否则，栈顶运算符退栈到 exp2，w 再与新栈顶操作符作上述比较处理，重复(1)，直至 w 入栈。(2)w 为左括号 ()，w 入栈。(3)w 为右括号()，操作符栈退栈并进入 exp2，直到碰到左括号为止，左括号退栈(不能进入exp2)
16、，右括号也丢掉，达到 exp2 中消除括号的目的。(4)w 为#，表示中缀表达式expl 结束，操作符栈中元素依次退栈进入 exp2，直至碰到#，退栈，整个操作结束。这里，再介绍一种简单方法。中缀表达式转为后缀表达式有三步：首先，将中缀表达式中所有的子表达式按计算规则用嵌套括号括起来；接着，顺序将每对括号中的运算符移到相应括号的后面；最后，删除所有括号。例如，将中缀表达式 8 一(3+5)*(562)转为后缀表达式。按如上步骤：执行完上面第一步后为：(8 一(3+5)*(5 一(62)；执行完上面第二步后为：(8(35)+(5(62)f)一)*)一；执行完上面第三步后为：8 3 5+5 6 2
17、一*一。同样可将中缀表达式转为前缀表达式，差别是第二步，将运算符移至相应括号的左侧。17 【正确答案】 ab+c*d+eg+h*一18 【正确答案】 中缀表达式转为后缀表达式的规则基本上与上面 21 题相同，不同之处是对运算符料优先级的规定。在算术运算中，先乘除后加减，先括号内后括号外，相同级别的运算符按从左到右的规则运算。而对料运算符，其优先级同常规理解，即高于加减乘除而小于左括号。为了适应本题中“从右到左计算” 的要求，规定栈顶运算符料的级别小于正从表达式中读出的运算符料，即刚读出的运算符料级别高于栈顶运算符料，因此也入栈。下面以 A*B*C 为例说明实现过程。读入A，不是操作符，直接写入
18、结果表达式。再读入*，这里规定在读入 *后，不能立即当乘号处理，要看下一个符号，若下个符号不是*，则前个*是乘号。这里因为下一个待读的符号也是*，故认为*是一个运算符，与运算符栈顶比较(运算符栈顶初始化后，首先压入#作为开始标志)，其级别高于#，入栈。再读入 B，直接进入结果表达式。接着读入料，与栈顶比较，均为料，我们规定，后读入的料级别高于栈顶的料，因此料入栈。接着读入 C，直接到结果表达式。现在部分结果(后缀)表达式是 ABC。最后读入 #，表示输入表达式结束，这时运算符栈中从栈顶到栈底有两个料和一个#。两个运算符料退栈至结果表达式，结果表达式变为 ABC*。运算符栈中只剩#，退栈，运算结
19、束。19 【正确答案】 XSXXXSSSXXSXXSXXSSSS20 【正确答案】 十进制数转换为八进制数的核心语句段如下： while(N)Push(s，N 8)；N=N8； while(!stackEmpty(s) (Pop(s，e; cout 10=(21503)8，运算中八进制数入栈的顺序是 30512。21 【正确答案】 设操作数栈是 opnd，操作符栈是 optr，对算术表达式 A 一B*CDEF 求值，过程如下：22 【正确答案】 一般来说，高级语言的变量名是以字母开头的字母数字序列。故本题答案是：AP321，PA32 1，P3A21 ，P32A1，P321A 。23 【正确答案
20、】 设顺序存储队列用一维数组 gm表示，其中 m 为队列中元素个数，队列中元素在向量中的下标从 0 到 m 一 1。设队头指针为舶 nt，队尾指针是rear，约定 front 指向队头元素的前一位置， rear 指向队尾元素。当 front 等于一 1时队空，rear 等于 m 一 1 时为队满。由于队列的性质(“删除” 在队头而“插入”在队尾)，所以当队尾指针 rear 等于 m 一 1 时，再无法入队。若经过几次退队，队列中会有空闲单元，所以队列并不是真满，这称为“假溢出” 。其解决办法有二，一是将队列元素向前“ 平移”( 占用 0 至 rear 一 front1)；二是将队列看成首尾相连
21、，即看做循环队列(0 一 m 一 1)。在循环队列下，仍定义 front=rear 时为队空，而判断队满则常用两种方法：一种是用“牺牲一个单元” ，即 rear+1=front(准确记是(rear+1) 时 m=front，m 是队列容量)时为队满；另一种方法是“ 设标记”，如设标记tag，tag=0 时为队空；tag=1 时，若因插入导致舶 nt=rear 则为队满。24 【正确答案】 typedef struct nodeelemtype elemcqm； m 为队列最大可能的容量int front，rear； front 和 rear 分别为队头和队尾指针cqnode ；cqnode c
22、q；(1)初始状态cqfront=cqrear=0 ；(2)队列空cqfront=cqrear；(3)队列满(cqrear+1) m=cqfront；25 【正确答案】 循环单链表若只设头指针，则出队操作时间复杂度是 O(1)，而入队操作时间复杂度是 O(n)；若只设尾指针，则出队和入队操作时间复杂度都是O(1)。显然，后者更好。26 【正确答案】 栈的特点是后进先出，队列的特点是先进先出。初始时设栈 s1和栈 s2 均为空。(1) 用栈 s1 和 s2 模拟一个队列的输入：设 s1 和 s2 容量相等。分以下三种情况讨论：若 s1 未满，则元素入 s1 栈；若 s1 满，s2 空，则将 s1
23、 退栈到空，退栈元素依次压栈入 s2，之后元素入 s1 栈；若 s1 满，s2 不空(已有出队列元素)，则不能入队。(2)用栈 s1 和 s2 模拟队列出队(删除)：若栈 s2 不空，退栈，即是队列的出队；若 s2 为空且 s1 不空，则将 s1 栈中全部元素退栈，并依次压入 s2中，s2 栈顶元素退栈，这就是相当于队列的出队。若栈 s1 为空并且 s2 也为空，队列空，不能出队。(3)判队空：若栈 s1 为空并且 s2 也为空，才是队列空。讨论：s1和 s2 容量之和是队列的最大容量。其操作是，s1 栈满后，全部退栈并压栈入s2(设 s1 和 s2 容量相等)。再入栈 s1 直至 s1 满。
24、这相当于队列元素 “入队”完毕。出队时，s2 退栈完毕后，s1 栈中元素依次退栈到 s2，s2 退栈完毕，相当于队列中全部元素出队。在栈 s2 不空情况下，若要求入队操作，只要 s1 不满，就可压入 s1中。若 s1 满和 s2 不空状态下要求队列的入队时，按出错处理。27 【正确答案】 typedef structElemType q cm；int front，count；front 是队首指针，count 是队列中元素个数cqnode； 定义类型标识符(1)判空：int Empty(cqnode cq) cq 是 cqnode 类型的变量if(cqcount=o)return(1)；els
25、e return(0) ； 空队列入队：int EnQueue(cqnode cq，E1emType x)if(count=m)cout“队满” ，exit(0) ；cqq(cqfront+count)m=x； x 入队count+；return(1)；) 队列中元素个数增加 1，入队成功出队：int DelQueue(cqnode cq)if(count=0)cout“队空 ”；return(0)；)cout“出队元素 ”cqqcqfrontendl ；x=cqqcqfront；cqfront=(cq front+1)m； 计算新的队头指针return(x) 28 【正确答案】 队列中能容纳元素的最多个数为 m。队头指针 front 指向队头元素。
