返回主页
已有25条笔记
[数据结构 P1508] 已知三叉树 T 中 6 个叶结点的权分别是 2，3，4，5，6，7，T 的带权（外部）路径长度最小是
未通过
已知三叉树 T 中 6 个叶结点的权分别是 2，3，4，5，6，7，T 的带权（外部）路径长度最小是
A. 27
B. 46
C. 54
D. 56
上面问题的答案是：
加入错题本
个人笔记
参考答案：B
答案解析：利用...
用户登录可进行刷题及查看答案
参考答案：B
答案解析：利用三叉树的 6 个叶子结点的权构建最小带权生成树，最小的带权路径长度为(2 + 3) * 3 + (4 + 5) * 2 + (6 + 7) * 1 = 46。
方法一：模拟
T 的带权（外部）路径长度最小是 (2+3)×3+(4+5)×2+(6+7)×1=46 。
本题选B。
方法二：贪心
下面提供秒题解法。
题目要求“最小”，四个选项中A选项最小，直接选A？
如果是这样你就错了， (2+3+4+5+6+7)×1=27 ，A选项表示一棵六叉树。
与 T 为三叉树矛盾，所以我们只能在剩余三个选项中选最小值。
本题选B。
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后提交答案