A Level Computer Science Paper 3
Covers Linear Data Structures, Trees and Graphs, Searching and Sorting Algorithms and 9 more.
Questions
Question 1 [1 mark]
Boolean Algebra and Logic Gates
A logic circuit implements the Boolean expression X = (A AND B) OR (NOT C).
Evaluate X when A = 1, B = 0 and C = 0.
Question 2 [3 marks]
Linear Data Structures
A queue is a linear data structure that follows First In First Out (FIFO).
The following operations are performed on an empty queue: enqueue(A), enqueue(B), enqueue(C), dequeue(), enqueue(D).
State the contents of the queue, from front to back, after these operations.
Question 3 [3 marks]
Databases and SQL
The Student table has columns StudentID, FirstName, LastName and YearGroup.
Write an SQL statement to select the FirstName and LastName of all students whose LastName begins with the letter 'S'.
Question 4 [4 marks]
Searching and Sorting Algorithms
A binary search repeatedly checks the middle element of a list and decides whether to search the left or right half based on whether the middle value is smaller or larger than the target.
Explain why a binary search requires the list to be sorted, and state what could go wrong if it is used on an unsorted list.
Question 5 [4 marks]
Programming Paradigms
Prolog is a logic programming language in which a program consists of facts and rules, and a query asks the system to find values that satisfy them.
State what is meant by logic programming, and give one example each of a fact and a rule that might appear in a simple Prolog program about family relationships.
Question 6 [4 marks]
Theory of Computation
A grammar in Backus-Naur Form defines a symbol <S> as follows: <S> ::= a <S> b | ab
Show how the string 'aabb' can be derived from <S> using this grammar, and explain why this grammar can never generate the string 'aab' (with an unequal number of a's and b's).
Question 7 [4 marks]
Programming: Trace, Write and Explain
Write pseudocode for a function called IsPalindrome that takes a string, s, as its parameter, and returns TRUE if s reads the same forwards and backwards, and FALSE otherwise. You may assume a function LEN(s) returns the length of s, and that individual characters of s can be accessed using s[i], indexed from 0.
Question 8 [4 marks]
Algorithmic Complexity
A recursive function to compute factorial(n) calls itself n times before returning, with each call adding a new stack frame.
An iterative version uses a single loop and one accumulator variable.
State the space complexity of each version, in terms of n, and explain the difference. Use auxiliary space, assume fixed-size arithmetic, and assume recursive stack frames are retained without tail-call elimination.
Question 9 [4 marks]
Data Representation
Two 8-bit unsigned binary numbers, 11001101 and 00111010, are added together using binary addition.
Show the result of the addition, and state whether an overflow has occurred, given that an 8-bit unsigned number can hold values from 0 to 255.
Question 10 [4 marks]
Computer Architecture and the CPU
A simplified processor executes the following sequence of instructions, where ACC is the accumulator register, and JUMPIFZERO n jumps execution to address n only if ACC currently holds 0:
LOAD 20 ; SUB 21 ; JUMPIFZERO 40 ; ADD 22
Address 20 holds 15, address 21 holds 15, and address 22 holds 9. State the value in ACC after LOAD and after SUB, state whether the jump is taken, and state the value of ACC immediately after the jump decision, before executing any instruction at its destination.
Question 11 [5 marks]
Trees and Graphs
A graph has vertices W, X, Y, Z with undirected edges W-X, W-Z, X-Y, Y-Z.
An adjacency matrix represents a graph as a grid where a 1 in row P column Q means an edge exists between P and Q, and a 0 means no edge.
State the value in the adjacency matrix for the pairs (W, Y) and (X, Z), and explain why an adjacency matrix for an undirected graph is always symmetrical about its diagonal.
Question 12 [6 marks]
Searching and Sorting Algorithms
An optimised bubble sort stops early if a complete pass makes no swaps, since this means the list is already sorted.
The list [3, 8, 12, 19, 25] is sorted using this optimised bubble sort.
State what happens during the first pass, state whether a second pass is needed, and explain why this gives bubble sort a best-case time complexity of O(n) rather than O(n^2).
Question 13 [4 marks]
Networks and Communication
A packet-filtering firewall examines each packet's header, such as its source and destination IP address and port number, and allows or blocks it based on a set of rules, without looking at the actual data (payload) it carries.
An application-level (proxy) firewall instead inspects the actual content of the traffic for a specific application, such as checking the content of web pages being requested. Assume the application content is available to the proxy for inspection.
Explain one advantage the application-level firewall has over the packet-filtering firewall, and one disadvantage.
Question 14 [6 marks]
Algorithmic Complexity
An algorithm is timed on inputs of different sizes: n = 10 takes 1 ms, n = 100 takes 100 ms, and n = 1000 takes 10000 ms.
Using this pattern, identify which of O(n), O(n log n) and O(n^2) best matches the algorithm's growth, showing your reasoning, and state one limitation of judging time complexity from timings like these rather than from the algorithm's structure.
Question 15 [4 marks]
Networks and Communication
A website uses HTTPS, which relies on encryption to protect data sent between a browser and the server.
Explain the difference between symmetric and asymmetric encryption, and state why a combination of both is often used when establishing a secure connection.
Model solutions
| Question 1[1 mark] | |
|---|---|
| Answer or working | Marks |
| X = 1; correct output alone earns full credit | A1 |
| Final answer: X = 1. | |
| Question 2[3 marks] | |
|---|---|
| Answer or working | Marks |
| enqueuing A, B and C to give the order A, B, C from front to back | M1 |
| dequeue() removing A from the front, leaving B, C | M1 |
| enqueue(D) giving the final order B, C, D Award all 3 marks for the complete correct requested answer: Front to back: B, C, D. 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: Front to back: B, C, D. | |
| Question 3[3 marks] | |
|---|---|
| Answer or working | Marks |
| selecting FirstName and LastName | M1 |
| selecting from Student | M1 |
| selecting surnames beginning with S, using LIKE with S% or an equivalent valid predicate including an empty suffix | A1 |
| Final answer: SELECT FirstName, LastName FROM Student WHERE LastName LIKE 'S%'; | |
| Question 4[4 marks] | |
|---|---|
| Answer or working | Marks |
| explaining a binary search decides which half to search next by comparing the target with the middle value, assuming every value on one side is smaller and every value on the other side is larger | B1 |
| stating this assumption only holds if the list is sorted | B1 |
| explaining that on an unsorted list, the target could lie in the half that gets discarded | B1 |
| stating the search could then incorrectly report the target is not present, even though it is actually in the list | B1 |
| Final answer: Binary search assumes one side of the middle is all smaller and the other all larger, which only holds when sorted; on an unsorted list it could discard the half containing the target and wrongly report it missing | |
| Question 5[4 marks] | |
|---|---|
| Answer or working | Marks |
| defining logic programming through facts and rules and answering queries by inference: B1 for facts/rules and B1 for query solving This row begins a shared allocation of 2 marks for the same requested result or explanation. | B1 |
| mark 2 of the same 2-mark allocation above. A complete response meeting that allocation earns every mark in the group; this row adds no separate requirement. Retain the partial-credit guidance stated in the first row of the group. | B1 |
| one valid family-relationship fact, such as parent(alice,bob). | B1 |
| one valid family-relationship rule, such as grandparent(X,Z) :- parent(X,Y), parent(Y,Z). No further declarative-versus-imperative comparison is required. | B1 |
| Final answer: Logic programming expresses facts and rules and answers queries by inference, e.g. fact parent(mary, sam); rule grandparent(X, Y) :- parent(X, Z), parent(Z, Y) | |
| Question 6[4 marks] | |
|---|---|
| Answer or working | Marks |
| the first derivation step, <S> -> a <S> b | M1 |
| substituting the second rule for the inner <S>, giving a ab b, which is aabb | A1 |
| explaining every use of the first rule adds exactly one a and one b, one at each end, and the second rule (the only way to stop) adds one more a and one more b | B1 |
| concluding every string this grammar generates must therefore contain an equal number of a's and b's, so 'aab', with 2 a's and 1 b, can never be generated | B1 |
| Final answer: aabb: <S> -> a<S>b -> a(ab)b = aabb. Every rule adds equal a's and b's, so a string with unequal counts, like 'aab', can never be generated | |
| Question 7[4 marks] | |
|---|---|
| Answer or working | Marks |
| IsPalindrome with parameter s | M1 |
| comparing mirrored characters, or an equivalent comparison with the reversed string | M1 |
| returning FALSE when any corresponding characters differ | A1 |
| returning TRUE when all corresponding characters match; accept equivalent algorithms without requiring early return or a midpoint bound | A1 |
| Final answer: FUNCTION IsPalindrome(s) left = 0 right = LEN(s) - 1 WHILE left < right IF s[left] != s[right] THEN RETURN FALSE ENDIF left = left + 1 right = right - 1 ENDWHILE RETURN TRUE ENDFUNCTION | |
| Question 8[4 marks] | |
|---|---|
| Answer or working | Marks |
| stating the recursive version has space complexity O(n) | B1 |
| explaining this is because each recursive call adds a stack frame that remains until the call returns | B1 |
| stating the iterative version has space complexity O(1) | B1 |
| explaining this is because it reuses the same variables on each loop iteration rather than growing the call stack | B1 |
| Final answer: Recursive: O(n) because each call adds a stack frame; iterative: O(1) because it reuses the same variables | |
| Question 9[4 marks] | |
|---|---|
| Answer or working | Marks |
| converting each operand to denary (or working directly in binary): 205 and 58 | M1 |
| correctly computing the sum as 263 | M1 |
| binary 100000111; accept 00000111 with carry-out 1 as an equivalent representation of the full sum. | A1 |
| stating that an overflow has therefore occurred | A1 |
| Final answer: 205 + 58 = 263, needing 9 bits; this overflows an 8-bit register, which would incorrectly hold 00000111 (7) | |
| Question 10[4 marks] | |
|---|---|
| Answer or working | Marks |
| ACC = 15 after LOAD 20 | M1 |
| ACC = 0 after SUB 21 | M1 |
| the jump being taken, since ACC = 0 at that point | A1 |
| ACC = 0 immediately after the jump decision, before any instruction at address 40 executes. | A1 |
| Final answer: ACC = 15 after LOAD; 0 after SUB; jump taken; ACC remains 0 immediately after the jump decision. | |
| Question 11[5 marks] | |
|---|---|
| Answer or working | Marks |
| identifying no edge exists between W and Y | M1 |
| the adjacency matrix entry for (W, Y) being 0 | A1 |
| identifying no edge exists between X and Z | M1 |
| the adjacency matrix entry for (X, Z) being 0 | A1 |
| explaining the matrix is symmetrical because an undirected edge P-Q means Q-P also exists, so the entry at [P][Q] always matches [Q][P] 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. Both entries and a reason for symmetry are requested. Absence of each edge is directly evidenced by its zero entry. | B1 |
| Final answer: (W,Y)=0 and (X,Z)=0. In an undirected graph an edge P-Q is also the connection Q-P, so matrix entries at row P column Q and row Q column P are equal. | |
| Question 12[6 marks] | |
|---|---|
| Answer or working | Marks |
| comparing each adjacent pair in turn during the first pass: 3&8, 8&12, 12&19, 19&25 | M1 |
| stating no swaps occur during the first pass, since the list is already in order | A1 |
| stating a second pass is not needed, because the optimisation detects no swaps were made | A1 |
| stating this means only one pass of comparisons was performed | B1 |
| explaining a single pass over the whole list is O(n) | B1 |
| explaining this is the best case, since an unsorted list would typically need close to n passes, giving the usual O(n^2) Award all 6 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. The first pass, stopping decision and best-case explanation are all requested. Typical unsorted behaviour should not be required in addition to explaining the linear best case. | B1 |
| Final answer: First pass compares 3/8, 8/12, 12/19 and 19/25, making no swaps. No second pass is needed. One pass uses n-1 adjacent comparisons, so best-case time is O(n). | |
| Question 13[4 marks] | |
|---|---|
| Answer or working | Marks |
| one valid advantage over header filtering, such as blocking malicious content within otherwise permitted traffic or enforcing application-specific content rules. | B1 |
| explaining how inspection of application content enables the stated advantage beyond what header-only rules can distinguish. | B1 |
| one valid disadvantage, such as increased latency, reduced throughput or greater configuration and maintenance complexity. | B1 |
| explaining the chosen disadvantage: deeper inspection consumes processing time, or application-specific parsers and rules require more setup and maintenance. Accept another valid linked explanation; neither route is compulsory. | B1 |
| Final answer: A proxy can block malicious payloads that pass header rules. It needs application-specific parsers and rules, increasing configuration and maintenance complexity; alternatively, deeper processing can add delay. | |
| Question 14[6 marks] | |
|---|---|
| Answer or working | Marks |
| explaining the quadratic timing pattern, either by the factor-10 input and factor-100 time changes or by showing that t/n^2 is constant (0.01 ms) across all samples. Either complete method earns all three marks; separate ratio statements are not required when using the constant-quotient method. Award up to M2 for correct incomplete pattern reasoning. This row begins a shared allocation of 3 marks for the same requested result or explanation. | M1 |
| mark 2 of the same 3-mark allocation above. A complete response meeting that allocation earns every mark in the group; this row adds no separate requirement. Retain the partial-credit guidance stated in the first row of the group. | M1 |
| mark 3 of the same 3-mark allocation above. A complete response meeting that allocation earns every mark in the group; this row adds no separate requirement. Retain the partial-credit guidance stated in the first row of the group. | M1 |
| selecting O(n^2) as the best fit | A1 |
| stating one valid limitation, such as timings depending on hardware or particular inputs; no second limitation or separate explanation is required This row begins a shared allocation of 2 marks for the same requested result or explanation. | B1 |
| mark 2 of the same 2-mark allocation above. A complete response meeting that allocation earns every mark in the group; this row adds no separate requirement. Retain the partial-credit guidance stated in the first row of the group. | B1 |
| Final answer: O(n^2): a 10x increase in n gives a 100x increase in time, matching (10n)^2 = 100n^2. Limitation: timings depend on hardware/inputs and are not a guaranteed bound | |
| Question 15[4 marks] | |
|---|---|
| Answer or working | Marks |
| symmetric encryption using a shared secret key. | B1 |
| asymmetric cryptography using a related public/private key pair with the private key kept secret. | B1 |
| public-key mechanisms allowing secure establishment of shared session keys, with authentication; accept the simplified public-key transport example without requiring it as the only mechanism. | B1 |
| symmetric encryption being efficient for bulk data transfer. | B1 |
| Final answer: Symmetric uses a shared secret; asymmetric uses a related public/private pair; establish keys securely then use efficient symmetric bulk encryption | |