1
WGU C949 OBJECTIVE ASSESSMENT LATEST 2026/2027
ACTUAL EXAM| C949 DATA STRUCTURES AND ALGORITHMS
ACTUAL EXAM QUESTIONS AND CORRECT DETAILED ANSWERS
(VERIFIED ANSWERS) ALREADY GRADED A+ (BRAND NEW!!)
Question 1
What is the worst-case time complexity of searching for an element in a balanced
binary search tree that contains *n* nodes?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
: Answer : B
Rationale: A balanced BST (e.g., AVL or Red-Black tree) guarantees that the height
is O(log n). Searching follows a single path from the root to a leaf, visiting at most
h + 1 nodes. Therefore, the number of comparisons is proportional to the height,
giving O(log n).
Distractor analysis:
• A: O(1) is possible only in a hash table (average) or direct access structure,
never in a BST search.
• C: O(n) is the worst case for an unbalanced BST that degenerates into a
linked list.
• D: O(n log n) is typical for comparison-based sorting algorithms, not search.
Full rotation rationale: No rotation is needed here; the balance condition
ensures O(log n) height, which directly yields O(log n) search time.
Question 2
pg. 1
,2
Given an array of *n* integers, which sorting algorithm exhibits O(n²) worst-case
time complexity but O(n log n) average-case complexity and is not stable?
A. Merge sort
B. Insertion sort
C. Quick sort (with random pivot)
D. Counting sort
: Answer : C
Rationale: Quick sort with random pivot has an average time of O(n log n), but if
the pivot repeatedly partitions the array into the smallest/largest element, the
depth becomes n, leading to O(n²) worst-case. Quick sort is not stable because
equal elements may be swapped across partitions.
Distractors:
• A: Merge sort is O(n log n) worst-case and stable.
• B: Insertion sort is O(n²) worst and average, but stable.
• D: Counting sort is O(n + k) and stable but not comparison-based.
Full rotation: Not a tree rotation question; the rationale focuses on the
pivot selection’s impact on partition depth.
Question 3
An AVL tree is initially empty. Insert the keys 30, 20, 10 in that order. Which
rotation(s) are performed, and what is the resulting root?
A. Single right rotation; root = 20
B. Single left rotation; root = 30
C. Left-right double rotation; root = 20
D. Right-left double rotation; root = 20
: Answer : A
Rationale (Full rotation):
1. Insert 30: tree is 30.
2. Insert 20: 30’s left child is 20. Heights: node 30 balance = +1 (left higher).
No rotation.
pg. 2
,3
3. Insert 10: 10 becomes left child of 20. Now balance factors: node 20 = +1
(left), node 30 = +2 (left-left case).
4. Left-left (LL) imbalance → single right rotation on 30.
Rotation steps:
o Let pivot = 30, its left child L = 20.
o 30’s left pointer becomes L’s right child (null).
o L’s right pointer becomes 30.
o Update heights: 30 height = 1, 20 height = 2.
o New root is 20.
Resulting tree: 20 with left child 10, right child 30. Root = 20.
Distractors:
• B: A left rotation would be for right-right imbalance.
• C: Left-right double rotation would be for left-right case (insert into right
subtree of left child). Here it’s left-left.
• D: Right-left double rotation is for right-left case.
Question 4
What is the output of a post-order traversal of the binary search tree formed by
inserting the following values in order: 50, 30, 70, 20, 40, 60, 80?
A. 20, 40, 30, 60, 80, 70, 50
B. 50, 30, 20, 40, 70, 60, 80
C. 20, 30, 40, 50, 60, 70, 80
D. 20, 40, 60, 80, 70, 30, 50
: Answer : A
Rationale: Post-order visits left subtree, right subtree, then root.
The constructed BST:
50
/ \
30 70
pg. 3
, 4
/ \ / \
20 40 60 80
Post-order: Left of 50 → (30’s left: 20, right: 40, then 30) gives 20,40,30. Right of
50 → (70’s left: 60, right: 80, then 70) gives 60,80,70. Finally root 50 →
20,40,30,60,80,70,50.
Distractor B is level-order, C is in-order (sorted), D is a different sequence.
Full rotation: Not applicable; traversal order explained step-by-step.
Question 5
Which data structure provides amortized O(1) time complexity for both push and
pop operations, and is typically implemented using a dynamic array?
A. Queue
B. Stack
C. Priority queue
D. Deque
: Answer : B
Rationale: A stack implemented with a dynamic array (like Python’s list) has
amortized O(1) push (append) and pop (from the end). Occasional resizing causes
O(n) but amortized constant time.
Distractors:
• A: Queue (FIFO) using an array would need O(n) for dequeue if
implemented naively, though circular buffer gives O(1) amortized but the
question specifically says “push and pop” which are stack terminology.
• C: Priority queue operations (insert, extract-min) are O(log n) typically.
• D: Deque can have O(1) amortized for both ends but push/pop terminology
is stack-specific. The classic “push/pop” maps to stack.
Question 6
When inserting a new element into a max-heap of *n* elements, what is the
worst-case number of swaps (bubble-up steps)?
pg. 4
WGU C949 OBJECTIVE ASSESSMENT LATEST 2026/2027
ACTUAL EXAM| C949 DATA STRUCTURES AND ALGORITHMS
ACTUAL EXAM QUESTIONS AND CORRECT DETAILED ANSWERS
(VERIFIED ANSWERS) ALREADY GRADED A+ (BRAND NEW!!)
Question 1
What is the worst-case time complexity of searching for an element in a balanced
binary search tree that contains *n* nodes?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
: Answer : B
Rationale: A balanced BST (e.g., AVL or Red-Black tree) guarantees that the height
is O(log n). Searching follows a single path from the root to a leaf, visiting at most
h + 1 nodes. Therefore, the number of comparisons is proportional to the height,
giving O(log n).
Distractor analysis:
• A: O(1) is possible only in a hash table (average) or direct access structure,
never in a BST search.
• C: O(n) is the worst case for an unbalanced BST that degenerates into a
linked list.
• D: O(n log n) is typical for comparison-based sorting algorithms, not search.
Full rotation rationale: No rotation is needed here; the balance condition
ensures O(log n) height, which directly yields O(log n) search time.
Question 2
pg. 1
,2
Given an array of *n* integers, which sorting algorithm exhibits O(n²) worst-case
time complexity but O(n log n) average-case complexity and is not stable?
A. Merge sort
B. Insertion sort
C. Quick sort (with random pivot)
D. Counting sort
: Answer : C
Rationale: Quick sort with random pivot has an average time of O(n log n), but if
the pivot repeatedly partitions the array into the smallest/largest element, the
depth becomes n, leading to O(n²) worst-case. Quick sort is not stable because
equal elements may be swapped across partitions.
Distractors:
• A: Merge sort is O(n log n) worst-case and stable.
• B: Insertion sort is O(n²) worst and average, but stable.
• D: Counting sort is O(n + k) and stable but not comparison-based.
Full rotation: Not a tree rotation question; the rationale focuses on the
pivot selection’s impact on partition depth.
Question 3
An AVL tree is initially empty. Insert the keys 30, 20, 10 in that order. Which
rotation(s) are performed, and what is the resulting root?
A. Single right rotation; root = 20
B. Single left rotation; root = 30
C. Left-right double rotation; root = 20
D. Right-left double rotation; root = 20
: Answer : A
Rationale (Full rotation):
1. Insert 30: tree is 30.
2. Insert 20: 30’s left child is 20. Heights: node 30 balance = +1 (left higher).
No rotation.
pg. 2
,3
3. Insert 10: 10 becomes left child of 20. Now balance factors: node 20 = +1
(left), node 30 = +2 (left-left case).
4. Left-left (LL) imbalance → single right rotation on 30.
Rotation steps:
o Let pivot = 30, its left child L = 20.
o 30’s left pointer becomes L’s right child (null).
o L’s right pointer becomes 30.
o Update heights: 30 height = 1, 20 height = 2.
o New root is 20.
Resulting tree: 20 with left child 10, right child 30. Root = 20.
Distractors:
• B: A left rotation would be for right-right imbalance.
• C: Left-right double rotation would be for left-right case (insert into right
subtree of left child). Here it’s left-left.
• D: Right-left double rotation is for right-left case.
Question 4
What is the output of a post-order traversal of the binary search tree formed by
inserting the following values in order: 50, 30, 70, 20, 40, 60, 80?
A. 20, 40, 30, 60, 80, 70, 50
B. 50, 30, 20, 40, 70, 60, 80
C. 20, 30, 40, 50, 60, 70, 80
D. 20, 40, 60, 80, 70, 30, 50
: Answer : A
Rationale: Post-order visits left subtree, right subtree, then root.
The constructed BST:
50
/ \
30 70
pg. 3
, 4
/ \ / \
20 40 60 80
Post-order: Left of 50 → (30’s left: 20, right: 40, then 30) gives 20,40,30. Right of
50 → (70’s left: 60, right: 80, then 70) gives 60,80,70. Finally root 50 →
20,40,30,60,80,70,50.
Distractor B is level-order, C is in-order (sorted), D is a different sequence.
Full rotation: Not applicable; traversal order explained step-by-step.
Question 5
Which data structure provides amortized O(1) time complexity for both push and
pop operations, and is typically implemented using a dynamic array?
A. Queue
B. Stack
C. Priority queue
D. Deque
: Answer : B
Rationale: A stack implemented with a dynamic array (like Python’s list) has
amortized O(1) push (append) and pop (from the end). Occasional resizing causes
O(n) but amortized constant time.
Distractors:
• A: Queue (FIFO) using an array would need O(n) for dequeue if
implemented naively, though circular buffer gives O(1) amortized but the
question specifically says “push and pop” which are stack terminology.
• C: Priority queue operations (insert, extract-min) are O(log n) typically.
• D: Deque can have O(1) amortized for both ends but push/pop terminology
is stack-specific. The classic “push/pop” maps to stack.
Question 6
When inserting a new element into a max-heap of *n* elements, what is the
worst-case number of swaps (bubble-up steps)?
pg. 4
