AS & A Level Computer Science (9618)
Data representation Banker
22 questions · about 6% of the marks we indexed · examined in 9 of 9 sessions.
Practice questions
Original questions written by HomiLabs in the style of the exam, with answers and mark schemes. They are not
Cambridge past paper questions and have not been reviewed by Cambridge. Try each one before opening the answer.
Q1User-defined data types · Core · Paper 3 style · 6 marks- (a) Explain the difference between a non-composite data type and a composite data type. [2]
- (b) State whether each user-defined type is composite or non-composite.(i) enumerated(ii) record(iii) pointer(iv) set(v) class [3]
- (c) Explain why programming languages allow programmers to define their own data types. [1]
Show answer
- (a) A non-composite data type is defined without reference to any other data type (it holds a single value, e.g. an enumerated or pointer type). A composite data type is made up of / refers to one or more other data types (e.g. a record, set, array or class).
B1 non-composite – not defined in terms of other types / single value. B1 composite – built from other data types.
- (b) (i) non-composite (ii) composite (iii) non-composite (iv) composite (v) composite
3 marks all five correct; 2 marks four correct; 1 mark three correct.
- (c) The built-in types may not match the data in the problem; user-defined types make the program easier to read and maintain and let the translator check that only suitable values are used.
B1 any one valid reason.
A weather app records the type of day: Sunny, Cloudy, Rainy, Windy, Stormy.
- (a) Write pseudocode to declare an enumerated data type TDayType for these values. [2]
- (b) Write pseudocode to declare a variable Today of this type and assign it the value Rainy. [2]
- (c) State the result of the expression Today < Windy when Today has the value Rainy. Give a reason. [2]
Show answer
- (a) TYPE TDayType = (Sunny, Cloudy, Rainy, Windy, Stormy)
B1 TYPE TDayType = ( … ). B1 all five values as identifiers, not strings (no quotation marks).
- (b) DECLARE Today : TDayTypeToday ← Rainy
B1 declaration. B1 assignment.
- (c) TRUE, because the values of an enumerated type are ordered as they are listed, and Rainy comes before Windy.
B1 TRUE. B1 values are ordinal / ordered by position in the declaration.
A school library in Hyderabad stores data about each book: ISBN (13 characters), title, author, price in rupees, and whether it is on loan.
- (a) Write pseudocode to declare a record type TBook for this data. [4]
- (b) Write pseudocode to declare a 1D array, Library, to store 500 books, and to set the price of the first book to 1250. [2]
Show answer
- (a) TYPE TBook DECLARE ISBN : STRING DECLARE Title : STRING DECLARE Author : STRING DECLARE Price : REAL DECLARE OnLoan : BOOLEANENDTYPE
B1 TYPE TBook … ENDTYPE. B1 ISBN, Title, Author as STRING. B1 Price as REAL (or CURRENCY/INTEGER if justified). B1 OnLoan as BOOLEAN. (ISBN must not be INTEGER – it may start with 0 and is not used in calculations.)
- (b) DECLARE Library : ARRAY[1:500] OF TBookLibrary[1].Price ← 1250
B1 array declaration of TBook. B1 dot notation assignment.
- (a) Explain what is meant by a pointer data type. [2]
- (b) Write pseudocode to declare a pointer type TRealPtr that points to a REAL, and a variable PriceRef of this type. [2]
- (c) State the meaning of PriceRef^ and of @Price, where Price is a REAL variable. [2]
Show answer
- (a) A data type whose variables store a memory address, which is the location of (references) a value of another given type.
B1 stores a memory address. B1 of a variable/data of a stated type.
- (b) TYPE TRealPtr = ^REALDECLARE PriceRef : TRealPtr
B1 TYPE TRealPtr = ^REAL. B1 DECLARE PriceRef : TRealPtr.
- (c) PriceRef^ is the value stored at the address held in PriceRef (dereferencing). @Price is the memory address of the variable Price.
B1 each.
TYPE TIntPointer = ^INTEGERDECLARE Num1, Num2 : INTEGERDECLARE P : TIntPointerNum1 ← 20Num2 ← 35P ← @Num1P^ ← P^ + 5P ← @Num2Num1 ← Num1 + P^OUTPUT Num1, " ", Num2, " ", P^
- (a) State the output of the pseudocode. [3]
- (b) Explain why the statement P^ ← P^ + 5 changes the value of Num1. [2]
Show answer
- (a) 60 35 35
B1 Num1 = 60 (20 + 5 = 25 via the pointer, then 25 + 35). B1 Num2 = 35 (unchanged). B1 P^ = 35.
- (b) P holds the address of Num1, so P^ refers to the same memory location as Num1; storing a value in P^ stores it in Num1.
B1 P contains the address of Num1. B1 dereferencing accesses/changes that location.
A set data type is declared in pseudocode like this:TYPE TLetterSet = SET OF CHARDEFINE Vowels ('A', 'E', 'I', 'O', 'U') : TLetterSet
- (a) Write a DEFINE statement for a set Initials of type TLetterSet containing the characters 'A', 'B', 'P', 'T', 'E'. [1]
- (b) Give the result of each set operation.(i) Vowels UNION Initials(ii) Vowels INTERSECTION Initials(iii) Initials DIFFERENCE Vowels [3]
- (c) State two properties of a set that make it different from an array. [2]
Show answer
- (a) DEFINE Initials ('A', 'B', 'P', 'T', 'E') : TLetterSet
B1.
- (b) (i) {'A', 'E', 'I', 'O', 'U', 'B', 'P', 'T'} (ii) {'A', 'E'} (iii) {'B', 'P', 'T'}
B1 each (any order).
- (c) A set has no order (elements cannot be accessed by index), and each value can appear only once (no duplicates).
1 mark each: unordered / no index; no duplicate values; size can change; supports set operations such as membership test.
TYPE TSeason = (Spring, Summer, Autumn, Winter)A farmer in Punjab uses a program that plans crops by season.
- (a) Write pseudocode for a function NextSeason(S : TSeason) RETURNS TSeason that returns the season after S. The season after Winter is Spring. [4]
- (b) Explain why using TSeason is better than storing the season as an integer 1 to 4. [2]
Show answer
- (a) FUNCTION NextSeason(S : TSeason) RETURNS TSeason DECLARE Result : TSeason CASE OF S Spring : Result ← Summer Summer : Result ← Autumn Autumn : Result ← Winter Winter : Result ← Spring ENDCASE RETURN ResultENDFUNCTION
B1 function header and ENDFUNCTION. B1 CASE (or IF) structure on S. B1 Spring→Summer, Summer→Autumn, Autumn→Winter. B1 Winter→Spring and value returned. Accept IF S = Winter THEN RETURN Spring ELSE RETURN S + 1 if the language allows arithmetic on ordinal values.
- (b) The code is easier to read and understand (Summer rather than 2), and the variable can only take one of the four valid values, so invalid values such as 7 are rejected.
B1 readability / self-documenting. B1 restricts to valid values / fewer errors.
A cricket league stores data about each player as a record.TYPE TPlayer DECLARE Name : STRING DECLARE Team : STRING DECLARE Innings : INTEGER DECLARE Runs : INTEGERENDTYPEDECLARE Squad : ARRAY[1:25] OF TPlayer
- (a) Write a pseudocode procedure ShowAverages() that outputs the name and batting average (Runs ÷ Innings) of every player in Squad. Players who have not batted (Innings = 0) must be output with the message "no innings" instead of an average. [5]
- (b) A player has 412 runs from 9 innings. Calculate the average to 2 decimal places. [1]
Show answer
- (a) PROCEDURE ShowAverages() DECLARE Index : INTEGER FOR Index ← 1 TO 25 IF Squad[Index].Innings = 0 THEN OUTPUT Squad[Index].Name, " no innings" ELSE OUTPUT Squad[Index].Name, " ", Squad[Index].Runs / Squad[Index].Innings ENDIF NEXT IndexENDPROCEDURE
1 mark each: procedure header/end; loop 1 to 25; test for Innings = 0 with message; average calculated as Runs / Innings; correct dot notation used to access fields with output of name.
- (b) 45.78
B1: 412 ÷ 9 = 45.78.
For each item of data, choose the most suitable user-defined data type from: enumerated, pointer, set, record. Give a reason for each.
- (a(i)) The state of a traffic light: Red, Amber, Green. [2]
- (a(ii)) The next node in a linked list stored in dynamic memory. [2]
- (a(iii)) A customer's ID, name, phone number and loyalty points. [2]
- (a(iv)) The collection of characters that are allowed in a password, where order does not matter. [2]
Show answer
- (a(i)) Enumerated – a small fixed list of named values.
B1 data type. B1 reason.
- (a(ii)) Pointer – it holds the memory address of the next node.
B1 data type. B1 reason.
- (a(iii)) Record – it groups related data items of different types under one identifier.
B1 data type. B1 reason.
- (a(iv)) Set – an unordered collection of unique values that can be tested for membership.
B1 data type. B1 reason.
A linked list is held in dynamic memory.TYPE TNodePtr = ^TNodeTYPE TNode DECLARE Data : INTEGER DECLARE Next : TNodePtrENDTYPEDECLARE StartPtr : TNodePtrStartPtr holds the address 3040. The nodes are:address 3040: Data 12, Next 3016address 3016: Data 30, Next 3088address 3088: Data 7, Next NULL
- (a) State the value of StartPtr^.Next^.Data. [1]
- (b) Write pseudocode for a function ListTotal() RETURNS INTEGER that follows the pointers from StartPtr and returns the total of all the Data values. [5]
- (c) State the value returned by the function for this list. [1]
Show answer
- (a) 30
B1: StartPtr^ is the node at 3040; its Next is 3016; the Data there is 30.
- (b) FUNCTION ListTotal() RETURNS INTEGER DECLARE Current : TNodePtr DECLARE Total : INTEGER Total ← 0 Current ← StartPtr WHILE Current <> NULL Total ← Total + Current^.Data Current ← Current^.Next ENDWHILE RETURN TotalENDFUNCTION
1 mark each: local pointer declared and set to StartPtr; total initialised to 0; loop until NULL; Data added using Current^.Data; pointer moved using Current^.Next and total returned.
- (c) 49
B1: 12 + 30 + 7 = 49.
TYPE TIntPtr = ^INTEGERDECLARE Score, Bonus : INTEGERDECLARE Ptr : TIntPtrThe variables are stored at these memory addresses: Score 5120, Bonus 5121, Ptr 5122.Score ← 48Bonus ← 7Ptr ← @ScorePtr^ ← Ptr^ + BonusPtr ← @BonusBonus ← Ptr^ * 2
- (a) Complete the final values: Score, Bonus, Ptr, Ptr^ and @Ptr. [5]
- (b) Explain why the statement Bonus ← Ptr^ * 2 has the same effect as Ptr^ ← Ptr^ * 2 at that point in the code. [1]
Show answer
- (a) Score 55, Bonus 14, Ptr 5121, Ptr^ 14, @Ptr 5122
B1 each. Score = 48 + 7 = 55; Bonus = 7 × 2 = 14; Ptr holds the address of Bonus (5121); Ptr^ is the value at 5121 = 14; @Ptr is the address of Ptr itself = 5122.
- (b) Ptr points to Bonus, so Ptr^ and Bonus are the same memory location.
B1.
A courier company in Pakistan charges for parcels like this: Rs 180 for the first kilogram or part of a kilogram, plus Rs 90 for each extra kilogram or part of a kilogram. Express parcels cost double.Write your answers in Python. (Java or VB.NET are also accepted.)
- (a) Write program code to declare the class Parcel with the private attributes TrackingID (string), Weight (real, in kg) and Express (Boolean), a constructor that takes all three values as parameters, and a get method GetTrackingID(). [5]
- (b) Write the method GetCost() that returns the cost of the parcel in rupees. [4]
- (c) Write main program code that creates these four Parcel objects in an array (list), then outputs each tracking ID with its cost, and finally the total cost.KHI-1001, 0.8 kg, not expressLHE-2040, 2.3 kg, expressISB-3307, 5.0 kg, not expressPEW-4112, 1.01 kg, expressState the output. [5]
Show answer
- (a) class Parcel: def __init__(self, TrackingID, Weight, Express): self.__TrackingID = TrackingID self.__Weight = Weight self.__Express = Express def GetTrackingID(self): return self.__TrackingID
1 mark each: class heading; constructor with three parameters; all three attributes private (double underscore in Python / Private in VB / private in Java); attributes assigned from parameters; get method returns TrackingID.
- (b) import math # at the top of the program def GetCost(self): Kilos = math.ceil(self.__Weight) Cost = 180 + (Kilos - 1) * 90 if self.__Express: Cost = Cost * 2 return Cost
1 mark each: weight rounded up to whole kilograms (math.ceil or equivalent); 180 for first kg; + 90 × (kg − 1); doubled when Express is True and value returned.
- (c) Parcels = [Parcel("KHI-1001", 0.8, False), Parcel("LHE-2040", 2.3, True), Parcel("ISB-3307", 5.0, False), Parcel("PEW-4112", 1.01, True)]Total = 0for P in Parcels: print(P.GetTrackingID(), P.GetCost()) Total = Total + P.GetCost()print("Total cost: Rs", Total)Output:KHI-1001 180LHE-2040 720ISB-3307 540PEW-4112 540Total cost: Rs 1980
1 mark each: four objects created with correct arguments; stored in a list/array; loop outputs ID and cost using the methods; total accumulated and output; correct output (180, 720, 540, 540, total 1980). Tested in Python 3.
A clinic in Rawalpindi stores patient data. Each patient has a patient number, a name, a blood group (one of A+, A−, B+, B−, AB+, AB−, O+, O−), a date of birth, and a list of the allergies they have, chosen from a fixed list: Penicillin, Aspirin, Latex, Peanuts, Iodine.
- (a) Write pseudocode to declare an enumerated type TBloodGroup. Use identifiers such as APos and ANeg. [2]
- (b) Write pseudocode to declare a set type TAllergySet for the allergies, using an enumerated type TAllergy. [2]
- (c) Write pseudocode to declare a record type TPatient that uses these types. [3]
- (d) Explain why a set is more suitable than an array for storing a patient's allergies. [1]
Show answer
- (a) TYPE TBloodGroup = (APos, ANeg, BPos, BNeg, ABPos, ABNeg, OPos, ONeg)
B1 correct TYPE syntax. B1 all eight values as identifiers.
- (b) TYPE TAllergy = (Penicillin, Aspirin, Latex, Peanuts, Iodine)TYPE TAllergySet = SET OF TAllergy
B1 enumerated TAllergy. B1 SET OF TAllergy.
- (c) TYPE TPatient DECLARE PatientNo : STRING DECLARE Name : STRING DECLARE BloodGroup : TBloodGroup DECLARE DateOfBirth : DATE DECLARE Allergies : TAllergySetENDTYPE
B1 TYPE … ENDTYPE with PatientNo and Name. B1 BloodGroup : TBloodGroup and DateOfBirth : DATE. B1 Allergies : TAllergySet.
- (d) Each allergy is either present or not, order does not matter and no allergy can be stored twice; membership can be tested directly (e.g. Penicillin IN Allergies).
B1.
In this question, floating-point numbers use an 8-bit mantissa followed by a 4-bit exponent, both in two's complement. The binary point in the mantissa is after the first (sign) bit.
- (a) Convert this normalised floating-point number to denary. Show your working.Mantissa 01101000, exponent 0011 [3]
- (b) State how you can tell that this number is normalised. [1]
Show answer
- (a) 6.5
M1 mantissa = 0.1101 = 0.8125. M1 exponent = 3. A1 0.8125 × 2³ = 6.5 (or move point 3 places: 0110.1000 = 6.5).
- (b) The first two bits of the mantissa are different (0 then 1).
B1.
In this question, floating-point numbers use an 8-bit mantissa followed by a 4-bit exponent, both in two's complement. The binary point in the mantissa is after the first (sign) bit.
- (a) Show how the denary number +3.75 is represented as a normalised floating-point number. Show your working. [3]
- (b) Give the denary value of the largest positive number that can be represented in this format. [2]
Show answer
- (a) Mantissa 01111000, exponent 0010
M1 3.75 = 11.11 in binary. M1 = 0.1111 × 2². A1 mantissa 01111000 and exponent 0010.
- (b) 127
M1 mantissa 01111111 = 127/128, exponent 0111 = 7. A1 127/128 × 2⁷ = 127.
In this question, floating-point numbers use an 8-bit mantissa followed by a 4-bit exponent, both in two's complement. The binary point in the mantissa is after the first (sign) bit.
- (a) Give two reasons why floating-point numbers are normalised. [2]
- (b) State which of these mantissas are normalised.P 00101100Q 01000001R 11011010S 10110000 [2]
Show answer
- (a) To give the greatest possible precision for the number of mantissa bits (no wasted leading 0s or 1s), and so that each value has only one representation.
B1 maximises precision. B1 unique representation (easier comparison).
- (b) Q and S
2 marks both and no others; 1 mark one correct with no wrong one. A normalised positive mantissa starts 01, a normalised negative mantissa starts 10.
In parts (b) and (c), floating-point numbers use a 10-bit mantissa followed by a 6-bit exponent, both in two's complement. The binary point in the mantissa is after the first (sign) bit.In part (a) the format is an 8-bit mantissa and a 4-bit exponent.
- (a) Convert this floating-point number to denary: mantissa 10100000, exponent 0100. [2]
- (b) Show how −5.25 is represented as a normalised floating-point number with a 10-bit mantissa and 6-bit exponent. [3]
- (c) Convert this normalised number (10-bit mantissa, 6-bit exponent) to denary: mantissa 1011010000, exponent 000100. [2]
Show answer
- (a) −12
M1 mantissa = −1 + 0.25 = −0.75. A1 −0.75 × 2⁴ = −12.
- (b) Mantissa 1010110000, exponent 000011
M1 +5.25 = 101.01 = 0.10101 × 2³. M1 two's complement of mantissa: 0101010000 → 1010110000. A1 exponent 000011.
- (c) −9.5
M1 mantissa = −1 + 0.25 + 0.125 + 0.03125 = −0.59375. A1 × 2⁴ = −9.5.
In this question, floating-point numbers use an 8-bit mantissa followed by a 4-bit exponent, both in two's complement. The binary point in the mantissa is after the first (sign) bit.
- (a) Normalise this floating-point number: mantissa 00010110, exponent 0011. Give the new mantissa and exponent. [2]
- (b) Normalise this floating-point number: mantissa 11110100, exponent 0010. Give the new mantissa and exponent, and the denary value. [3]
Show answer
- (a) Mantissa 01011000, exponent 0001
M1 shift mantissa left 2 places. A1 exponent reduced by 2: 3 − 2 = 1 → 0001.
- (b) Mantissa 10100000, exponent 1111; value −0.375
M1 shift left 3 places to get 10100000. A1 exponent 2 − 3 = −1 = 1111. A1 −0.75 × 2⁻¹ = −0.375.
In this question, floating-point numbers use an 8-bit mantissa followed by a 4-bit exponent, both in two's complement. The binary point in the mantissa is after the first (sign) bit.
- (a) Give the mantissa and exponent of the smallest positive normalised number in this format, and its denary value as a fraction. [3]
- (b) The 12 bits are reorganised as a 9-bit mantissa and a 3-bit exponent. Explain the effect on the range and the precision of the numbers that can be represented. [2]
Show answer
- (a) Mantissa 01000000, exponent 1000; value 1/512
B1 mantissa 01000000. B1 exponent 1000 (−8). B1 0.5 × 2⁻⁸ = 1/512.
- (b) Precision increases because there are more mantissa bits; range decreases because the exponent has fewer bits so it can take fewer (smaller) values.
B1 precision increases (more mantissa bits). B1 range decreases (smaller exponent).
In this question, floating-point numbers use an 8-bit mantissa followed by a 4-bit exponent, both in two's complement. The binary point in the mantissa is after the first (sign) bit.
- (a) Show that the denary number 0.1 cannot be represented exactly in this format. Give the nearest normalised representation and its denary value. [4]
- (b) Calculate the absolute error in storing 0.1 like this. [1]
Show answer
- (a) Nearest: mantissa 01100110, exponent 1101, value 0.099609375
M1 0.1 in binary is the recurring fraction 0.000110011…, so it can never be stored exactly in a finite number of bits. M1 normalised as 0.1100110011… × 2⁻³. A1 mantissa 01100110, exponent 1101. A1 51/512 = 0.099609375.
- (b) 0.000390625
B1: 0.1 − 0.099609375 = 0.000390625.
In this question, floating-point numbers use a 10-bit mantissa followed by a 6-bit exponent, both in two's complement. The binary point in the mantissa is after the first (sign) bit.
- (a) Give the mantissa and exponent of the most negative number that can be represented, and its denary value as a power of 2. [3]
- (b) Give the denary value of the largest positive number, as an exact integer. [2]
- (c) Explain the terms overflow and underflow in the context of floating-point arithmetic. [2]
Show answer
- (a) Mantissa 1000000000, exponent 011111; value −2³¹
B1 mantissa 1000000000 (−1). B1 exponent 011111 (31). B1 −1 × 2³¹ = −2³¹ (−2 147 483 648).
- (b) 2 143 289 344
M1 (1 − 2⁻⁹) × 2³¹. A1 2 143 289 344.
- (c) Overflow: the result of a calculation is too large in size to be represented (exponent would need to be bigger than the maximum, 31). Underflow: the result is too close to zero (non-zero but smaller than the smallest representable magnitude), so it is stored as 0.
B1 overflow – result too large / exponent exceeds maximum. B1 underflow – result too small in magnitude / exponent below minimum, becomes 0.
In this question, floating-point numbers use an 8-bit mantissa followed by a 4-bit exponent, both in two's complement. The binary point in the mantissa is after the first (sign) bit.
- (a) Show how the denary value −0.40625 is represented as a normalised floating-point number. Show your working. [4]
- (b) A student writes the answer as mantissa 11001100, exponent 0000. Show that this represents the same value, and explain why it is not acceptable. [2]
Show answer
- (a) Mantissa 10011000, exponent 1111
M1 0.40625 = 0.01101 in binary. M1 normalised positive: 0.1101 × 2⁻¹ → 01101000. M1 two's complement of mantissa: 10011000. A1 exponent −1 = 1111.
- (b) 11001100 = −1 + 0.5 + 0.0625 + 0.03125 = −0.40625, × 2⁰ = −0.40625. It is not normalised because it starts 11, so one bit of precision is wasted.
B1 shows the value is −0.40625. B1 not normalised (first two bits the same) / less precision.
In this question, floating-point numbers use an 8-bit mantissa followed by a 4-bit exponent, both in two's complement. The binary point in the mantissa is after the first (sign) bit.X: mantissa 01100000, exponent 0011Y: mantissa 01010000, exponent 0001
- (a) Give the denary values of X and Y. [2]
- (b) Describe how the processor adds X and Y, and give the result as a normalised floating-point number. [4]
- (c) Explain why shifting a mantissa to the right before an addition can lead to a loss of accuracy. [1]
Show answer
- (a) X = 6, Y = 1.25
B1 each: X = 0.75 × 2³; Y = 0.625 × 2¹.
- (b) Make the exponents the same: shift Y's mantissa right 2 places so Y = 0.0101 × 2³. Add mantissas: 0.11 + 0.0101 = 0.1110100. Result mantissa 01110100, exponent 0011 (already normalised) = 7.25.
M1 exponents equalised (smaller exponent increased to 3, mantissa shifted right). M1 mantissas added. A1 mantissa 01110100. A1 exponent 0011 (value 7.25).
- (c) Bits shifted off the right end of the mantissa are lost, so the result may be rounded/truncated.
B1.
In this question, floating-point numbers use a 12-bit mantissa followed by a 4-bit exponent, both in two's complement. The binary point in the mantissa is after the first (sign) bit.A program for a petrol pump in Karachi adds 0.1 litres to a total each time a sensor pulses.
- (a) Give the nearest normalised representation of 0.1 in this format (truncate the recurring pattern), and its exact value as a fraction. [3]
- (b) Calculate the error in the total after 10 000 pulses, correct to 3 significant figures, assuming each addition is exact. [2]
- (c) Suggest how the programmer could avoid this kind of error. [1]
Show answer
- (a) Mantissa 011001100110, exponent 1101; value 819/8192
M1 0.1 = 0.0001100110011… = 0.11001100110 × 2⁻³. A1 mantissa 011001100110, exponent 1101. A1 819/8192.
- (b) 0.244 litres too small
M1 error per pulse = 0.1 − 819/8192 = 0.0000244140625. A1 × 10 000 = 0.244 litres.
- (c) Count pulses as an integer and divide by 10 only when displaying (or store the total in fixed units such as millilitres / use a decimal type).
B1.
- (a) Describe each method of file organisation.(i) serial(ii) sequential(iii) random [3]
- (b) State the difference between sequential access and direct access. [2]
Show answer
- (a) (i) Records are stored one after another in the order in which they were added (chronological), not sorted. (ii) Records are stored in order of a key field. (iii) The address of each record is calculated from its key using a hashing algorithm, so records can be stored anywhere in the file.
B1 each.
- (b) Sequential access reads records one after another from the start of the file until the required one is found. Direct access goes straight to the required record's location (e.g. by hashing the key or using an index) without reading the others.
B1 sequential. B1 direct.
- (a) For each application, state the most suitable file organisation and give a reason.(i) a log of every card transaction made at a supermarket checkout during the day(ii) a monthly payroll file of 3000 employees, processed in employee number order(iii) a flight booking system where any passenger's booking must be found instantly [6]
Show answer
- (a) (i) serial – records only need adding to the end as they happen; no order needed. (ii) sequential – every record is processed in key order in one batch run. (iii) random – the record can be accessed directly using a hash of the booking reference, giving fast access to individual records.
B1 organisation and B1 reason for each.
A warehouse in Karachi stores product records in a random file with 97 record locations, numbered 0 to 96. The hashing algorithm is: location = ProductCode MOD 97.
- (a) Calculate the location for each product code.(i) 20451(ii) 18733(iii) 30172(iv) 15601 [4]
- (b) Explain the problem shown by your answers, and describe two ways of dealing with it. [4]
Show answer
- (a) (i) 81 (ii) 12 (iii) 5 (iv) 81
B1 each.
- (b) Two different keys (20451 and 15601) hash to the same location (a collision). 1: Open hashing / linear probing – store the record in the next free location after 81 (82, 83 …); a search starts at 81 and checks onwards. 2: Overflow area – store the record in a separate overflow area that is searched serially when the home location holds a different key (or chain the records with pointers).
B1 collision identified. B1 method 1 named and B1 described. B1 method 2 described (overflow area / chaining).
A sequential file holds 5000 customer records in order of customer ID.
- (a) Calculate the average number of records that must be read to find a record that is in the file, assuming each record is equally likely to be requested. [2]
- (b) Explain why a search of this file for a customer ID that is not present can usually stop before the end of the file. [1]
- (c) Describe how a new record is added to the sequential file. [3]
Show answer
- (a) 2500.5
M1 (1 + 5000) ÷ 2. A1 2500.5.
- (b) Because records are in key order, the search can stop as soon as it reads a record with a larger ID than the one wanted.
B1.
- (c) A new file is created. Records are copied from the old file to the new file until the correct position (the first record with a larger key) is reached. The new record is written, then the remaining records are copied. The new file replaces the old one.
1 mark each, max 3: new file created; copy records before insertion point; write new record; copy remaining records; replace old file.
A random file has 13 locations numbered 0 to 12. Location = Key MOD 13. Collisions are dealt with by linear probing: the record is stored in the next free location, wrapping round from 12 to 0. The file starts empty.
- (a) The records with these keys are added in this order: 68, 41, 94, 29, 115, 25, 51. Give the location of each record. [4]
- (b) State how many locations must be read to find the record with key 29, and how many to show that a record with key 16 is not in the file. [2]
- (c) Explain why deleting the record with key 94 by simply emptying location 4 would cause a problem. [2]
Show answer
- (a) 68 → 3, 41 → 2, 94 → 4, 29 → 5, 115 → 11, 25 → 12, 51 → 0
B1 68, 41, 115 and 25 (no collision). B1 94 → 4. B1 29 → 5. B1 51 → 0 (wraps round).
- (b) 29: 3 locations (3, 4, 5). Key 16: 4 locations (3, 4, 5 then empty location 6).
B1 3. B1 4 – the search stops at the first empty location.
- (c) A later search for 29 would start at 3, then find location 4 empty and stop, wrongly reporting that 29 is not in the file. Deleted locations must be marked as 'deleted' rather than empty.
B1 search for 29 stops at the gap / not found. B1 use a deleted marker (tombstone) instead.
Student ID numbers are stored in a hash table so they can be found quickly. Write your answers in Python. (Java or VB.NET are also accepted.)The global list HashTable has 11 elements, numbered 0 to 10. An element with the value −1 is empty. The hash value of a key is Key MOD 11. Collisions are dealt with by linear probing (wrapping round from 10 to 0).
- (a) Write a function Insert(Key) that stores Key in HashTable and returns True, or returns False if the table is full. [5]
- (b) Write a function Search(Key) that returns the index where Key is stored, or −1 if it is not in the table. The search must stop at an empty element. [4]
- (c) The keys 4521, 3307, 1189, 8806, 2214, 6630, 7015, 9874 are inserted in this order. Give the final contents of HashTable and the values returned by Search(9874) and Search(5000). [4]
Show answer
- (a) TableSize = 11HashTable = [-1] * TableSizedef Hash(Key): return Key % TableSizedef Insert(Key): Index = Hash(Key) Count = 0 while HashTable[Index] != -1 and Count < TableSize: Index = (Index + 1) % TableSize Count = Count + 1 if Count == TableSize: return False HashTable[Index] = Key return True
1 mark each: hash calculated with MOD 11; loop while location not empty; index incremented with wrap-around (MOD 11); full table detected and False returned; key stored and True returned.
- (b) def Search(Key): Index = Hash(Key) Probes = 1 while HashTable[Index] != Key: if HashTable[Index] == -1 or Probes == TableSize: return -1 Index = (Index + 1) % TableSize Probes = Probes + 1 return Index
1 mark each: starts at hash position; loops until key found; returns −1 at an empty element or after checking every element; returns index when found.
- (c) HashTable = [4521, 1189, -1, 2214, -1, -1, 8806, 3307, 6630, 7015, 9874]Search(9874) returns 10Search(5000) returns -1
B1 first six keys at their hash positions (0, 7, 1, 6, 3, 8). B1 7015 at 9 (collision at 8). B1 9874 at 10 (7, 8, 9 full). B1 Search(9874) = 10 and Search(5000) = −1 (checks 6, 7, 8, 9, 10, 0, 1 then empty 2). Tested in Python 3.
