2012西藏自治区数据库入门入门

1、给定 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]<w[i][j]) w[i][j]=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 算法构造其最小生成树(每选 取一条边画一个图) 。

2、给出折半查找的递归算法,并给出算法时间复杂度性分析。

3、假设以 I 和 O 分别表示入栈和出栈操作。栈的初态和终态均为空, 入栈和出栈的操作序列可表示为仅由 I 和 O 组成的序列,称可以操作的序列为合法序列,否 则称为非法序列。 (15 分)

(1)下面所示的序列中哪些是合法的?

A. IOIIOIOO

B. IOOIOIIO

C. IIIOIOIO

D. IIIOOIOO

(2) 通过对 (1) 的分析, 写出一个算法, 判定所给的操作序列是否合法。 若合法, 返回 true, 否则返回 false(假定被判定的操作序列已存入一维数组中) 。

4、假设以 I 和 O 分别表示入栈和出栈操作。栈的初态和终态均为空, 入栈和出栈的操作序列可表示为仅由 I 和 O 组成的序列,称可以操作的序列为合法序列,否 则称为非法序列。 (15 分)

(1)A 和 D 是合法序列,B 和 C 是非法序列。

(2)设被判定的操作序列已存入一维数组 A 中。

int Judge(char A[])

//判断字符数组 A 中的输入输出序列是否是合法序列。 如是, 返回 true, 否则返回 false。

{i=0;

//i 为下标。


相关文档

2012年西藏自治区数据库入门入门
2012年西藏自治区数据库入门基础
2012西藏自治区学习数据库入门
2012西藏自治区数据库入门深入
2012年西藏自治区学习数据库入门
2012西藏自治区数据库入门高级
2012年西藏自治区数据库入门深入
2012西藏自治区数据库入门加强
电脑版