Revision Library
Choose a subject
Menu
Computer Science
Need a new topic?
Missing a topic, found a bug, or want something added?

A Level Paper 4: Data and Networks

Covers data representation, networks, databases and SQL, boolean logic and logic gates, trees and graphs, and searching and sorting algorithms.

20 questions - 80 marks

Download PDF

Open A Level Computer Science workspace

Questions

Question 1 [2 marks]

Boolean Algebra and Logic Gates

State the output of the logic expression A OR B for each of the four possible combinations of A and B (each 0 or 1).

Question 2 [2 marks]

Networks and Communication

A LAN (Local Area Network) covers a small geographical area, such as a single building. A WAN (Wide Area Network) covers a much larger geographical area, such as a whole country or the world.

Give one example of a LAN and one example of a WAN.

Question 3 [3 marks]

Trees and Graphs

A binary search tree has the following structure: the root holds 40; its left child holds 20 and its right child holds 60; 20's left child holds 10 and its right child holds 30.

List the values visited by an in-order traversal of this tree (left subtree, root, right subtree, applied recursively).

Question 4 [4 marks]

Databases and SQL

The Student table also has a column AverageGrade (a number).

Write an SQL statement to select the FirstName, LastName and AverageGrade of all students with an AverageGrade greater than 75, ordered from highest AverageGrade to lowest.

Question 5 [4 marks]

Data Representation

Convert the denary number -45 into an 8-bit two's complement binary number.

Question 6 [4 marks]

Searching and Sorting Algorithms

The list [15, 8, 42, 3, 27, 19] is searched using a linear search for the value 3, checking each element in turn starting from index 0.

State the number of comparisons made before the target is found (counting the comparison that finds it), and state the index at which it is found.

Question 7 [4 marks]

Trees and Graphs

A graph has vertices A, B, C, D with undirected edges A-B, A-C, B-D, C-D.

An adjacency list represents a graph by storing, for each vertex, a list of the vertices it is directly connected to.

Write the adjacency list for this graph, listing each vertex's neighbours in alphabetical order.

Question 8 [4 marks]

Networks and Communication

An IPv4 address is 192.168.1.130 and its subnet mask is 255.255.255.192.

State the number of bits used for the network portion of the address under this subnet mask, and explain how a subnet mask is used to determine whether two IP addresses are on the same subnet.

Question 9 [4 marks]

Trees and Graphs

A binary search tree is built by inserting values one at a time into an initially empty tree, in this order: 50, 25, 75, 10, 30.

Each new value is compared with the current node, moving left if it is smaller and right if it is larger, until an empty position is found.

State the parent value and the side (left or right child) that each of 10 and 30 is inserted as.

Question 10 [4 marks]

Searching and Sorting Algorithms

Merge sort divides a list into sublists, sorts them, then merges the sorted sublists back together.

Two sorted sublists, [2, 9, 11] and [4, 6, 15], are merged into a single sorted list by repeatedly comparing the front elements of each sublist and taking the smaller.

Show the merged list.

Question 11 [3 marks]

Databases and SQL

The Student table also has a column Withdrawn (a value of 'Y' or 'N').

Write an SQL statement to delete every row from Student where Withdrawn is 'Y', and explain one risk of running a DELETE statement without a WHERE clause.

Question 12 [5 marks]

Trees and Graphs

A graph has vertices P, Q, R, S, T with undirected edges P-Q, P-R, Q-S, R-S, S-T.

A breadth-first search starts at P and visits unvisited neighbours in alphabetical order, using a queue.

State the order in which the vertices are visited.

Question 13 [5 marks]

Databases and SQL

A school wants to list every student's FirstName and LastName, together with their CourseName if they are enrolled on one, but the list should still include students who are not enrolled on any course.

Explain why a LEFT JOIN (from Student to Enrolment) should be used here rather than an INNER JOIN, and write the SQL statement.

Question 14 [5 marks]

Searching and Sorting Algorithms

