B CompE Bachelor of Computer Engineering Bachelor of Computer Engineering Data Structure 4

Question 1

Which sorting algorithm has the best average-case time complexity among the following?

Accepted Answer

Merge sort

Answer

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?

Accepted Answer

O(n²)

Answer

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

Accepted Answer

Caching results of subproblems to avoid recomputation

Answer

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?

Accepted Answer

The ratio of stored elements to total bucket count

Answer

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?

Accepted Answer

All paths from a node to leaves must have equal total nodes

Answer

Red-Black Trees require equal numbers of BLACK nodes on all paths to leaves, not equal total nodes.

B CompE Bachelor of Computer Engineering Practice Test