WGU C949 DATA STRUCTURES AND
ALGORITHMS FINAL PAPER QUESTIONS
⩥ 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).
⩥ 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
,⩥ bucket. 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)
⩥ 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.
⩥ 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.
⩥ 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)
⩥ 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)
⩥ Percolating. Answer: The upward movement of a node in a max-heap
⩥ Min-Heap. Answer: Similar to a max-heap, but a node's key is less
than or equal to its children's keys.
ALGORITHMS FINAL PAPER QUESTIONS
⩥ 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).
⩥ 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
,⩥ bucket. 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)
⩥ 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.
⩥ 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.
⩥ 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)
⩥ 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)
⩥ Percolating. Answer: The upward movement of a node in a max-heap
⩥ Min-Heap. Answer: Similar to a max-heap, but a node's key is less
than or equal to its children's keys.
