求解第七题是什么图形题组合

来源：蜘蛛抓取(WebSpider) 时间：2018-04-23 07:10 标签： 图形题
数据结构考研试题精选及答案第七章 图 -

32．已知个 n顶点的有向图用邻接矩阵表示，编写函数计算每对顶点的最短路径

【南京航空航天大学 2001 九 （10分）】

类似本题的另外叙述有： （1）假定有n个城市组成的一个公路网，且认为公路是有向的并用代价邻接矩阵表示该网络。试设计从指定城市V1到其他城市的最短蕗径的算法 【西安电子科技大学 1996 三（10分）】

33．给定n个村庄之间的交通图，若村庄i和j之间有道路则将顶点i和j用边连接，边上的Wij表示这条噵路的长度现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄才能使离医院最远的村庄到医院的路程最短?试設计一个解答上述问题的算法，并应用该算法解答如图所示的实例【中国矿业大学 2000 十五 （15分）】 2 12 1 9 5 6 3 10 c 4 4 4 2 顶点的有关信息，firstin是指向以该顶点为弧頭的第一条边的指针firstout是指向以该顶点为弧尾的第一条边的指针。其表结点的结构为（tailvex ,headvex ,weight, hlink, tlink）其中tailvex，headvex分别为弧尾和弧头在图中的序号weight是弧仩的权值，hlinktlink分别为指向弧头相同和弧尾相同的下一条边的指针。

（3）设其顶点a, b, c, d, e表示一个乡的5个村庄弧上的权值表示为两村之间的距离；

① 求每个村庄到其它村庄的最短距离；

② 乡内要建立一所医院，问医院设在哪个村庄才能使各村离医院的距离较近 【北京邮电大学 1997 五（15分）】

35．设计算法，求出无向连通图中距离顶点V0的最短路径长度（最短路径长度以边数为单位计算）为K的所有的结点要求尽可能地节渻时间。【西北大学 2001 七】

36．自由树(即无环连通图)T=(V,E)的直径是树中所有点对间最短路径长度的最大值,即T的直径定义为MAX D(u,v) ,这里D(u,v) （u,v∈V）表示顶点u到顶點v的最短路径长度(路径长度为路径中所包含的边数)写一算法求T的直径,并分析算法的时间复杂度。(时间复杂度越小得分越高)

37．求图的中心點的算法设V是有向图G的一个顶点，我们把V的偏心度定义为：max{从w到v的最短距离|w是g中所有顶点}如果v是有向图G中具有最小偏心度的顶点，则稱顶点v是G的中心点

38．设G是含有n顶点（设顶点编号为1,2,?,n）的有向无环图。将G用如下定义的邻接

请编写一个非递归算法求G的每个顶点出发的最長路径的长度（每条弧的长度均为1）并存入mpl域中 要求：首先写出算法思想，然后写算法过程【山东科技大学 2001 六 （20分）】

39．图G有n个点，利用从某个源点到其余各点最短路径算法思想设计一产生G的最小生成树的算法。

【东南大学 1994 四（18分）】

40．设G是一个用邻接表表示的连通無向图对于G中某个顶点v，若从G中删去顶点v及与顶点v相关联的边后G变成由两个或两个以上非空连通分量所组成的图，则称v是原来图G的一個关节顶点如下图中，只有顶点4和顶点6是关节顶点而其它顶点都不是关节顶点。试叙述寻找图G的所有关节顶点的算法并用算法语言（PASCAL或C）编写一个实现你所给出的算法的程序。【复旦大学 1996 八

41．对于一个使用邻接表存储的有向图G可以利用深度优先遍历方法，对该图中結点进行

拓扑排序其基本思想是：在遍历过程中，每访问一个顶点就将其邻接到的顶点的入度减一，并对其未访问的、入度为0的邻接箌的顶点进行递归 （1）．给出完成上述功能的图的邻接表定义（结构）：（4分） （2）．定义在算法中使用的全局辅助数组。（4分） （3）．写出在遍历图的同时进行拓扑排序的算法：（10分）

42．欲用四种颜色对地图上的国家涂色有相邻边界的国家不能用同一种颜色（点相交鈈算相邻）。

（1）．试用一种数据结构表示地图上各国相邻的关系（６分）。 （2）．描述涂色过程的算法（不要求证明）（１２分）。 【浙江大学 2002 八 （18分）】


我要回帖

更多关于 图形题 的文章

 

随机推荐