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

Every parent is greater than its children

Answer

Left child is always smaller than right child

Answer

All leaves are at the same level

Question 2

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

Accepted Answer

O(n)

Answer

O(n²)

Answer

O(n log n)

Answer

O(1)

Question 3

Which graph algorithm detects negative weight cycles?

Accepted Answer

Bellman-Ford algorithm

Answer

Dijkstra's algorithm

Answer

Prim's algorithm

Answer

Kruskal's algorithm

Question 4

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

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(n²)

Answer

O(√n)

Question 5

Which abstract data type operates on the principle of FIFO?

Accepted Answer

Queue

Answer

Stack

Answer

Tree

Answer

Graph

Question 6

Dynamic programming is best used when a problem exhibits which two properties?

Accepted Answer

Overlapping subproblems and optimal substructure

Answer

Greedy choice and optimal substructure

Answer

Divide and conquer and memoization

Answer

Recursion and backtracking