Insertion Sort Interview Question Part 2

13. What is the output of insertion sort after the 4th iteration given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 3 7 5 1 9 8 4 6
b. 1 3 5 7 9 8 4 6
c. 3 4 1 5 6 8 7 9
d. 1 3 4 5 6 7 8 9
Ans:b


14. What is the output of insertion sort after the 5th iteration given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 3 7 5 1 9 8 4 6
b. 1 3 4 5 7 9 8 6
c. 3 4 1 5 6 8 7 9
d. 1 3 5 7 8 9 4 6
Ans:d

15. What is the output of insertion sort after the 6th iteration given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 3 7 5 1 9 8 4 6
b. 1 3 4 5 7 8 9 6
c. 3 4 1 5 6 8 7 9
d. 1 3 4 5 6 7 9 8
Ans:b

16.The frequency count of insertion sort in the worst case is
a.n*n
b.n(n-1)/2
c.n
d.logn
Ans:b

17.The frequency count of insertion sort in the average case is
a.n*n
b.n(n-1)/2
c.n(n-1)/4
d.logn
Ans:c

18.Insertion sort is an example of
a.incremental algorithm
b.decremental algorithm
c.both
d.none
Ans:a

19.The best case running time T(n) for insertion sort is
a.a quadratic function of n
b.a linear function of n
c.a logarithmic function of n
d.none
Ans:b
Complexity is O(n)

20. The worst case running time T(n) for insertion sort is
a.a quadratic function of n
b.a linear function of n
c.a logarithmic function of n
d.none
Ans:a
Complexity is O(n*n)

21. The sort that keeps making the left side of the array sorted until the whole array is sorted and which sorts the values seen so far and repeatedly inserts unseen values in the array into the left sorted array is called
a.selection sort
b.bubble sort
c.insertion sort
d.heap sort
Ans:c
22. What is the output of insertion sort after the 1st iteration given the following sequence of numbers: 3 10 4 6 8 9 7 2 1 5
a. 3 4 10 6 8 7 9 2 1 5
b. 3 4 6 10 8 9 7 2 1 5
c. 3 10 4 6 8 9 7 2 1 5
d. 3 4 10 6 8 9 2 7 1 5
Ans:c

23. What is the output of insertion sort after the 2nd iteration given the following sequence of numbers: 3 10 4 6 8 9 7 2 1 5
a. 3 4 10 6 8 7 9 2 1 5
b. 3 4 10 6 8 9 7 2 1 5
c. 3 4 10 6 8 9 7 2 1 5
d. 3 4 10 6 8 9 2 7 1 5
Ans:b

24. What is the output of insertion sort after the 3rd iteration given the following sequence of numbers: 3 10 4 6 8 9 7 2 1 5
a. 3 4 6 8 10 9 7 2 1 5
b. 3 4 6 10 8 9 7 2 1 5
c. 3 4 10 6 8 9 7 2 1 5
d. 3 4 10 6 8 9 2 7 1 5
Ans:b