Advanced Data Representation and File Organisation: Computer Science 9618 (Cambridge International AS & A Level)
Syllabus 13.1, 13.2, 13.3 · Strand 1 Data Representation and Multimedia
- Questions
- 10
- Total marks
- 65
- Tier mix
- 10 Core
0 of 10 questions completed
Syllabus coverage
- 13.1 5 questions completed
- 13.2 2 questions completed
- 13.3 3 questions completed
Building on AS-level data types, this A Level topic (syllabus ref 13.1–13.3) is about defining your own types and representing real numbers in binary with limited precision. A user-defined type can be non-composite, like an enumerated type or a pointer, or composite, like a set, record or class/object. Choosing the right one for a given problem is the exam skill. Files also need an organisation strategy: serial, sequential (using a key field) or random (using a record key), each paired with a matching access method, and a hashing algorithm can map a key directly to a random file’s storage location.
Floating-point representation stores a real number as a mantissa and exponent in two’s complement form, and normalising it maximises precision for a given bit allocation. Because only finitely many bits are available, some real numbers can only be approximated, which is the root cause of rounding error; pushing a value beyond the representable range causes overflow or underflow. Converting a floating-point number to and from denary, and explaining what changing the mantissa/exponent split does to range and precision, are both directly examined.
The worked examples below are original and step through each conversion and design choice in full.
Question 1
A quiz app stores each question's difficulty level. A difficulty level can only ever be one of
four fixed named values: Easy, Medium, Hard or Expert. No other value is ever valid.
Which user-defined data type should be used to store a single question's difficulty level?
Question 2
A vehicle repair garage keeps three separate computer files.
-
JobLog: every time a mechanic finishes a repair job, a new record is appended to the end of this file. At the end of each day, the whole file is read from start to finish to print a worksheet of everything completed that day. Individual jobs are never looked up on their own, and the file is never searched for one specific job.
-
CustomerMaster: this file holds one record per customer, held in order of the key field
CustomerID. Once a month, the file is processed from the first record to the last, inCustomerIDorder, to update every customer's loyalty points. Occasionally, when a customer phones in, the receptionist needs to bring up that one customer's record straight away. -
PartsStock: the till system must fetch a single spare part's record immediately by its
PartCodethe moment a part is scanned, without reading through any other records first.
(a) State which file organisation is most suitable for JobLog, and justify your choice. [2]
(b) State which file organisation is most suitable for CustomerMaster, and describe the file access method(s) this organisation supports that let the garage meet both of the stated needs for this file. [3]
(c) State which file organisation is most suitable for PartsStock, and explain how the storage location of an individual record is determined in this organisation. [3]
Question 3
A gym stores each member's record in a random access file, MemberFile. The storage location for
a member's record is calculated from their four-digit MemberID using this hashing algorithm:
hash value ← MemberID MOD 7
MOD gives the remainder after integer division, for example, 20 MOD 7 = 6, because
7 × 2 = 14 and 20 − 14 = 6.
(a) Complete the table below by calculating the hash value produced for each MemberID. Show
your working for at least one row. [4]
| MemberID | Hash value |
|---|---|
| 2041 | ? |
| 2045 | ? |
| 2049 | ? |
| 2056 | ? |
(b) State what is meant by a collision in this context, and identify, using your answers to
part (a), which two MemberIDs collide. [2]
(c) Describe one method the file-handling routine could use to resolve the collision identified
in part (b) when the second of the two colliding records is added to MemberFile. [3]
Question 4
A sensor logging system stores real numbers using binary floating-point representation with:
- 8 bits for the mantissa
- 4 bits for the exponent
- two's complement form for both the mantissa and the exponent
- the mantissa's binary point placed immediately to the right of its sign bit, so the mantissa represents a fraction between -1 and +1, which is then multiplied by 2 raised to the power of the exponent.
(a) Write the normalised floating-point representation (mantissa and exponent, in binary) of the denary value +22. Show your working. [3]
(b) Write the normalised floating-point representation (mantissa and exponent, in binary) of the denary value -22, using the same format. Show your working. [3]
(c) State the rule that identifies a mantissa as normalised, and confirm that your answer to part (b) satisfies it. [2]
Question 5
Two floating-point systems each use a 12-bit word, split between the mantissa and the exponent (both held in two's complement form, with the mantissa's binary point immediately to the right of its sign bit):
- System P: 8 bits for the mantissa, 4 bits for the exponent.
- System Q: 6 bits for the mantissa, 6 bits for the exponent.
(a) State, with a reason, which system can represent a given real number to greater precision. [2]
(b) State, with a reason, which system can represent real numbers over a wider range of magnitudes. [2]
(c) Explain what is meant by overflow in a binary floating-point system, and describe the situation that causes it in System P. [2]
(d) Explain what is meant by underflow in a binary floating-point system, and describe the situation that causes it in System P. [2]
(e) The denary value 22.3 is stored in System P. Explain why this value cannot be represented exactly, and name the general type of error this produces. [3]
Question 6
A vehicle-tracking app needs, for each vehicle, to store its RegistrationNumber and its
current Speed together with a self-contained operation IsSpeeding() that works out. Using
only that one vehicle's own stored data. Whether it is currently over the speed limit. The
operation must be bundled with the data it acts on, rather than written as a separate function
kept apart from the data.
Which composite user-defined data type is most suitable for representing one vehicle?
Question 7
A small bookshop wants to store, for each book on one shelf, four pieces of data: its Title,
its Author, its Price, and whether it is currently InStock.
(a) Write a pseudocode TYPE definition, BookRecord, that declares these four fields with
appropriate data types. [2]
(b) Write a pseudocode declaration for Bookshelf, an array able to hold BookRecord values
for exactly 3 books. [1]
(c) Write pseudocode statements that set the second book's Title, Author, Price and
InStock fields in Bookshelf to "The Hobbit", "Tolkien", 8.50 and TRUE, respectively.
[2]
(d) Write a pseudocode FOR loop that outputs the Title field of every book currently held in
Bookshelf. [2]
Question 8
A hospital's walk-in clinic wants to create a record for a new patient only at the moment that patient actually arrives, rather than reserving space in advance for a fixed number of patients who may never show up. Once created, the system must still be able to access and update that one patient's record for the rest of the session.
This pseudocode convention is used below: NEW <type> creates space in memory for a new
variable of that type and returns a pointer to it. DECLARE <name> : POINTER TO <type>
declares a pointer variable that can store a reference to a variable of that type. If Ptr is
a pointer variable, Ptr^ means "the variable that Ptr currently points to", and
Ptr^.FieldName accesses a field of that variable through the pointer.
A record type has already been defined:
TYPE PatientRecord
DECLARE NHSNumber : STRING
DECLARE Name : STRING
DECLARE Age : INTEGER
ENDTYPE
(a) State what is meant by a pointer data type. [2]
(b) Write a pseudocode declaration for PatientPtr, a pointer variable that can reference a
variable of type PatientRecord. [1]
(c) Write pseudocode that uses NEW to dynamically create a new PatientRecord variable,
makes PatientPtr reference it, and then sets the Name field of that new record, through
PatientPtr, to "Grace Oduya". [3]
(d) State one advantage of creating this patient's record dynamically via a pointer, rather
than declaring a fixed array of PatientRecord variables in advance. [2]
Question 9
A weather station stores real numbers using binary floating-point representation with:
- 10 bits for the mantissa
- 6 bits for the exponent
- two's complement form for both the mantissa and the exponent
- the mantissa's binary point placed immediately to the right of its sign bit, so the mantissa represents a fraction between -1 and +1, which is then multiplied by 2 raised to the power of the exponent.
A stored reading has mantissa 0101101000 and exponent 000100.
(a) State whether this mantissa, 0101101000, is normalised, explaining how you know. [2]
(b) Convert the exponent, 000100, to its denary value. [1]
(c) Convert the mantissa, 0101101000, to its denary fraction value, showing your working.
[3]
(d) Hence state the overall denary value represented by this stored floating-point number. [1]
(e) A second reading is stored with mantissa 1011010000 and exponent 111110. Convert both
parts to denary and state the overall denary value this represents, showing your working.
[4]
Question 10
A program needs to store which programming languages a particular student has ever used, so
that the program can quickly check whether a given language, such as Python, is among them.
The order in which the student first used each language does not matter, and if the student
has used a language more than once, it should still only be counted once, never held twice
over.
Which composite user-defined data type is most suitable for storing one student's languages?