PRG 420 Java Programming I
Finals Mock Exam Review
(Questions & Solutions)
2025
©2025
, Question 1:
A software engineer needs a self-balancing binary search tree that
provides faster lookup speeds by enforcing strict balance but may require
more frequent rotations during insertions and deletions. Which data
structure best meets these criteria?
- A. Red‑Black Tree
- B. AVL Tree
- C. Splay Tree
- D. Treap
ANS: B. AVL Tree
Rationale: AVL trees maintain a stricter balance (the height difference
between left and right subtrees is at most one), which yields faster
lookups compared to red‑black trees. However, this strict balancing
sometimes cost more rotations during insertions and deletions.
---
Question 2:
For implementing an efficient priority queue where operations such as
insertion and extract‑min must be performed frequently, which data
structure is most effective?
- A. Binary search tree
- B. Binary heap
- C. Linked list
- D. Hash table
ANS: B. Binary heap
Rationale: Binary heaps provide O(log n) insertion and deletion
(extract‑min or extract‑max) time, making them ideal for implementing
priority queues where such operations are frequent.
---
©2025
, Question 3:
In applications such as search engines and autocomplete systems, which
data structure is best suited for efficient prefix-based searches?
- A. Hash table
- B. Trie
- C. Binary search tree
- D. Graph
ANS: B. Trie
Rationale: Tries (prefix trees) are designed to store strings in a tree-like
structure, enabling very fast prefix searches. Although hash tables are
efficient for exact matches, they are not inherently designed for prefix
queries.
---
Question 4:
Which data structure is the optimal choice for implementing an
associative array (dictionary) that supports average-case constant-time
search, insertion, and deletion, assuming a well-designed hash function?
- A. Binary search tree
- B. Trie
- C. Hash table
- D. Skip list
ANS: C. Hash table
Rationale: Hash tables generally provide average-case O(1) operations
for search, insertion, and deletion when collisions are minimized by a
good hash function.
---
Question 5:
A project calls for dynamic maintenance of a sorted order of elements
©2025
, along with support for rank queries (e.g., finding the kth smallest
element) in O(log n) time. Which augmented data structure meets these
requirements?
- A. Order-statistic tree
- B. R-Tree
- C. Splay tree
- D. Linked list
ANS: A. Order-statistic tree
Rationale: Order-statistic trees are augmented binary search trees
(often based on red‑black trees) that store subtree sizes, enabling
efficient rank queries and selection operations.
---
Question 6:
Which data structure is most commonly used to implement the Depth-
First Search (DFS) algorithm in graph traversal?
- A. Queue
- B. Stack
- C. Priority queue
- D. Hash table
ANS: B. Stack
Rationale: DFS can be implemented using either recursion (implicitly
using the call stack) or an explicit stack data structure to keep track of
nodes to be visited.
---
Question 7:
To resolve collisions in a hash table, one common technique involves
maintaining a linked list of entries for each hash bucket. This method is
known as:
- A. Open addressing
©2025
Finals Mock Exam Review
(Questions & Solutions)
2025
©2025
, Question 1:
A software engineer needs a self-balancing binary search tree that
provides faster lookup speeds by enforcing strict balance but may require
more frequent rotations during insertions and deletions. Which data
structure best meets these criteria?
- A. Red‑Black Tree
- B. AVL Tree
- C. Splay Tree
- D. Treap
ANS: B. AVL Tree
Rationale: AVL trees maintain a stricter balance (the height difference
between left and right subtrees is at most one), which yields faster
lookups compared to red‑black trees. However, this strict balancing
sometimes cost more rotations during insertions and deletions.
---
Question 2:
For implementing an efficient priority queue where operations such as
insertion and extract‑min must be performed frequently, which data
structure is most effective?
- A. Binary search tree
- B. Binary heap
- C. Linked list
- D. Hash table
ANS: B. Binary heap
Rationale: Binary heaps provide O(log n) insertion and deletion
(extract‑min or extract‑max) time, making them ideal for implementing
priority queues where such operations are frequent.
---
©2025
, Question 3:
In applications such as search engines and autocomplete systems, which
data structure is best suited for efficient prefix-based searches?
- A. Hash table
- B. Trie
- C. Binary search tree
- D. Graph
ANS: B. Trie
Rationale: Tries (prefix trees) are designed to store strings in a tree-like
structure, enabling very fast prefix searches. Although hash tables are
efficient for exact matches, they are not inherently designed for prefix
queries.
---
Question 4:
Which data structure is the optimal choice for implementing an
associative array (dictionary) that supports average-case constant-time
search, insertion, and deletion, assuming a well-designed hash function?
- A. Binary search tree
- B. Trie
- C. Hash table
- D. Skip list
ANS: C. Hash table
Rationale: Hash tables generally provide average-case O(1) operations
for search, insertion, and deletion when collisions are minimized by a
good hash function.
---
Question 5:
A project calls for dynamic maintenance of a sorted order of elements
©2025
, along with support for rank queries (e.g., finding the kth smallest
element) in O(log n) time. Which augmented data structure meets these
requirements?
- A. Order-statistic tree
- B. R-Tree
- C. Splay tree
- D. Linked list
ANS: A. Order-statistic tree
Rationale: Order-statistic trees are augmented binary search trees
(often based on red‑black trees) that store subtree sizes, enabling
efficient rank queries and selection operations.
---
Question 6:
Which data structure is most commonly used to implement the Depth-
First Search (DFS) algorithm in graph traversal?
- A. Queue
- B. Stack
- C. Priority queue
- D. Hash table
ANS: B. Stack
Rationale: DFS can be implemented using either recursion (implicitly
using the call stack) or an explicit stack data structure to keep track of
nodes to be visited.
---
Question 7:
To resolve collisions in a hash table, one common technique involves
maintaining a linked list of entries for each hash bucket. This method is
known as:
- A. Open addressing
©2025
