Selection Sort Interview Question Part 2

14.The efficiency of selection sort is
a.n*(n/2)
b.n*n
c.n(n-1)/2
d.none
Ans:a
The first loop goes from 0 to n, and the second loop goes from x to n, so it goes from 0 to n, then from 1 to n, then from 2 to n and so on. The multiplication works out so that the efficiency is n*(n/2), though the order is still O(n^2).
15.The frequency count of selection sort is
a.n*n
b.n(n-1)/2
c.n
d.logn
Ans:b
(n-1)+(n-2)+……+3+2+1=n(n+1)/2 – n =n(n-1)/2

16.The total number of iterations in selection sort is
a.n-1
b.n
c.n*n
d.2*n
Ans:a


17. For a List with L elements numbered from 0 to L-1 , the selection sort algorithm is

Set marker to L-1 (begin with the last element in the list)
While marker>0
Find the largest element in the range numbered from 0 to marker.
Swap that element with the element at location marker.
Increase marker back by 1
Assume the initial list is 3, 9, 1,7 ,2

What are the correct intermediate output values during the process of sorting?
a.3, 2, 1, 7, 9
b.3, 9, 1, 2, 7
c.1, 2, 3, 7, 9
d.9, 3, 1, 2, 7
Ans:a

18. Consider the following selection sort algorithm and the integer data set given thereafter.
For a list with L elements numbered from 0 to L-1, the selection sort algorithms is :
1. Set marker to L-1 (beginning with the last element in the list)
2. While marker >0 ;
i. Find the largest element in the range numbered from 0 to marker.
ii. Swap the largest element with the element at the location marker.
iii. Increase marker back by 1
Data set: { 4 10 2 8 3 }
If the above algorithm works on the given data set , what would not be the pair of swapping values during the
process of sorting?
(a) (3,10) (b) (4,2) (c) (2,3) (d) (10,2)
Ans: d

19. Let there be a list with L elements numbered from 0 to L-1, and consider the following algorithm:

Step 1: set marker1 to L-1 (begin with the location of the last element in the list)
Step 2: While marker > 0
Step 3: find the largest element in the range numbered from 0 to marker
Step 4: swap that element with the element at location marker.
Step 5: Increase marker by 1
The above algorithm describes
(a) Bubble sort. (b) Selection sort. (c) Insertion sort. (d)Merge sort
Ans:b
20.What is the output of selection sort for the following numbers after the first pass?
3 6 9 2 7 10 1 5 8 4
a. 1 6 9 3 7 10 2 5 4 8
b. 1 6 9 3 7 2 10 5 8 4
c.1 6 9 3 7 10 2 5 8 4
d. 1 6 9 7 3 10 2 5 8 4
Ans:c

21. What is the output of selection sort for the following numbers after the 2nd pass?
3 6 9 2 7 10 1 5 8 4
a. 1 6 9 3 7 10 2 5 4 8
b. 1 2 9 6 7 10 3 5 8 4
c.1 6 9 3 7 10 2 5 8 4
d. 1 2 6 9 7 10 3 5 8 4
Ans:b

22. What is the output of selection sort for the following numbers after the 3rd pass?
3 6 9 2 7 10 1 5 8 4
a. 1 2 3 6 7 10 9 5 8 4
b. 1 2 9 6 7 10 3 5 8 4
c.1 6 9 3 7 10 2 5 8 4
d. 1 2 6 9 7 10 3 5 8 4
Ans:a

23. What is the output of selection sort for the following numbers after the 4th pass?
3 6 9 2 7 10 1 5 8 4
a. 1 2 3 6 7 10 9 5 8 4
b. 1 2 9 6 7 10 3 5 8 4
c.1 6 9 3 7 10 2 5 8 4
d. 1 2 3 4 7 10 9 6 8 5
Ans:d

24. What is the output of selection sort for the following numbers after the 5th pass?
3 6 9 2 7 10 1 5 8 4
a. 1 2 3 6 7 10 9 5 8 4
b. 1 2 9 6 7 10 3 5 8 4
c.1 2 3 4 5 10 9 7 8 6
d. 1 2 3 4 7 10 9 6 8 5
Ans:c

25. What is the output of selection sort for the following numbers after the 6th pass?
3 6 9 2 7 10 1 5 8 4
a. 1 2 3 4 5 6 10 9 8 7
b. 1 2 9 6 7 10 3 5 8 4
c.1 2 3 4 5 10 9 7 8 6
d. 1 2 3 4 7 10 9 6 8 5
Ans:a

26.What is the output of selection sort for the following numbers after the 7th pass?
3 6 9 2 7 10 1 5 8 4
a. 1 2 3 4 5 6 10 9 8 7
b. 1 2 3 4 5 6 7 9 8 10
c.1 2 3 4 5 10 9 7 8 6
d. 1 2 3 4 7 10 9 6 8 5
Ans:b