Super Exciting (How Can It Not Be?) Midterm 2

0. (0 points) NAME______________________________________ PERIOD_______ FISH ________________

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.
• Data Abstraction Violations will result in a maximum 2 out of 5 points. Please make sure to use appropriate selectors when using abstractions!
• Don't panic. It's just a test.

1. (5 points) Draw a box-and-pointer diagram for the following three lines of code.

> (define x '(A ((B) C)))



> (define y (cons 'D x))



> (define z (list (cddadr x) (caadr x) (cadr y)))

2. (5 points) Here is an abstraction for binary trees. Assume that all of these have been written for you and work together 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
tet                              ; shorthand way of writing the-empty-tree
(empty-tree? bintree)            ; #t if the-empty-tree, #f otherwise
(leaf? bintree)                  ; #t if a node with no children, #f otherwise

Here is a binary search tree as discussed in class:

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

and a picture of what that tree looks like: bst --> 15
                                         / \
                                        /   \
                                       6    22
                                      /    /  \
                                     /    /    \
                                    2    17    24
                                        /  \ 
                                       /    \
                                      16    19

(From the homework) Write the function contains? which takes a binary search tree of numbers and a datum as its input and returns #t if the datum is in the tree, #f otherwise.

> (contains? bst 17) 
#t 
> (contains? bst 18) 
#f

Write contains? so that it runs in O(logn) time. If you do not write contains? in O(logn) time, the best score you can get is 2 out of 5. You need to demonstrate understanding of the "search" part of "binary search tree".

(define (contains? bst number)
; YOUR CODE HERE
  (cond ((empty-tree? bst) #f)
        ((< n (datum bst)) (contains? n (left bst)))
        ((> n (datum bst)) (contains? n (right bst)))
        (else #t)))

3. (5 points, from the homework) The procedure bintree-accumulate takes as arguments a binary tree, an operator, an identity value that goes with the operator, and a term function like the one used in previous versions of accumulate that modifies the data in the tree.

> (bintree-accumulate bst + 0 (lambda (x) x))
121
> (bintree-accumulate (left bst) * 1 (lambda (x) x))
12
> (bintree-accumulate bst
                      (lambda (x y z) (append (list x) y z))
                      '()
                      (lambda (x) x))
'(15 6 2 22 17 16 19 24)

Write bintree-accumulate by filling in the blanks.

(define (bintree-accumulate tree op id term)

  (cond ((empty-tree? tree) id)
       
        (else (op (term (datum tree))

                  (bintree-accumulate (left tree) op id term)
                  
                  (bintree-accumulate (right tree) op id term)))))

4. (5 points) (Karly Hou, Carly Feng, Kelly Wang, Alexander Wang) The function deep-filter takes a predicate and a list as inputs. The list it returns is identical to the input list, but all elements, including all elements of all sublists but not the sublists themselves, that don't satisfy the predicate are eliminated. These are examples of inputs and outputs:

> (deep-filter even? '(0 1 2 () 3 4 5 (6 7 8) 9))
'(0 2 () 4 (6 8))
> > (deep-filter number? '(A (B ((3) D)) 5))
'((((3))) 5)

(define (deep-filter pred? lyst)
  (cond ((null? lyst) '())
        ((list? (car lyst))
         (cons (deep-filter pred? (car lyst))
               (deep-filter pred? (cdr lyst))))
        ((pred? (car lyst))
         (cons (car lyst) 
               (deep-filter pred? (cdr lyst))))
        (else (deep-filter pred? (cdr lyst)))))

Extra Credit (1/2 point, so don't do this until you have completed the rest of the test and checked your work)

What would the output be if, in Problem #1, z were typed into the interpreter? (Your answer must be completely correct to receive credit.)