Sorting Interview Questions Part 4

61.How many passes are required to sort the set of integers using the bubble sort algorithm? {20,60,50,37,16,92,70,35}.

(a) 6 (b) 7 (c) 8
(d) 9 (e) 5
Ans. b

62.Consider the following pseudo code algorithm
found = false;
i=1;
while (i =< n ) and ( not found)
{
if key=k[i] then
{
search =i;
found =true;
else
i++;
}
}
if not found
{
search=0;
}
What is the above algorithm intended to do?
(a) Sequential Search (b) Depth First Algorithm
(c) Shell sort algorithm (d) Index sequential search
(e) Breadth first search
Ans. a

63. Consider the following (iv) conditions:
(i) Sorts which cannot be performed in the main memory, can be done on disk or tape. These are also quite important. This type of sorting is called external sorting.
(ii) The simplest algorithms usually take O(n2) time to sort in objects and are only useful for sorting short lists.
(iii) One of the most popular sorting algorithm is quicksort; which takes O(log n) time on average.
(iv) Merge sort is well suited for external sorting.
Which of the above conditions are applied for the sorting algorithm?
a. (i),(ii) and (iii) only
b. (i),(ii) and (iv) only
c. (ii),(iii) and (iv) only
d. (i) and (iii) only

Ans. b

64. Which sorting method(s) runs fastest for file which is already sorted?
a.Selection sort
b.insertion sort
c.quick sort
d.bubble sort
Ans:b
65.
(i) Quick Sort can be implemented in recursive way.
(ii) Heap Sort is the best sorting method compared to bubble, selection, insertion sort on the basis of complexity.

Correct statement(s) is/are?
A(i) only
b (ii) only
c.(i) and (ii)
d.none
Ans:c
66. In calculating the time complexity of an algorithm, we use some rules.

Rule 1.
If T1 (N)=O(f(N)) and T2(N)=O(g(N)) then
Statement 1 T1(N) + T2 (N)=Max(O(f(N)),O(g(N)))
Statement 2 T1(N)* T2(N)=O(f(N)*g(N))
Rule 2
If T1(N)=O(f(N)) and T2(N)=O(g(N)) then
Statement 1 T1(N)+ T2(N)=Min(O(f(N)),O(g(N)))
Statement 2 T1(N)* T2(N)=O(f(N))+O(g(N))
Rule 3
O(C f(N))=O(f(N)) if C is a constant
Rule 4
If T1 (N)=O(f(N)) and T2(N)=O(g(N)) and If g(N) < = f(N) then
T1(N)+ T2(N)=O(f(N))

What are the correct rules out of the above?
a.Rule 1 , Rule 2 and Rule 3 only
b.Rule 1 and Rule 4 only
c.Rule 1 , Rule 3 and Rule 4 only
d.Rule 2, Rule 3 and Rule 4 only
Ans:c



67. What is the name of the following algorithm?

Initialize marker to 1 (2nd element in the list)
If element[marker1] < element [marker1-1] , store element[marker1] in a temporary location temp, initialize marker2 to marker1-1 (the location just before marker1).
While element [marker2] > temp and marker2 >= 0 shift element [marker2] to location marker2+1. [this slides the element over to make room to its left) Decrease marker2 by 1.
Insert temp into the location just vacated by a shift.
Increase marker1 by 1.
a. Insertion sort b. bubble sort c. selection sort d. none
Ans: d