A2 · Practice questions · File organisation, access and hashing

Hash it, then seek.

Six original Cambridge-style questions on file organisation, file access and hashing, with mark points.

Original questions All questions on this page are original work, written in the Cambridge AS & A Level style. They are not from past papers. They test the same concepts and skills the syllabus rewards.

Keep these straight

Organise, then access.

Serial: order of arrival. Sequential: key order. Random: address = hash(key).
Sequential access reads from the start; direct access jumps to the record.
High hit rate, batch: sequential. One record at a time, fast: random.
Collisions: next free address (wrap round) or an overflow area; always check the key you read.

Recall

[2 marks]

Describe the difference between a serial file and a sequential file.

Serial: records are stored in the order in which they are added / arrive (chronological), with no ordering by key. ✓
Sequential: records are stored in order of a key field. ✓

Explain

[3 marks]

Explain how a record is located in a random file, and why this is faster than searching a serial file.

The hashing algorithm is applied to the record's key field to calculate its address. ✓
The program moves (SEEKs) directly to that address and reads the record, checking its key. ✓
Searching a serial file reads records one by one from the start, which on average reads half the file. ✓

Calculate

[4 marks]

A random file has addresses 0 to 49. The hashing algorithm is Key MOD 50 and collisions are stored at the next free address. The keys 1207, 3457, 2058 and 907 are inserted in that order into an empty file. State the address of each record.

1207 MOD 50 = 7: stored at 7. ✓
3457 MOD 50 = 7: collision, stored at 8. ✓
2058 MOD 50 = 8: collision with 3457, stored at 9. ✓
907 MOD 50 = 7: 7, 8 and 9 taken, stored at 10. ✓

Apply

[4 marks]

For each situation, state the most suitable file organisation and justify your choice.

(a) A bank's monthly run that adds interest to every savings account.
(b) A library system that must show the details of one book as soon as its ISBN is scanned.

(a) Sequential (ordered on account number). ✓
Every record is processed in one batch (high hit rate), so reading in key order from start to end is efficient. ✓
(b) Random (hashed on the ISBN). ✓
Each look-up needs one record quickly; the hash gives its address for direct access. ✓

Explain

[3 marks]

Describe two methods of handling a collision when writing a record to a random file.

Next free address: search forward from the home address (wrapping to the start) for the next empty address and store the record there. ✓
Overflow area: store the record in a separate overflow area, searched serially if the record is not at its home address. ✓
Both methods must be followed in the same way when the record is later read (third mark for detail on either). ✓

Write

[6 marks]

Each record in the random file Stock.dat is of type ItemRecord, with an INTEGER field ItemCode. There are addresses 0 to 499, the hash is ItemCode MOD 500, an empty address has ItemCode 0, and collisions use the next free address. Write a function FindItem(Code : INTEGER) RETURNS INTEGER that returns the address of the record with that code, or -1 if it is not in the file.

Declare Address, Count (INTEGER) and Current (ItemRecord); Address ← Code MOD 500 and Count ← 0. ✓
OPENFILE "Stock.dat" FOR RANDOM, then SEEK "Stock.dat", Address and GETRECORD "Stock.dat", Current. ✓
Loop WHILE Current.ItemCode <> Code AND Current.ItemCode <> 0 AND Count < 500. ✓
In the loop: Address ← (Address + 1) MOD 500, SEEK, GETRECORD and Count ← Count + 1. ✓
After the loop: CLOSEFILE "Stock.dat". ✓
IF Current.ItemCode = Code THEN RETURN Address ELSE RETURN -1 (ENDIF, ENDFUNCTION). ✓

Mark this once you have attempted all six and checked your working. It records a Practiced badge on the topic and adds a one-time bonus. Revealing the solutions alone does not count.