Sample final exam questions

There is a version of this page that includes solutions.

Open textbook (but no other books), open notes. No use of computers. There are 12 problems, each worth 20 points. Do only ten problems, cross out two. The first ten that are not crossed out count.

If in doing a programming problem you need some supporting functions that are as simple as, for example, the maximum of two integers, just assume you have such functions.

Which was your recitation?

R012   M   1000AM-1115AM     ECCH 105     Cyrus
R013   M   0100PM-0215PM     ECCH 105     Damon
R014   M   0300PM-0415PM     ECCH 105     Cyrus
R015   M   0500PM-0615PM     ECCH 105     Trevor
R016   T   0930AM-1045AM     ECCH 105     Alan
R017   T   1100AM-1215PM     ECCH 105     Alan

What does this search tree look like after a left rotation at the root?
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.
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.
Show it after another element has been removed and it has been made into a heap again.
Show it after one more element has been removed and it has been made into a heap again.
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
```

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.
```
     ___________________________________________________
```
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.
```
     ___________________________________________________
```
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 '-':










        case '*':







    }
}
```
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.
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.
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?
What if you had to sort by subject?
True or false?
1. Hashing is a good way of sorting.
2. Priority queues are useful for merging sorted files.
3. CountingSort does not work well for sorting integers.
Randomization is important to assure good performance of the following:
1. QuickSort
2. HeapSort
3. SelectionSort
4. BubbleSort
5. Hashtables
6. Priority queues
About counting sort ...
1. CountingSort never compares two of the values that are to be sorted.
2. CountingSort works well for sorting a million integers.
3. CountingSort works well for strings.
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.
2. Computing the depth of a tree.
3. Inserting a new entry into a binary search tree when the addition is done by adding a leaf.
4. Inserting a new entry into a binary search tree when the addition is done “at the root.”
5. Inserting a new entry into a randomized binary search tree.

9:07 PM, Friday, December 13, 2002