Data Structures and Algorithms Design Quiz-1 -MTech Software Systems- BITS PILANI - WILP

Data Structures and Algorithms Design (SSZG519)- Quiz- 1
MTech Software Systems- WILP(Work Integrated Learning Programmes) 
Birla Institute of Technology and Science, Pilani


1. 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. 2
b. None of the above
c. -1
d. 1
e. 0

Ans: d. 1

2. Suppose T is a proper binary tree with 11 internal nodes. What is the size of  T?

Select one:
a. 21
b. None of the above
c. 22
d. 23
e. 12

Ans: d. 23

3. Which of the following expressions is not sublinear?

Select one:
a. None of the above
b. O(logn)
c.n√n
d. O(log log n)
e. O(n)

Ans: e. O(n)

4. 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. n
b. 5
c. 1
d. 3
e. None of the above

Ans: b. 5

5. 1+3+9+27+... + 3n is

Select one:
a. O(2n)
b. O(n3)
c. None of the above
d. O(4n)

Ans: d. O(4n)

6. Consider a binary tree of size n. The minimum size of array in the array implementation is
Select one:
a. n
b. n2
c. None of the aboven
d. n log n
e. 2n

Ans: a. n

7.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 worst case is

Select one:
a. None of the above
b. 5n+1
c. 5n
d. 5n+3
e. 5n-2

Ans: d. 5n+3

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

Select one:
a. O(n³)
b. O(n²)
c. O(log n)
d. O(n log n)
e. None of the above

Ans: a. O(n³)

9. Stack is empty when t=1

Select one:
a. t=0
b. None of the above
c. t=-1
d. t=1

Ans: c. t=-1

10. Which of the following statements are true. '

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

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

Select one:
a. ii only
b. None of them is true
c. i only
d. Both of them are true

Ans: c. i only

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


Select one:
a. None of the above
b. 5
c. 4
d. 10

Ans: a. None of the above

12. Which of the following formulas in big-O notation best represent the expression n²+3nlogn?

Select one:
a. O(n)
b. O(42)
c. O(n³)
d. O(n²)
e. None of the above

Ans: d. O(n²)

13. Algorithm A uses 5nlog n operations and algorithm B uses n\sqrt n operations. Determine the value n_0 such that A is better than B for n >n_0.
Select one:
a. None of the above
b. 2048
c. 1024
d. 4096
e. 512

Ans: d. 4096

14.Which of the following statements are true?

i. If f(n) is O(n3), then f(n) is o(n3)

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

iii. If f(n) is o(n3), then f(n) is O(n3)

Select one:
a. i only
b. i and iii only
c. All of them are true
d. None of them is true
e. iii only

Ans: e. iii only

15. log2(n/2) is

Select one:
a. None of the above
b. log n2
c. log2 n-1
d. log2 n -2logn +1

Ans: d. log2 n -2logn +1

16.T(n)  = b if n=1

             2T(n-1) +b otherwise

 Then T(n) is

Select one:
a. O(n2)
b. None of the above
c. O(log n)
d. O(2^n)
e. O(nb)

Ans: d. O(2^n)

17. 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. None of the above
b. n(n+1)/2 +7
c. n(n+1)/2 +2
d. n(n+1)/2
e. n(n-1)/2

Ans: c. n(n+1)/2 +2

18. f-r Queue is full in the circular array implementation when n

Select one:
a. r-f=1
b. f-r=1
c. f-r=0
d. None of the above

Ans: d. None of the above

19. Which of the following statements are true?

I) n! Is O(n)

ii) n! Is O(n^n)

iii) n! Is O(2n)

Select one:
a. ii and iii
b. ii only
c. None of the above
d. i only

Ans: b. ii only

20. 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. None of the above
b. O(logn)
c. n√n
d. O(n)
e. O(1)

Ans: d. O(n)


No comments:

Post a Comment