Algorithm MCQ (Multiple Choice Questions), Algorithm Online Quiz

1 .

Identify the approach followed in Floyd Warshall's algorithm?

A)

Backtracking

B)

Greedy Technique

C)

Linear programming

D)

Dynamic Programming

Correct Answer : Option (D) : Dynamic Programming

2 .

Another name of the fractional knapsack is?

A)

0/1 knapsack problem

B)

Continuous Knapsack Problem

C)

Divisible knapsack problem

D)

Non-continuous knapsack problem

Correct Answer : Option (B) : Continuous Knapsack Problem

3 .

In what time complexity can we find the diameter of a binary tree optimally?

A)

O(V)

B)

O(E)

C)

O(V + E)

D)

O(V * log E)

Correct Answer : Option (C) : O(V + E)

4 .

What will be the best sorting algorithm, given that the array elements are small (<= 1e6)?

A)

Merge Sort

B)

Bubble Sort

C)

Heap Sort

D)

Counting Sort

Correct Answer : Option (D) : Counting Sort

5 .

What is the time complexity of the Sieve of Eratosthenes to check if a number is prime?

A)

O(nlog(logn)) Precomputation, O(1) for check.

B)

O(n) Precomputation, O(1) for the check.

C)

O(n) Precomputation, O(logn) for check.

D)

O(n * logn) Precomputation, O(logn) for check.

Correct Answer : Option (A) : O(nlog(logn)) Precomputation, O(1) for check.

6 .

The recurrence relation that arises in relation with the complexity of the binary search is

A)

T(n)= T(n/2)+n

B)

T(n)= T(n/2)+k

C)

T(n)= 2T(n/2)+k

D)

T(n)= T(n/2)+logn

Correct Answer : Option (B) : T(n)= T(n/2)+k

7 .

What is the Time complexity of insertion sort?

A)

Quadratic

B)

Cubic

C)

Linear

D)

Exponential

Correct Answer : Option (A) : Quadratic

8 .

The time complexity of the non-deterministic algorithm is always__________

A)

equal to deterministic algorithm

B)

greater than deterministic algorithm

C)

less than deterministic algorithm

D)

None of the above

Correct Answer : Option (C) : less than deterministic algorithm

9 .

Out of 4 distinct keys how many distinct primary keys can be created?

A)

5

B)

14

C)

20

D)

45

Correct Answer : Option (B) : 14

Explanation :

The no of keys given are 4

apply the formula Bn=1/(n+1)*(2n!/n!n!)

where B is the binary tree and n is the number of keys.

Bn=1/(4+1)*(8!/4!4!)

Bn=1/5*(8*7*6*5*4!)/4!4!

Bn=8*7*9*6/(4*3*2)

Bn=56/4

Bn=14

Hence, the total no of binary trees with n=4 is 14.

10 .

Algorithms: Consider a B-tree of order 4 and is built from scratch by 10 successive insertions. What would be the maximum number of node splitting operations that take place?

A)

6

B)

4

C)

3

D)

2

Correct Answer : Option (D) : 2

Explanation :

A B-tree of order m contains n records and each contains b records on average then the tree will have about n/b leaves. If we split k nodes along the path from leaves then

k<=1+logm/2 [n/b]

here n=10,b=3,m=4 so

k<=1+log4/2 [n/b]

k<=1+log2 4

k<= 1+2

k<=3