COMPSCI 61A Study Guide - Final Guide: Cheat Sheet, Insert Key, Kruskal'S Tree Theorem
CS 61A Structure and Interpretation of Computer Programs
Spring 2015 Final Exam
INSTRUCTIONS
•You have 3 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 3 official 61A midterm study guides 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
Login
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 Q. 5 Q. 6 Total
/16 /14 /8 /18 /14 /10 /80
2
THIS PAGE CONTAINS NO QUESTIONS
For your reference, a complete implementation of the Tree class appears below.
class Tree :
""" A tree with entry as its root value .
>>> Tree (1)
Tree (1)
>>> Tree (1 , [])
Tree (1)
>>> Tree(Tree(1))
Tree ( Tree (1))
>>> t = Tree (1 , [ Tre e (2) , T ree ( 3)])
>>> t
Tr ee (1 , [ Tr ee (2) , Tree ( 3)])
>>> t . entry
1
>>> t . branches
[ Tree (2) , Tree (3)]
"""
de f __ in it __ ( self , entr y , b ra nch es =( )) :
self . entry = entry
for branch in branches :
assert isi ns ta nc e ( branch , Tree )
self . b ran ches = list ( bra nche s )
def __r epr __ ( self ):
if self . br anch es :
bra nc hes _s tr = ’ , ’ + repr ( self . br anch es )
else:
branches_str = ’’
ret ur n ’ T ree ( {0 }{ 1} ) ’. f or ma t ( s elf . ent ry , b r an ch es _s tr )
3
1. (16 points) Lumberjack
For each row below, fill in the blanks in the output displayed by the interactive Python interpreter when the
expression is evaluated. Expressions are evaluated in order, and expressions may affect later expressions.
Whenever the interpreter would report an error, write Error. You should include any lines displayed before
an error. Reminder: The interactive interpreter displays the repr string of the value of a successfully evaluated
expression, unless it is None. The first two rows are completed for you.
The Tree class appears on the previous page. It’s also on the Midterm 2 Study Guide, but the exam version is
complete. Assume you have started Python 3, executed the Tree class statement, then executed the following:
odd = lambda x: ( x % 2) == 1
big = lambda x: x > 2
f = lambda f : lambda g : lambda x : not ( f( x ) or g( x ))
de f c ho os e (s , f ):
for i in rang e (0 , len ( s )):
if f (s [i ]):
return Tree (i , [ Tree (j ) for j in s [i :] if not f (j )])
lumber = Tree (1)
ja ck = Tree (1 , [ lumber , lu mber ])
lumber . entry = 2
lumber = Tree ( l umber )
class Wood ( Tree ):
de f __ in it __ ( self , s ou rc e ):
source . entry += 1
Tr ee . _ _i ni t_ _ ( self , Tr ee ( s our ce ))
Expression Output
Tree(2, [Tree(3)]) Tree(2, [Tree(3)])
1/0 Error
tuple(map(odd, filter(big, range(5))))
sum(filter(f(big)(print), range(1, 5)))
lumber
jack.branches
print(choose([1], big))
choose([2, 3, 4], odd)
choose([4, 3, 2], f(big)(odd))
Wood(Tree(2))
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: 1 q. For your reference, a complete implementation of the tree class appears below. class tree : """ a tree with entry as its root value . >>> t = tree (1 , [ tree (2) , tree (3)]) Tree (1 , [ tree (2) , tree (3)]) >>> t . r a n c h e s. For each row below, ll in the blanks in 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. You should include any lines displayed before an error. Reminder : the interactive interpreter displays the repr string of the value of a successfully evaluated expression, unless it is none.
