《吉林省数据要领深入》由会员分享，可在线阅读，更多相关《吉林省数据要领深入（13页珍藏版）》请在金锄头文库上搜索。
1、、给定n个村庄之间的交通图，若村庄i和之间有道路,则将顶点i和j用边连接,边上的W表达这条道路的长度,目前要从这个村庄中选择一种村庄建一所医院，问这所医院应建在哪个村庄,才干使离医院最远的村庄到医院的路程最短?试设计一种解答上述问题的算法，并应用该算法解答如图所示的实例。20分void Hospitl(djar w,ntn) /在以邻接带权矩阵表达的n个村庄中,求医院建在何处,使离医院最远的村庄到医院的途径最短。 for(k1;k=n；k) /求任意两顶点间的最短途径 o （i=1;i=n;+) for(j=1；j=n;j+) if (wi+wkjwj) wi=ikwkj; m=MXIT; /
2、设定m为机器内最大整数。 for (1;i=;i） /求最长途径中最短的一条。 s0； r(j1;j=n;j+）/求从某村庄i（1s）sij; if (=m） m=; k=;/在最长途径中,取最短的一条。记最长途径，k记出发顶点的下标。 Print(“医院应建在%d村庄，到医院距离为%n”，i,); /fr算法结束对以上实例模拟的过程略。各行中最大数依次是,9，6，7，9,9。这几种最大数中最小者为6,故医院应建在第三个村庄中,离医院最远的村庄到医院的距离是6。1、对图1所示的连通网G,请用im算法构造其最小生成树(每选用一条边画一种图）。、我们可用“破圈法”求解带权连通无向图的一棵最小代价生
3、成树。所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一环节，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的具体算法，并用程序实现你所给出的算法。注:圈就是回路。3、假设以I和分别表达入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作序列可表达为仅由和O构成的序列,称可以操作的序列为合法序列,否则称为非法序列。（1分） (1)下面所示的序列中哪些是合法的? A. IIIOIOO B. IOOOIO . IIIOO D. IIIOIO (2）通过对(1）的分析，写出一种算法,鉴定所给的操作序列与否合法。若合法,返回tue,否则返回fl(假定被鉴
4、定的操作序列已存入一维数组中)。、假设K1，,Kn是n个核心词，试解答：试用二叉查找树的插入算法建立一棵二叉查找树，即当核心词的插入顺序为1,K2,Kn时,用算法建立一棵以LLINK / RLN 链接表达的二叉查找树。5、 二叉树的层次遍历序列的第一种结点是二叉树的根。事实上,层次遍历序列中的每个结点都是“局部根”。拟定根后,到二叉树的中序序列中，查到该结点,该结点将二叉树分为“左根右”三部分。若左、右子树均有,则层顺序列根结点的背面应是左右子树的根;若中序序列中只有左子树或只有右子树，则在层顺序列的根结点后也只有左子树的根或右子树的根。这样，定义一种全局变量指针R，指向层顺序列待解决元素。算
5、法中先解决根结点，将根结点和左右子女的信息入队列。然后,在队列不空的条件下，循环解决二叉树的结点。队列中元素的数据构造定义如下:typeef suctintlv； /层顺序列指针,总是指向目前“根结点”在层顺序列中的位置itl,h; /中序序列的下上界t ； /层顺序列中目前“根结点”的双亲结点的指针in lr； /1双亲的左子树2双亲的右子树qnode; Bi rea(dataye n,level,nt n）/由二叉树的层顺序列leveln和中序序列in生成二叉树。 n是二叉树的结点数if （ndata=el0； p-lcl=null; pchildnl; /填写该结点数据fo (i=0;
6、ilchld=nll； slvl=+;s.li+1; .h=n-1； s.=p;sl=2; eqeu(Q，s);ese if (=n1) /根结点无右子树,遍历序列的1-1是左子树-rcid=ull; s.lvl+R；.l1; s.=-1;sfp; sl=1； enqee(Q,s）; ese /根结点有左子树和右子树s.ll=+; sl=0； s.h=i1; s.=p;s.l=1;uue(Q,s)；/左子树有关信息入队列.l+R;sl=i+;.=n-1；s.p; s.lr=2；nqueu(Q，s);/右子树有关信息入队列whil （!empy(Q）) /当队列不空,进行循环,构造二叉树的左右子
7、树 s=delqee（Q);fater=s; o (i=s.l;iat=les.lv; -lchild=null; phild=nul； /填写该结点数据 if （l=) fther-lchd=;else fatr-rchild=; /让双亲的子女指针指向该结点 if(i=s.l) pld=nul； /解决无左子女s.vl=+R; s.l=i+1； s.f=p； s.lr=2; nue(Q,s); ele if (i=s.h) -rchi=ull； /解决无右子女 l+R；s.=-1;sf=p； s.l=1;enquee(Q,s); elses.lvl=+;s.h=i1； sf=; .lr=;
8、nqeue(Q,s);/左子树有关信息入队列 s.lvl+R;s.i+1; s.f=p; .lr=; nqueu(Q,s)； 右子树有关信息入队列 /结束wie (!mpt(Q)reurn()；/算法结束6、假设以邻接矩阵作为图的存储构造,编写算法鉴别在给定的有向图中与否存在一种简朴有向回路,若存在，则以顶点序列的方式输出该回路（找到一条即可)。(注:图中不存在顶点到自己的弧）有向图判断回路要比无向图复杂。运用深度优先遍历,将顶点提成三类:未访问；已访问但其邻接点未访问完；已访问且其邻接点已访问完。下面用0,1，表达这三种状态。前面已提到,若fs(v)结束前浮现顶点u到的回边，则图中必有涉及顶
9、点v和u的回路。相应程序中v的状态为1,而是正访问的顶点，若我们找出u的下一邻接点的状态为1,就可以输出回路了。void int(in v,nt strt) /输出从顶点str开始的回路。fr(i=1；i=n;i+) f(gvi!=0 & visitedi=1） /若存在边（,i),且顶点i的状态为。 print(“”,v);if(i=star)rnf(“n”)； else Prit(i,tart);beak;/f /nod ds（int） vsiedv=1；fr(j=1;j=；j+ ) i（!=0)/存在边(,j) i (vistedj!=1） if （！viitedj） dfs();/if
10、 ese ccle=1;Prnt(j,j)； visiev=2;/dfsvid findycle() /判断与否有回路,有则输出邻接矩阵。viste数组为全局变量。 for （i=1;=n;i+） visitedi=; for(i1;i=;i+ ) if(!istedi) df(i);/find_cle7、 连通图的生成树涉及图中的所有n个顶点和足以使图连通的n-1条边,最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条目前权值最大的边后,就去测试图与否仍连通,若不再连通，则将该边恢复。若仍连通，继续向下删;直到剩n条边为止。 vod nree(AdjLit ) /用“破圈法”求解带权连通无向图的一棵最小代价生成树。tedfstrut in i,j,nde;/设顶点信息就是顶点编号，权是整型数 noe ge； scanf( %d,&e,&n) ;/输入边数和顶点数。 fr（i=;i=e;+) /输入e条边：顶点，权值。 scaf(%dd,&dgei.i ,egei.j ,&egeiw); fr (i;=e;+） /按边上的权值大小，对边进行逆序排序。 ee0=dge;j=i-;whi (gj.w=n) /破圈,直到边数en-1. i (connect(k)） /删除第k条边若仍连通。 e.w=0;
