CS61A, Fall 1994
Midterm #3
Question 1 (3 points):
What will the Scheme interpreter print in response to each of the following
expressions? Also, draw a ``box and pointer'' diagram for the result of
each expression. Hint: It'll be a lot easier if you draw the box and
pointer diagram first!
(let ((x (list 1 2 3 4)))
(set-car! (cdr x) (cddr x))
x)
(let ((x (list 1 2 3 4)))
(set-cdr! (cdr x) (caddr x))
x)
(let ((x (list 1 '(2 3) 4)))
(set-car! x (caddr x))
x)
Question 2 (4 points):
Write make-alist!, a procedure that takes as its argument a list
of alternating keys and values, like this:
(color orange zip 94720 name wakko)

and changes it, by mutation, into an association list, like this:
((color . orange) (zip . 94720) (name . wakko))

You may assume that the argument list has an even number of elements.
The result of your procedure requires exactly as many pairs as the
argument, so you will work by rearranging the pairs in the argument
itself. Do not allocate any new pairs in your solution!
Question 3 (4 points):
Define a stream named all-integers that includes all the
integers: positive, negative, and zero.
You may use any stream or procedure defined in the text.
Question 4 (4 points):
We are going to modify the adventure game project by inventing a new kind
of place, called a hyperspace. Hyperspaces are just like other places,
connected to neighboring non-hyperspace places in specific directions,
except that they behave strangely when someone enters one: The person who
entered is sometimes magically transported to another hyperspace. (The
hyperspaces must all know about each other, but they are not connected
to each other through exits. Each hyperspace is connected to specific
neighbors, just as any place is.)
Your job is to define the hyperspace class. The class must be
defined in a way that allows you to know all of its instances. When a
person enters a hyperspace, half the time nothing special should happen,
but half the time the hyperspace should ask the person to
go-directly-to some randomly chosen other hyperspace.
You may use the following auxiliary procedures if you wish:
(define (coin-heads?) (= (random 2) 1))
(define (choose-randomly stuff)
(nth (random (length stuff)) stuff))
Do not modify any existing class definitions.
Group Question (4 points):
Draw the environment diagram for the situation after the following
definition and invocation have been evaluated:
(define (every-nth num lst)
(define (help lst pos)
(cond ((null? lst) '())
((= (remainder pos num) 0)
(cons (car lst) (help (cdr lst) (1+ pos))))
(else (help (cdr lst) (1+ pos)))))
(help lst 1))
(every-nth 2 '(she loves you))
Take a peek at the
solutions