计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编5
(总分：80.00，做题时间：90分钟)
一、 单项选择题(总题数：28，分数：56.00)
1.对于栈操作数据的原则是____。【青岛大学2001年】
 A.先进先出
 B.后进先出 √
 C.后进后出
 D.不分顺序
考查栈的概念。栈是一种后进先出的数据结构。
2.在初始为空的堆栈中依次插入元素f，e，d，c，b，a以后，连续进行了三次删除操作，此时栈项元素是____。【北京航空航天大学2002年】
 A.c
 B.d √
 C.b
 D.e
考查栈的基本性质。数据入栈时，先入栈的元素后出栈，只需简单地画图即可看出栈顶元素应是d。
3.六个不同元素依次进栈，能得到____种不同的出栈序列。【北京邮电大学2007年】
 A.42
 B.82
 C.132 √
 D.192
考查栈的基本性质。设有n个不同元素时，有f(n)种出栈序列。若第一个元素是第i个出栈的，则在这个元素之前是编号为2～i的元素出栈，之后是编号为i+1～n的元素出栈。所以第一个元素是第i个出栈对应f(i-1)*f(n—i)种出栈顺序。 f(1)=1 f(2)=2 f(3)=f(2)+f(1)*f(1)+f(2)=5 f(4)=f(3)+f(1)+f(2)十f(2)+f(1)+f(3)=14 f(5)=f(4)+(1)+f(3)+“2)+f(2)+f(3)*(1)+f(4)=42 f(6)=f(5)+(1)+f(4)+f(2)+f(3)+f(3),f(2)+f(4)+f(1)+f(5)=42+14+10+10+14+42=132
4.入栈序列为1，2，3，4，5，则可能得到的出栈序列是____。【上海交通大学2005】
 A.12534
 B.31254
 C.32541 √
 D.14235
考查栈的性质。C的情况是由以下操作得到：1、2、3先入栈，接着3弹栈，2弹栈，然后4、5入栈，5弹栈，4弹栈，最后1弹栈。其他各种情况，都不可能由栈的操作得到。
5.一个栈的输入序列为1，2，3，4，5，则下列序列中不可能是栈的输出序列的是____。【北京理工大学2000年】【北京交通大学2006年】【中南大学2003年】
 A.23415
 B.54132 √
 C.23145
 D.15432
考查栈的性质。考生可通过画图得出正确答案。A是可能的：先是1、2入栈，然后2弹栈，3入栈，3弹栈，4入栈，4弹栈，1弹栈，5入栈，5弹栈。C是可能的：1和2入栈，2弹栈，3入栈，3弹栈，1弹栈，4入栈，4弹栈，5入栈，5弹栈。D是可能的：1入栈，l弹栈，2345入栈，5432弹栈。
6.若已知一个栈的入栈序列为1，2，3，4，其出栈序列为pl，p2，p3，p4，则p2，p4不可能是____。【华中科技大学2007年】
 A.2、4
 B.2、1
 C.4、3 √
 D.3、4
考查栈的性质。对于A，可能的顺序：1入栈，1弹栈，2入栈，2弹栈，3入栈，3弹栈，4入栈，4弹栈。对于B，可能的顺序：1入栈，2入栈，3入栈，3弹栈，2弹栈，4入栈，4弹栈，1弹栈。对于D，可能的顺序：1入栈，1弹栈，2入栈，3入栈，3弹栈，2弹栈，4入栈，4弹栈。C则没有对应的序列。
7.某堆栈的输入序列为a，b，c，d，下面的四个序列中，不可能是它的输出序列的是____。【北京航空航天大学2005年】【北京邮电大学2005年】
 A.a，c，b，d
 B.b，c，d，a
 C.c，d，b，a
 D.d，c，a，b √
考查栈的性质。A可能的序列：a入栈，a出栈，b入栈，c入栈，c出栈，b出栈，d入栈，d出栈。B可能的序列：a、b入栈，b出栈，c入栈，c出栈，d入栈，d出栈，a出栈。C可能的序列：a、b、c入栈，c出栈，d入栈，d出栈，b出栈，a出栈。
8.输入序列为ABC，可以变为CBA时，经过的栈操作为____。【中山大学1999年】
 A.push，pop，push，pOp，push，pop
 B.push，push，push，pOp，pOp，pop √
 C.push，push，pop，pOp，push，pop
 D.push，pOp，push，push，pOp，pop
考查栈的性质。本题属于比较简单的类型。正确的顺序：A入栈，B入栈，c入栈，c弹栈，B弹栈，A弹栈。
9.若栈采用顺序存储方式存储，现两栈共享空间V[1．．m]，top[i]代表第i个栈(j=1，2)栈顶，栈1的底在V【1】，栈2的底在V[m]，则栈满的条件是____。【南京理工大学1999年】
 A.1top[2]top[1]1=0
