BITS WILP Data Structures and Algorithms Design Quiz-1 2017-H1

Question 1

Consider the ArrayFind algorithm.

input : an element x, n, an array A of n integers

Output : The index i such that A[i]=x or -1 if no element in A is equal to x

i ← 0

while i <n do

   if x = A[i] then

        return i

   else

   i ←i+1

return -1

 The number of primitive operations for the best case is

Select one:

a. 5n+3

b. 5n-2

c. None of the above

d. 5n

e. 5n+1

Feedback

The correct answer is: 5n+1

Question 2

T(n) = b if n=1

          2T(n-1) +b otherwise

Then T(n) is

Select one:

a. O(2^n)

b. O(n)

c. O(n^b)

d. None of the above

e. O(n2)

Feedback

The correct answer is: O(2^n)

Question 3

1+3+9+27+... +3^n

Select one:

a. O(n^3)

b. O(2^n)

c. O(n)

d. O(4^n)

e. None of the above

Feedback

The correct answer is: O(4^n)

Question 4

Algorithm Loop(n)

p ← 1

for i← 1 to n do

       p ← p.i

return p

What is the value of Loop(6)?

Select one:

a. 720

b. 5

c. 1

d. None of the above

e. 120

Feedback

The correct answer is: 720

Question 5

Which of these is the correct big-O expression for 1+4+9+...+(n+2)²?

Select one:

a. O(log n)

b. O(n log n)

c. O(n²)

d. None of the above

e. O(n³)

Feedback

The correct answer is: O(n³)

Question 6

Consider the ArrayFind algorithm.

input : an element x, n, an array A of n integers

Output : The index i such that A[i]=x or -1 if no element in A is equal to x

i ← 0

while i <n do

   if x = A[i] then

       return i

   else

   i ←i+1

return -1

The number of primitive operations for the best case is

Select one:

a. 5

b. n/2

c. None of the above

d. 4

e. n

Feedback

The correct answer is: 5

Question 7

Consider the following recurrence relation.

T(n) = 5 if n <= 2

           T(n-1)+ n otherwise

Closed form solution for T(n) is

Select one:

a. n(n+1)/2 +2

b. n(n+1)/2 +7

c. n(n-1)/2

d. n(n+1)/2

e. None of the above

Feedback

The correct answer is: n(n+1)/2 +2

Question 8

Which of the following statements are true? 

i. If f(n) is O(n^3), then f(n)+10n^3 is O(n^3)

ii. If f(n) is O(n^3), then f(n) is Θ(n^3)

iii. If f(n)+10n^3 is O(n^3), then f(n) is O(n^3)

Select one:

a. None of the above

b. All of them are true

c. iii only

d. i only

e. i and iii only

Feedback

The correct answer is: i and iii only

Question 9

If C =1, what would be the appropriate value of n0 to show that 2n² +9 is O( n²)?

Select one:

a. 4

b. None of the above

c. 100

d. 5

e. 10

Feedback

The correct answer is: None of the above

Question 10

Consider the array implementation of Stack ADT with array size N. 

Which of the following statements are true? 

1. We can store at max N-1 elements in the stack
2. Stack ADT supports inserting elements anywhere

Select one:

a. Both of them are true

b. i only

c. ii only

d. None of them are true

Feedback

The correct answer is: None of them are true

Question 11

Which of the following statements are true?

i) n! is O(n)

ii) n! is O(n^n)

iii) n! is O(2^n)

Select one:

a. i only

b. None of the above

c. ii and iii only

d. i and iii only

e. ii only

Feedback

The correct answer is: ii only

Question 12

Algorithm Loop(n)

p ← 1

for i← 1 to n do

    p ← p.i

return p

Give a big-Oh characterization for the above algorithm. 

Select one:

a. O(1)

b. O(√n)

c. O(log n)

d. O(n)

e. None of the above

Feedback

The correct answer is: O(n)

Question 13

Which of the following statements are true.

i) (2^(n+1)) is O(2^(n/2))

ii) (2^(2n)) is O(2^n)

Select one:

a. i only

b. None of them true

c. Both of them are true

d. None of the above

e. ii only

Feedback

The correct answer is: None of them true

Question 14

Consider the array implementation of Stack ADT S and we modify the Pop operation as follows.

Algorithm pop()

if isEmpty() then

     return Error

dummy ← ???

t ← t-1

return dummy

What should ??? be replaced with?

Select one:

a. S[t+1]

b. S[t]

c. None of the above

d. S[t-1]

e. S[0]

Feedback

The correct answer is: S[t]

Question 15

Algorithm A uses 5nlog n operations and algorithm B uses n√

operations. Determine the value n0 such that A is better than B for n > n0

Select one:

a. 2048

b. 1024

c. None of the above

d. 512

e. 4096

Feedback

The correct answer is: 512

Question 16

Consider the following stack operations. new(), push(a), push(b), pop(), push (c), pop(), push(5). what is the index of top element in the array implementation?

Select one:

a. 0

b. -1

c. 2

d. 1

e. None of the above

Feedback

The correct answer is: 1

Question 17

Which of the following formulas in big-O notation best represent the expression 10n²+5nlogn?

Select one:

a. None of the above

b. O(n)

c. O(n³)

d. O(42)

e. O(n²)

Feedback

The correct answer is: O(n²)

Question 18

Which of the following expressions is not sublinear? 

Select one:

a. O(logn)

b. O(n)

c. None of the above

d. O(n√)

e. O(log log n)

Feedback

The correct answer is: O(n)

Question 19

Log^2 (n/2) is

Select one:

a. log^2 (n)−2logn+1

b. log^2 (n) -1

c. None of the above

d. log log (n/2)

e. log(n2)

Feedback

The correct answer is: log^2 (n)−2logn+1

Question 20

Consider the Array implementation for Stack ADT. Stack is empty when 

Select one:

a. t=1

b. t=0

c. None of the above

d. t= -1

Feedback

The correct answer is: t= -1