当前位置：首页> 2011年吉林省数据理论加强

2011年吉林省数据理论加强

时间：下载该word文档

1、二部图（bipartitegraph）G=（V，E）是一个能将其结点集V分为两不相交子集V1和V2=V-V1的无向图，使得：V1中的任何两个结点在图G中均不相邻，V2中的任何结点在图G中也均不相邻。（1）．请各举一个结点个数为5的二部图和非二部图的例子。（2）．请用C或PASCAL编写一个函数BIPARTITE判断一个连通无向图G是否是二部图，并分析程序的时间复杂度。设G用二维数组A来表示，大小为n*n（n为结点个数）。请在程序中加必要的注释。若有必要可直接利用堆栈或队列操作。【
2、假设K1，„，Kn是n个关键词，试解答：
试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，„，Kn时，用算法建立一棵以LLINK/RLINK链接表示的二叉查找树。
3、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。20分voidHospital(AdjMatrixw,intn
//在以邻接带权矩阵表示的n个村庄中，求医院建在何处，使离医院最远的村庄到医院的路径最短。
{for(k=1;k<=n;k++//求任意两顶点间的最短路径for(i=1;i<=n;i++for(j=1;j<=n;j++
if(w[i][k]+w[k][j]m=MAXINT;//设定m为机器内最大整数。for(i=1;i<=n;i++//求最长路径中最短的一条。{s=0;
for(j=1;j<=n;j++//求从某村庄i（1<=i<=n）到其它村庄的最长路径。if(w[i][j]>ss=w[i][j];
if(s<=m{m=s;k=i;}//在最长路径中，取最短的一条。m记最长路径，k记出发顶点的下标。
Printf(“医院应建在%d村庄，到医院距离为%d\n”,i,m;}//for}//算法结束
对以上实例模拟的过程略。各行中最大数依次是9，9，6，7，9，9。这几个最大数中最小者为6，故医院应建在第三个村庄中,离医院最远的村庄到医院的距离是6。
1、对图1所示的连通网G，请用Prim算法构造其最小生成树（每选取一条边画一个图）。
4、本题应使用深度优先遍历，从主调函数进入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++;//访问的顶点数＋1
if(num==n{printf(“%d是有向图的根。\n”,v;num=0;}//ifp=g[v].firstarc;while(p
{if(visied[p->adjvex]==0dfs(p->adjvex;p=p->next;}//while
visited[v]=0;num--;//恢复顶点v}//dfs
voidJudgeRoot(
//判断有向图是否有根，有根则输出之。{staticinti;
for(i=1;i<=n;i++//从每个顶点出发，调用dfs(各一次。{num=0;visited[1..n]=0;dfs(i;}}//JudgeRoot
算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用g[i].vertex。

阅读全文