3
x
5 2 4 8
t1
t2
l
7
Quiz #6: Linked Lists, Trees, Inheritance ICS-33 Fall 2020


When working on this quiz, recall the rules stated on the Academic Integrity statement that you signed. You
can download the q6helper project folder (available for Friday, on the Weekly Schedule link) in which to
write/test/debug your code. Submit your completed q6solution module online by Thursday, 11:30pm. I will
post my solutions to EEE reachable via the Solutions link on Friday afternoon.
1. (4 pts) Examine the mystery method and hand simulate the call mystery(x); using the linked list below. Lightly
cross out ALL references that are replaced and Write in new references: don’t erase any references. It will look a bit
messy, but be as neat as you can. Show references to None as /. Do your work on scratch paper first.
def mystery(l):
while l.next != None and l.next.next != None:
t1 = l.next
t2 = t1.next
t1.next = t2.next
t2.next = t1
l.next = t2
l = t1












2. (2 pts) Draw the binary search tree that results from inserting the following values (in the following order) into an
empty binary search tree: 13, 10, 6, 5, 8, 3, 4, 16, 11, 17, 1, 2, 15, 19, 18, 14, 9, 20, 7, and 12. Draw the number for
each tree node, with lines down to its children nodes. Space-it-out to be easy to read. Answer the questions in the box.











Size =

Height =
class LN:
def __init__(self, value, next=None):
self.value, self.next = value, next

class TN:
def __init__(self, value, left=None, right=None):
self.value, self.left, self.right = value, left, right

For Problems 1 and 2, print the Answers.pdf file (in the q6helper folder and on Gradescope), write your answers on it, then upload it to
Gradescope by Friday 11/27 at 11:30pm. If you cannot print files, write your answer as best you can on a blank sheet of paper and upload it to
Gradescope. Upload your solutions to problems 3-6 in the q6solution.py file the normal way to Checkmate by Thursday 11/26 at 11:30pm.
Submit Solution on Gradescope
Submit Solution on Gradescope
3. (4 pts) Define an iterative function named separate; it is passed one linked list and a predicate; it returns a
2-tuple of two linked lists: the first is a linked list of all the values in the parameter where the predicate returns
True; the second is a linked list of all the values in the parameter where the predicate returns False; the values
in each list must be the reverse of their order in the parameter linked list (this makes the code easier to write, not
harder: adding a value at the front of a linked list is easier). For example if we defined
a = list_to_ll([1,2,3,4,5,6])
writing even,odd = separate(a,lambda x : x%2 == 0) results in even referring to a linked list
containing the values 6, 4, and 2 (in that order) ; odd referring to a linked list containing the values 5, 3,
and 1 (in that order). You may not use Python lists, tuples, sets, or dicts in your code: just use linked lists.
4. (4 pts) A min-heap is a binary tree whose order property is that every node is strictly smaller than any of
its children (if a left/right child is None, you don’t have to check it). Write the recursive function
is_min_heap which checks this order property for every node in the tree and returns True if the binary
tree is a min-heap and False if it is not. Think symmetry.
5. (4 pts) We learned that when we declare a class using inheritance, the __bases__ attribute of the class is
bound to a tuple of references to its base classes. Write a recursive function named bases that takes a
reference to any class and returns a set containing that class and all its base classes (all the way back to the
object class). You may not use the __mro__ or mro attributes of the class, which would trivialize your
function. You may use both iteration (over the __bases__ list) and recursion to write this function. For
example, given the following class definitions in a script (class A appears as __main__.A)
class F:pass
class C:pass
class G:pass
class B(F):pass
class D(G):pass
class A(B,C,D):pass
Hint: the union method for a set takes any number of arguments (other sets: a.union(b,c,d)) and computes
the union of all of them Remember how to use * to take a tuple of sets and convert them into that many set
arguments in a function call.. You can also use functools.reduce with | (the set union operator: a | b).
6. (7 pts) Define a class named popdict, derived from the dict class; in addition to being a dictionary, it
remembers how often each key is accessed (how popular it is), and iterates through the popdict in
decreasing order of how frequently the key was accessed. Besides storing the standard dictionary of keys and
their values, a popdict stores an auxiliary dictionary remembering how often each key has been accessed.
The keys in the actual dictionary should always be the same as the keys in the auxiliary dictionary. See the
notes for how pdefaultdict is derived from dict; this derivation is similar.
Define the derived class popdict with only the following methods:
• __init__ (self,initial_dict=[],**kargs): initializes the dictionary and also creates an auxiliary
popularity dictionary (I used a defaultdict) for remembering how often each key is accessed: initialize this
popularity dictionary so that it shows each key in the newly initialized dictionary as being used once so far.
• __getitem__ (self,key): for any key in the dictionary, return its associated value and increase its
popularity (how often it has been used) by 1 in the popularity dictionary.
• __setitem__ (self,key,value): set key to associate with value in the dictionary and increase its
popularity (how often it has been used) by 1 in the popularity dictionary.
Calling bases(A) returns the set

{, , ,
, , ,
}

• __delitem__ (self,key): for any key in the dictionary, remove it from both the dictionary and popularity
dictionary.
• __call__ (self,key): returns the popularity of key (the number of times it has been used); for a key not in
the dictionaries, return 0.
• clear (self): remove all keys (and their associated values) from both dictionaries.
• __iter__ (self): return a generator that will yield all the keys in order of decreasing popularity.