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 Short Paper A

Covers Linear Data Structures, Trees and Graphs, Searching and Sorting Algorithms and 3 more.

10 questions - 40 marks

Download PDF

Open A Level Computer Science workspace

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

Mark scheme for Question 1 [2 marks]
Question 1[2 marks]
Answer or workingMarks
a definition such as: abstraction presents a simplified view of an object, showing only what it does rather than how it does it internallyB1
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 complexityB1
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
Mark scheme for Question 2 [3 marks]
Question 2[3 marks]
Answer or workingMarks
recognising the inner loop runs n times for each iteration of the outer loopM1
recognising the total number of iterations is n multiplied by nM1
O(n^2)A1
Mark scheme for Question 3 [3 marks]
Question 3[3 marks]
Answer or workingMarks
stating the degree of a vertex is the number of edges connected to (incident on) itB1
counting the edges at C: A-C, B-C and C-DM1
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.
Mark scheme for Question 4 [4 marks]
Question 4[4 marks]
Answer or workingMarks
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)
Mark scheme for Question 5 [3 marks]
Question 5[3 marks]
Answer or workingMarks
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 timeB1
a valid comparison, such as binary search needing at most around 20 comparisons, against up to 1,000,000 for linear searchB1
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
Mark scheme for Question 6 [5 marks]
Question 6[5 marks]
Answer or workingMarks
explaining that an intractable problem is decidable in principleB1
explaining that no polynomial-time algorithm for all instances is known under the stated conventionB1
explaining that an undecidable problem has no always-terminating correct algorithm for every instanceB1
distinguishing computational expense from the nonexistence of a universal deciderB1
giving one valid generally considered intractable example, such as decision travelling salesman, SAT or subset sum; no explanation of the example or heuristic is requiredB1
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.
Mark scheme for Question 7 [5 marks]
Question 7[5 marks]
Answer or workingMarks
identifying equal-grade entries as the relevant groupB1
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 CaseyB1
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.
Mark scheme for Question 8 [5 marks]
Question 8[5 marks]
Answer or workingMarks
traversing from the head until the node holding 14 is reached, the node before 21B1
reading the pointer stored in the node holding 21, which points to the node holding 35B1
setting the pointer of the node holding 14 to point to the node holding 35, skipping over 21B1
the node holding 21 now being unreachable and able to be discardedB1
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.
Mark scheme for Question 9 [4 marks]
Question 9[4 marks]
Answer or workingMarks
placing O(log n) before O(n) in increasing growth orderM1
the complete order O(log n), O(n), O(n log n), O(n^2), from most to least efficientA1
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
Mark scheme for Question 10 [6 marks]
Question 10[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.