CS 61A Structure and Interpretation of Computer Programs
Spring 2017
INSTRUCTIONS
• You have 2 hours to complete the exam.
• The exam is open book, open notes, closed computer, closed calculator.
• Mark your answers on the exam itself. We will not grade answers written on scratch paper.
Test 1
Last name
First name
Student ID number
CalCentral email
TA
Name of the person to your left
Name of the person to your right
Room in which you are taking exam
Seat number in the exam room
I pledge my honor that during this examination I have neither given nor received assistance.
(please sign)
2
Reference Material.
# Linked Lists (implementations not shown)
empty = … # The empty list
def link(first, rest):
“””A linked list whose first element is FIRST and the linked list
REST is the rest of the list.”””
def first(lnklst):
“””The first item in linked list LNKLST.”””
def rest(lnklst):
“””The list following the first item in linked list LNKLST.”””
def isempty(lnklst):
“””True if LNKLST is empty.”””
def print_link(lnklst):
“””Prints the linked list LNKLST in the format (v0, v1, …).”””
Name: 3 1. (12 points) Evaluate These! (At least one of these is out of Scope: WWPD, Lists, Recursion, Lambda)
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 an error occurs, write “Error”. If an expression yields (or prints) a function, write “
The interactive interpreter displays the value of a successfully evaluated expression, unless it is None, plus all values passed to print.
Assume that python3 has executed the statements on the left:
Expression
pow(2, 3)
Interactive Output
8
print(4, 5) + 1
45 Error
1 + (4 and 6) + (5 or 0) + (0 and 8)
f = lambda x: x
g = lambda y: f(g)
g(2)(2)
0 and print(2)
range(1,20)[-2]
w([1, 2, 3, 1, 8, 2])
f = lambda x: lambda y: \
lambda z: x+y+z
reduce(lambda g, x: g(x),
[1, 2, 3], f)
def w(L):
if len(L) == 0:
return L
elif L[0] in L[1:]:
return w(L[1:])
else:
return [L[0]] + w(L[1:])
def reduce(f, L, init):
if len(L) == 0:
return init
else:
return reduce(f, L[1:],
f(init, L[0]))
1 2 3 4 5
• 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.
Global frame
h g
f1: [parent= ]
Return value
f2: [parent= ]
Return value
f3: [parent= ]
Return value
f4: [parent= ]
Return value
func h(y) [parent=
func g(f) [parent=
func λ ()
> [parent=
> [parent=
> [parent=
]
]
]
]
Name: 5
(b) (6 pt) The environment diagram below corresponds to the execution of a certain program. The frames shown were created in top-to-bottom order, and at one point they were all simultaneously active (their functions had not returned). The diagram shows the situation right after all the functions have returned. Write a Python program whose execution corresponds to this environment diagram. Many answers are possible, but as a guideline, fewer than 10 lines are really needed. In any case, your answer must not create extra frames or additional functions.
Global frame
a
k z3
func a() [parent=Global]
func k(b) [parent=Global]
func g() [parent= f1]
f1: a [parent=Global]
g
Return value 3
f2: k [parent=Global]
b
Write solution here.
f3: g [parent=f1]
Return value 3
Return value 3
6
3. (4 points) Sequence Checking (All are in Scope: HOFs)
Fill in the following function so that it fulfills its comment.
def make_checker(relation, start, end):
“””Assumes that START and END are integers and RELATION is a two-argument
function that returns true/false values. Returns a function that, given
a function f as input, returns True if RELATION returns true for
all adjacent values in the sequence f(START), f(START+1), … f(END-1).
For example, eq_chk, below, checks that the values returned by
its argument function for values 0-4 are all equal, while up_chk checks
that the values returned by the argument function are in strictly
increasing order.
>>> eq_chk = make_checker(lambda x, y: x == y, 0, 5) # Check all equal
>>> eq_chk(lambda x: 3)
True
>>> eq_chk(lambda x: x)
False
>>> up_chk = make_checker(lambda x, y: x < y, 0, 5) # Check increasing
>>> up_chk(lambda x: x)
True
>>> up_chk(lambda x: 3)
False
“””
Name: 7 4. (1 points) Extra
Intheformulaa=0.4+0.3·2m (m=−inf,0,1,2,…),whatdoesareferto?
5. (4 points) Insert (All are in Scope: Linked Lists, Recursion)
Fill in the following function to fulfill its comment. The linked-list interface that you should use is given on page ??. Warning: this problem deals with linked lists, NOT Python lists or tuples. You cannot use +, len(), indexing (L[k]), or list construction ([…]).
def link_insert(lnklst, value, before):
“””Return a linked list identical to LNKLST, but with VALUE inserted just
before the first occurrence of BEFORE in the list, if any. The returned
list is identical to LNKLST if BEFORE does not occur in LNKLST.
The operation is non-destructive.
>>> L = link(2, link(3, link(7, link(1))))
>>> print_link(L)
(2, 3, 7, 1)
>>> Q = link_insert(L, 19, 7)
>>> print_link(Q)
(2, 3, 19, 7, 1)
>>> print_link(link_insert(L, 19, 20))
(2, 3, 7, 1)
“””
if _________________________________________________________________:
return _________________________________________________________
elif _______________________________________________________________:
return _________________________________________________________
else:
return _________________________________________________________
8
6. (4 points) Longest Nondecreasing Suffix (All are in Scope: Lists)
Consider a function up_suffix that is supposed to return the longest suffix of a Python list of integers such
that the suffix consists of nondecreasing values. For example, when applied to
[1, 2, 3, 4, 5, 1, 3, 3, 4]
it should yield [1, 3, 3, 4].
Fill in the following function to do this:
def up_suffix(L):
“””Returns the longest non-descending suffix of Python list L. “””
def longest_suffix_start(L):
“””The index in L of the beginning of the longest nondecreasing suffix
of L. For the empty list, returns 0.
>>> longest_suffix_start([1, 2, 3, 4, 5, 1, 3, 3, 4])
5
>>> longest_suffix_start([2, 4, 6, 8, 10])
0
“””
k = ____________________________________________________________
while __________________________________________________________:
____________________________________________________________
return _________________________________________________________
return L[ ______________________________________________________ : ]
Name: 9
7. (4 points) Post’s Problem (All are in Scope: Recursion, Lists)
Consider two Python lists of strings, where the two lists have equal length, N:
A = [ “a”, “ab”, “bba”]
B = [ “baa”, “aa”, “bb” ]
Is there a sequence of integers—i1, i2, …im—where m > 0 and 0 ≤ ik < N for all k, such that A[i1] + A[i2] + · · · + A[im] = B[i1] + B[i2] + · · · + B[im]?
This is called the Post Correspondence Problem. For this A and B, the answer is yes for m = 4: (2, 1, 2, 0), because
A[2] + A[1] + A[2] + A[0] == "bba" + "ab" + "bba" + "a" == "bbaabbbaa"
B[2] + B[1] + B[2] + B[0] == "bb" + "aa" + "bb" + "baa" == "bbaabbbaa"
On the other hand, the answer is no if we limit m to 3 (so we cannot add more than three strings), or if we shorten the lists by removing A[0] and B[0]. Fill in the following function to determine whether there is a solution.
def correspond(A, B, M):
"""Assuming A and B are lists of strings with len(A) == len(B), and M
is an integer, returns true iff there is a sequence of indices into A
and B, (i1, i2, ..., im), where 1 <= m <= M, such that
A[i1] + A[i2] + ... + A[im] == B[i1] + B[i2] + ... + B[im].
"""
N = len(A)
def can_correspond(sa, sb, M):
"""Return true iff there is some sequence of indices into A and
B, (i1, i2, ..., im), where 1 <= m <= M, such that
SA + A[i1] + A[i2] + ... + A[im] == SB + B[i1] + B[i2] + ... + B[im].
Assumes M is a non-negative integer.
"""
if ___________________________________________________________:
return False
else:
for i in _________________________________________________:
ta = _________________________________________________
tb = _________________________________________________
if ta == tb:
return True
elif can_correspond(__________, ___________, ___________):
return True
return False
return can_correspond("", "", M)