CPSC 461 Spring 2000 Final

QUESTION 1 (worth 25 marks in total)

a. [2 marks--bonus]  What was the topic or contents of the longest text file used as test data
                     in the Data Compression Assignment?

b. [2 marks] Why are there multiple copies of the SuperBlock in a Unix Partition?

c. [2 marks] How many copies of the Superblock are there in a Unix Partition?

d. [3 marks] What is it about Scientific file Formats (and the data they represent) that sets them
             apart from multimedia formats?

e. [3 marks] How are sampling rate and frequency related to each other in audio data (with respect
             to minimum values)?

f. [4 marks] What are two essential qualities of a hashing function?

g. [4 marks] Name 4 elements that are essential to the header of any (and all) Graphics File Format
             file(s)?

h. [5 marks] How does vioce data differ from music data (at least 2 differences in the nature of the
             data) Briefly explain how that affects the way the data is stored.

QUESTION 2 (worth 20 marks in total)

Suppose we wanted to implement a B-Tree of order 4 using an array such taht each node of the B-Tree
corresponds to one element of the array.  In order to do so we must make room in the array for all 
possible nodes right at the start.
a.  How is this tree traversed? (given a parent LIST[j], how do we calculate the location of each of
    it's children, and given a child, how do we calculate the location of the parent?)
b.  If we decide we need to increase the depth of the tree, how can we accomplish this?  (re-copying
    the existing tree is not an option)
c.  What aspects of this array approach are useful?
d.  Discuss this approach with respect to achieving efficient disk accesses.

QUESTION 3 (worth 20 marks in total)

Using the following simple hashing and incrementing funciton, insert the given list of keys into the
table using BINARY TREE INSERTION for collision resolution.  Re-draw the table as necessary to keep
moved keys visible, show calculations and explain movement of keys.  Draw the decision tree for each
instance where the placement of the incoming key involves the movement of one or more other keys.

Record Keys:  14, 51, 37, 18, 16, 25, 36, 17, 11, 27
Table Size=11
Hash Function= hash(key)=key mod 11
Incrementing Function=i(key)= (key/11) mod 11

QUESTION 4 (worth 20 marks in total)

Given N sorted lists, write a program (or pseudo-code) to merge them using a tournamenet tree. The
records are 100 bytes long, and the key is in the first field ( it is a long int).  Your algorithm
must be clean, clear and as efficient as possible.