CMSC--202 Computer Science II for Majors
Fall 1997 16 November 1997 Final Review

The final exam will be held at the following times and places. Please note that these are NOT the usual class times.

Cumulative Material

Every question from Exam 1 and from Exam 2 (the exams, not the reviews for the exams). The questions will be modified slightly so don't just memorize the answers.

Trees

1. Define the following terms
   • tree (formal definition)
   • binary tree (formal definition)
   • binary search tree
   • leaf of a tree
   • degree of a tree node
   • degree of a tree
   • path in a tree
   • length of a path in a tree
   • descendents of a node in a tree
   • ancestors of a node in a tree
   • depth of a node in a tree
   • height of a node in a tree
   • height of a tree

2. Give an ADT for binary trees.

3. Draw the expression tree for the expression a*(b+c)-(d+(e-f)*g)

4. For the tree

   

   1. What is the height of node A?
   2. What is the height of the tree?
   3. What is the depth of node E?
   4. What is the parent of node F?
   5. Name the descendent(s) of node B.
   6. Name the leaves in the tree.

5. Write a C function tree_type copy_tree(tree_type T) that returns a copy of binary tree T

6. Write a C function

   tree_type expand_leaf(tree_type T, tree_item_type x, tree_item_type y)
   

   that returns a new binary tree that is identical to the binary tree T except that every leaf in T now has a left child and a right child whose values are equal to x and y, respectively. For example, invoking expand_leaf(T, 9, 12) on the tree on the left produces the tree on the right.

7. Write a C function int height(tree_type T) that returns the height of the binary tree T.

8. Write a C function

   tree_type delete_root(tree_type T)
   

   that returns a new tree that contains every value stored in T except for the value stored in the root of T. The root of the new tree should be one of the children of the root of T (the other child must remain where it was); each child of the root of the new tree should be either a child or a grandchild of the root of T, and so on. If delete_root is called on an empty tree, or on a tree containing exactly one node, it should return the_empty_tree. The function delete_root should be non-destructive (not modify its argument in any way). Hint: The base cases apply when T is empty or if the left child is empty. If the left child is empty, the resultant tree is the right child. Use wishful thinking otherwise: ``if only I could delete the root of the left child of T, then I could delete the root of T. I would make the left child of T (with its root deleted) be the root of the new tree. I would use the right child of T as the right child of this new root.''

9. Write a C function

   BOOL same_tree(tree_type T1, tree_type T2)
   

   that returns TRUE if binary trees T1 and T2 are exactly the same (same values, same structure), and returns FALSE otherwise. You may assume that values of tree_item_type can be compared by means of the == operator.

10. Write a C function

      tree_type bst_insert(tree_item_type item, tree_type T)
    

    that inserts item into the binary search tree T. After the insertion, T must remain a binary search tree. You may assume that tree_item_type values are comparable using the ==, <, and > C operators. Draw the binary search tree resulting from sequentially calling bst_insert on an initially empty binary tree with the values 9,12,5,15,7,10,18.

Tree Traversal

1. For the tree

   

   1. Write the node labels in pre-order order
   2. Write the node labels in in-order order
   3. Write the node labels in post-order order

2. 1. Write the C function

      void PreOrder(tree_type T, void (*operation)(tree_type))
      

      that takes a binary tree T and performs operation on each of its nodes during a preorder traversal.

   2. Write C code, using the ADT operations for binary tree, to construct this binary tree of char

      

   3. Write a function void Foo(tree_type T) that takes a binary tree, T, of char and performs some function (your choice) on the tree. Briefly describe what the function does in your own words.
   4. Show the function call of PreOrder on the tree you constructed above, using the function Foo you defined above.

Search

Functions for DFS and BFS of binary trees from the notes will given to you in the exam, if needed.

1. Let tree T be this tree

   

   and let the function IsB be defined as

   BOOL IsB(tree_type T)
   {
      return (tree_data(T) == 'B') ? TRUE : FALSE;
   }
   

   1. Draw the subtree returned by DFS(T, IsB)
   2. Draw the subtree returned by BFS(T, IsB)

