Midterm Exam

1. (6 points) List representations.
   For each of the following requirements on a list representation, which would be the best implementation scheme (chose from sequential storage, linked list, or doubly linked list).
   1. you need to frequently insert and delete items anywhere in the list.
   2. you need to insert or delete items 2 or 3 spaces before or after a given item.
   3. you need to access random items in the list.
2. (6 points) Restricted lists
   Given the sequence of operations: insert A, insert B, delete, Insert C, insert D, delete. Which of the following data structures can produce the results shown (choices are stack, queue, or input restricted deque
   1. B C
   2. A C
   3. C D
3. (10 points) Trees
   Consider the following tree:

   

   1. Write the preorder traversal for this tree.
   2. Write the postorder traversal for this tree.
   3. Represent the tree as a binary tree, using the transformation scheme discussed in class.
   4. Is the preorder traversal for the converted binary tree the same as for the original tree?
   5. Is the postorder traversal the same?
4. (10 points) Prove inductively that a tree with n nodes has n-1 edges (links between a parent and a child).
5. (10 points) 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 3) (A C 8) (B D 2) (B E 6) (C F 7) (C D 2) (D F 2) (E F 4)

6. (10 points) Prove one of the following:
   1. that a graph of n nodes and less than n-1 edges is not connected ( n>1 ).
   2. that a graph of n nodes with n or more edges has a cycle ( n>2 ).
7. (20 points) Consider the following Lisp function:

   (defun mystery (list1 list2)
       (cond ((null list1) list2)
             ((null list2) list1)
             (t (cons (car list1) 
                      (cons (car list2)
                            (mystery (cdr list1) (cdr list2)))))))

   1. In English, what does mystery do?
   2. what is the result of the following call:
      (mystery '(1 2 3 4) '(a b c))
   3. Draw the cons cells created in the following call:
      (setq X (mystery (list 1 3 5 6) (list 2 4)))
   4. assuming X is the only immediately accessible pointer, mark the accessible cons cells and tell how many are now garbage.
8. (4 points) Storage Management: Assume that free memory initially contains a list of blocks of the following sizes: 1000, 500, 400, 200, 800.
   Now consider the following sequence of memory allocation requests: 500, 600, 500, 400.
   1. What will the remaining free list be according to the first-fit algorithm?
   2. What will be the remaining free list according to the best-fit algorithm?
9. (3 points) Show the results of the first three passes of insertion sort on the following data (sorting from lowest to highest):
   1 12 3 8 4 9
10. (5 points) Make a heap of the following data:
    5 4 1 9 2 8 6 7 3
    
11. (12 points) Write a lisp program to compute merge sort. You should write (at least) two functions: one called mergesort which takes an arbitrary list of numbers and returns a sorted list by calling the second: mergelists which takes two sorted lists and returns one sorted list containing all of the elements of each list. You can also assume the functions firsthalf which takes a list of n items and returns a list containing the first items, and secondhalf which takes a list of n items and returns a list containing the last items, as well as the functions discussed in class. Make sure to check for the appropriate base cases in each function.
12. (4 points) Draw a (point) quadtree resulting from the following sequence of insertions: