首页 > 通信工程师

题目内容（请给出正确答案）

[主观题]

问题描述:给定一棵有向树T,树T中每个顶点u都有一个权w（u),树的每条边（u,v)也都有一个非负边长

问题描述:给定一棵有向树T,树T中每个顶点u都有一个权w(u),树的每条边(u,v)也都有一个非负边长d(u,v).有向树T的每个顶点u可以看作客户,其服务需求量为w(u).

每条边(u,v)的边长d(u,v)可以看作运输费用.如果在顶点u处未设置服务机构,则将顶点u处的服务需求沿有向树的边(u,v)转移到顶点v处服务机构所需付出的服务转移费用为w(u).d(u,v).树根处已设置了服务机构,现在要在树T中增设k处服务机构,使得整棵树T的服务转移费用最小.

算法设计:对于给定的有向树T,计算在树T中增设k处服务机构的最小服务转移费用.数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和k.n表示有向树T的边数,k是要增设的服务机构数.有向树T的顶点编号为0,1,...,n.根结点编号为0.在接下来的n行中,每行有表示有向树T的一条有向边的3个整数.第i+1行的3个整数w_i、v_i、d_i,分别表示编号为i的顶点的权为w_i,相应的有向边为(i,v_i),其边长为di.

结果输出:将计算的最小服务转移费用输出到文件output.txt.

问题描述:给定一棵有向树T,树T中每个顶点u都有一个权w（u),树的每条边（u,v)也都有一个非负边

查看答案

如果结果不匹配，请联系老师获取答案

您可能会需要：

重置密码查看订单联系客服

安装优题宝APP，拍照搜题省时又省心！

更多“问题描述:给定一棵有向树T,树T中每个顶点u都有一个权w（u…”相关的问题

第1题

阅读下列函数说明和C函数，将应填入（n)处的字句写在对应栏内。[说明] Kruskal算法是一种构造图的最

阅读下列函数说明和C函数，将应填入(n)处的字句写在对应栏内。

[说明]

Kruskal算法是一种构造图的最小生成树的方法。设G为一无向连通图，令T是由G的顶点构成的于图，Kmskal算法的基本思想是为T添加适当的边使之成为最小生成树：初始时，T中的点互相不连通；考察G的边集E中的每条边，若它的两个顶点在T中不连通，则将此边添加到T中，同时合并其两顶点所在的连通分量，如此下去，当添加了n-1条边时，T的连通分量个数为1，T便是G的一棵最小生成树。

下面的函数void Kruskal(EdgeType edges[],int n)利用Kruskal算法，构造了有n个顶点的图 edges的最小生成树。其中数组father[]用于记录T中顶点的连通性质：其初值为father[i]=-1 (i=0,1,…,n-1)，表示各个顶点在不同的连通分量上；若有father[i]=j，j＞-1，则顶点i，j连通；函数int Find(int father[],int v)用于返回顶点v所在树形连通分支的根结点。

[函数]

define MAXEDGE 1000

typedef struct

{ int v1;

int v2;

}EdgeType;

void Kruskal(EdgeType edges[],int n)

{ int father[MAXEDGE];

int i,j,vf1,vt2;

for(i=0;i＜n;i+ +) father[i]=-1;

i=0;

j=0;

while(i＜MAXEDGE && j＜(1))

{ vf1=Find(father,edges[i].v1);

vf2=Find(father,edges[i].v2);

if((2))

{(3)=vf1;

(4);

printf("%3d%3d\n",edges[i].v1,edges[i].v2);

}

(5);

}

}

int Find(int father[],int v)

{ int t;

t=v;

while(father[t]＞=0) t=father[t];

return(t);

}

点击查看答案

第2题

设T是正则二叉树，有6个叶子结点，那么树T的高度最多可以是（22)；最小可以是（23)；树T的内结点数是（2

设T是正则二叉树，有6个叶子结点，那么树T的高度最多可以是(22)；最小可以是(23)；树T的内结点数是(24)。如果T又是Huffman最优树，且每个叶子结点的权分别是1，2，3，45，5，6，则最优树T的非叶子结点的权之和是(25)；权为1的叶子结点的高度是(26)。(注：树的根结点高度为1)

A．7

B．6

C．5

D．4

点击查看答案

第3题

DNS的每个域名实际上就是一棵很大的逆向树中的路径，这棵逆向树称为域名空间（)。

DNS的每个域名实际上就是一棵很大的逆向树中的路径，这棵逆向树称为域名空间()。

点击查看答案

第4题

下列关于数据库数据模型的叙述中，哪一个是不正确的？

A.任何一张二维表都表示一个关系

B.层次模型的结构是一棵有向树

C.网状模型中记录之间的联系是通过指针实现的

D.在面向对象模型中每一个对象都有一个惟一的标识

点击查看答案

第5题

设连通图G的顶点数和边数与一立方体相同，即有8个顶点和12条边。任意一棵G的生成树的总边数为A．7B．

设连通图G的顶点数和边数与一立方体相同，即有8个顶点和12条边。任意一棵G的生成树的总边数为

A．7

B．8

C．9

D．10

点击查看答案

第6题

下列命题中为真的是A．任意n阶无向图的最大度≤nB．欧拉回路都是初级回路C．若无向图G是n阶m条边r个

下列命题中为真的是

A．任意n阶无向图的最大度≤n

B．欧拉回路都是初级回路

C．若无向图G是n阶m条边r个面的平面图，则n-m+1=2

D．若T为非平凡的无向树，则T中每条边都是桥

点击查看答案

第7题

下列命题中为真的是A．任意n阶无向图的最大度△≤nB．欧拉回路都是初级回路C．若无向图G是n阶m条边r个

下列命题中为真的是

A．任意n阶无向图的最大度△≤n

B．欧拉回路都是初级回路

C．若无向图G是n阶m条边r个面的平面图，则n-m+1=2

D．若T为非平凡的无向树，则T中每条边都是桥

点击查看答案

第8题

下列命题为真的是A．任意n阶无向图的最大度△≤nB．欧拉回路都是初级回路C．若无向图G是n阶m条边r个

下列命题为真的是

A．任意n阶无向图的最大度△≤n

B．欧拉回路都是初级回路

C．若无向图G是n阶m条边r个面的平面图，则n-m+r=2

D．若T为非平凡的无向树，则T中每条边都是桥

点击查看答案

第9题

设树T的度为4，其中度为1，2，3，4的节点个数分别为4，2，1，1。则T中叶子节点数为()。

A.8

B.7

C.6

D.5

点击查看答案

第10题

在一棵度为3的树中，若有2个度为3的结点，有1个度为2的结点，则有______个度为0的结点。

A.4

B.5

C.6

D.7

点击查看答案

第11题

设树T的度为4，其中度为1，2，3，4的节点个数分别为4，2，1，1，则T中的叶子节点数为______。

A.8

B.7

C.6

D.5

点击查看答案

长沙正则教育科技有限公司版权所有 ©2024

湘ICP备20014704号-1 营业执照

违法和不良信息举报电话：400-118-7898

举报/反馈/投诉邮箱：deng＃ujigu.com（请将＃替换成@）