WGU D446 DATA STRUCTURES AND
ALGORITHMS I - COMPREHENSIVE OA
PRACTICE EXAM QUESTIONS AND
ANSWERS
1. What is the Big O notation for the worst-case time complexity of an insertion into a Binary
Search Tree (BST) that is not balanced?
A. O(log n)
B. O(1)
C. O(n log n)
D. O(n)
Answer: D
Conceptual Explanation: In a worst-case scenario where a BST becomes a degenerate
(linked-list-like) structure, insertion requires traversing all nodes, leading to O(n)
complexity.
2. Which data structure is most efficient for implementing a Last-In-First-Out (LIFO) behavior?
A. Stack
B. Queue
,C. Linked List
D. Heap
Answer: A
Conceptual Explanation: A Stack is specifically designed for LIFO operations where the
last element added is the first one removed.
3. In the context of Big O notation, what does it mean if an algorithm is O(log n)?
A. The execution time increases linearly with input size.
B. The execution time increases by a constant amount as input size doubles.
C. The execution time doubles as the input size doubles.
D. The execution time is constant regardless of input size.
Answer: B
Conceptual Explanation: Logarithmic time O(log n) implies that as the input size n
increases exponentially (doubles), the time only increases by a fixed constant amount.
4. Which sorting algorithm has a worst-case time complexity of O(n^2) but is often faster in
practice due to a low constant factor?
A. Merge Sort
B. Radix Sort
C. Heap Sort
, D. Quick Sort
Answer: D
Conceptual Explanation: Quick Sort has a worst-case of O(n^2) when the pivot selection
is poor, but its average-case is O(n log n) and typically outperforms Merge Sort due to
cache locality and low overhead.
5. What is the primary disadvantage of using a Singly Linked List compared to an Array?
A. Slower insertion at the beginning.
B. Higher memory overhead per element due to pointers.
C. Inability to store large data types.
D. Fixed size constraints.
Answer: B
Conceptual Explanation: Linked lists require extra memory for pointers at each node,
whereas arrays only store the raw data, though arrays have contiguous memory
requirements.
6. When using a Hash Table, what is ‘Linear Probing’?
A. A collision resolution method that checks the next slot in the array.
B. A technique to sort the table.
C. A method to increase the hash function speed.
D. The process of resizing the table.
ALGORITHMS I - COMPREHENSIVE OA
PRACTICE EXAM QUESTIONS AND
ANSWERS
1. What is the Big O notation for the worst-case time complexity of an insertion into a Binary
Search Tree (BST) that is not balanced?
A. O(log n)
B. O(1)
C. O(n log n)
D. O(n)
Answer: D
Conceptual Explanation: In a worst-case scenario where a BST becomes a degenerate
(linked-list-like) structure, insertion requires traversing all nodes, leading to O(n)
complexity.
2. Which data structure is most efficient for implementing a Last-In-First-Out (LIFO) behavior?
A. Stack
B. Queue
,C. Linked List
D. Heap
Answer: A
Conceptual Explanation: A Stack is specifically designed for LIFO operations where the
last element added is the first one removed.
3. In the context of Big O notation, what does it mean if an algorithm is O(log n)?
A. The execution time increases linearly with input size.
B. The execution time increases by a constant amount as input size doubles.
C. The execution time doubles as the input size doubles.
D. The execution time is constant regardless of input size.
Answer: B
Conceptual Explanation: Logarithmic time O(log n) implies that as the input size n
increases exponentially (doubles), the time only increases by a fixed constant amount.
4. Which sorting algorithm has a worst-case time complexity of O(n^2) but is often faster in
practice due to a low constant factor?
A. Merge Sort
B. Radix Sort
C. Heap Sort
, D. Quick Sort
Answer: D
Conceptual Explanation: Quick Sort has a worst-case of O(n^2) when the pivot selection
is poor, but its average-case is O(n log n) and typically outperforms Merge Sort due to
cache locality and low overhead.
5. What is the primary disadvantage of using a Singly Linked List compared to an Array?
A. Slower insertion at the beginning.
B. Higher memory overhead per element due to pointers.
C. Inability to store large data types.
D. Fixed size constraints.
Answer: B
Conceptual Explanation: Linked lists require extra memory for pointers at each node,
whereas arrays only store the raw data, though arrays have contiguous memory
requirements.
6. When using a Hash Table, what is ‘Linear Probing’?
A. A collision resolution method that checks the next slot in the array.
B. A technique to sort the table.
C. A method to increase the hash function speed.
D. The process of resizing the table.
