2015年下半年浙江省基础数据深入.doc

2015年下半年浙江省基础数据深入 导读：就爱阅读网友为您分享以下“2015年下半年浙江省基础数据深入”的资讯，希望对您有所帮助，感谢您对92的支持! 1、题目中要求矩阵两行元素的平均值按递增顺序排序，由于每行元素个数相等，按平均值排列与按每行元素之和排列是一个意思。所以应先求出各行元素之和，放入一维数组中，然后选择一种排序方法，对该数组进行排序，注意在排序时若有元素移动，则与之相应的行中各元素也必须做相应变动。void Translation（float *matrix，int n）//本算法对n×n的矩阵matrix，通过行变换，使其各行元素的平均值按递增排列。{int i,j,k,l；float sum，min； //sum暂存各行元素之和 float *p, *pi, *pk;for(i=0; ilt;n; i++){sum=0.0; pk=matrix+i*n; //pk指向矩阵各行第1个元素.for (j=0; jlt;n; j++){sum+=*(pk); pk++;} //求一行元素之和.*(p+i)=sum; //将一行元素之和存入一维数组.}//for ifor(i=0; ilt;n-1; i++) //用选择法对数组p进行排序{min=*(p+i); k=i; //初始设第i行元素之和最小.for(j=i+1;jlt;n;j++) if(p[j]lt;min) {k=j; min=p[j];} //记新的最小值及行号.if(i!=k) //若最小行不是当前行,要进行交换(行元素及行元素之和){pk=matrix+n*k; //pk指向第k行第1个元素.pi=matrix+n*i; //pi指向第i行第1个元素.for(j=0;jlt;n;j++) //交换两行中对应元素.{sum=*(pk+j); *(pk+j)=*(pi+j); *(pi+j)=sum;}sum=p[i]; p[i]=p[k]; p[k]=sum; //交换一维数组中元素之和.}//if}//for ifree(p); //释放p数组.}// Translation[算法分析] 算法中使用选择法排序,比较次数较多,但数据交换(移动)较少.若用其它排序方法,虽可减少比较次数,但数据移动会增多.算法时间复杂度为O(n2).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;ilt;=n;i++)if(g[v][i]!=0 amp;amp; visited[i]==1 ) //若存在边（v,i），且顶点i的状态为1。{printf(“%d”,v);if(i==start) printf(“\n”); else Print(i,start);break;}//if}//Printvoid dfs(int v){visited[v]=1;for(j=1;jlt;=n;j++ ) if (g[v][j]!=0) //存在边(v,j)if (visited[j]!=1) {if (!visited[j]) dfs(j); }//ifelse {cycle=1; Print(j,j);}visited[v]=2;}//dfsvoid find_cycle() //判断是否有回路，有则输出邻接矩阵。visited数组为全局变量。{for (i=1;ilt;=n;i++) visited[i]=0;for (i=1;ilt;=n;i++ ) if (!visited[i]) dfs(i);}//find_cycle3、 将顶点放在两个集合V1和V2。对每个顶点，检查其和邻接点是否在同一个集合中，如是，则为非二部图。为此，用整数1和2表示两个集合。再用