B CompE Bachelor of Computer Engineering Bachelor of Computer Engineering Data Structure 2 ā Questions and Answers
Question 1: Which tree traversal visits nodes in the order: left subtree, root, right subtree?
- Pre-order
- In-order (Correct answer)
- Post-order
- Level-order
Correct answer: In-order
In-order traversal visits left subtree first, then the root, then the right subtree, yielding sorted output for a BST.
Question 2: What is the worst-case time complexity for searching in an unbalanced Binary Search Tree with n nodes?
- O(log n)
- O(n log n)
- O(n) (Correct answer)
- O(1)
Correct answer: O(n)
In the worst case, a BST degrades to a linked list (e.g., sorted insertions), making search O(n).
Question 3: Which data structure is most appropriate for implementing a priority queue efficiently?
- Stack
- Linked list
- Binary heap (Correct answer)
- Hash table
Correct answer: Binary heap
A binary heap supports O(log n) insert and O(log n) extract-min/max, making it ideal for priority queues.
Question 4: In a max-heap, which property must hold for every node?
- Each node is smaller than its children
- Each node is greater than or equal to its children (Correct answer)
- Left child is always greater than right child
- The tree must be a full binary tree
Correct answer: Each node is greater than or equal to its children
The max-heap property requires every parent node to be greater than or equal to its children.
Question 5: What is the time complexity of building a heap from an unsorted array of n elements using the heapify approach?
- O(n log n)
- O(nĀ²)
- O(n) (Correct answer)
- O(log n)
Correct answer: O(n)
Bottom-up heap construction using heapify runs in O(n) due to the mathematical sum of subtree heights.
Question 6: Which graph traversal algorithm uses a queue to explore nodes level by level?
- Depth-First Search
- Dijkstra's algorithm
- Breadth-First Search (Correct answer)
- Prim's algorithm
Correct answer: Breadth-First Search
BFS uses a queue (FIFO) to visit all neighbors of a node before moving to the next depth level.
Question 7: What is the space complexity of Depth-First Search on a graph with V vertices and E edges?
- O(V + E)
- O(V) (Correct answer)
- O(E)
- O(VĀ²)
Correct answer: O(V)
DFS uses a stack (or recursion stack) that holds at most V vertices in the worst case.
B CompE Bachelor of Computer Engineering Bachelor of Computer Engineering Data Structure 2
Which tree traversal visits nodes in the order: left subtree, root, right subtree?