DAA Quiz 1

Where is linear searching used?

• When the list has only a few elements

• When performing a single search in an unordered list

• Used all the time

• When the list has only a few elements and When performing a single search in an unordered list

What is the worst case for linear search?

• O(nlogn)

• O(logn)

• O(n)

• O(1)

Given an input arr = {2,5,7,99,899}; key = 899; What is the level of recursion?

• 5

• 2

• 3

• 4

Merge sort is preferred for arrays over linked lists.

• True

• False

Choose the correct statement from the following.

• branch and bound is not suitable where a greedy algorithm is not applicable

• branch and bound divides a problem into at least 2 new restricted sub problems

• backtracking divides a problem into at least 2 new restricted sub problems

• branch and bound is more efficient than backtracking

Which of the following is false about the Kruskal’s algorithm?

• It constructs MST by selecting edges in increasing order of their weights

• It is a greedy algorithm

• It uses union-find data structure

• It can accept cycles in the MST

Suppose two activities A and B, having start and finish time as S_A, F_A and S_B, F_B respectively. Both the activities are said to be compatible, under which of the following condition?

• S_A = F_B

• S_A > F_B

• S_A >= F_B or S_B >= F_A

• S_A >= F_B and S_B = F_A

Consider the following algorithm to find the solution of the activity selection problem. Which of the following option is best suited to fill the blank?

Sort the given activity List

display the first activity

set i = 1

for j = 1 to n-1 do

if begin time of activity[j] >= completion of activity[i] then

___________

i = j

• display the ith activity

• display the jth activity

• discard the activity

• increment j

Time complexity to find the solution of activity selection problem takes O(n log n) time, when the list is not sorted.

• True

• False

In Huffman coding, data in a tree always occur?

• roots

• leaves

• left sub trees

• right sub trees