Categories

Algorithms programming - Data structure

CSE - Algorithms programming - Data structure - Questions and solutions
Question:-
Option (A)
38
Option (B)
72
Option (C)
46
Option (D)
None of these
Correct Option:
A
Question Solution:
32. (b) 33. (a)
Apply algorithm B to the list of numbers we obtain a tree

So the exact number of comparisons.
0 + 1 + 1 + 2 + 2 + 3 + 2 + 3 + 3 + 3 + 3 + 2 + 4 + 4 + 5 = 38
For the algorithm A
The exact number of compressions:
0 + 1 + 2 + 3 + 2 + 4 + 5 + 4 + 6 + 7 + 6 + 8 + 9 + 5 + 10 = 72
Question:-
Option (A)
330
Option (B)
666
Option (C)
926
Option (D)
None of these
Correct Option:
D
Question Solution:
In the first path we can create sorted sub files, each 5 page long. In the second pass by 4-way merging, one can create sorted sub-files, each 20 page long (except last). Again applying 4way merge sort, we can create sorted sub files. These two can be merged to get the final sorted file. We require a total of 4 passes. Total cost will be 2 x 105 x 4 = 840 units.
Question:-
Option (A)
11
Option (B)
12
Option (C)
13
Option (D)
None of these
Correct Option:
B
Question Solution:
30. A & 31. B
               Probes
16 mod 11 = 5   1
23 mod 11 = 1   1
9 mod 11 = 9    1
34 mod 11 = 1   2   5 - 34 mod 5 = 1
12 mod 11 = 1   2   5 - 12 mod 5 = 3
56 mod 11 = 1   5   5 - 56 mod 5 = 4
There is collision on inserting 34. So we use the second hash function. Now 34 stored at
1 + (1 x 1) = 2 (location)
Collision on inserting 12. So we use the second hash function. Now 12 stored as
1 + (1 x 3) = 4
Collision on inserting 56. So we use second hash function. Now 56 stored at
1 + (1 x 4) = 5
Now again collision take place
So new location 1 + (2 x 4) = 9
Again collision
So new location 1 + (3 x 4) = 13, 13 mod 11 = 2
again collision
So new location 1 + (4 x 4) = 17, 17 mod 11 = 6
So 56 stored at location 6.
So total number of probes = 1 + 1 + 1 + 2 + 2 + 5 = 12