COMPSCI 61A Study Guide - Midterm Guide: Cheat Sheet, Ovaltine, Kruskal'S Tree Theorem
CS 61A Structure and Interpretation of Computer Programs
Spring 2015 Midterm 2
INSTRUCTIONS
•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 (...@berkeley.edu)
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 Q. 4 Total
/12 /12 /14 /12 /50
2
1. (12 points) Mutater-tot
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. Expressions are evaluated in
order, and expressions may affect later expressions.
Whenever the interpreter would report an error, write Error. If execution would take forever, write Forever.
Assume that you have started Python 3 and executed the following statements:
def ready ( betty ):
print ( len ( b etty ))
betty [0]. append ( betty )
return betty [0:1]
def ge t_s et ( s ):
ready (s)
ret urn s. pop ()
def go ( on , up ):
if up :
re turn go ( on [0] , up -1)
else:
return on
f = [1 , [2]]
g = [[3 , 4], [5] , 6]
h = [g , g ]
Expression Interactive Output
f.pop() [2]
h[1].pop()
g[g[1][0]-g[0][1]]
len(ready(g))
g[0][2][0][1]
ready(get_set(h))[0][0]
[len(go(h, k)) for k in range(3)]
Login: 3
2. (12 points) Vulcans
(a) (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.
Remember: Do not add a new frame when calling a built-in function (such as abs). The built-in abs
function is always written as func abs(...) [parent=Global].
def live(long):
def prosper(spock, live):
nonlocal long
if len(long) == 1:
return spock+1
long[1] = live(long[0])
long = long[1:]
prosper(long[0], abs)
return spock[0]+1
prosper(long, lambda trek: trek-3)
live([1, 4])
1
2
3
4
5
6
7
8
9
10
11
f1: ___________ [parent=____________]
Return Value
Global frame live
func live(long) [parent=Global]
f2: ___________ [parent=____________]
Return Value
f3: ___________ [parent=____________]
Return Value
f4: ___________ [parent=____________]
Return Value
22
COMPSCI 61A Full Course Notes
Verified Note
22 documents
Document Summary
If you are not sure of your answer you may wish to provide a brief explanation. All the work on this exam is my own. (please sign) For each of the expressions in the table below, write the output displayed by the interactive python interpreter when the expression is evaluated. Expressions are evaluated in order, and expressions may a ect later expressions. Whenever the interpreter would report an error, write error. 3 (a) (8 pt) fill in the environment diagram that results from executing the code below until the entire program is nished, an error occurs, or all frames are lled. 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).
