Sorting Interview Questions Part 6

1. Divide-and-conquer is a
a.top-down technique
b.Bottom-up technique
c.Both
d.none
Ans:a
2.The technique for designing algorithms that consists of dividing the problem into smaller subproblems hoping that the solutions of the subproblems are easier to find and then composing the partial solutions into the solution of the original problem is _____
Ans:Divide and conquer
3. Divide-and-conquer paradigm consists of following major phases:Arrange them in order
a.Solve the sub-problem recursively (successively and independently), and then
b.Breaking the problem into several sub-problems that are similar to the original problem but smaller in size,
c.Combine these solutions to subproblems to create a solution to the original problem.
a. bac
b. abc
c. cab
d. none
Ans:a
4. Bubble sort requires extra memory.(T/F)
Ans:False
5. Insertion sort is an example of
a.incremental sort
b.decremental sort
c.non-stable sort
d.none
Ans:a
Insertion sort is an example of an incremental algorithm; it builds the sorted sequence one number at a time.
6. An algorithm considering the elements one at a time, inserting each in its suitable place among those already considered (keeping them sorted) is called
a.selection sort
b.insertion sort
c.bubble sort
d.none
Ans:b
7.The following process depicts which sorting algorithm: first find the smallest in the array and exchange it with the element in the first position, then find the second smallest element and exchange it with the element in the second position, and continue in this way until the entire array is sorted.
a.selection sort
b.insertion sort
c.bubble sort
d.none
Ans:a
8. Selection sort is quadratic in both the worst and the average case, and requires no extra memory.(T/F)
Ans:True
9. For each i from 1 to n - 1, there are ____ exchanges for selection sort.
a.1
b.n-1
c.n
d.none
Ans:a
10.For each i from 1 to n - 1, there is _______comparisons for selection sort.
a.n
b.n-i
c.i
d.n-1
Ans:b
For each i from 1 to n - 1, there is one exchange and n - i comparisons, so there is a total of n -1 exchanges and (n -1) + (n -2) + . . . + 2 + 1 = n(n -1)/2 comparisons. These observations hold no matter what the input data is.