CMPT 280 MIDTERM EXAM QUESTIONS AND CORRECT ANSWERS
What is a heap? - Answer a binary tree which has the heap property
Name a heap property - Answer * Parent nodes have to be >= children nodes
*largest item (root) removed in delete
Define the term 'parent' in regards to a tree - Answer a direct ancestor of current node.
[directly above current node]
Define the term 'ancestor' in regards to a tree - Answer a node that comes before the
node we are currently on [path to root]
Define the term 'descendant' in regards to a tree - Answer a node that comes after the
node we are currently on [path away from root]
Identify the information that must be stored in a binary tree node - Answer *an element
of type <I>
*reference to root node of left and right subtree children
Define characteristics of a binary tree root node - Answer *it has no parent
*it can have 0-2 children
Informally describe an implementation of a binary tree within the framework of lib280 -
Answer *implement container interface [ because it collects elements]
*define methods [rootItem(), rootRightSubtree(LeftSubtree), ..etc
*create class that stores information about nodes
, describe the conditions under which nodes must be visited in a depth-first tree traversal
- Answer start at root; visit children [subtree] of visited node before visiting nodes
sibling(s) [other subtree]
identify valid depth-first traversals of trees - Answer *post-order * from left to right
*pre-order *from right to left
*in-order *in random order
describe the conditions under which nodes must be visited in a breadth-first tree
traversal - Answer start at root; visit all nodes in current level before going to next level
identify valid breadth-first traversals of trees - Answer *level order traversal [visited
from left to right]
define and identify pre-order - Answer start at root; node, left, right
*nodes visited before subtrees
define and identify post-order traversals of binary trees. - Answer start at left most
bottom; left, right, node
define and identify in-order traversals of binary trees. - Answer start at left most bottom;
left, node, right
*not a breadth-first traversal
define what an ordered binary tree is - Answer [a.k.a binary search tree] an additional
structure which arranges elements in a tree making it more efficient during searches
What properties must a ordered binary tree possess? - Answer *elements stored to the
left of a node is LESS than said node
*elements stored to the right of a node is GREATER than or equal to said node
What is a heap? - Answer a binary tree which has the heap property
Name a heap property - Answer * Parent nodes have to be >= children nodes
*largest item (root) removed in delete
Define the term 'parent' in regards to a tree - Answer a direct ancestor of current node.
[directly above current node]
Define the term 'ancestor' in regards to a tree - Answer a node that comes before the
node we are currently on [path to root]
Define the term 'descendant' in regards to a tree - Answer a node that comes after the
node we are currently on [path away from root]
Identify the information that must be stored in a binary tree node - Answer *an element
of type <I>
*reference to root node of left and right subtree children
Define characteristics of a binary tree root node - Answer *it has no parent
*it can have 0-2 children
Informally describe an implementation of a binary tree within the framework of lib280 -
Answer *implement container interface [ because it collects elements]
*define methods [rootItem(), rootRightSubtree(LeftSubtree), ..etc
*create class that stores information about nodes
, describe the conditions under which nodes must be visited in a depth-first tree traversal
- Answer start at root; visit children [subtree] of visited node before visiting nodes
sibling(s) [other subtree]
identify valid depth-first traversals of trees - Answer *post-order * from left to right
*pre-order *from right to left
*in-order *in random order
describe the conditions under which nodes must be visited in a breadth-first tree
traversal - Answer start at root; visit all nodes in current level before going to next level
identify valid breadth-first traversals of trees - Answer *level order traversal [visited
from left to right]
define and identify pre-order - Answer start at root; node, left, right
*nodes visited before subtrees
define and identify post-order traversals of binary trees. - Answer start at left most
bottom; left, right, node
define and identify in-order traversals of binary trees. - Answer start at left most bottom;
left, node, right
*not a breadth-first traversal
define what an ordered binary tree is - Answer [a.k.a binary search tree] an additional
structure which arranges elements in a tree making it more efficient during searches
What properties must a ordered binary tree possess? - Answer *elements stored to the
left of a node is LESS than said node
*elements stored to the right of a node is GREATER than or equal to said node
