Written Assignment #5: Practice Midterm

(Note: each 5 points on this practice exam can replace one missed point on other written assignments - thus this assignment can replace up to 20 points total)

1. (4 pts) Give an algorithm for inserting a new item j after item i in a doubly linked list. Assume that each node (e.g., i, j has fields prev and next.

2. (4 pts) Given the following operations to an empty stack, what will the stack contents be afterwards:
   push a, push b, push c, pop, push d, pop, pop, push e

3. (4 pts) Given the following operations to an empty queue, what will the contents be afterwards:
   insert a, insert b, insert c, remove, insert d, remove, remove, insert e

4. (5 pts) Give a topological sort for the following relations:
   a < b, a < c, d < b, e < c, a < e, a < d

5. (10 pts) Prove inductively that a binary tree of depth d has at most nodes.

6. (12 pts) Consider the following tree:

   	Write the preorder traversal for this tree. Write the inorder traversal for this tree. Write the postorder traversal for this tree.

7. (10 pts) Compute the minimal spanning tree for the following graph, given in edge-based form (each edge is a list of three elements, the two nodes and the cost of the edge):

       (A B 6) (A C 3) (B C 3) (B E 6) (C E 7) (C D 2) (E D 3)

8. (4 pts) Write the graph from the previous problem in vertex-based notation.

9. ( 3 pts) Does this graph have a Eulerian cycle?

10. (4 pts) Draw box and pointer diagrams for the following lisp expressions
    1. (A . B)
    2. (A B C)
    3. (cons 'A (cons 'B nil))
    4. (list 'A 'B)

11. (20 pts) Consider the following Lisp function:

    (defun mystery (list)
        (cond ((null list) nil)
              ((null (cdr list)) list)
              (t (cons (car list) 
                       (append (mystery (cdr list))
                               (cons (car list) nil))))))

    1. In english, what does mystery do?
    2. what is the result of the following call:
       (mystery '(a b c))
    3. Draw the cons cells created in evlauating the following expression:
       (setq X (mystery (list 1 3 5 6)))
    4. assuming X is the only immediately accessible pointer, mark the accessible cons cells and tell how many are now garbage.

12. (15 pts) Write a lisp program to compute insertion sort. You should write (at least) two functions: one called insertionsort which takes an arbitary list of numbers and returns a sorted list by repeatedly calling the second: insert, which takes an item and a sorted list, and returns a new list with the item included in it's proper location.

13. (5 pts) Assume you have the following points as part of a point quadtree:

    Chicago, (10, 40)   (the root)
    Miami, (90, 100)

    If you are looking for items inside the box centered at Miami with horizontal extent 100 and vertical extent 60, which quadrants of Chicago can you avoid searching?