A sorted list contains 15 elements, and a binary search is used to find a target value.

State the maximum number of comparisons a binary search could need for this list, and explain your reasoning using the fact that each comparison at most halves the number of elements still to be searched.

Question 15 [6 marks]

Trees and Graphs

A binary search tree is built by inserting values one at a time into an initially empty tree, in this order: 40, 20, 60, 10, 25, 5.

State each inserted node's parent and whether it is a left or right child, then state the height of the tree, where a single root node alone has height 0.

Question 16 [3 marks]

Boolean Algebra and Logic Gates

A NAND gate is described as a universal gate, because any other logic gate (AND, OR, NOT and so on) can be built using only NAND gates.

Explain how a single NAND gate, with both of its inputs connected together to the same signal A, can be used to build a NOT gate, and explain why being a universal gate makes NAND useful in practice.

Question 17 [5 marks]

Trees and Graphs

A weighted graph has vertices A, B, C, D with edges: A-B weight 4, A-C weight 2, C-B weight 1, C-D weight 7, B-D weight 3.

Dijkstra's algorithm is used to find the shortest path from A to D.

Find the shortest distance from A to D, and state the path taken.

Question 18 [2 marks]

Boolean Algebra and Logic Gates

Simplify the Boolean expression Y = (A OR B) AND (A OR (NOT B)), showing each law used.

Question 19 [5 marks]

Databases and SQL

A website builds an SQL query by directly inserting user input into a string: SELECT * FROM Student WHERE LastName = 'INPUT_HERE', substituting whatever the user types in place of INPUT_HERE.

A malicious user enters, as their input, the text: X' OR '1'='1

Explain why this input causes an SQL injection vulnerability, and explain how a parameterised query (prepared statement) prevents this attack.

Question 20 [6 marks]

Trees and Graphs

A graph has vertices M, N, O, P, Q with undirected edges M-N, M-O, N-P, O-P, P-Q.

A depth-first search starts at M, and at each step moves to the first unvisited neighbour in alphabetical order; when a vertex has no unvisited neighbours, it backtracks to the most recent vertex that still has one.

State the order in which the vertices are visited.

Model solutions

