WGU C949 STUDY GUIDE
WGU C949 STUDY GUIDE
Study online at https://quizlet.com/_8dz8lm
1. Array A data structure that stores an ordered list of items, with each item is directly
accessible by a positional index.
2. Linked List A data structure that stores ordered list of items in nodes, where each node stores
data and has a pointer to the next node.
3. Bianary Search A data structure in which each node stores data and has up to two children, known
Tree as a left child and a right child.
4. Hash Table A data structure that stores unordered items by mapping (or hashing) each item
to a location in an array (or vector).
5. Hashing mapping each item to a location in an array (in a hash table).
6. 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.
7. Hash key value used to map an index
8. bucket each array element in a hash table
ie A 100 elements hash table has 100 buckets
9. modulo hash computes a bucket index from the items key.
function It will map (num_keys / num_buckets) keys to each bucket.
ie... keys range 0 to 49 will have 5 keys per bucket.
= 5
10. hash table Hash tables support fast search, insert, and remove.
searching Requires on average O(1)
Linear search requires O(N)
11. modulo operator common has function uses this. which computes the integer remainder when
% dividing two numbers.
1
, WGU C949 STUDY GUIDE
WGU C949 STUDY GUIDE
Study online at https://quizlet.com/_8dz8lm
Ex: For a 20 element hash table, a hash function of key % 20 will map keys to bucket
indices 0 to 19.
12. 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.
13. 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.
14. 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)
15. Max-heap re- Always a removal of the root, and is done by replacing the root with the last
move level's last node, and swapping that node with its greatest child until no max-heap
property violation occurs.
Complexity O(logN)
16. Percolating The upward movement of a node in a max-heap
17. Min-Heap Similar to a max-heap, but a node's key is less than or equal to its children's keys.
18. Heap - Parent Because heaps are not implemented with node structures and parent/child point-
and child indices ers, 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.
2
, WGU C949 STUDY GUIDE
WGU C949 STUDY GUIDE
Study online at https://quizlet.com/_8dz8lm
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
19. Heap - parent_in- parent_index = (node_index - 1) // 2
dex or node_index // 2 - 1
20. Heap - left_child_index = 2 * node_index + 1
left_child_index
21. Heap - right_child_index = 2 * node_index + 2
right_child_index
22. Implementing Both functions return the value in the root, but the Pop function removes the value
priority queues and the Peek function does not. Pop is worst-case O(logN) and Peek is worst-case
with heaps. O(1).
Push and pop operate have runtime O(logN). All other operations (Peek, IsEmpty,
GetLength) happen in constant time O(1).
23. Array based list
3
WGU C949 STUDY GUIDE
Study online at https://quizlet.com/_8dz8lm
1. Array A data structure that stores an ordered list of items, with each item is directly
accessible by a positional index.
2. Linked List A data structure that stores ordered list of items in nodes, where each node stores
data and has a pointer to the next node.
3. Bianary Search A data structure in which each node stores data and has up to two children, known
Tree as a left child and a right child.
4. Hash Table A data structure that stores unordered items by mapping (or hashing) each item
to a location in an array (or vector).
5. Hashing mapping each item to a location in an array (in a hash table).
6. 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.
7. Hash key value used to map an index
8. bucket each array element in a hash table
ie A 100 elements hash table has 100 buckets
9. modulo hash computes a bucket index from the items key.
function It will map (num_keys / num_buckets) keys to each bucket.
ie... keys range 0 to 49 will have 5 keys per bucket.
= 5
10. hash table Hash tables support fast search, insert, and remove.
searching Requires on average O(1)
Linear search requires O(N)
11. modulo operator common has function uses this. which computes the integer remainder when
% dividing two numbers.
1
, WGU C949 STUDY GUIDE
WGU C949 STUDY GUIDE
Study online at https://quizlet.com/_8dz8lm
Ex: For a 20 element hash table, a hash function of key % 20 will map keys to bucket
indices 0 to 19.
12. 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.
13. 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.
14. 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)
15. Max-heap re- Always a removal of the root, and is done by replacing the root with the last
move level's last node, and swapping that node with its greatest child until no max-heap
property violation occurs.
Complexity O(logN)
16. Percolating The upward movement of a node in a max-heap
17. Min-Heap Similar to a max-heap, but a node's key is less than or equal to its children's keys.
18. Heap - Parent Because heaps are not implemented with node structures and parent/child point-
and child indices ers, 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.
2
, WGU C949 STUDY GUIDE
WGU C949 STUDY GUIDE
Study online at https://quizlet.com/_8dz8lm
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
19. Heap - parent_in- parent_index = (node_index - 1) // 2
dex or node_index // 2 - 1
20. Heap - left_child_index = 2 * node_index + 1
left_child_index
21. Heap - right_child_index = 2 * node_index + 2
right_child_index
22. Implementing Both functions return the value in the root, but the Pop function removes the value
priority queues and the Peek function does not. Pop is worst-case O(logN) and Peek is worst-case
with heaps. O(1).
Push and pop operate have runtime O(logN). All other operations (Peek, IsEmpty,
GetLength) happen in constant time O(1).
23. Array based list
3
