问答题VSAM(虚拟存储存取方法)文件的优点是：动态地__________，不需要文件进行__________，并能较快地__________进行查找。【山东大学2001三、4(2分)】
问答题设T是一棵高度平衡树(又称平衡树)，给定关键词K，如果在T中查找K失败，且查找路径上的任一结点的平衡系数皆为零，试回答用高度平衡树插入算法在T中插入关键词为K的新结点后，树T的高度是否一定增加?并回答为什么。【吉林大学1996四、2(7分)】
问答题试设计一个Heaplnsert(r，key)算法，将关键字key插入到堆R中去，并保证插入后R仍是堆。并分析你的算法的时间复杂性。【哈尔滨工业大学2005五、1(15分)】
问答题当B一树作为文件的索引时，一个结点除了包含关键字和指向孩子结点的指针外，还包含指向文件记录的指针。假设一个结点占用的最大空间被限定为4096字节，每个关键字和每个指针都占2字节。如果采用n阶B树作为文件的索引，则它的最大的阶数应该是多少?【北京理工大学2006十一、5(5分)】
问答题给出字符串’abacabaaad’在KMP算法中的next和nextval数组。【北京邮电大学2000三、1(5分)】
问答题设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W
1
，W
2
，…，W
n
。问能否从这n件物品中选择若干件放入背包，使得放入的重量之和正好是S。设布尔函数Knap(S，n)表示背包问题的解，W(i=1，2，…，n)均为正整数，并已顺序存储在数组W中。请在下列算法的下划线处填空，使其正确求解背包问题。
Knap(S，n)
若S=0
则Knap←true
否则若(S0且n<1)
则Knap←false
否则若Knap(1)，=true
则print(w[n])；Knap←true
否则Knap+-Knap(2) ，
【山东工业大学1996五(10分)1998二、1(4分)】
问答题对给定文件(28，07，39，10，65，14，61，17，50，21)选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。【厦门大学1998七、1(8分)】
问答题将下列树的孩子兄弟链表改为后根遍历全线索链表。【清华大学1994二(10分)】
问答题简述递归过程的关键点。【电子科技大学2005三、4(6分)】
问答题设模式T=“abcabaabc”，求它的next函数的修正值nextval，下面的函数用于求模式T的nextval之值。其中，T[0]用于保存模式T的字符个数，而T[1]，T[2]，……，T[M]依次保存模式T的各个字符。请在该函数中的[A]、[B]处各填入一个赋值表达式，使得数组nextval能够给出模式T的next函数的修正值nextval。 void get—nextval(sstring T，int＆nextval[]) {i=I，nextval[1]=0；j=0； while(i
问答题下面是队列QUEUE和栈STACK的主要操作：
QUEUE:(设定每个队列元素的数据类型为Type)
bool isEmpty(QUEUE Q); //判断队列空否,true为空,false不空
bool getFront(QUEUE Q,Type //通过x返回队头元素的值
void enQueue(QUEUE Q,Type x); //将新元素x插入到队列的队尾
void deQueue(Queue Q); //从队列中退出队头元素
STACK:(设定每个栈元素的数据类型与队列相同,为Type)
void initStack(STACK S); //对新创建的栈初始化,置成空栈
bool isEmpty(STACK S); //判断栈空否,true栈空,false不空
void push(STACK S,Type x); //将新元素X进栈
void pop(STACK S); //栈顶元素退栈
bool getTop(STACK S,Type //通过x返回栈顶元素的值
利用以上栈和队列的操作，编写以下针对队列的函数的实现代码(要求非递归实现)。
问答题设有一组关键字{9，01，23，14，55，20，84，27)，采用哈希函数：H(key)=key mod 7，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di)mod10(di=1
2
，2
2
，3
2
，…)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。【东北大学2002二、2(5分)】
问答题若某非空二叉树采用顺序存储结构，结点的数据信息依次存放于一个一维数组中(假设数组的第一个元素的下标为1)，下标分别为i和j的两个结点处在树中同一层的条件是__________。(i≠j≠1)【北京航空航天大学2006一、6(1分)】
问答题请设计算法将不带头结点的单链表就地逆置。【北京交通大学2001年】
问答题给定(已生成)一个带表头结点的单链表，设head为头指针，结点的结构为(dam，next)，dam为整型元素，next为指针，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。(要求：不允许使用数组作辅助空间。)【华中理工大学2000八、2(13分)】
问答题二叉排序树采用二叉链表存储。写一个算法，删除结点值是X的结点。要求删除该结点后，此树仍然是一棵二叉排序树，并且高度没有增长(注：可不考虑被删除的结点是根的情况)。【中科院软件所1999七、1(8分)】
问答题在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样的说法对吗?举例说明之。
问答题二叉树结点的平衡因子(bf)定义为该结点的左子树高度与右子树高度之差。设二叉树结点结构为：(1child，data，bf，rchild)，1child，rchild是左右儿子指针；data是数据元素；bf是平衡因子，编写递归算法计算二叉树中各个结点的平衡因子。
问答题设有两个栈S1、S2都采用顺序栈方式，并且共享一个存储区[0．．maxsize一1]，为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1、S2有关入栈和出栈的操作算法。【哈尔滨工业大学2001七(12分)】
问答题给出下列所示的三元多项式的广义表表示(分别以X
1
，X
2
，X
3
第一到第三层变元。)P(X
1
X
2
X
3
)=X
1
5
X
2
3
X
3
+2X
1
X
2
X
3
+5X
1
5
X
2
3
X
3
3
+3X
1
X
2
4
X
3
2
+X
2
X
3
+6【华南理工大学2001一、2(4分)】