edited by
14,373 views
35 votes
35 votes

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:

  1. $165$
  2. $90$
  3. $75$
  4. $65$
edited by

4 Answers

Best answer
35 votes
35 votes
Arrange files in increasing order of records:

$\overset{\boxed5}{\text{D}}\quad \overset{\boxed{10}}{\text{A}}\quad\overset{\boxed{15}}{\text{C}}\quad\overset{\boxed{20}}{\text{B}}\quad\overset{\boxed{25}}{\text{E}}$


$\qquad\qquad\qquad\qquad\color{blue}{75}$

$\qquad\qquad\quad\color{blue}{30}\qquad\qquad\qquad\color{blue}{45}$

$\qquad\quad\color{blue}{15}\qquad\overset{\boxed{\text{C}}}{15}\qquad\qquad\overset{\boxed{\text{B}}}{20}\qquad\overset{\boxed{\text{E}}}{25}$

$\quad\overset{\boxed{\text{D}}}{5}\qquad\overset{\boxed{\text{A}}} {10}$

No. of movements $=15+30+45+75=165.$

Correct Answer: $A$
edited by
7 votes
7 votes

No of movements=15+30+45+75=165

3 votes
3 votes

Try to implement it like Huffman coding.

Sorted files 5,10,15,20,25

1) merge min two -- 15,15,20,25 | merges=5+10=15

2) next two -- 30,20,25 -> reordering -- 20,25,30 | merges = merges+15+15=15+(15+15) = 45

3) next two -- 45,30 --> reordering -- 30,45 | merges= merges+ 20+25 = 45+(20+25) = 45+45= 90

4) last two -- 75 | merges = merges+45+30 = 90+(45+30) = 90+75 = 165

so, 165 is the answer

2 votes
2 votes
Sort the files: 5, 10, 15, 20, 25.
Merge the smallest two records 15, 15, 20, 25
Merge 30, 20, 25
Sort 20, 25, 30
Merge 45, 30
75. So C is the answer
Answer:

Related questions

21 votes
21 votes
6 answers
4