BSCS Bachelor of Science in Computer Science: Algorithms and Data Structures 4

Question 1

What is the main advantage of a B-tree over a binary search tree for database indexing?

Accepted Answer

B-trees reduce disk I/O by storing many keys per node and keeping tree height low

Answer

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?

Accepted Answer

A stack is LIFO; a queue is FIFO

Answer

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?

Accepted Answer

T(n) = T(n/2) + O(1), solving to O(log n)

Answer

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?

Accepted Answer

O(1)

Answer

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?

Accepted Answer

To simplify edge-case handling by eliminating special checks for empty lists or end conditions

Answer

Sentinel (dummy) head and tail nodes remove the need to handle NULL pointer edge cases, making insert/delete code simpler and less error-prone.

BSCS - Bachelor of Science in Computer Science Practice Test