1、计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编 2 及答案解析(总分：64.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.某表达式的前缀形式为：+-*ABCDEF+GH，它的中缀形式为( )。【中国科学技术大学 1992 八、7(1分)】（分数：2.00）A.A B *C-D+EFG+HB.C.A B* C-D+E(F(G+H)D.A B*(C-D) +E/(G+H)2.表达式 a * (b+c)一 d 的后缀表达式是( )。【南京理工大学 2001 一、2(15 分)】（分数：2.00）A.abcd * +一B.abc+ * d-C.abc * +d
2、-D.-+ * abcd3.与中缀表达式 a * b+cd-e 等价的前缀表达式是( )。【华中科技大学 2006 一、5(2 分)】（分数：2.00）A.一+*abcdeB.*+-abcdeC.abcde*+一D.+*ab-cde4.利用栈求表达式的值时，设立操作数栈 OPND，设 OPND 只有两个存储单元，在下列表达式中，不发生上溢的是( )。【四川大学 2005】（分数：2.00）A.A-B*(C-D)B.(A-B)*C-DC.(-B*C)一 DD.(A 一 B)*(C-D)5.有六个元素 6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列?( )【北方交通大学2001
3、 一、3(2 分)】（分数：2.00）A.5 4 3 6 12B.4 5 3 1 2 6C.3 4 6 5 2 1D.2 3 4 1 5 66.设栈的输入序列是 1，2，3，4，则( )不可能是其出栈序列。【中科院计算所 2000 一、10(2 分)】【烟台大学 2007 一、4(2 分)】（分数：2.00）A.1，2，4，3B.2，1，3，4C.1，4，3，2D.4，3，1，2E.3，2，1，47.四个元素 1，2，3，4 依次进栈，出栈次序不可能出现( )种情况。【北京邮电大学 2005 一、1(2 分)】（分数：2.00）A.1，2，3，4B.4，1，3，2C.1，4，3，2D.4，3，
4、2，18.如进栈序列 1，2，3，4，5。可能得到的出栈序列为( )。【上海交通大学 2005 四、1(2 分)】（分数：2.00）A.1，2，5，3，4B.3，1，2，5，4C.3，2，5，4，1D.1，4，2，3，5E.都不可能9.一个栈的入栈序列为 A，B，C,D，E，则栈的不可能出栈序列是( )。【中南大学 2005 一、2(2 分)】（分数：2.00）A.ABCDEB.EDCBAC.DECBAD.DCEAB10.设 n 个元素进栈序列是 1，2，3，n，其输出序列是 p 1 ，p 2 ，p 3 ，p N ，若 p 1 =3，则p 2 的值为( )。【武汉大学 2006】（分数：2.0
5、0）A.一定是 2B.一定是 1C.不可能是 1D.以上都不对11.某堆栈的输入序列为 a，b，C，d，下面的四个序列中，不可能是它的输出序列的是( )。【北京航空航天大学 2000 一、3(2 分)】【北京邮电大学 1999 一、3(2 分)】（分数：2.00）A.a，c，b，dB.b，C，d，aC.C，d，b，aD.d，c，a，b12.(多选)若已知一个栈的入栈序列是 1，2，3，4，其出栈序列为 p 1 ，p 2 ，p 3 ，p 4 ，则 p 2 ，p 4 可能为 ( )。【华中科技大学 2007 二、16(2 分)】（分数：2.00）A.2、4B.2、1C.4、3D.3、413.输入序
6、列为 ABC，可以变为 CBA 时，经过的栈操作为( )。【中山大学 1999 一、8(1 分)】（分数：2.00）A.push，pop，push，pop，push，popB.push，push，push，pop，Pop，popC.push，push，pop，pop，push，popD.push，pop，push，push，pop，pop14.依次读入数据元素序列a，b，c，d，e，f，g进栈，每进一个元素，机器可要求下一个元素进栈或弹栈，如此进行，则栈空时弹出的元素构成的序列是以下哪些序列? ( )。【哈尔滨工业大学 2000 七(8 分)】（分数：2.00）A.d, e，c，b，g，a)B
7、.f,e，g，d，a，c，b)C.e，d，g，b，C，aD.c，d,b，e，f,a，g)15.4 个圆盘的 Hanoi 塔，总的移动次数为( )。【北京邮电大学 2005 一、3(2 分)】（分数：2.00）A.7B.一 8C.15D.16二、填空题(总题数：7，分数：14.00)16.设有一个空栈，栈顶指针为 1000H(十六进制)，现有输入序列为 1，2，3，4，5，经过PUSH，PUSH，POP，PUSH，POP,PUSH，PUSH 之后，输出序列是_，而栈顶指针值是_H。设栈为顺序栈，每个元素占 4 字节。【西安电子科技大学 1998 二、1(4 分)】（分数：2.00）_17.当两个
8、栈共享一存储区时，栈利用一维数组 stack(1，n)表示，两栈顶指针为 top1与 top【2】，则当栈 1 空时，top1为_，栈 2 空时，top2为_，栈满时为_。【南京理工大学 1997 三、1(3 分)】（分数：2.00）_18.两个栈共享空间时栈满的条件_。【中山大学 1998 一、3(1 分)】【北京邮电大学 2006 一、3(2 分)】（分数：2.00）_19.在进行入栈运算时应先判别栈是否(1)；在进行出栈运算时应先判别栈是否(2)；当栈中元素为 n 个，作进栈运算时发生上溢，则说明该栈的最大容量为(3)。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空
9、间时，应将两栈的(4)分别设在内存空间的两端，这样只有当 (5)时才产生溢出。【山东工业大学 1 994 一、1(5 分)】（分数：2.00）_20.多个栈共存时，最好用_作为存储结构。【南京理工大学 2001 二、7(2 分)】（分数：2.00）_21.有五个数据依次进栈：1，2，3，4，5。在各种出栈的序列中，以 3，4 先出栈的序列有_个。(3 在 4 之前出栈)【上海交通大学 1997 一(6 分)】（分数：2.00）_22.顺序栈用 data1.n存储数据，栈顶指针是 top，则值为 x 的元素入栈的操作是_。【合肥工业大学 2001 三、2(2 分)】（分数：2.00）_三、判断题
10、(总题数：10，分数：20.00)23.堆栈和队列都是操作受限的线性表。栈是插入和删除只能在一端进行的线性表；队列是插入在一端进行，删除在另一端进行的线性表。 ( )【吉林大学 2007 一、10(1 分)】（分数：2.00）A.正确B.错误24.栈和队列均为操作受限的线性表。( )【中国海洋大学 2005 二、9(1 分)】（分数：2.00）A.正确B.错误25.栈和队列都是限制存取点的线性结构。( )【中科院软件所 1999 六、(5)(2 分)】（分数：2.00）A.正确B.错误26.任何一个递归过程都可以转换成非递归过程。( )【上海交通大学 1998 一、3(1 分)】（分数：2.0
11、0）A.正确B.错误27.只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。( )【上海交通大学 1998一、4(1 分)】（分数：2.00）A.正确B.错误28.中缀表达式：(a+b)*d+e/(f+a*d)+c 的后缀表达式为：ab+d*efad+*+c+。( )【南京理工大学 2004二、1(1 分)】（分数：2.00）A.正确B.错误29.在链队列中，即使不设置尾指针也能进行入队操作。( )【中南大学 2005 三、5(2 分)】（分数：2.00）A.正确B.错误30.在链队列中执行出队操作是在队头进行的，故不可能改变尾指针的值。( )【中国科学技术大学2004】（分数
12、：2.00）A.正确B.错误31.队列在程序调用时必不可少，因此递归离不开队列。( )【北京邮电大学 2006 二、3(1 分)】（分数：2.00）A.正确B.错误32.通常使用队列来处理函数或过程的调用。( )【南京航空航天大学 1997 一、5(1 分)】（分数：2.00）A.正确B.错误计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编 2 答案解析(总分：64.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.某表达式的前缀形式为：+-*ABCDEF+GH，它的中缀形式为( )。【中国科学技术大学 1992 八、7(1分)】（分数：2.00）A.A B
13、 *C-D+EFG+HB.C.A B* C-D+E(F(G+H) D.A B*(C-D) +E/(G+H)解析：2.表达式 a * (b+c)一 d 的后缀表达式是( )。【南京理工大学 2001 一、2(15 分)】（分数：2.00）A.abcd * +一B.abc+ * d- C.abc * +d-D.-+ * abcd解析：3.与中缀表达式 a * b+cd-e 等价的前缀表达式是( )。【华中科技大学 2006 一、5(2 分)】（分数：2.00）A.一+*abcde B.*+-abcdeC.abcde*+一D.+*ab-cde解析：4.利用栈求表达式的值时，设立操作数栈 OPND，设
14、 OPND 只有两个存储单元，在下列表达式中，不发生上溢的是( )。【四川大学 2005】（分数：2.00）A.A-B*(C-D)B.(A-B)*C-D C.(-B*C)一 DD.(A 一 B)*(C-D)解析：5.有六个元素 6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列?( )【北方交通大学2001 一、3(2 分)】（分数：2.00）A.5 4 3 6 12B.4 5 3 1 2 6C.3 4 6 5 2 1 D.2 3 4 1 5 6解析：6.设栈的输入序列是 1，2，3，4，则( )不可能是其出栈序列。【中科院计算所 2000 一、10(2 分)】【烟台大学 20
15、07 一、4(2 分)】（分数：2.00）A.1，2，4，3B.2，1，3，4C.1，4，3，2D.4，3，1，2 E.3，2，1，4解析：7.四个元素 1，2，3，4 依次进栈，出栈次序不可能出现( )种情况。【北京邮电大学 2005 一、1(2 分)】（分数：2.00）A.1，2，3，4B.4，1，3，2 C.1，4，3，2D.4，3，2，1解析：8.如进栈序列 1，2，3，4，5。可能得到的出栈序列为( )。【上海交通大学 2005 四、1(2 分)】（分数：2.00）A.1，2，5，3，4B.3，1，2，5，4C.3，2，5，4，1 D.1，4，2，3，5E.都不可能解析：9.一个栈的
16、入栈序列为 A，B，C,D，E，则栈的不可能出栈序列是( )。【中南大学 2005 一、2(2 分)】（分数：2.00）A.ABCDEB.EDCBAC.DECBAD.DCEAB 解析：10.设 n 个元素进栈序列是 1，2，3，n，其输出序列是 p 1 ，p 2 ，p 3 ，p N ，若 p 1 =3，则p 2 的值为( )。【武汉大学 2006】（分数：2.00）A.一定是 2B.一定是 1C.不可能是 1 D.以上都不对解析：11.某堆栈的输入序列为 a，b，C，d，下面的四个序列中，不可能是它的输出序列的是( )。【北京航空航天大学 2000 一、3(2 分)】【北京邮电大学 1999
17、一、3(2 分)】（分数：2.00）A.a，c，b，dB.b，C，d，aC.C，d，b，aD.d，c，a，b 解析：12.(多选)若已知一个栈的入栈序列是 1，2，3，4，其出栈序列为 p 1 ，p 2 ，p 3 ，p 4 ，则 p 2 ，p 4 可能为 ( )。【华中科技大学 2007 二、16(2 分)】（分数：2.00）A.2、4 B.2、1 C.4、3D.3、4 解析：解析：若 p2 为 4，说明在 4 入栈前，1，2，3 已经进栈，且有一个已经出栈，3 不可能最后出栈，因此 C 是得不到的，其余 3 个答案均有可能。13.输入序列为 ABC，可以变为 CBA 时，经过的栈操作为( )
18、。【中山大学 1999 一、8(1 分)】（分数：2.00）A.push，pop，push，pop，push，popB.push，push，push，pop，Pop，pop C.push，push，pop，pop，push，popD.push，pop，push，push，pop，pop解析：14.依次读入数据元素序列a，b，c，d，e，f，g进栈，每进一个元素，机器可要求下一个元素进栈或弹栈，如此进行，则栈空时弹出的元素构成的序列是以下哪些序列? ( )。【哈尔滨工业大学 2000 七(8 分)】（分数：2.00）A.d, e，c，b，g，a) B.f,e，g，d，a，c，b)C.e，d，g，
19、b，C，aD.c，d,b，e，f,a，g) 解析：15.4 个圆盘的 Hanoi 塔，总的移动次数为( )。【北京邮电大学 2005 一、3(2 分)】（分数：2.00）A.7B.一 8C.15 D.16解析：解析：n 个圆盘的 Hanoi 塔总的移动次数是 2 n 一 1。公式推导参见四、17。二、填空题(总题数：7，分数：14.00)16.设有一个空栈，栈顶指针为 1000H(十六进制)，现有输入序列为 1，2，3，4，5，经过PUSH，PUSH，POP，PUSH，POP,PUSH，PUSH 之后，输出序列是_，而栈顶指针值是_H。设栈为顺序栈，每个元素占 4 字节。【西安电子科技大学 1
20、998 二、1(4 分)】（分数：2.00）_正确答案：(正确答案：2，3，100C)解析：17.当两个栈共享一存储区时，栈利用一维数组 stack(1，n)表示，两栈顶指针为 top1与 top【2】，则当栈 1 空时，top1为_，栈 2 空时，top2为_，栈满时为_。【南京理工大学 1997 三、1(3 分)】（分数：2.00）_正确答案：(正确答案：0、n+1、top1+1=top2)解析：18.两个栈共享空间时栈满的条件_。【中山大学 1998 一、3(1 分)】【北京邮电大学 2006 一、3(2 分)】（分数：2.00）_正确答案：(正确答案：两栈顶指针值相减的绝对值为 1(或
21、两栈顶指针相邻)解析：19.在进行入栈运算时应先判别栈是否(1)；在进行出栈运算时应先判别栈是否(2)；当栈中元素为 n 个，作进栈运算时发生上溢，则说明该栈的最大容量为(3)。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的(4)分别设在内存空间的两端，这样只有当 (5)时才产生溢出。【山东工业大学 1 994 一、1(5 分)】（分数：2.00）_正确答案：(正确答案：(1)满 (2)空 (3)n (4)栈底 (5)两栈顶指针相邻(即值之差的绝对值为 1)解析：20.多个栈共存时，最好用_作为存储结构。【南京理工大学 2001 二、7(2 分)】（分数：
22、2.00）_正确答案：(正确答案：链式存储结构)解析：21.有五个数据依次进栈：1，2，3，4，5。在各种出栈的序列中，以 3，4 先出栈的序列有_个。(3 在 4 之前出栈)【上海交通大学 1997 一(6 分)】（分数：2.00）_正确答案：(正确答案：3(分别是：34521，34251，34215)解析：22.顺序栈用 data1.n存储数据，栈顶指针是 top，则值为 x 的元素入栈的操作是_。【合肥工业大学 2001 三、2(2 分)】（分数：2.00）_正确答案：(正确答案：if(top!=n)data+top=x；)解析：三、判断题(总题数：10，分数：20.00)23.堆栈和队
23、列都是操作受限的线性表。栈是插入和删除只能在一端进行的线性表；队列是插入在一端进行，删除在另一端进行的线性表。 ( )【吉林大学 2007 一、10(1 分)】（分数：2.00）A.正确 B.错误解析：24.栈和队列均为操作受限的线性表。( )【中国海洋大学 2005 二、9(1 分)】（分数：2.00）A.正确 B.错误解析：25.栈和队列都是限制存取点的线性结构。( )【中科院软件所 1999 六、(5)(2 分)】（分数：2.00）A.正确 B.错误解析：26.任何一个递归过程都可以转换成非递归过程。( )【上海交通大学 1998 一、3(1 分)】（分数：2.00）A.正确 B.错误解
24、析：27.只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。( )【上海交通大学 1998一、4(1 分)】（分数：2.00）A.正确B.错误 解析：28.中缀表达式：(a+b)*d+e/(f+a*d)+c 的后缀表达式为：ab+d*efad+*+c+。( )【南京理工大学 2004二、1(1 分)】（分数：2.00）A.正确B.错误 解析：29.在链队列中，即使不设置尾指针也能进行入队操作。( )【中南大学 2005 三、5(2 分)】（分数：2.00）A.正确 B.错误解析：解析：从头指针开始，可以查找到队尾，在队尾进行入队。30.在链队列中执行出队操作是在队头进行的，故不可能改变尾指针的值。( )【中国科学技术大学2004】（分数：2.00）A.正确B.错误 解析：解析：若队列中只有一个元素，出队时就会改变尾指针的值。31.队列在程序调用时必不可少，因此递归离不开队列。( )【北京邮电大学 2006 二、3(1 分)】（分数：2.00）A.正确B.错误 解析：32.通常使用队列来处理函数或过程的调用。( )【南京航空航天大学 1997 一、5(1 分)】（分数：2.00）A.正确B.错误 解析：