2. Given an array containing the sequence 1,5,29,45,67,76,92,104,187,234 (in that order)
   1. state each comparison made in finding the number 234 using linear search. (For example, 234:1 is a comparison of 234 with 1.)
   2. state each comparison made in determining that the number 48 is not present using linear search.

3. Given an array containing the sequence 1, 5,29,45,67,76,92,104,187,234 (in that order)
   1. state each comparison made in finding the number 234 using binary search. (For example, 234:1 is a comparison of 234 with 1.)
   2. state each comparison made in determining that the number 48 is not present using binary search.

4. Given the following sequence of integers (for example, integers received from the keyboard)

   29,234,1,45,92,76,67,187,104,5
   

   (in that order)
   1. draw the binary search tree that would result from inserting the integers in the order given.

   2. state each comparison made in finding the number 234 in the tree (For example, 234:1 is a comparison of 234 with 1.)
   3. state each comparison made in determining that the number 48 is not present in the tree.
   4. write the integers as they would be encountered in an in-order traversal of the tree.

5. For the given set of inputs 1,5,29,45,67,76,92,104,187,234 (in that order)
   1. give a pictorial representation of a hash table of with 5 buckets containing the above set of inputs entered in the order given. Assume the hash function is:

      int hash(hash_item_type x)
      {
       return (x % 5);
      }
      

   2. state each comparison made in finding the number 234 in the table. (For example, 234:1 is a comparison of 234 with 1.)
   3. state each comparison made in determining that the number 48 is not present in the table.

6. Name two qualities of a good hashing function.

7. Linear search can be done on data in an array or in a list. Name an advantage and a disadvantage of the list implementation over the array implementation.

8. Binary search can be done on data in a sorted array or in a binary search tree. Name an advantage and a disadvantage of the array implementation over the BST implementation.

Sorting

1. The signature of the standard library function qsort is

   void qsort(void * base, size_t nmemb, size_t size, 
              int (* compar)(const void *, void *));
   

   1. Define types and variables necessary to produce an array of N structs. The structs have a field char * key, in addition to at least one other field of your choice. The array should be assigned to the variable A.

   2. Define a function precedes as the compar function for use with qsort on array A. precedes causes sorting in ascending (lexicographic) order by the key field.

   3. Show the call to qsort that will sort A

2. How many permutations of N distinct items are there?

3. Show that the maximum number of comparisons necessary to sort three items is 3. Do this by using a comparison tree.

4. Show that the minimum number of comparisons necessary to sort three items is 2. Do this by using a comparison tree.

5. Show that the average number of comparisons necessary to sort three items is . Do this by using a comparison tree.

6. Explain: selection sort is an algorithm on average.

7. Explain: quicksort is an algorithm on average, but is an algorithm worst case.

8. Code from the notes for selectsort, mergesort, and quicksort will be given to you on the exam if needed.

   Given an array containing the integers 12 9 3 6 4 1 (in that order),

   1. Show the array as it is sorted by the function selectsort. Show the array before the call to the function swap. Show the array even if it is unchanged.

   2. Show the array as it is sorted by the function mergesort Show the array before each call of the function merge. Show the array even if it is unchanged.

   3. Show the array as it is sorted by the function quicksort Show the array before each call of the function partition. Show the array even if it is unchanged.

Asymptotic Analysis

1. Fill in the following in increasing order

   

   from the set

   

2. Give a formal definition of ``Big-Oh.'' Do not use terms such as ``upper-bound,'' this must be a formal, mathematical definition.

3. Prove that the time complexity to build a queue of n items, using n enqueue operations, is when the queue is implemented as a simple list. What is the time complexity for the pointer-based implementation of queue?

4. Linear search can be done on data in an array or in a list. What is the average time complexity for successful search using an array? Using a list? Name an advantage of the list implementation. Name an advantage of the array implementation.

5. Binary search can be done on data in a sorted array or in a binary search tree. What is the average time complexity for successful search using the array? Using the BST? What is the worst case time complexity for each? Name an advantage of the BST implementation. Name an advantage of the sorted array implementation.