XX青海省C入门

XX青海省C入门 1、编写一个过程，对一个nn矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。 2、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。 （注图中不存在顶点到自己的弧）有向图判断回路要比无向图复杂。 利用深度优先遍历，将顶点分成三类未访问；已访问但其邻接点未访问完;已访问且其邻接点已访问完。 下面用0，1，2表示这三种状态。 前面已提到，若dfs（v）结束前出现顶点u到v的回边，则图中必有包含顶点v和u的回路。 对应程序中v的状态为1，而u是正访问的顶点，若我们找出u的下一邻接点的状态为1，就可以输出回路了。 void Print(int v,int start)/输出从顶点start开始的回路。 for(i=1;i=n;i+)if(gvi!=0&visitedi=1)/若存在边（v,i），且顶点i的状态为1。 printf(“%d”,v);if(i=start)printf(“n”);else Print(i,start);break;/if/Print voiddfs(int v)visitedv=1;for(j=1;j=n;j+)if(gvj!=0)/存在边(v,j)if(visitedj!=1)if(!visitedj)dfs(j);/if elsecycle=1;Print(j,j);visitedv=2;/dfs voidfind_cycle()/判断是否有回路，有则输出邻接矩阵。 visited数组为全局变量。 for(i=1;i=n;i+)visitedi=0;for(i=1;i=n;i+)if(!visitedi)dfs(i);/find_cycle 3、本题要求建立有序的循环链表。 从头到尾扫描数组A，取出Ai（0next=h;/形成空循环链表for(i=0;inext;while(p!=h&p-datanext;/查找Ai的插入位置if(p=h|p-data!=Ai)/重复数据不再输入s=(LinkedList)malloc(sizeof(LNode);s-data=Ai;pre-next=s;s-next=p;/将结点s链入链表中/for return(h);算法结束 4、有一种简单的排序算法，叫做计数排序（count sorting）。 这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。 必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。 (1)(3分)给出适用于计数排序的数据表定义; (2)(7分)使用Pascal或C语言编写实现计数排序的算法； (3)(4分)对于有n个记录的表，关键码比较次数是多少? (4)(3分)与简单选择排序相比较，这种方法是否更好?为什么? 5、在有向图G中，如果r到G中的每个结点都有路径可达，则称结点r为G的根结点。 编写一个算法完成下列功能 （1）建立有向图G的邻接表存储结构； （2）判断有向图G是否有根，若有，则打印出所有根结点的值。 6、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。 （20分） 7、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。 29.试找出满足下列条件的二叉树1）先序序列与后序序列相同2）中序序列与后序序列相同3）先序序列与中序序列相同4）中序序列与层次遍历序列相同 8、在有向图G中，如果r到G中的每个结点都有路径可达，则称结点r为G的根结点。 编写一个算法完成下列功能 （1）建立有向图G的邻接表存储结构； （2）判断有向图G是否有根，若有，则打印出所有根结点的值。 9、二路插入排序是将待排关键字序列r1.n中关键字分二路分别按序插入到辅助向量d1.n前半部和后半部（注:向量d可视为循环表），其原则为，先将rl赋给d1，再从r2记录开始分二路插入。 编写实现二路插入排序算法。 10、设一棵二叉树的结点结构为(LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。 11、请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。 二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。 分析你的算法的时、空复杂度。 12、二叉树的层次遍历序列的第一个结点是二叉树的根。 实际上，层次遍历序列中的每个结点都是“局部根”。 确定根后，到二叉树的中序序列中，查到该结点，该结点将二叉树分为“左根右”三部分。 若左、右子树均有，则层次序列根结点的后面应是左右子树的根；若中序序列中只有左子树或只有右子树，则在层次序列的根结点后也只有左子树的根或右子树的根。 这样，定义一个全局变量指针R，指向层次序列待处理元素。 算法中先处理根结点，将根结点和左右子女的信息入队列。 然后，在队列不空的条件下，循环处理二叉树的结点。 队列中元素的数据结构定义如下typedef structint lvl;/层次序列指针，总是指向当前“根结点”在层次序列中的位置int l,h;/中序序列的下上界int f;/层次序列中当前“根结点”的双亲结点的指针int lr;/1双亲的左子树2双亲的右子树qnode;BiTree Creat(datatype in,level,int n)/由二叉树的层次序列leveln和中序序列inn生成二叉树。 n是二叉树的结点数if(ndata=level0;p-lchild=null;p-rchild=null;/填写该结点数据for(i=0;ilchild=null;s.lvl=+R;s.l=i+1;s.h=n-1;s.f=p;s.lr=2;enqueue(Q,s);else if(i=n-1)/根结点无右子树，遍历序列的1n-1是左子树p-rchild=null;s.lvl=+R;s.l=1;s.h=i-1;s.f=p;s.lr=1;enqueue(Q,s);else/根结点有左子树和右子树s.lvl=+R;s.l=0;s.h=i-1;s.f=p;s.lr=1;enqueue(Q,s);/左子树有关信息入队列s.lvl=+R;s.l=i+1;s.h=n-1;s.f=p;s.lr=2;enqueue(Q,s);/右子树有关信息入队列while(!empty(Q)/当队列不空，进行循环，构造二叉树的左右子树s=delqueue(Q);father=s.f;for(i=s.l;idata=levels.lvl;p-lchild=null;p-rchild=null;/填写该结点数据if(s.lr=1)father-lchild=p;else father-rchild=p；/让双亲的子女指针指向该结点if(i=s.l)p-lchild=null;/处理无左子女s.lvl=+R;s.l=i+1;s.f=p;s.lr=2;enqueue(Q,s);else if(i=s.h)p-rchild=null;/处理无右子女s.lvl=+R;s.h=i-1;s.f=p;s.lr=1;enqueue(Q,s);elses.lvl=+R;s.h=i-1;s.f=p;s.lr=1;enqueue(Q,s);/左子树有关信息入队列s.lvl=+R;s.l=i+1;s.f=p;s.lr=2;enqueue(Q,s);/右子树有关信息入队列/结束while(!empty(Q)return(p);/算法结束 13、在有向图G中，如果r到G中的每个结点都有路径可达，则称结点r为G的根结点。 编写一个算法完成下列功能 （1）建立有向图G的邻接表存储结构； （2）判断有向图G是否有根，若有，则打印出所有根结点的值。 14、矩阵中元素按行和按列都已排序，要求查找时间复杂度为O（m+n），因此不能采用常规的二层循环的查找。 可以先从右上角（i=a,j=d）元素与x比较，只有三种情况一是Ai,jx，这情况下向j小的方向继续查找；二是Ai,j 否则，若下标已超出范围，则查找失败。 void search(datatype A,int a,b,c,d,datatype x)/n*m矩阵A,行下标从a到b,列下标从c到d,本算法查找x是否在矩阵A中.i=a;j=d;flag=0;/flag是成功查到x的标志while(i=c)if(Aij=x)flag=1;break;else if(Aijx)j-;else i+;if(flag)printf(“A%d%d=%d”,i,j,x);/假定x为整型.else printf(“矩阵A中无%d元素”，x)；算法search结束。 算法讨论算法中查找x的路线从右