Advance Algorithm MCQ

Question 31 : What is the complexity of quick sort algorithm?

1. O(n2)
2. O(logn)
3. O(n)
4. O(nlogn)

Question 32 : What is runtime complexity of graham scan algorithm, if the points are already sorted by one of the coordinates or by the angle to a fixed vector?

1. O(nlogn )
2. O(n)
3. O(logn )
4. O(n2 )

Question 33 : In Binomial Heap, there are B0, B1, B2and B3 binomial trees present, so how many total nodes are there in BH?

1. 11
2. 13
3. 15
4. 4

Question 34 : Johnson's algorithm used to solve following problem?

1. All pair shortest path
2. Min-cut
3. Single source shortest path
4. Minimum spanning tree

Question 35 : Bellman Ford algorithm uses which algorithm design technique?

1. Dynamic Programming
2. Greedy Algorithms
3. Linear Programming
4. Branch and Bound

Question 36 : If the cross product of the vectors p1 and p2 is 0 then

1. p1 is clockwise from p2 with respect to the origin (0,0).
2. p1 is counterclockwise from p2 with respect to the origin (0,0).
3. Either p1 is clockwise from p2 or p2 is clockwise from p1
4. p1 and p2 are collinear, pointing in either opposite or same direction.

Question 37 : Which data structure Graham’s Scan algorithm uses for storing the points of convex hull?

1. Tree
2. Linked List
3. Stack
4. Queue

Question 38 : Which is the correct technique for finding a maximum matching in a graph?

1. DFS traversal
2. BFS traversal
3. Shortest path traversal
4. Heap order traversal

Question 39 : What is the complexity of Ford Fulkerson's algorithm?

1. O(|f*| |E|)
2. O(|E|)
3. O(VE)
4. O(|V|)

Question 40 : When inserting a new entry into red black tree, the newly created node will be

1. red,if the new node is not the root node
2. red, if the new node is the root node
3. black if the new node is not the root node
4. the same color as its sibling

Question 41 : The flow function f maps a value for each edge where ___________

1. f(u,v) <=c(u,v)
2. f(u,v)>= c(u,v)
3. f(u,v) < c(u,v)
4. f(u,v)> c(u,v)

Question 42 : The number of trees in a binomial heap with n nodes is

1. logn
2. n
3. nlogn
4. n/2

Question 43 : To prove NP-Completeness of a problem

1. Select a known P problem
2. Select a known NP problem
3. Select a known NP-Complete problem
4. Select a known NP-Hard problem

Question 44 : Cross product of two vectors originating at origin can be interpreted as

1. Area of Square
2. Perimeter of Square
3. Area of Parallelogram
4. Perimeter of Parallelogram

Question 45 : Which of the following problems should be solved using dynamic programming?

1. Merge sort
2. Binary search
3. Longest common subsequence
4. Quick sort

Question 46 : Which of the following method is taking overcharge for some operations in amortized analysis

1. aggregate method
2. potential method
3. average method
4. accounting method

Question 47 : For solving recurrences, which of the following method is used to generate a good guess of the solution?

1. Iteration method
2. Substitution method
3. Recursion tree method
4. Master method

Question 48 : Approach used by Matrix chain multiplication algorithm

1. Dynamic Programming
2. Greedy
3. Brute Force
4. Branch and Bound

Question 49 : Which technique of Ford- Fulkerson algorithm helps it to solve max flow problem

1. Naive greedy algorithm approach
2. Minimum spanning tree
3. Residual graphs
4. Minimum cut

Question 50 : What is the special property of red-black trees and what root should always be?

1. a color which is either red or black and root should always be black color only
2. height of the tree
3. pointer to next node
4. a color which is either green or black