BCS Data Structures and Algorithms 1 — Questions and Answers
Question 1: What is the time complexity of binary search on a sorted array of n elements?
- O(n)
- O(log n) (Correct answer)
- O(n²)
- O(1)
Correct answer: O(log n)
Binary search repeatedly halves the search space, resulting in O(log n) time complexity.
Question 2: Which data structure uses LIFO (Last In, First Out) ordering?
- Queue
- Linked List
- Stack (Correct answer)
- Heap
Correct answer: Stack
A stack follows LIFO ordering, where the last element pushed is the first one popped.
Question 3: 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²) in the worst case when the pivot consistently picks the smallest or largest element.
Question 4: In a binary search tree (BST), where is the minimum value located?
- Root node
- Rightmost node
- Leftmost node (Correct answer)
- Any leaf node
Correct answer: Leftmost node
In a BST, the minimum value is always found by traversing to the leftmost node.
Question 5: Which sorting algorithm has a guaranteed O(n log n) time complexity in all cases?
- QuickSort
- BubbleSort
- MergeSort (Correct answer)
- InsertionSort
Correct answer: MergeSort
MergeSort always divides the array in half and merges, guaranteeing O(n log n) in best, average, and worst cases.
Question 6: What is the space complexity of a recursive Fibonacci function without memoization?
- O(1)
- O(n) (Correct answer)
- O(n²)
- O(2^n)
Correct answer: O(n)
The recursive call stack grows to depth n, resulting in O(n) space complexity.
BCS Data Structures and Algorithms 1
What is the time complexity of binary search on a sorted array of n elements?