CPA Data Structures & Algorithms 3 — Questions and Answers
Question 1: What property must every node in a max-heap satisfy?
- Its value is less than both children
- Its value is greater than or equal to its children's values (Correct answer)
- It has exactly two children
- Its left child is always larger than its right child
Correct answer: Its value is greater than or equal to its children's values
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?
- Bubble sort
- Insertion sort
- Quick sort (Correct answer)
- Selection sort
Correct answer: Quick sort
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:
- Complete graph
- Bipartite graph
- Directed graph
- Acyclic graph (Correct answer)
Correct answer: Acyclic graph
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?
- The cost of the most expensive single operation
- The average cost per operation over a sequence of operations (Correct answer)
- The minimum possible cost of any operation
- The cost after removing outlier operations
Correct answer: The average cost per operation over a sequence of operations
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?
- Queue
- Stack (Correct answer)
- Binary search tree
- Hash table
Correct answer: Stack
A stack's LIFO property naturally models back navigation — the last page visited is the first retrieved.
Question 6: The time complexity of accessing an element by index in a dynamic array (ArrayList) is:
- O(n)
- O(log n)
- O(n log n)
- O(1) (Correct answer)
Correct answer: O(1)
Dynamic arrays store elements contiguously, so index-based access requires only a single memory address calculation, giving O(1).
Question 7: Which of the following is a stable sorting algorithm?
- Quick sort
- Heap sort
- Merge sort (Correct answer)
- Selection sort
Correct answer: Merge sort
Merge sort preserves the relative order of equal elements, making it a stable sorting algorithm.
CPA Data Structures & Algorithms 3
What property must every node in a max-heap satisfy?