**AP
Much Better Programming Test #2**

**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**. - Friends are not permitted.
- 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) **(Michael Qu) Draw box-and-pointer diagrams for the following:

**NOTE: When referencing a pair, draw an arrow from the originating car or cdr to that pair. The target of the arrow is pointing at the whole pair. When referencing a value, just write in the value.**

For example, the (cons 4 a) in the second part refers to a value 4 and reference a.

> (define a (cons 1 (list 2 3))) > (define b (list (cons 4 a) 5)) > (define c (list (cdr b) a (cadr a))

**2. (10 points in two problems)** A *node* contains a datum and references
to other nodes, called children. A *binary tree* is a tree in
which each node has at most two children. A *binary search tree* is
a tree in which children are broken into categories *left* and *right*,
with children on the left having values less than that of the parent node
and children on the right having values that are greater than that of the
parent node. Here is a visual example of a binary search tree:

bst --> 15 / \ / \ 6 22 / / \ / / \ 2 17 24 / \ / \ 16 19

A *leaf* is a node with no children. There are four leaves in the above binary
search tree; they: 2, 16, 19, and 24.

The abstraction for binary trees includes the following functions. Assume that all of these have been written for you and work properly:

(make-bintree datum left right) ; creates a binary tree node (datum bintree) ; returns the datum of a node in a binary tree (left bintree) ; returns the left subtree of a binary tree (right bintree) ; returns the right subtree of a binary tree the-empty-tree ; a tree with no content (empty-tree? bintree) ; #t if the-empty-tree, #f otherwise (leaf? bintree) ; #t if a non-empty tree with no children, #f otherwise

The above binary search tree `bst`, above, is constructed as follows:

(define bst (make-bintree 15 (make-bintree 6 (make-bintree 2 the-empty-tree the-empty-tree) the-empty-tree) (make-bintree 22 (make-bintree 17 (make-bintree 16 the-empty-tree the-empty-tree) (make-bintree 19 the-empty-tree the-empty-tree)) (make-bintree 24 the-empty-tree the-empty-tree))))

**2A. (5 points)** The `max` function (which is part of the Scheme language) takes any number of numeric inputs and returns the maximum.

> (max 2 4 6 8 9 7 5) 9

The function `maxpath` takes a binary tree and finds the largest sum of data connecting a root to a leaf.

> (maxpath bst) ; Greatest sum is 15+22+17+19 = 73 73

Write `maxpath`.

(define (maxpath bst) (cond ((empty-tree? bst) 0) (else (+ (datum bst) (max (maxpath (left bst)) (maxpath (right bst)))))))

**2B. (5 points)** (Rishi Iyer) The function `pathway` takes a number and a *binary search tree* containing numbers as its two inputs. It returns a list of steps on how to get to the value in the binary search tree, terminating with the word `done`. If the value is not in the binary search tree, the last element of the returned list is `#f`. Here are examples of how it works with the sample tree, `bst`:

> (pathway 19 bst) (right left right done) > (pathway 15 bst) (done) > (pathway 33 bst) (right right right #f) > (pathway 2 bst) (left left done) > (pathway 8 bst) (left right #f)

Write `pathway`.

**NOTE: #f and 'done need to be put into lists so that the sequence of conses will terminate with a list. Try removing the list functions to see what happens without them.**

(define (pathway num bst) (cond ((empty-tree? bst) (list #f)) ((< num (datum bst)) (cons 'left (pathway num (left bst)))) ((> num (datum bst)) (cons 'right (pathway num (right bst)))) (else (list 'done))))

**3. (5 points) **(Alex Xiao, Dillon Hu, Tavor Baharav) Write a procedure `deepmap` that takes an operation and a list as inputs. It should return the list but all elements including elements in nested lists should have been operated on.

> (deepmap square '(1 2 3 4 5 (5 6))) (1 4 9 16 25 (25 36)) > (deepmap (lambda (x) (cons x 'l)) '(dillon tavor alex (pikachu peter (jeffrey)))) ((dillon . l) (tavor . l) (alex . l) ((pikachu . l) (peter . l) ((jeffrey . l))))

Write `deepmap`.

**NOTE: Regardless of whether the car is a list, the cdr needs to be deepmapped. Also, if lyst is empty, it doesn't matter whether we use lyst or '(); they are both empty lists.**

(define (deepmap func lyst) (cond ((null? lyst) lyst) ((list? (car lyst)) (cons (deepmap func (car lyst)) (deepmap func (cdr lyst)))) (else (cons (func (car lyst)) (deepmap func (cdr lyst))))))