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

1、证明由二叉树的中序序列和后序序列,也可以唯一确定一棵二叉树。 当 n=1 时,只有一个根结点,由中序序列和后序序列可以确定这棵二叉树。 设当 n=m-1 时结论成立,现证明当 n=m 时结论成立。 设中序序列为 S1, S2, ?, Sm,后序序列是 P1,P2,?, Pm。 因后序序列最后一个元素 Pm 是根, 则在中序序列中可找到与 Pm 相等的结点(设二叉树中各结点互不相同)Si(1≤i≤m),因中 序序列是由中序遍历而得,所以 Si 是根结点,S1,S2,?,Si-1 是左子树的中序序列,而 Si+1,Si+2,?,Sm 是右子树的中序序列。 若 i=1,则 S1 是根,这时二叉树的左子树为空,右子树的结点数是 m-1,则{S2,S3,?,Sm} 和{P1,P2,?,Pm-1}可以唯一确定右子树,从而也确定了二叉树。 若 i=m,则 Sm 是根, 这时二叉树的右子树为空, 左子树的结点数是 m-1, 则{S1, S2, ?, Sm-1} 和{P1,P2,?,Pm-1}唯一确定左子树,从而也确定了二叉树。 最后,当 1<i<m 时,Si 把中序序列分成{S1,S2,?,Si-1}和{Si+1,Si+2,?,Sm}。由于后 序遍历是“左子树—右子树—根结点” ,所以{P1,P2,?,Pi-1}和{Pi,Pi+1,?Pm-1}是二叉树 的左子树和右子树的后序遍历序列。因而由{S1,S2,?,Si-1}和{P1,P2,?,Pi-1} 可唯一确定二叉树的左子树,由{Si+1,Si+2,?,Sm}和 {Pi,Pi+1,?,Pm-1}可唯一确定二叉树的右子树。 2、设 T 是一棵满二叉树,编写一个将 T 的先序遍历序列转换为后序遍历序列的递归算法。 3、给定 n 个村庄之间的交通图,若村庄 i 和 j 之间有道路,则将顶点 i 和 j 用边连接,边上 的 Wij 表示这条道路的长度,现在要从这 n 个村庄中选择一个村庄建一所医院,问这所医院 应建在哪个村庄, 才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算 法,并应用该算法解答如图所示的实例。 (20 分) 4、在有向图 G 中,如果 r 到 G 中的每个结点都有路径可达,则称结点 r 为 G 的根结点。编写 一个算法完成下列功能: (1) .建立有向图 G 的邻接表存储结构; (2) .判断有向图 G 是否有根,若有,则打印出所有根结点的值。 5、设计一个尽可能的高效算法输出单链表的倒数第 K 个元素。 6、我们用 l 代表最长平台的长度,用 k 指示最长平台在数组 b 中的起始位置(下标) 。用 j 记住局部平台的起始位置, 用 i 指示扫描 b 数组的下标, i 从 0 开始, 依次和后续元素比较, 若局部平台长度(i-j)大于 l 时,则修改最长平台的长度 k(l=i-j)和其在 b 中的起始位 置(k=j) ,直到 b 数组结束,l 即为所求。 void Platform (int b[ ], int N) //求具有 N 个元素的整型数组 b 中最长平台的长度。 {l=1;k=0;j=0;i=0; while(i<n-1) {while(i<n-1 && b[i]==b[i+1]) i++; if(i-j+1>l) {l=i-j+1;k=j;} //局部最长平台 i++; j=i; } //新平台起点 printf(“最长平台长度%d,在 b 数组中起始下标为%d” ,l,k); }// Platform 7、给定 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 算法构造其最小生成树(每选取一条边画一个图) 。 8、 将顶点放在两个集合 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); }//是二部图 [算法讨论] 题目给的是连通无向图,若非连通,则算法要修改。


相关文档

2012年西藏自治区数据库入门深入
2012西藏自治区学习数据库深入
2012年西藏自治区学习数据库深入
2012西藏自治区数据库入门入门
2012年西藏自治区数据库入门纲要
2012年西藏自治区数据库入门摘要
2012年西藏自治区数据库入门入门
2012西藏自治区学习数据库入门
2012年西藏自治区数据库入门基础
2012西藏自治区数据库考试含答案入门
电脑版