CS 61A Structure and Interpretation of Computer Programs
Spring 2015
INSTRUCTIONS
Midterm 1
• 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 61A midterm 1 study guide attached to the back of this exam.
• Mark your answers ON THE EXAM ITSELF. If you are not sure of your answer you may wish to provide a brief explanation.
Last name
First name
SID
Email
Login (e.g., cs61a-ta)
TA & section time
Name of the person to your left
Name of the person to your right
All the work on this exam is my own. (please sign)
For staff use only
Q. 1 Q. 2 Q. 3 Total /12 /14 /14 /40
2
1. (12 points) In-N-Out
For each of the expressions in the tables below, write the output displayed by the interactive Python interpreter when the expression is evaluated. The output may have multiple lines. No errors occur.
The first two rows have been provided as examples of the behavior of the built-in pow and print functions. Recall: The interactive interpreter displays the value of a successfully evaluated expression, unless it is None. Assume that you have started Python 3 and executed the following statements:
from operator import add
def re(peat):
return print(peat, peat)
def cheap(eat):
car , seat = re , print seat(car(eat))
return double(eat)
def double(double): if double:
return double + double
elif car(double)(print)(print):
return 1000 else:
return seat (3) seat = double
car
Expression
pow(2, 3)
print(4, 5)
= lambda c: lambda a: lambda r: r(5, a(c))
Interactive Output Expression Interactive Output
8 4 5
print(re(1+2), print(4))
car(1)(double)(pow)
cheap(3)
double(print(1))
cheap(seat(2))
car(0)(seat)(add)
Login: 3 2. (14 points) Supernatural
(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.
Remember: Do not add a new frame when calling a built-in function (such as abs).
batman, superman, ivy = 1, -2, -3
!
def nanana(batman):
while batman(superman) > ivy:
def batman(joker):
return ivy
return -ivy
!
def joker(superman):
if superman(batman):
ivy = -batman
return nanana
!
joker(abs)(abs)
1 2 3 4 5 6 7 8 9
10 11 12 13 14
func joker(superman) [parent=Global]
func nanana(batman) [parent=Global]
func abs(…) [parent=Global]
Global frame batman 1 superman -2 ivy -3
joker nanana
f1: ___________ [parent=____________]
Return Value
f2: ___________ [parent=____________]
Return Value
f3: ___________ [parent=____________]
Return Value
4
(b) (8 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.
1
2
3 func still(glad) [parent=Global] 4
5
6
7
8
9
def still(glad):
def heart(broken):
glad = lambda heart: lambda: heart-broken
return glad(grin) return heart(glad-grin)()
!
broken, grin = 5, 3 still(broken-1)
Global frame
still
broken 5 grin 3
f1: ___________ [parent=____________]
Return Value
f2: ___________ [parent=____________]
Return Value
f3: ___________ [parent=____________]
Return Value
f4: ___________ [parent=____________]
Return Value
Login: 5 3. (14 points) You Complete Me
(a) (4 pt) Implement the longest_increasing_suffix function, which returns the longest suffix (end) of a positive integer that consists of strictly increasing digits.
def longest_increasing_suffix(n):
“””Return the longest increasing suffix of a positive integer n.
>>> longest_increasing_suffix (63134) 134
>>> longest_increasing_suffix (233) 3
>>> longest_increasing_suffix (5689) 5689
>>> longest_increasing_suffix (568901) 1
“””
m, suffix, k = 10, 0, 1 while n:
# 01 is the
suffix ,
displayed
as 1
______________________________________________, last = n // 10, n % 10
if ___________________________________________________________________:
m, suffix , k = ______________ , ___________________________ , 10 * k else:
return suffix return suffix
(b) (3 pt) Add parentheses and single-digit integers in the blanks below so that the expression on the second line evaluates to 2015. You may only add parentheses and single-digit integers. You may leave some blanks empty.
lamb = lambda lamb: lambda: lamb + lamb
lamb(1000)______ + (lambda b, c: b______ * b______ – c______)(lamb(______), 1)______
6
(c) (3 pt) Implement the combine function, which takes a non-negative integer n, a two-argument function f, and a number result. It applies f to the first digit of n and the result of combining the rest of the digits of n by repeatedly applying f (see the doctests). If n has no digits (because it is zero), combine returns result.
from def
operator import add , mul
combine(n, f, result):
“””Combine the digits in non-negative integer n using f.
>>> combine(3, mul, 2) # mul(3, 2) 6
>>> combine(43, mul, 2) # mul(4, mul(3, 2)) 24
>>> combine(6502, add, 3) # add(6, add(5, add(0, add(2, 3))) 16
>>> combine(239, pow, 0) # pow(2, pow(3, pow(9, 0))) 8
“””
if n == 0:
return result else:
return combine(___________ , ___________ , _____________________________)
(d) (4 pt) Implement the memory function, which takes a number x and a single-argument function f. It returns a function with a peculiar behavior that you must discover from the doctests. You may only use names and call expressions in your solution. You may not write numbers or use features of Python not yet covered in the course.
square = lambda x: x * x double = lambda x: 2 * x
def memory(x, f):
“””Return a higher-order function that prints its memories.
>>> f = memory(3, lambda x: x)
>>> f = f(square) 3
>>> f = f(double)
9
>>> f = f(print) 6
>>> f = f(square) 3
None
“””
def g(h):
print(______________________________________________________________)
return _____________________________________________________________ return g