WGU C949 Algorithms & Data Structures
Frequently Tested Exam Questions With
Verified Multiple Choice and Conceptual
Actual 100% Correct Detailed Answers
Guaranteed Pass!!Current Update!!
1. Heapsort - ANSWER Optimal time and space
2. Height of a binary heap with N keys. - ANSWER log N
3. A binary heap is a complete tree. A complete tree is a tree with n levels,
where for each level d ≤ n − 1, the number of existing nodes at level d is
equal to 2d. The height of a binary heap is logN.
4. Height of a BST with N keys. - ANSWER N
5. In the worst-case, the height of a BST is N, e.g., when keys are inserted in
increasing or de- creasing order.
6. Number of comparisons to sort N equal keys using our standard version of
quicksort. - ANSWER N^2
N log N
, 7. Number of comparisons to sort N equal keys using 3-way quicksort. -
ANSWER N
8. For equal keys, 3-way quicksort is linear whereas basic quicksort (where
partitioning stops on equal keys) is quadratic.
9. Time to iterate over the keys in a BST using inorder traversal. - ANSWER
N
10.Traversal of a BST requires O(N) time, since it must visit every node.
11.Number of array access to insert a key into a BinarySearchST of size N. -
ANSWER N
12.When inserting a new key into BinarySearchST, each item with key larger
than new key will be shifted one position to the right. In the worst-case, the
new key must be placed in the first slot of the array, so it takes O(N)
operations.
13.push(): always grow array by 1 pop(): always shrink array by 1 - ANSWER
Quadratic
14.push(): double array if it is full pop(): never shrink array - ANSWER
Linear
Frequently Tested Exam Questions With
Verified Multiple Choice and Conceptual
Actual 100% Correct Detailed Answers
Guaranteed Pass!!Current Update!!
1. Heapsort - ANSWER Optimal time and space
2. Height of a binary heap with N keys. - ANSWER log N
3. A binary heap is a complete tree. A complete tree is a tree with n levels,
where for each level d ≤ n − 1, the number of existing nodes at level d is
equal to 2d. The height of a binary heap is logN.
4. Height of a BST with N keys. - ANSWER N
5. In the worst-case, the height of a BST is N, e.g., when keys are inserted in
increasing or de- creasing order.
6. Number of comparisons to sort N equal keys using our standard version of
quicksort. - ANSWER N^2
N log N
, 7. Number of comparisons to sort N equal keys using 3-way quicksort. -
ANSWER N
8. For equal keys, 3-way quicksort is linear whereas basic quicksort (where
partitioning stops on equal keys) is quadratic.
9. Time to iterate over the keys in a BST using inorder traversal. - ANSWER
N
10.Traversal of a BST requires O(N) time, since it must visit every node.
11.Number of array access to insert a key into a BinarySearchST of size N. -
ANSWER N
12.When inserting a new key into BinarySearchST, each item with key larger
than new key will be shifted one position to the right. In the worst-case, the
new key must be placed in the first slot of the array, so it takes O(N)
operations.
13.push(): always grow array by 1 pop(): always shrink array by 1 - ANSWER
Quadratic
14.push(): double array if it is full pop(): never shrink array - ANSWER
Linear
