BSCS Bachelor of Science in Computer Science: Algorithms and Data Structures 4 ā Questions and Answers
Question 1: What is the main advantage of a B-tree over a binary search tree for database indexing?
- B-trees require less memory per node
- B-trees reduce disk I/O by storing many keys per node and keeping tree height low (Correct answer)
- B-trees support O(1) search
- B-trees automatically sort data during insertion
Correct answer: B-trees reduce disk I/O by storing many keys per node and keeping tree height low
B-trees pack many keys into each node, reducing tree height and the number of disk page reads needed to locate a record.
Question 2: Which of the following correctly describes the difference between a stack and a queue?
- A stack is FIFO; a queue is LIFO
- A stack is LIFO; a queue is FIFO (Correct answer)
- Both are LIFO but differ in implementation
- Both are FIFO but differ in access time
Correct answer: A stack is LIFO; a queue is FIFO
A stack follows Last-In-First-Out (LIFO) order, while a queue follows First-In-First-Out (FIFO) order.
Question 3: What is the recurrence relation for binary search, and what does it solve to?
- T(n) = T(n-1) + O(1), solving to O(n)
- T(n) = 2T(n/2) + O(1), solving to O(n)
- T(n) = T(n/2) + O(1), solving to O(log n) (Correct answer)
- T(n) = T(n/2) + O(n), solving to O(n)
Correct answer: T(n) = T(n/2) + O(1), solving to O(log n)
Binary search discards half the search space each step, giving T(n) = T(n/2) + O(1), which solves to O(log n) by the Master Theorem.
Question 4: In a graph represented as an adjacency matrix, what is the time complexity of checking whether an edge (u, v) exists?
- O(V)
- O(E)
- O(1) (Correct answer)
- O(log V)
Correct answer: O(1)
An adjacency matrix stores a VĆV array, so checking matrix[u][v] is a direct array lookup taking O(1) time.
Question 5: What is the purpose of sentinel nodes in a linked list implementation?
- To store the list's maximum element
- To simplify edge-case handling by eliminating special checks for empty lists or end conditions (Correct answer)
- To mark deleted nodes without removing them
- To provide O(1) random access
Correct answer: To simplify edge-case handling by eliminating special checks for empty lists or end conditions
Sentinel (dummy) head and tail nodes remove the need to handle NULL pointer edge cases, making insert/delete code simpler and less error-prone.
Question 6: Which algorithm solves the all-pairs shortest path problem in O(VĀ³) time?
- Dijkstra's algorithm
- Bellman-Ford algorithm
- Floyd-Warshall algorithm (Correct answer)
- Johnson's algorithm
Correct answer: Floyd-Warshall algorithm
Floyd-Warshall uses a three-nested-loop DP approach to compute shortest paths between all pairs of vertices in O(VĀ³).
Question 7: What is a key characteristic of a greedy algorithm?
- It always backtracks to improve solutions
- It makes the locally optimal choice at each step, hoping to reach a global optimum (Correct answer)
- It divides the problem into independent subproblems recursively
- It stores all subproblem solutions to avoid recomputation
Correct answer: It makes the locally optimal choice at each step, hoping to reach a global optimum
Greedy algorithms commit to the best-looking local choice without reconsidering past decisions, which works correctly only when the greedy choice property holds.
BSCS Bachelor of Science in Computer Science: Algorithms and Data Structures 4
What is the main advantage of a B-tree over a binary search tree for database indexing?