MASSACHVSETTS INSTITVTE OF TECHNOLOGY Depart ment of Electrical Engineering and Computer Science 01-Structure and Interpret at ion of Computer Programs Spring Semester, 2005 Quiz it Closed book two sheets of not es Throug hout this quiz, we have set aside space in which you should write your answers. Please try to put all of your answers in the designated spaces, as we will look only in t his spaces when grading Note that any procedures or code fragment s that you write will be judged not only on correct function, but also on clarity and good programming practice. NAME: Section Number Tutor's n: PART Value grade Grader 15 100
!""# $ % %& '""( ) ) ) % * +& , )- % % % ,) ) . %) , . %,%! $% . . %,% ) % %%& % , , / . ) % %% ,) ! ) . % % ) . , , 0 1 . & 0 % . ! 2 02 3% 2 $4 '( ' 5" 5 ( 6 5" ""
6.001, Spring Semester, 2005--Quiz II Part 1:(25 points) We are going to explore a new kind of data structure, called a cycle. You can think of this as a kind of circular list: indeed we are going to represent a cy cle as a loop of cons cells, where the car of each cell point s to a value, and the cdr of each cell points to the next element in the circular sequence. To create a cycle from a list, we can use (define (list->cycle lst) et-cdr! (last lst) lst) (define (last lst) (if (null? lst) (error "not long enough") (if (null? (cdr lst)) (last (cdr lst))))) (define test-cycle (list->cycle (a b c g))) To see what this struct ure looks like, you might find it convenient to draw a box-and-pointer Associated wit h a cycle, we have several operat ions head will ret urn the value stored at the cell in the cy cle pointed to by its argument, e. g (head test-cycle)will return the value a rotate-left willrot ate t he cycle one element to the left, e.g,(head (rotate-left test-cycle)) will return the value b; (you can think of a cycle as a circular list in which the arranged in clo ckwise sequence, the head is at the top, and"left means rot at ing the sequence counter-clockwise) rotate-right will rot ate the cycle one element to the right, in analogy to rot ate-left, e. g (head (rot ate-right test-cy cle)) will ret urn t he value
' : < , / % & ! ) / ) % % / %2 , % . % %& ,) ) ) % - & ) ) % ) < ) %* ! . %& , %2 <2 % ,) ) % % /% /& . ) = - , 0<7 7 ) % 0,! %% , ) .& , )- %- %2 , ) - % ) ) . 0. % & ! ! , ) - > , ) . ) & ! !& , ) - > ?. ) / . % % ,) ) ) % /, % %* & ) ) % ) & @A % ) %* 7/, %B> , ) . ) )& . & ! !& , ) - !
6.001, Spring Semester, 2005--Quiz Il Defining head is easy (define head car) Question 1: Write the pro cedure rotate-left. Be sure that it ret urns a pointer to the right cell the sequence. You may assume that the argument is a non-empty cycle. Question 2: Write the pro cedure rotate-right. Be sure t hat it returns a pointer to the right cell in the sequence. You may assume that the argument is a non-empty cycle
5 = % %.2 : ) ! 9 % ) % ) ) ) %* ! . %% ) ) % 7. .! : ) ! 9 % ) % ) ) ) %* ! . %% ) ) % 7. .!
6.001, Spring Semester, 2005--Quiz Il Now we want to add a new element to a cycle. This means we want to insert a new cons cell, wit h the supplied argument as its car, before the lo cat ion in the cy cle current ly pointed to by the supplied argument. We are going to treat this as a mut ator(that is, it changes an exist ing dat a struct ure), so we do not want to rely on the value ret urned by the procedure. Hence by convention, let's have the procedure ret urn the sy mbol done. Here is an example behavior define test-cycle (list->cycle '(a b c g))) Value: test-cycle (head test-cy cle) head (rotate-left (rotate-left test -cycle))) Value: c (insert-cy cle! (rotate-left (rotate-left test-cycle))'x)) d test-cy cle head (rotate-left (rotate-left test-cycle))) Value: x head (rotate-left (rotate-left (rotate-left test-cy cle)))) Value: c non-empty cycle. You should use rotate-left and /or rotat e-right where approprlate nt is a Question 3: Write the procedure insert-cycle!. You may assume that the argume
6 , , , , .! ) % % , , % , & , ) ) % % % & 0 ) ) . . 0. ) % ! : ) % % ?) %& ) % < % % B& % , , . ) - 0. ) ! & 0. - & 3% )- ) ) %.0 ! % < 0)- 2 : ) ! . %% ) ) % 7. .! %) % C ,) !
6.001, Spring Semester, 2005--Quiz Il Finally, suppose we want to remove an element from the cycle. Our goal is to remove from the cycle the cell to which the supplied argument points, as well as any pointers into the cycle from removed cells. Note that if we remove the cell to which a global variable refers, we may break our data struct ure, but we will assume that it is the responsibility of t he user to manage pointers into the cycle Question 4: Provide a definit ion for the procedure delet e-cycle!. Use rotate-right, rotate-left head and set-cdr but no other list operations. Also be sure that you change the cdr of the cycl cell t hat contained the deleted value to the empty list
( .& % % , , - ) .! % - ) . ) ,) ) ) % %& % , % . % ) . - %! ) , - ) ,) ) 0 - 0 %& , . 0/ % & 0 , , %% ) % ) %% 0 . ) % % ) .! $- = ) ! D% 0 ) % %! % 0 % ) . ) ) ) . ) ) - ) . %!