1、计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编 7 及答案解析(总分：74.00，做题时间：90 分钟)一、单项选择题(总题数：19，分数：38.00)1.若循环队列使用 C 数组 Am存放其数据元素，已知头指针 front 指向队首元素，尾指针 rear 指向队尾元素后的空单元，则当前队列中的元素个数为( )。【华中科技大学 2007 一、3(2 分)】（分数：2.00）A.(rearfront+m)mB.rear-front+1C.rear-frontD.rear-front-12.设顺序队列的容量为 MaxSize，其头指针为 front，尾指针为 rear，空队列的条件为( )
2、。【电子科技大学 2008 一、4(2 分)】（分数：2.00）A.front=rearB.front=-MaxSizeC.front+1=rearD.rear=03.循环队列存储在数组 A0m中，则入队时的操作为( )。【中山大学 1999 一、6(1 分)】（分数：2.00）A.rear=rear+1B.rear=(rear-H)mod(m 一 1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)4.若用一个大小为 6 的数组来实现循环队列，且当前 rear 和 front 的值分别为 0 和 3，当从队列中删除一个元素，再加入两个元素后，rear 和
3、front 的值分别为多少?( )【浙江大学 1999 四、1(4 分)】（分数：2.00）A.1 和 5B.2 和 4C.4 和 2D.5 和 15.已知输入序列为 abcd，经过输出受限的双向队列后能得到的输出序列有( )。【西安交通大学 1996 三、3(3 分)】（分数：2.00）A.dacbB.cadbC.dbcaD.bdacE.以上答案都不对6.若以 1234 作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是( )。【西安电子科技大学 1996 一、5(2 分)】【烟台大学 2007 一、5(2 分)】（分数：2.00）A.123
4、4B.4132C.4231D.42137.最大容量为 n 的循环队列，队尾指针是 rear，队头是 frunt，则队空的条件是( )。【南京理工大学1999 一、16(2 分)】（分数：2.00）A.(rear+1)MOD n=frontB.rear=frontC.rear+1=frontD.(rear-1)MODn=front8.栈和队的共同点是( )。【大连理工大学 2004 一、1(2 分)】（分数：2.00）A.都是先进后出B.都是后进先出C.只允许在端点处插入和删除元素D.没有共同点9.将递归算法转变成对应非递归算法时，需要使用( )保存中间结果。【华中科技大学 2007 一、15(
5、2 分)】（分数：2.00）A.栈B.队列C.二叉树D.单链表10.队列的“先进先出”特性是指( )。【武汉理工大学 2004 一、4(3 分)】（分数：2.00）A.最后插入队列中的元素总是最后被删除B.当同时进行插入、删除操作时，总是插入操作优先C.每当有删除操作时，总要先做一次插入操作D.每次从队中删除的总是最早插入的元素11.设栈 S 和队列 Q 的初始状态为空，元素 e 1 ，e 2 ，e 3 ，e 4 ，e 5 和 e 6 依次通过栈 S，一个元素出栈后即进队列 Q，若 6 个元素出队的序列是 e 2 ，e 4 ，e 3 ，e 6 ，e 5 ，e 1 ，则栈 S 的容量至少应该是(
6、 )。【南京理工大学 2000 一、6(15 分)】【哈尔滨工业大学 2004 、3(1 分)】（分数：2.00）A.6B.4C.3D.212.用单链表表示的链式队列的队头在链表的( )位置。【清华大学 1998 一、1(2 分)】 【烟台大学 2007一、6(2 分)】（分数：2.00）A.链头B.链尾C.链中13.实现时需使用队列的运算是( )。【电子科技大学 2005 一、9(1 分)】（分数：2.00）A.递归过程B.二叉树的中序遍历C.图的深度优先搜索D.二叉树的层次遍历14.下列更合适表示队列的链表结构是( )。【北京理工大学 2006 九、6(1 分)】（分数：2.00）A.单向
7、链表B.单向循环链表C.双向链表D.双向循环链表15.队列操作的原则是( )。【暨南大学 2010 一、2(2 分)】（分数：2.00）A.先进先出B.后进先出C.只能进行插入D.只能进行删除16.执行( )操作时，需要使用队列作辅助存储空间。【华中科技大学 2006 一、1(2 分)】（分数：2.00）A.查找哈希(Hash)表B.广度优先搜索网C.先序(根)遍历二叉树D.深度优先搜索网17.在下列栈的基本操作中，( )的初始条件不要求栈 S 已存在。【北京理工大学 2007 一、3(1 分)】（分数：2.00）A.InitStack(&S)B.DestroyStack(&S)C.Clear
8、Stack(&S)D.StackEmpty(S)18.在算符优先级中，算符“+”和“(”的优先关系是( )。【北京理工大学 2007 一、5(1 分)】（分数：2.00）A.“+”“(”B.“+”m，队头和队尾指针分别为 front 和 rear，则此循环队列判满的条件是_。【中南大学 2003 三、4(1 分)】（分数：2.00）_21.循环队列用数组 A0 一 m 一 1存放其元素值，已知其头尾指针分别是 front 和 rear，则当前队列的元素个数是_。【厦门大学 2000 六、1(163 分)】【北京交通大学 2005 二、9(2 分)】（分数：2.00）_22.用循环链表表示的队列
9、长度为 n，若只设头指针，则出队和入队的时间复杂度分别是一和_；若只设尾指针，则出队和入队的时间复杂度分别是_和_。【西安电子 科技大学 2003 一、2(2010 分)】（分数：2.00）_23.设循环队列容量为 Q，当 rear“(”B.“+”m，队头和队尾指针分别为 front 和 rear，则此循环队列判满的条件是_。【中南大学 2003 三、4(1 分)】（分数：2.00）_正确答案：(正确答案：(rear+1)(n 一 m+1)=front)解析：21.循环队列用数组 A0 一 m 一 1存放其元素值，已知其头尾指针分别是 front 和 rear，则当前队列的元素个数是_。【厦门
10、大学 2000 六、1(163 分)】【北京交通大学 2005 二、9(2 分)】（分数：2.00）_正确答案：(正确答案：(real 一 front+m)m；)解析：22.用循环链表表示的队列长度为 n，若只设头指针，则出队和入队的时间复杂度分别是一和_；若只设尾指针，则出队和入队的时间复杂度分别是_和_。【西安电子 科技大学 2003 一、2(2010 分)】（分数：2.00）_正确答案：(正确答案：O(1)，O(n)，O(1)，O(1)解析：23.设循环队列容量为 Q，当 rear=Sstacksize 一 1 (2)!Sbase(3)Sbase+Sstacksize一 1 (4)Sst
11、acksize+1 (5)*(+Stop)=e)解析：三、综合题(总题数：11，分数：22.00)27.假设以 I 和 O 分别表示入栈和出栈操作，栈的初态和终态均为空。入栈和出栈的操作序列表示为仅由I 和 O 组成的序列。“(1)下面所示的序列中哪些是合法的?(2 分)A.IOIIOIOOB.IOOIOIIOC.IIIOIOIO D.IIIOOIOO“(2)通过对(1)的分析，给出判断一个给定序列是否合法的算法思想。 (4 分)【哈尔滨工业大学 2005 四、2(6 分)】【武汉大学 2000 五、2(12 分)】（分数：2.00）_正确答案：(正确答案：(1)A 和 D 是合法的。(2)设
12、立一个字符栈，从左到右对 IO 序列做如下处理。遇 I就入栈，遇 O 就出栈。若遇 O 出栈前栈空，则序列不合法，退出算法。若序列处理完但是栈不空，序列不合法。只有序列处理完且栈空，序列才是合法序列。)解析：28.假设以 S 和 X 分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由 S 和 X 组成的序列表示(如 SXSX)。(1)试指出判别给定序列是否合法的一般规则。(2)两个不同合法序列(对同一输入序列)能否得到相同的输出元素序列?如能得到，请举列说明。【东南大学 1992 二(10 分)】（分数：2.00）_正确答案：(正确答案：(1)通常有两条规则。第一是给定序列中 S 的个数
13、和 X 的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，S 的个数要大于或等于 X 的个数。(2)可以得到相同的输出元素序列。例如，输入元素为 A，B，C，则两个输入的合法序列 ABC 和 BAC 均可得到输出元素序列 ABC。对于合法序列 ABC，我们使用本题约定的 SXSXSX 操作序列；对于合法序列 BAC，我们使用 SSXXSX 操作序列。)解析：29.设 a，b，c 三个元素的进栈次序是 a，b，c，符号 PUSH：与 POP 分别表示对堆栈进行一次进栈操作与一次出栈操作。(1)请分别写出所有可能的出栈序列以及获得该出栈序列的操作序列；(2)指出不可能出现的出栈序列。【北
14、京航空航天大学 2007 一、1(3 分)】（分数：2.00）_正确答案：(正确答案：(1)出栈序列有：abc，acb，bac，bca，cba 出栈序列 abc 的操作序列是 PUSHPOP PUSHPOP PUSHPOP，其他操作序列略。(2)cab 是不可能的出栈序列。c 进栈时 ab 已在栈中，a 在栈底，不可能先于 b 出栈。)解析：30.有 n 个数顺序依次进栈，所有可能的出栈序列共有多少种?【厦门大学 2006 一、2(203 分)】（分数：2.00）_正确答案：(正确答案：1(n+1)*(2n)!)(n!)*(n!)解析：31.名词解释：栈。【吉林工业大学 1999 一、3(2
15、分)】【燕山大学 1999 一、1(2 分)】（分数：2.00）_正确答案：(正确答案：栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出(LIFO)表。)解析：32.名词解释：队列。【大连海事大学 1996 一、6(1 分)】（分数：2.00）_正确答案：(正确答案：队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离开(删除)，故队列也常称先进先出(FIFO)表。)解析：33.什么是循环队列?【哈尔滨工业大学 2001 三、2(3 分)】【河南大学 1998
16、一、4(3 分)】（分数：2.00）_正确答案：(正确答案：用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质(队尾插入和队头删除)，容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再入队，然而队列中元素个数小于队列的长度(容量)。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队 满”和“队空”的判定问题。应该指出，除特别说明，循环队列通常是指顺序存储结构，而不是链式存储结构。)解析：34.有 5 个元素，其入栈次序为 A，B，e D，E，在各种可能的出栈序列中，第一个出栈元素为 C 且第二个
17、出栈元素为 D 的出栈序列有哪几个?【武汉理工大学 2003 三、23(6 分)】【北京航空航天大学 2008 一、2(4 分)】（分数：2.00）_正确答案：(正确答案：三个：CDEBA，CDBEA，CDBAE)解析：35.设栈 S 和队列 Q 的初始状态为空，元素 1、2、3、4、5、6 依次通过栈 S，一个元素出栈后即进入队列Q。若这 6 个元素出队列的顺序是 2、4、3、6、5、1，则栈的容量至少应该是多少?【厦门大学 2006 一、1(203 分)】（分数：2.00）_正确答案：(正确答案：3)解析：36.递归算法和非递归算法比较有哪些主要的优点和缺点?【北京理工大学 2005 三、
18、2(4 分)】（分数：2.00）_正确答案：(正确答案：递归程序的优点是程序结构简单、清晰，程序易读，易证明其正确性。缺点是执行中占内存空间较多，运行效率低，算法不容易优化。)解析：37.简述递归过程的关键点。【电子科技大学 2005 三、4(6 分)】（分数：2.00）_正确答案：(正确答案：递归算法的设计实际上就是对问题抽象的过程，如果抽象到每个小问题都有相同特征时，那就形成了递归。递归定义由基本项和归纳项两部分组成。基本项描述了递归过程的一个或几个终结状态，即不需要继续递归就可求值的状态。归纳项描述了从当前状态向终结状态的转换。即将复杂问题化为较简单的问题，而简单问题与复杂问题的形式是一样的。每递归一次都要向终止条件靠近一步，最终达到终止条件。递归是程序设计中的重要技术。当问题的定义是递归的、数据结构是递归的和问题的解法是递归的时，最好利用递归。求解递归问题时，要先写出问题求解的递归定义。递归定义由基本项和归纳项组成。递归过程的实质是将复杂问题分解成若干子问题，子问题与原问题具有相同特征，但是简单了。子问题解决了，原问题就迎刃而解了。)解析：
