Revision Library
Choose a subject
Menu
Computer Science
Need a new topic?
Missing a topic, found a bug, or want something added?

A Level Computer Science Paper 4

Covers Linear Data Structures, Trees and Graphs, Searching and Sorting Algorithms and 9 more.

16 questions - 60 marks

Download PDF

Open A Level Computer Science workspace

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

Mark scheme for Question 1 [2 marks]
Question 1[2 marks]
Answer or workingMarks
a valid LAN example, such as the network inside a single school or office buildingB1
a valid WAN example, such as the internet, or a company's network connecting offices in different citiesB1
Final answer: LAN example: a school's internal network; WAN example: the internet
Mark scheme for Question 2 [3 marks]
Question 2[3 marks]
Answer or workingMarks
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.
Mark scheme for Question 3 [3 marks]
Question 3[3 marks]
Answer or workingMarks
selecting FirstName and LastName, accepting aliases and equivalent projection syntaxM1
selecting from StudentM1
restricting the result to YearGroup = 12 in a complete valid statementA1
Final answer: SELECT FirstName, LastName FROM Student WHERE YearGroup = 12;
Mark scheme for Question 4 [3 marks]
Question 4[3 marks]
Answer or workingMarks
bundling an object's data with its operationsB1
controlling access to internal state through an interface rather than unrestricted direct changesB1
one valid benefit, such as protecting invariants or changing representation without changing callers; do not require a second benefitB1
Final answer: Encapsulation hides an object's data behind its methods, e.g. protecting data from invalid direct changes
Mark scheme for Question 5 [4 marks]
Question 5[4 marks]
Answer or workingMarks
converting 200 to hexadecimal by finding 200 = 12 x 16 + 8M1
hexadecimal C8 (12 = C, 8 = 8)A1
converting 200 to binary by summing place values 128 + 64 + 8M1
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
Mark scheme for Question 6 [3 marks]
Question 6[3 marks]
Answer or workingMarks
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 timeB1
a valid comparison, such as binary search needing at most around 20 comparisons, against up to 1,000,000 for linear searchB1
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
Mark scheme for Question 7 [3 marks]
Question 7[3 marks]
Answer or workingMarks
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.
Mark scheme for Question 8 [3 marks]
Question 8[3 marks]
Answer or workingMarks
the labelled equal-input XOR rows 00 -> 0 and 11 -> 0B1
the labelled unequal-input rows 01 -> 1 and 10 -> 1B1
an equivalent expression using only AND, OR and NOT, such as (A AND NOT B) OR (NOT A AND B); accept any valid equivalent constructionA1
Final answer: 00 -> 0; 01 -> 1; 10 -> 1; 11 -> 0. X = (A AND (NOT B)) OR ((NOT A) AND B).
Mark scheme for Question 9 [3 marks]
Question 9[3 marks]
Answer or workingMarks
Classify(14) = big evenA1
Classify(4) = small evenA1
Classify(7) = oddA1
Final answer: Classify(14) = big even; Classify(4) = small even; Classify(7) = odd.
Mark scheme for Question 10 [4 marks]
Question 10[4 marks]
Answer or workingMarks
SUM = A XOR B or an equivalent expressionB1
identifying the SUM gate as XORB1
CARRY = A AND B or an equivalent expressionB1
identifying the CARRY gate as ANDB1
Final answer: SUM = A XOR B (XOR gate); CARRY = A AND B (AND gate).
Mark scheme for Question 11 [4 marks]
Question 11[4 marks]
Answer or workingMarks
a regular expression starting with 1M1
the middle section allowing any combination of 0s and 1s, such as (0|1)*M1
the complete expression 1(0|1)*0, ending in 0A1
confirming '100' matches, since it starts with 1, has a single 0 in the middle section, and ends with 0B1
Final answer: 1(0|1)*0; '100' matches, since it starts with 1, ends with 0, with '0' as the middle section
Mark scheme for Question 12 [5 marks]
Question 12[5 marks]
Answer or workingMarks
identifying the minimum of the whole list, 1, in pass one, and swapping it into index 0M1
the list reading 1, 2, 8, 6 after pass oneA1
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 occursM1
the list remaining 1, 2, 8, 6 after pass twoA1
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].
Mark scheme for Question 13 [2 marks]
Question 13[2 marks]
Answer or workingMarks
showing valid laws for a complete simplification, such as distributivity, complementarity and identity; accept any valid derivationM1
Y = AA1
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.
Mark scheme for Question 14 [6 marks]
Question 14[6 marks]
Answer or workingMarks
20 inserted as the left child of 40, and 60 as the right child of 40M1
10 inserted as the left child of 20, following the path 40 then 20M1
25 inserted as the right child of 20, following the path 40 then 20M1
5 inserted as the left child of 10, following the path 40, 20, then 10A1
identifying the longest root-to-leaf path as 40, 20, 10, 5M1
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.
Mark scheme for Question 15 [6 marks]
Question 15[6 marks]
Answer or workingMarks
total pixels = 500 x 500 = 250000M1
total bits = 250000 x 24 = 6000000M1
converting bits to bytes by dividing by 8M1
750000 bytesA1
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 pixelsB1
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 shapesB1
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
Mark scheme for Question 16 [6 marks]
Question 16[6 marks]
Answer or workingMarks
identifying one membership check for each of n transactionsM1
O(nm) worst-case list processingA1
O(n) average hash-set processing, with storage already builtA1
multiplying n by each membership costB1
explaining that list checks grow with m but average hash checks stay constant under the stated assumptionB1
linking this increasing per-check gap to its repetition across all n transactions; accept O(n+m) if explicitly including expected hash-set constructionB1
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

Build a free practice pack.

Pick the topics, add the student's name and print one PDF.