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.
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
| Question 1[2 marks] | |
|---|---|
| Answer or working | Marks |
| the labelled rows 00 -> 0 and 01 -> 1 | B1 |
| the labelled rows 10 -> 1 and 11 -> 1 | B1 |
| Final answer: 00 -> 0; 01 -> 1; 10 -> 1; 11 -> 1. | |
| Question 2[2 marks] | |
|---|---|
| Answer or working | Marks |
| a valid LAN example, such as the network inside a single school or office building | B1 |
| a valid WAN example, such as the internet, or a company's network connecting offices in different cities | B1 |
| Final answer: LAN example: a school's internal network; WAN example: the internet | |
| Question 3[3 marks] | |
|---|---|
| Answer or working | Marks |
| correctly traversing the left subtree of 40 first, giving 10, 20, 30 | M1 |
| visiting the root, 40, next | M1 |
| the complete sequence 10, 20, 30, 40, 60 | A1 |
| Final answer: 10, 20, 30, 40, 60 | |
| Question 4[4 marks] | |
|---|---|
| Answer or working | Marks |
| selecting FirstName, LastName and AverageGrade | M1 |
| selecting from Student | M1 |
| the strict condition AverageGrade > 75 | M1 |
| ordering AverageGrade descending in a complete valid statement | A1 |
| Final answer: SELECT FirstName, LastName, AverageGrade FROM Student WHERE AverageGrade > 75 ORDER BY AverageGrade DESC; | |
| Question 5[4 marks] | |
|---|---|
| Answer or working | Marks |
| finding the binary representation of 45 as 00101101 | M1 |
| inverting all bits to give 11010010 | M1 |
| adding 1 to the inverted bits | M1 |
| 11010011 Award equivalent credit for another valid complete conversion method; the particular listed route is not compulsory. | A1 |
| Final answer: 11010011 | |
| Question 6[4 marks] | |
|---|---|
| Answer or working | Marks |
| checking index 0 (15), index 1 (8) and index 2 (42) in turn, none matching | M1 |
| finding a match at index 3, value 3 | A1 |
| stating the target is found after 4 comparisons | A1 |
| 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. | |
| Question 7[4 marks] | |
|---|---|
| Answer or working | Marks |
| identifying A's neighbours as B and C | M1 |
| identifying B's neighbours as A and D | M1 |
| identifying C's neighbours as A and D, and D's neighbours as B and C | A1 |
| the complete adjacency list: A: B, C ; B: A, D ; C: A, D ; D: B, C | A1 |
| Final answer: A: B, C; B: A, D; C: A, D; D: B, C | |
| Question 8[4 marks] | |
|---|---|
| Answer or working | Marks |
| converting the last octet, 192, to binary: 11000000 | M1 |
| 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 address | B1 |
| stating two addresses are on the same subnet if this calculation gives the same network address for both | B1 |
| Final answer: 26 network bits; two addresses are on the same subnet if ANDing each with the subnet mask gives the same network address | |
| Question 9[4 marks] | |
|---|---|
| Answer or working | Marks |
| 10 having parent 25 | A1 |
| 10 being a left child. | A1 |
| 30 having parent 25 | A1 |
| 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. | |
| Question 10[4 marks] | |
|---|---|
| Answer or working | Marks |
| 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 empty | M1 |
| appending the remaining element from the non-empty sublist | A1 |
| 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]. | |
| Question 11[3 marks] | |
|---|---|
| Answer or working | Marks |
| DELETE FROM Student | M1 |
| restricting deletion to Withdrawn = Y, treating Y as text | A1 |
| explaining that omitting WHERE deletes all rows, including non-withdrawn students; do not require an unconditional claim of irreversibility | B1 |
| Final answer: DELETE FROM Student WHERE Withdrawn = 'Y'; Without WHERE every row is deleted, including students who have not withdrawn. | |
| Question 12[5 marks] | |
|---|---|
| Answer or working | Marks |
| starting at P and enqueuing its unvisited neighbours Q and R in alphabetical order | M1 |
| visiting Q next and enqueuing its new unvisited neighbour S | M1 |
| visiting R next, with no new neighbours to enqueue | M1 |
| visiting S next and enqueuing its new unvisited neighbour T | M1 |
| 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. | |
| Question 13[5 marks] | |
|---|---|
| Answer or working | Marks |
| explaining INNER JOIN excludes students without matching enrolments | B1 |
| explaining LEFT JOIN retains those students, with NULL course values where unmatched | B1 |
| selecting the requested student names and course field | M1 |
| using Student as the preserved side of an outer join, accepting an equivalent reversed RIGHT JOIN | M1 |
| 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 StudentID | A1 |
| 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; | |
| Question 14[5 marks] | |
|---|---|
| Answer or working | Marks |
| explaining that each unsuccessful comparison removes about half the candidates | M1 |
| a valid shrinking sequence such as 15,7,3,1. | M1 |
| accounting for a final comparison on the last candidate | A1 |
| 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. | |
| Question 15[6 marks] | |
|---|---|
| Answer or working | Marks |
| 20 inserted as the left child of 40, and 60 as the right child of 40 | M1 |
| 10 inserted as the left child of 20, following the path 40 then 20 | M1 |
| 25 inserted as the right child of 20, following the path 40 then 20 | M1 |
| 5 inserted as the left child of 10, following the path 40, 20, then 10 | A1 |
| identifying the longest root-to-leaf path as 40, 20, 10, 5 | M1 |
| 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. | |
| Question 16[3 marks] | |
|---|---|
| Answer or working | Marks |
| explaining that tied inputs give NOT (A AND A) = NOT A, so the output inverts A; accept a complete two-case explanation | B1 |
| universality allowing arbitrary logic to be implemented using NAND gates alone | B1 |
| a practical benefit of using one gate type, such as simpler manufacture, design, testing or stock | B1 |
| 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. | |
| Question 17[5 marks] | |
|---|---|
| Answer or working | Marks |
| path starting A-C | A1 |
| continuing C-B | A1 |
| finishing B-D. | A1 |
| distance 6 | A1 |
| 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). | |
| Question 18[2 marks] | |
|---|---|
| Answer or working | Marks |
| showing valid laws for a complete simplification, such as distributivity, complementarity and identity; accept any valid derivation | M1 |
| Y = A | A1 |
| 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. | |
| Question 19[5 marks] | |
|---|---|
| Answer or working | Marks |
| the input quote ending the intended surname string | B1 |
| the added OR comparison being always true | B1 |
| explaining that every Student row therefore satisfies the predicate | B1 |
| fixed query text with user input bound separately as a parameter | B1 |
| explaining that bound input is literal data, so its quotes and OR text cannot alter SQL syntax | B1 |
| 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. | |
| Question 20[6 marks] | |
|---|---|
| Answer or working | Marks |
| visiting M, then moving to its first unvisited neighbour alphabetically, N | M1 |
| moving from N to its only unvisited neighbour, P | M1 |
| moving from P to its first unvisited neighbour alphabetically, O, before Q | M1 |
| backtracking from O to P, since O has no unvisited neighbours | A1 |
| moving from P to its remaining unvisited neighbour, Q | A1 |
| 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. | |