SP Data Structures and Algorithms 1 — Questions and Answers
Question 1: What is the time complexity of searching in a balanced binary search tree?
- O(log n) (Correct answer)
- O(n)
- O(1)
- O(n^2)
Correct answer: O(log n)
A balanced BST halves the search space at each step, resulting in logarithmic time complexity.
Question 2: Which data structure operates on a Last-In-First-Out (LIFO) principle?
- Stack (Correct answer)
- Queue
- Linked List
- Hash Table
Correct answer: Stack
A stack follows LIFO ordering — the most recently added element is the first to be removed.
Question 3: What is a hash collision?
- When two different keys produce the same hash value (Correct answer)
- When a hash table runs out of memory
- When a hash function returns null
- When two hash tables are merged
Correct answer: When two different keys produce the same hash value
A hash collision occurs when different inputs map to the same index in a hash table, requiring collision resolution.
Question 4: What is the main advantage of a linked list over an array?
- Efficient insertion and deletion without shifting elements (Correct answer)
- Faster random access to elements
- Less memory usage per element
- Simpler implementation
Correct answer: Efficient insertion and deletion without shifting elements
Linked lists allow O(1) insertion and deletion at known positions without moving other elements, unlike arrays.
Question 5: Which sorting algorithm has the best average-case time complexity?
- Merge Sort with O(n log n) (Correct answer)
- Bubble Sort with O(n^2)
- Selection Sort with O(n^2)
- Insertion Sort with O(n^2)
Correct answer: Merge Sort with O(n log n)
Merge Sort consistently achieves O(n log n) time complexity using a divide-and-conquer approach.
Question 6: What is the purpose of a queue data structure?
- To process elements in First-In-First-Out (FIFO) order (Correct answer)
- To sort elements automatically
- To store elements in sorted order
- To enable random access to elements
Correct answer: To process elements in First-In-First-Out (FIFO) order
Queues process elements in FIFO order, like a line at a store — first to arrive is first to be served.
SP Data Structures and Algorithms 1
What is the time complexity of searching in a balanced binary search tree?