The minimum number of record movements required to merge five files A (with 10…
1999
The minimum number of record movements required to merge five files A (with 10 records), B (with 20 records), C (with 15 records), D (with 5 records) and E (with 25 records) is:
- A.
165
- B.
90
- C.
75
- D.
65
Attempted by 21 students.
Show answer & explanation
Correct answer: A
Use the optimal merge pattern: repeatedly merge the two smallest files, because each merge cost is the sum of the sizes of the two files being merged.
Initial sizes in increasing order: 5, 10, 15, 20, 25.
1. Merge 5 and 10: cost = 15, new sizes = 15, 15, 20, 25.
2. Merge 15 and 15: cost = 30, new sizes = 20, 25, 30.
3. Merge 20 and 25: cost = 45, new sizes = 30, 45.
4. Merge 30 and 45: cost = 75.
Minimum total record movements = 15 + 30 + 45 + 75 = 165.
Therefore, the correct answer is 165.