Mark scheme for Question 1 [2 marks]
Question 1[2 marks]
Answer or workingMarks
the labelled rows 00 -> 0 and 01 -> 1B1
the labelled rows 10 -> 1 and 11 -> 1B1
Final answer: 00 -> 0; 01 -> 1; 10 -> 1; 11 -> 1.
Mark scheme for Question 2 [2 marks]
Question 2[2 marks]
Answer or workingMarks
a valid LAN example, such as the network inside a single school or office buildingB1
a valid WAN example, such as the internet, or a company's network connecting offices in different citiesB1
Final answer: LAN example: a school's internal network; WAN example: the internet
Mark scheme for Question 3 [3 marks]
Question 3[3 marks]
Answer or workingMarks
correctly traversing the left subtree of 40 first, giving 10, 20, 30M1
visiting the root, 40, nextM1
the complete sequence 10, 20, 30, 40, 60A1
Final answer: 10, 20, 30, 40, 60
Mark scheme for Question 4 [4 marks]
Question 4[4 marks]
Answer or workingMarks
selecting FirstName, LastName and AverageGradeM1
selecting from StudentM1
the strict condition AverageGrade > 75M1
ordering AverageGrade descending in a complete valid statementA1
Final answer: SELECT FirstName, LastName, AverageGrade FROM Student WHERE AverageGrade > 75 ORDER BY AverageGrade DESC;
Mark scheme for Question 5 [4 marks]
Question 5[4 marks]
Answer or workingMarks
finding the binary representation of 45 as 00101101M1
inverting all bits to give 11010010M1
adding 1 to the inverted bitsM1
11010011 Award equivalent credit for another valid complete conversion method; the particular listed route is not compulsory.A1
Final answer: 11010011
Mark scheme for Question 6 [4 marks]
Question 6[4 marks]
Answer or workingMarks
checking index 0 (15), index 1 (8) and index 2 (42) in turn, none matchingM1
finding a match at index 3, value 3A1
stating the target is found after 4 comparisonsA1
stating the index found is 3 Award all 4 marks for the complete correct requested answer: 4 comparisons; found at index 3. 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: 4 comparisons; found at index 3.
Mark scheme for Question 7 [4 marks]
Question 7[4 marks]
Answer or workingMarks
identifying A's neighbours as B and CM1
identifying B's neighbours as A and DM1
identifying C's neighbours as A and D, and D's neighbours as B and CA1
the complete adjacency list: A: B, C ; B: A, D ; C: A, D ; D: B, CA1
Final answer: A: B, C; B: A, D; C: A, D; D: B, C
Mark scheme for Question 8 [4 marks]
Question 8[4 marks]
Answer or workingMarks
converting the last octet, 192, to binary: 11000000M1
26 network bits in total (8 + 8 + 8 + 2)A1
explaining a bitwise AND is performed between an IP address and the subnet mask to find its network addressB1
stating two addresses are on the same subnet if this calculation gives the same network address for bothB1
Final answer: 26 network bits; two addresses are on the same subnet if ANDing each with the subnet mask gives the same network address
Mark scheme for Question 9 [4 marks]
Question 9[4 marks]
Answer or workingMarks
10 having parent 25A1
10 being a left child.A1
30 having parent 25A1
30 being a right child. No ancestor comparison trace is required.A1
Final answer: 10 is the left child of 25; 30 is the right child of 25.
Mark scheme for Question 10 [4 marks]
Question 10[4 marks]
Answer or workingMarks
correctly comparing the front elements at each step (2 then 4, then 6, then 9, then 11)M1
taking the smaller element each time until one sublist is emptyM1
appending the remaining element from the non-empty sublistA1
the complete merged list 2, 4, 6, 9, 11, 15 Award all 4 marks for the complete correct requested answer: [2,4,6,9,11,15]. 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,4,6,9,11,15].
Mark scheme for Question 11 [3 marks]
Question 11[3 marks]
Answer or workingMarks
DELETE FROM StudentM1
restricting deletion to Withdrawn = Y, treating Y as textA1
explaining that omitting WHERE deletes all rows, including non-withdrawn students; do not require an unconditional claim of irreversibilityB1
Final answer: DELETE FROM Student WHERE Withdrawn = 'Y'; Without WHERE every row is deleted, including students who have not withdrawn.
Mark scheme for Question 12 [5 marks]
Question 12[5 marks]
Answer or workingMarks
starting at P and enqueuing its unvisited neighbours Q and R in alphabetical orderM1
visiting Q next and enqueuing its new unvisited neighbour SM1
visiting R next, with no new neighbours to enqueueM1
visiting S next and enqueuing its new unvisited neighbour TM1
the complete order P, Q, R, S, T Award all 5 marks for the complete correct requested answer: P, Q, R, S, T. 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: P, Q, R, S, T.
Mark scheme for Question 13 [5 marks]
Question 13[5 marks]
Answer or workingMarks
explaining INNER JOIN excludes students without matching enrolmentsB1
explaining LEFT JOIN retains those students, with NULL course values where unmatchedB1
selecting the requested student names and course fieldM1
using Student as the preserved side of an outer join, accepting an equivalent reversed RIGHT JOINM1
a complete valid relationship condition if a link is supplied or explicitly assumed; no linking columns are printed, so accept a justified generic link or identification of the missing relationship instead of demanding StudentIDA1
Final answer: LEFT JOIN retains every Student row and supplies NULL CourseName for no match; INNER JOIN omits those students. If the linking columns are both StudentID: SELECT s.FirstName, s.LastName, e.CourseName FROM Student s LEFT JOIN Enrolment e ON s.StudentID = e.StudentID;
Mark scheme for Question 14 [5 marks]
Question 14[5 marks]
Answer or workingMarks
explaining that each unsuccessful comparison removes about half the candidatesM1
a valid shrinking sequence such as 15,7,3,1.M1
accounting for a final comparison on the last candidateA1
maximum 4 comparisons.A1
a coherent link between repeated halving and that bound, including equivalent reasoning or floor(log2(15))+1=4. A logarithm expression is not required.B1
Final answer: Maximum 4 comparisons. The largest remaining candidate counts after unsuccessful comparisons are 15 -> 7 -> 3 -> 1 -> 0. A deepest successful search also uses 4 comparisons.
Mark scheme for Question 15 [6 marks]
Question 15[6 marks]
Answer or workingMarks
20 inserted as the left child of 40, and 60 as the right child of 40M1
10 inserted as the left child of 20, following the path 40 then 20M1
25 inserted as the right child of 20, following the path 40 then 20M1
5 inserted as the left child of 10, following the path 40, 20, then 10A1
identifying the longest root-to-leaf path as 40, 20, 10, 5M1
stating the height of the tree is 3 Award all 6 marks for the complete correct requested answer: 40 is the root (no parent); 20 is left of 40; 60 is right of 40; 10 is left of 20; 25 is right of 20; 5 is left of 10. Height is 3 edges. 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: 40 is the root (no parent); 20 is left of 40; 60 is right of 40; 10 is left of 20; 25 is right of 20; 5 is left of 10. Height is 3 edges.
Mark scheme for Question 16 [3 marks]
Question 16[3 marks]
Answer or workingMarks
explaining that tied inputs give NOT (A AND A) = NOT A, so the output inverts A; accept a complete two-case explanationB1
universality allowing arbitrary logic to be implemented using NAND gates aloneB1
a practical benefit of using one gate type, such as simpler manufacture, design, testing or stockB1
Final answer: NAND(A,A) = NOT (A AND A) = NOT A. Universality allows any logic function to be built from one gate type, simplifying manufacture, stock and circuit implementation.
Mark scheme for Question 17 [5 marks]
Question 17[5 marks]
Answer or workingMarks
path starting A-CA1
continuing C-BA1
finishing B-D.A1
distance 6A1
a distance consistent with the complete path (2+1+3=6). Award all 5 marks for distance 6 and path A-C-B-D without tentative-distance states.A1
Final answer: Shortest distance 6, via A -> C -> B -> D (2+1+3).
Mark scheme for Question 18 [2 marks]
Question 18[2 marks]
Answer or workingMarks
showing valid laws for a complete simplification, such as distributivity, complementarity and identity; accept any valid derivationM1
Y = AA1
Final answer: Y = A. Dual distributivity gives A OR (B AND NOT B). Complementarity gives B AND NOT B = 0. Identity gives A OR 0 = A.
Mark scheme for Question 19 [5 marks]
Question 19[5 marks]
Answer or workingMarks
the input quote ending the intended surname stringB1
the added OR comparison being always trueB1
explaining that every Student row therefore satisfies the predicateB1
fixed query text with user input bound separately as a parameterB1
explaining that bound input is literal data, so its quotes and OR text cannot alter SQL syntaxB1
Final answer: SELECT * FROM Student WHERE LastName = 'X' OR '1'='1' returns all rows because the OR comparison is always true. Use SELECT * FROM Student WHERE LastName = ? with the input bound as a parameter; it is data, never parsed as SQL syntax.
Mark scheme for Question 20 [6 marks]
Question 20[6 marks]
Answer or workingMarks
visiting M, then moving to its first unvisited neighbour alphabetically, NM1
moving from N to its only unvisited neighbour, PM1
moving from P to its first unvisited neighbour alphabetically, O, before QM1
backtracking from O to P, since O has no unvisited neighboursA1
moving from P to its remaining unvisited neighbour, QA1
the complete order M, N, P, O, Q Award all 6 marks for the complete correct requested answer: M, N, P, O, Q. 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: M, N, P, O, Q.

Build a free practice pack.

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