Data Structures Data Structures 2 — Questions and Answers
Question 1: What is the worst-case time complexity of searching for an element in a balanced binary search tree with n nodes?
- O(log n) (Correct answer)
- O(n)
- O(1)
- O(n log n)
Correct answer: O(log n)
A balanced BST halves the search space at each level, giving O(log n) worst-case search time.
Question 2: Which data structure uses the Last-In-First-Out (LIFO) principle?
- Stack (Correct answer)
- Queue
- Linked list
- Hash table
Correct answer: Stack
A stack only allows insertion and removal at the top, so the last element pushed is the first popped.
Question 3: In a singly linked list, what does the last node's next pointer typically reference?
- Null (Correct answer)
- The head node
- The previous node
- Itself
Correct answer: Null
In a standard singly linked list, the tail node's next pointer is null to mark the end of the list.
Question 4: Which of the following operations is most efficient on an array compared to a linked list?
- Random access by index (Correct answer)
- Insertion at the front
- Deletion at the front
- Dynamic resizing
Correct answer: Random access by index
Arrays store elements contiguously, allowing O(1) access by index, while linked lists require O(n) traversal.
Question 5: What happens when two keys hash to the same index in a hash table using chaining?
- Both entries are stored in a linked list at that index (Correct answer)
- The second key overwrites the first
- The table is immediately resized
- The second key is rejected
Correct answer: Both entries are stored in a linked list at that index
Chaining resolves collisions by storing multiple entries in a list (or similar structure) at the same bucket.
Question 6: Which traversal of a binary search tree visits nodes in ascending sorted order?
- In-order (Correct answer)
- Pre-order
- Post-order
- Level-order
Correct answer: In-order
In-order traversal visits left subtree, node, then right subtree, which yields sorted order in a BST.
Question 7: What is the time complexity of enqueue and dequeue operations in a queue implemented with a linked list that tracks both head and tail?
- O(1) for both (Correct answer)
- O(n) for both
- O(1) enqueue, O(n) dequeue
- O(n) enqueue, O(1) dequeue
Correct answer: O(1) for both
With head and tail pointers, insertion at the tail and removal from the head are both constant time.
Data Structures Data Structures 2
What is the worst-case time complexity of searching for an element in a balanced binary search tree with n nodes?