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