问答题线性表中元素存放在向量A(1，…，n)中，元素是整型数。试写出递归算法求出A中的最大和最小元素。【北京邮电大学1994八(10分)】
问答题对于正整数n，输出其和等于n且满足以下限制条件的所有正整数的和式，组成和式的数字自左至右构成一个非递增的序列，如n=4，程序输出为； 4=4 4=3+1 4=2+2 4=2+1+1 4=1+1+1+1 test是实现该功能的C程序段，请将未完成的部分补足，使之完整。test函数为一递归函数，参数n为被分解和式的数，k为当前的分解深度。算法思想是对n的所有合理的和式分解，将分解出的数(称为和数)存于数组a[]中。当其中一个分解已不再需要进一步进行时，即找到一个解，将存于a[]中的一个完整和式的和数输出。当还需要进一步分解的数及分解时，以要进一步分解的数及分解深度为参数，递归调用test函数。 #define MAXN 100 int a[MAXN]；test(Int n， lnt K] {int i，j； for(j= (1) i j>：1 j j一一) (3分) (a[k]=j； if( (2)) ) (3分) {printf(”％d=％d”? a[0]， a[1])； for(i=2；i<=k；i++) prin七f(“+％d”， a[i])； printf(“＼n”)； } else test((3);k+1)； (4分) } } main()( test(4， 1)； )【中国科学技术大学1997三、1(10分)】
问答题在一棵表示有序集S的二叉搜索树(binary search tree)中，任意一条从根到叶结点的路径将S分为3部分：在该路径左边结点中的元素组成的集合S1；在该路径上的结点中的元素组成的集合S2；在该路径右边结点中的元素组成的集合S3。S=S1∪S2∪S3。若对于任意的a∈S1，b∈S2，c∈S3是否总有a≤b≤c?为什么?【清华大学2000四(10分)】【武汉大学2000三、3】
问答题将表达式a+b)*c+d-(e+g)*h改写成后缀表达式。 【吉林大学2007二、4(3分)】
问答题已知一图如下图所示：(1)写出全部拓扑排序；(2)以V1为源点，以V8为终点，给出所有事件允许发生的最早时间和最晚时间，并给出关键路径；(3)求V1结点到各点的最短距离。【北京邮电大学2000五(15分)】
问答题计算以t为根的二叉树中各结点中的最大元素的值，假设数据类型为float型。
问答题给定n×m矩阵A[a..b，c一d，并设A[i,j]≤A[i，j+1](a≤i≤b，c≤j≤d-1)和A[i,j]≤A[i+1，f] (a≤i≤b一1，c≤j≤d)。设计一算法判定x的值是否在A中，要求时间复杂度为O(m+n)。【东南大学2005四(10分)2001六(13分) 1994三(17分)】【清华大学1998六(10分)】
问答题求解下面有向图的有关问题：(1)判断此有向图是否有强连通分量?若有请画出。(2)画出此有向图的十字链表存储结构；其顶点表结点结构为(data，firstin，firstout)，其中data，是顶点的有关信息；firstin是指向以该顶点为弧头的第一条边的指针；firstout是指向以该顶点为弧尾的第一条边的指针。其表结点的结构为(tailvex，headvex，weight，hlink，tlink)，其中tailvex、headvex分别为弧尾和弧头在图中的序号；weight是弧上的权值，hlink、tlink分别为指向弧头相同和弧尾相同的下一条边的指针。"(3)设其顶点a，b，c，d,e表示一个乡的5个村庄，弧上的权值表示为两村之间的距离。①求每个村庄到其他村庄的最短距离；②乡内要建立一所医院，问医院设在哪个村庄才能使各村离医院的距离较近。【北京邮电大学1997五(15分)】"
问答题如果只想在一个有n个元素的任意序列中得到其中最小的第k(k＜＜n)个元素之前的部分排序序列，那么最好采用什么排序方法?为什么?例如有这样一个序列{57，40，38，11，13，34，48，75，6，19，9，7}，要得到其第4个元素之前的部分有序序列{6，7，9，11}，用所选择的算法实现时，要执行多少次比较?
问答题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返回栈顶元素的值
利用以上栈和队列的操作，编写以下针对队列的函数的实现代码(要求非递归实现)。