CS 61A Structure and Interpretation of Computer Programs
Fall 2015
INSTRUCTIONS
Midterm 2 Solutions
• You have 2 hours to complete the exam.
• The exam is closed book, closed notes, closed computer, closed calculator, except one hand-written 8.5” × 11”
crib sheet of your own creation and the official CS 61A study guides.
• Mark your answers on the exam itself. We will not grade answers written on scratch paper.
Last name
First name
Student ID number
BearFacts email
TA
All the work on this exam is my own.
(please sign)
2
1. (12 points) ok –submit
For each of the expressions in the table below, write the output displayed by the interactive Python interpreter when the expression is evaluated. The output may have multiple lines. If more than 3 lines are displayed, just write the first 3. If an error occurs, write “Error”. If evaulation would run forever, write “Forever”.
The first two rows have been provided as examples.
Assume that you have started python3 and executed the following statements (which do not cause errors):
class Ok:
py = [3.14]
def __init__(self, py): self.ok = self.py Ok.py.append(3 * py)
def my(self, eye): print(self.my(eye)) return self.ok.pop()
def __str__(self):
return str(self.ok)[:4]
class Go(Ok):
def my(self, help):
return [help+3, len(Ok.py)]
oh = Go (5)
Go.py = [3, 1, 4]
oh.no = {’just’: Go(9)}
Expression
’z’ * 3
oh.py
oh.my(3)
oh.ok + oh.no[’just’].ok
print(oh)
Ok(’go’).my(5)
Interactive Output
’zzz’
[3, 1, 4]
[6, 3]
[3.14, 15, 27, 3, 1, 4] [3.1
“Error”
print(4, 5) + 1
45 Error
Ok.my(oh, 5)
[8, 4]
’gogogo’
Name: 3 2. (14 points) Exercises
(a) (6 pt) Fill in the environment diagram that results from executing the code below until the entire program is finished, an error occurs, or all frames are filled. You may not need to use all of the spaces or frames.
A complete answer will:
• Add all missing names and parent annotations to all local frames. • Add all missing values created or referenced during execution.
• Show the return value for each local frame.
You are not required to write index numbers in list boxes.
Global
f
b
fit bit
def f(it):
it.append(it[1]())
def b(it):
def steps():
nonlocal it
it = fit[0]
return fit.pop()
return steps
fit = [1, [2]]
bit = [fit, b(fit[1])]
f(bit)
1
2
3
4
5
6
7
8
9 list
10 11 12 13
func f(it) [parent=Global]
func b(it) [parent=Global]
list
list
02 func steps() [parent=f1]
01
1
0
1
2
f1: b [parent=Global]
1
it steps
Return Value
f2: f [parent=Global]
it
Return Value None
f3: si [parent=f1]
Return Value
4
(b) (8 pt) In each box next to a line of code below, write the number of the environment diagram that would result after executing that line and complete the diagram by adding all missing values (boxes and arrows). Suggestion: You may want to write out the whole diagram elsewhere (scratch paper or the bottom left of this page) before filling in the answer area.
Write numbers
(1, 2, or 3)
in these boxes
Complete these
diagrams
#1
list list 0111 0111
list
0 1 1 1 2
list 01
list list 01112 01
list 01112
list list 011 01
list 01112
list
Global frame a
b c d
a = [1, 1]
b = [1, 1]
c = a + [b]
d = c[1:2]
while a:
b.extend([[a.pop()]])
d, b = b, d a=b
b[2][0], d = c, b[2]
#2
Global frame a
b c d
#3
list 110
012
Global frame a
b c d
Name: 5 3. (24 points) Return of the Digits
(a) (4 pt) Implement complete, which takes a Tree instance t and two positive integers d and k. It returns whether t is d-k-complete. A tree is d-k-complete if every node at a depth less than d has exactly k branches and every node at depth d is a leaf. Notes: The depth of a node is the number of steps from the root; the root node has depth 0. The built-in all function takes a sequence and returns whether all elements are true values: all([1, 2]) is True but all([0, 1]) is False. Tree appears on the Midterm 2 Study Guide. def complete(t, d, k):
“””Return whether t is d-k-complete.
>>> complete(Tree(1), 0, 5)
True
>>> u = Tree(1, [Tree(1), Tree(1), Tree(1)])
>>> [ complete(u, 1, [True, False, False] >>> complete(Tree(1, True
“””
if not t.branches:
3) , complete(u, 1, 2) , complete(u, 2, 3) ] [u, u, u]), 2, 3)
return d == 0
bs = [complete(b, d-1, k) for b in t.branches] return len(t.branches) == k and all(bs)
(b) (4 pt) Implement adder, which takes two lists x and y of digits representing positive numbers. It mutates x to represent the result of adding x and y. Notes: The built-in reversed function takes a sequence and returns its elements in reverse order. Assume that x[0] and y[0] are both positive.
def adder(x, y):
“””Adds y into x for lists of digits x and y representing positive numbers. >>> a = [3, 4, 5]
>>> adder(a, [4, 0, 0] >>> adder(a, [1, 2, 3, 4] >>> adder(a, [3, 4, 5, 6, “””
[5, 5]) [8, 3, 4])
[3, 3, 3, 7]
# 345 + 55 = 400
# 400 + 834 = 1234 3, 3]) # 1234 + 33333 = 34567
carry , i = 0, len(x)-1
for d in reversed([0] + y):
if i == -1: x.insert(0, 0)
i=0
d = carry + x[i] +
carry, x[i], i = d
if x[0] == 0: x.remove(0)
return x
d
// 10, d % 10, i-1
6
(c) (6 pt) Implement multiples, which takes a positive integer k and a linked list s of digits greater than 0 and less than 10. It returns a linked list of all positive n that are multiples of k greater than k and made up of digits only from s. The digits in each n must appear in the same order as they do in s, and each digit from s can appear only once in each n. The Link class appears on the Midterm 2 Study Guide.
def multiples(k, s):
“””Return a linked list of all multiples of k selected from digits in s.
>>> odds = Link(1, Link(3, Link(5, Link(7, Link(9))))) >>> multiples(5, odds)
Link(135, Link(15, Link(35)))
>>> Link >>> Link >>> () “””
t = def
multiples(7, odds)
(1379 , Link (357 , Link (35))) multiples(9, odds)
(1359 , Link (135)) multiples(2, odds)
Link.empty f(n, s):
nonlocal t
if s is Link.empty:
if n > k and n % k == 0:
f(0, s) return t
else:
t = Link(n, t)
f(n, s.rest) f(n*10+s.first , s.rest)
(d) (2 pt) Circle the Θ expression that describes the length of the linked list returned by multiples(1, s) for an input list of length n. Assume multiples is implemented correctly.
Θ(1) Θ(log n) Θ(n) Θ(n2) Θ(2n)
Note: Θ(1) was also accepted if accompanied by the justification that s would not contain repeated digits.
Name: 7
(e) (8 pt) Implement int_set, which is a higher-order function that takes a list of non-negative integers called contents. It returns a function that takes a non-negative integer n and returns whether n appears in contents. Your partner left you this clue: Every integer can be expressed uniquely as a sum of powers of 2. E.g., 5 equals 1 + 4 equals pow(2, 0) + pow(2, 2). The bits helper function encodes a list of nums using sequences of 0’s and 1’s that tell you whether each power of 2 is used, starting with pow(2, 0).
Note: You may not use built-in tests of list membership, such as an in expression or a list’s index method. def bits(nums):
“””A set of nums represented as a function that takes ’entry’, 0, or 1.
>>> t = bits([4, 5]) # Contains 4 and 5, but not 2
>>> t(0)(0)(1)(’entry’) # 4 = 0 * pow(2, 0) + 0 * pow(2, 1) True
>>> t(0)(1)(’entry’) # 2 = 0 * pow(2, 0) + 1 * pow(2, 1) False
>>> t(1)(0)(1)(’entry’) # 5 = 1 * pow(2, 0) + 0 * pow(2, 1) True
“””
def branch(last):
if last == ’entry’: return 0 in nums
return bits([k // 2 for k in nums if k % 2 == last]) return branch
+ 1 * pow(2, 2)
+ 1 * pow(2, 2)
def int_set(contents):
“””Return a function that represents a set of non-negative integers.
>>> int_set([1, 2])(1) , int_set([1, 2])(3) # 1 in [1, 2] (True, False)
>>> s = int_set([1, 3, 4, 7, 9])
>>> [s(k) for k in range (10)]
[False, True, False, True, True, False, False, True, False, “””
index = bits(contents) def contains(n):
t = index while n:
last, n = n % 2, n // 2
t = t(last) return t(’entry’)
return contains
but 3 is not
True]
8
4. (0 points) Back to the Future
Draw a picture of what would happen if Fibonacci traveled through time to October 22, 2015.