计算机专业基础综合数据结构(栈和队列)历年真题试卷汇编2

计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编2(分：64.00做题时间：分钟)一、单项择(总题数：，数30.00)1.某表达式的前缀式为：+-*ABCDE／，它的中缀式()。【中国学技术大学1992八、7(1分)A.AB.

*C-D+EF／C.AC-D+E／(F／(G+H))D.A+E/(G+H)

√2.表达式a(b+c)一d后缀表达式是()。【南京理工学2001一2(1．)A.abcdB.abc+C.abc

+一d-+d-

√D.-+

abcd3.与中缀表达a

b+c／d-e等价的前缀表达式是()。【中科技大学2006、分)】A.+*ab／cdeB.*+-abcdeC.abcde*+／D.+*ab-／

√4.利用栈求表达式值时，设立操作数栈OPND，设OPND只有两个存储单元，在下列表达式中，不发生上溢的是()。四川大学2005】A.A-B*(C-D)B.(A-B)*C-D

√C.(-B*C)一DD.(A一B)*(C-D)5.有六个元素65，3，，的顺序进栈，问下列哪一个不是合法的出栈序列(【北方交通大学一、3(2)A.543612B.453126C.346521D.234156

√6.设栈的输入序列12，3，4则()可能是其出栈序列。【中科院计算所一、10(2分【烟台大学2007一、分)】A.1，2，4，3B.2，1，3，4C.1，4，3，2D.4，3，1，2E.3，2，1，4

√7.四个元12，，4依次进栈，出栈序不可能出现)种况。【北京邮电大学2005一、分)A.1，2，3，4B.4，1，3，2C.1，4，3，2D.4，3，2，1

√8.如进栈序列1，，4，5可能得到的出栈序列为()。【上海交通大学2005、分)A.1，2，5，3，4B.3，1，2，5，4

C.3，2，5，4，1D.1，4，2，3，5E.不可能

√9.一个栈的入栈序为A，B，，则栈的不可能出栈序列是()。中南大学2005一、2(2)A.ABCDEB.EDCBAC.DECBAD.DCEAB

√10.n个素进栈序列是1，3…，n其输出序列是p

，

，p

，…，

，若p

=3，则p

的值为()。武汉大学2006】A.定是2B.定是1C.可能是1D.上都不对

√11.某栈的输入序列为a，bCd下面的四个序列中，不可能是它的输出序列的是。【北京航空航天大学2000一、分)】【北京邮电大学1999一、3(2分)】A.a，c，b，dB.b，C，d，aC.C，d，b，aD.d，c，a，b

√12.(选)已知一个栈的入栈序列是1，，4，其出序列为p

，p

，p

，

，则p

，p

可能为()【华中科技大学2007、16(2分A.2、4B.2、1C.4、3D.3、4

√√√若p24，说明在4入栈前，2，已经进栈，且有一已经出栈，可能最后出栈，因此C是不到的，其余3个案均有可能。13.输序列为ABC可以变为，经过的栈操作为()【中山大学1999一8(1分)A.pushpop，push，push，popB.pushpush，push，，，C.pushpush，pop，poppush，popD.pushpop，push，push，pop

√14.依读入数据元素序列a，bcd，f，进栈，进一个元素，机器可要求下一个元素进栈或弹栈，如此进行，则栈空时弹出的元素构成的序列是以下哪些序?()。哈尔滨工业大2000七8分A.{d,e，，b，，a)√B.{f,eg，，a，C.{ed，，b，a}D.{cd,b，，f,ag)

√15.4个盘的Hanoi塔，总的移动次数为()。【北京邮电学2005、分)A.7B.一8C.15√D.16n个圆盘的Hanoi塔总的移动次数是

一。公式推导参见17二、填空(总题数：7，分数14.00)16.设一个空栈栈顶指针为1000H(十六进制现有输入序列为12345经过PUSHPUSHPOP，PUSHPOP,PUSH，PUSH之后，输出序列是_________，而栈顶指针值是__________H。栈为顺序栈，每个元素占4字。【西安电子科技大学1998、1(4)

__________________________________________________________________________________________正确答案：(确答案：23100C)17.当个栈共享一存储区时，栈利用一维数组stack(1，表示，两栈顶指针为top[1]与top2，则当栈1空，top[1]为__________，2空时，top[2]为__________栈满时为__________。【南京理工大学1997三、分)】__________________________________________________________________________________________正确答案：(确答案：0n+1、top[1]+1=top[2])18.两栈共享空间时栈满的条件__________。中山大学1998一3(1)【北京邮电大学一、3(2)__________________________________________________________________________________________正确答案：(确答案：两栈顶指针值相减的绝对值为两栈顶指针相邻)19.在行入栈运算时应先判别栈是否1)在进行出栈运算时应先判别栈是否2)当栈中元素为n作进栈运算时发生上溢则说明该栈的最大容量为(3)。为了增加内存空间的利用率和减少溢出的可能性两个栈共享一片连续的空间时，应将两栈的(4)分别设在内存空间的两端，这样只有当时才产生溢出。【山东工业大学1994、1(5分)__________________________________________________________________________________________正确答案：(确答案：(1)(2)(4)栈(5)两栈顶指针相邻值之差的绝对值为20.多栈共存时，最好用__________作存储结构。【南京理工大学2001二7(2分)】__________________________________________________________________________________________正确答案：(确答案：链式存储结构)21.有个数据依次进栈：，3，5在各种出栈的序列中，34先出栈的序列有__________个(3在4前出栈上海交通大学1997一(6分)】__________________________________________________________________________________________正确答案：(确答案：3(分别是：3425134215))22.顺栈用data[1.n]储数据，栈顶指针是top，则为x的元素入栈的操作是__________。【合肥工业大学2001三、分)】__________________________________________________________________________________________正确答案：(确答案：if(top!=n)data[++top]=x；三、判断(总题数：10，分数：20.00)23.堆和队列都是操作受限的线性表插入和删除只能在一端进行的线性表列插入在一端进行，删除在另一端进行的线性表。()【吉林大学一、10(1分A.确B.误

√24.栈队列均为操作受限的线性表。)【国海洋大学2005、9(1)A.确B.误

√25.栈队列都是限制存取点的线性结构。)【中科院软所1999六(5)(2分)】A.确B.误

√26.任一个递归过程都可以转换成非递归过程。)【上交通大学1998一3(1分A.确B.误

√27.只那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈海交通大1998一、4(1)A.确B.误

√28.中表达式(a+b)*d+e/(f+a*d)+c的后缀表达式为ab+d*efad+／*+c+【京理工大学2004二1(1)A.确

B.误

√29.在队列中，即使不设置尾指针也能进行入队操作。)【中南大学2005、分)】A.确B.误

√从头指针开始，可以查找到