CS 61A Structure and Interpretation of Computer Programs
Spring 2017
INSTRUCTIONS
Mock Midterm 1
• You have 1 hour to complete the exam.
• The exam is closed book, closed notes, closed computer, closed calculator, except one 8.5” × 11” cheat sheet
of your own creation.
• Mark your answers on the exam itself. We will not grade answers written on scratch paper.
Last name
First name
Student ID number
Instructional account (cs61a-_)
BearFacts email
TA
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)
2
1. (10 points) Send Help
b=5
def x(x, help):
def
def
a = def
send(help): print(help) return nope nope(send): print(send) return help send(help)
help ():
return x(“help”)
print(“More”) return a
Expression
a = print(“hi”)() b=a
Interactive Output
print(print(print(“hi”)))
print((lambda x: print(“which”))
(print(“is”)), “first”)
print(b)
x = x(lambda x: print(“oh dear”),
print(“which print”))
x = x(“almost”)
print(x())
Name: 3 2. (10 points) Stuk In Lambda’s
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 frames. • Add all missing values created or referenced during execution. • Show the return value for each local frame.
4
3. (10 points) Gib-me the Words!
Did you know that in Python, you can access elements in a string exactly like you access elements in a list? For example, if we were given the string, Gibbes:
(a) Assigning to the variable g, allows us to access the ’G’ with g[0].
(b) Slicing and concatenation are valid: g[3:] + ’t’ evaluates to ’best’.
Write a function that follows the specs below by creating a list of words out of a string, where a word has no spaces (’ ’). DO NOT USE LEN.
You may only use the lines provided. You may not use any Python built-in sorting functions.
def wordify(s):
“”” Takes a string s and divides it into a list of words.
Assume that the last element of the string is a whitespace.
Duplicate words allowed.
>>> wordify( s u m total of human knowledge )
[’sum’, ’total’, ’of’, ’human’, ’knowledge’]
>>> wordify(’one should never use exclamation points in writing! ’)
[’one’, ’should’, ’never’, ’use’, ’exclamation’, ’points’, ’in’, ’writing!’] “””
start , end , lst = _____________ , ______________ , _______________
for letter in __________________:
if letter != ’ ’:
end = _____________________________
elif start == end:
start , end = __________________ , __________________
else:
lst += [________________________________________]
start , end = ______________________ , ______________________ return ______________________
Name: 5 4. (10 points) Walt is Relevant
We have a list of numeric data points l, and we want to see if a list of relevant numbers s is found in the data. The catch is, we want to see if the numbers in s occur in the same order within the data of l, though not necessarily one after the other. If so, then s is a subsequence of l.
Write a predicate function subseq that takes two lists l and s as arguments, and determines if s is a sub- sequence of l. If so, the function should return True; otherwise, it should return False. We have provided a few doctests to demonstrate the definition and usage.
def subsequence(l, s): “””
Returns true if s is a subsequence of l.
>>> subsequence([9, 1, 4, 5, 6], [4, 5, 6]) True
>>> subsequence([3, 5, 0, 3, 4, 3, 7, 9, 3, 2], [3, 3, 9, 2]) True
>>> # Below , the numbers in seq2
>>> # but not in the same order.
>>> subsequence([3, 5, 5, 8, 3],
False
>>> # Below, not all the numbers
>>> subsequence([3, 5, 5, 8, 3],
False
>>> subsequence([3, 2, 57, 8], [3, 5, 7]) False
“””
if s == []:
return __________________ elif l == []:
return ____________________________________ elif __________________ == __________________:
return subsequence(__________________ , __________________)
else:
return subsequence(__________________ , __________________)
5. (0 points) Games of Berkeley
In the box below, write a positive integer. The student who writes the lowest unique integer will receive one extra credit point. In other words, write the smallest positive integer that you think no one else will write.
appear in seq1 , [8, 5, 3])
in seq2 are present in seq1. [3, 2, 8])