# GATE 2020 - Algorithms Test 2

This Test will cover trick questions about Sorting algorithms, some numerical and a few questions about Trees.
Q. Breadth-first traversal(BFS) is a method to traverse __________ ?
 A. All successors of a visited node before any successors of any those successors B. A single path of the graph as far it can go C. Graph using shortest path D. None of these
Q. A machine needs a minimum of 100 sec to sort 1000 names by Quick Sort. The minimum time needed to sort 100 names will be approximately?
 A. 50.2 sec B. 6.7 sec C. 72.7 sec D. 11.2 sec
Q. A machine took 200 sec to sort 200 names, using Bubble Sort. In 800 sec, it can approximately sort?
 A. 400 names B. 800 names C. 750 names D. 900 names
Q. For merging two sorted lists of sizes `m` and `n` into a sorted list of size `m+n`, we require comparisons of __________ ?
 A. O(m) B. O(n) C. O(m+n) D. O(log n+log m)

Q. Algorithm which solves the all-pair Shortest Path problem is __________ ?
 A. Dijkstra's algorithm B. Floyd's algorithm C. Prim's algorithm D. Warshall's algorithm
Q. The way a card game player arranges his cards as he picks them up one by one, is an example of __________ ?
 A. Bubble sort B. Selection sort C. Insertion sort D. Merge sort
Q. If there is an NP-complete language `L` whose complement is in `NP`, then complement of any language in `NP` is in?
 A. P B. NP C. Both (a) and (b) D. None of these
Q. Which of the following is correct?
 A. 3-Sat <= p CNF-Sat B. At the language level, 3-Satisfiable <= p CNF-Satisfiable C. Both (a) and (b) D. None of these
Q. Both P and NP are closed under the operation of?
 A. Union B. Intersection C. Concatenation D. Kleene

Q. In a binary max heap containing `n` numbers, the smallest element can be found in __________ time?
 A. O(1) B. O(log n) C. O(log log(n)) D. O(1)
Q. To implement Dijkstra's Shortest Path algorithm on Unweighted Graphs so that it runs in linear time, then data structure to be used is __________ ?
 A. Queue B. Stack C. Heap D. B-tree
Q. Which one of the following needs the minimum number of swaps?
 A. Quick sort B. Insertion sort C. Selection sort D. Heap sort
Q. The maximum number of binary trees that can be formed with three unlabelled nodes are __________ ?
 A. 1 B. 5 C. 4 D. 3
Q. Which of the following Sorting Algorithms has the lowest worst-case complexity?
 A. Merge sort B. Bubble sort C. Quick sort D. Selection sort
Q. The Inorder and Preorder traversal of a binary tree are `d f e a f c g` and `a b d e c f g` respectively. Then the Postorder traversal of that binary tree will be __________ ?
 A. d e b f g c a B. e d b g f c a C. e d b f g c a D. d e f g b c a

### Related Tests:

#### Explore more Subjects:

Tests for various other programming languages and subjects: