B.S.W.E. Bachelor of Software Engineering Algorithms & Data Structures 1 — Questions and Answers
Question 1: What is the time complexity of binary search?
- O(n)
- O(n²)
- O(log n) (Correct answer)
- O(1)
Correct answer: O(log n)
Binary search has O(log n) time complexity because it eliminates half the remaining search space with each comparison.
Question 2: What data structure uses LIFO (Last In, First Out) ordering?
- Queue
- Stack (Correct answer)
- Linked List
- Binary Tree
Correct answer: Stack
A stack uses LIFO ordering where the last element pushed is the first one popped, like a stack of plates.
Question 3: What is the time complexity of inserting an element at the beginning of an array?
- O(1)
- O(log n)
- O(n) (Correct answer)
- O(n²)
Correct answer: O(n)
Inserting at the beginning of an array requires shifting all n existing elements one position to the right, resulting in O(n) time.
Question 4: What is a hash table?
- A sorted array of key-value pairs
- A data structure using a hash function to map keys to array indices for fast lookup (Correct answer)
- A binary tree sorted by key values
- A linked list with index-based access
Correct answer: A data structure using a hash function to map keys to array indices for fast lookup
A hash table uses a hash function to compute an index into an array of buckets, providing average O(1) time for insertions and lookups.
Question 5: What is the fundamental difference between a stack and a queue?
- Stacks have slower performance than queues
- Stacks use LIFO ordering; queues use FIFO ordering for element removal (Correct answer)
- Stacks store numbers; queues store strings
- Stacks are implemented as arrays; queues as linked lists
Correct answer: Stacks use LIFO ordering; queues use FIFO ordering for element removal
Stacks use Last In First Out (LIFO) while queues use First In First Out (FIFO) — the difference is which end elements are removed from.
Question 6: 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 produces maximally unbalanced partitions, such as on already-sorted input.
B.S.W.E. Bachelor of Software Engineering Algorithms & Data Structures 1
What is the time complexity of binary search?