2013年山西省数据统计大纲

2、若第n件物品能放入背包，则问题变为能否再从n-1件物品中选出若干件放入背包（这时背包可放入物品的重量变为s-w[n]）。若第n件物品不能放入背包，则考虑从n-1件物品选若干件放入背包（这时背包可放入物品仍为s）。若最终s=0,则有一解；否则，若s<0或虽然s>0但物品数n<1,则无解。

（1）s-w[n],n-1 //Knap(s-w[n],n-1)=true（2）s,n-1 // Knap←Knap(s,n-1)

3、本题应使用深度优先遍历，从主调函数进入dfs(v)时 ，开始记数，若退出dfs()前，已访问完有向图的全部顶点（设为n个），则有向图有根，v为根结点。将n个顶点从1到n编号，各调用一次dfs()过程，就可以求出全部的根结点。题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。建立有向图g的邻接表存储结构参见上面第2题，这里只给出判断有向图是否有根的算法。 int num=0， visited[]=0 //num记访问顶点个数,访问数组visited初始化。

const n=用户定义的顶点数;

AdjList g ; //用邻接表作存储结构的有向图g。 void dfs(v)

{visited [v]=1; num++; //访问的顶点数＋1

if (num==n) {printf(“%d是有向图的根。\\n”,v);num=0;}//if

p=g[v].firstarc; while (p)

{if (visied[p->adjvex]==0) dfs (p->adjvex);p=p->next;} //while

visited[v]=0; num--; //恢复顶点v}//dfs

void JudgeRoot()

//判断有向图是否有根，有根则输出之。{static int i ;

for (i=1;i<=n;i++ ) //从每个顶点出发，调用dfs()各一次。{num=0; visited[1..n]=0; dfs(i); }　}// JudgeRoot

算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用g[i].vertex。

4、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。20分

void Hospital(AdjMatrix w,int n)

//在以邻接带权矩阵表示的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]>s) s=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算法构造其最小生成树（每选取一条边画一个图）。

5、设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，

要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。