最优二叉树(或哈夫曼树)是指权值为w1，w2，…，wnn个叶结点二叉树中带权路径长度最小二叉树。( )是哈夫曼树(叶结点中数字为其权值)。
- A.见图A
- B.见图B
- C.见图C
- D.见图D
正确答案及解析
正确答案
A
解析
本题考查数据结构基础知识。
哈夫曼树又称为最优二叉树，是一类带权路径长度最短树。
树带权路径长度(WPL)为树中所有叶子结点带权路径长度之和，记为
其中n为带权叶子结点数目，wk为叶子结点权值，lk为根到叶子结点路径长度。
选项A所示二叉树WPL=(2+4)*3+5*2+7*1=35
选项B所示二叉树WPL=(2+4+5+7)*2=36
选项C所示二叉树WPL=(5+7)*3+4*2+2*1=46
选项D所示二叉树WPL=(4+5)*3+7*2+2*1=43
你可能感兴趣的试题
-
- A.V(S2)和P(S4)
- B.P(S2)和V(S4)
- C.P(S2)和P(S4)
- D.V(S2)和V(S4)
- 查看答案
-
- A.V（S1）P（S2）和V（S3）
- B.P（S1）V（S2）和V（S3）
- C.V（S1）V（S2）和V（S3）
- D.P（S1）P（S2）和V（S3）
- 查看答案
-
- A.P（S4）和V（S4）V（S5）
- B.V（S5）和P（S4）P（S5）
- C.V（S3）和V（S4）V（S5）
- D.P（S3）和P（S4）V（P5）
- 查看答案
-
- A.P(S3)和V(S4)V(S5)
- B.V(S3)和P(S4)P(S5)
- C.P(S3)和P(S4)P(S5)
- D.V(S3)和V(S4)V(S5)
- 查看答案
-
- A.P（S2）和P（S4）
- B.P（S2）和V（S4）
- C.V（S2）和P（S4）
- D.V（S2）和V（S4）
- 查看答案