A Level Computer Science Paper 2
Covers Linear Data Structures, Trees and Graphs, Searching and Sorting Algorithms and 9 more.
Questions
Question 1 [2 marks]
Boolean Algebra and Logic Gates
State the output of the logic expression A AND B for each of the four possible combinations of A and B (each 0 or 1).
Question 2 [2 marks]
Searching and Sorting Algorithms
The sorted list [3, 7, 12, 18, 24, 31, 40, 52] is searched using a binary search for the value 24. When a list has an even number of elements, take the lower of the two middle elements as the middle.
State the index (counting from 0) of the middle element checked first, and state whether the target is found on this first comparison.
Question 3 [2 marks]
Algorithmic Complexity
A hash table allows a value to be looked up directly by its key.
State the average-case time complexity of a lookup in a hash table, using Big O notation, and give a brief reason.
Question 4 [2 marks]
Programming Paradigms
In object-oriented programming, abstraction means exposing only the essential features of an object while hiding the complex implementation details.
State what is meant by abstraction, and give one benefit it gives to a programmer using the object.
Question 5 [3 marks]
Databases and SQL
The Enrolment table has columns StudentID and CourseName, with one row per student per course, so the same CourseName can appear many times.
Write an SQL statement to list every distinct CourseName that appears in the Enrolment table, with no course listed more than once.
Question 6 [4 marks]
Trees and Graphs
A directed graph has vertices P, Q, R, S with directed edges P->Q, Q->R, R->P, R->S.
State the in-degree and out-degree of vertex R, where in-degree is the number of edges pointing into a vertex and out-degree is the number of edges pointing out of it.
Question 7 [4 marks]
Theory of Computation
The regular expression a(b|c)*d matches strings that start with a, are followed by zero or more repetitions of either b or c in any combination, and end with d.
State, with a reason, whether each of the following strings matches the regular expression: 'ad', 'abccbd', 'aXd'.
Question 8 [3 marks]
Networks and Communication
In the client-server model, a web browser (the client) requests a web page from a web server.
Describe the roles of the client and the server in this exchange, and state one advantage of the client-server model over a peer-to-peer model for a busy website.
Question 9 [3 marks]
Programming: Trace, Write and Explain
A student writes the following pseudocode, intended to check whether a list of numbers, values, with n elements (indexed 0 to n - 1) is sorted in ascending order:
isSorted = TRUE
FOR i = 0 TO n - 3
IF values[i] > values[i + 1] THEN
isSorted = FALSE
ENDIF
NEXT i
OUTPUT isSorted
Explain why this code gives the wrong answer for the list [1, 2, 5, 3], and rewrite the FOR line so the code correctly checks every adjacent pair in a list of any length.
Question 10 [2 marks]
Networks and Communication
A school is deciding whether to connect its computer suite to the network using wired Ethernet cables or a wireless (Wi-Fi) connection.
State one advantage of the wired connection and one advantage of the wireless connection for this scenario.
Question 11 [4 marks]
Linear Data Structures
A queue of maximum size 5 is implemented as a circular buffer using an array with indices 0 to 4, a front pointer and a rear pointer.
The queue currently holds, from front to rear, 8, 3, 6, with front pointing at index 0 and rear pointing at index 2 (the index of the last item added).
enqueue(9) and enqueue(1) are then called, followed by dequeue().
State the index used to store each newly enqueued value, and the value returned by the dequeue() call.
Question 12 [4 marks]
Computer Architecture and the CPU
A CPU has a clock speed of 3.2 GHz (3,200,000,000 cycles per second). A particular instruction takes 4 clock cycles to complete.
Calculate the time, in nanoseconds, taken to execute this one instruction, and state one factor other than clock speed that affects how many instructions a CPU can complete per second.
Question 13 [5 marks]
Data Representation
Convert the 8-bit two's complement binary number 11101001 into denary.
Question 14 [3 marks]
Networks and Communication
A network switch forwards frames using MAC addresses, while a router forwards packets between networks using IP addresses.
Explain the difference in purpose between a MAC address and an IP address, and explain why global uniqueness of an interface identifier alone would not provide the network-location information needed for efficient routing across the internet.
Question 15 [2 marks]
Boolean Algebra and Logic Gates
A logic circuit has inputs A, B and C, and its output Z is 1 for exactly these combinations: A = 0, B = 0, C = 1; A = 0, B = 1, C = 1; and A = 1, B = 1, C = 1. Z is 0 for every other combination.
Write the Boolean expression for Z as a sum of products (before simplification), then simplify it to its shortest form.
Question 16 [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 17 [5 marks]
Algorithmic Complexity
A naive recursive function to compute the nth Fibonacci number calls itself twice for every non-base-case value of n, without storing any previously calculated results, giving a time complexity of O(2^n).
A memoised version stores each Fibonacci number the first time it is calculated, and simply looks up the stored value if it is needed again, giving a time complexity of O(n).
Explain why the naive version's time complexity grows so much faster than the memoised version's, and state one cost of memoisation that the naive version does not have.
Question 18 [6 marks]
Computer Architecture and the CPU
A pipelined processor executes the following two instructions back to back:
ADD R1, R2, R3 ; R1 = R2 + R3
SUB R4, R1, R5 ; R4 = R1 - R5
In a simple pipeline, the ADD instruction's result is not written back to R1 until several cycles after it starts, but the SUB instruction needs to read R1 as one of its inputs.
Explain what a data hazard is, and explain how forwarding (bypassing) can reduce the delay this data hazard would otherwise cause.
Model solutions
| Question 1[2 marks] | |
|---|---|
| Answer or working | Marks |
| the labelled rows 00 -> 0 and 01 -> 0 | B1 |
| the labelled rows 10 -> 0 and 11 -> 1 | B1 |
| Final answer: 00 -> 0; 01 -> 0; 10 -> 0; 11 -> 1. | |
| Question 2[2 marks] | |
|---|---|
| Answer or working | Marks |
| identifying the first middle element checked as index 3, value 18 | M1 |
| stating 24 is not found on this first comparison, since 24 is greater than 18 Award all 2 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 index and whether it finds the target are requested. Naming the value 18 is optional evidence. | A1 |
| Final answer: First middle index is 3 (value 18); 24 is not found on this comparison. | |
| Question 3[2 marks] | |
|---|---|
| Answer or working | Marks |
| O(1) | B1 |
| a reason such as a key's hash value maps directly to a storage location, so no searching through other elements is normally needed | B1 |
| Final answer: O(1) - a key's hash maps directly to its storage location | |
| Question 4[2 marks] | |
|---|---|
| Answer or working | Marks |
| a definition such as: abstraction presents a simplified view of an object, showing only what it does rather than how it does it internally | B1 |
| a benefit such as: the programmer using the object can work with a simple, high-level interface without needing to understand or manage its internal complexity | B1 |
| Final answer: Abstraction hides internal complexity, showing only what an object does; it lets a programmer use it via a simple interface without needing to understand the implementation | |
| Question 5[3 marks] | |
|---|---|
| Answer or working | Marks |
| selecting CourseName | M1 |
| selecting from Enrolment | M1 |
| removing duplicate course values using DISTINCT, GROUP BY or another equivalent valid query; no explanation or ordering is required | A1 |
| Final answer: SELECT DISTINCT CourseName FROM Enrolment; | |
| Question 6[4 marks] | |
|---|---|
| Answer or working | Marks |
| correctly identifying the incoming count as the in-degree | B1 |
| its value 1. Award both marks for in-degree 1 alone. | B1 |
| correctly identifying the outgoing count as the out-degree | B1 |
| its value 2. Award both marks for out-degree 2 alone. Award all 4 marks for in-degree 1 and out-degree 2 alone. Naming edges is optional evidence; accept equivalent valid notation. | B1 |
| Final answer: In-degree 1; out-degree 2. | |
| Question 7[4 marks] | |
|---|---|
| Answer or working | Marks |
| stating that ad matches because zero repetitions of b or c are allowed between a and d | B1 |
| stating that abccbd matches because its middle bccb uses only b or c between a and d | B1 |
| stating that aXd does not match because X is neither b nor c: B1 for the decision and B1 for the reason. No additional general summary of the expression 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: 'ad' matches, 'abccbd' matches, 'aXd' does not match | |
| Question 8[3 marks] | |
|---|---|
| Answer or working | Marks |
| describing the client's role, such as sending a request for a resource, for example an HTTP request for a page | B1 |
| describing the server's role, such as receiving the request, processing it and returning the requested resource | B1 |
| a valid advantage, such as centralised control and management of data and security, or resources being easier to back up when kept in one place | B1 |
| Final answer: The client requests a resource; the server processes the request and returns it. Client-server gives centralised control of data and security | |
| Question 9[3 marks] | |
|---|---|
| Answer or working | Marks |
| explaining that the loop omits the final adjacent pair at indices 2 and 3 | B1 |
| explaining that the missed pair 5,3 is out of order, so the original output incorrectly stays TRUE | B1 |
| FOR i = 0 TO n - 2, or an equivalent bound covering every adjacent pair | A1 |
| Final answer: The bound n - 3 omits the final pair (5,3), so isSorted incorrectly stays TRUE. Replace with FOR i = 0 TO n - 2. | |
| Question 10[2 marks] | |
|---|---|
| Answer or working | Marks |
| one valid contextual wired advantage, such as less radio interference and more reliable fixed-desktop connections. | B1 |
| one valid contextual wireless advantage, such as mobility within coverage or avoiding cables to each desk; do not require multiple advantages. | B1 |
| Final answer: Wired can be more reliable in a fixed suite; wireless allows mobility without a cable to every desk | |
| Question 11[4 marks] | |
|---|---|
| Answer or working | Marks |
| enqueue(9) being stored at index 3 | M1 |
| enqueue(1) being stored at index 4 | A1 |
| dequeue() returning the value currently at the front index | M1 |
| dequeue() returning 8 Award all 4 marks for the complete correct requested answer: 9 is stored at index 3; 1 at index 4; dequeue returns 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: 9 is stored at index 3; 1 at index 4; dequeue returns 8. | |
| Question 12[4 marks] | |
|---|---|
| Answer or working | Marks |
| one clock cycle taking 1 / 3200000000 seconds. | M1 |
| converting to nanoseconds, obtaining 0.3125 ns per cycle. | M1 |
| 4 * 0.3125 = 1.25 ns; accept calculating 4 / 3200000000 seconds then converting. | A1 |
| one valid other performance factor, such as cycles per instruction, cache behaviour or useful parallelism; no second factor is required. | B1 |
| Final answer: 1.25 ns; cycles per instruction also affect throughput | |
| Question 13[5 marks] | |
|---|---|
| Answer or working | Marks |
| recognising the leading bit is 1, so the number is negative | M1 |
| inverting all bits to give 00010110 | M1 |
| adding 1 to the inverted bits to give 00010111 | M1 |
| converting 00010111 to denary, 23 | A1 |
| stating the final value is -23 Award equivalent credit for another valid complete conversion method; the particular listed route is not compulsory. | A1 |
| Final answer: -23 | |
| Question 14[3 marks] | |
|---|---|
| Answer or working | Marks |
| MAC addressing identifying a network interface for local frame delivery; do not require addresses to be permanently fixed or universally unique. | B1 |
| IP being logical addressing used for delivery across networks. | B1 |
| explaining IP network prefixes support route selection, whereas global uniqueness alone supplies no such location structure. | B1 |
| Final answer: MAC identifies an interface for local frame delivery; IP supplies hierarchical routing information across networks | |
| Question 15[2 marks] | |
|---|---|
| Answer or working | Marks |
| the unsimplified sum of products (NOT A AND NOT B AND C) OR (NOT A AND B AND C) OR (A AND B AND C), accepting reordered terms | M1 |
| C AND (NOT A OR B), or an equivalent minimal expression; no separate derivation is requested | A1 |
| Final answer: Z = ((NOT A) AND (NOT B) AND C) OR ((NOT A) AND B AND C) OR (A AND B AND C) = C AND ((NOT A) OR B). | |
| Question 16[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 17[5 marks] | |
|---|---|
| Answer or working | Marks |
| explaining that the naive version recomputes overlapping Fibonacci subproblems | B1 |
| linking this repetition to a branching exponential call tree; O(2^n) is the supplied upper bound, not an exact doubling law | B1 |
| explaining that memoisation computes each distinct Fibonacci value only once | B1 |
| explaining that there are O(n) distinct indices, with cached results reused, giving O(n) work | B1 |
| stating one valid cost, such as extra cache memory or cache-management overhead; no separate trade-off explanation is required | B1 |
| Final answer: Naive recursion repeatedly recomputes overlapping subproblems; memoisation computes each of O(n) distinct indices once. F(n-2) is reached both directly and through F(n-1), with repetitions branching recursively. The supplied O(2^n) is an upper bound; the tighter usual growth is Theta(phi^n). Memoisation uses O(n) extra cache entries, in addition to recursion stack space. | |
| Question 18[6 marks] | |
|---|---|
| Answer or working | Marks |
| explaining a data hazard occurs when an instruction needs a value that a previous, still in-progress instruction has not yet produced or written back | B1 |
| identifying this specific hazard as SUB needing the new value of R1 before ADD has finished writing it back | B1 |
| explaining that without any mitigation, the pipeline would need to stall (pause) SUB until ADD's result is safely written back | B1 |
| explaining forwarding instead takes the result of ADD directly from within the pipeline, as soon as it is calculated, rather than waiting for it to be written back to the register first | B1 |
| explaining this result is then fed directly into the stage of the pipeline where SUB needs it as an input | B1 |
| a further correct point, such as forwarding removing or reducing the need to stall the pipeline, keeping it running closer to its full speed | B1 |
| Final answer: A data hazard is an instruction needing a result a previous, unfinished instruction has not yet produced; here SUB needs ADD's new R1. Forwarding feeds ADD's result directly from within the pipeline into SUB as soon as it is calculated, avoiding (or reducing) a stall | |