Algorithms programming - Data structure
CSE - Algorithms programming - Data structure - Questions and solutions
Question:-
Option (A)
3
Option (B)
7
Option (C)
9
Option (D)
6
Correct Option:
A
Question Solution:
Initially we start filling table from 6 and so on
_{}
Now fill alphabet from the position 0. So we get
_{}
So I stored at location 3.
Question:-
Applying algorithm B to the list of numbers
14, 10, 17, 12, 10, 11, 20, 12, 18, 25, 20, 8, 22, 11, 13
We obtain a tree. Calculate the exact number of comparisons is
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
_{}
Question:-
Option (A)
6
Option (B)
8
Option (C)
10
Option (D)
11
Correct Option:
A
Question:-
Common Data Questions 32 and 33.
Consider the two algorithm, Algorithm A and Algorithm B:
Algo A :Scan the elements from A_{1} to A_{n }(Left to Right)
(a) For each element A_{k}, compare A_{k} with A_{1}, A_{2}, ..., A_{k-1} that is, compare A_{k} with those elements which precedes A_{k}.
(b) If A_{k} does occur among A_{1}, A_{2}, ..., A_{k-1} then delete A_{k}.
Algo B:Build a binary search tree T using the elements A_{1}, A_{2}, .... , A_{k}. In building the tree, delete A_{k} from the list whenever the value of A_{k} already appear in the tree.
Consider the following list of 15 numbers
14, 10, 17, 12, 10, 11, 20, 12, 18, 25, 20, 8, 22, 11, 23
On applying algorithm A to this list of numbers we obtain the tree. So the number of comparisons required by algorithm A is approximately
Option (A)
38
Option (B)
72
Option (C)
46
Option (D)
None of these
Correct Option:
B