Engineering Questions with Answers - Multiple Choice Questions

# Closest Pair Problem MCQs

1 - Question

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

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

2 - Question

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

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

3 - Question

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)

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

4 - Question

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

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 - Question

What is the basic operation of closest pair algorithm using brute force technique?
a) Euclidean distance
c) Area
d) Manhattan distance

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

6 - Question

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

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 - Question

Which of the following strategies does the following diagram depict? a) Divide and conquer strategy
b) Brute force
c) Exhaustive search
d) Backtracking

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 - Question

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

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

9 - Question

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)

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

10 - Question

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)

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 - Question

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

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

12 - Question

Which of the following strategies does the following diagram depict? a) Brute force
b) Divide and conquer
c) Exhaustive search
d) Branch and bound

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 - Question

Which of the points are closer to each other? a) p1 and p11
b) p3 and p8
c) p2 and p3
d) p9 and p10