CPA Data Structures & Algorithms 3

Question 1

What property must every node in a max-heap satisfy?

Accepted Answer

Its value is greater than or equal to its children's values

Answer

In a max-heap, each parent node's value must be greater than or equal to the values of its children.

Question 2

Which sorting algorithm has the best average-case performance of O(n log n) and is commonly used in standard library implementations?

Accepted Answer

Quick sort

Answer

Quick sort achieves O(n log n) average-case and is favored in practice due to cache efficiency and low constant factors.

Question 3

In graph theory, a graph with no cycles is called a:

Accepted Answer

Acyclic graph

Answer

An acyclic graph contains no cycles; a directed acyclic graph (DAG) is a common special case.

Question 4

What does the 'amortized' cost concept mean in algorithm analysis?

Accepted Answer

The average cost per operation over a sequence of operations

Answer

Amortized analysis spreads the total cost of a sequence of operations over all operations to give an average per-operation cost.

Question 5

Which data structure is most appropriate for implementing a browser's back-navigation history?

Accepted Answer

Stack

Answer

A stack's LIFO property naturally models back navigation — the last page visited is the first retrieved.

(CPA) Certified Associate Programmer Practice Test