&p[1]+1=top[2] √
&p[1]+top[2]=m
&p[1]=top[2]
考查栈共享空间的问题。可以通过画图来寻问题的解，当空间V装满后，必有栈1的栈项+1=栈2的栈顶，即top[1]+1=top[2]。
10.向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应该执行____。【北京理工大学2005年】
 A.h．>next=s：
 B.s->next=h；
 C.s．>next=h：h->next=s；
 D.s->next=h一>next．h->next=S； √
考查链栈的插入操作。实际上考查的是在一个链表的头结点后插入一个新结点的操作，因此如果熟练掌握了链表的插入操作，本题是比较容易的。由于该链表是带头结点的，因此h指向的是头结点，所以插入新结点的操作是：s一>lqext=h一>Fiext；h一>rtext=s；
11.执行完下列语句段后，i值为____。【浙江大学2000年】intf(intx){return((x>0)?x*f(x一1)：2)；}inti；i=f(f(1))；
 A.2
 B.4 √
 C.8
 D.无限递归
考查对递归的理解和应用。由题得f(0)=2；f(1)=1*f(0)=2；f(1))=f(2)=2*f(1)=4，即f(1))=4。
12.一个递归算法必须包括____。【武汉大学2000年】
 A.递归部分
 B.终止条件和递归部分 √
 C.迭代部分
 D.终止条件和迭代部分
考查对于递归的理解。一个递归算法分为终止条件和递归部分两个部分。终止条件是递归算法的出口，也就是终止递归的条件。递归部分是一个递推的关系式。
13.将递归算法转变成对应非递归算法时，需要使用____保存中间结果。【华中科技大学2007年】
 A.栈 √
 B.队列
 C.二叉树
 D.单链表
考查递归算法转化为非递归算法的方法。栈的一个重要应用就是实现程序中的递归。
14.表达式a*(b+c)一d的后缀表达式是____。【南京理工大学2001年】
 A.abed*+一
 B.abc+*d— √
 C.abe*+d—
 D.-+*abcd
考查后缀表达式的计算方法。后缀表达式中，每一个计算符号均位于它的两个操作数的直接后面，按这样的方式逐步根据计算的优先级将每个计算式进行变换即可得到后缀表达式。或者还可以采用下面的方法：将表达式构造为一棵树，然后以后序遍历法遍历这棵树即可得到
后缀表达式。同理可得前缀表达式、中缀表达式。比如在此题中，表达式a*(b+c)一d构造的树如图2．1所示。将此树按照后序遍历，即可得到abc+*d一。
15.中缀表达式(A+B)*(C—D)／(E—F*G)的后缀表达式是____。【北京邮电大学2005年】
二叉树的基本性质
 A.A+B*C—D／E～F*G
 B.AB十CD一*EFG*一／ √
 C.AB+C*D—E／F—G+
 D.ABCDEFG+*一／一*
考查由中缀表达式计算后缀表达式的方法。本题给出了中缀表达式，可以通过中缀表达式构建表达式的树结构，然后以后序遍历这棵树，即可得到后缀表达式。
16.中缀表达式A一(B+C／D)}E的后缀形式是____。【北京航空航天大学2007年】
 A.ABCD／+E*一 √
 B.ABC+D／*E—
 C.AB—C+D／E*
 D.ABC一+D／E*
考查由中缀表达式计算后缀表达式的方法。按照上题的方法，可以很快得出答案。
17.设计一个判别表达式中左、右括号是否配对出现的算法，采用____数据结构最佳。【西安电子科技大学1996年】
 A.线性表的顺序存储结构
 B.队列
 C.线性表的链式存储结构
 D.栈 √
考查栈和队列的应用领域。栈通常在数制转换、括号匹配检验、表达式求值、行编辑程序设
计以及迷宫求解等方面有应用。
18.在链队列的出队操作中，修改尾指针的情况发生在____。【广东工业大学2002年】
 A.变成空队列的时候
 B.变成满队列的时候
 C.队列只剩一个元素的时候 √
 D.任何时候
考查链队列的出队操作。链队列是一种特殊的链表。链队列的入队操作是在链表尾部插入一个新的结点，出队操作是在队头删除一个结点。所以只有等到只剩一个元素时，出队操作才会修改尾指针。
19.对于循环队列，正确的是____。【哈尔滨工业大学2007年】
 A.无法判断队列是否为空
 B.无法判断队列是否为满
 C.队列不可能满
 D.以上说法都不对 √
考查循环队列的基本概念。考生可以很容易判断A、B和C三项均不正确。
20.循环队列A[0—m一1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是____。【南京理工大学2001年】【华中科技大学2007年】
 A.(rear—front+m)％m √
&ar—front+l
&ar—front一1
&ar—front
考查循环队列元素数的计算方法。对于循环队列，计算元素数目的公式就是(rear—front+m)
％m。
21.循环队列存储在数组A[0—m]中，则入队时的操作为____。【中山大学1999年】
&ar=rear+1
&ar=(rear+1)mod(m一1)
&ar=(rear+1)modm
&ar=(rear+1)mod(re+1) √
考查循环队列入队操作。循环队列新元素入队时操作算法为rear=(rear+1)modmaxsize，本题中maxsize=m+1。因此入队操作为rear=(rear+1)mod(m+1)。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。