1、设一棵二叉树的结点结构为(LLINK,INFO,RLINK,ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。
2、本题应使用深度优先遍历，从主调函数进入dfs(v时，开始记数，若退出dfs(前，已访问完有向图的全部顶点（设为n个），则有向图有根，v为根结点。将n个顶点从1到n编号，各调用一次dfs(过程，就可以求出全部的根结点。题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。建立有向图g的邻接表存储结构参见上面第2题，这里只给出判断有向图是否有根的算法。
intnum=0，visited[]=0//num记访问顶点个数,访问数组visited初始化。constn=用户定义的顶点数;
AdjListg;//用邻接表作存储结构的有向图g。voiddfs(v
{visited[v]=1;num++;//访问的顶点数＋1
if(num==n{printf(“%d是有向图的根。\n”,v;num=0;}//ifp=g[v].firstarc;while(p
{if(visied[p->adjvex]==0dfs(p->adjvex;p=p->next;}//while
visited[v]=0;num--;//恢复顶点v}//dfs
voidJudgeRoot(
//判断有向图是否有根，有根则输出之。{staticinti;
for(i=1;i<=n;i++//从每个顶点出发，调用dfs(各一次。{num=0;visited[1..n]=0;dfs(i;}}//JudgeRoot
算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用g[i].vertex。
3、设有一个数组中存放了一个无序的关键序列K1、K2、„、Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。
51.借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l..h]中。若查找成功，则输出该记录在r数组中的位置及其值，否则显示“notfind”信息。请编写出算法并简要说明算法思想。
4、约瑟夫环问题（Josephus问题）是指编号为1、2、„，n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，„，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。#includetypedefintdatatype;typedefstructnode
{datatypedata;structnode*next;}listnode;
typedeflistnode*linklist;
voidjose(linklisthead,ints,intm{linklistk1,pre,p;intcount=1;pre=NULL;
k1=head;/*k1为报数的起点*/while(count!=s/*找初始报数起点*/{pre=k1;
k1=k1->next;count++;}
while(k1->next!=k1/*当循环链表中的结点个数大于1时*/{p=k1;/*从k1开始报数*/count=1;
while(count!=m/*连续数m个结点*/{pre=p;p=p->next;count++;}
pre->next=p->next;/*输出该结点，并删除该结点*/printf("%4d",p->data;free(p;
k1=pre->next;/*新的报数起点*/}
printf("%4d",k1->data;/*输出最后一个结点*/free(k1;}
main(
{linklisthead,p,r;intn,s,m,i;printf("n=";scanf("%d",&n;printf("s=";scanf("%d",&s;printf("m=",&m;scanf("%d",&m;
if(n<1printf("n<0";else{/*建表*/
head=(linklistmalloc(sizeof(listnode;/*建第一个结点*/head->data=n;
r=head;
for(i=n-1;i>0;i--/*建立剩余n-1个结点*/{p=(linklistmalloc(sizeof(listnode;p->data=i;p->next=head;head=p;}
r->next=head;/*
