13.2 File Organisation & Access
A Level · 23 questions found
What this topic covers
Section titled “What this topic covers”- File organisation methods: serial, sequential (key field), random (record key)
- Sequential access for serial/sequential files; direct access for sequential/random files
- Hashing algorithms: describe, use to read/write data to a random/sequential file
Past paper questions
Section titled “Past paper questions”A program stores records in the 2D array HashTable . Each record is stored at a specific index of
the array that is calculated using a hashing algorithm with the record’s key field.
The array has 100 × 10 elements. The hashing algorithm uses the key to generate an index between 0 and 99 (inclusive). If two key fields generate the same index, there is a collision. Any records that have a collision are stored in the next space in the same index.
For example: In this table two record keys generated the same hash value of 1. Four record keys generated the same hash value of 3.
| Index | 0 | 1 | 2 | 3 | 4 | 5 | … | 9 |
|---|---|---|---|---|---|---|---|---|
| 0 | record | |||||||
| 1 | record | record | ||||||
| 2 | ||||||||
| 3 | record | record | record | record | ||||
| 4 | ||||||||
| … | ||||||||
| 99 |
The program uses Object-Oriented Programming (OOP).
| (a) The class Record stores data about the records: | |
|---|---|
Record |
Record |
Key : IntegerData : String |
stores the integer key field for the data stores the string data |
Constructor() |
initialisesKey andData to its parameter values |
The attributes Key and Data are public.
Write program code to declare the class Record and its constructor.
Use your programming language appropriate constructor.
Save your program as Question3_N25 .
Copy and paste the program code into part 3(a) in the evidence document. 2 marks
(b) The procedure InitialiseHashTable() initialises each element in the array to an empty or null record. 2 marks
Write program code to declare the global 2D array HashTable and the procedure
InitialiseHashTable()
Save your program.
Copy and paste the program code into part 3(b) in the evidence document.
(c) The function Hash() : 2 marks
takes an integer key field as a parameter
calculates and returns the hash value of the key field.
The hash value is the result from the formula: key MOD 100
Write program code for Hash()
Save your program.
Copy and paste the program code into part 3(c) in the evidence document.
(d) The procedure InsertData() : 4 marks
takes an object of type
Recordas a parametercalculates the hash value for the parameter using the appropriate function
stores the parameter in the correct position in
HashTable
You can assume there will be no more than 10 objects that generate the same hash value.
Write program code for InsertData()
Save your program.
Copy and paste the program code into part 3(d) in the evidence document.
(e) The file "HashTableData.txt" stores 200 key values and string data items in the format: 5 marks
key,string
For example, the first row in the text file is:
528,permission
The key is 528 and the string data is "permission"
The procedure ReadData() :
opens the text file and reads each line
splits each line into the key and data
calls
InsertData()with an object containing each key and matching data.
Write program code for ReadData()
Save your program.
Copy and paste the program code into part 3(e) in the evidence document.
(f) The function GetRecord() : 5 marks
takes an integer key field as a parameter
calculates the hash value for the key field using the appropriate function
searches the hash table for the record with the matching key field
returns the data for the record if the record is found
returns
"Not found"if the record is not found.
Write program code for GetRecord()
Save your program.
Copy and paste the program code into part 3(f) in the evidence document.
(g) The main program:
calls
InitialiseHashTable()andReadData()takes five integer key fields as input from the user
calls
GetRecord()with each input and outputs the return value.
(i) Write program code for the main program. 3 marks
Save your program.
Copy and paste the program code into part 3(g)(i) in the evidence document.
(ii) Test your program with the following five inputs in the order given: 2 marks
528
1128
1828
1062
Take a screenshot of the output(s).
Save your program.
Copy and paste the screenshot(s) into part 3(g)(ii) in the evidence document.
Show mark scheme
3(a) [2 marks]
1 mark each • Class header (and end) and constructor header (and end) in class • Constructor takes two parameters and stores each in attributes Example program code Java class Record{ public Integer Key; public String Data; public Record(Integer pKey, String pData){ Key = pKey; Data = pData; } } VB.NET Class Record Dim Key As Integer Dim Data As String Sub New(pKey, pData) Key = pKey Data = pData End Sub End Class Python class Record: def init(self, pKey, pData): self.Key = pKey #integer self.Data = pData #string
3(b) [2 marks]
1 mark each • 2D array of 100 10 elements of type Record • Procedure header (and end) and initialises each element in the 2D array to an empty/null InitialiseHashTable() record in procedure Example program code Java public static Record[][] HashTable = new Record[100][10]; public static void InitialiseHashTable(){ Record EmptyRecord = new Record(-1,"-1"); for(Integer X = 0; X < 100; X++){ for(Integer Y = 0; Y < 10; Y++){ HashTable[X][Y] = EmptyRecord; } } } VB.NET Dim HashTable(99, 9) As Record Sub InitialiseHashTable() Dim EmptyRecord As Record = New Record(-1, "") For X = 0 To 99 For Y = 0 To 9 HashTable(X, Y) = EmptyRecord Next Next End Sub Python HashTable = [] def InitialiseHashTable(): global HashTable HashTable = [[Record(-1,"")]*10 for i in range(100)]
3(c) [2 marks]
1 mark each • Function header (and end) taking one parameter and returning calculated hash • …. hash calculated correctly from parameter Example program code Java public static Integer Hash(Integer TheKey){ return(TheKey % 100); } VB.NET Function Hash(Key) Return Key Mod 100 End Function Python def Hash(Key): return Key % 100
3(d)
Python def InsertData(RecordData): global HashTable HashValue = Hash(RecordData.Key) for X in range(0, 10): if HashTable[HashValue][X].Key == -1: HashTable[HashValue][X] = RecordData
3(e)
VB.NET Sub ReadData() Dim Line As String Dim Data(3) As String Dim TheRecord As Record Dim FileReader As New System.IO.StreamReader("HashTableData.txt") While Not FileReader.EndOfStream Line = FileReader.ReadLine() Data = Split(Line, ",") TheRecord = New Record(Integer.Parse(Data(0)), Data(1)) InsertData(TheRecord) End While FileReader.Close() End Sub Python def ReadData(): global HashTable File = open("HashTableData.txt") for Line in File: Data = Line.strip() Data = Line.split(",") InsertData(Record(int(Data[0]), Data[1])) File.close()
3(f)
Python def GetRecord(Key): global HashTable HashValue = Hash(Key) for X in range(0, 10): if HashTable[HashValue][X].Key == Key: return HashTable[HashValue][X].Data return "Not found"
3(g)(i)
Python InitialiseHashTable() ReadData() for x in range(5): Key = int(input("Enter key field ")) print(GetRecord(Key))
3(g)(ii) [2 marks]
1 mark each for screenshot(s) showing • Input of the 4 integers and matching word output 528 permission 1128 peace 1828 precedent 1062 up • Input of and output of 39 Not found e.g.
The pseudocode algorithm checks whether a location in a stock file StockList.dat is empty or not. The location is given by the user. If the location is empty, a suitable message is displayed, otherwise the item stored at that location is displayed.
Complete this file-handling pseudocode algorithm.
DECLARE Location : INTEGER DECLARE Item : STRING DECLARE Continue : BOOLEAN DECLARE Answer : CHAR Continue TRUE
OPENFILE WHILE Continue OUTPUT "Enter a location between 1 and 500: " INPUT Location
GETRECORD IF Item = "" THEN OUTPUT "This record is missing." ELSE OUTPUT "The item in stock is ", ENDIF OUTPUT "Another location (Y or N)?" INPUT Answer IF Answer <> 'Y' THEN Continue FALSE ENDIF ENDWHILE
OUTPUT "End of program" 5 marks
Show mark scheme
12 [5 marks]
One mark for each correctly completed line ( Max 5 ) DECLARE Location : INTEGER DECLARE Item : STRING DECLARE Continue : BOOLEAN DECLARE Answer : CHAR Continue TRUE OPENFILE "StockList.dat" FOR RANDOM WHILE Continue OUTPUT "Enter a location between 1 and 500: " INPUT Location SEEK "StockList.dat", Location GETRECORD "StockList.dat", Item IF Item = "" THEN OUTPUT "This record is missing" ELSE OUTPUT "The item in stock is ", Item ENDIF OUTPUT "Another location (Y or N)?" INPUT Answer IF Answer <> 'Y' THEN Continue FALSE ENDIF ENDWHILE CLOSEFILE "StockList.dat" OUTPUT "End of program"
The pseudocode algorithm below uses random file access to copy 50 records from a live file CurrentResults.dat to a stored file StoredResults.dat one record at a time. It uses the user-defined type StudentResult.
TYPE StudentResult DECLARE LastName : STRING DECLARE FirstName : STRING DECLARE ExamGrade : STRING ENDTYPE
If any grades are missing in CurrentResults.dat, the text "Missing grade" is added to the ExamGrade field in StoredResults.dat
Complete this file handling pseudocode algorithm.
DECLARE Grade : StudentResult DECLARE Position : INTEGER
OPENFILE "StoredResults.dat" FOR RANDOM
SEEK "CurrentResults.dat", Position GETRECORD "CurrentResults.dat", Grade IF Grade.ExamGrade = "" THEN
ENDIF
NEXT Position CLOSEFILE "CurrentResults.dat" CLOSEFILE "StoredResults.dat" 5 marks
Show mark scheme
13 [5 marks]
One mark for each correctly completed line DECLARE Grade : StudentResult DECLARE Position : INTEGER OPENFILE "CurrentResults.dat" FOR RANDOM OPENFILE "StoredResults.dat" FOR RANDOM FOR Position 1 TO 50 SEEK "CurrentResults.dat", Position GETRECORD "CurrentResults.dat", Grade IF Grade.ExamGrade = "" THEN Grade.ExamGrade "Missing grade" ENDIF SEEK "StoredResults.dat", Position PUTRECORD "StoredResults.dat", Grade NEXT Position CLOSEFILE "CurrentResults.dat" CLOSEFILE "StoredResults.dat"
The pseudocode algorithm below allows a user to input a new stock item. The random file is searched for the next empty location in the file and the new item is inserted there. A suitable message is displayed if the file is full.
Complete this pseudocode.
DECLARE Location : INTEGER DECLARE NewStock : STRING DECLARE CurrentStock : STRING DECLARE Stored : BOOLEAN DECLARE Max : INTEGER Max ← 100000 Stored ← FALSE Location ← 1
OUTPUT "Enter the new item you wish to store: " INPUT NewStock WHILE NOT Stored AND Location <= Max
GETRECORD "StockList.dat", IF CurrentStock = "" THEN
______ "StockList.dat", NewStock Stored ← TRUE ELSE Location ← Location + 1 ENDIF ENDWHILE
______ THEN OUTPUT "The new item has not been stored as the file was full." ENDIF CLOSEFILE "StockList.dat" 5 marks
Show mark scheme
11 [5 marks]
One mark for each correctly completed line DECLARE Location : INTEGER DECLARE NewStock : STRING DECLARE CurrentStock : STRING DECLARE Stored : BOOLEAN DECLARE Max : INTEGER Max 100000 Stored FALSE Location 1 OPENFILE "StockList.dat" FOR RANDOM OUTPUT "Enter the new item you wish to store" INPUT NewStock WHILE NOT Stored AND Location <= Max SEEK "StockList.dat", Location GETRECORD "StockList.dat", CurrentStock IF CurrentStock = "" THEN PUTRECORD "StockList.dat", NewStock Stored TRUE ELSE Location Location + 1 ENDIF ENDWHILE IF Stored = FALSE THEN OUTPUT "The new stock item has not been stored as the file was full" ENDIF CLOSEFILE "StockList.dat"
A program stores data in a 1D array of records, HashTable . The array has space for 200 records.
Each data item is stored in a specific index of the array that is calculated using an algorithm. The
index is calculated from the key field using the formula: Key MOD 200
If two key fields generate the same index, there is a collision. Any records that have a collision
are stored in a second array, Spare . This array has space for 100 records. When a collision is
detected, the record is stored in the next free space in Spare .
(a) The pseudocode record format is: 2 marks
TYPE NewRecord
DECLARE Key : INTEGER
DECLARE Item1 : INTEGER
DECLARE Item2 : INTEGER
ENDTYPE
Write program code to declare the record type NewRecord
If your chosen programming language does not support record formats, a class can be used instead.
Save your program as Question2_J25 .
Copy and paste the program code into part 2(a) in the evidence document.
(b) (i) Write program code to declare the global arrays HashTable and Spare 1 mark
Save your program.
Copy and paste the program code into part 2(b)(i) in the evidence document.
(ii) An empty record has the integer –1 stored in each field. 2 marks
The procedure Initialise() stores an empty record in each element in HashTable
and Spare
Write program code for Initialise()
Save your program.
Copy and paste the program code into part 2(b)(ii) in the evidence document.
(c) The hash value is calculated from the key field using the formula: Key MOD 200 The function CalculateHash() takes a key field as a parameter and calculates and returns the hash value for the key field. 2 marks
Write program code for CalculateHash()
Save your program.
Copy and paste the program code into part 2(c) in the evidence document.
(d) The procedure InsertIntoHash() : 6 marks
takes a record of type
NewRecordas a parameteruses
CalculateHash()to calculate the hash value for the key field in the recordchecks if the hash value index in
HashTablecurrently stores an empty recordif the index stores an empty record, store the parameter in this index
if the index does not store an empty record, store the parameter in
Spare
You can assume there will always be enough space in Spare to store any collisions.
Write program code for InsertIntoHash()
Save your program.
Copy and paste the program code into part 2(d) in the evidence document.
(e) The text file HashData.txt stores up to 200 rows of data to be stored into the hash table. 5 marks
Each row contains three integer numbers separated by commas.
The first number is the key field, the second number is item 1 and the third number is item 2.
For example:
The first row in the text file contains: 646, 12, 568
The key field is 646, item 1 is 12 and item 2 is 568
The procedure CreateHashTable() :
opens the file
HashData.txtcreates a record for each row of data in the file
calls
InsertIntoHash()with each record.
Write program code for CreateHashTable()
Save your program.
Copy and paste the program code into part 2(e) in the evidence document.
(f) (i) The procedure PrintSpare() outputs the key field of each element in the array Spare that does not contain an empty record. 2 marks
Write program code for PrintSpare()
Save your program.
Copy and paste the program code into part 2(f)(i) in the evidence document.
(ii) The main program should call the procedure to initialise the arrays, call the procedure to create the hash table and then call the procedure to output the contents of the array 1 mark
Spare
Write program code for the main program.
Save your program.
Copy and paste the program code into part 2(f)(ii) in the evidence document.
(iii) Test your program. 1 mark
Take a screenshot of the output(s).
Save your program.
Copy and paste the screenshot into part 2(f)(iii) in the evidence document.
Show mark scheme
2(a) [2 marks]
1 mark each • Record/class declared NewRecord • 3 variables within structure (all integer) private Integer Key; private Integer Item1; private Integer Item2; public NewRecord(Integer pKey, Integer pItem1, Integer pItem2){ Key = pKey; Item1 = pItem1; Item2 = pItem2; } public Integer GetKey(){ return Key; } public Integer GetItem1(){ return Item1; } public Integer GetItem2(){ return Item2; }}
2(b)(i) [1 mark]
1 mark for • (200 records) and (100 records) declared as (global) arrays HashTable Spare
2(b)(ii) [2 marks]
1 mark each • Procedure header (and close where appropriate) that initialises all elements in both arrays … Initialise() • … to an empty record with –1 in each of the 3 fields/elements NewRecord EmptyRecord = new NewRecord(-1,-1,-1); for(Integer X = 0; X < 200; X++){ HashTable[X] = EmptyRecord; } for(Integer X = 0; X < 100; X++){ Spare[X] = EmptyRecord; }
2(c) [2 marks]
1 mark each • Function header (and close where appropriate), taking one (integer) parameter • Calculation of parameter MOD 200 return(TheKey % 200);
2(d) [6 marks]
1 mark each: • Procedure header (and end where appropriate) taking one record as a parameter • Calling with key from parameter record and storing/using return value CalculateHash() • Checking if at return value from is empty HashTable CalculateHash • … if it is empty, store parameter in location • … otherwise, locating next free space in … Spare • … and storing in that index only (i.e. not in all other free spaces)
Integer HashValue = CalculateHash(TheRecord.GetKey()); if(HashTable[HashValue].GetKey().equals(-1)){ HashTable[HashValue] = TheRecord; }else{ for(Integer X = 0; X < 99; X++){ if(Spare[X].GetKey().equals(-1)){ Spare[X] = TheRecord; X = 99; } } }
2(e) [5 marks]
1 mark each to max 5 • Procedure header (and end where appropriate), opening and closing file • Reading in all lines of data … • … splitting each line by commas • Creating record with correct values with each line read in from file • Calling with each record they have created InsertIntoHash() • Exception handling for opening and reading from file with appropriate catch and output. String[] Data = new String[3]; Integer NewKey; Integer NewItem1; Integer NewItem2; try{ FileReader File = new FileReader("HashData.txt"); try{ BufferedReader Reader = new BufferedReader(File); String Line= Reader.readLine(); while (Line != null){ Line = Line.replace("\n",""); Data = Line.split(","); NewKey = Integer.parseInt(Data[0]); NewItem1 = Integer.parseInt(Data[1]); NewItem2 = Integer.parseInt(Data[2]); NewRecord ReadData = new NewRecord(NewKey, NewItem1, NewItem2); InsertIntoHash(ReadData); Line= Reader.readLine(); } Reader.close(); }catch(IOException ex){} }catch(FileNotFoundException e){System.out.println("File not found");}
2(f)(i) [2 marks]
1 mark each • Procedure header (and end where appropriate) and looping through each element in • … checking if record is empty and outputting key field if not empty Integer X = 0; while(Spare[X].GetKey() != -1){ System.out.println(Spare[X].GetKey()); X++; }
2(f)(ii) [1 mark]
1 mark for calling then then Initialise() CreateHashTable() PrintSpare()
2(f)(iii) [1 mark]
1 mark for output
(a) Explain what is meant by a hashing algorithm in the context of file access. 3 marks
(b) The use of a hashing algorithm can result in the same storage location being identified for more than one record. 2 marks
Outline two methods of overcoming this issue.
1
2
Show mark scheme
5(a) [3 marks]
One mark per mark point ( Max 3 ) MP1 A hashing algorithm is used in direct access methods on random and sequential files MP2 It is a mathematical formula MP3 … used to perform a calculation applied to the key field of the record being searched / stored MP4 The result of the calculation gives the address where the record should be found / stored.
5(b) [2 marks]
One mark per mark point ( Max 2 ) MP1 The record is stored in the next free memory space after the one identified by the hashing algorithm // Use linear progression MP2 An overflow area is set up and the record is stored in the next free memory space in the overflow area.
(a) Describe serial file organisation as a method of storing data records in a file. 2 marks
(b) State one example of a use for serial file organisation. 1 mark
Show mark scheme
2(a) [2 marks]
One mark per mark point ( Max 2 ) MP1 Records are stored one after the other as they are collected // records are stored in chronological order MP2 New records are appended to the end of the file.
2(b) [1 mark]
One mark for a use ( Max 1 ) MP1 Creating unsorted / temporary transaction files MP2 Creating data logging files
(a) Explain what is meant by a hashing algorithm in the context of file access. 3 marks
(b) The use of a hashing algorithm can result in the same storage location being identified for more than one record. 2 marks
Outline two methods of overcoming this issue.
1
2
Show mark scheme
5(a) [3 marks]
One mark per mark point ( Max 3 ) MP1 A hashing algorithm is used in direct access methods on random and sequential files MP2 It is a mathematical formula MP3 … used to perform a calculation applied to the key field of the record being searched / stored MP4 The result of the calculation gives the address where the record should be found / stored.
5(b) [2 marks]
One mark per mark point ( Max 2 ) MP1 The record is stored in the next free memory space after the one identified by the hashing algorithm // Use linear progression MP2 An overflow area is set up and the record is stored in the next free memory space in the overflow area.
(a) Describe the sequential method of file access . 2 marks
(b) Explain how the sequential method of file access is applied to files with serial organisation and to files with sequential organisation. 3 marks
Show mark scheme
4(a) [2 marks]
mark per mark point ( Max 2 ) Sequential access method searches for records one after the other … from the physical start of the file until the record is found/the end of file.
4(b) [3 marks]
mark per mark point ( Max 3 ) For serial files, records are stored in chronological order … every record needs to be checked until the record is found, or all records have been checked. For sequential files, records are stored in order of a key field/index, and it is the key field/index that is compared. … every record is checked until the record is found, or the key field of the current record is greater than the key field of the target record.
(a) Outline what is meant by direct access as a method of file access. 2 marks
(b) Explain how direct access is used to locate a specific record in sequential files and random files.
(i) Sequential files 2 marks
(ii) Random files 2 marks
Show mark scheme
7(a) [2 marks]
mark per mark point ( Max 2 ) Direct access allows a record to be found in a file without other records being read. Records are found by using the key field of the target record // the location of the record is found using a hashing algorithm .
7(b)(i) [2 marks]
mark per mark point ( Max 2 ) In sequential files, an index of all key fields is kept The index is searched for the address of the file location where the target record is stored.
7(b)(ii) [2 marks]
mark per mark point ( Max 2 ) A hashing algorithm is used on the key field of the record … to calculate the address of the memory location where the target record is expected to be stored. Method to find a record if it is not at the expected location e.g. linear probing, search overflow area etc.
(a) Describe the sequential method of file access . 2 marks
(b) Explain how the sequential method of file access is applied to files with serial organisation and to files with sequential organisation. 3 marks
Show mark scheme
4(a) [2 marks]
mark per mark point ( Max 2 ) Sequential access method searches for records one after the other … from the physical start of the file until the record is found/the end of file.
4(b) [3 marks]
mark per mark point ( Max 3 ) For serial files, records are stored in chronological order … every record needs to be checked until the record is found, or all records have been checked. For sequential files, records are stored in order of a key field/index, and it is the key field/index that is compared. … every record is checked until the record is found, or the key field of the current record is greater than the key field of the target record.
(a) Describe sequential and random methods of file organisation. 4 marks
Sequential file organisation
Random file organisation
(b) Outline the process of sequential access for serial and sequential files. 2 marks
Show mark scheme
4(a) [4 marks]
One mark per mark point – sequential ( Max 2 ) MP1 Records (in the file) are ordered MP2 … based on the key field MP3 A new version (of the file) has to be created to update the file One mark per mark point – random ( Max 2 ) MP4 Records are stored in no particular order within the file // There is no sequencing in the placement of the records MP5 There is a relationship between the key of the record and its location within the file // a hashing algorithm is used to find the location of the record MP6 Updates to the file can be carried out directly.
4(b) [2 marks]
One mark per mark point ( Max 2 ) MP1 Start at the beginning of the file MP2 …check records linearly MP3 …until the desired record is found // … processing / updating records as required //… EOF found.
(a) A pseudocode algorithm finds a customer account record in a random file and outputs it. The records are stored using the user-defined data type TAccount . 5 marks
TYPE TAccount
DECLARE AccountNumber : INTEGER
DECLARE LastName : STRING
DECLARE FirstName : STRING
DECLARE Address : STRING
DECLARE ContactNumber : STRING
ENDTYPE
Complete the file handling pseudocode.
The function Hash() takes the customer account number as a parameter, calculates and
returns the hash value.
DECLARE Customer : TAccount
DECLARE Location : INTEGER
DECLARE AccountFile : STRING
______ "AccountRecords.dat"
______ AccountFile
OUTPUT "Please enter an account number"
INPUT Customer.AccountNumber
Location Hash( ______)
SEEK ______, Location
______ AccountFile,
OUTPUT Customer // output customer record
CLOSEFILE AccountFile
(b) Define the term exception handling . 1 mark
(c) State two possible causes of an exception. 2 marks
Show mark scheme
8(a) [5 marks]
One mark for each correctly completed line ( Max 5 ) DECLARE Customer : TAccount DECLARE Location : INTEGER DECLARE AccountFile : STRING AccountFile "AccountRecords.dat" OPENFILE AccountFile FOR RANDOM OUTPUT "Please enter an account number" INPUT Customer.AccountNumber Location Hash( Customer.AccountNumber ) SEEK AccountFile , Location GETRECORD AccountFile, Customer OUTPUT Customer CLOSEFILE AccountFile
8(b) [1 mark]
One mark for correct definition (Exception handling is the process of) responding to an unexpected event when the program is running so it does not halt unexpectedly
8(c) [2 marks]
One mark per mark point ( Max 2 ), for example: • Programming errors • User errors • Hardware failure • Runtime errors
The location of a record in a random file is determined using a hashing algorithm.
A collision may occur during the process of adding a record.
(a) Outline what is meant by the term collision in this context. 2 marks
(b) Explain how a collision can be dealt with when writing records to a random file. 3 marks
Show mark scheme
3(a) [2 marks]
One mark per mark point ( Max 2 ) MP1 A collision is when the two values / data items in the key field for two records (pass through a hashing algorithm and) result in the same hash value MP2 …so the location identified (by the hashing algorithm) may already be in use // two records cannot occupy the same address.
3(b) [3 marks]
One mark per mark point ( Max 3 ) MP1 A process of collision resolution is used MP2 Start at the original hashed storage space MP3 …go through the following spaces in a linear fashion MP4 …and store the data item in the first available slot. OR MP5 Search the overflow area MP6 …go through the following spaces in a linear fashion MP7 …and store the data item in the first available slot. OR MP8 Each storage space holds a reference to a collection / chain of items MP9 …which can be searched individually. MP10 The data item is stored in the first available space in this chain.
(b) A pseudocode algorithm searches for a customer record in a random file AccountRecord.dat . A user inputs the name of the customer. 7 marks
The records are stored using the user‑defined data type TAccount .
TYPE TAccount
DECLARE AccountNumber : INTEGER
DECLARE Name : STRING
DECLARE Address : STRING
DECLARE Telephone : STRING
ENDTYPE
If the record is found, it is output, otherwise an error message is displayed.
Complete the file handling pseudocode.
DECLARE Customer : TAccount
DECLARE Location : INTEGER
DECLARE MaxSize : INTEGER
DECLARE FoundFlag : BOOLEAN
DECLARE SearchCustomer : STRING
MaxSize 1000
OPENFILE
Location 1
______ FALSE
OUTPUT "Enter the customer’s name"
______ AND Location <= MaxSize
______ "AccountRecord.dat",
GETRECORD "AccountRecord.dat", Customer
IF SearchCustomer = Customer.Name THEN
OUTPUT "Customer found: "
OUTPUT Customer // output customer record
FoundFlag TRUE
ENDIF
Location Location + 1
ENDWHILE
IF NOT FoundFlag THEN
OUTPUT " ______ "
ENDIF
Show mark scheme
12(a) [2 marks]
One mark for description, for example: An exception is an event that occurs during the execution of a program that disrupts the normal flow of instructions / causes the program to halt execution One mark for example: • Hardware failure // hard disk crash • Programming error // trying to access out-of-bounds array element // divide by zero error // runtime error • User error // typing incorrect filename / data type
12(b) [7 marks]
One mark for each correctly completed blank ( Max 7 ) DECLARE Customer : TAccount DECLARE Location : INTEGER DECLARE MaxSize : INTEGER DECLARE: FoundFlag : BOOLEAN DECLARE SearchCustomer : STRING MaxSize 1000 OPENFILE "AccountRecord.dat" FOR RANDOM Location 1 FoundFlag FALSE OUTPUT "Enter the customer’s name" INPUT SearchCustomer WHILE NOT FoundFlag AND Location <= MaxSize SEEK "AccountRecord.dat", Location GETRECORD "AccountRecord.dat", Customer IF SearchCustomer = Customer.Name THEN OUTPUT "Customer found: " OUTPUT Customer FoundFlag TRUE ENDIF Location Location + 1 ENDWHILE IF NOT FoundFlag THEN OUTPUT " Customer does not exist. " ENDIF
(a) Describe sequential and random methods of file organisation. 4 marks
Sequential file organisation
Random file organisation
(b) Outline the process of sequential access for serial and sequential files. 2 marks
Show mark scheme
4(a) [4 marks]
One mark per mark point – sequential ( Max 2 ) MP1 Records (in the file) are ordered MP2 … based on the key field MP3 A new version (of the file) has to be created to update the file One mark per mark point – random ( Max 2 ) MP4 Records are stored in no particular order within the file // There is no sequencing in the placement of the records MP5 There is a relationship between the key of the record and its location within the file // a hashing algorithm is used to find the location of the record MP6 Updates to the file can be carried out directly.
4(b) [2 marks]
One mark per mark point ( Max 2 ) MP1 Start at the beginning of the file MP2 …check records linearly MP3 …until the desired record is found // … processing / updating records as required //… EOF found.
(a) A pseudocode algorithm finds a customer account record in a random file and outputs it. The records are stored using the user-defined data type TAccount . 5 marks
TYPE TAccount
DECLARE AccountNumber : INTEGER
DECLARE LastName : STRING
DECLARE FirstName : STRING
DECLARE Address : STRING
DECLARE ContactNumber : STRING
ENDTYPE
Complete the file handling pseudocode.
The function Hash() takes the customer account number as a parameter, calculates and
returns the hash value.
DECLARE Customer : TAccount
DECLARE Location : INTEGER
DECLARE AccountFile : STRING
______ "AccountRecords.dat"
______ AccountFile
OUTPUT "Please enter an account number"
INPUT Customer.AccountNumber
Location Hash( ______)
SEEK ______, Location
______ AccountFile,
OUTPUT Customer // output customer record
CLOSEFILE AccountFile
(b) Define the term exception handling . 1 mark
(c) State two possible causes of an exception. 2 marks
Show mark scheme
8(a) [5 marks]
One mark for each correctly completed line ( Max 5 ) DECLARE Customer : TAccount DECLARE Location : INTEGER DECLARE AccountFile : STRING AccountFile "AccountRecords.dat" OPENFILE AccountFile FOR RANDOM OUTPUT "Please enter an account number" INPUT Customer.AccountNumber Location Hash( Customer.AccountNumber ) SEEK AccountFile , Location GETRECORD AccountFile, Customer OUTPUT Customer CLOSEFILE AccountFile
8(b) [1 mark]
One mark for correct definition (Exception handling is the process of) responding to an unexpected event when the program is running so it does not halt unexpectedly
8(c) [2 marks]
One mark per mark point ( Max 2 ), for example: • Programming errors • User errors • Hardware failure • Runtime errors
(a) A hashing algorithm is used to calculate storage locations for records in a random access file. 2 marks
It calculates hash values by using the function modulus 3.
The function modulus gives the remainder after integer division. For example, 1030 modulus 3 = 1. Therefore, the record key 1030 gives a hash value of 1.
Complete the table to show the remaining hash values.
| Record key | Hash value |
|---|---|
1030 |
1 |
1050 |
|
1025 |
(b) Describe what happens, in relation to the storage or retrieval of a record in the file, when the calculated hash value is a duplicate of a previously calculated hash value for a different record key. 4 marks
Show mark scheme
3(a) [4 marks]
One mark for each correct hash value ( Max 2 ) Record key Hash value 1030 1 1050 0 1025 2
3(b)
One mark per mark point ( Max 4 ) MP1 A collision occurs when the record key doesn’t match the stored record key MP2 … this means the determined storage location has already been used for another record. If the record is to be stored MP3 Search the file linearly MP4 … to find the next available storage space (closed hash) MP5 Search the overflow area linearly MP6 … to find next available storage space (open hash) If the record is to be found MP7 … search the overflow area linearly (open hash) until the matching record key is found MP8 … search linearly from where you are (closed hash) until the matching record key is found MP9 If not found record is not in file
(a) Describe how records are organised and accessed in a sequential file. 3 marks
(b) A hashing algorithm is used to calculate storage locations for records in a random access file. 2 marks
The algorithm calculates hash values using the function modulus 5.
The function modulus gives the remainder after integer division. For example, 3003 modulus 5 = 3, so the record key 3003 gives a hash value of 3.
Complete the table to show the remaining hash values.
| Record key | Hash value |
|---|---|
3003 |
3 |
1029 |
|
7630 |
Show mark scheme
2(a) [3 marks]
One mark per mark point ( Max 3 ) MP1 records are stored in a particular order MP2 the order is determined based on the value in a key field MP3 records are accessed one after the other MP4 records can be found by searching from the beginning of the file, record by record, MP5 … until the required record is found or key field value is exceeded.
2(b) [2 marks]
One mark for each correct hash value ( Max 2 ) Record key Hash value 3003 3 1029 4 7630 0
(a) Write pseudocode statements to declare the composite data type, TAppointments, to hold data about patients for a dental clinic. It will include for each patient: 4 marks
name (first name and last name)
date of birth
telephone number
date of last appointment
date of next appointment
all treatments are complete (yes or no).
(b) This pseudocode algorithm reads dental records stored in a random file using the user‑defined data type TAppointments and prints the contents of the file, one record at a time. 5 marks
Complete this file handling pseudocode:
DECLARE DentalRecord : ARRAY[1:250] OF TAppointments
DECLARE DentalFile : STRING
DECLARE Count : INTEGER
DentalFile "DentalFile.dat"
OUTPUT "The file ", DentalFile, " contains these records:"
OPENFILE
______ 1
REPEAT
SEEK DentalFile, Count
OUTPUT DentalRecord[Count]
Count Count + 1
______ (DentalFile)
Show mark scheme
6(a) [5 marks]
One mark for and correct TYPE TAppointments ENDTYPE One mark for every two correct declarations ( Max 3 ) Example answer TYPE TAppointments DECLARE Name : STRING DECLARE DateOfBirth : DATE DECLARE Telephone : STRING DECLARE LastAppointment : DATE DECLARE NextAppointment : DATE DECLARE TreatmentsComplete : BOOLEAN ENDTYPE
6(b) [2 marks]
One mark for each correctly completed line ( Max 5 ) DECLARE DentalRecord : ARRAY[1:250] OF TAppointments DECLARE DentalFile : STRING DECLARE Count : INTEGER DentalFile "DentalFile.dat" OUTPUT "The file ", DentalFile, " contains these records:" OPENFILE DentalFile FOR RANDOM Count 1 REPEAT SEEK DentalFile, Count GETRECORD DentalFile, DentalRecord[Count] OUTPUT DentalRecord[Count] Count Count + 1 UNTIL EOF (DentalFile) CLOSEFILE DentalFile
(a) A hashing algorithm is used to calculate storage locations for records in a random access file. 2 marks
It calculates hash values by using the function modulus 3.
The function modulus gives the remainder after integer division. For example, 1030 modulus 3 = 1. Therefore, the record key 1030 gives a hash value of 1.
Complete the table to show the remaining hash values.
| Record key | Hash value |
|---|---|
1030 |
1 |
1050 |
|
1025 |
(b) Describe what happens, in relation to the storage or retrieval of a record in the file, when the calculated hash value is a duplicate of a previously calculated hash value for a different record key. 4 marks
Show mark scheme
3(a) [4 marks]
One mark for each correct hash value ( Max 2 ) Record key Hash value 1030 1 1050 0 1025 2
3(b)
One mark per mark point ( Max 4 ) MP1 A collision occurs when the record key doesn’t match the stored record key MP2 … this means the determined storage location has already been used for another record. If the record is to be stored MP3 Search the file linearly MP4 … to find the next available storage space (closed hash) MP5 Search the overflow area linearly MP6 … to find next available storage space (open hash) If the record is to be found MP7 … search the overflow area linearly (open hash) until the matching record key is found MP8 … search linearly from where you are (closed hash) until the matching record key is found MP9 If not found record is not in file
(a) Compare sequential and serial methods of file organisation. 4 marks
(b) State the most suitable method of file access when a record is referenced by a unique address on a disk-type storage medium. 1 mark
(c) State the most suitable method of file access when a bank stores its data records in ascending order of account number. 1 mark
Show mark scheme
5(a) [4 marks]
One mark for each correct marking point (Max 4) In both serial and sequential files records are stored one after the other … • … and need to be accessed one after the other • Serial files are stored in chronological order • Sequential files are stored with ordered records • … and stored in the order of the key field • In serial files, new records are added in the next available space / records • are appended to the file In sequential files, new records are inserted in the correct position. •
5(b) [1 mark]
Direct (access)
5(c) [1 mark]
Sequential (access)
(a) Compare sequential and serial methods of file organisation. 4 marks
(b) State the most suitable method of file access when a record is referenced by a unique address on a disk-type storage medium. 1 mark
(c) State the most suitable method of file access when a bank stores its data records in ascending order of account number. 1 mark
Show mark scheme
5(a) [4 marks]
One mark for each correct marking point (Max 4) In both serial and sequential files records are stored one after the other … • … and need to be accessed one after the other • Serial files are stored in chronological order • Sequential files are stored with ordered records • … and stored in the order of the key field • In serial files, new records are added in the next available space / records • are appended to the file In sequential files, new records are inserted in the correct position. •
5(b) [1 mark]
Direct (access)
5(c) [1 mark]
Sequential (access)