A Level Computer Science Short Paper A
Covers Linear Data Structures, Trees and Graphs, Searching and Sorting Algorithms and 3 more.
Questions
Question 1 [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 2 [3 marks]
Algorithmic Complexity
A program contains the following pseudocode, where n is the length of list:
FOR i = 1 TO n
FOR j = 1 TO n
total = total + list[i] * list[j]
NEXT j
NEXT i
State the time complexity of this code in Big O notation, and explain how the nested loops lead to this complexity.
Question 3 [3 marks]
Trees and Graphs
A graph has vertices A, B, C, D and undirected edges A-B, A-C, B-C, C-D.
State the degree of vertex C, and explain what the degree of a vertex means.
Question 4 [4 marks]
Programming Paradigms
Prolog is a logic programming language in which a program consists of facts and rules, and a query asks the system to find values that satisfy them.
State what is meant by logic programming, and give one example each of a fact and a rule that might appear in a simple Prolog program about family relationships.
Question 5 [3 marks]
Algorithmic Complexity
A linear search and a binary search are both available to search a sorted list of 1,000,000 items.
Explain why a binary search is more efficient than a linear search for this list, referring to their time complexities.
Question 6 [5 marks]
Theory of Computation
A problem is described as intractable if no known algorithm can solve every instance of it in polynomial time, even though an algorithm that always eventually finds the correct answer does exist.
Explain the difference between an intractable problem and an undecidable problem, and give one example of a problem generally considered intractable.
Question 7 [5 marks]
Searching and Sorting Algorithms
A sorting algorithm is described as stable if two elements that compare as equal always keep their original relative order after sorting.
A list of exam entries is sorted by grade: (Alex, grade B), (Bo, grade A), (Casey, grade B). A stable sort by grade should keep Alex before Casey in the result, since they are both grade B and Alex appeared first.
Explain why a stable sort matters in this scenario, and state whether a standard bubble sort, which only swaps adjacent elements that are strictly out of order, is stable.
Question 8 [5 marks]
Linear Data Structures
A singly linked list stores each node as a value and a pointer to the next node. The list currently holds, in order, 6 -> 14 -> 21 -> 35, with a head pointer to the node holding 6.
Describe, as a sequence of steps, how the node holding 21 is removed so the list becomes 6 -> 14 -> 35. You do not need to write code.
Question 9 [4 marks]
Algorithmic Complexity
Four algorithms have time complexities O(log n), O(n), O(n log n) and O(n^2).
Order these four complexities from most efficient to least efficient for large values of n, and identify which of the four would be the best choice for sorting a very large list, given that general comparison-based sorting needs at least a constant multiple of n log n comparisons in the worst case.
Question 10 [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 |
| 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 2[3 marks] | |
|---|---|
| Answer or working | Marks |
| recognising the inner loop runs n times for each iteration of the outer loop | M1 |
| recognising the total number of iterations is n multiplied by n | M1 |
| O(n^2) | A1 |
| Question 3[3 marks] | |
|---|---|
| Answer or working | Marks |
| stating the degree of a vertex is the number of edges connected to (incident on) it | B1 |
| counting the edges at C: A-C, B-C and C-D | M1 |
| a degree of 3 Award all 3 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 degree and its meaning are requested. Naming each incident edge is optional evidence of the count. | A1 |
| Final answer: C has degree 3: it is incident to edges C-A, C-B and C-D. Degree counts edges incident to a vertex. | |
| Question 4[4 marks] | |
|---|---|
| Answer or working | Marks |
| defining logic programming through facts and rules and answering queries by inference: B1 for facts/rules and B1 for query solving 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 |
| one valid family-relationship fact, such as parent(alice,bob). | B1 |
| one valid family-relationship rule, such as grandparent(X,Z) :- parent(X,Y), parent(Y,Z). No further declarative-versus-imperative comparison is required. | B1 |
| Final answer: Logic programming expresses facts and rules and answers queries by inference, e.g. fact parent(mary, sam); rule grandparent(X, Y) :- parent(X, Z), parent(Z, Y) | |
| Question 5[3 marks] | |
|---|---|
| Answer or working | Marks |
| stating linear search is O(n) and binary search is O(log n) | B1 |
| explaining binary search halves the search space at each step, rather than checking one element at a time | B1 |
| a valid comparison, such as binary search needing at most around 20 comparisons, against up to 1,000,000 for linear search | B1 |
| Final answer: Binary search is O(log n) against linear search's O(n): it halves the remaining list each step, so far fewer comparisons are needed for a large list | |
| Question 6[5 marks] | |
|---|---|
| Answer or working | Marks |
| explaining that an intractable problem is decidable in principle | B1 |
| explaining that no polynomial-time algorithm for all instances is known under the stated convention | B1 |
| explaining that an undecidable problem has no always-terminating correct algorithm for every instance | B1 |
| distinguishing computational expense from the nonexistence of a universal decider | B1 |
| giving one valid generally considered intractable example, such as decision travelling salesman, SAT or subset sum; no explanation of the example or heuristic is required | B1 |
| Final answer: Intractable problems have a decider but no known polynomial-time algorithm for all instances; undecidable problems have no universal terminating correct decider. The decision travelling-salesman problem (a tour within a bound) is generally considered intractable: finite exhaustive search terminates but is not polynomial. General halting is undecidable. | |
| Question 7[5 marks] | |
|---|---|
| Answer or working | Marks |
| identifying equal-grade entries as the relevant group | B1 |
| explaining that stability preserves their original relative order. Accept any equivalent valid explanation, without inventing a submission-order context. | B1 |
| applying that preservation to Alex and Casey | B1 |
| keeping Alex before Casey. Award both marks for Alex stays before Casey, or an equivalent contextual explanation. A separate account of what an unstable sort might do is optional. | B1 |
| stating that standard bubble sort is stable. Explaining why bubble sort is stable is optional. Award all 5 marks for preserving the original order of equal-grade entries, keeping Alex before Casey, and stating that standard bubble sort is stable. | B1 |
| Final answer: Stability preserves the original order of equal-grade entries, keeping Alex before Casey. Standard bubble sort is stable. | |
| Question 8[5 marks] | |
|---|---|
| Answer or working | Marks |
| traversing from the head until the node holding 14 is reached, the node before 21 | B1 |
| reading the pointer stored in the node holding 21, which points to the node holding 35 | B1 |
| setting the pointer of the node holding 14 to point to the node holding 35, skipping over 21 | B1 |
| the node holding 21 now being unreachable and able to be discarded | B1 |
| confirming the list now correctly reads 6, 14, 35 Award all 5 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. Locating the predecessor, bypassing the node and the resulting list are within the requested deletion sequence. Discarding may mean permitting garbage collection; explicit free is not required. | B1 |
| Final answer: Locate predecessor 14 and bypass 21 by setting 14.next to 21.next (35). The list is 6 -> 14 -> 35. Reclaim the removed node if the memory model requires it; garbage collection is also valid. | |
| Question 9[4 marks] | |
|---|---|
| Answer or working | Marks |
| placing O(log n) before O(n) in increasing growth order | M1 |
| the complete order O(log n), O(n), O(n log n), O(n^2), from most to least efficient | A1 |
| identifying O(n log n) as the best listed choice for general comparison-based sorting; no separate reason is required This row begins a shared allocation of 2 marks for the same requested result or explanation. | A1 |
| 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. | A1 |
| Final answer: Most to least efficient: O(log n), O(n), O(n log n), O(n^2); O(n log n) is the best achievable for sorting a large list | |
| Question 10[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. | |