DAT 305 Data Structures for Problem
Solving
Finals Mock Exam Review
(Questions & Solutions)
2025
©2025
, Question 1:
An algorithm is defined by the recurrence:
T(n) = 2T(n/2) + n².
Using the Master Theorem, what is the asymptotic time complexity of
the algorithm?
- A. Θ(n log n)
- B. Θ(n²)
- C. Θ(n² log n)
- D. Θ(n³)
ANS: C. Θ(n² log n)
Rationale: Here, a = 2, b = 2, and f(n) = n². We calculate n^(log_b a) =
n^(log₂2) = n. Since f(n) = n² is asymptotically larger than n by a
polynomial factor (n^(2) vs n^(1)), we check Case 3 of the Master
Theorem. Because f(n) is polynomially larger than n^(log_b a), the time
complexity becomes Θ(f(n) · log n) = Θ(n² log n).
---
Question 2:
Which algorithm design paradigm is best suited for problems that exhibit
overlapping subproblems and an optimal substructure, where storing
intermediate results is beneficial?
- A. Greedy algorithms
- B. Divide-and-conquer
- C. Dynamic programming
- D. Backtracking
ANS: C. Dynamic programming
Rationale: Dynamic programming is ideal when a problem has
overlapping subproblems and optimal substructure. It avoids redundant
computation by caching intermediate results (using memoization or
tabulation).
©2025
, ---
Question 3:
In the context of logical reasoning in computer science, which formal
system extends propositional logic by incorporating quantifiers such as
“for all” (∀) and “there exists” (∃)?
- A. Modal logic
- B. Predicate logic
- C. Fuzzy logic
- D. Intuitionistic logic
ANS: B. Predicate logic
Rationale: Predicate logic (also known as first-order logic) extends
propositional logic by including quantifiers and predicates, enabling
reasoning about properties of objects.
---
Question 4:
The technique used to prove that a recursive algorithm correctly
computes its result for all inputs is known as:
- A. Proof by contradiction
- B. Mathematical induction
- C. Direct proof
- D. Recursive verification
ANS: B. Mathematical induction
Rationale: Mathematical induction is a standard proof technique used
to show that a property holds for all natural numbers, making it ideal for
proving the correctness of recursive algorithms.
---
Question 5:
©2025
Solving
Finals Mock Exam Review
(Questions & Solutions)
2025
©2025
, Question 1:
An algorithm is defined by the recurrence:
T(n) = 2T(n/2) + n².
Using the Master Theorem, what is the asymptotic time complexity of
the algorithm?
- A. Θ(n log n)
- B. Θ(n²)
- C. Θ(n² log n)
- D. Θ(n³)
ANS: C. Θ(n² log n)
Rationale: Here, a = 2, b = 2, and f(n) = n². We calculate n^(log_b a) =
n^(log₂2) = n. Since f(n) = n² is asymptotically larger than n by a
polynomial factor (n^(2) vs n^(1)), we check Case 3 of the Master
Theorem. Because f(n) is polynomially larger than n^(log_b a), the time
complexity becomes Θ(f(n) · log n) = Θ(n² log n).
---
Question 2:
Which algorithm design paradigm is best suited for problems that exhibit
overlapping subproblems and an optimal substructure, where storing
intermediate results is beneficial?
- A. Greedy algorithms
- B. Divide-and-conquer
- C. Dynamic programming
- D. Backtracking
ANS: C. Dynamic programming
Rationale: Dynamic programming is ideal when a problem has
overlapping subproblems and optimal substructure. It avoids redundant
computation by caching intermediate results (using memoization or
tabulation).
©2025
, ---
Question 3:
In the context of logical reasoning in computer science, which formal
system extends propositional logic by incorporating quantifiers such as
“for all” (∀) and “there exists” (∃)?
- A. Modal logic
- B. Predicate logic
- C. Fuzzy logic
- D. Intuitionistic logic
ANS: B. Predicate logic
Rationale: Predicate logic (also known as first-order logic) extends
propositional logic by including quantifiers and predicates, enabling
reasoning about properties of objects.
---
Question 4:
The technique used to prove that a recursive algorithm correctly
computes its result for all inputs is known as:
- A. Proof by contradiction
- B. Mathematical induction
- C. Direct proof
- D. Recursive verification
ANS: B. Mathematical induction
Rationale: Mathematical induction is a standard proof technique used
to show that a property holds for all natural numbers, making it ideal for
proving the correctness of recursive algorithms.
---
Question 5:
©2025
