DS MCQ
DS MCQ
DS MCQ
The worst case time complexity of AVL tree is better in comparison to binary search tree for
2. Which of the following are two special functions that are meant for handling exception, that occur during
3. Given an empty stack, after performing push (1), push (2), Pop, push (3), push (4), Pop, Pop, push(5), P
of the stack ?
a. 4
b. 3
c. 2
d. 1
Answer: (d).1
4. The total number of spanning trees that can be drawn using five labelled vertices is:
a. 125
b. 64
c. 36
d. 16
Answer: (a).125
5. Suppose there are logn sorted lists of n logn elements each. The time complexity of producing a sorted l
heap data structure)
a. O (n log logn)
b. θ(n logn)
c. Ω(n logn)
d. Ω(n3/2)
6. The Object Modelling Technique (OMT) uses the following three kinds of model to describe a system
a. Run-length coding
b. Huffman coding
c. Predictive coding
d. LZW coding
Answer: (d).LZW coding
a. h' is always 0
b. g is always 1
a. -3/8
b. -8/3
c. 24
d. -24
Answer: (d).-24
10. If the queue is implemented with a linked list, keeping track of a front pointer and a rear pointer, which of
during an insertion into a non-empty queue?
a. Diagonalization
b. Communitivity
c. Mathematical Induction
d. Matrix Multiplication
Answer: (c).Mathematical Induction
12. For any B-tree of minimum degree t ≥ 2, every node other than the root must have atleast keys and e
____ keys.
a. t -1, 2t + 1
b. t + 1, 2t + 1
c. t-1, 2t-1
d. t+ 1, 2t-1
Answer: (c).t-1, 2t-1
13. Given two sorted list of size 'm' and 'n' respectively. The number of comparison needed in the worst case
be
a. mxn
b. max (m, n)
c. min (m, n)
d. m +n-1
Answer: (d).m +n-1
codes:
abcd
a. iii iv i ii
b. iv iii ii i
c. ii iv i iii
d. ii iii iv i
Answer: (a).iii iv i ii
15. The compiler converts all operands up to the type of the largest operand is called
a. Type Promotion
b. Type Evaluation
c. Type Conversion
d. Type Declaration
Answer: (a).Type Promotion
16. _____________ comparisons are necessary in the worst case to find both the maximum and minimum
a. 2n-2
b. n + floor(log n) -2
c. floor(3n/2) -2
d. 2 log n -2
Answer: (c).floor(3n/2) -2
17. Let A and B be two n x n matrices,The efficient algorithm to multiply the two matrices , has the time comp
a. O(n^3)
b. O(n^2.81)
c. O(n^2.67)
d. O(n^2)
Answer: (b).O(n^2.81)
18. Assuming there are n keys and each key is in the range [0, m - 1]. The run time of bucket sort is
a. O(n)
b. O(n log n)
c. O(n log m)
d. O(n+n)
Answer: (d).O(n+n)
19. You have to sort a list L, consisting of a sorted list followed by a few 'random' elements. Which of the foll
most suitable for such a task?
a. Bubble sort
b. Selection sort
c. Quick sort
d. Insertion sort
Answer: (d).Insertion sort
a. n nodes
b. log2 n nodes
c. 2n-1 nodes
d. 2^n nodes
Answer: (c).2n-1 nodes
21. How many PUSH and POP operations will be needed to evaluate the following expression by reverse po
(A * B) + (C * D/E)?
22. Consider an array A[20. 10], assume 4 words per memory cell and the base address of array A is 100. W
Assume row major storage.
a. 560
b. 565
c. 570
d. 575
Answer: (a).560
23. Convert the following infix expression into its equivalent post fix expression (A + B^D)/(E - F) + G
a. ABD^ + EF-/G+
b. ABD + ^EF-/G+
c. ABD + ^EF/-G+
d. ABD^ + EF/-G+
Answer: (a).ABD^ + EF-/G+
a. Ω (n)
b. Ω(/gn)
c. Ω(n/gn)
d. Ω(n^2)
Answer: (d).Ω(n^2)
code:
a b c d
a. iv ii i iii
b. ii iv i iii
c. iv ii iii i
d. iii ii iv i
Answer: (d).iii ii iv i
26. Suppose that we have numbers between 1 and 1000 in a binary search tree and we want to search for th
following sequences could not be the sequence of nodes examined ?
b. 926,222,913,246,900,260,364,365
c. 927,204,913, 242,914,247,365
Answer: (c).927,204,913, 242,914,247,365
27. Converting a primitive type data into its corresponding wrapper class object instance is called
a. Boxing
b. Wrapping
c. Instantiation
d. Autoboxing
Answer: (d).Autoboxing
29. The inorder and preorder Traversal of binary Tree are dbeafcg and abdecfg respectively.The post order
a. dbefacg
b. debfagc
c. dbefcga
d. debfgca
Answer: (d).debfgca
30. Level order Traversal of a rooted Tree can be done by starting from root and performing
c. Root search
d. Deep search