IT 403 : FUNDAMENTALS OF INFORMATION PROCESSING, Autumn 2006

SAMPLE QUESTIONS

UNIT I

1. What are the desired qualities of a hash function?
2. What is an overflow in hash file organization and it can be handled?
3. What are disadvantages of static hashing file organization. Describe the general structure of a extendible hashing.
4. Explain how queries and updates are handled in extendible hashing.
5. Suppose that we are using extendible hashing on a file that contains records with the following search-key values:
   

   2, 3, 5, 7, 11, 17, 19, 23, 29, 31.

   Show the extendible hash structure for this file if the hash function is h(x) = x mod 8 and buckets can hold three records. Also show how the extendible hash structure changes as the result of each of the following steps:

   • Delete 11
   • Delete 31
   • Insert 1
   • Insert 15
6. Distinguish between primary index and secondary index. What is an index sequential file?
7. What is the difference between dense index and sparse index? What are factors used to evaluate an indexing texhnique?
8. Is it possible in general to have two clustering indices on the same file for different search keys? Explain your answer.
9. Since indices speed query processing, is it advisable to keep several indeces on several search keys? Explain.
10. Construct a B+ tree for the following set of key values:

    2, 3, 5, 7, 11, 17, 19, 23, 29, 31.

    Assume that the tree is initially empty and values are added in ascending order. Construct B+ trees for cases where the number of pointers that will fit in one node is as follows:
    • Four
    • Six
11. For each B+ tree of the above exercise, show the form of the tree after each of the following series of operations:
    • Insert 9
    • Insert 8
    • Delete 23