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

1. ___________ is a method of constructing a smallest polygon out of n given points.

a) closest pair problem

b) quick hull problem

c) path compression

d) union-by-rank

View Answer

Explanation: Quick hull is a method of constructing a smallest convex polygon out of n given points in a plane.

2. What is the other name for quick hull problem?

a) convex hull

b) concave hull

c) closest pair

d) path compression

View Answer

Explanation: The other name for quick hull problem is convex hull problem whereas the closest pair problem is the problem of finding the closest distance between two points.

3. How many approaches can be applied to solve quick hull problem?

a) 1

b) 2

c) 3

d) 4

View Answer

Explanation: Most commonly, two approaches are adopted to solve quick hull problem- brute force approach and divide and conquer approach.

4. What is the average case complexity of a quick hull algorithm?

a) O(N)

b) O(N log N)

c) O(N^{2})

d) O(log N)

View Answer

Explanation: The average case complexity of quickhull algorithm using divide and conquer approach is mathematically found to be O(N log N).

5. What is the worst case complexity of quick hull?

a) O(N)

b) O(N log N)

c) O(N^{2})

d) O(log N)

View Answer

Explanation: The worst case complexity of quickhull algorithm using divide and conquer approach is mathematically found to be O(N

^{2}).

6. What does the following diagram depict?

a) closest pair

b) convex hull

c) concave hull

d) path compression

View Answer

Explanation: The above diagram is a depiction of convex hull, also known as quick hull, since it encloses n points into a convex polygon.

7. Which of the following statement is not related to quickhull algorithm?

a) finding points with minimum and maximum coordinates

b) dividing the subset of points by a line

c) eliminating points within a formed triangle

d) finding the shortest distance between two points

View Answer

Explanation: Finding the shortest distance between two points belongs to closest pair algorithm while the rest is quickhull.

8. The quick hull algorithm runs faster if the input uses non- extreme points.

a) true

b) false

View Answer

Explanation: It is proved that the quick hull algorithm runs faster if the input uses non-extreme points and also, if it uses less memory.

9. To which type of problems does quick hull belong to?

a) numerical problems

b) computational geometry

c) graph problems

d) string problems

View Answer

Explanation: Quick hull problem and closest pair algorithms are some of the examples of computational problems.

10. Which of the following algorithms is similar to a quickhull algorithm?

a) merge sort

b) shell sort

c) selection sort

d) quick sort

View Answer

Explanation: Quickhull algorithm is similar to a quick sort algorithm with respect to the run time average case and worst case efficiencies.

11. Who formulated quick hull algorithm?

a) Eddy

b) Andrew

c) Chan

d) Graham

View Answer

Explanation: Eddy formulated quick hull algorithm. Graham invented graham scan. Andrew formulated Andrew’s algorithm and Chan invented Chan’s algorithm.

12. The time is taken to find the ‘n’ points that lie in a convex quadrilateral is?

a) O(N)

b) O(N log N)

c) O(N^{2})

d) O(log N)

View Answer

Explanation: The time taken to find the ‘n’ points that lie in a convex quadrilateral is mathematically found to be O(N).

**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__.