CSCI 2270 Computer Science 2: Data Structures
Spring 2003
Karl Winklmann

The final covers sorting algorithms: selection sort, merge sort, quicksort, heapsort (all covered in Chapter 13), counting sort, radix sort, bucket sort (see sorting.html); hash tables (see Section 12.2); recursion (as used in Assignment 4); 2-D arrays (as used in Assignment 5); breadth-first search, including shortest path algorithms (Chapter 15) . Contrary to an earlier handout, parsing won't be on the final.

The exam is open textbook (but no other books), open notes. No use of computers. There are 5 problems, each worth 20 points.

1. The following function Graph::bfs was useful in Assignment 5 to carry out a breadth-first search.

   void Graph::bfs ()
   {
       if (n == 0)
           return;
   
       queue <int> Q;
   
       int i;
       int j;
       int node;
   
       // to keep track of which nodes have been seen
       bool* visited = new bool [n];
   
       // initializing arrays
       for (i = 0; i < n; i++)
           visited [i] = false;
   
       // initialize array that kleeps track
       // of which edges have been added to the
       // spanning tree
       for (i = 0; i < n; i++)
           for (j = 0; j < n; j++)
               treeEdges [i][j] = false;
   
       // seed queue
       Q.push (0);
       visited [0] = true;
   
       // loop that does the search
       while (!Q.empty ())
       {
           // removed node from queue
           node = Q.front ();
           Q.pop ();
   
           // add its not yet visited neighbors to the queue
           for (i = 0; i < n; i++)
           {
               if (edges [node][i] && !visited [i])
               {
                   Q.push (i);
                   visited [i] = true;
   
                   // and put into the tree the edges that connect
                   // the newly added nodes to the just deleted one
                   treeEdges [node][i] = true;
                   treeEdges [i][node] = true;
               }
           }
       }
   
       // show the result
       drawTree ();
   
       // no memory leak here
       delete [] visited;
   
   
   
   
   
   }
   
   

   Edit the above function so that at the end it prints a message saying how far the farthest visited node was from node 0.

   ---

2. Which of the following statements are true? Assume we are sorting integers.
   • CountingSort cannot be made to work on negative numbers.
   • HeapSort runs in O(n log n) time no matter what the data looks like (except that the data is integers).
   • HeapSort will run in O(n) time if the data is of a special kind.
   • QuickSort will run in O(n) time if the data is of a special kind.
   • MergeSort
   • BucketSort always works (i.e., sorts the numbers) but its speed depends on the data.

   ---

3. In Assignment 5 we use a 2-D bool array ...

   bool * * edges;
   

   with n rows and n columns to remember which edges were present in the graph. Complete the following function:

   void Graph::closure ()
   {
       // This function adds an edge from node i to node j
       // whenever there is an edge from i to k and an
       // edge from k to j, for some node k.  (I.e., if one can get
       // from i to j in two steps, this function puts in a direct
       // connection.)  It keeps doing that until no more edges
       // get added.
   
       int i;
   
   
   
           for (i = 0; i < n; i++)
               for (j = 0; j < n; j++)
   
   
   
   
   
   
   
   
   
   
   
   
   }
   

   ---

4. Consider hashing people's names into a hash table of size 1024.

   Most (all?) of the following proposed hash functions have a serious flaw. Very briefly describe those flaws. (Assume that whatever number i gets computed, the subscript used is i%1024.)

   1. Take the sum (of the ascii code) of the first two letters of the name.

      
           ___________________________________________________
      
      

   2. Take the sum (of the ascii code) of all the letters of the name.

      
           ___________________________________________________
      
      

   3. Take the product (of the ascii code) of all the letters of the name.

      
           ___________________________________________________
      
      

   4. Take the product (of the ascii code) of the first two letters of the name.

      
           ___________________________________________________
      
      

   ---

5. Write a function Polynomial::brackets () that prints a polynomial of the kind used in Assignment 4 as a line of text, fully parenthesized, but with square brackets used for multiplication, parentheses for addition and subtraction, like this:

         [ ( x - 1 ) * ( [ 2 * x ] - 3 ) ]