BCS Data Structures and Algorithms 3

Question 1

What property must a min-heap satisfy?

Accepted Answer

Every parent is less than or equal to its children

Answer

A min-heap requires every parent node to be less than or equal to its children, ensuring the minimum is always at the root.

Question 2

What is the best-case time complexity of Insertion Sort?

Accepted Answer

O(n)

Answer

Insertion Sort achieves O(n) in the best case when the input array is already sorted, requiring only one comparison per element.

Question 3

Which graph algorithm detects negative weight cycles?

Accepted Answer

Bellman-Ford algorithm

Answer

Bellman-Ford can detect negative weight cycles by checking if distances can still be reduced after V-1 relaxations.

Question 4

What is the height of a complete binary tree with n nodes?

Accepted Answer

O(log n)

Answer

A complete binary tree with n nodes has a height of floor(log₂ n), which is O(log n).

Question 5

Which abstract data type operates on the principle of FIFO?

Accepted Answer

Queue

Answer

A queue follows First In, First Out (FIFO) ordering, where elements are inserted at the rear and removed from the front.

BCS - Bachelor Of Computer Science Degree Practice Test