A Level Computer Science Paper 1
Covers Linear Data Structures, Trees and Graphs, Searching and Sorting Algorithms and 9 more.
Questions
Question 1 [2 marks]
Algorithmic Complexity
A linear search checks each element of a list in turn until the target is found or the list is exhausted.
State the time complexity of a linear search on a list of n elements in the worst case, using Big O notation, and give a brief reason.
Question 2 [3 marks]
Databases and SQL
A database table Student has columns StudentID, FirstName, LastName and YearGroup.
Write an SQL statement to update the YearGroup to 13 for the student whose StudentID is 1042.
Question 3 [3 marks]
Linear Data Structures
A stack is a linear data structure that follows Last In First Out (LIFO).
The following operations are performed on an empty stack: push(4), push(9), pop(), push(2), pop().
State the value returned by each pop() operation, in the order they occur.
Question 4 [3 marks]
Theory of Computation
A finite state machine has states S0 (start), S1 and S2 (accepting state). From S0, input a goes to S1 and input b goes to S0. From S1, input a goes to S1 and input b goes to S2. From S2, any input stays at S2.
Trace the machine for the input string aab, and state whether the string is accepted.
Question 5 [4 marks]
Data Representation
Convert the denary number 200 into hexadecimal, and then into an 8-bit unsigned binary number.
Question 6 [1 mark]
Computer Architecture and the CPU
A computer's memory hierarchy includes CPU registers, cache memory and main memory (RAM), typically in that order from fastest to slowest.
State one reason a computer does not simply use registers for all of its memory, given how much faster they are than main memory.
Question 7 [3 marks]
Programming Paradigms
A class called Student defines attributes such as name and yearGroup, plus methods that act on them.
Explain the difference between a class and an object, using Student as an example, and state what is meant by instantiation.
Question 8 [4 marks]
Searching and Sorting Algorithms
The list [5, 2, 9, 1, 6] is sorted using insertion sort, which builds a sorted section at the start of the list by inserting each new element into its correct position.
State the contents of the whole list after the first three elements (5, 2, 9) have been inserted into the sorted section, but before 1 is considered.
Question 9 [4 marks]
Networks and Communication
A large file is sent across a network using packet switching, rather than being sent as one continuous stream.
Explain what is meant by packet switching, and state one advantage it has over circuit switching, in which a dedicated path is reserved for the communication.
Question 10 [4 marks]
Computer Architecture and the CPU
A simplified processor executes the following sequence of instructions, where ACC is the accumulator register:
LOAD 12 ; load the value stored at address 12 into ACC
ADD 13 ; add the value stored at address 13 to ACC
SUB 14 ; subtract the value stored at address 14 from ACC
STORE 15 ; store the value in ACC at address 15
Address 12 holds 20, address 13 holds 15, and address 14 holds 8.
State the value in ACC after each of the LOAD, ADD and SUB instructions, and the value stored at address 15.
Question 11 [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 12 [5 marks]
Programming: Trace, Write and Explain
Write pseudocode for a function called CountOccurrences that takes a list of values, items, and a target value, target, as parameters, and returns the number of times target appears in items.
Question 13 [4 marks]
Computer Architecture and the CPU
A processor has an L1 cache with access time 1 ns, an L2 cache with access time 8 ns, and main memory with access time 80 ns. Treat each stated access time as the total time for an access served by that level, including any earlier failed cache lookups.
For a particular program, of all memory accesses: 80% are served by L1, 15% are served by L2, and the remaining 5% are served by main memory.
Calculate the average memory access time for this program.
Question 14 [5 marks]
Trees and Graphs
A binary search tree has root 50; its left child is 30 and right child is 70; 30's left child is 20 and right child is 40; 70's left child is 60 and right child is 80.
The value 30 is deleted. Since 30 has two children, it is replaced by its in-order successor: the smallest value in its right subtree.
State the in-order successor of 30, and state the value that ends up as the new left child of the root after the deletion.
Question 15 [5 marks]
Linear Data Structures
A stack-based algorithm checks whether a string of brackets is balanced. For each opening bracket it pushes the bracket onto a stack. For each closing bracket, it pops the stack and checks the popped bracket matches the closing bracket; if the stack is empty when a closing bracket is read, the string is not balanced. At the end, the string is balanced only if the stack is empty.
Trace this algorithm for the string ( [ ) ]. State, with a reason, whether the string is reported as balanced.
Question 16 [6 marks]
Trees and Graphs
A graph has vertices A, B, C, D, E, F with undirected edges A-B, B-C, A-C, D-E.
A graph is connected if every vertex can be reached from every other vertex by following edges. Explain how a breadth-first or depth-first search could be used to test whether this graph is connected, then state whether this particular graph is connected, and identify any vertex or vertices that would be unreachable from A.
Model solutions
| Question 1[2 marks] | |
|---|---|
| Answer or working | Marks |
| O(n) | B1 |
| a reason such as every element may need to be checked when the target is absent or is the last element | B1 |
| Final answer: O(n) - every element may need to be checked | |
| Question 2[3 marks] | |
|---|---|
| Answer or working | Marks |
| UPDATE Student | M1 |
| SET YearGroup = 13 | M1 |
| restricting the update with WHERE StudentID = 1042 or an equivalent predicate | A1 |
| Final answer: UPDATE Student SET YearGroup = 13 WHERE StudentID = 1042; | |
| Question 3[3 marks] | |
|---|---|
| Answer or working | Marks |
| applying LIFO correctly; this may be inferred from the correct requested pop values and does not require an intermediate stack state. | M1 |
| the first pop returning 9. | A1 |
| the second pop returning 2. Award all 3 marks for 9, 2 in order alone. | A1 |
| Final answer: The pop values are 9, then 2. | |
| Question 4[3 marks] | |
|---|---|
| Answer or working | Marks |
| correctly moving S0 to S1 to S1 on the two a inputs | M1 |
| moving S1 to S2 on the final b input | A1 |
| stating the string is accepted, since S2 is an accepting state | A1 |
| Final answer: Accepted - the machine ends in accepting state S2 | |
| 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[1 mark] | |
|---|---|
| Answer or working | Marks |
| stating one valid reason, such as registers being more expensive per byte than RAM or requiring more chip area per byte; either statement alone earns full credit. | B1 |
| Final answer: Registers are much more expensive per byte than RAM. | |
| Question 7[3 marks] | |
|---|---|
| Answer or working | Marks |
| explaining a class is a template or blueprint defining the attributes and methods that its objects will have, such as Student defining name and yearGroup | B1 |
| explaining an object is a specific instance created from a class, with its own actual values for those attributes, such as one particular student | B1 |
| explaining instantiation is the process of creating a new object from a class | B1 |
| Final answer: Student is the class (a template); a particular student is an object (an instance of it) with real values; instantiation is creating that object from the class | |
| Question 8[4 marks] | |
|---|---|
| Answer or working | Marks |
| 2 being shifted before 5 to give the sorted section 2, 5 | M1 |
| 9 remaining after 5, since it is already larger, giving the sorted section 2, 5, 9 | M1 |
| the unsorted elements 1 and 6 remaining unchanged in their original positions | A1 |
| the complete list 2, 5, 9, 1, 6 Award all 4 marks for the complete correct requested answer: [2,5,9,1,6]. 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: [2,5,9,1,6]. | |
| Question 9[4 marks] | |
|---|---|
| Answer or working | Marks |
| dividing data into labelled packets with routing/sequence information. | B1 |
| packets being forwarded independently and potentially following different routes. | B1 |
| reassembling the original data at the destination. | B1 |
| stating one valid advantage over a reserved circuit, such as more efficient link use or greater resilience to a failed path; no additional explanation or second advantage is required. | B1 |
| Final answer: Split into packets; route independently; reassemble; share links without reserving a circuit | |
| Question 10[4 marks] | |
|---|---|
| Answer or working | Marks |
| ACC = 20 after LOAD 12 | M1 |
| ACC = 35 after ADD 13 | M1 |
| ACC = 27 after SUB 14 | A1 |
| 27 stored at address 15 | A1 |
| Final answer: ACC: 20, then 35, then 27; address 15 stores 27 | |
| Question 11[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 12[5 marks] | |
|---|---|
| Answer or working | Marks |
| CountOccurrences with items and target parameters | M1 |
| initialising a zero counter | M1 |
| inspecting every element for equality with target | M1 |
| counting each matching occurrence without stopping early | M1 |
| returning the count; equivalent valid algorithms receive credit | A1 |
| Final answer: FUNCTION CountOccurrences(items, target) count = 0 FOR EACH v IN items IF v = target THEN count = count + 1 ENDIF NEXT v RETURN count ENDFUNCTION | |
| Question 13[4 marks] | |
|---|---|
| Answer or working | Marks |
| L1 contribution = 0.80 * 1 = 0.8 ns. | M1 |
| L2 contribution = 0.15 * 8 = 1.2 ns. | M1 |
| main-memory contribution = 0.05 * 80 = 4 ns. | M1 |
| average = 0.8 + 1.2 + 4 = 6.0 ns. | A1 |
| Final answer: 6.0 ns. | |
| Question 14[5 marks] | |
|---|---|
| Answer or working | Marks |
| identifying 40 as the in-order successor | A1 |
| selecting the smallest value in the right subtree | A1 |
| correctly associating that successor with deleted node 30. These points may all be inferred from successor 40. | A1 |
| new left child of root being 40 | A1 |
| correctly distinguishing this new child from root 50. Award all 5 marks for successor 40 and new root-left child 40 without further deletion states. | A1 |
| Final answer: The in-order successor is 40, which becomes the new left child of root 50. | |
| Question 15[5 marks] | |
|---|---|
| Answer or working | Marks |
| pushing ( onto the stack when the first character is read | M1 |
| pushing [ onto the stack when the second character is read, giving stack contents (, [ | M1 |
| popping the top of the stack, [, when the closing bracket ) is read | M1 |
| recognising the popped bracket [ does not match the closing bracket ) | A1 |
| concluding the string is reported as not balanced, because of the mismatch rather than an empty stack | A1 |
| Final answer: Not balanced - the popped bracket [ does not match the closing bracket ) | |
| Question 16[6 marks] | |
|---|---|
| Answer or working | Marks |
| describing a BFS or DFS from one vertex, recording visited vertices | B1 |
| explaining that the graph is connected exactly when all vertices are reached. Accept equivalent valid BFS or DFS descriptions. | B1 |
| concluding this graph is not connected. A separate search trace and descriptions of the other components are optional. | A1 |
| identifying D as unreachable from A. | A1 |
| identifying E as unreachable from A. | A1 |
| identifying F as unreachable from A. Award all 6 marks for the connectivity-test method, the not-connected conclusion and these three unreachable vertices alone. | A1 |
| Final answer: Run BFS or DFS from A, recording visited vertices, and compare with all vertices. Only A,B,C are reached; D,E,F are unreachable from A, so the graph is not connected. | |