B CompE Bachelor of Computer Engineering Bachelor of Computer Engineering Data Structure 4 — Questions and Answers
Question 1: Which sorting algorithm has the best average-case time complexity among the following?
- Bubble sort
- Selection sort
- Merge sort (Correct answer)
- Insertion sort
Correct answer: Merge sort
Merge sort achieves O(n log n) average-case time, which is optimal for comparison-based sorting.
Question 2: What is the worst-case time complexity of QuickSort?
- O(n log n)
- O(n)
- O(n²) (Correct answer)
- O(log n)
Correct answer: O(n²)
QuickSort degrades to O(n²) when the pivot consistently selects the smallest or largest element (e.g., sorted input).
Question 3: In dynamic programming, what is 'memoization'?
- Sorting results for binary search
- Caching results of subproblems to avoid recomputation (Correct answer)
- Allocating memory at compile time
- Removing duplicate values from an array
Correct answer: Caching results of subproblems to avoid recomputation
Memoization stores the results of expensive function calls so repeated calls with the same inputs return immediately.
Question 4: What does the 'load factor' of a hash table represent?
- The number of hash collisions
- The ratio of stored elements to total bucket count (Correct answer)
- The speed of the hash function
- The size of each bucket
Correct answer: The ratio of stored elements to total bucket count
Load factor = number of elements / number of buckets, and it determines when to resize the hash table.
Question 5: Which of the following is NOT a property of a Red-Black Tree?
- The root is always black
- No two consecutive red nodes exist on any path
- All leaves (NIL) are black
- All paths from a node to leaves must have equal total nodes (Correct answer)
Correct answer: All paths from a node to leaves must have equal total nodes
Red-Black Trees require equal numbers of BLACK nodes on all paths to leaves, not equal total nodes.
Question 6: A trie (prefix tree) is most efficiently used for which operation?
- Sorting integers
- Prefix-based string search and autocomplete (Correct answer)
- Finding shortest paths in graphs
- Storing key-value pairs with integer keys
Correct answer: Prefix-based string search and autocomplete
Tries store strings character by character, enabling O(m) prefix searches where m is the query length.
Question 7: What is the time complexity of finding the lowest common ancestor (LCA) of two nodes in a Binary Search Tree?
- O(n)
- O(log n) for balanced, O(n) worst case (Correct answer)
- O(1)
- O(n log n)
Correct answer: O(log n) for balanced, O(n) worst case
In a balanced BST, LCA is found in O(log n) by comparing node values; in the worst case (skewed tree) it's O(n).
B CompE Bachelor of Computer Engineering Bachelor of Computer Engineering Data Structure 4
Which sorting algorithm has the best average-case time complexity among the following?