发布时间 : 星期四 文章[考研类试卷]计算机专业基础综合数据结构(栈和队列)历年真题试卷汇编6.doc更新完毕开始阅读8e7690802a160b4e767f5acfa1c7aa00b52a9da7
[考研类试卷]计算机专业基础综合数据结构（栈和队列）历年真题试卷
汇编6
一、综合题
1 将两个栈S1和S2存入数组V[1．m]应如何安排最好?请写出栈顶指针top的初始值和判断栈空、栈满的条件是什么?【东南大学1998一、5(6分)】【烟台大学2007四、1(5分)】
2 若有一个一维数组A，它的元素下标从1开始到MAX。要在数组A中建立两个栈共享同一空间，栈S1的栈顶指针为top1，栈S2的栈顶指针为top2，为了最大限度地利用数组A的空间，则应该如何共享?栈满和栈空的条件是什么?【北京理工大学2006十一、3(5分)】
3 设输入序列为a，b，c，d，试写出借助一个栈可得到的两个输出序列和两个不能得到的输出序列。【北京科技大学2001一、4(2分)】
4 试证明：若借助栈由输入序列1，2，…，n得到输出序列为P1，P2，…，Pn(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着Pfki。【上海交通大学1998二(15分)】
5 什么是递归程序?
6 递归程序的优、缺点是什么?
7 递归程序在执行时，应借助于什么来完成?
8 递归程序的入口语句、出口语句一般用什么语句实现?【大连海事大学1996二、4(4分)】
9 试推导出总盘数为n的Hanoi塔的移动次数。【北京邮电大学2001四、3(5分)】
答案见麦多课文库
10 用一个数组S(设大小为MAX)作为两个堆栈的共享空间。请说明共享方法，栈满／栈空的判断条件，并用C或Pascal设计公用的入栈操作push(i，x)，其中i为0或1，用于表示栈号，x为入栈值。【浙江大学1998五、2(7分)】
10 在一个算法中需要建立多个堆栈时可以选用下列三种方案之一，试问：这三种方案之间相比较各有什么优缺点?
11 分别用多个顺序存储空间建立多个独立的堆栈；
12 多个堆栈共享一个顺序存储空间；
13 分别建立多个独立的链接堆栈。【北京航空航天大学1998一、6(4分)】
13 在某程序中，有两个栈共享一个一维数组空间SPACE[N]、SPACE[0]、SPAC[N-1]分别是两个栈的栈底。
14 对栈1、栈2，试分别写出(元素x)入栈的主要语句和出栈的主要语句。
15 对栈1、栈2，试分别写出栈满、栈空的条件。【北京理工大学1999二、2(8分)】
16 用栈实现将中缀表达式8一(3+5)*(5—6／2)转换成后缀表达式，画出栈的变化过程图。【南京航空航天大学2001五(10分)】
17 将表达式a+b)*c+d-(e+g)*h改写成后缀表达式。 【吉林大学2007二、4(3分)】
18 在表达式中，有的运算符要求从右到左计算，如A**B**C的计算次序应为(A**(B**C))，这在由中缀生成后缀的算法中是怎样实现的?(以**为例说明)【东南大学1993一、2(6分)1997一、1(8分)】
19 有字符串次序为3*-y-a/y^2，利用栈，给出将次序改为3y-*ay2^／的操作步骤。(可用X代表扫描该字符串过程中顺序取一个字符进栈的操作，用S代表从栈中取出一个字符加入到新字符串尾的出栈操作。例如，ABC变为BCA的操作步骤为XXSXSS。)【东北大学2001一、4(4分)】
答案见麦多课文库
20 用栈作工具，将十进制数9027转换为八进制数，试列出运算过程和栈中元素的变化过程。【华中科技大学2006四、1(10分)】
21 画出对算术表达式A-B*C／D-E↑F求值时，操作数栈和运算符栈的变化过程。【东南大学2000一、3(6分)】
22 设输入元素为1、2、3、P和A，输入次序为123PA，如图(编者略)。元素经过栈后到达输出序列，当所有元素均到达输出序列后，有哪些序列可以作为高级语言的变量名?【中山大学1997】
23 简述顺序存储队列的假溢出的避免方法及队列满和空的条件。【山东大学2000一、2(4分)】
24 简要叙述循环队列的数据结构，并写出其初始状态、队列空、队列满时的队首指针与队尾指针的值。【南京航空航天大学1995七(5分)】
25 队列可以用循环单链表来实现，故可以只设置一个头指针或者只设置一个尾指针。请你分析对于循环单链表实现的队列，用哪种方案更合适。【北京大学2003五、1(5分)】
26 利用两个栈s1、s2模拟一个队列时，如何用栈的运算实现队列的插入、删除以及判队空运算。请简述这些运算的算法思想。【北京邮电大学1992一、1】【东南大学1999一、1(7分)】
26 如果用一个循环数组q[0一m一1]表示队列时，该队列只有一个队列头指针front，不设队列尾指针rear，而改置计数器count用以记录队列中结点的个数。
27 编写实现队列的三个基本运算：判空、入队、出队。(3分)
28 队列中能容纳元素的最多个数是多少? (1分)【东北大学2002一、1】
答案见麦多课文库