December 1999
SW204 : SOFTWARE AND
FILE DESIGN

QUESTION 4

Total Marks: 15 Marks

• Question 1
• Question 2
• Question 3
• Question 5
• Cover Page

SUGGESTED SOLUTIONS
Solutions and allocated marks are indicated in green.
Return to Question 4

What are the two objectives of randomising algorithms?
To produce an address for every possible key (1 mark)and to produce an even spread of key addresses (1 mark).

(i)Describe,using an example,how self-addressing works.[2marks ]
Self-addressing works by making a record ’s address equal to its key value (1 mark).A further mark should be awarded for a suitable example.

(ii)List two benefits associated with self-addressing.[2marks ]
One mark should be awarded for each benefit named (up to a maximum of two marks).Examples include the following:

•Self-addressing leads directly to the desired record.
•No index is required. [2marks ]

Describe,using examples,how each of the following indirect addressing techniques work:

(i)Prime number division.[2marks ]
The key is divided by the largest prime number within the number of available blocks;the remainder from the division is the relative block number (1 mark).A further mark should be awarded for a suitable example.

(ii)Mid-square.[2marks ]
The key is squared and the address is obtained by truncating digits at both ends until the desired length is obtained.A further mark should be awarded for a suitable example.

(iii)Folding.[2marks ]
The key is split into two or more parts and the parts are then added together.A further mark should be awarded for a suitable example.

(i)What can synonyms in the context of addressing?[1 mark ]
A synonym occurs when two or more records are transformed to the same address by a hashing algorithm.

(ii)Name two ways in which synonyms can be handled.[2marks ]
One mark should be awarded for each technique named (up to a maximum of two marks).Examples include the following:

•Progressive overflow.
•Chained records.
•Tagged records.