A Level Computer Science Paper 4
Covers Linear Data Structures, Trees and Graphs, Searching and Sorting Algorithms and 9 more.
Questions
Question 1 [2 marks]
Networks and Communication
A LAN (Local Area Network) covers a small geographical area, such as a single building. A WAN (Wide Area Network) covers a much larger geographical area, such as a whole country or the world.
Give one example of a LAN and one example of a WAN.
Question 2 [3 marks]
Linear Data Structures
A stack supports push(), pop(), peek() (which returns the top value without removing it) and isEmpty().
The following operations are performed on an empty stack: push(6), push(2), peek(), pop(), isEmpty().
State the value returned by peek(), the value returned by pop(), and the value returned by isEmpty().
Question 3 [3 marks]
Databases and SQL
A database table Student has columns StudentID, FirstName, LastName and YearGroup.
Write an SQL statement to select the FirstName and LastName of all students in YearGroup 12.
Question 4 [3 marks]
Programming Paradigms
Object-oriented programming groups data and the methods that act on it into objects created from classes.
Explain what is meant by encapsulation, and state one benefit it gives to a program.
Question 5 [4 marks]
Data Representation
Convert the denary number 200 into hexadecimal, and then into an 8-bit unsigned binary number.
Question 6 [3 marks]
Algorithmic Complexity
A linear search and a binary search are both available to search a sorted list of 1,000,000 items.
Explain why a binary search is more efficient than a linear search for this list, referring to their time complexities.
Question 7 [3 marks]
Computer Architecture and the CPU
A company is choosing between a processor with 1 core running at 4.0 GHz and a processor with 4 cores each running at 2.0 GHz, for a program that needs to process a large batch of independent image files. Assume comparable work per clock cycle, enough independent files to keep all cores busy, and negligible scheduling and I/O overheads.
State which processor is likely to complete the batch faster, and explain why, referring to the nature of the task.
Question 8 [3 marks]
Boolean Algebra and Logic Gates
The XOR (exclusive OR) gate outputs 1 only when its two inputs are different from each other.
Write the truth table for X = A XOR B for all four combinations of A and B, and write an equivalent expression for X using only AND, OR and NOT.
Question 9 [3 marks]
Programming: Trace, Write and Explain
The following function is defined:
FUNCTION Classify(n): IF n MOD 2 = 0 THEN (IF n > 10 THEN RETURN 'big even' ELSE RETURN 'small even' ENDIF) ELSE RETURN 'odd' ENDIF ENDFUNCTION
State the value returned by Classify(14), Classify(4) and Classify(7).
Question 10 [4 marks]
Boolean Algebra and Logic Gates
A half adder is a circuit that adds two single binary digits, A and B, producing a SUM output and a CARRY output.
State the Boolean expression for SUM and for CARRY in terms of A and B, and identify which standard logic gate each expression corresponds to.
Question 11 [4 marks]
Theory of Computation
Write a regular expression that matches exactly the binary strings that start with a 1 and end with a 0, with any combination of 0s and 1s (including none) in between.
State, with a reason, whether your regular expression matches the string '100'.
Question 12 [5 marks]
Searching and Sorting Algorithms
The list [6, 2, 8, 1] is sorted using selection sort, which repeatedly finds the minimum value in the unsorted part of the list and swaps it into the correct position, working from the start of the list.
Show the contents of the list after each of the three passes needed to fully sort a 4-element list.
Question 13 [2 marks]
Boolean Algebra and Logic Gates
Simplify the Boolean expression Y = (A OR B) AND (A OR (NOT B)), showing each law used.
Question 14 [6 marks]
Trees and Graphs
A binary search tree is built by inserting values one at a time into an initially empty tree, in this order: 40, 20, 60, 10, 25, 5.
State each inserted node's parent and whether it is a left or right child, then state the height of the tree, where a single root node alone has height 0.
Question 15 [6 marks]
Data Representation
A company must store a logo made of solid coloured shapes. Two options are considered: a bitmap image at 500 by 500 pixels with a colour depth of 24 bits, or a vector image described by a small number of shape coordinates and fill colours.
Calculate the file size, in bytes, of the uncompressed bitmap version.
Explain one reason the vector version would likely be far smaller, and state one situation in which a bitmap would be a better choice than a vector image.
Question 16 [6 marks]
Algorithmic Complexity
A program must process a list of n transactions. For every transaction, it needs to check whether the customer's account number appears in a separate list of m frozen accounts.
If the frozen accounts are stored in an unsorted list, each check is a linear search, O(m). If they are instead stored in a hash set, each check is O(1) on average.
State the overall time complexity of processing all n transactions for each storage choice, in terms of n and m, and explain why the difference matters more as m grows large. Analyse membership checks with each storage structure already built; state explicitly if you include construction.
Model solutions
| Question 1[2 marks] | |
|---|---|
| Answer or working | Marks |
| a valid LAN example, such as the network inside a single school or office building | B1 |
| a valid WAN example, such as the internet, or a company's network connecting offices in different cities | B1 |
| Final answer: LAN example: a school's internal network; WAN example: the internet | |
| Question 2[3 marks] | |
|---|---|
| Answer or working | Marks |
| peek() returning 2. | A1 |
| pop() returning 2. | A1 |
| isEmpty() returning false. | A1 |
| Final answer: peek returns 2; pop returns 2; isEmpty returns false because 6 remains. | |
| Question 3[3 marks] | |
|---|---|
| Answer or working | Marks |
| selecting FirstName and LastName, accepting aliases and equivalent projection syntax | M1 |
| selecting from Student | M1 |
| restricting the result to YearGroup = 12 in a complete valid statement | A1 |
| Final answer: SELECT FirstName, LastName FROM Student WHERE YearGroup = 12; | |
| Question 4[3 marks] | |
|---|---|
| Answer or working | Marks |
| bundling an object's data with its operations | B1 |
| controlling access to internal state through an interface rather than unrestricted direct changes | B1 |
| one valid benefit, such as protecting invariants or changing representation without changing callers; do not require a second benefit | B1 |
| Final answer: Encapsulation hides an object's data behind its methods, e.g. protecting data from invalid direct changes | |
| Question 5[4 marks] | |
|---|---|
| Answer or working | Marks |
| converting 200 to hexadecimal by finding 200 = 12 x 16 + 8 | M1 |
| hexadecimal C8 (12 = C, 8 = 8) | A1 |
| converting 200 to binary by summing place values 128 + 64 + 8 | M1 |
| 8-bit binary 11001000 Award equivalent credit for another valid complete conversion method; the particular listed route is not compulsory. | A1 |
| Final answer: Hexadecimal C8, binary 11001000 | |
| Question 6[3 marks] | |
|---|---|
| Answer or working | Marks |
| stating linear search is O(n) and binary search is O(log n) | B1 |
| explaining binary search halves the search space at each step, rather than checking one element at a time | B1 |
| a valid comparison, such as binary search needing at most around 20 comparisons, against up to 1,000,000 for linear search | B1 |
| Final answer: Binary search is O(log n) against linear search's O(n): it halves the remaining list each step, so far fewer comparisons are needed for a large list | |
| Question 7[3 marks] | |
|---|---|
| Answer or working | Marks |
| choosing the four-core 2.0 GHz processor under the printed assumptions. | B1 |
| explaining that independent image files can be processed simultaneously on different cores. | B1 |
| explaining that the extra parallel work outweighs the lower per-core clock speed; accept a qualitative comparison or 4 * 2.0 versus 1 * 4.0. A calculated ratio is not required. | B1 |
| Final answer: Four-core 2.0 GHz processor; ideal aggregate throughput is twice that of the single 4.0 GHz core under the printed assumptions. | |
| Question 8[3 marks] | |
|---|---|
| Answer or working | Marks |
| the labelled equal-input XOR rows 00 -> 0 and 11 -> 0 | B1 |
| the labelled unequal-input rows 01 -> 1 and 10 -> 1 | B1 |
| an equivalent expression using only AND, OR and NOT, such as (A AND NOT B) OR (NOT A AND B); accept any valid equivalent construction | A1 |
| Final answer: 00 -> 0; 01 -> 1; 10 -> 1; 11 -> 0. X = (A AND (NOT B)) OR ((NOT A) AND B). | |
| Question 9[3 marks] | |
|---|---|
| Answer or working | Marks |
| Classify(14) = big even | A1 |
| Classify(4) = small even | A1 |
| Classify(7) = odd | A1 |
| Final answer: Classify(14) = big even; Classify(4) = small even; Classify(7) = odd. | |
| Question 10[4 marks] | |
|---|---|
| Answer or working | Marks |
| SUM = A XOR B or an equivalent expression | B1 |
| identifying the SUM gate as XOR | B1 |
| CARRY = A AND B or an equivalent expression | B1 |
| identifying the CARRY gate as AND | B1 |
| Final answer: SUM = A XOR B (XOR gate); CARRY = A AND B (AND gate). | |
| Question 11[4 marks] | |
|---|---|
| Answer or working | Marks |
| a regular expression starting with 1 | M1 |
| the middle section allowing any combination of 0s and 1s, such as (0|1)* | M1 |
| the complete expression 1(0|1)*0, ending in 0 | A1 |
| confirming '100' matches, since it starts with 1, has a single 0 in the middle section, and ends with 0 | B1 |
| Final answer: 1(0|1)*0; '100' matches, since it starts with 1, ends with 0, with '0' as the middle section | |
| Question 12[5 marks] | |
|---|---|
| Answer or working | Marks |
| identifying the minimum of the whole list, 1, in pass one, and swapping it into index 0 | M1 |
| the list reading 1, 2, 8, 6 after pass one | A1 |
| identifying the minimum of the remaining unsorted part (2, 8, 6) as 2, which is already in its correct position (index 1), so no swap occurs | M1 |
| the list remaining 1, 2, 8, 6 after pass two | A1 |
| pass three swapping the minimum of the last two elements, 6, into index 2, giving the fully sorted list 1, 2, 6, 8 Award all 5 marks for a complete correct answer to the requested task. Accept equivalent valid explanations and notation. Method details not explicitly requested may be inferred from the correct requested results. All three pass states are requested; finding minima and describing self-swaps are optional working. Award all 5 marks for the complete correct requested answer: Pass 1: [1,2,8,6]. Pass 2: [1,2,8,6]. Pass 3: [1,2,6,8]. Accept equivalent valid notation and explanations. Intermediate method evidence below is optional and may be inferred from a correct requested result; do not require unasked states or extra explanations. | A1 |
| Final answer: Pass 1: [1,2,8,6]. Pass 2: [1,2,8,6]. Pass 3: [1,2,6,8]. | |
| Question 13[2 marks] | |
|---|---|
| Answer or working | Marks |
| showing valid laws for a complete simplification, such as distributivity, complementarity and identity; accept any valid derivation | M1 |
| Y = A | A1 |
| Final answer: Y = A. Dual distributivity gives A OR (B AND NOT B). Complementarity gives B AND NOT B = 0. Identity gives A OR 0 = A. | |
| Question 14[6 marks] | |
|---|---|
| Answer or working | Marks |
| 20 inserted as the left child of 40, and 60 as the right child of 40 | M1 |
| 10 inserted as the left child of 20, following the path 40 then 20 | M1 |
| 25 inserted as the right child of 20, following the path 40 then 20 | M1 |
| 5 inserted as the left child of 10, following the path 40, 20, then 10 | A1 |
| identifying the longest root-to-leaf path as 40, 20, 10, 5 | M1 |
| stating the height of the tree is 3 Award all 6 marks for the complete correct requested answer: 40 is the root (no parent); 20 is left of 40; 60 is right of 40; 10 is left of 20; 25 is right of 20; 5 is left of 10. Height is 3 edges. Accept equivalent valid notation and explanations. Intermediate method evidence below is optional and may be inferred from a correct requested result; do not require unasked states or extra explanations. | A1 |
| Final answer: 40 is the root (no parent); 20 is left of 40; 60 is right of 40; 10 is left of 20; 25 is right of 20; 5 is left of 10. Height is 3 edges. | |
| Question 15[6 marks] | |
|---|---|
| Answer or working | Marks |
| total pixels = 500 x 500 = 250000 | M1 |
| total bits = 250000 x 24 = 6000000 | M1 |
| converting bits to bytes by dividing by 8 | M1 |
| 750000 bytes | A1 |
| explaining the vector version only needs to store a small number of coordinates and colours describing the shapes, rather than a colour value for every one of the 250000 pixels | B1 |
| a valid situation favouring a bitmap, such as storing a photograph, where colour varies continuously and cannot be described as a small number of simple shapes | B1 |
| Final answer: 750000 bytes; the vector stores only shape coordinates and colours rather than every pixel, so it is much smaller for simple designs; a bitmap suits photographs, where colour varies continuously | |
| Question 16[6 marks] | |
|---|---|
| Answer or working | Marks |
| identifying one membership check for each of n transactions | M1 |
| O(nm) worst-case list processing | A1 |
| O(n) average hash-set processing, with storage already built | A1 |
| multiplying n by each membership cost | B1 |
| explaining that list checks grow with m but average hash checks stay constant under the stated assumption | B1 |
| linking this increasing per-check gap to its repetition across all n transactions; accept O(n+m) if explicitly including expected hash-set construction | B1 |
| Final answer: Unsorted list: O(n x m); hash set: O(n). The gap widens as m grows, since every lookup gets slower with the list but stays constant with the hash set | |