CSC148 Exam Study Guide Questions with
Complete solutions (A Graded)
depth of a nested list - ANSWER the maximum number of times a list is nested inside other lists
partial tracing - ANSWER -> trace the base case
-> trace the recursive step while assuming it will return the correct answer
design recipe for recursive functions - ANSWER -> determine the recursive structure of the
input, then use an appropriate code template
-> implement code for base cases
a tree is either - ANSWER empty or has a root value, or subtrees
size of a tree - ANSWER the total number of values in a tree
a leaf - ANSWER a value with no subtrees
height of subtree - ANSWER longest path from root to one of its leaves
children of a value - ANSWER all values directly connected underneath that value
descendants of a value - ANSWER all values beneath the value
parent - ANSWER value immediately above & connected to a value
, ancestors - ANSWER all values that come before a value
preconditions for trees - ANSWER if root is none, the tree is empty
if root is none then subtrees is empty
error that is encountered when we delete a value by promoting its subtrees - ANSWER if that
value is a leaf, then we create an empty subtree - which is not allowed
binary search tree - ANSWER every item is greater than all items in its left subtree and less than
all items in its right subtree
binary search tree structure - ANSWER if root is none, left and right are none
if root is not none, left and right are either noneor a tree
pre-order traversal - ANSWER dealing with the root before its subtrees
post order traversals - ANSWER processing the root after its subtrees
what abstract data type is a tree - ANSWER multiset
a tree of height h can have at least how many items - ANSWER 2^h - 1
range of size of a binary search tree - ANSWER at largest -> n
smallest -> log(n)
run time of sorted list | search, insert, delete - ANSWER search: worst case is O(logn)
Complete solutions (A Graded)
depth of a nested list - ANSWER the maximum number of times a list is nested inside other lists
partial tracing - ANSWER -> trace the base case
-> trace the recursive step while assuming it will return the correct answer
design recipe for recursive functions - ANSWER -> determine the recursive structure of the
input, then use an appropriate code template
-> implement code for base cases
a tree is either - ANSWER empty or has a root value, or subtrees
size of a tree - ANSWER the total number of values in a tree
a leaf - ANSWER a value with no subtrees
height of subtree - ANSWER longest path from root to one of its leaves
children of a value - ANSWER all values directly connected underneath that value
descendants of a value - ANSWER all values beneath the value
parent - ANSWER value immediately above & connected to a value
, ancestors - ANSWER all values that come before a value
preconditions for trees - ANSWER if root is none, the tree is empty
if root is none then subtrees is empty
error that is encountered when we delete a value by promoting its subtrees - ANSWER if that
value is a leaf, then we create an empty subtree - which is not allowed
binary search tree - ANSWER every item is greater than all items in its left subtree and less than
all items in its right subtree
binary search tree structure - ANSWER if root is none, left and right are none
if root is not none, left and right are either noneor a tree
pre-order traversal - ANSWER dealing with the root before its subtrees
post order traversals - ANSWER processing the root after its subtrees
what abstract data type is a tree - ANSWER multiset
a tree of height h can have at least how many items - ANSWER 2^h - 1
range of size of a binary search tree - ANSWER at largest -> n
smallest -> log(n)
run time of sorted list | search, insert, delete - ANSWER search: worst case is O(logn)
