1、设有一个数组中存放了一个无序的关键序列K1、K2、„、Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。51.借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l..h]中。若查找成功，则输出该记录在r数组中的位置及其值，否则显示“notfind”信息。请编写出算法并简要说明算法思想。
2、数组A和B的元素分别有序，欲将两数组合并到C数组，使C仍有序，应将A和B拷贝到C，只要注意A和B数组指针的使用，以及正确处理一数组读完数据后将另一数组余下元素复制到C中即可。
voidunion(intA[],B[],C[],m,n
//整型数组A和B各有m和n个元素，前者递增有序，后者递减有序，本算法将A和B归并为递增有序的数组C。
{i=0;j=n-1;k=0;//i，j，k分别是数组A,B和C的下标，因用C描述，下标从0开始while(i=0
if(a[i]while(iwhile(j>=0c[k++]=b[j--];
}算法结束
4、要求二叉树按二叉链表形式存储。15分
（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。BiTreeCreat(//建立二叉树的二叉链表形式的存储结构{ElemTypex；BiTreebt;
scanf(“%d”,&x;//本题假定结点数据域为整型if(x==0bt=null;
elseif(x>0
{bt=(BiNode*malloc(sizeof(BiNode;
bt->data=x;bt->lchild=creat(;bt->rchild=creat(;}
elseerror(“输入错误”；return(bt;}//结束BiTree
intJudgeComplete(BiTreebt//判断二叉树是否是完全二叉树,如是，返回1，否则，返回0
{inttag=0;BiTreep=bt,Q[];//Q是队列，元素是二叉树结点指针，容量足够大if(p==nullreturn(1;
QueueInit(Q;QueueIn(Q,p;//初始化队列，根结点指针入队while(!QueueEmpty(Q
{p=QueueOut(Q;//出队
if(p->lchild&&!tagQueueIn(Q,p->lchild;//左子女入队
else{if(p->lchildreturn0;//前边已有结点为空，本结点不空elsetag=1;//首次出现结点为空if(p->rchild&&!tagQueueIn(Q,p->rchild;//右子女入队elseif(p->rchildreturn0;elsetag=1;}//while
return1;}//JudgeComplete
3、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。20分voidHospital(AdjMatrixw,intn
//在以邻接带权矩阵表示的n个村庄中，求医院建在何处，使离医院最远的村庄到医院的路径最短。
{for(k=1;k<=n;k++//求任意两顶点间的最短路径for(i=1;i<=n;i++for(j=1;j<=n;j++
if(w[i][k]+w[k][j]m=MAXINT;//设定m为机器内最大整数。for(i=1;i<=n;i++//求最长路径中最短的一条。
{s=0;
for(j=1;j<=n;j++//求从某村庄i（1<=i<=n）到其它村庄的最长路径。if(w[i][j]>ss=w[i][j];
if(s<=m{m=s;k=i;}//在最长路径中，取最短的一条。m记最长路径，k记出发顶点的下标。
Printf(“医院应建在%d村庄，到医院距离为%d\n”,i,m;}//for
}//算法结束
对以上实例模拟的过程略。各行中最大数依次是9
