Data Structures :: Searching & Sorting

Home > Data Structures > Searching & Sorting > General Questions

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

1 / 65

 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
0
Solv. Corr.
0
Solv. In. Corr.
0
Attempted
0 M:0 S
Avg. Time

2 / 65

 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
0
Solv. Corr.
0
Solv. In. Corr.
0
Attempted
0 M:0 S
Avg. Time

3 / 65

 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
0
Solv. Corr.
0
Solv. In. Corr.
0
Attempted
0 M:0 S
Avg. Time

4 / 65

 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;
}

Which oe of the following statements about the function Process Array is CORRECT?

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
0
Solv. Corr.
0
Solv. In. Corr.
0
Attempted
0 M:0 S
Avg. Time

5 / 65

 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
0
Solv. Corr.
0
Solv. In. Corr.
0
Attempted
0 M:0 S
Avg. Time

6 / 65

 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
0
Solv. Corr.
0
Solv. In. Corr.
0
Attempted
0 M:0 S
Avg. Time

7 / 65

 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
0
Solv. Corr.
0
Solv. In. Corr.
0
Attempted
0 M:0 S
Avg. Time

8 / 65

 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
0
Solv. Corr.
0
Solv. In. Corr.
0
Attempted
0 M:0 S
Avg. Time

9 / 65

 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

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

10 / 65

 The quick sort algorithm exploit _________ design technique

AGreedy

BDynamic programming

CDivide and Conquer

DBacktracking

Answer: Option C

Explanation:

Here is no explanation for this answer

Workspace