WGU C949 STUDY GUIDE EXAM QUESTIONS
WITH CORRECT ANSWERS
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.
50 |/ |10 |= |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
WITH CORRECT ANSWERS
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.
50 |/ |10 |= |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
