Quiz_01

Which of the following sorting algorithms in its typical implementation gives best performance when applied on an array which is sorted or almost sorted (maximum 1 or two elements are misplaced).

• Merge sort

• Insertion sort

• Heap sort

• none

What is the worst case time complexity of insertion sort where position of the data to be inserted is calculated using binary search?

• N^2

• N(logN)^2

• N(logN)

• N

Which sorting algorithm will take least time when all elements of input array are identical? Consider typical implementations of sorting algorithms.

• Insertion sort

• Selection sort

• Bubble sort

• Merge sort

Which is the correct order of the following algorithms with respect to their time Complexity in the best case ?

• Merge sort > Quick sort >Insertion sort > selection sort

• insertion sort < Quick sort < selection sort

• Quick sort>Merge sort >Insertion sort > selection sort

• None

Depth First Search is equivalent to which of the traversal in the Binary Trees?

• a) Pre-order Traversal

• b) Post-order Traversal

• c) Level-order Traversal

• d) In-order Traversal

Time Complexity of DFS is? (V – number of vertices, E – number of edges)

• a) O(V + E)

• b) O(V)

• c) O(E)

• d) O(V*E)

What is the worst case complexity of Quick Sort?

• a) O(nlogn)

• b) O(logn)

• c) O(n)

• d) O(n2)

How many comparisons will be made to sort the array arr={1, 5, 3, 8, 2} using counting sort?

• 8

• 5

• 0

• 1

Which of the following sorting techniques is most efficient if the range of input data is not significantly greater than a number of elements to be sorted?

• insertion sort

• MERGE SORT

• SHELL SORT

• COUNTING SORT

In what time can a binary heap be built?

• a) O(N)

• b) O(N log N)

• c) O(log N)

• d) O(N2)