Ch 2 · 10 Data Types and Structures · AS & A Level Computer Science 9618
Topic 2 of 3 in Algorithms, Data Structures and Programming — AS & A Level Computer Science 9618 — 88 lessons.
Introduction
A program is only as good as the way it organises its data. This lesson covers the data types used in Cambridge pseudocode, records, 1D and 2D arrays (with a bubble sort and a linear search), text files, and three abstract data types: the stack, the queue and the linked list. (Syllabus topic 10: sections 10.1–10.4.)
Key ideas — 10.1 (a) Data types
Choose the type that matches the data: a telephone number is a STRING (it may start with 0, and no arithmetic is done on it); a price is REAL; a count is INTEGER; a yes/no answer is BOOLEAN.
🧑🏫 Teacher's explanation
Think of data types as the different types of containers in a kitchen. You wouldn't store milk in a sieve or flour in a tea cup; you need the right container for the right substance to ensure it remains useful and doesn't leak. In computer science, telling the computer exactly what kind of data you are storing (the 'type') ensures the CPU knows how much memory to set aside and what operations are allowed.
📖 Definitions
🔍 Worked example — Easy
Identify the most appropriate data type for the following: 1) A student's age, 2) A student's GPA, 3) A student's initials.
🔍 Worked example — Standard
A system stores user profiles. Each profile contains a Username (e.g., 'coder123'), an Age (e.g., 25), and an AccountBalance (e.g., 150.50). Write the pseudocode to define this record structure.
🔍 Worked example — Exam-style
A programmer uses a STRING to store a telephone number '0123456789'. Explain why this is a better choice than an INTEGER.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) Identify the most appropriate data type for the ISBN. [1] (b) Write pseudocode to define a record structure named 'Book' that contains these three fields. [3] [4 marks]
Key ideas — 10.1 (b) Records
A record is a user-defined data structure that holds a set of data items of different data types under one identifier. Each item is a field.
🧑🏫 Teacher's explanation
Imagine you are organizing a school trip. If you only had simple variables, you would have one variable for every single student's name, another for every student's age, and another for every student's bus seat. This becomes a mess very quickly. A record is like a single physical folder for one student. Inside that folder, you have different types of information: a name (STRING), an age (INTEGER), and whether they have paid (BOOLEAN). Instead of managing hundreds of loose papers, you just manage a collection of folders.
📖 Definitions
🔍 Worked example — Easy
Define a record type called TCar that contains a Make (STRING), a Year (INTEGER), and IsElectric (BOOLEAN). Then, declare a variable MyCar of type TCar and assign it the values: Make = "Tesla", Year = 2022, IsElectric = TRUE.
🔍 Worked example — Standard
Given the following record definition:
🔍 Worked example — Exam-style
A system stores student grades. A record TGrade has StudentName : STRING and Score : INTEGER. An array ClassGrades[1:2] stores two records.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) Write the pseudocode to define a new data type TBook to hold this information. [2] (b) Write pseudocode to declare an array named Library that can hold 100 books and assign the title "The Hobbit" to the first book in the array. [2] [4 marks]
Key ideas — 10.2 (a) Arrays
An array is a data structure holding a fixed number of items of the same data type under one identifier. Each item is accessed by its index.
🧑🏫 Teacher's explanation
Imagine you are organizing a classroom of students. If you want to keep a list of their names, a single long strip of paper works perfectly—this is a 1D array. However, if you want to record each student's marks for five different subjects, a single list isn't enough. You need a grid or a table where each row is a student and each column is a subject. This grid is a 2D array.
📖 Definitions
🔍 Worked example — Easy
A 1D array is declared as DECLARE Grades : ARRAY[1:5] OF INTEGER. What is the value of Grades[3] if the array is initialized with the values [80, 75, 90, 65, 85]?
🔍 Worked example — Standard
A 2D array is declared as DECLARE Matrix : ARRAY[1:2, 1:3] OF INTEGER. Given the following data: Row 1: [10, 20, 30] Row 2: [40, 50, 60] Calculate the sum of all elements in the array.
🔍 Worked example — Exam-style
A 1D array DECLARE Data : ARRAY[1:4] OF INTEGER contains [5, 2, 8, 1]. Trace the array after one full pass of a Bubble Sort (where the largest element 'bubbles' to the end).
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) State the most appropriate data structure to use. [1] (b) Write pseudocode to declare this array. [1] (c) Write pseudocode to calculate the average mark of the first student (the first row) across all 5 subjects. [3] [5 marks]
Key ideas — 10.2 (b) Bubble sort
A bubble sort compares each pair of adjacent items and swaps them if they are in the wrong order. After each pass, the largest remaining item has "bubbled" to the end, so the next pass can stop one place earlier. If a pass makes no swaps, the array is sorted and the algorithm stops.
🧑🏫 Teacher's explanation
Imagine a line of students of different heights standing in a row. To sort them from shortest to tallest, you start at the beginning of the line. You look at the first two students; if the one on the left is taller than the one on the right, they swap places. Then you move to the next pair (the 2nd and 3rd students) and do the same. You keep doing this until you reach the end of the line.
📖 Definitions
🔍 Worked example — Standard
Given the array X = [12, 7, 15, 3], how many swaps occur during the entire bubble sort process to sort it in ascending order?
🔍 Worked example — Exam-style
An array B contains [10, 20, 30, 40]. How many passes will the optimized bubble sort (using a 'swapped' flag) perform before terminating?
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Key ideas — 10.2 (c) Linear search
A linear search checks each element in turn, from the first, until the item is found or the end is reached. It works on unsorted data.
🧑🏫 Teacher's explanation
Imagine you are looking for a specific book in a messy pile of books on a desk. You don't know where it is, and the books aren't in alphabetical order. To find it, you pick up the first book, check the title, and if it's not the one, you set it aside and pick up the second book. You keep doing this, one by one, until you either find your book or you run out of books in the pile.
📖 Definitions
🔍 Worked example — Easy
An array Scores contains the following values: [15, 42, 7, 88, 32]. Using a linear search, find the index of the value 88. Assume the array is 1-indexed.
🔍 Worked example — Standard
Trace the following pseudocode for an array Data containing ['A', 'B', 'C'] searching for 'Z'.
🔍 Worked example — Exam-style
An array Prices has 10 elements. A linear search is performed for a value that is not in the array. How many comparisons between the search value and array elements are made?
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Key ideas — 10.3 Text files
Why files are needed: data in variables and arrays is lost when the program ends. Files store data permanently on secondary storage, so it can be used again later, by the same or another program.
🧑🏫 Teacher's explanation
Imagine you are playing a video game. When you are playing, your character's health, position, and inventory are stored in the computer's RAM (Primary Storage). This is like writing on a whiteboard; it is very fast to read and change, but as soon as you turn off the power, the board is wiped clean. If you want to continue your adventure tomorrow, you need a way to save that progress.
📖 Definitions
🔍 Worked example — Easy
A program needs to create a new file named "log.txt" and record the message "System Start". Write the pseudocode to perform this task.
🔍 Worked example — Standard
A file "data.txt" contains the following lines: Line 1: Alice Line 2: Bob Line 3: Charlie Write pseudocode to read the file and output only the names that start with 'A'.
🔍 Worked example — Exam-style
A programmer uses OPENFILE "results.txt" FOR WRITE. They then use WRITEFILE "results.txt", "Score: 50". They realize they forgot a line and want to add "Score: 100" to the end of the file without deleting the first line. Write the pseudocode to add the new line.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Key ideas — 10.4 (a) Abstract data types
An abstract data type (ADT) is a collection of data and a set of operations on that data. The user of an ADT only needs to know what the operations do, not how they are implemented.
🧑🏫 Teacher's explanation
Imagine you are using a vending machine. You don't need to know how the internal motors turn or how the coin sensor works; you only need to know that if you press 'A1', a specific snack comes out. This concept of 'hiding the messy details' is what an Abstract Data Type (ADT) does. It provides a clean interface (the buttons) while hiding the complex implementation (the motors).\n\nAn ADT is essentially a package that contains both the data itself and the specific rules (operations) for how that data can be manipulated. Instead of just having a list of numbers, you have a 'Stack' which dictates that you can only add or remove items from the very top. You aren't just managing data; you are managing the *behavior* of that data.
📖 Definitions
🔍 Worked example — Easy
A stack contains the elements [A, B, C] where C is at the top. Perform the following operations: PUSH(D), POP, PUSH(E). List the final elements from bottom to top.
🔍 Worked example — Standard
A queue is implemented using an array of size 5. The current front index is 0 and the rear index is 2. Elements are at indices 0, 1, and 2. Perform: ENQUEUE(X), DEQUEUE. What is the new front index and the new rear index?
🔍 Worked example — Exam-style
A linked list has three nodes. Node 1 contains data 'Red' and points to Node 2. Node 2 contains data 'Blue' and points to Node 3. Node 3 contains data 'Green' and points to NULL. If we delete Node 2, what does the pointer in Node 1 point to?
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Key ideas — 10.4 (b) Implementing ADTs with arrays
Stack: a 1D array plus a top-of-stack pointer (the index of the top item; 0 when empty).
🧑🏫 Teacher's explanation
An Abstract Data Type (ADT) is like a vending machine. You don't care how the internal gears turn; you only care about the operations: 'insert money' and 'select snack'. In computer science, an ADT defines *what* can be done with data, while the implementation (like using an array) defines *how* it is actually stored in memory.
📖 Definitions
🔍 Worked example — Easy
A stack is implemented using a 1D array of size 5. The current TopPointer is 3. Perform a PUSH operation with the value 99.
🔍 Worked example — Standard
A circular queue has an array of size 5 (indices 1 to 5). The FrontPointer is 5, the RearPointer is 4, and the Count is 4. Perform a DEQUEUE operation.
🔍 Worked example — Exam-style
A linked list is implemented using two arrays: Data[1..5] and Pointer[1..5]. Current state: StartPointer = 1, FreePointer = 4. Data[1] = 'A', Pointer[1] = 3; Data[3] = 'C', Pointer[3] = -1. Insert 'B' between 'A' and 'C'.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) Describe the state of the FrontPointer and RearPointer after a DEQUEUE operation is performed. [2] (b) Describe the state of the FrontPointer and RearPointer after an ENQUEUE operation is performed. [2] [4 marks]
Worked example
A circular queue uses an array Queue[1:5]. Front = 4, Rear = 5, Count = 2. Show the pointer values after: enqueue "X", enqueue "Y", dequeue.
🔍 Worked example — Easy
A queue is implemented using an array Queue[1:5]. Currently, the queue contains 2 items: Queue[1] = "A" and Queue[2] = "B". The Front pointer is 1 and the Rear pointer is 2. Perform the following operations: 1. Enqueue "C", 2. Dequeue.
🔍 Worked example — Standard
A queue is implemented using an array Queue[1:5]. Current state: Front = 4, Rear = 5, Count = 2. The items are Queue[4] = "P" and Queue[5] = "Q". Perform: 1. Enqueue "R", 2. Enqueue "S", 3. Dequeue.
🔍 Worked example — Exam-style
Write pseudocode to perform a Dequeue operation on a circular queue Queue[1:5] where Front, Rear, and Count are integers. Assume the queue is not empty.
⚠️ Common errors
Common mistakes
Practice
Answers: (1) (a) DATE; (b) BOOLEAN; (c) STRING; (d) REAL. (2) TYPE TBook / DECLARE ISBN : STRING / DECLARE Title : STRING / DECLARE Price : REAL / DECLARE OnLoan : BOOLEAN / ENDTYPE / DECLARE Book : TBook / Book.Title ← "Dune". (3) Lower bound 0, upper bound 9, 10 elements. (4) If a complete pass makes no swaps, every adjacent pair is in order, so the array is sorted and no more passes are needed. (5) Count ← 0 / OPENFILE "Log.txt" FOR READ / WHILE NOT EOF("Log.txt") / READFILE "Log.txt", Line / Count ← Count + 1 / ENDWHILE / CLOSEFILE "Log.txt" / OUTPUT Count. (6) Pop returns 30 (stack 10, 20); push 40 (10, 20, 40); push 50 (10, 20, 40, 50); pop returns 50 (stack 10, 20, 40).