当前位置: 首页 > >

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、#define maxsize 栈空间容量 void InOutS(int s[maxsize]) //s 是元素为整数的栈,本算法进行入栈和退栈操作。 {int top=0; //top 为栈顶指针,定义 top=0 时为栈空。 for(i=1; i<=n; i++) //n 个整数序列作处理。 {scanf(“%d”,&x); //从键盘读入整数序列。 if(x!=-1) // 读入的整数不等于-1 时入栈。 if(top==maxsize-1){printf(“栈满\n”);exit(0);} else s[++top]=x; //x 入栈。 else //读入的整数等于-1 时退栈。 {if(top==0){printf(“栈空\n”);exit(0);} else printf(“出栈元素是%d\n”,s[top--]);} } }//算法结 3、 连通图的生成树包括图中的全部 n 个顶点和足以使图连通的 n-1 条边, 最小生成树是边上 权值之和最小的生成树。故可按权值从大到小对边进行排序,然后从大到小将边删除。每删

除一条当前权值最大的边后,就去测试图是否仍连通,若不再连通,则将该边恢复。若仍连 通,继续向下删;直到剩 n-1 条边为止。 void SpnTree (AdjList g) //用“破圈法”求解带权连通无向图的一棵最小代价生成树。 {typedef struct {int i,j,w}node; //设顶点信息就是顶点编号,权是整型数 node edge[]; scanf( "%d%d",&e,&n) ; //输入边数和顶点数。 for (i=1;i<=e;i++) //输入 e 条边:顶点,权值。 scanf("%d%d%d" ,&edge[i].i ,&edge[i].j ,&edge[i].w); for (i=2;i<=e;i++) //按边上的权值大小,对边进行逆序排序。 {edge[0]=edge[i]; j=i-1; while (edge[j].w<edge[0].w) edge[j+1]=edge[j--]; edge[j+1]=edge[0]; }//for k=1; eg=e; while (eg>=n) //破圈,直到边数 e=n-1. {if (connect(k)) //删除第 k 条边若仍连通。 {edge[k].w=0; eg--; }//测试下一条边 edge[k],权值置 0 表示该边被删除 k++; //下条边 }//while }//算法结束。 connect()是测试图是否连通的函数,可用图的遍历实现, 4 、 (1)p->rchild (2)p->lchild (3)p->lchild (4)ADDQ(Q,p->lchild) (5)ADDQ(Q,p->rchild) 25. (1)t->rchild!=null (2)t->rchild!=null (3)N0++ (4)count(t->lchild) (5)count(t->rchild) 26. .(1)top++ (2) stack[top]=p->rchild (3)top++ (4)stack[top]=p->lchild 27. (1)*ppos // 根结点(2)rpos=ipos (3)rpos–ipos (4)ipos (5)ppos+1




友情链接: