给定一棵所有边的长度均为整数的树,现要求延长其中某些边,使得从根到任意节点的路径长度相等。
Joseph Kruskal于1956年提出了构造极小支撑树的另一算法:
将每个顶点视作一棵树,并将所有边按权重非降排序;
依次考查各边,只要其端点分属不同的树,则引入该边,并将端点所分别归属的树合二为一;
如此迭代,直至累计已引入n-1条边时,即得到一棵极小支撑树。
试证明:
a)算法过程中所引入的每一条边,都是某一割的极短跨越边(因此亦必属于某棵极小支撑树);
b)算法过程中的任一时刻,由已引入的边所构成的森林,必是某棵极小支撑树的子图;
圆排列问题描述如下:给定n个大小不等的圆,现要将这n个圆排进一个矩形框中,且要求各圆与矩形框的底边相切.圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列.例如,当n=3,且所给的3个圆的半径分别为1、1、2时,这3个圆的最小长度的圆排列见图5-9,其最小长度为.
算法设计:对于给定的n个圆,计算最小长度圆排列.
数据输入:由文件input.txt提供输入数据.文件的第1行是1个正整数n,表示有n个圆.第2行有n个正数,分别表示n个圆的半径.
结果输出:将计算的最小长度输出到文件output.txt.文件的第1行是最小长度,保留5位小数.
面试题:二叉树中和为某一值的路径
题目:输入一棵二叉树和一个整数,打印出二叉数中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。二叉树结点的定义如下:
S truct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode*m_pLeft;
BinaryTreeNode*m_pRight ;
};
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个整数wi、vi、di分别表示编号为i的顶点的权为wi,相应的有向边为(i,vi),其边长为di.
结果输出:将计算的最小服务转移费用输出到文件output.txt.
5,Jacky : 90
for i in range(10):
print('{:____},{:____}:{:____}'.format(i, name[i], score[i]))请填入最简单的形式。
(),搜索不成功的平均搜索长度是()。
A、21/7
B、28/7
C、15/6
D、16/6
面试题:二叉树的深度
题目一:输入一棵二叉权的根结点,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成的一条路径的长度为树的深度。
二叉树的结点定义如下:
struct BinaryTreeNode
{
int m_nValue ;
BinaryTreeNode* m_pLeft;
BinarvTreeNode* m_pRight ;
}
题目二:输入一棵二叉树的根结点,判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。例如图6.1中的二叉树就是一棵平衡二叉树。