DSL Previous Years Solved Sample Placement Papers
-
Which one of the following data structures is preferred in database-system implementation?
- a) AVL tree
- b) B-tree
- c) B+ -tree (Ans)
- d) Splay tree
Explanation: The database-system implementations use the B+ -tree data structure because they can be used for multilevel indexing.
-
What is an AVL tree?
- a) a tree which is balanced and is a height balanced tree (Ans)
- b) a tree which is unbalanced and is a height balanced tree
- c) a tree with three children
- d) a tree with at most 3 children
Explanation: It is a self-balancing tree with a height difference of at most 1.
-
Why do we need a binary tree which is height balanced?
- a) to avoid formation of skew trees (Ans)
- b) to save memory
- c) to attain faster memory access
- d) to simplify storing
Explanation: In real-world scenarios, dealing with random values is often not possible. The probability of encountering non-random values (like sequential ones) often leads to skew trees, causing worst-case scenarios. Thus, height balance is maintained by rotations.
-
What is the maximum height of an AVL tree with p nodes?
- a) p
- b) log(p) (Ans)
- c) log(p)/2
- d) p^2
Explanation: The number of nodes in terms of height follows the recurrence relation: N(he) = N(he-1) + 1 + N(he-2). Solving this relation gives N(he) = O(logp) as the worst-case height.
-
To restore the AVL property after inserting an element, do we start at the insertion point and move towards the root of the tree?
- a) true (Ans)
- b) false
Explanation: After insertion, only the path from the insertion point to the root or specific subtrees may become imbalanced in terms of height.
-
Given an empty AVL tree, how would you construct an AVL tree when a set of numbers is given without performing any rotations?
- a) just build the tree with the given input
- b) find the median of the set of elements given, make it the root, and construct the tree (Ans)
- c) use trial and error
- d) use dynamic programming to build the tree
Explanation: Constructing the tree with the median as the root ensures balance without requiring rotations.