Exam Answers

Chapter 8

33.(15 points)

37.(20 points)

Chapter 9

1.(10 points)

7.(15 points)

14.(20 points)

45.(20 points)

Chapter 11

23.

41.

46.

48.

49.

1.(10%)

Searching the overflow area of a bucket in a hashed file involves a sequential search. If these records are sorted, the search for a nonexistent record can be terminated once its position has been passed. Otherwise, the search would have to continue until all the records in the overflow area were checked.

2.(10%)

When trying to find a person’s telephone number, a telephone directory resembles a hash file. The person’s name identifies a bucket (all the names beginning with the same letter) and that bucket is searched for the particular entry in question. If, however, one is trying to find the person who is assigned a particular telephone number, the telephone directory resembles a sequential file.

3.(15%)

4.(10%)

Find the dates at which each current position within the company was last filled.

5.(10%)

The sum computed by T1 would be $100 too large because it added the balance of A before the transfer made by T2 to the balance of B after the transfer.

6.(10%)

The merge sort would perform 4 name comparisons when sorting the list Alice, Bob, Carol, and David. The precise number performed when sorting the list Alice, Bob, Carol, David, and Elaine depends on the point at which the odd entry is considered.

7.(15%)

There wold be 2⁴⁰ different combinations so it would require 2⁴⁰/(10⁶) = 1,099,511 seconds.

8.(10%)

1.    WXYZ + Y’(X’Z’ + WZ)

9.(10%)

F (X, Y, Z) = Σm (2, 3, 5, 7)    -> X’Y + XZ