WGU C949 STUDY GUIDE EXAMS WITH
CORRECT ANSWERS /GRADED A+
1. Hash key - ANS☑☑---value used to map an index
2. bucket - ANS☑☑---each array element in a hash table
ie A 100 elements hash table has 100 buckets
3. modulo hash function - ANS☑☑---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
4. hash table searching - ANS☑☑---Hash tables support fast search, insert, and
remove.
Requires on average O(1)
Linear search requires O(N)
5. modulo operator % - ANS☑☑---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.
6. Max-Heap - ANS☑☑---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.
7. Heap storage - ANS☑☑---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.
8. Array - ANS☑☑---A data structure that stores an ordered list of items, with
each item is directly accessible by a positional index.
9. Linked List - ANS☑☑---A data structure that stores ordered list of items in
nodes, where each node stores data and has a pointer to the next node.
10. Bianary Search Tree - ANS☑☑---A data structure in which each node stores
data and has up to two children, known as a left child and a right child.
11. Hash Table - ANS☑☑---A data structure that stores unordered items by
mapping (or hashing) each item to a location in an array (or vector).
12. Hashing - ANS☑☑---mapping each item to a location in an array (in a hash
table).
13. Chaining - ANS☑☑---handles hash table collisions by using a list for each
bucket, where each list may store multiple items that map to the same bucket.
, 14. Max-heap insert - ANS☑☑---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 remove - ANS☑☑---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)
16. Percolating - ANS☑☑---The upward movement of a node in a max-heap
17. Min-Heap - ANS☑☑---Similar to a max-heap, but a node's key is less than or
equal to its children's keys.
18. Heap - Parent and child indices - ANS☑☑---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
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
CORRECT ANSWERS /GRADED A+
1. Hash key - ANS☑☑---value used to map an index
2. bucket - ANS☑☑---each array element in a hash table
ie A 100 elements hash table has 100 buckets
3. modulo hash function - ANS☑☑---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
4. hash table searching - ANS☑☑---Hash tables support fast search, insert, and
remove.
Requires on average O(1)
Linear search requires O(N)
5. modulo operator % - ANS☑☑---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.
6. Max-Heap - ANS☑☑---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.
7. Heap storage - ANS☑☑---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.
8. Array - ANS☑☑---A data structure that stores an ordered list of items, with
each item is directly accessible by a positional index.
9. Linked List - ANS☑☑---A data structure that stores ordered list of items in
nodes, where each node stores data and has a pointer to the next node.
10. Bianary Search Tree - ANS☑☑---A data structure in which each node stores
data and has up to two children, known as a left child and a right child.
11. Hash Table - ANS☑☑---A data structure that stores unordered items by
mapping (or hashing) each item to a location in an array (or vector).
12. Hashing - ANS☑☑---mapping each item to a location in an array (in a hash
table).
13. Chaining - ANS☑☑---handles hash table collisions by using a list for each
bucket, where each list may store multiple items that map to the same bucket.
, 14. Max-heap insert - ANS☑☑---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 remove - ANS☑☑---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)
16. Percolating - ANS☑☑---The upward movement of a node in a max-heap
17. Min-Heap - ANS☑☑---Similar to a max-heap, but a node's key is less than or
equal to its children's keys.
18. Heap - Parent and child indices - ANS☑☑---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
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
