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 3

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

15 questions - 60 marks

Download PDF

Open A Level Computer Science workspace

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

Mark scheme for Question 1 [1 mark]
Question 1[1 mark]
Answer or workingMarks
X = 1; correct output alone earns full creditA1
Final answer: X = 1.
Mark scheme for Question 2 [3 marks]
Question 2[3 marks]
Answer or workingMarks
enqueuing A, B and C to give the order A, B, C from front to backM1
dequeue() removing A from the front, leaving B, CM1
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.
Mark scheme for Question 3 [3 marks]
Question 3[3 marks]
Answer or workingMarks
selecting FirstName and LastNameM1
selecting from StudentM1
selecting surnames beginning with S, using LIKE with S% or an equivalent valid predicate including an empty suffixA1
Final answer: SELECT FirstName, LastName FROM Student WHERE LastName LIKE 'S%';
Mark scheme for Question 4 [4 marks]
Question 4[4 marks]
Answer or workingMarks
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 largerB1
stating this assumption only holds if the list is sortedB1
explaining that on an unsorted list, the target could lie in the half that gets discardedB1
stating the search could then incorrectly report the target is not present, even though it is actually in the listB1
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
Mark scheme for Question 5 [4 marks]
Question 5[4 marks]
Answer or workingMarks
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)
Mark scheme for Question 6 [4 marks]
Question 6[4 marks]
Answer or workingMarks
the first derivation step, <S> -> a <S> bM1
substituting the second rule for the inner <S>, giving a ab b, which is aabbA1
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 bB1
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 generatedB1
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
Mark scheme for Question 7 [4 marks]
Question 7[4 marks]
Answer or workingMarks
IsPalindrome with parameter sM1
comparing mirrored characters, or an equivalent comparison with the reversed stringM1
returning FALSE when any corresponding characters differA1
returning TRUE when all corresponding characters match; accept equivalent algorithms without requiring early return or a midpoint boundA1
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
Mark scheme for Question 8 [4 marks]
Question 8[4 marks]
Answer or workingMarks
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 returnsB1
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 stackB1
Final answer: Recursive: O(n) because each call adds a stack frame; iterative: O(1) because it reuses the same variables
Mark scheme for Question 9 [4 marks]
Question 9[4 marks]
Answer or workingMarks
converting each operand to denary (or working directly in binary): 205 and 58M1
correctly computing the sum as 263M1
binary 100000111; accept 00000111 with carry-out 1 as an equivalent representation of the full sum.A1
stating that an overflow has therefore occurredA1
Final answer: 205 + 58 = 263, needing 9 bits; this overflows an 8-bit register, which would incorrectly hold 00000111 (7)
Mark scheme for Question 10 [4 marks]
Question 10[4 marks]
Answer or workingMarks
ACC = 15 after LOAD 20M1
ACC = 0 after SUB 21M1
the jump being taken, since ACC = 0 at that pointA1
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.
Mark scheme for Question 11 [5 marks]
Question 11[5 marks]
Answer or workingMarks
identifying no edge exists between W and YM1
the adjacency matrix entry for (W, Y) being 0A1
identifying no edge exists between X and ZM1
the adjacency matrix entry for (X, Z) being 0A1
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.
Mark scheme for Question 12 [6 marks]
Question 12[6 marks]
Answer or workingMarks
comparing each adjacent pair in turn during the first pass: 3&8, 8&12, 12&19, 19&25M1
stating no swaps occur during the first pass, since the list is already in orderA1
stating a second pass is not needed, because the optimisation detects no swaps were madeA1
stating this means only one pass of comparisons was performedB1
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).
Mark scheme for Question 13 [4 marks]
Question 13[4 marks]
Answer or workingMarks
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.
Mark scheme for Question 14 [6 marks]
Question 14[6 marks]
Answer or workingMarks
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 fitA1
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
Mark scheme for Question 15 [4 marks]
Question 15[4 marks]
Answer or workingMarks
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

Build a free practice pack.

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