Department of Computer Science and Engineering CSE 102
University of California at San Diego Winter 1997

More Practice Questions

1. Insert the following rocords into a linear hashing structure having and with .

   

   Assume there are two chains at the start so N is two. Use the hash functions .

2. Show the average chain length in linear hashing is a linear (increasing) function of .

3. What is the purpose of the the N in the hash functions presented in the first exercise? In other words, why not always use the sequence of hash functions ?

4. Suppose our key space consists of integer values in the range 0 through . We are storing records according using an index structure implemented via linear hashing. Currently, the state variable next is 5 and level is 3. How many buckets exist? Which keys map to bucket 3 and which map to bucket 6?

5. Consider the key space of the previous problem; we store records using an index structure implemented via interpolation-based index maintenance. The state variable next is 5 and level is 3. How many buckets exist? Which keys map to bucket 3 and which map to bucket 6?

6. Insert the following records into an interpolation based index maintenance structure having and with .

   

   The key space has lowest value 0 and highest value 50. What functions do you use?

7. What sequence of order 3 B+trees results if you insert the following keys into an empty tree?

   cat, pig, fox, elk, sow, yak, ant, hen, cow, dog, bee, jay, emu, gnu

8. Assume you know all the records that are to be inserted into a B+tree dictionary index; this is the off-line insertion problem. Describe a means to build a B+tree which results in a tree of least height.

9. A disk drive has seek latency of 15ms and rotational latency of 8ms. Its (external) transfer rate is 10MB/s; what are the times to access 1000 bytes and 60KB?

10. A disk drive spins at 5600rpm, and has tracks with 60KB of user data. If a cylinder contains 5 platters, what is the maximum (internal) transfer rate the drive can sustain?

• About this document ...