Dark Mode On/Off

# GATE 2016 - Algorithms Test 3

This Test will cover complete Algorithms with very important questions, starting off from basics to advanced level.
Q. In an Unweighted, Undirected connected Graph, the shortest path from a node `S` to every other node is computed most efficiently, in terms of time complexity, by?
 A. Dijkstra's algorithm starting from S B. Warshall's algorithm C. Performing a DFS starting from S D. Performing a BFS starting from S
Q. The most efficient algorithm for finding the number of connected components in an undirected graph on `n` vertices and `m` edges has time complexity __________ ?
 A. O(n) B. O(m) C. O(m+n) D. O(mn)
Q. The minimum number of comparisons required to determine, if an integer appears more than `n/2` times in a sorted array of `n` integers?
 A. Theta(n) B. Theta(log n) C. Theta(log n*n) D. Theta(1)
Q. A B-tree of order `4` is built from scratch by `10` successive insertions. What is the maximum number of node splitting operations that may take place?
 A. 3 B. 4 C. 5 D. 6

Q. G is a graph on `n` vertices and `2n-2` edges. The edges of G can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for G?
 A. For every subset of k vertices, the induced subgraph has at most 2k-2 B. The minimum cut in G has at least two edges C. There are two edge-disjoint paths between every pair of vertices D. There are two vertex-disjoint paths between every pair of vertices
Q. We have a binary heap on `n` elements and wish to insert `n` more elements(not necessarily one after another) into this heap. Total time required for this is?
 A. Theta(log n) B. Theta(n) C. Theta(n log n) D. Theta(n*n)
Q. What is the number of swaps required to sort `n` elements using selection sort, in the worst case?
 A. Theta(n) B. Theta(n log n) C. Theta(n*n) D. Theta(n*n log n)
Q. In quick sort, for sorting `n` elements, the `(n/4)th` smallest element is selected as Pivot using an `O(n)` time algorithm. What is the worst case time complexity of the Quick Sort?
 A. Theta(n) B. Theta(n log n) C. Theta(n*n) D. Theta(n*n log n)
Q. Two alternative package A and B are available for processing a database having `10^k` records. Package A requires `0.00001 n^2` time units and package B requires `10nlog(n)` [Base of log is 10] time units to process `n` records. What is the smallest value of `k` for which B will be preferred over A?
 A. 12 B. 10 C. 6 D. 5

Q. Let `W(n)` and `A(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?
 A. A(n) = Omega(W(n)) B. A(n) = Theta(W(n)) C. A(n) = O(W(n)) D. None of these
Q. The recurrence relation capturing the optimal execution time of the Tower of Hanoi problem with `n` discs is?
 A. T(N) = 2T(n-2)+2 B. T(n) = 2T(n-1)+n C. T(n) = 2T(n/2)+1( D. T(n) = 2T(n-1)+1
Q. The worst case running to search for an element in a balanced binary search tree with `n2^n` elements is?
 A. Theta(n log n) B. Theta(n 2^n) C. Theta(n) D. Theta(log n)
Q. Assuming P not equal to NP, which of the following is TRUE?
 A. NP-complete = NP B. NP-complete intersection P = Null C. NP-hard = NP D. P = NP-complete
Q. A list of `n` strings, each of length `n`, is sorted into lexicographic order using the Merge-Sort algorithm. The worst case running time of this computation is?
 A. O(n log n) B. O(n*n log n) C. O(n*n+log n) D. O(n*n)
Q. You are given the Postorder traversal, P, of a binary search tree on the n elements 1,2,...,n. You have to determine the unique Binary Search Tree that has P as its Postorder traversal. What is the Time Complexity of the most efficient algorithm for doing this?
 A. Theta(log n) B. Theta(n) C. Theta(n log n) D. None of the above, as the tree cannot be uniquely determined.