Data Structures :: Searching & Sorting

NA
SHSTTON
26
Solv. Corr.
99
Solv. In. Corr.
125
Attempted
0 M:0 S
Avg. Time

1 / 66

Selection sort and quicksort both fall into the same category of sorting algorithms. What is this category?


AO(n log n) sorts

BDivide-and-conquer sorts

CInterchange sorts

DAverage time is quadratic

 View Answer |  Discuss in Forum |  Workspace | Asked In BOA (Bank of America) |

Answer: Option C

Explanation:

Selection sort is not O(n log n) and not a Divide-conquer sort too and Average time of quicksort is not quadratic.

Workspace

NA
SHSTTON
154
Solv. Corr.
101
Solv. In. Corr.
255
Attempted
0 M:6 S
Avg. Time

2 / 66

Choose the correct option.

Which of the following algorithmic paradigm is used in the merge sort?


ADynamic Programming

BBackTracking

CGreedy method

DDivide and Conquer

Answer: Option D

Explanation:

Here is no explanation for this answer

Workspace

NA
SHSTTON
119
Solv. Corr.
121
Solv. In. Corr.
240
Attempted
0 M:15 S
Avg. Time

3 / 66

Choose the correct option.

What is the worst case performance of Selection sort algorithm?


AO(log n)

BO(n* n)

CO(n)

DO(n log n)

Answer: Option B

Explanation:

Here is no explanation for this answer

Workspace

NA
SHSTTON
58
Solv. Corr.
135
Solv. In. Corr.
193
Attempted
0 M:9 S
Avg. Time

4 / 66

Choose the correct option.

Let P be a quick sort program to sort numbers in ascending order using the first element as the pivot. Let t1 and t2 be the number of comparisons made by P for the input [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?


At1 = 5

Bt1 < t2

Ct1 > t2

Dt1 = t2

Answer: Option C

Explanation:

When first element or last element is chosen as pivot, Quick Sort's worst case occurs for the sorted arrays.

In every step of quick sort, numbers are divided as per the following recurrence.

T(n) = T(n-1) + O(n)

Workspace

NA
SHSTTON
58
Solv. Corr.
78
Solv. In. Corr.
136
Attempted
1 M:39 S
Avg. Time

5 / 66

Which one of the following statements about the function Process Array is CORRECT?
Consider the C function given below. Assume the array listA contains (n>0) elements, sorted in ascending order.

int Process array (int * list A, int x, int n)
{
int i, j, k;
i =0;j=n-1;
do {
k = (i+j)/2;
if (x<=list A[k])
j=k-1;
if (list A[k] <=x)
i =k+1;
} while (i <=j);
if (list A[k] == x)
return (k);
else
return -1;
}

AIt will run into an infinite loop when x is not in listA

BIt is an implementation of binary search.

CIt will always find the maximum element in listA.

DIt will return -1 even when x is present in listA.

Answer: Option B

Explanation:

Here is no explanation for this answer

Workspace

NA
SHSTTON
81
Solv. Corr.
120
Solv. In. Corr.
201
Attempted
0 M:0 S
Avg. Time

6 / 66

Choose the correct option.

What sorting algos have their best and worst case times equal ?


Aheap and selection sort

Binsersition sort & merge sort

Cmerge sort and heap sort

DNone of these

Answer: Option C

Explanation:

O(nlogn) for mergesort and heap sort

Workspace

NA
SHSTTON
117
Solv. Corr.
81
Solv. In. Corr.
198
Attempted
0 M:3 S
Avg. Time

7 / 66

Choose the correct option.

What data structures you should use for dictionary searching and it should be capable of doing spell check also ?


Aarray

BHashing

Clinked list

DTree

Answer: Option B

Explanation:

Here is no explanation for this answer

Workspace

NA
SHSTTON
95
Solv. Corr.
93
Solv. In. Corr.
188
Attempted
0 M:0 S
Avg. Time

8 / 66

Choose the correct option.

In worst case Quick Sort has order


AO(n log n)

B\(O\left(n^{2}\right)\)

CO(log n)

D\(O\left(\frac{n^{2}}{4}\right)\)

Answer: Option B

Explanation:

The worst case time complexity of a typical implementation of QuickSort is O(n2)

Workspace

NA
SHSTTON
22
Solv. Corr.
159
Solv. In. Corr.
181
Attempted
0 M:10 S
Avg. Time

9 / 66

Choose the correct option.

A sort which relatively passes through a list to exchange the first element with any element less than it and then repeats with a new first element is called


Ainsertion sort.

Bselection sort.

Cheap sort.

Dquick sort.

Answer: Option D

Explanation:

The right answer is the Selection Sort.

Workspace

NA
SHSTTON
83
Solv. Corr.
86
Solv. In. Corr.
169
Attempted
0 M:3 S
Avg. Time

10 / 66

Choose the correct option.

Which of the following sorting algorithms does not have a worst case running time of O(n^2)?


AInsertion sort

BMerge sort

CQuick sort

DBubble sort

Answer: Option B

Explanation:

Here is no explanation for this answer

Workspace