题目内容
（请给出正确答案）
问题描述:给定一棵树T,树中每个顶点u都有权值w(u),可以是负数.现在要找到树T的一个连通子图使该子图的权值和最大.
算法设计:对于给定的树T,计算树T的最大连通分支.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数n,表示树T有n个顶点.树T的顶点编号为1,2,...,n.第2行有n个整数,表示n个顶点的权值.接下来的n-1行中,每行有表示树T的一条边的2个整数u和v,表示顶点u与顶点v相连.
结果输出:将计算出的最大连通分支的权值输出到文件output.txt.
如果结果不匹配，请 联系老师 获取答案
更多“问题描述:给定一棵树T,树中每个顶点u都有权值w（u),可以…”相关的问题
算法设计:对于给定的树T,以及障碍物在树T中的分布情况,计算机器人从起点s到终点t的最少移动次数.
数据输入:由文件input.txt提供输入数据.文件的第1行有3个正整数n,s和t,分别表示树T的顶点数,起点s的编号和终点t的编号.
接下来的n行分别对应于树T中编号为0,1,...,n-1的项点.每行的第1个整数h表示顶点的初始状态,当h+1时表示该顶点为空顶点,当h=0时表示该顶点为满顶点,其中已有一个障碍物.第2个数k表示有k个顶点与该项点相连.接下来的k个数是与该顶点相连的顶点编号.
结果输出:将计算出的机器人最少移动次数输出到文件output.txt.如果无法将机器人从起点s移动到终点t,则输出“NoSolution!"
图的m着色问题描述如下:给定无向连通图G和m种不同的颜色.用这些颜色为图G的各顶点着色,每个顶点着一种颜色.如果有一种着色法,使G中每条边的2个顶点着不同颜色,则称这个图是m可着色的.图的m着色问题是对于给定图G和m种颜色,找出所有不同的着色法.
算法设计:对于给定的无向连通图G和m种不同的颜色,计算图的所有不同的着色法.
数据输入:由文件input.txt给出输入数据.第1行有3个正整数n,k和m,表示给定的图G有n个项点和k条边,m种颜色.顶点编号为1,2,...,n接下来的k行中,每行有2个正整数u、v,表示图G的一条边(u,v).
结果输出:将计算的不同的着色方案数输出到文件output.txt.
问题描述:给定一个无向图G=(V.E),设
是G的顶点集.对任意
,若u∈U且v∈V-U,就称(u,1)为关于顶点集U的条割边.顶点集U的所有割边构成图G的一个割.G的最大割是指G中所含边数最多的割.
算法设计:对于给定的无向图G,设计一个优先队列式分支限界法,计算G的最大割.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m,表示给定的图G有n个顶点和m条边,顶点编号为1,2,...,n.接下来的m行中,每行有2个正整数u和y,表示图G的一条边(u,v).
结果输出:将计算的最大割的边数和顶点集U输出到文件output.txt.文件的第1行是最大割的边数;第2行是表示顶点集U的向量x(1≤i≤n),x=0表示顶点i不在项点集U中,x=1表示顶点i在顶点集U中.
程分为若于阶段，每一阶段选取若干条边.算法思路如下：
(1)将每个顶点视为一棵树，图中所有顶点形成一个森林;
(2)为每棵树选取一条边，它是该树与其他树相连的所有边中权值最小的一条边，把该边加入生成树中。如果某棵树选取的边已经被其他树选过，则该边不再选取。
重复以上操作，直到整个森林变成一棵树。
以图8-44所示的图为例，写出执行以上算法的过程。
Joseph Kruskal于1956年提出了构造极小支撑树的另一算法：
将每个顶点视作一棵树，并将所有边按权重非降排序;
依次考查各边，只要其端点分属不同的树，则引入该边，并将端点所分别归属的树合二为一;
如此迭代，直至累计已引入n-1条边时，即得到一棵极小支撑树。
试证明：
a)算法过程中所引入的每一条边，都是某一割的极短跨越边(因此亦必属于某棵极小支撑树);
b)算法过程中的任一时刻，由已引入的边所构成的森林，必是某棵极小支撑树的子图;
A.给定一个游戏搜索树，minimax算法通过每个节点的minimax值来决定最优策略
B.minimax搜索不需要遍历游戏树中所有节点
C.MIN节点希望对方收益最小化
D.MAX节点希望自己收益最大化
设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。
问题描述:给定一条有向直线L及L上的n+1个点
.有向直线L上的每个点x都有权值w(xi),每条有向边
都有一个非负边长
.有向直线L上的每个点x可以看作客户,其服务需求量为w(xi)e每条边
的边长可以看作运输费用.如果在点xi处未设置服务机构,则将点xi处的服务需求沿有向边转移到点xj处服务机构需付出的服务转移费用为
.在点x0处已设置了服务机构,现在要在直线L上增设2处服务机构,使得整体服务转移费用最小.
算法设计:对于给定的有向直线L,计算在直线L上增设2处服务机构的最小服务转移费用.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数m,表示有向直线L上除了点x0还有n个点
接下来的n行中,每行有2个整数.第i+1行的2个整数分别表示
和
.
结果输出:将计算的最小服务转移费用输出到文件output.txt.
A.二叉树中每个结点有两个子结点，而树无此限制，因此二叉树是树的特殊情况
B.当K≥1时高度为K的二叉树至多有2k-l个结点
C.将一棵树转换成二叉树后，根结点没有左子树
D.哈夫曼树是带权路径最短的树，路径上权值较大的结点离根较近
