WGU C949 Study Guide (Data Structures &
Algorithms 1) – Questions With Suitable
Solutions
Array Correct Answer - A data structure that stores an ordered
list of items, with each item is directly accessible by a positional
index.
Linked List Correct 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 Correct 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 Correct Answer - A data structure that stores
unordered items by mapping (or hashing) each item to a location in
an array (or vector).
Hashing Correct Answer - mapping each item to a location in
an array (in a hash table).
Chaining Correct 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 Correct Answer - value used to map an index
bucket Correct Answer - each array element in a hash table
ie A 100 elements hash table has 100 buckets
,modulo hash function Correct 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 Correct Answer - Hash tables support fast
search, insert, and remove.
Requires on average O(1)
Linear search requires O(N)
modulo operator % Correct 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 Correct 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 Correct 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 Correct 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 Correct 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 Correct Answer - The upward movement of a node
in a max-heap
Min-Heap Correct Answer - Similar to a max-heap, but a node's
key is less than or equal to its children's keys.
Heap - Parent and child indices Correct 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
1) 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
Node index Parent Index Child Indices
0 N/A 1, 2
Algorithms 1) – Questions With Suitable
Solutions
Array Correct Answer - A data structure that stores an ordered
list of items, with each item is directly accessible by a positional
index.
Linked List Correct 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 Correct 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 Correct Answer - A data structure that stores
unordered items by mapping (or hashing) each item to a location in
an array (or vector).
Hashing Correct Answer - mapping each item to a location in
an array (in a hash table).
Chaining Correct 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 Correct Answer - value used to map an index
bucket Correct Answer - each array element in a hash table
ie A 100 elements hash table has 100 buckets
,modulo hash function Correct 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 Correct Answer - Hash tables support fast
search, insert, and remove.
Requires on average O(1)
Linear search requires O(N)
modulo operator % Correct 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 Correct 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 Correct 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 Correct 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 Correct 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 Correct Answer - The upward movement of a node
in a max-heap
Min-Heap Correct Answer - Similar to a max-heap, but a node's
key is less than or equal to its children's keys.
Heap - Parent and child indices Correct 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
1) 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
Node index Parent Index Child Indices
0 N/A 1, 2
