Data Structures & Algorithms Multiple Choice Questions on “Quickhull”.
1. ___________ is a method of constructing a smallest polygon out of n given points. Answer: b 2. What is the other name for quick hull problem? 3. How many approaches can be applied to solve quick hull problem? 4. What is the average case complexity of a quick hull algorithm? Answer: b 5. What is the worst case complexity of quick hull? Answer: c 6. What does the following diagram depict? Answer: b 7. Which of the following statement is not related to quickhull algorithm? Answer: d 8. The quick hull algorithm runs faster if the input uses non- extreme points. Answer: a 9. To which type of problems does quick hull belong to? Answer: b 10. Which of the following algorithms is similar to a quickhull algorithm? Answer: d 11. Who formulated quick hull algorithm? Answer: a 12. The time is taken to find the ‘n’ points that lie in a convex quadrilateral is? Answer: a here is complete set of 1000+
a) closest pair problem
b) quick hull problem
c) path compression
d) union-by-rank
Clarification: Quick hull is a method of constructing a smallest convex polygon out of n given points in a plane.
a) convex hull
b) concave hull
c) closest pair
d) path compression
Answer: a
Clarification: 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.
a) 1
b) 2
c) 3
d) 4
Answer: b
Clarification: Most commonly, two approaches are adopted to solve quick hull problem- brute force approach and divide and conquer approach.
a) O(N)
b) O(N log N)
c) O(N2)
d) O(log N)
Clarification: The average case complexity of quickhull algorithm using divide and conquer approach is mathematically found to be O(N log N).
a) O(N)
b) O(N log N)
c) O(N2)
d) O(log N)
Clarification: The worst case complexity of quickhull algorithm using divide and conquer approach is mathematically found to be O(N2).
a) closest pair
b) convex hull
c) concave hull
d) path compression
Clarification: The above diagram is a depiction of convex hull, also known as quick hull, since it encloses n points into a convex polygon.
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
Clarification: Finding the shortest distance between two points belongs to closest pair algorithm while the rest is quickhull.
a) true
b) false
View Answer
Clarification: It is proved that the quick hull algorithm runs faster if the input uses non-extreme points and also, if it uses less memory.
a) numerical problems
b) computational geometry
c) graph problems
d) string problems
View Answer
Clarification: Quick hull problem and closest pair algorithms are some of the examples of computational problems.
a) merge sort
b) shell sort
c) selection sort
d) quick sort
Clarification: Quickhull algorithm is similar to a quick sort algorithm with respect to the run time average case and worst case efficiencies.
a) Eddy
b) Andrew
c) Chan
d) Graham
Clarification: Eddy formulated quick hull algorithm. Graham invented graham scan. Andrew formulated Andrew’s algorithm and Chan invented Chan’s algorithm.
a) O(N)
b) O(N log N)
c) O(N2)
d) O(log N)
Clarification: The time taken to find the ‘n’ points that lie in a convex quadrilateral is mathematically found to be O(N).