Given six weights 4, 15, 25, 5, 8, 16, construct a 2-tree (binary tree). What is the minimum weighted path length?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. 172
Explanation
Huffman merges: 4 + 5 = 9; 8 + 9 = 17; 15 + 16 = 31; 17 + 25 = 42; 31 + 42 = 73. The weighted path length is the sum of the internal nodes: 9 + 17 + 31 + 42 + 73 = 172.
More Data Structures and Algorithms questions
- Consider: A. The number of labelled binary trees possible with n nodes is (2n)!/(n + 1)!. B. The number of binary search trees possible wit…
- Which of the following are correct about Hamiltonian problems? A. The Hamiltonian cycle problem is NP-complete. B. If G is an undirected bi…
- For matrix multiplication with a simple divide-and-conquer algorithm: A. the running time is T(n) = Θ(n³) B. the running time is T(n) = Θ(n…
- Match List I with List II
- Match List I with List II
- What is the maximum value of items you can carry if maximum weight allowed is 25 with a fractional knapsack?