伤城文章网 > 韩语学习 > 2013年黑龙江省数据分析入门

2013年黑龙江省数据分析入门


1、 将顶点放在两个集合 V1 和 V2。 对每个顶点, 检查其和邻接点是否在同一个集合中, 如是, 则为非二部图。为此,用整数 1 和 2 表示两个集合。再用一队列结构存放图中访问的顶点。 int BPGraph (AdjMatrix g) //判断以邻接矩阵表示的图 g 是否是二部图。 {int s[]; //顶点向量,元素值表示其属于那个集合(值 1 和 2 表示两个集合) int Q[];//Q 为队列,元素为图的顶点,这里设顶点信息就是顶点编号。 int f=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 放入集合 S1 while(f<r) {v=Q[++f]; if (s[v]==1) jh=2; else jh=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;} //邻接点入队列 else if (s[j]==s[v]) return(0);} //非二部图 }//if (!visited[v]) }//while return(1); }//是二部图 [算法讨论] 题目给的是连通无向图,若非连通,则算法要修改。 2、在有向图 G 中,如果 r 到 G 中的每个结点都有路径可达,则称结点 r 为 G 的根结点。编写 一个算法完成下列功能: (1) .建立有向图 G 的邻接表存储结构; (2) .判断有向图 G 是否有根,若有,则打印出所有根结点的值。 3、 将顶点放在两个集合 V1 和 V2。 对每个顶点, 检查其和邻接点是否在同一个集合中, 如是, 则为非二部图。为此,用整数 1 和 2 表示两个集合。再用一队列结构存放图中访问的顶点。 int BPGraph (AdjMatrix g) //判断以邻接矩阵表示的图 g 是否是二部图。 {int s[]; //顶点向量,元素值表示其属于那个集合(值 1 和 2 表示两个集合) int Q[];//Q 为队列,元素为图的顶点,这里设顶点信息就是顶点编号。 int f=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 放入集合 S1 while(f<r) {v=Q[++f]; if (s[v]==1) jh=2; else jh=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;} //邻接点入队列 else if (s[j]==s[v]) return(0);} //非二部图

}//if (!visited[v]) }//while return(1); }//是二部图 [算法讨论] 题目给的是连通无向图,若非连通,则算法要修改。 4、设有一个数组中存放了一个无序的关键序列 K1、K2、?、Kn。现要求将 Kn 放在将元素排 序后的正确位置上,试编写实现该功能的算法,要求比较关键字的次数不超过 n。 51. 借助于快速排序的算法思想,在一组无序的记录中查找给定关键字值等于 key 的记录。 设此组记录存放于数组 r[l..h]中。若查找成功,则输出该记录在 r 数组中的位置及其值, 否则显示“not find”信息。请编写出算法并简要说明算法思想。


搜索更多“2013年黑龙江省数据分析入门”

网站地图

All rights reserved Powered by 伤城文章网 5xts.com

copyright ©right 2010-2021。
伤城文章网内容来自网络,如有侵犯请联系客服。zhit325@126.com