A Better Test 2

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))))))