Ch 1 · 13 Data Representation · AS & A Level Computer Science 9618
Topic 1 of 2 in Data Representation and Communication — AS & A Level Computer Science 9618 — 96 lessons.
Introduction
At A Level, data representation goes further: you design your own data types, choose how records are organised in files (including hashing for direct access), and represent real numbers in floating-point binary. (Syllabus topic 13: sections 13.1–13.3.)
Key ideas — 13.1 (a) Why user-defined types?
Built-in types (INTEGER, STRING, ...) cannot describe every kind of data a problem needs. A user-defined data type is designed by the programmer, so the data can be modelled more closely (e.g. a Season that can only be one of four values), the code is easier to read, and invalid values are prevented.
🧑🏫 Teacher's explanation
Imagine you are organizing a massive library. Using only built-in types like INTEGER or STRING is like having only two types of boxes: one for numbers and one for text. If you want to store a 'Book', you could use a STRING for the title and an INTEGER for the page count, but the computer doesn't actually know those two things belong together as a single 'Book' object. It just sees a pile of disconnected labels and numbers.
📖 Definitions
🔍 Worked example — Easy
A programmer needs to represent the days of the week. Design an enumerated type for this.
🔍 Worked example — Standard
Create a composite data type for a 'Student' which includes a Name (STRING), an Age (INTEGER), and a Grade (REAL).
🔍 Worked example — Exam-style
A system tracks flight status. The possible statuses are 'On Time', 'Delayed', or 'Cancelled'. Why is an enumerated type better than a STRING for this?
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
a) Define a user-defined composite data type to represent an 'Appointment'. [3]
Key ideas — 13.1 (b) Non-composite types
A non-composite type is defined without referring to other data types (it holds a single value).
🧑🏫 Teacher's explanation
In standard programming, you are limited to the basic building blocks provided by the computer, like integers, booleans, or characters. However, real-world problems often require more specific categories. Imagine you are organizing a library; while the computer only understands 'numbers' or 'text', you need a way to represent 'Genre' (Fiction, Non-Fiction, Sci-Fi) or 'Shelf Location'.
📖 Definitions
🔍 Worked example — Easy
A programmer needs to define a type for the days of the week to ensure only valid days are used. Using Cambridge pseudocode, define the type and assign 'Wednesday' to a variable named 'Today'.
🔍 Worked example — Standard
Given a pointer variable P of type ^INTEGER and an integer variable X currently stored at memory address 0x001. If X has the value 25, what is the value of P^ (the dereferenced value) and what is the value of P?
🔍 Worked example — Exam-style
A system uses an enumerated type TYPE Status = (Pending, Active, Closed). If the current status is StatusVar, determine the result of the following logic: IF StatusVar > Pending THEN OUTPUT 'Not Pending' ELSE OUTPUT 'Is Pending' ENDIF assuming StatusVar is set to Active.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) Define a user-defined non-composite data type for the delivery status using Cambridge pseudocode. [2] (b) Explain why an enumerated type is more appropriate for this requirement than a standard integer type. [2] [4 marks]
Key ideas — 13.1 (c) Composite types
A composite type is built from other data types.
🧑🏫 Teacher's explanation
In standard programming, you are limited to basic building blocks like integers, booleans, and characters. However, real-world data is rarely that simple. If you were building a database for a school, a single 'Student' isn't just a number; it is a collection of a name (string), an ID (integer), and a list of subjects (set).
📖 Definitions
🔍 Worked example — Easy
A programmer needs to store the details of a single book. The book has a title (string), a price (real), and a publication year (integer). Identify the most appropriate user-defined type.
🔍 Worked example — Standard
Define a user-defined type in Cambridge pseudocode for a 'Student' which contains a name (STRING), an age (INTEGER), and a set of grades (SET OF CHAR).
🔍 Worked example — Exam-style
A system tracks the available colors in a warehouse. The colors are 'Red', 'Blue', and 'Green'. The system must ensure no color is listed twice and the order does not matter. Which composite type is best, and why?
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) Identify the most appropriate user-defined composite type to represent a single book. [1] (b) Write the Cambridge pseudocode to define this user-defined type. [3] [4 marks]
Key ideas — 13.2 (a) File organisation
🧑🏫 Teacher's explanation
Imagine you are organizing a massive collection of books in a library. If you just throw books into a bin as they arrive, that is serial organisation; it is easy to do, but if you want to find one specific book, you have to dig through the whole pile. If you arrange them by the author's name, that is sequential organisation; it takes more effort to put them away, but you can find things much faster by following the alphabet.
📖 Definitions
🔍 Worked example — Easy
A system records temperature readings from a sensor every 10 seconds. The data must be stored exactly as it arrives to ensure a chronological history. Which file organisation is most appropriate?
🔍 Worked example — Standard
A bank needs to update the monthly interest for 1,000,000 customers. The process involves reading every single account, calculating interest, and writing the new balance back. Which file organisation and access method is best?
🔍 Worked example — Exam-style
A flight booking system uses a hashing algorithm H(k) to determine the storage address of a booking. The key k is the BookingID. If the hashing algorithm is H(k) = k pmod100, calculate the storage address for a BookingID of 5432.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) Generate monthly payroll for all employees. (b) Allow a manager to instantly look up an employee's contact details using their EmployeeID.
Key ideas — 13.2 (b) File access
🧑🏫 Teacher's explanation
Imagine you are looking for a specific song on an old cassette tape versus a modern Spotify playlist. To find a song on a cassette, you have to press 'fast forward' and listen to every song in order until you hit the one you want. This is like sequential access; you start at the beginning and go one by one.
📖 Definitions
🔍 Worked example — Easy
A company stores employee records in a serial file. To find the record for Employee ID 505, which must be accessed via sequential access, how many records must be read if the target record is the 505th record in the file?
🔍 Worked example — Standard
A database uses an indexed sequential file. The file contains 1000 records. To find a specific record, the system first searches an index of 10 entries. If the index points to the correct block, and the record is the 5th record in that block, describe the access method used for the index and the block.
🔍 Worked example — Exam-style
A hashing algorithm is used for a random file. The hash function is h(k) = k pmod100. If we want to store and then retrieve a record with key k = 125, calculate the address and explain the access method.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) Identify the type of file organisation used. [1] (b) State the type of access required to find a specific student's result. [1] (c) Explain why direct access would be more efficient for this system if the number of students increased to 1,000,000. [2] [4 marks]
Key ideas — 13.2 (c) Hashing algorithms
A hashing algorithm calculates a storage address (a home address) from a record's key.
🧑🏫 Teacher's explanation
Imagine you are organizing a massive library with 1,000 lockers. If you just put books in the first available locker, you'll spend forever searching through them. Instead, you decide on a rule: take the last three digits of the book's ID and use that as the locker number. This is a hashing algorithm. It allows you to jump straight to a specific location without checking every single locker.
📖 Definitions
🔍 Worked example — Easy
A file has 50 storage locations (indexed 0 to 49). Calculate the home address for a record with key 1287 using the modulo operator.
🔍 Worked example — Standard
A hashing algorithm uses the 'folding' method. The key is 54321. The algorithm splits the key into parts: 54 + 32 + 1. If the file has 100 locations, find the address.
🔍 Worked example — Exam-style
A file has 100 locations (0-99). Key A hashes to address 42. Key B hashes to address 42. Key C hashes to address 45. Using linear probing, determine the final addresses for A, B, and C if the file was initially empty.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Key ideas — 13.3 (a) Floating-point format
A floating-point number is stored as a mantissa and an exponent, both in two's complement:
🧑🏫 Teacher's explanation
Think of scientific notation in math, like 1.5 × 10^3. Instead of writing a huge number of zeros, we store the 'significant digits' (the mantissa) and the 'power of ten' (the exponent). In computer science, we do the same thing but with base 2.
📖 Definitions
🔍 Worked example — Easy
Convert the following binary floating-point number to denary: Mantissa: 01101000, Exponent: 0011 (Assume 8-bit mantissa, 4-bit exponent).
🔍 Worked example — Standard
Convert the following binary floating-point number to denary: Mantissa: 10110000, Exponent: 0010 (Assume 8-bit mantissa, 4-bit exponent).
🔍 Worked example — Exam-style
A system uses 8 bits for the mantissa and 4 bits for the exponent (both in two's complement). Convert the denary number -5.75 into this floating-point format. The mantissa must be normalised.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) Calculate the denary value of the following binary floating-point number: Mantissa: 01101000 Exponent: 0011
Key ideas — 13.3 (b) Normalisation
A floating-point number is normalised when the first two bits of the mantissa are different:
Key ideas — 13.3 (c) Range, precision and allocation of bits
With a fixed total number of bits:
🧑🏫 Teacher's explanation
Imagine you are using a scientific calculator to measure distances. If you decide to use a ruler with very fine millimeter markings (high precision), you can measure tiny objects very accurately, but you might run out of space on your paper to record huge distances. If you decide to use a scale that measures in kilometers (high range), you can record the distance to the moon, but you lose the ability to measure a tiny pebble accurately.
📖 Definitions
🔍 Worked example — Easy
A floating-point number is represented using 8 bits for the mantissa and 4 bits for the exponent (in two's complement). Calculate the largest positive value.
🔍 Worked example — Standard
A floating-point number is represented using 8 bits for the mantissa and 4 bits for the exponent. Calculate the smallest positive normalised value.
🔍 Worked example — Exam-style
A system uses 10 bits for the mantissa and 5 bits for the exponent. Compare the range and precision of this system to a system with 8 bits for the mantissa and 7 bits for the exponent.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Key ideas — 13.3 (d) Approximation, rounding errors, overflow and underflow
🧑🏫 Teacher's explanation
Imagine you are trying to measure the exact length of a hair using only a ruler that only has centimeter markings. You cannot represent 0.00123 cm; you have to round it to 0.0 cm or 0.1 cm. This 'gap' between the true value and your measurement is the essence of approximation in computers.
📖 Definitions
🔍 Worked example — Easy
A system uses a 4-bit mantissa and a 3-bit exponent. If a calculation results in a value that requires an exponent of 2^5, what happens?
🔍 Worked example — Standard
Convert the denary 0.1_10 to binary to show why it causes a rounding error.
🔍 Worked example — Exam-style
A floating-point format has a minimum representable positive value of 1.0 × 2^-38. A calculation results in 1.0 × 2^-42. What is the result?
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Worked example
Represent 0.3125 and −0.3125 as normalised floating-point numbers with an 8-bit mantissa and a 4-bit exponent.
Common mistakes
Practice
Answers: (1) To model data that the built-in types do not describe and restrict values to valid ones, making code clearer; TYPE Light = (Red, Amber, Green). (2) (a) Random, with direct access by hashing the book ID: one record is needed quickly; (b) sequential, ordered by employee ID: every record is processed in key order. (3) 1234 MOD 50 = 34; 3184 MOD 50 = 34: a collision. Store the second record in the next free location (linear probing), an overflow area, or a chained list. (4) 0.625 × 2⁴ = 10. (5) Shift left 2 places: 0.1100000, exponent 6 − 2 = 4: 0100. (6) 0.1 is a recurring fraction in binary (0.000110011...), so it must be rounded to fit the mantissa; the stored value is an approximation, causing rounding errors that can accumulate in calculations.