CS 311 MIDTERM
DATA STRUCTURES & ALGORITHMS
COMPREHENSIVE PREP
Exam-Style Practice Questions
Correct Answers · Rationales · Explanations
COMPLEXITY · ITERATORS · OPERATORS · OWNERSHIP
MASTER THEOREM · TRADE-OFFS · LOWER BOUNDS
Arrays · Lists · Sorting · Searching · C++ Essentials
QUICK · CLEAR · PROFESSIONAL
,CS 311 MIDTERM | DATA STRUCTURES & ALGORITHMS Comprehensive Prep
PRACTICE SET 1
1. Printing the last item in an array whose size is known is Θ of what?
A. Θ(n)
B. Θ(1)
C. Θ(log n)
D. Θ(n log n)
Correct Answer: B
Rationale:
Random-access: index n−1 in constant time.
Size known ⇒ no traversal needed.
2. Printing the last item in a singly linked list whose size is known is typically:
A. Θ(1) always with only a head pointer
B. Θ(n) if only a head pointer is available (must walk the list)
C. Θ(log n)
D. Θ(n²)
Correct Answer: B
Rationale:
Singly linked lists do not support random access.
Even knowing size, you still traverse from the head unless a tail pointer exists.
3. Finding an item with a given value in a sorted array (binary search) is:
A. Θ(n)
B. Θ(log n)
C. Θ(1)
D. Θ(n log n)
Correct Answer: B
Rationale:
Each step halves the search space.
Comparison model, sorted random-access array.
4. Sorting a linked list with a comparison-based method is generally:
A. Θ(1)
B. Θ(n log n) with a good algorithm (e.g., merge sort adapted to lists)
C. Θ(log n)
D. Impossible
Correct Answer: B
Rationale:
Merge sort works well on linked lists (no random access needed for merging).
Comparison lower bound Ω(n log n) still applies.
Page 2
,CS 311 MIDTERM | DATA STRUCTURES & ALGORITHMS Comprehensive Prep
PRACTICE SET 2
5. Sorting an array with Insertion Sort is:
A. Θ(1)
B. Θ(n²) in the worst and average cases
C. Θ(n log n) always
D. Θ(log n)
Correct Answer: B
Rationale:
Nested loops; ~n²/4 comparisons on average.
Best case Θ(n) when already sorted.
6. Θ notation describes:
A. Only upper bounds
B. Tight asymptotic bounds (both O and Ω)
C. Only lower bounds
D. Exact operation counts for all n
Correct Answer: B
Rationale:
f is Θ(g) if f is both O(g) and Ω(g).
Commonly used for “the” order of an algorithm.
7. Binary search requires which property of the input?
A. Unsorted linked list
B. Sorted random-access sequence
C. Only a hash table
D. Unsorted array with no order
Correct Answer: B
Rationale:
Halving depends on order and indexable midpoints.
Linked lists make mid-finding expensive.
8. The comparison-based sorting lower bound is:
A. Ω(n)
B. Ω(n log n)
C. Ω(log n)
D. Ω(n²)
Correct Answer: B
Rationale:
Decision-tree argument: n! leaves need height ≥ log■(n!).
Stirling ⇒ ~n log n.
Page 3
, CS 311 MIDTERM | DATA STRUCTURES & ALGORITHMS Comprehensive Prep
PRACTICE SET 3
9. Vector src = {0,10,20,30,40,50,60,70}. std::copy(begin(src)+2, begin(src)+5, begin(dest)) copies:
A. 0, 10, 20
B. 20, 30, 40
C. 30, 40, 50
D. 50, 60, 70
Correct Answer: B
Rationale:
Half-open range [first, last): indices 2,3,4.
Values 20, 30, 40.
10. C++ iterators to the end of a range are:
A. Inclusive of the last element in the half-open convention
B. One past the last element (half-open [begin, end))
C. Always null
D. Random only
Correct Answer: B
Rationale:
Standard library algorithms use half-open ranges.
end is not dereferenced.
11. Random-access iterators support:
A. Only ++ and *
B. +, -, indexing, and constant-time jumps
C. Only bidirectional movement
D. No comparison
Correct Answer: B
Rationale:
vector and deque iterators are random-access.
list iterators are only bidirectional.
12. std::copy requires the destination to have:
A. No capacity concerns ever
B. Sufficient space or use of inserters for growing containers
C. Only empty state
D. Reverse iterators always
Correct Answer: B
Rationale:
copy does not resize automatically.
back_inserter can grow a vector.
Page 4
DATA STRUCTURES & ALGORITHMS
COMPREHENSIVE PREP
Exam-Style Practice Questions
Correct Answers · Rationales · Explanations
COMPLEXITY · ITERATORS · OPERATORS · OWNERSHIP
MASTER THEOREM · TRADE-OFFS · LOWER BOUNDS
Arrays · Lists · Sorting · Searching · C++ Essentials
QUICK · CLEAR · PROFESSIONAL
,CS 311 MIDTERM | DATA STRUCTURES & ALGORITHMS Comprehensive Prep
PRACTICE SET 1
1. Printing the last item in an array whose size is known is Θ of what?
A. Θ(n)
B. Θ(1)
C. Θ(log n)
D. Θ(n log n)
Correct Answer: B
Rationale:
Random-access: index n−1 in constant time.
Size known ⇒ no traversal needed.
2. Printing the last item in a singly linked list whose size is known is typically:
A. Θ(1) always with only a head pointer
B. Θ(n) if only a head pointer is available (must walk the list)
C. Θ(log n)
D. Θ(n²)
Correct Answer: B
Rationale:
Singly linked lists do not support random access.
Even knowing size, you still traverse from the head unless a tail pointer exists.
3. Finding an item with a given value in a sorted array (binary search) is:
A. Θ(n)
B. Θ(log n)
C. Θ(1)
D. Θ(n log n)
Correct Answer: B
Rationale:
Each step halves the search space.
Comparison model, sorted random-access array.
4. Sorting a linked list with a comparison-based method is generally:
A. Θ(1)
B. Θ(n log n) with a good algorithm (e.g., merge sort adapted to lists)
C. Θ(log n)
D. Impossible
Correct Answer: B
Rationale:
Merge sort works well on linked lists (no random access needed for merging).
Comparison lower bound Ω(n log n) still applies.
Page 2
,CS 311 MIDTERM | DATA STRUCTURES & ALGORITHMS Comprehensive Prep
PRACTICE SET 2
5. Sorting an array with Insertion Sort is:
A. Θ(1)
B. Θ(n²) in the worst and average cases
C. Θ(n log n) always
D. Θ(log n)
Correct Answer: B
Rationale:
Nested loops; ~n²/4 comparisons on average.
Best case Θ(n) when already sorted.
6. Θ notation describes:
A. Only upper bounds
B. Tight asymptotic bounds (both O and Ω)
C. Only lower bounds
D. Exact operation counts for all n
Correct Answer: B
Rationale:
f is Θ(g) if f is both O(g) and Ω(g).
Commonly used for “the” order of an algorithm.
7. Binary search requires which property of the input?
A. Unsorted linked list
B. Sorted random-access sequence
C. Only a hash table
D. Unsorted array with no order
Correct Answer: B
Rationale:
Halving depends on order and indexable midpoints.
Linked lists make mid-finding expensive.
8. The comparison-based sorting lower bound is:
A. Ω(n)
B. Ω(n log n)
C. Ω(log n)
D. Ω(n²)
Correct Answer: B
Rationale:
Decision-tree argument: n! leaves need height ≥ log■(n!).
Stirling ⇒ ~n log n.
Page 3
, CS 311 MIDTERM | DATA STRUCTURES & ALGORITHMS Comprehensive Prep
PRACTICE SET 3
9. Vector src = {0,10,20,30,40,50,60,70}. std::copy(begin(src)+2, begin(src)+5, begin(dest)) copies:
A. 0, 10, 20
B. 20, 30, 40
C. 30, 40, 50
D. 50, 60, 70
Correct Answer: B
Rationale:
Half-open range [first, last): indices 2,3,4.
Values 20, 30, 40.
10. C++ iterators to the end of a range are:
A. Inclusive of the last element in the half-open convention
B. One past the last element (half-open [begin, end))
C. Always null
D. Random only
Correct Answer: B
Rationale:
Standard library algorithms use half-open ranges.
end is not dereferenced.
11. Random-access iterators support:
A. Only ++ and *
B. +, -, indexing, and constant-time jumps
C. Only bidirectional movement
D. No comparison
Correct Answer: B
Rationale:
vector and deque iterators are random-access.
list iterators are only bidirectional.
12. std::copy requires the destination to have:
A. No capacity concerns ever
B. Sufficient space or use of inserters for growing containers
C. Only empty state
D. Reverse iterators always
Correct Answer: B
Rationale:
copy does not resize automatically.
back_inserter can grow a vector.
Page 4
