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)