1. Which of the following is not a type of balanced tree?
a) Binary search tree
b) Height-balanced tree
c) AVL tree
d) Red-black tree
Answer: a) Binary search tree
Explanation: Binary search trees are not inherently balanced. While they maintain the binary search property, they can become unbalanced, leading to inefficient operations.
2. In a height-balanced tree, what is the maximum height difference allowed between the left and right subtrees of any node?
a) 1
b) 2
c) 3
d) 4
Answer: a) 1
Explanation: A height-balanced tree ensures that the height difference between the left and right subtrees of any node is at most 1.
3. Which of the following is a property of 2-3 trees?
a) Each node can have up to 2 children
b) Each node can have up to 3 children
c) Each node can have up to 2 keys
d) Each node can have up to 3 keys
Answer: c) Each node can have up to 2 keys
Explanation: In 2-3 trees, each node can have either one key and two children or two keys and three children, making it a balanced tree.
4. B-trees are commonly used in which of the following scenarios?
a) Database indexing
b) Sorting arrays
c) Priority queue implementation
d) Symbol table construction
Answer: a) Database indexing
Explanation: B-trees are often used in database systems for indexing due to their balanced structure and efficient disk access properties.
5. Which traversal technique visits nodes in the following order: root, left subtree, right subtree?
a) In-order
b) Pre-order
c) Post-order
d) Depth-first search
Answer: b) Pre-order
Explanation: Pre-order traversal visits the root node first, then recursively visits the left subtree and right subtree.
6. Which traversal technique visits nodes in the following order: left subtree, root, right subtree?
a) In-order
b) Pre-order
c) Post-order
d) Breadth-first search
Answer: a) In-order
Explanation: In-order traversal visits the left subtree first, then the root node, and finally the right subtree.
7. Which traversal technique visits nodes in the following order: left subtree, right subtree, root?
a) In-order
b) Pre-order
c) Post-order
d) Depth-first search
Answer: c) Post-order
Explanation: Post-order traversal visits the left subtree first, then the right subtree, and finally the root node.
8. Which traversal technique is typically implemented using a stack data structure?
a) Breadth-first search
b) Depth-first search
c) In-order traversal
d) Post-order traversal
Answer: b) Depth-first search
Explanation: Depth-first search is typically implemented using a stack to keep track of nodes to visit.
9. Which search technique explores nodes level by level, starting from the root?
a) Depth-first search
b) Breadth-first search
c) Dijkstra’s algorithm
d) A* search algorithm
Answer: b) Breadth-first search
Explanation: Breadth-first search explores nodes level by level, starting from the root, before moving to the next level.
10. Which complexity class represents problems that are generally believed to be intractable?
a) P
b) NP
c) NP-complete
d) NP-hard
Answer: c) NP-complete
Explanation: NP-complete problems are those in the complexity class NP that are at least as hard as the hardest problems in NP. They are believed to be intractable, although not yet proven to be so.