广西壮族自治区数据简介高级_广西壮族自治区简介

广西壮族自治区数据简介高级由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“广西壮族自治区简介”。

1、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。20分 void Hospital(AdjMatrix w,int n)//在以邻接带权矩阵表示的n个村庄中，求医院建在何处，使离医院最远的村庄到医院的路径最短。

{for(k=1;ks)s=w[i][j];if(s

Printf(“医院应建在%d村庄，到医院距离为%dn”,i,m);}//for }//算法结束

对以上实例模拟的过程略。各行中最大数依次是9，9，6，7，9，9。这几个最大数中最小者为6，故医院应建在第三个村庄中,离医院最远的村庄到医院的距离是6。

1、对图1所示的连通网G，请用Prim算法构造其最小生成树（每选取一条边画一个图）。

2、后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。本题要找p和q 的最近共同祖先结点r ,不失一般性，设p在q的左边。后序遍历必然先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（即相等）的元素就是结点p 和q的最近公共祖先。

typedef struct {BiTree t;int tag;//tag=0 表示结点的左子女已被访问，tag=1表示结点的右子女已被访问 }stack;stack s[],s1[];//栈，容量够大

BiTree Ancestor(BiTree ROOT,p,q,r)//求二叉树上结点p和q的最近的共同祖先结点r。{top=0;bt=ROOT;while(bt!=null ||top>0){while(bt!=null && bt!=p && bt!=q)//结点入栈 {s[++top].t=bt;s[top].tag=0;bt=bt->lchild;} //沿左分枝向下

if(bt==p)//不失一般性，假定p在q的左侧,遇结点p时，栈中元素均为p的祖先结点 {for(i=1;i

for(i=top;i>0;i--)//；将栈中元素的树结点到s1去匹配 {pp=s[i].t;for(j=top1;j>0;j--)if(s1[j].t==pp){printf(“p 和q的最近共同的祖先已找到”)；return(pp);} ｝

while(top!=0 && s[top].tag==1)top--;//退栈

if(top!=0)｛s[top].tag=1;bt=s[top].t->rchild;｝ //沿右分枝向下遍历 }//结束while(bt!=null ||top>0)return(null);//ｑ、p无公共祖先 ｝//结束Ancestor

3、请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink-rlink法存储。

4、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={，，，，} 写出G的拓扑排序的结果。

G拓扑排序的结果是：V1、V2、V4、V3、V5、V6、V7

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

6、两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左右子树是否相似，采用递归算法。

int Similar(BiTree p,q)//判断二叉树p和q是否相似 {if(p==null && q==null)return(1);else if(!p && q || p &&!q)return(0);else return(Similar(p->lchild,q->lchild)&& Similar(p->rchild,q->rchild))}//结束Similar

7、请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink-rlink法存储。

8、冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。

48.有n个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向起泡排序即相邻两趟排序向相反方向起泡）

9、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。#define MAX 100 typedef struct Node {char info;struct Node *llink, *rlink;}TNODE;char pred[MAX],inod[MAX];main(int argc,int **argv){ TNODE *root;if(argcinfo=(1)_______;for((2)_______;rposllink=restore(ppos+1,(4)_______,k);ptr->rlink=restore((5)_______+k,rpos+1,n-1-k);return ptr;} postorder(TNODE*ptr){ if(ptr=NULL)return;postorder(ptr->llink);postorder(ptr->rlink);printf(“%c”,ptr->info);}