Closest Pair Problem Multiple Choice Questions and Answers (MCQs)

«
»

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Closest Pair Problem”.

1. Which of the following areas do closest pair problem arise?
a) computational geometry
b) graph colouring problems
c) numerical problems
d) string matching
View Answer

Answer: a
Explanation: Closest pair problem arises in two most important areas- computational geometry and operational research.
advertisement

2. Which approach is based on computing the distance between each pair of distinct points and finding a pair with the smallest distance?
a) Brute force
b) Exhaustive search
c) Divide and conquer
d) Branch and bound
View Answer

Answer: a
Explanation: Brute force is a straight forward approach that solves closest pair problem using that algorithm.

3. What is the runtime efficiency of using brute force technique for the closest pair problem?
a) O(N)
b) O(N log N)
c) O(N2)
d) O(N3 log N)
View Answer

Answer: c
Explanation: The efficiency of closest pair algorithm by brute force technique is mathematically found to be O(N2).

4. The most important condition for which closest pair is calculated for the points (pi, pj) is?
a) i>j
b) i!=j
c) i=j
d) i<j
View Answer

Answer: d
Explanation: To avoid computing the distance between the same pair of points twice, we consider only the pair of points (pi, pj) for which i<j.

5. What is the basic operation of closest pair algorithm using brute force technique?
a) Euclidean distance
b) Radius
c) Area
d) Manhattan distance
View Answer

Answer: a
Explanation: The basic operation of closest pair algorithm is Euclidean distance and its formula is given by d=√(xi-xj)2+(yi-yj)2.
advertisement

6. Which of the following is similar to Euclidean distance?
a) Manhattan distance
b) Pythagoras metric
c) Chebyshev distance
d) Heuristic distance
View Answer

Answer: b
Explanation: In older times, Euclidean distance metric is also called a Pythagoras metric which is the length of the line segment connecting two points.

7. Which of the following strategies does the following diagram depict?
closest-pair-problem-questions-answers-q7
a) Divide and conquer strategy
b) Brute force
c) Exhaustive search
d) Backtracking
View Answer

Answer: b
Explanation: Brute force is a straight forward approach to solve critical problems. Here, we use brute force technique to find the closest distance between p1 and p2.

8. Manhattan distance is an alternative way to define a distance between two points.
a) true
b) false
View Answer

Answer: a
Explanation: Manhattan distance is an alternative way to calculate distance. It is the distance between two points measured along axes at right angles.

9. What is the optimal time required for solving the closest pair problem using divide and conquer approach?
a) O(N)
b) O(log N)
c) O(N log N)
d) O(N2)
View Answer

Answer: c
Explanation: The optimal time for solving using a divide and conquer approach is mathematically found to be O(N log N).
advertisement

10. In divide and conquer, the time is taken for merging the subproblems is?
a) O(N)
b) O(N log N)
c) O(N2)
d) O(log N)
View Answer

Answer: b
Explanation: The time taken for merging the smaller subproblems in a divide and conquer approach is mathematically found to be O(N log N).

11. The optimal time obtained through divide and conquer approach using merge sort is the best case efficiency.
a) true
b) false
View Answer

Answer: a
Explanation: The optimal time obtained through divide and conquer approach is the best class efficiency and it is given by Ω(N log N).

12. Which of the following strategies does the following diagram depict?
closest-pair-problem-questions-answers-q12
a) Brute force
b) Divide and conquer
c) Exhaustive search
d) Branch and bound
View Answer

Answer: b
Explanation: The above diagram depicts the implementation of divide and conquer. The problem is divided into sub problems and are separated by a line.

13. Which of the points are closer to each other?
closest-pair-problem-questions-answers-q13
a) p1 and p11
b) p3 and p8
c) p2 and p3
d) p9 and p10
View Answer

Answer: c
Explanation: From symmetry, we determine that the closest pair is p2 and p3. But the exact calculations have to be done using Euclid’s algorithm.
advertisement

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn