Advance Algorithm MCQ's




Question 1 :
In a binomial tree, the key of a node is ______ the key of its parent.

  1. greater than
  2. greater than or equal to
  3. less than
  4. less than or equal to
  

Question 2 :
In a B-tree of order n, root node contains how many minimum keys?

  1. 1
  2. n
  3. n-1
  4. (n - 1)/2
  

Question 3 :
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 4 :
BINOMIAL_HEAP_MERGE returns a root list H that is sorted by _____ degree

  1. monotonically decreasing
  2. monotonically increasing
  3. random
  4. Initially increasing, later decreasing
  

Question 5 :
Let f1(n) and f2(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. Which of the following is always true?

  1. f2(n) = Omega(f1(n))
  2. f2(n) = theta(f1(n))
  3. f2(n) = O(f1(n))
  4. f2(n) = o(f1(n))
  

Question 6 :
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 7 :
If T(n) = T(n/2) + n, then the complexity will be as follows:

  1. O(log n)
  2. O(n)
  3. O(n.log n)
  4. O(n2)
  

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

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

Question 9 :
For vectors p1 and p2 to check if p1 is clockwise from p2 with respect to origin(0,0) which of the following is true:

  1. p1 × p2 is +ve
  2. p1 × p2 is -ve
  3. p1 × p2 is 0
  4. p1 and p2 are collinear, pointing in either opposite or same direction.
  

Question 10 :
Which asymptotic notation is used to show loose upperbound

  1. Big O
  2. Small o
  3. Theta
  4. Omega
  

Question 11 :
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 12 :
The complexity of the ford fulkerson algorithm is

  1. O(V2E)
  2. O(|E|log|V|)
  3. O(E|f*|)
  4. O(V3)
  

Question 13 :
Let X is a problem that belongs to the class NP. Then which one of the following is TRUE?

  1. There is no polynomial time algorithm for X.
  2. If X can be solved deterministically in polynomial time, then P = NP.
  3. If X is NP-hard, then it is NP-complete.
  4. X may be undecidable.
  

Question 14 :
Closest pair algorithm using brute force performs which basic operation

  1. Euclidean distance
  2. Manhattan distance
  3. Area
  4. Radius
  

Question 15 :
In LPP, the optimal value of the objective function is attained at the points

  1. Given by intersection of inequations with axes only
  2. Given by intersection of inequations with x-axis only
  3. Given by corner points of the feasible region.
  4. Given by intersection of inequations with y-axis only
  

Question 16 :
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 17 :
Recursion tree is used for?

  1. solving recurrences
  2. solving iterative relations
  3. analyzing loops
  4. calculating the time complexity of any code
  

Question 18 :
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 19 :
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 20 :
When to prefer Red-black trees over AVL trees?

  1. When log(nodes) time complexity is needed.
  2. When more search operations are needed.
  3. When there are more insertions or deletions.
  4. When tree must be balanced
  

Question 21 :
Calculate complexity of the given recurrence equation. T(n) = 4T(n/2) + n2

  1. ϴ(n)
  2. ϴ(n logn)
  3. ϴ(n2)
  4. ϴ(n2 log n)
  

Question 22 :
The flow from vertex u to vertex v is the negative of the flow in reverse direction is called as

  1. Capacity constraint
  2. Skew Symmetry
  3. Flow conservation property
  4. Residual Capacity
  

Question 23 :
Approach used by Matrix chain multiplication algorithm

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

Question 24 :
The number of black nodes from the root to a node is the node's____ ______; the uniform number of black nodes in all paths from root to the leaves is called the ____ _____ of the red–black tree.

  1. Black depth, Black height
  2. Black height, black depth
  3. red depth, red height
  4. red height, red depth
  

Question 25 :
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 26 :
The black height of a red black tree is

  1. Black height of its root
  2. Black height of a node
  3. Red height of a node
  4. Height of a tree
  

Question 27 :
During the execution of BINOMIAL_HEAP_UNION, how many maximum roots of a given degree can be there on the root list of Binomial Heap H.

  1. 2
  2. 3
  3. 1
  4. 0
  

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

Question 29 :
How many nodes a binomial tree Bk consists of?

  1. K
  2. 2k-1
  3. 2k+1
  4. 2k
  

Question 30 :
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 )
  
Pages