WGU C949 STUDY GUIDE EXAMS
WITH CORRECT ANSWERS /GRADED
A+
1. Array - ANSWER-A data structure that stores an ordered list of items,
with each item is directly accessible by a positional index.
2. 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.
3. 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.
4. Hash Table - ANSWER-A data structure that stores unordered items
by mapping (or hashing) each item to a location in an array (or
vector).
5. Hashing - ANSWER-mapping each item to a location in an array (in a
hash table).
6. 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.
7. Hash key - ANSWER-value used to map an index
, 8. bucket - ANSWER-each array element in a hash table
9. ie A 100 elements hash table has 100 buckets
10. 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
11. hash table searching - ANSWER-Hash tables support fast search,
insert, and remove.
Requires on average O(1)
Linear search requires O(N)
12. 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.
13. 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.
14. 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.
, 15. Max-heap insert - ANSWER-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)
16. Max-heap remove - ANSWER-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)
17. Percolating - ANSWER-The upward movement of a node in a
max-heap
18. Min-Heap - ANSWER-Similar to a max-heap, but a node's key is
less than or equal to its children's keys.
19. Heap - Parent and child indices - ANSWER-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
WITH CORRECT ANSWERS /GRADED
A+
1. Array - ANSWER-A data structure that stores an ordered list of items,
with each item is directly accessible by a positional index.
2. 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.
3. 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.
4. Hash Table - ANSWER-A data structure that stores unordered items
by mapping (or hashing) each item to a location in an array (or
vector).
5. Hashing - ANSWER-mapping each item to a location in an array (in a
hash table).
6. 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.
7. Hash key - ANSWER-value used to map an index
, 8. bucket - ANSWER-each array element in a hash table
9. ie A 100 elements hash table has 100 buckets
10. 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
11. hash table searching - ANSWER-Hash tables support fast search,
insert, and remove.
Requires on average O(1)
Linear search requires O(N)
12. 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.
13. 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.
14. 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.
, 15. Max-heap insert - ANSWER-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)
16. Max-heap remove - ANSWER-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)
17. Percolating - ANSWER-The upward movement of a node in a
max-heap
18. Min-Heap - ANSWER-Similar to a max-heap, but a node's key is
less than or equal to its children's keys.
19. Heap - Parent and child indices - ANSWER-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
