Sample final exam questions with solutions

  1. What does this search tree look like after a left rotation at the root?
    Transparency 91

  2. Assume you are dealing with trees where nodes can have up to three children: left, middle, and right. (These are called “ternary” trees.) Write a function that returns the size (=number of nodes) of such a tree.


    Answer: [An earlier version had the “1 + ” missing.] 

    int size (Node* root)
{
    if (root == NULL)
        return 0;

    return 1 + size (root->left) + size (root->middle) + size (root->right);
}

  3. This array is organized as a heap (a priority queue). 
      10  8  6  2  1  4  5
    Show it after its top element has been removed and it has been made into a heap again. 
      8  5  6  2  1  4

    Show it after another element has been removed and it has been made into a heap again. 

      6  5  4  2  1

    Show it after one more element has been removed and it has been made into a heap again. 

      5  2  4  1

  4. Assume we want to do look-ups by phone number to find a person's name that goes with a given phone number. Assume we are using open hashing with an array of size 1024 and we are using the last three digits of the phone number as our hash function.

    Starting with an empty hash table, show the picture around subscript 380 after each of the following operations: 

        insert 492 4380   Joe
    insert 443 6380   Mary
    insert 544 5380   Sue
    delete 443 6380   Mary
    Answer: 
               |                 |
           |-----------------|
      380: | 492 4380   Joe  |
           |-----------------|
      381: |                 |
           |-----------------|
      382: |                 |
           |-----------------|
      383: |                 |
           |-----------------|

               |                 |
           |-----------------|
      380: | 492 4380   Joe  |
           |-----------------|
      381: | 443 6380   Mary |
           |-----------------|
      382: |                 |
           |-----------------|
      383: |                 |
           |-----------------|

               |                 |
           |-----------------|
      380: | 492 4380   Joe  |
           |-----------------|
      381: | 443 6380   Mary |
           |-----------------|
      382: | 544 5380   Sue  |
           |-----------------|
      383: |                 |
           |-----------------|

               |                 |
           |-----------------|
      380: | 492 4380   Joe  |
           |-----------------|
      381: | XXXXXXXXXXXXXXX |
           |-----------------|
      382: | 544 5380   Sue  |
           |-----------------|
      383: |                 |
           |-----------------|

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

    Each of the following proposed hash functions has a serious flaw. Very briefly describe the flaw.

    1. Take the sum (of the ascii code) of the first two letters of the name. 
           Only a small part of the table ever gets used.
    2. Take the sum (of the ascii code) of all the letters of the name. 
           Still not a good use of the table but worse than that,
     some subscripts will be outside the table.
    3. Take the product (of the ascii code) of all the letters of the name. 
           Same problem as previous, aggravated.
    4. Take the product (of the ascii code) of the first two letters of the name. 
           Very poor usage of the table when the subscripts 
     are within range, and, worse, many subscripts are
     outside the table.

  6. Consider expressions like the ones in Assignment 4 but without division. 
    bool Expression::linear ()
{
    if (constant ())
        return true;

    if (op == 'x')
        return true;

    switch (op) {
        case '+':
        case '-':
            return left->linear () && right->linear ();
        case '*':
            return 
                (left->linear () && right->constant ())
                 ||
                (left->constant () && right->linear ());
    }
}
    Complete the above function. It is supposed to find out if the expression is constant or linear in x. Assume that a suitable function constant has been written.

  7. Write a function that finds out if a tree passes the following test for being balanced: for every subtree, the sizes of its left and right subtrees differ by at most one. 
    
// assuming trees are pointers to tree nodes ...

bool balanced (TreeNode* t)
{
    if (t == NULL)
        return true;

    return
        abs (size (t->left) - size (t->right) <= 1
         &&
        balanced (t->left)
         &&
        balanced (t->right);
}

  8. Assume the task is to sort by date 1,000,000 email messages that have been received in a steady stream over the course of one year. What sorting method(s) are likely to perform best for this task? 
    Bucket sort with a bucket for each
time unit (e.g., minute).

    What if you had to sort by subject? 

    Probably nothing much one can do other than
use a general-purpose (i.e., comparison-based) 
sort such as quicksort.

  9. True or false?

    1. Hashing is a good way of sorting. False.
    2. Priority queues are useful for merging sorted files. True.
    3. CountingSort does not work well for sorting integers. CountingSort, if done by two columns of two bytes each on four-btye integers, works well (and should then properly be called RadixSort). CountingSort done in one pass on the whole width of four-byte integers does not work well because it would need a counting array of excessive size.

  10. Randomization is important to assure good performance of the following:

    1. QuickSort Yes.
    2. HeapSort No.
    3. SelectionSort No.
    4. BubbleSort No.
    5. Hashtables No.
    6. Priority queues No.

  11. About counting sort ...

    1. CountingSort never compares two of the values that are to be sorted. True (at least if the range of values is known beforehand; otherwise there may need to be some comparisons to find the smallest and largest values).
    2. CountingSort works well for sorting a million integers. True if understood to sort column by column, see above.
    3. CountingSort works well for strings. False.

  12. Which of the following algorithms on trees can be carried out by doing work only along one path from the root to a leaf?

    1. Computing the size of a tree. No.
    2. Computing the depth of a tree. No.
    3. Inserting a new entry into a binary search tree when the addition is done by adding a leaf. Yes.
    4. Inserting a new entry into a binary search tree when the addition is done “at the root.” Yes.
    5. Inserting a new entry into a randomized binary search tree. Yes.

Back to top

© 2002 Karl Winklmann

9:07 PM, Friday, December 13, 2002