计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编6(总分：60.00，做题时间：90分钟)一、单项选择题(总题数：14，分数：28.00)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.1B.2C.3 √D.4按元素出队顺序计算栈的容量。
b进栈时栈中有a，b出栈，cd进栈，栈中有acd，dc出栈，ef进栈，栈中有aef,fea出栈，栈空，g进栈后出栈。
所以栈S的容量至少是3。
3.若元素a，b，c，d,e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是( )。
【2010年全国试题1(2)分】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)分】A.b，a，c，d, eB.d,b，a，c，eC.d，b,c，a，e √D.e，c，b，a，da先入队，b和c可在a的任一端入队，选项A、B、D都符合要求，只有选项C不可能出现。
双端队列出队结果的分析可参见四、36。
5.元素a，b，c，d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是( )。
【2011年全国试题2(2)分】A.3B.4 √C.5D.6元素d进栈时，元素a，b，c已在栈中，d出栈后，P可以在a，b，c任一元素的前面进栈并出栈，也可以在元素a后出栈，c，b，a必须依次出栈，所以元素d开头的序列个数是4。
6.已知循环队列存储在一维数组A[0．n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。
若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是( )。
[2011年全国试题3(2)分】A.0，0B.0，n—1 √C.n一1，0D.n一1，n一1队列的入队在队尾，答案中B和D入队(0一1)+1)％n的结果为0，因为要求第1个进入队列的元素存储在A[0]处，且front和rear分别指向队头元素和队尾元素，故选B。
7.已知操作符包括“+”，“-”，“／”，“(’和’)’。
将中缀表达式a+b一a*((c+d)／e-f+g转换为等价的后缀表达式ab+acd+e/f*-g+时，用栈来存放暂时还不能确定运算次序的操作符。
若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是( )。
【2012年全国试题2(2)分】A.5 √B.7C.8D.1 18.一个栈的入栈序列为1，2，3，…，n，其出栈序列是p 1，p 2，p 3，…，p n。
若p 2 =3，则p 3可能取值的个数是( )。
【2013年全国试题2(2)分】A.n一3B.n一2C.n一1 √D.无法确定1，2先于3已入栈，且其中有一个已出栈，另一个在3入栈并出栈后可立即出栈。
从4到n，任何一个都可以入栈后立即出栈。
因此，p3可能的取值有，1一1个，故选C。
9.假设栈初始为空，将中缀表达式a／b+(c*d-e*f)g转换为等价的后缀表达式的过程中，当扫描到f时，栈中的元素依次是( )。
【2014年全国试题2(2)分】A.+(*一B.+(一* √C.／+(*一*D.／+一*求解过程请参见四、21。
10.循环队列存放在一维数组A[0．M-1]中，endl指向队头元素，end2指向队尾元素的后一个位置。
假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素，初始时为空。
下列判断队空和队满的条件中，正确的是( )。
【2014年全国试题3(2)分】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(n’<=0)’0=s(n-1)+n； }void main(){ cout<A.main()一>S(1)一>S(0) √B.S(0)一>S(1)一>main()C.main()一>S(0)一>S(1)D.S(1)一>S(0)一>main()主函数调用被调用函数，要做三件事：一是将实参和返回地址传给被调用函数保存，二是为被调用函数的参数和局部变量分配工作区，三是将控制权转给被调用函数的入口。
调用按后调用先返回，必须使用栈。
这里是主函数调用一个递归函数，递归函数调用自身，出口是参数为0。
被调用函数返回主调用函数前也完成三件事：保存被调用函数(过程)的计算结果；释放被调用函数(过程)的工作区，按被调用函数(过程)保存的返回地址将控制权交给调用函数(过程)。
12.一个栈的输入序列为1，2，3，…，n，若输出序列的第一个元素是n，输出第i(1≤f≤n)个元素是( )。
【电子科技大学2012一、4(2分)】【中山大学1999一、9(1分)】A.不确定B.n-iC.iD.n-i+l √13.设栈的输入序列为1，2，3，…，n；输出序列为p1，p2，…，Pn!若p1=n，则当n≥i≥1时，p t为( )；若存在k>1使p k =n，则当t>k时，P t为( )。
【中国科学技术大学1992八、8(1分)】A.p<subt=i+l √B.p i不确定√C.p i =n-(i-k)14.中缀表达式(A+B)*(C-D)／(E-F*G)的后缀表达式是( )。
【北京邮电大学2005一、2(2分)】A.A+B*C-D／E-F*GB.AB+CD-*EFG*-／√C.AB+C*D-E／-G*D.ABCDEFG+*／-*二、填空题(总题数：6，分数：12.00)15.若某堆栈初始为空，PUSH与POP分别表示对栈进行一次进栈与出栈操作，那么，对于输入序列a，b，c，d，e，经过PUSH，PUSH，POP,PUSH，POP,PUSH，PUSH以后，输出序列是__________。
【北京航空航天大学2006一、3(1分)】__________________________________________________________________________________________正确答案：(正确答案：bc，栈中尚有ade)16.在栈的ADT定义中，除初始化操作外，其他基本操作的初始条件都要求__________。
【北京理工大学2005二、1(2分)】__________________________________________________________________________________________正确答案：(正确答案：栈已存在)17.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p 1，p 2，p 3…，p n，若p 1 =n，则p i为__________。
【北京交通大学2005二、2(2分)】__________________________________________________________________________________________正确答案：(正确答案：n～i+1)18.栈是__________的线性表，其运算遵循__________的原则。
【北京科技大学1997一、3】__________________________________________________________________________________________正确答案：(正确答案：操作受限(或限定仅在表尾进行插入和删除操作)、后进先出)19.堆栈是一种操作受限的线性表，它只能在线性表的__________进行插入和删除操作，对栈的访问是按照__________的原则进行的。
【暨南大学2010二、3(2分)】__________________________________________________________________________________________正确答案：(正确答案：一端，后进先出)20.向栈中压入元素的操作是先__________，后__________。
【暨南大学2011二、5(2分)】__________________________________________________________________________________________正确答案：(正确答案：进栈，退栈)三、判断题(总题数：10，分数：20.00)21.同一组不重复输入序列执行不同的入、出栈组合操作，所得结果也可能相同。
( )【北京邮电大学2005二、3(1分)】A.正确√B.错误22.消除递归不一定需要使用栈。
( )【中科院计算所1998二、2(2分)】【中国科技大学1998二、2(2分)】A.正确√B.错误尾递归的消除就不需用栈。
23.栈是实现过程和函数等子程序所必需的结构。
( )【合肥工业大学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个数顺序(依次)进栈，出栈序列有Cn种，Cn=[1／n+1)]*(2n)!／[(n!)*(n!)]。