WGU C949 STUDY GUIDE QUESTIONS AND
ANSWERS COMPLETE EXAM PREP
TERMINOLOGY PRACTICE TEST
| GRADED A+ | GUARANTEED SUCCESS
UPDATED QUESTIONS AND ANSWERS
100% VERIFIED EXAM PREP
[EXAM• STUDY GUIDE • SUMMARY • ASSIGNMENT]
A clean, organized resource designed for easy revision and reference.
QUICK • CLEAR • PROFESSIONAL
,Array A data structure that stores an ordered list of items, with each item is directly accessible
by a positional index.
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.
Bianary Search Tree 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 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.
ANSWERS COMPLETE EXAM PREP
TERMINOLOGY PRACTICE TEST
| GRADED A+ | GUARANTEED SUCCESS
UPDATED QUESTIONS AND ANSWERS
100% VERIFIED EXAM PREP
[EXAM• STUDY GUIDE • SUMMARY • ASSIGNMENT]
A clean, organized resource designed for easy revision and reference.
QUICK • CLEAR • PROFESSIONAL
,Array A data structure that stores an ordered list of items, with each item is directly accessible
by a positional index.
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.
Bianary Search Tree 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 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.
