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 1

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]

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

Mark scheme for Question 1 [2 marks]
Question 1[2 marks]
Answer or workingMarks
O(n)B1
a reason such as every element may need to be checked when the target is absent or is the last elementB1
Final answer: O(n) - every element may need to be checked
Mark scheme for Question 2 [3 marks]
Question 2[3 marks]
Answer or workingMarks
UPDATE StudentM1
SET YearGroup = 13M1
restricting the update with WHERE StudentID = 1042 or an equivalent predicateA1
Final answer: UPDATE Student SET YearGroup = 13 WHERE StudentID = 1042;
Mark scheme for Question 3 [3 marks]
Question 3[3 marks]
Answer or workingMarks
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.
Mark scheme for Question 4 [3 marks]
Question 4[3 marks]
Answer or workingMarks
correctly moving S0 to S1 to S1 on the two a inputsM1
moving S1 to S2 on the final b inputA1
stating the string is accepted, since S2 is an accepting stateA1
Final answer: Accepted - the machine ends in accepting state S2
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 [1 mark]
Question 6[1 mark]
Answer or workingMarks
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.
Mark scheme for Question 7 [3 marks]
Question 7[3 marks]
Answer or workingMarks
explaining a class is a template or blueprint defining the attributes and methods that its objects will have, such as Student defining name and yearGroupB1
explaining an object is a specific instance created from a class, with its own actual values for those attributes, such as one particular studentB1
explaining instantiation is the process of creating a new object from a classB1
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
Mark scheme for Question 8 [4 marks]
Question 8[4 marks]
Answer or workingMarks
2 being shifted before 5 to give the sorted section 2, 5M1
9 remaining after 5, since it is already larger, giving the sorted section 2, 5, 9M1
the unsorted elements 1 and 6 remaining unchanged in their original positionsA1
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].
Mark scheme for Question 9 [4 marks]
Question 9[4 marks]
Answer or workingMarks
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
Mark scheme for Question 10 [4 marks]
Question 10[4 marks]
Answer or workingMarks
ACC = 20 after LOAD 12M1
ACC = 35 after ADD 13M1
ACC = 27 after SUB 14A1
27 stored at address 15A1
Final answer: ACC: 20, then 35, then 27; address 15 stores 27
Mark scheme for Question 11 [4 marks]
Question 11[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 12 [5 marks]
Question 12[5 marks]
Answer or workingMarks
CountOccurrences with items and target parametersM1
initialising a zero counterM1
inspecting every element for equality with targetM1
counting each matching occurrence without stopping earlyM1
returning the count; equivalent valid algorithms receive creditA1
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
Mark scheme for Question 13 [4 marks]
Question 13[4 marks]
Answer or workingMarks
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.
Mark scheme for Question 14 [5 marks]
Question 14[5 marks]
Answer or workingMarks
identifying 40 as the in-order successorA1
selecting the smallest value in the right subtreeA1
correctly associating that successor with deleted node 30. These points may all be inferred from successor 40.A1
new left child of root being 40A1
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.
Mark scheme for Question 15 [5 marks]
Question 15[5 marks]
Answer or workingMarks
pushing ( onto the stack when the first character is readM1
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 readM1
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 stackA1
Final answer: Not balanced - the popped bracket [ does not match the closing bracket )
Mark scheme for Question 16 [6 marks]
Question 16[6 marks]
Answer or workingMarks
describing a BFS or DFS from one vertex, recording visited verticesB1
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.

Build a free practice pack.

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