1、计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编 2 及答案与解析一、单项选择题1 为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( )。【2009 年全国试题 1(2)分】（A）栈（B）队列（C）树（D）图2 设栈 S 和队列 Q 的初始状态均为空，元素 a，b ，c ，d,e,j,g=g 依次进入栈 S。若每个元素出栈后立即进入队列 Q，且 7 个元素出队的顺序是b，d，c，f，e ，a，g，则栈 S 的容量至少是( )。【2009 年全国试题 2(2)分】（A）
2、1（B） 2（C） 3（D）43 若元素 a， b，c ，d,e，f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是( )。 【2010 年全国试题 1(2)分】（A）d,c，e，b，f,a（B） c，b，d,a ，e ，f（C） b，c，a ，e ，f ，d（D）a,f，e,d,c，b4 某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a，b，c，d，e 依次入此队列后再进行出队操作，则不可能得到的出队序列是( )。【2010 年全国试题 2(2)分】（A）b，a， c，d, e（B） d,b，a，c ，e（C） d，b,c，a
3、 ，e（D）e，c，b，a，d5 元素 a，b， c，d,e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素 d 开头的序列个数是( )。 【 2011 年全国试题 2(2)分】（A）3（B） 4（C） 5（D）66 已知循环队列存储在一维数组 A0n-1中，且队列非空时 front 和 rear 分别指向队头元素和队尾元素。若初始时队列为空，且要求第 1 个进入队列的元素存储在A0处，则初始时 front 和 rear 的值分别是( )。 2011 年全国试题 3(2)分】（A）0，0（B） 0，n1（C） n 一 1，0 （D）n
4、一 1，n 一 17 已知操作符包括“+”，“-”，“”，“(和)。将中缀表达式 a+b 一 a*(c+d)e-f+g转换为等价的后缀表达式 ab+acd+e/f*-g+时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是( )。【2012 年全国试题 2(2)分】（A）5（B） 7（C） 8（D）1 18 一个栈的入栈序列为 1，2，3，n，其出栈序列是 p1，p 2，p 3，p n。若p2=3，则 p3 可能取值的个数是( ) 。【2013 年全国试题 2(2)分】（A）n 一 3（B） n 一 2（C） n 一 1（D）无法确定9
5、假设栈初始为空，将中缀表达式 ab+(c*d-e*f)g 转换为等价的后缀表达式的过程中，当扫描到 f 时，栈中的元素依次是( )。【2014 年全国试题 2(2)分】（A）+(*一（B） +(一*（C） +(*一 *（D）+ 一*10 循环队列存放在一维数组 A0M-1中，endl 指向队头元素，end2 指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳 M-1个元素，初始时为空。下列判断队空和队满的条件中，正确的是( )。【2014 年全国试题 3(2)分 】（A）队空：end1=end2； 队满：end1=(end2+1)mod M（B）队空：end1=en
6、d2 ； 队满：end2=(end1+1)modM-1)（C）队空：end2=(end1+1)modM; 队满：end4=(end2+1)modM（D）队空：end1=(end2+1)modM； 队满：end2=(endl+1)modM-1)11 已知程序如下：int s(int n) return(nS(1)一S(0)（B） S(0)一S(1)一main()（C） main()一 S(0)一S(1)（D）S(1)一S(0)一main()12 一个栈的输入序列为 1，2，3，n，若输出序列的第一个元素是 n，输出第i(1fn)个元素是( )。【电子科技大学 2012 一、4(2 分)】【中山大
7、学 1999 一、9(1 分)】（A）不确定（B） n-i（C） i （D）n-i+l13 设栈的输入序列为 1，2，3，n；输出序列为 p1，p2，Pn!若 p1=n，则当 ni1 时，p t 为( )；若存在 k1 使 pk=n，则当 tk 时，P t 为( ) 。【中国科学技术大学 1992 八、8(1 分) 】（A）p=i+l（B） pi 不确定（C） pi=n-(i-k)14 中缀表达式(A+B)*(C-D)(E-F*G)的后缀表达式是( )。【北京邮电大学 2005一、2(2 分) 】（A）A+B*C-D E-F*G（B） AB+CD-*EFG*-（C） AB+C*D-E-G*（D
8、）ABCDEFG+*-*二、填空题15 若某堆栈初始为空，PUSH 与 POP 分别表示对栈进行一次进栈与出栈操作，那么，对于输入序列 a，b， c，d，e，经过PUSH，PUSH，POP,PUSH ，POP,PUSH，PUSH 以后，输出序列是_。【北京航空航天大学 2006 一、3(1 分)】16 在栈的 ADT 定义中，除初始化操作外，其他基本操作的初始条件都要求_。【北京理工大学 2005 二、1(2 分)】17 若已知一个栈的入栈序列是 1，2，3，n，其输出序列为p1，p 2，p 3，p n，若 p1=n，则 pi 为_。【北京交通大学 2005 二、2(2 分)】18 栈是_的线
9、性表，其运算遵循_的原则。【北京科技大学1997 一、3】19 堆栈是一种操作受限的线性表，它只能在线性表的_进行插入和删除操作，对栈的访问是按照_的原则进行的。【暨南大学 2010 二、3(2 分)】20 向栈中压入元素的操作是先_，后_。【暨南大学 2011 二、5(2 分)】三、判断题21 同一组不重复输入序列执行不同的入、出栈组合操作，所得结果也可能相同。( )【北京邮电大学 2005 二、3(1 分)】（A）正确（B）错误22 消除递归不一定需要使用栈。( )【中科院计算所 1998 二、2(2 分)】【中国科技大学 1998 二、2(2 分) 】（A）正确（B）错误23 栈是实现过
10、程和函数等子程序所必需的结构。( )【合肥工业大学 2000 二、2(1分)】（A）正确（B）错误24 栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。( )【暨南大学 201 1 三、6(1 分) 】（A）正确（B）错误25 两个栈共享一个向量空间的优点是其中一个栈可用该空间的一半或以上。( )【哈尔滨工程大学 2005】（A）正确（B）错误26 即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。( )【北京邮电大学 1999 二、4(2 分)】【中国海洋大学 2005 二、11(1 分)】（A）正确（B）错误27 有 n 个数顺序(
11、依次) 进栈，出栈序列有 Cn 种，Cn=1n+1)*(2n)! (n!)*(n!)。( )【北京邮电大学 1998 一、3(2 分) 】（A）正确（B）错误28 设栈采用顺序存储结构。若已有 i-1 个元素入栈，则将第 i 个元素入栈时，入栈算法的时间复杂性为 O(i)。( ) 【上海交通大学 1994 一、1(2 分)】（A）正确（B）错误29 栈的输入序列是 1，2，n，输出序列是 a1，a 2，a n，若 ai=n(1f，2) ，则有：a iai+1an。( )【 中国科学技术大学：1991 一、5(2 分) 】（A）正确（B）错误30 设栈采用顺序存储结构，若已有 n 个元素进栈，则
12、出栈算法的时间复杂性为O(n)。( ) 【上海海事大学 2005 一、2(2 分)】（A）正确（B）错误计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编 2 答案与解析一、单项选择题1 【正确答案】 B2 【正确答案】 C【试题解析】 按元素出队顺序计算栈的容量。b 进栈时栈中有 a，b 出栈，cd 进栈，栈中有 acd，dc 出栈，ef 进栈，栈中有 aef,fea 出栈，栈空，g 进栈后出栈。所以栈 S 的容量至少是 3。3 【正确答案】 D4 【正确答案】 C【试题解析】 a 先入队，b 和 c 可在 a 的任一端入队，选项 A、B 、D 都符合要求，只有选项 C 不可能出现。双端
13、队列出队结果的分析可参见四、 36。5 【正确答案】 B【试题解析】 元素 d 进栈时，元素 a，b ，c 已在栈中，d 出栈后，P 可以在a，b，c 任一元素的前面进栈并出栈，也可以在元素 a 后出栈，c，b，a 必须依次出栈，所以元素 d 开头的序列个数是 4。6 【正确答案】 B【试题解析】 队列的入队在队尾，答案中 B 和 D 入队(0 一 1)+1)n 的结果为0，因为要求第 1 个进入队列的元素存储在 A0处，且 front 和 rear 分别指向队头元素和队尾元素，故选 B。7 【正确答案】 A8 【正确答案】 C【试题解析】 1，2 先于 3 已入栈，且其中有一个已出栈，另一个
14、在 3 入栈并出栈后可立即出栈。从 4 到 n，任何一个都可以入栈后立即出栈。因此，p3 可能的取值有，1 一 1 个，故选 C。9 【正确答案】 B【试题解析】 求解过程请参见四、21。10 【正确答案】 A11 【正确答案】 A【试题解析】 主函数调用被调用函数，要做三件事：一是将实参和返回地址传给被调用函数保存，二是为被调用函数的参数和局部变量分配工作区，三是将控制权转给被调用函数的入口。调用按后调用先返回，必须使用栈。这里是主函数调用一个递归函数，递归函数调用自身，出口是参数为 0。被调用函数返回主调用函数前也完成三件事：保存被调用函数(过程)的计算结果；释放被调用函数(过程)的工作区
15、，按被调用函数(过程) 保存的返回地址将控制权交给调用函数(过程)。12 【正确答案】 D13 【正确答案】 A,B14 【正确答案】 B二、填空题15 【正确答案】 bc ，栈中尚有 ade16 【正确答案】 栈已存在17 【正确答案】 ni+118 【正确答案】 操作受限(或限定仅在表尾进行插入和删除操作)、后进先出19 【正确答案】 一端，后进先出20 【正确答案】 进栈，退栈三、判断题21 【正确答案】 A22 【正确答案】 A【试题解析】 尾递归的消除就不需用栈。23 【正确答案】 A24 【正确答案】 A25 【正确答案】 A26 【正确答案】 B【试题解析】 有可能相同，不是“一定相同”。27 【正确答案】 A【试题解析】 这个数是前序序列为 1，2，3，n，所能得到的不相似的二叉树的数目。28 【正确答案】 B【试题解析】 时间复杂度无 O(i)这种表示。本题正确答案是 O(1)。29 【正确答案】 A【试题解析】 若 a=n(1in)，说明 n 最后已经入栈，压在它下面的数是按降序排列的。30 【正确答案】 B
