Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors

Trees, Graphs, and NP-Completeness MCQ

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
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
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
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
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
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
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?

b) Depth-first search
c) In-order traversal
d) Post-order traversal
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