CS 61A Structure and Interpretation of Computer ProgramsFall 2012 Final ExaminationINSTRU CTIO NS• You have 3 hours to complete the exam.• The exam is close d book, closed notes, closed computer, closed calcu l at or, 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 ex am.• Mark your answers ON THE EXAM ITSELF. If you are not sure of your answer you may wish to provi de abrief explanation.Last nameFirst nameSIDLoginTA & section timeName of the person toyour leftName of the person toyour rightAll the work on this examis my own. (ple ase sign)For sta↵ 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 a↵ect 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]]mar(jan, feb)jannext(iter(jan))len(mar(range(5, 50), range(20, 200)))4(b) (10 pt) For each of the following expressions, write the repr string of the value to which the expressionevaluates. S pecial cases: If an expression evaluat es 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 th eStream 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)(fire.first, fire.rest.first)fire.rest is fire.rest(ash.first, ash.rest.first)ash.rest.rest.rest.firstLogin: 52. (16 points) Web Rater Ink(a) (8 pt) Fill in the environment diagram that results from executing the code below until the enti re 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 wil l :• 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 Value6(b) (8 pt) Fill in the environment diagram that results from executing the code below until the enti r e 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 wil l :• 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 ValueLogin: 73. (30 points) Twin Breaker(a) (8 pt) Run-length encoding (RLE) is a technique used to compress sequen ce s that contain repeatedelements. For example, the sequ en ce 1, 1, 1, 4, 2, 2, 2, 2 would be enco d ed 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 encoding of a sequence.>>> 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 elements :if ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ _ :self. runs. append ( ________________________________________ )if ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ _ :last , count = _ ____ ___ ____ ___ ____ ___ ____ ___ ____ ___ ___ ____else:count += 1_________________________________________________________________def __len__ ( self ):return sum( ______________________________________________________ )def __getitem__ (self , k):run = 0while ___________________________________________________________ :k, run = ____________________________________________________return self.runs[run ][1]8(b) (6 pt) A path through a tree is a sequence of connected nodes in which each node app e ars at most once.The height of a t r ee 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 (_________________________________________________________________________________________________________________________________________________________)def longest ( tree ):""" Return the length of the longest path between any two nodes .>>> longest( None )0>>> longest( Tree (5))1>>> [ longest (b) for b in (s . left .left , s . left , s )][3 , 3, 4]>>> longest( t)12"""if tree is None :return 0return max(