当前位置：首页> 2013年河南省数据统计要领

2013年河南省数据统计要领

时间：下载该word文档

1、有一种简单的排序算法，叫做计数排序（countsorting）。这种排序算法对一个待排序的表(用数组表示进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。(1(3分给出适用于计数排序的数据表定义;
(2(7分使用Pascal或C语言编写实现计数排序的算法；(3(4分对于有n个记录的表，关键码比较次数是多少?
(4(3分与简单选择排序相比较，这种方法是否更好?为什么?
2、将顶点放在两个集合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(f
{v=Q[++f];if(s[v]==1jh=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]}//while
return(1;}//是二部图
[算法讨论]题目给的是连通无向图，若非连通，则算法要修改。

阅读全文