1、计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编 6 及答案解析(总分：60.00，做题时间：90 分钟)一、单项选择题(总题数：14，分数：28.00)1.为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( )。【2009 年全国试题 1(2)分】（分数：2.00）A.栈B.队列C.树D.图2.设栈 S 和队列 Q 的初始状态均为空，元素 a，b，c，d,e,j,g=g 依次进入栈 S。若每个元素出栈后立即进入队列 Q，且 7 个元素出队的顺序是 b，d，c，f，e，
2、a，g，则栈 S 的容量至少是( )。【2009 年全国试题 2(2)分】（分数：2.00）A.1B.2C.3D.43.若元素 a，b，c，d,e，f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是( )。 【2010 年全国试题 1(2)分】（分数：2.00）A.d,c，e，b，f,aB.c，b，d,a，e，fC.b，c，a，e，f，dD.a,f，e,d,c，b4.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素 a，b，c，d，e 依次入此队列后再进行出队操作，则不可能得到的出队序列是( )。 【2010 年全国试题 2(2)
3、分】（分数：2.00）A.b，a，c，d, eB.d,b，a，c，eC.d，b,c，a，eD.e，c，b，a，d5.元素 a，b，c，d,e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素 d 开头的序列个数是( )。 【2011 年全国试题 2(2)分】（分数：2.00）A.3B.4C.5D.66.已知循环队列存储在一维数组 A0n-1中，且队列非空时 front 和 rear 分别指向队头元素和队尾元素。若初始时队列为空，且要求第 1 个进入队列的元素存储在 A0处，则初始时 front 和 rear 的值分别是( )。 2011
4、年全国试题 3(2)分】（分数：2.00）A.0，0B.0，n1C.n 一 1，0D.n 一 1，n 一 17.已知操作符包括“+”，“-”，“”，“(和)。将中缀表达式 a+b 一 a*(c+d)e-f+g 转换为等价的后缀表达式 ab+acd+e/f*-g+时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是( )。【2012 年全国试题 2(2)分】（分数：2.00）A.5B.7C.8D.1 18.一个栈的入栈序列为 1，2，3，n，其出栈序列是 p 1 ，p 2 ，p 3 ，p n 。若 p 2 =3，则 p 3 可能取值的个数是
5、( )。【2013 年全国试题 2(2)分】（分数：2.00）A.n 一 3B.n 一 2C.n 一 1D.无法确定9.假设栈初始为空，将中缀表达式 ab+(c*d-e*f)g 转换为等价的后缀表达式的过程中，当扫描到 f 时，栈中的元素依次是( )。【2014 年全国试题 2(2)分】（分数：2.00）A.+(*一B.+(一*C.+(*一*D.+一*10.循环队列存放在一维数组 A0M-1中，endl 指向队头元素，end2 指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳 M-1 个元素，初始时为空。下列判断队空和队满的条件中，正确的是( )。【2014 年全
6、国试题 3(2)分】（分数：2.00）A.队空：end1=end2； 队满：end1=(end2+1)mod MB.队空：end1=end2； 队满：end2=(end1+1)modM-1)C.队空：end2=(end1+1)modM; 队满：end4=(end2+1)modMD.队空：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
7、，若输出序列的第一个元素是 n，输出第 i(1fn)个元素是( )。【电子科技大学 2012 一、4(2 分)】【中山大学 1999 一、9(1 分)】（分数：2.00）A.不确定B.n-iC.iD.n-i+l13.设栈的输入序列为 1，2，3，n；输出序列为 p1，p2，Pn!若 p1=n，则当 ni1 时，p t 为( )；若存在 k1 使 p k =n，则当 tk 时，P t 为( )。【中国科学技术大学 1992 八、8(1 分)】（分数：2.00）A.pa i+1 a n 。( )【中国科学技术大学：1991 一、5(2 分)】（分数：2.00）A.正确B.错误30.设栈采用顺序存储
8、结构，若已有 n 个元素进栈，则出栈算法的时间复杂性为 O(n)。( )【上海海事大学 2005 一、2(2 分)】（分数：2.00）A.正确B.错误计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编 6 答案解析(总分：60.00，做题时间：90 分钟)一、单项选择题(总题数：14，分数：28.00)1.为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( )。【2009 年全国试题 1(2)分】（分数：2.00）A.栈B.队列 C.树D.图解析：2.设栈 S 和队列 Q
9、 的初始状态均为空，元素 a，b，c，d,e,j,g=g 依次进入栈 S。若每个元素出栈后立即进入队列 Q，且 7 个元素出队的顺序是 b，d，c，f，e，a，g，则栈 S 的容量至少是( )。【2009 年全国试题 2(2)分】（分数：2.00）A.1B.2C.3 D.4解析：解析：按元素出队顺序计算栈的容量。b 进栈时栈中有 a，b 出栈，cd 进栈，栈中有 acd，dc 出栈，ef 进栈，栈中有 aef,fea 出栈，栈空，g 进栈后出栈。所以栈 S 的容量至少是 3。3.若元素 a，b，c，d,e，f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出
10、栈序列是( )。 【2010 年全国试题 1(2)分】（分数：2.00）A.d,c，e，b，f,aB.c，b，d,a，e，fC.b，c，a，e，f，dD.a,f，e,d,c，b 解析：4.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素 a，b，c，d，e 依次入此队列后再进行出队操作，则不可能得到的出队序列是( )。 【2010 年全国试题 2(2)分】（分数：2.00）A.b，a，c，d, eB.d,b，a，c，eC.d，b,c，a，e D.e，c，b，a，d解析：解析：a 先入队，b 和 c 可在 a 的任一端入队，选项 A、B、D 都符合要求，只有选项 C 不可能出现
11、。双端队列出队结果的分析可参见四、36。5.元素 a，b，c，d,e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素 d 开头的序列个数是( )。 【2011 年全国试题 2(2)分】（分数：2.00）A.3B.4 C.5D.6解析：解析：元素 d 进栈时，元素 a，b，c 已在栈中，d 出栈后，P 可以在 a，b，c 任一元素的前面进栈并出栈，也可以在元素 a 后出栈，c，b，a 必须依次出栈，所以元素 d 开头的序列个数是 4。6.已知循环队列存储在一维数组 A0n-1中，且队列非空时 front 和 rear 分别指向队头元素和队
12、尾元素。若初始时队列为空，且要求第 1 个进入队列的元素存储在 A0处，则初始时 front 和 rear 的值分别是( )。 2011 年全国试题 3(2)分】（分数：2.00）A.0，0B.0，n1 C.n 一 1，0D.n 一 1，n 一 1解析：解析：队列的入队在队尾，答案中 B 和 D 入队(0 一 1)+1)n 的结果为 0，因为要求第 1 个进入队列的元素存储在 A0处，且 front 和 rear 分别指向队头元素和队尾元素，故选 B。7.已知操作符包括“+”，“-”，“”，“(和)。将中缀表达式 a+b 一 a*(c+d)e-f+g 转换为等价的后缀表达式 ab+acd+e/
13、f*-g+时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是( )。【2012 年全国试题 2(2)分】（分数：2.00）A.5 B.7C.8D.1 1解析：8.一个栈的入栈序列为 1，2，3，n，其出栈序列是 p 1 ，p 2 ，p 3 ，p n 。若 p 2 =3，则 p 3 可能取值的个数是( )。【2013 年全国试题 2(2)分】（分数：2.00）A.n 一 3B.n 一 2C.n 一 1 D.无法确定解析：解析：1，2 先于 3 已入栈，且其中有一个已出栈，另一个在 3 入栈并出栈后可立即出栈。从 4 到n，任何一个都可以入
14、栈后立即出栈。因此，p3 可能的取值有，1 一 1 个，故选 C。9.假设栈初始为空，将中缀表达式 ab+(c*d-e*f)g 转换为等价的后缀表达式的过程中，当扫描到 f 时，栈中的元素依次是( )。【2014 年全国试题 2(2)分】（分数：2.00）A.+(*一B.+(一* C.+(*一*D.+一*解析：解析：求解过程请参见四、21。10.循环队列存放在一维数组 A0M-1中，endl 指向队头元素，end2 指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳 M-1 个元素，初始时为空。下列判断队空和队满的条件中，正确的是( )。【2014 年全国试题 3(
15、2)分】（分数：2.00）A.队空：end1=end2； 队满：end1=(end2+1)mod M B.队空：end1=end2； 队满：end2=(end1+1)modM-1)C.队空：end2=(end1+1)modM; 队满：end4=(end2+1)modMD.队空：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()解析：解析：主函数调用被调用函数，要做三件
16、事：一是将实参和返回地址传给被调用函数保存，二是为被调用函数的参数和局部变量分配工作区，三是将控制权转给被调用函数的入口。调用按后调用先返回，必须使用栈。这里是主函数调用一个递归函数，递归函数调用自身，出口是参数为 0。被调用函数返回主调用函数前也完成三件事：保存被调用函数(过程)的计算结果；释放被调用函数(过程)的工作区，按被调用函数(过程)保存的返回地址将控制权交给调用函数(过程)。12.一个栈的输入序列为 1，2，3，n，若输出序列的第一个元素是 n，输出第 i(1fn)个元素是( )。【电子科技大学 2012 一、4(2 分)】【中山大学 1999 一、9(1 分)】（分数：2.00）
17、A.不确定B.n-iC.iD.n-i+l 解析：13.设栈的输入序列为 1，2，3，n；输出序列为 p1，p2，Pn!若 p1=n，则当 ni1 时，p t 为( )；若存在 k1 使 p k =n，则当 tk 时，P t 为( )。【中国科学技术大学 1992 八、8(1 分)】（分数：2.00）A.pa i+1 a n 。( )【中国科学技术大学：1991 一、5(2 分)】（分数：2.00）A.正确 B.错误解析：解析：若 a=n(1in)，说明 n 最后已经入栈，压在它下面的数是按降序排列的。30.设栈采用顺序存储结构，若已有 n 个元素进栈，则出栈算法的时间复杂性为 O(n)。( )【上海海事大学 2005 一、2(2 分)】（分数：2.00）A.正确B.错误 解析：
