WGU C949 STUDY GUIDE [ACTUAL EXAM] LATEST VERSION [QUESTIONS AND
ANSWERS] WITH PRACTICE EXAM DETAILED AND VERIFIED FOR GUARANTEED
PASS- LATEST UPDATE 2025 GRADED A (BRAND NEW!!)
Hash Table - ✔✔✔✔✔ A data structure that stores unordered items by mapping (or
hashing) each item to a location in an array (or vector).
Hashing - ✔✔✔✔✔ mapping each item to a location in an array (in a hash table).
Chaining - ✔✔✔✔✔ handles hash table collisions by using a list for each bucket,
where each list may store multiple items that map to the same bucket.
Hash key - ✔✔✔✔✔ value used to map an index
bucket - ✔✔✔✔✔ each array element in a hash table
ie A 100 elements hash table has 100 buckets
modulo hash function - ✔✔✔✔✔ computes a bucket index from the items key.
It will map (num_keys / num_buckets) keys to each bucket.
ie... keys range 0 to 49 will have 5 keys per bucket.
= 5
hash table searching - ✔✔✔✔✔ Hash tables support fast search, insert, and remove.
Requires on average O(1)
Linear search requires O(N)
modulo operator % - ✔✔✔✔✔ common has function uses this. which computes the
integer remainder when dividing two numbers.
,Ex: For a 20 element hash table, a hash function of key % 20 will map keys to bucket
indices 0 to 19.
Max-Heap - ✔✔✔✔✔ A binary tree that maintains the simple property that a node's
key is greater than or equal to the node's childrens' keys. (Actually, a max-heap may be
any tree, but is commonly a binary tree).
*a max-heap's root always has the maximum key in the entire tree.
Heap storage - ✔✔✔✔✔ Heaps are typically stored using arrays. Given a tree
representation of a heap, the heap's array form is produced by traversing the tree's
levels from left to right and top to bottom. The root node is always the entry at index 0 in
the array, the root's left child is the entry at index 1, the root's right child is the entry at
index 2, and so on.
Max-heap insert - ✔✔✔✔✔ An insert into a max-heap starts by inserting the node in
the tree's last level, and then swapping the node with its parent until no max-heap
property violation occurs.
The upward movement of a node in a max-heap is sometime called percolating.
Complexity O(logN)
Max-heap remove - ✔✔✔✔✔ Always a removal of the root, and is done by replacing
the root with the last level's last node, and swapping that node with its greatest child
until no max-heap property violation occurs.
Complexity O(logN)
Percolating - ✔✔✔✔✔ The upward movement of a node in a max-heap
Min-Heap - ✔✔✔✔✔ Similar to a max-heap, but a node's key is less than or equal to
its children's keys.
Heap - Parent and child indices - ✔✔✔✔✔ Because heaps are not implemented with
node structures and parent/child pointers, traversing from a node to parent or child
nodes requires referring to nodes by index. The table below shows parent and child
index formulas for a heap.
ie
, 1) parent index for node at index 12? 5
*** ((12-1) // 2) = 5 or 12 //2 -1 = 5
2) child indices for a node at index 6? 13 & 14
*** 2 * 6 + 1 = 13 and 2 * 6 + 2 = 14
**Double# and add 1, double# and add 2
Node index Parent Index Child Indices
0 N/A 1, 2
1 0 3, 4
2 0 5, 6
3 1 7, 8
4 1 9, 10
5 2 11, 12
Heap - parent_index - ✔✔✔✔✔ parent_index = (node_index - 1) // 2
or node_index // 2 - 1
Heap - left_child_index - ✔✔✔✔✔ left_child_index = 2 * node_index + 1
Heap - right_child_index - ✔✔✔✔✔ right_child_index = 2 * node_index + 2
Implementing priority queues with heaps. - ✔✔✔✔✔ Both functions return the value in
the root, but the Pop function removes the value and the Peek function does not. Pop is
worst-case O(logN) and Peek is worst-case O(1).
Push and pop operate have runtime O(logN). All other operations (Peek, IsEmpty,
GetLength) happen in constant time O(1).
Array based list - ✔✔✔✔✔ A list ADT implemented using an array. An array-based list
supports the common list ADT operations, such as append, prepend, insert after,
remove, and search.
Linked list vs Array - ✔✔✔✔✔ If a program requires fast insertion of new data, a linked
list is a better choice than an array.
ANSWERS] WITH PRACTICE EXAM DETAILED AND VERIFIED FOR GUARANTEED
PASS- LATEST UPDATE 2025 GRADED A (BRAND NEW!!)
Hash Table - ✔✔✔✔✔ A data structure that stores unordered items by mapping (or
hashing) each item to a location in an array (or vector).
Hashing - ✔✔✔✔✔ mapping each item to a location in an array (in a hash table).
Chaining - ✔✔✔✔✔ handles hash table collisions by using a list for each bucket,
where each list may store multiple items that map to the same bucket.
Hash key - ✔✔✔✔✔ value used to map an index
bucket - ✔✔✔✔✔ each array element in a hash table
ie A 100 elements hash table has 100 buckets
modulo hash function - ✔✔✔✔✔ computes a bucket index from the items key.
It will map (num_keys / num_buckets) keys to each bucket.
ie... keys range 0 to 49 will have 5 keys per bucket.
= 5
hash table searching - ✔✔✔✔✔ Hash tables support fast search, insert, and remove.
Requires on average O(1)
Linear search requires O(N)
modulo operator % - ✔✔✔✔✔ common has function uses this. which computes the
integer remainder when dividing two numbers.
,Ex: For a 20 element hash table, a hash function of key % 20 will map keys to bucket
indices 0 to 19.
Max-Heap - ✔✔✔✔✔ A binary tree that maintains the simple property that a node's
key is greater than or equal to the node's childrens' keys. (Actually, a max-heap may be
any tree, but is commonly a binary tree).
*a max-heap's root always has the maximum key in the entire tree.
Heap storage - ✔✔✔✔✔ Heaps are typically stored using arrays. Given a tree
representation of a heap, the heap's array form is produced by traversing the tree's
levels from left to right and top to bottom. The root node is always the entry at index 0 in
the array, the root's left child is the entry at index 1, the root's right child is the entry at
index 2, and so on.
Max-heap insert - ✔✔✔✔✔ An insert into a max-heap starts by inserting the node in
the tree's last level, and then swapping the node with its parent until no max-heap
property violation occurs.
The upward movement of a node in a max-heap is sometime called percolating.
Complexity O(logN)
Max-heap remove - ✔✔✔✔✔ Always a removal of the root, and is done by replacing
the root with the last level's last node, and swapping that node with its greatest child
until no max-heap property violation occurs.
Complexity O(logN)
Percolating - ✔✔✔✔✔ The upward movement of a node in a max-heap
Min-Heap - ✔✔✔✔✔ Similar to a max-heap, but a node's key is less than or equal to
its children's keys.
Heap - Parent and child indices - ✔✔✔✔✔ Because heaps are not implemented with
node structures and parent/child pointers, traversing from a node to parent or child
nodes requires referring to nodes by index. The table below shows parent and child
index formulas for a heap.
ie
, 1) parent index for node at index 12? 5
*** ((12-1) // 2) = 5 or 12 //2 -1 = 5
2) child indices for a node at index 6? 13 & 14
*** 2 * 6 + 1 = 13 and 2 * 6 + 2 = 14
**Double# and add 1, double# and add 2
Node index Parent Index Child Indices
0 N/A 1, 2
1 0 3, 4
2 0 5, 6
3 1 7, 8
4 1 9, 10
5 2 11, 12
Heap - parent_index - ✔✔✔✔✔ parent_index = (node_index - 1) // 2
or node_index // 2 - 1
Heap - left_child_index - ✔✔✔✔✔ left_child_index = 2 * node_index + 1
Heap - right_child_index - ✔✔✔✔✔ right_child_index = 2 * node_index + 2
Implementing priority queues with heaps. - ✔✔✔✔✔ Both functions return the value in
the root, but the Pop function removes the value and the Peek function does not. Pop is
worst-case O(logN) and Peek is worst-case O(1).
Push and pop operate have runtime O(logN). All other operations (Peek, IsEmpty,
GetLength) happen in constant time O(1).
Array based list - ✔✔✔✔✔ A list ADT implemented using an array. An array-based list
supports the common list ADT operations, such as append, prepend, insert after,
remove, and search.
Linked list vs Array - ✔✔✔✔✔ If a program requires fast insertion of new data, a linked
list is a better choice than an array.
