Given six weights 4, 15, 25, 5, 8, 16, construct a 2-tree (extended binary tree) with minimum weighted path length. 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. Weighted path length = sum of internal nodes = 9 + 17 + 31 + 42 + 73 = 172.More Data Structures and Algorithms questions
- Suppose we store n keys in a hash table of size m = n² using a hash function h chosen randomly from a universal class of hash functions. Th…
- Which of the following rotations are correctly explained in the context of an AVL tree? A. LL rotation: the new node is inserted in the lef…
- In the context of Hamiltonian problems, which of the following are correct? A. The Hamiltonian cycle problem is NP-complete. B. If G is an…
- For matrix multiplication using the simple divide-and-conquer algorithm: A. The running time is T(n) = Θ(n³) B. The running time is T(n) =…
- Match List I with List IIList I List II A. Linear Program I. Prim's Algorithm B. Predicate Logic II. In order C. Tree Traversal III. Simple…
- Match List I with List IIList I List II A. 8-Queens problem I. Divide and conquer B. Closest pair of points II. Dynamic Programming C. Stri…