CS 61A Structure and Interpretation of Computer ProgramsFall 2012 Final Examination SolutionsINSTRUCTIONS• 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 three official 61A 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 abrief explanation.Last nameFirst nameSIDLoginTA & section timeName of the person toyour leftName of the person toyour rightAl l the work on this examis my own. (please sign)For staff use onlyQ. 1 Q. 2 Q. 3 Q. 4 Total/20 /16 /30 /14 /802THIS PAGE INTENTIONALLY LEFT BLANKLogin: 31. (20 points) Bank Rewrite(a) (10 pt) For each of the following expressions, write the repr string of the value to which the expressionevaluates. Special cases: If an expression evaluates to a function, write Function. If evaluation wouldnever complete, write Forever. If an error would occur, write Error.Assume that the expressions are evaluated in order. Evaluating the first may affect thevalue of the second, etc.Assume that you have started Python 3 and executed the following statements:jan = [1 , 3 , 5]feb = [3 , 5 , 7]def mar ( apr , may ):if not apr or not may :return []if apr [0] == may [0]:return mar ( apr [1:] , may [1:]) + [ apr [0]]elif apr [0] < may [0]:return mar ( apr [1:] , may )else :return mar ( apr , may [1:])ExpressionEvaluates to5*525feb[jan[0]]5mar(jan, feb)[5, 3]jan[1, 3, 5]next(iter(jan))1len(mar(range(5, 50), range(20, 200)))304(b) (10 pt) For each of the following expressions, write the repr string of the value to which the expressionevaluates. Special cases: If an expression evaluates to a function, write Function. If evaluation wouldnever complete, write Forever. If an error would occur, write Error.Assume that you have started Python 3 and executed the following statements after executing theStream class statement from the Final Exam Study Guide:from operator import add , muldef stone (a ):return Stream (a , lambda : stone ( a +1))rock = stone (3)def lava (x , y , z ):def magma ():return lava ( x . rest , y . rest , z )volcano = z ( x . first , y . first )return Stream ( volcano , magma )fire = lava ( rock , rock . rest , mul )def hot ():crater = Stream (0 , lambda : lava ( crater , rock , add ))return craterash = hot ()ExpressionEvaluates to(1, rock.first)(1, 3)(rock.rest.first, rock.rest.rest.first)(4, 5)(fire.first, fire.rest.first)(12, 20)fire.rest is fire.restTrue(ash.first, ash.rest.first)(0, 3)ash.rest.rest.rest.first12Login: 52. (16 points) Web Rater Ink(a) (8 pt) Fill in the environment diagram that results from executing the code below until the entire programis 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, labels, and parent annotations to all local frames.• Add all missing values created during execution.• Show the return value for each local frame.Global framesnow func snow(x)def snow(x): def ice(x): if x == 0: return 1 return 2 + rain(ice, x) def rain(g, h): return 3 + g(h-x) return ice(x)snow(4)Return ValueReturn ValueReturn ValueReturn Valuef1: snowx 4icerainfunc ice(x) [parent=f1]func rain(g, h) [parent=f1]6 ice [parent=f1]x4 rain [parent=f1]gh 4 ice [parent=f1]x06416(b) (8 pt) Fill in the environment diagram that results from executing the code below until the entire programis 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, labels, and parent annotations to all local frames.• Add all missing values created during execution.• Show the return value for each local frame.Global framebox func box(a)def box(a): def box(b): def box(c): nonlocal a a = a + c return (a, b) return box gift = box(1) return (gift(2), gift(3))box(4)Return ValueReturn ValueReturn ValueReturn Valuef1: boxa 9boxgiftfunc box(b) [parent=f1]f2: box [parent=f1]b 1boxfunc box(c) [parent=f2] box [parent=f2]c2c 3 box [parent=f2]6tuple0119tuple0 11tuple0 1Login: 73. (30 points) Twin Breaker(a) (8 pt) Run-length encoding (RLE) is a technique used to compress sequences that contain repeatedelements. For example, the sequence 1, 1, 1, 4, 2, 2, 2, 2 would be encoded as three 1’s, one 4, and four 2’s.Fill in the blanks in the RLE class below, so that all doctests pass.class RLE ( object ):""" A run - length enco ding of a sequ ence .>>> RLE ([2 , 2 , 2 , 2, 2, 7]). runs[(5 , 2) , (1 , 7)]>>> s = RLE ([1 , 1, 1 , 4 , 2, 2, 2, 2])>>> s . runs[(3 , 1) , (1 , 4) , (4 , 2)]>>> len ( s )8>>> s [2] , s [3] , s [4] , s [5](1 , 4, 2 , 2)"""def __init_ _ (self , elements ):last , count = None , 0self . runs = []for elem in element s :if last != elem and count > 0:self . runs . append (( count , last ))if last != elem :last , count = elem , 1else :count += 1self . runs . append (( count , last ))def __len__ ( self ):return sum ( pair [0] for pair in self . runs )def __getitem__ (self , k ):run = 0while k >= self . runs [ run ][0]:k , run = k - self . runs [ run ][0] , run +1return self . runs [ run ][1]8(b) (6 pt) A path through a tree is a sequence of connected nodes in which each node appears at most once.The height of a tree is the longest path starting at the root. Fill in the blanks in the calls to max below,so that all doctests pass. Write each operand expression on a separate line. You may not need to useall of the blank lines. This question uses the Tree class statement from the Midterm 2 Study Guide.You may assume that height works correctly when implementing longest.s = Tree (0 , Tree (1 , Tree (2 , Tree (3) , Tree (4))))t = Tree (5 , Tree (6 , Tree (7 , s , Tree (8)) , Tree (9 , None , Tree (10 , s ))))def height ( tree ):""" Return the length of the longest path from the root to a leaf .>>> height ( None )0>>> height ( s )4>>> height ( t )8"""if tree is None :return 0return 1 + max ( height ( tree . left ) ,height ( tree . right ))def longest ( tree ):""" Return the length of the longest path from any two nodes .>>> longest ( None )0>>> longest ( Tree (5))1>>> [ longe st (b) for b in ( s . left . left , s . left , s)][3 , 3, 4]>>> longest ( t )12"""if tree is None :return 0return max ( longest ( tree . left )