Computer Science Algorithms & Data Structures 1 — Questions and Answers
Question 1: What is the time complexity of binary search in a sorted array?
- O(n)
- O(n log n)
- O(log n) (Correct answer)
- O(1)
Correct answer: O(log n)
Binary search works by repeatedly dividing the search interval in half, eliminating a large portion of the data with each comparison. This logarithmic reduction in the search space results in a time complexity of O(log n), making it highly efficient for large sorted arrays.
Question 2: Which data structure is best suited for implementing a LIFO (Last In, First Out) order?
- Queue
- Stack (Correct answer)
- Heap
- Linked List
Correct answer: Stack
A stack is a linear data structure that follows the LIFO (Last In, First Out) principle, meaning the last element added is the first one to be removed. Operations like push (add) and pop (remove) occur at only one end, known as the top of the stack, perfectly aligning with LIFO behavior.
Question 3: What is the primary advantage of using a hash table?
- Maintains sorted order of elements
- Uses less memory than other structures
- Allows fast data retrieval in O(1) time (Correct answer)
- Best suited for sequential access
Correct answer: Allows fast data retrieval in O(1) time
The primary advantage of using a hash table is its ability to provide average O(1) time complexity for data retrieval, insertion, and deletion operations. This constant time access is achieved by mapping keys directly to array indices using a hash function, making it incredibly fast for lookup-intensive tasks.
Question 4: Which sorting algorithm has the best average-case time complexity?
- Bubble Sort
- Selection Sort
- Merge Sort (Correct answer)
- Insertion Sort
Correct answer: Merge Sort
Merge Sort has an average-case time complexity of O(n log n), which is generally considered the best among comparison-based sorting algorithms for large datasets. It achieves this efficiency by consistently dividing the array into halves, sorting them, and then merging them back together.
Question 5: What is the main advantage of using a linked list over an array?
- Faster random access
- Efficient insertions and deletions (Correct answer)
- Lower memory usage
- Better sorting performance
Correct answer: Efficient insertions and deletions
A linked list offers efficient insertions and deletions compared to an array because elements do not need to be shifted when adding or removing nodes. Instead, only the pointers of adjacent nodes need to be updated, which can be done in O(1) time once the position is found.
Question 6: Which traversal method visits all nodes of a binary tree in ascending order?
- Pre-order traversal
- Post-order traversal
- In-order traversal (Correct answer)
- Level-order traversal
Correct answer: In-order traversal
In-order traversal visits the left subtree, then the root node, and finally the right subtree. When applied to a Binary Search Tree (BST), this specific order ensures that all nodes are visited in ascending order of their values. This property makes in-order traversal particularly useful for retrieving sorted data from a BST.
Computer Science Algorithms & Data Structures 1
What is the time complexity of binary search in a sorted array?