# Scheme: exam-level questions

If you need help reviewing Scheme, take a look at these resources:

Each question has a "Toggle Solution" button -- click it to reveal that question's solution.

## What would Scheme print

### Question 1

For the following questions, write the value that the expression evaluates to if you type it into `scm`. If the expression contains a function (or multiple), write "FUNCTION" in place of that function. If the expression causes an error, write "ERROR".

``````scm> (cons 1 (cons 2 (cons 3 (cons 4 nil))))
______(1 2 3 4)
scm> (cons (cons (cons 3 2) 1) (cons 4 nil))
______(((3 . 2) . 1) 4)
scm> (cdr (cons (cdr (list 1 2)) (cons 3 (cons 4 nil))))
______(3 4)
scm> (define lst (cons (lambda (x) (cons x x)) nil))
scm> ((car lst) lst)
______((FUNCTION) FUNCTION)
scm> (define (x) (lambda (x) (list x x)))
scm> (((car ((x) x))) 4)
______(4 4)``````

## Code-Writing questions

### Question 2

Implement a function `count-stairways`, which takes a number `n` as an argument. Assuming you can only take 2 or 3 steps at a time, return the number of ways you can reach the top of a staircase with `n` stairs.

This is different than the usual `count-stairways` — notice that this time, we can only take 2 or 3 steps, rather than 1 or 2.

``````(define (count-stairways n)
)

; Tests
scm> (count-stairways 1)
0
scm> (count-stairways 4)
1
scm> (count-stairways 5)
2
scm> (count-stairways 8)
4``````
``````(define (count-stairways n)
(cond ((= n 1) 0)
((or (= n 2) (= n 3)) 1)
(else (+ (count-stairways (- n 2))
(count-stairways (- n 3))))))``````

### Question 3

Implement a function `count-serpinski`, which takes a numbero `depth` as an argument. The function calculates how many triangles are contained in a Serpinski's triangle with the given depth. See the tests for examples.

How can you use recursive calls on n-1 to build your answer for n?

``````(define (count-serpinski depth)
)

; Tests
scm> (count-serpinski 1)
1
scm> (count-serpinski 2)
5
scm> (count-stairways 3)
17
scm> (count-stairways 4)
53``````
``````(define (count-serpinski n)
(if (= n 1)
1
(+ 2 (* 3 (count-serpinski (- n 1))))))``````

The recursive call can be derived as follows:

1. There are three smaller n-1 serpinski triangles at each of the corners
2. There are two additional triangles drawn — the triangle in the center, and the overall triangle.

## Fill-in the blank questions

Fill in the blanks for the `construct` function. It takes a value and a list of lists as arguments. It returns a new list of lists, where each element is a list from the old list, but with the value added to the front.

``````(define (construct value lists)
(if ______
______
(cons _____________
_____________)))
)

; Tests
scm> (define lists '((10) () (4 3) (2 5 3)))
lists
scm> (construct 6 lists)
((6 1) (6) (6 4 3) (6 2 5 3))
scm> (construct 6 '())
()``````
``````(define (construct value lists)
(if (null? lists)
nil
(cons (cons value (car lists))
(construct value (cdr lists)))))``````