CSC148 section 8 Study Questions with
Complete solutions
what is the drawback of the 'looping-through-all-items' search algorithm?
note: this drawback is shared with the tree.__contains__ method - ANSWER in the case of an
unsuccesful search, every item of the list is checked
this is a linear time operation: the time taken for an unsuccessful search grows
proportionally with the length of the list!
what is the efficient search algorithm that can be implemented on sorted lists? - ANSWER
binary search
what is the drawback of binary search due to the fact that it is based on Python's array-
based lists? - ANSWER insertion and deletion still has problems
the following still happens when adding/removing elements that are NOT at the end of sorted
lists:
, - shifting of elements during insertion
- shifting of elements during deletion
binary tree - ANSWER tree in which every item has at most two subtrees / children
an item in a binary tree satisfies the binary search tree property if... - ANSWER its value is
(1) greater than or equal to all items in its left subtree
(2) less than or equal to all items in its right subtree
a binary tree is a binary search tree (BST) if... - ANSWER every item in the tree satisfies the BST
property
state an advantageous inherent property of BSTs - ANSWER natural sorting: BSTs
inherently organize data in a sorted manner, even if input data was not sorted
BSTs are extremely efficient in __________ AND __________ AND __________ - ANSWER
searching AND insertion AND deletion
in the BinarySearchTree class, which 3 attributes are set to None if a BST is empty? - ANSWER
(1) _root
(2) _left
(3) _right
in the BinarySearchTree class, what is the ONLY case where any of the attributes of a BST
can be set to None? - ANSWER in the case that the BST is empty
a NON-EMPTY BST can have its _left and _right attributes refer to __________ (which is
different from these attributes being set to None) - ANSWER empty BSTs
Complete solutions
what is the drawback of the 'looping-through-all-items' search algorithm?
note: this drawback is shared with the tree.__contains__ method - ANSWER in the case of an
unsuccesful search, every item of the list is checked
this is a linear time operation: the time taken for an unsuccessful search grows
proportionally with the length of the list!
what is the efficient search algorithm that can be implemented on sorted lists? - ANSWER
binary search
what is the drawback of binary search due to the fact that it is based on Python's array-
based lists? - ANSWER insertion and deletion still has problems
the following still happens when adding/removing elements that are NOT at the end of sorted
lists:
, - shifting of elements during insertion
- shifting of elements during deletion
binary tree - ANSWER tree in which every item has at most two subtrees / children
an item in a binary tree satisfies the binary search tree property if... - ANSWER its value is
(1) greater than or equal to all items in its left subtree
(2) less than or equal to all items in its right subtree
a binary tree is a binary search tree (BST) if... - ANSWER every item in the tree satisfies the BST
property
state an advantageous inherent property of BSTs - ANSWER natural sorting: BSTs
inherently organize data in a sorted manner, even if input data was not sorted
BSTs are extremely efficient in __________ AND __________ AND __________ - ANSWER
searching AND insertion AND deletion
in the BinarySearchTree class, which 3 attributes are set to None if a BST is empty? - ANSWER
(1) _root
(2) _left
(3) _right
in the BinarySearchTree class, what is the ONLY case where any of the attributes of a BST
can be set to None? - ANSWER in the case that the BST is empty
a NON-EMPTY BST can have its _left and _right attributes refer to __________ (which is
different from these attributes being set to None) - ANSWER empty BSTs
