搜索
1、设一棵二叉树的结点结构为(LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。2、在有向图G中，如果r到G中的每个结点都有路径可达，则称结点r为G的根结点。编写一个算法完成下列功能：（1）．建立有向图G的邻接表存储结构；（2）．判断有向图G是否有根，若有，则打印出所有根结点的值。3、设有一个数组中存放了一个无序的关键序列K1、K2、„、Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。51.借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l..h]中。若查找成功，则输出该记录在r数组中的位置及其值，否则显示“notfind”信息。请编写出算法并简要说明算法思想。4、因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。voidLongestPath(BiTreebt)//求二叉树中的第一条最长路径长度{BiTreep=bt,l[],s[];//l,s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点inti，top=0,tag[],longest=0;while(p||top0){while(p){s[++top]=p；tag[top]=0;p=p-Lc;}//沿左分枝向下if(tag[top]==1)//当前结点的右分枝已遍历{if(!s[top]-Lc&&!s[top]-Rc)//只有到叶子结点时，才查看路径长度if(toplongest){for(i=1;i=top;i++)l[i]=s[i];longest=top;top--;}//保留当前最长路径到l栈，记住最高栈顶指针，退栈}elseif(top0){tag[top]=1;p=s[top].Rc;}//沿右子分枝向下}//while(p!=null||top0)}//结束LongestPath5、假设K1，„，Kn是n个关键词，试解答：试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，„，Kn时，用算法建立一棵以LLINK/RLINK链接表示的二叉查找树。6、约瑟夫环问题（Josephus问题）是指编号为1、2、„，n的n（n0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，„，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。#includestdlib.htypedefintdatatype;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(n1)printf(n0);else{/*建表*/head=(linklist)malloc(sizeof(listnode));/*建第一个结点*/head-data=n;r=head;for(i=n-1;i0;i--)/*建立剩余n-1个结点*/{p=(linklist)malloc(sizeof(listnode));p-data=i;p-next=head;head=p;}r-next=head;/*生成循环链表*/jose(head,s,m);/*调用函数*/}}7、矩阵中元素按行和按列都已排序，要求查找时间复杂度为O（m+n），因此不能采用常规的二层循环的查找。可以先从右上角（i=a,j=d）元素与x比较，只有三种情况：一是A[i,j]x，这情况下向j小的方向继续查找；二是A[i,j]x，下步应向i大的方向查找；三是A[i,j]=x，查找成功。否则，若下标已超出范围，则查找失败。voidsearch(datatypeA[][],inta,b,c,d,datatypex)//n*m矩阵A,行下标从a到b,列下标从c到d,本算法查找x是否在矩阵A中.{i=a;j=d;flag=0;//flag是成功查到x的标志while(i=b&&j=c)if(A[i][j]==x){flag=1;break;}elseif(A[i][j]x)j--;elsei++;if(flag)printf(“A[%d][%d]=%d”,i,j,x);//假定x为整型.elseprintf(“矩阵A中无%d元素”，x)；}算法search结束。[算法讨论]算法中查找x的路线从右上角开始，向下（当xA[i,j]）或向左（当xA[i,j]）。向下最多是m，向左最多是n。最佳情况是在右上角比较一次成功，最差是在左下角（A[b,c]），比较m+n次，故算法最差时间复杂度是O(m+n）。8、我们用l代表最长平台的长度，用k指示最长平台在数组b中的起始位置（下标）。用j记住局部平台的起始位置，用i指示扫描b数组的下标，i从0开始，依次和后续元素比较，若局部平台长度（i-j）大于l时，则修改最长平台的长度k（l=i-j）和其在b中的起始位置（k=j），直到b数组结束，l即为所求。voidPlatform(intb[],intN)//求具有N个元素的整型数组b中最长平台的长度。{l=1;k=0;j=0;i=0;while(in-1){while(in-1&&b[i]==b[i+1])i++;if(i-j+1l){l=i-j+1;k=j;}//局部最长平台i++;j=i;}//新平台起点printf(“最长平台长度%d，在b数组中起始下标为%d”，l，k)；}//Platform