搜索
1、将顶点放在两个集合V1和V2。对每个顶点，检查其和邻接点是否在同一个集合中，如是，则为非二部图。为此，用整数1和2表示两个集合。再用一队列结构存放图中访问的顶点。intBPGraph(AdjMatrixg)//判断以邻接矩阵表示的图g是否是二部图。{ints[];//顶点向量，元素值表示其属于那个集合（值1和2表示两个集合）intQ[];//Q为队列，元素为图的顶点，这里设顶点信息就是顶点编号。intf=0,r,visited[];//f和r分别是队列的头尾指针,visited[]是访问数组for(i=1;i=n;i++){visited[i]=0;s[i]=0;}//初始化，各顶点未确定属于那个集合Q[1]=1;r=1;s[1]=1;//顶点1放入集合S1while(fr){v=Q[++f];if(s[v]==1)jh=2;elsejh=1;//准备v的邻接点的集合号if(!visited[v]){visited[v]=1;//确保对每一个顶点，都要检查与其邻接点不应在一个集合中for(j=1,j=n;j++)if(g[v][j]==1){if(!s[j]){s[j]=jh;Q[++r]=j;}//邻接点入队列elseif(s[j]==s[v])return(0);}//非二部图}//if(!visited[v])}//whilereturn(1);}//是二部图[算法讨论]题目给的是连通无向图，若非连通，则算法要修改。2、设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。3、本题要求建立有序的循环链表。从头到尾扫描数组A，取出A[i]（0=in）,然后到链表中去查找值为A[i]的结点，若查找失败，则插入。LinkedListcreat(ElemTypeA[],intn)//由含n个数据的数组A生成循环链表，要求链表有序并且无值重复结点{LinkedListh;h=(LinkedList)malloc(sizeof(LNode));//申请结点h-next=h;//形成空循环链表for(i=0;in;i++){pre=h;p=h-next;while(p!=h&&p-dataA[i]){pre=p;p=p-next;}//查找A[i]的插入位置if(p==h||p-data!=A[i])//重复数据不再输入{s=(LinkedList)malloc(sizeof(LNode));s-data=A[i];pre-next=s;s-next=p;//将结点s链入链表中}}//forreturn(h);}算法结束4、设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。5、我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。注：圈就是回路。6、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。29.①试找出满足下列条件的二叉树1）先序序列与后序序列相同2）中序序列与后序序列相同3）先序序列与中序序列相同4）中序序列与层次遍历序列相同7、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。（20分）8、两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左右子树是否相似，采用递归算法。intSimilar(BiTreep,q)//判断二叉树p和q是否相似{if(p==null&&q==null)return(1);elseif(!p&&q||p&&!q)return(0);elsereturn(Similar(p-lchild,q-lchild)&&Similar(p-rchild,q-rchild))}//结束Similar9、约瑟夫环问题（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);/*调用函数*/}}10、给出折半查找的递归算法，并给出算法时间复杂度性分析。11、因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。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)}//结束LongestPath12、将顶点放在两个集合V1和V2。对每个顶点，检查其和邻接点是否在同一个集合中，如是，则为非二部图。为此，用整数1和2表示两个集合。再用一队列结构存放图中访问的顶点。intBPGraph(AdjMatrixg)//判断以邻接矩阵表示的图g是否是二部图。{ints[];//顶点向量，元素值表示其属于那个集合（值1和2表示两个集合）intQ[];//Q为队列，元素为图的顶点，这里设顶点信息就是顶点编号。intf=0,r,visited[];//f和r分别是队列的头尾指针,visited[]是访问数组for(i=1;i=n;i++){visited[i]=0;s[i]=0;}//初始化，各顶点未确定属于那个集合Q[1]=1;r=1;s[1]=1;//顶点1放入集合S1while(fr){v=Q[++f];if(s[v]==1)jh=2;elsejh=1;//准备v的邻接点的集合号if(!visited[v]){visited[v]=1;//确保对每一个顶点，都要检查与其邻接点不应在一个集合中for(j=1,j=n;j++)if(g[v][j]==1){if(!s[j]){s[j]=jh;Q[++r]=j;}//邻接点入队列elseif(s[j]==s[v])return(0);}//非二部图}//if(!visited[v])}//whilereturn(1);}//是二部图[算法讨论]题目给的是连通无向图，若非连通，则算法要修改。13、设一棵二叉树的结点结构为(LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。14、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={V1,V2,V1,V3,V1,V4,V2,V5,V3,V5,V3,V6,V4,V6,V5,V7,V6,V7}写出G的拓扑排序的结果。G拓扑排序的结果是：V1、V2、V4、V3、V5、V6、V715、本题应使用深度优先遍历，从主调函数进入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++;//访问的顶点数＋1if(num==n){printf(“%d是有向图的根。\n”,v);num=0;}//ifp=g[v].firstarc;while(p){if(visied[p-adjvex]==0)dfs(p-adjvex);p=p-next;}//whilevisited[v]=0;num--;//恢复顶点v}//dfsvoidJudgeRoot()//判断有向图是否有根，有根则输出之。{staticinti;for(i=1;i=n;i++)//从每个顶点出发，调用dfs()各一次。{num=0;visited[1..n]=0;dfs(i);}}//JudgeRoot算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用g[i].vertex。16、有一种简单的排序算法，叫做计数排序（countsorting）。这种排序算法对一个待排序的表(用数组表示)进行排序