AP CS Programming Test #3

0. (0 points) NAME________________________________________ PERIOD_________

INSTRUCTIONS

• Put your name on the test. Failure to do so will result in a loss of one point. (Let's face it, if you don't know your name, you probably have bigger problems than this test.)
• This test is closed book. No friends, no computer, just you, your brain, your test, and your pencil.
• Where possible, SHOW YOUR WORK! I don’t know how to assign partial credit to the void.
• Don't panic. It's just a test.

1. (5 points; 1 point per line of code) Suppose that the following five lines of Scheme code are executed. Draw the box-and-pointer diagram that results for each line of code.

(Draw one diagram for all five lines.)

```(define a '(1 (2 3) 4))

(define b (cons a (cdr a)))

(define c (list a b))

(set-cdr! (cadr b) 5)

(set-car! (cddar c) 6)```

(1/2 point bonus) What is the output of (cadr a)?

(2 . 5)

2. (3 points) Write Scheme code that will produce the following environment diagram:

Note that proc is a procedure that takes one input, z, but that procedure must be inside a let (the unnamed procedure on the left and the corresponding frame that gets created when it is called immediately). So we get:

```(define proc
(let ((x 5)
(y 7))
(lambda (z) (+ x y z))))
```

3. (8 points) Exercise 3.22 from the book.

Instead of representing a queue as a pair of pointers, we can build a queue as a procedure with local state. The local state will consist of pointers to the beginning and the end of an ordinary list. Thus, the make-queue procedure will have the form

```(define (make-queue)
(let ((front-ptr ...)
(rear-ptr ...))
<definitions of internal procedures>
(define (dispatch m) ...)
dispatch))```

Complete the definition of make-queue and provide implementations of the queue operations using this representation by filling in the blanks.

```(define (make-queue)
(let ((front-ptr '())
(rear-ptr '()))
(define (empty?)

(null? front-ptr))  ; Can actually ignore rear-ptr; need to set rear-ptr to '() in
; delete! if we want to include it here.

(define (insert! datum)
(let ((new-pair (cons datum '())))  ; For some reason, some people never used new-pair

(cond ((empty?) (set! front-ptr new-pair)

(set! rear-ptr new-pair))

(else (set-cdr! rear-ptr new-pair)

(set! rear-ptr new-pair)))))

(define (delete!)  ; Must return the first element of the queue in addition
; to deleting it from the queue
(cond ((empty?) (error "Nothing in queue to delete!"))

(else (let ((datum (car front-ptr)))  ; could also use (peek)

(set! front-ptr (cdr front-ptr))

datum))))

(define (peek)
(cond ((empty?) (error "Nothing in queue to return!"))

(else (car front-ptr))))

(define (dispatch m)
(cond ((eq? m 'insert!) insert!)
((eq? m 'delete!) delete!)
((eq? m 'peek) peek)))

dispatch))```

4. (4 points, 1/2 point per blank) Consider the following code:

```(define (make-thing)
(let ((a 0)
(b 1))
(define (next)
(let ((return b)
(c (+ a b)))
(set! a b)
(set! b c)
return))
(lambda (msg)
(cond ((eq? msg 'next) next)
(else (error "?"))))))
```

(1/2 point per blank) In each blank, fill in what will be returned for that line of code. (The code sequence matters.)

```> (define x (make-thing))

> (x 'next)       #<procedure>

> ((x 'next))     1

> ((x 'next))     1

> ((x 'next))     2

> ((x 'next))     3

> ((x 'next))     5

> ((x 'next))     8
```

In English, what would a good name for make-thing be? make-fibonacci