WGU C949 STUDY GUIDE WITH
COMPLETE SOLUTIONS
Array - ANSWER-A data structure that stores an ordered list of items, with
each item is directly accessible by a positional index.
Linked List - ANSWER-A data structure that stores ordered list of items in
nodes, where each node stores data and has a pointer to the next node.
Bianary Search Tree - ANSWER-A data structure in which each node stores
data and has up to two children, known as a left child and a right child.
Hash Table - ANSWER-A data structure that stores unordered items by
mapping (or hashing) each item to a location in an array (or vector).
Hashing - ANSWER-mapping each item to a location in an array (in a hash
table).
,Max-Heap - ANSWER-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 - ANSWER-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.
Chaining - ANSWER-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 - ANSWER-value used to map an index
bu
,Max-Heap - ANSWER-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 - ANSWER-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.
cket - ANSWER-each array element in a hash table
ie A 100 elements hash table has 100 buckets
modulo hash function - ANSWER-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 - ANSWER-Hash tables support fast search, insert, and
remove.
Requires on average O(1)
Linear search requires O(N)
Heap - parent_index - ANSWER-parent_index = (node_index - 1) // 2
or node_index // 2 - 1
Heap - left_child_index - ANSWER-left_child_index = 2 * node_index + 1
Heap - right_child_index - ANSWER-right_child_index = 2 * node_index + 2
modulo operator % - ANSWER-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.
COMPLETE SOLUTIONS
Array - ANSWER-A data structure that stores an ordered list of items, with
each item is directly accessible by a positional index.
Linked List - ANSWER-A data structure that stores ordered list of items in
nodes, where each node stores data and has a pointer to the next node.
Bianary Search Tree - ANSWER-A data structure in which each node stores
data and has up to two children, known as a left child and a right child.
Hash Table - ANSWER-A data structure that stores unordered items by
mapping (or hashing) each item to a location in an array (or vector).
Hashing - ANSWER-mapping each item to a location in an array (in a hash
table).
,Max-Heap - ANSWER-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 - ANSWER-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.
Chaining - ANSWER-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 - ANSWER-value used to map an index
bu
,Max-Heap - ANSWER-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 - ANSWER-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.
cket - ANSWER-each array element in a hash table
ie A 100 elements hash table has 100 buckets
modulo hash function - ANSWER-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 - ANSWER-Hash tables support fast search, insert, and
remove.
Requires on average O(1)
Linear search requires O(N)
Heap - parent_index - ANSWER-parent_index = (node_index - 1) // 2
or node_index // 2 - 1
Heap - left_child_index - ANSWER-left_child_index = 2 * node_index + 1
Heap - right_child_index - ANSWER-right_child_index = 2 * node_index + 2
modulo operator % - ANSWER-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.
