Algorithms - Algorithm Design Techniques
- Option : A
- Explanation : If new record hashes onto one of the six locations 7, 8, 9, 10, 1 or 2, the location 2 will receive a new record. the probability is 6/10 (as 10 is total possible number of locations).
- Option : D
- Explanation : We can verify that the 1st, 3rd, 5th, 7th ... probes check at location 5. 2nd, 6th, 10th ... probes check at location 8. 4nd, 8th, 12th ... probes check at location 4. Rest of the address space will never be probed.
- Option : A
- Explanation : If there is only one record, then
Probability of collision = 1/100
If there are two records,
then Probability of collision = 2/100
and if there are 9 records,
then Probability of collision = 9/100.
∴ Required probability =
= 0.45
5. Which one of the following statements is false?
- A
Optimal binary search tree construction can be performed efficiently using dynamic programming
- B
Breadth-first search cannot be used to find connected components of a graph
- C
Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed
- D
Depth-first search can be used to find connected components of a graph
- Option : B
- Explanation : BFS and DFS both algorithm are used to find connected component of graph in linear time.
