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 Topic Workbooks · Book 2 of 2

A Level Computer Science Topic Workbook 2

Object-Oriented Programming, Recursion and Advanced Algorithms, Elements of Computational Thinking and 6 more

Level
A Level · AQA 7517 · OCR H446
Series
A Level Computer Science Topic Workbooks, book 2 of 2
Suitable for
Years 12-13, AQA / OCR
FreePDF download · 2027 edition · 103 A4 pages
  • One file, prints straight to A4
  • No account, no password

Workbooks like this one, with 9 topics, 89 questions and mark schemes at the back, are usually printed and sold by publishers. This one is one of 558 free PDFs on the shelf.

Pages
103 A4 pages
Chapters
9 worksheet chapters
Questions
89 · 854 marks
Answers
From page 70
Working time
About 17h 5m

What is inside

9 chapters · answers from p70

Each chapter starts with a page showing its marks and a suggested time, followed by the questions. The mark schemes for all 9 chapters are at the back, so the book works for homework, a timed test or revision.

  1. 01Object-Oriented Programming8 questions · 96 marks · about 115 min Topic guide: Object-Oriented Programmingp3
  2. 02Recursion and Advanced Algorithms9 questions · 81 marks · about 95 min Topic guide: Recursion and Advanced Algorithmsp8
  3. 03Elements of Computational Thinking11 questions · 103 marks · about 125 min Topic guide: Elements of Computational Thinkingp15
  4. 04Problem Solving and Programming10 questions · 115 marks · about 135 min Topic guide: Problem Solving and Programmingp23
  5. 05Algorithms: Complexity, Searching and Sorting9 questions · 79 marks · about 95 min Topic guide: Algorithms: Complexity, Searching and Sortingp31
  6. 06Programming Paradigms and OOP9 questions · 61 marks · about 75 min Topic guide: Programming Paradigms and OOPp39
  7. 07Data Structures and Their Operations10 questions · 92 marks · about 110 min Topic guide: Data Structures and Their Operationsp46
  8. 08Advanced Algorithms: Searching, Sorting and Path-Finding9 questions · 99 marks · about 120 min Topic guide: Advanced Algorithms: Searching, Sorting and Path-Findingp52
  9. 09Data Representation and Theory of Computation14 questions · 128 marks · about 155 min Topic guide: Data Representation and Theory of Computationp61
  10. AnswersMark schemes for every chapterp70

Each chapter is drawn from one of our worksheet packs. Follow a chapter title for the full pack on its own page, or browse every A Level Computer Science pack. Every book on the shelf is a complete printable workbook of up to 120 A4 pages.

Explore this volume

A Level Computer Science Topic Workbook 2 includes Object-Oriented Programming (from page 3); Recursion and Advanced Algorithms (from page 8); Elements of Computational Thinking (from page 15); Problem Solving and Programming (from page 23); Algorithms: Complexity, Searching and Sorting (from page 31); Programming Paradigms and OOP (from page 39); Data Structures and Their Operations (from page 46); Advanced Algorithms: Searching, Sorting and Path-Finding (from page 52); Data Representation and Theory of Computation (from page 61).

Worked question 13 - Data Representation and Theory of Computation

Open the included worksheet

Data representation and the theory of computation

Original questions written for Revision Library.

This worksheet covers three related strands of the AQA A-Level Computer Science specification. Questions 1, 3, 4, 7, 8 and 14 cover how computers represent numbers: unsigned binary and hexadecimal, two's complement for negative integers, fixed-point binary, and floating-point representation (normalisation, range and precision). Questions 5, 9 and 10 cover how computers represent other kinds of data: characters (ASCII and Unicode), sound (sampling rate and bit depth) and bitmap images (resolution, colour depth and compression). Questions 6 and 11 cover Boolean algebra: the laws used to simplify logic expressions, and deriving a simplified expression directly from a truth table. Questions 2, 12 and 13 cover finite state machines (FSMs) as a model of computation, including tracing, constructing and evaluating them.

A software engineer is deciding whether to model a new lift (elevator) control system as a finite state machine. Discuss the benefits and limitations of using a finite state machine to model a real-world system such as this, and identify one feature of a real lift control system that a simple finite state machine (as used in Questions 2 and 12) might struggle to capture.

Answer and mark scheme

Question 13

CreditAnswer or working
5-6Level 3 A clear, well-developed discussion identifies at least one accurate benefit and one accurate limitation of FSM modelling, with specific, correct reference to a feature of a lift control system an FSM would struggle to capture.
3-4Level 2 Some accurate benefit(s) and/or limitation(s) are given, but the discussion is less developed or the link to the lift example is generic or limited.
1-2Level 1 A basic, undeveloped statement about FSMs is made, with little or no application to the lift example.
0Level 0 No creditable content.
  • Indicative content:
    • Benefit: an FSM gives a precise, unambiguous model of every state the system can be in and every transition between them, which can be systematically checked for completeness (e.g. every state has a defined transition for every input) and used to design and test the control logic methodically.
    • Benefit: because an FSM has a strictly finite number of states, its behaviour is fully predictable and can, in principle, be exhaustively traced or tested, which is valuable for a safety-critical control system such as a lift.
    • Limitation: an FSM's number of states is fixed and finite; if a system needs to remember or count an arbitrarily large or varying amount of information, rather than simply being in one of a small number of states, this either cannot be modelled exactly by a small FSM, or requires an impractically large number of states.
    • Applied to the lift: a lift may need to service several floor requests queued at once (e.g. requests from several different floors pending together) and decide an efficient order to visit them; a simple FSM state only records where the lift currently is or what it is currently doing, not the full combination of which floors currently have outstanding requests, so modelling every possible combination of pending requests would need a separate state for every combination, which does not scale well as the number of floors increases.
    • Valid overall conclusion: FSMs remain a useful model for the lift's basic modes (e.g. moving up, moving down, idle, doors open) but a full lift controller in practice usually needs extra memory or logic beyond a pure FSM to track multiple pending requests.

Answer: Extended, levels-marked response: award marks holistically against the levels of response grid, using the indicative content as a guide to creditable points; there is no single correct wording.

Question 11 - Data Representation and Theory of Computation

Open the included worksheet

Data representation and the theory of computation

Original questions written for Revision Library.

This worksheet covers three related strands of the AQA A-Level Computer Science specification. Questions 1, 3, 4, 7, 8 and 14 cover how computers represent numbers: unsigned binary and hexadecimal, two's complement for negative integers, fixed-point binary, and floating-point representation (normalisation, range and precision). Questions 5, 9 and 10 cover how computers represent other kinds of data: characters (ASCII and Unicode), sound (sampling rate and bit depth) and bitmap images (resolution, colour depth and compression). Questions 6 and 11 cover Boolean algebra: the laws used to simplify logic expressions, and deriving a simplified expression directly from a truth table. Questions 2, 12 and 13 cover finite state machines (FSMs) as a model of computation, including tracing, constructing and evaluating them.

A school's 3D-printer enclosure uses three independent temperature sensors, giving fault signals X, Y and Z (each equal to 1 if that sensor detects an over-temperature fault, 0 otherwise). To avoid a single faulty sensor triggering a false alarm, the enclosure's alarm output A uses majority voting: A = 1 only when at least two of the three sensors (X, Y, Z) report a fault.
(a)Complete the truth table for the alarm output A, for all 8 combinations of X, Y and Z.(3)
(b)Write the Boolean expression for A in sum-of-products (SOP) form, directly from the truth table (one AND term for each row where A=1, combined with OR).(3)
(c)Simplify this Boolean expression using Boolean algebra laws (or otherwise), showing your working, to show that A = X.Y + Y.Z + X.Z.(4)

Answer and mark scheme

Question 11

CreditAnswer or working
B1(a) A=0 correctly given for every row with zero or exactly one fault signal set to 1 (rows 000, 001, 010, 100)
B1(a) A=1 correctly given for every row with exactly two fault signals set to 1 (rows 011, 101, 110)
B1(a) A=1 correctly given for the row with all three fault signals set to 1 (row 111)
B1(b) the four rows where A=1 correctly identified: (0,1,1), (1,0,1), (1,1,0), (1,1,1)
B1(b) each row correctly written as an AND term with correct complementation, e.g. X'.Y.Z for (0,1,1)
B1(b) all four terms correctly combined with OR: A = X'.Y.Z + X.Y'.Z + X.Y.Z' + X.Y.Z
M1(c) recognises the idempotent law (X.Y.Z = X.Y.Z + X.Y.Z + X.Y.Z), allowing X.Y.Z to be paired with each of the other three terms
M1(c) each pair correctly factorised using the distributive law, e.g. X'.Y.Z + X.Y.Z = Y.Z.(X'+X)
M1(c) complement law and identity law correctly applied to each pair, e.g. X'+X=1, so Y.Z.(X'+X) = Y.Z
A1(c) A = X.Y + Y.Z + X.Z correctly given as the final simplified expression cao
  • (a) Answer:
    X Y ZA
    0 0 00
    0 0 10
    0 1 00
    0 1 11
    1 0 00
    1 0 11
    1 1 01
    1 1 11
  • (b) Answer: A = X'.Y.Z + X.Y'.Z + X.Y.Z' + X.Y.Z
  • (c) Answer: A = X.Y + Y.Z + X.Z

Question 12 - Data Representation and Theory of Computation

Open the included worksheet

Data representation and the theory of computation

Original questions written for Revision Library.

This worksheet covers three related strands of the AQA A-Level Computer Science specification. Questions 1, 3, 4, 7, 8 and 14 cover how computers represent numbers: unsigned binary and hexadecimal, two's complement for negative integers, fixed-point binary, and floating-point representation (normalisation, range and precision). Questions 5, 9 and 10 cover how computers represent other kinds of data: characters (ASCII and Unicode), sound (sampling rate and bit depth) and bitmap images (resolution, colour depth and compression). Questions 6 and 11 cover Boolean algebra: the laws used to simplify logic expressions, and deriving a simplified expression directly from a truth table. Questions 2, 12 and 13 cover finite state machines (FSMs) as a model of computation, including tracing, constructing and evaluating them.

A vending machine's control logic is to be designed as a finite state machine (FSM) that accepts only input strings (sequences of button presses, each either A or B) ending in 'AB', i.e. whose last two symbols, in order, are A followed by B. For example, AB, BAB and AAB should be accepted, but A, B, BA and ABA should not.
(a)Draw a state transition diagram (or an equivalent transition table) for a deterministic finite state machine (DFA) with three states, S0, S1 and S2, that accepts exactly the strings ending in 'AB'. Label the start state, the accepting (final) state, and every transition.(6)
(b)Use your FSM from part (a) to trace the input string BABAB, stating whether it is accepted or rejected, and explaining your reasoning by reference to the states visited.(3)
(c)State one difference between a deterministic finite state machine (DFA) and a non-deterministic finite state machine (NFA), and explain why every NFA can always be converted into an equivalent DFA.(3)

Answer and mark scheme

Question 12

CreditAnswer or working
B1(a) S0 correctly labelled as the start state
B1(a) S2 correctly labelled as the only accepting/final state
B1(a) correct transitions from S0: A -> S1, B -> S0
B1(a) correct transitions from S1: A -> S1, B -> S2
B1(a) correct transitions from S2: A -> S1, B -> S0
B1(a) every state has exactly one transition defined for each input (confirming a valid, complete DFA)
M1(b) correct sequence of states shown: S0, S0, S1, S2, S1, S2
A1(b) correctly concludes ACCEPTED, ft from their FSM in part (a)
B1(b) correct reasoning: the final state reached, S2, is the accepting state, because the last two symbols of BABAB are A then B
B1(c) correct difference: in a DFA every state has exactly one transition defined for each input symbol, whereas in an NFA a state may have zero, more than one, or empty (epsilon) transitions for the same input (oe)
B1(c) correctly states that NFAs and DFAs are equivalent in what they can recognise, i.e. they recognise exactly the same class of languages (regular languages) (oe)
B1(c) correctly references a conversion method, e.g. the subset construction, which builds a DFA whose states represent sets of NFA states that could be reached simultaneously (oe)
  • (a) Answer: Transition table (equivalent to the diagram): S0 (start), on A -> S1, on B -> S0. S1, on A -> S1, on B -> S2 (accepting). S2 (accepting, final), on A -> S1, on B -> S0.
  • (b) Answer: S0 -B-> S0 -A-> S1 -B-> S2 -A-> S1 -B-> S2. Accepted, since the final state, S2, is the accepting state (the string ends in AB).
  • (c) Answer: DFA: exactly one transition per state per input. NFA: can have zero, more than one, or epsilon transitions per state per input. Every NFA can be converted to an equivalent DFA (they recognise the same class of languages) using a method such as the subset construction, where each DFA state represents a set of possible NFA states.

Question 7 - Programming Paradigms and OOP

Open the included worksheet

A small business owner in Cardiff is developing a new student grade-tracking system for a secondary school. They are deciding whether to use the procedural paradigm or the object-oriented paradigm to build it. The system must store many students' names, subjects and marks, calculate averages and grade boundaries, and will be extended over several years by different developers as new features (e.g. attendance tracking) are added.
(a)Compare and contrast the procedural and object-oriented approaches for developing this grade-tracking system, discussing at least two relevant factors (for example: maintainability, code reuse, protection of data, or suitability for a system that will be extended by a team of developers over time).(8)

Answer and mark scheme

Question 7

CreditAnswer or working
1-2(a) L1 Basic, isolated points are made about procedural and/or object-oriented programming, with little or no reference to the grade-tracking scenario. The answer may simply define the paradigms with no comparison.
3-5(a) L2 Some relevant points of comparison are made between procedural and object-oriented approaches (e.g. data protection, code reuse), with limited application to the specific scenario of a school system extended over time by multiple developers.
6-8(a) L3 A clear, well-balanced comparison is given, correctly weighing at least two relevant factors (such as encapsulation/data protection, code reuse via inheritance, and maintainability by multiple developers over time), with a reasoned overall judgement clearly applied to the school grade-tracking scenario.
  • (a) Indicative content:
    • A procedural approach would store student data in arrays/records and use separate procedures/functions (e.g. CalculateAverage, AssignGrade) to act on that data; this can be quick to write initially but the data is not protected, so any procedure anywhere in the program could accidentally corrupt a student's marks.
    • An object-oriented approach would define a Student class encapsulating each student's own name, subjects and marks as private attributes, with public methods (e.g. AddMark, CalculateAverage) controlling how that data is read or changed, reducing the risk of accidental corruption.
    • Inheritance in OOP would allow, for example, a SixthFormStudent subclass to reuse and extend the base Student class (adding UCAS-related attributes) without duplicating existing code, whereas a procedural approach would likely need separate, duplicated procedures or extra conditional branches for different student types.
    • Because the system will be extended over several years by different developers, OOP's encapsulation makes it easier for a new developer to safely add features (e.g. attendance tracking) as a new class or subclass without fully understanding or risking every existing procedure, whereas procedural code with shared global data can be harder to safely extend as the system grows (increased coupling).
    • A counter-point: for a small, simple, one-off program the procedural approach may be quicker to write and easier for a single developer to follow, since OOP's class design adds some initial overhead; the choice depends on the scale and expected lifetime/team size of the project.
    • Overall judgement: given that this system is expected to grow over several years with multiple developers, the object-oriented approach is generally more appropriate, mainly due to better data protection (encapsulation) and easier code reuse/extension (inheritance and polymorphism).
  • (a) Answer: Best answers weigh encapsulation/data protection and reuse via inheritance (favouring OOP for a multi-year, multi-developer school system) against the simplicity of procedural code for small one-off tasks, reaching a reasoned overall recommendation for this scenario.

Question 6 - Programming Paradigms and OOP

Open the included worksheet

A vehicle-hire company in Oxford models its fleet using the classes below.
CLASS Vehicle
  PROTECTED make : STRING

PUBLIC PROCEDURE NEW(m)
    make <- m
  ENDPROCEDURE

PUBLIC FUNCTION Describe() RETURNS STRING
    RETURN make + ": generic vehicle"
  ENDFUNCTION
ENDCLASS

CLASS Car INHERITS Vehicle
  PUBLIC FUNCTION Describe() RETURNS STRING
    RETURN make + ": car, 4 wheels"
  ENDFUNCTION
ENDCLASS

CLASS Motorbike INHERITS Vehicle
  PUBLIC FUNCTION Describe() RETURNS STRING
    RETURN make + ": motorbike, 2 wheels"
  ENDFUNCTION
ENDCLASS

The following driver program is then run:
fleet <- []
fleet.APPEND(NEW Vehicle("Generic Co"))
fleet.APPEND(NEW Car("Skoda"))
fleet.APPEND(NEW Motorbike("Triumph"))
FOR EACH v IN fleet
  OUTPUT v.Describe()
NEXT v
(a)State the three lines of output produced by the driver program, in the order they are produced.(4)
(b)Explain why the second and third lines of output use the overridden versions of Describe() in Car and Motorbike, rather than the version defined in Vehicle, even though the loop only ever calls v.Describe().(4)

Answer and mark scheme

Question 6

CreditAnswer or working
B1(a) "Generic Co: generic vehicle"
B1(a) "Skoda: car, 4 wheels"
B1(a) "Triumph: motorbike, 2 wheels"
B1(a) all three lines given in the correct order matching the order objects were appended to fleet
B1(b) each element of fleet is declared/stored as a Vehicle type but actually refers to an object of its real (sub)class, Car or Motorbike (oe)
B1(b) when v.Describe() is called, the program does not simply use Vehicle's method because the object's actual class defines its own version (oe)
B1(b) this is dynamic (run-time) method binding/dispatch, where the version of the method that is run is decided by the object's actual class at run time, not by the declared type used to store the reference (oe)
B1(b) this is exactly what allows polymorphism: the same call v.Describe() behaves differently depending on which class of object v actually refers to at that point in the loop (oe)
  • (a) Answer:Generic Co: generic vehicle
    Skoda: car, 4 wheels
    Triumph: motorbike, 2 wheels
  • (b) Answer: Each element of fleet is stored using the general Vehicle type, but it actually refers to an object of its true class, Car or Motorbike. When v.Describe() is called, dynamic (run-time) method binding means the version that runs is chosen according to the object's real class, not its declared type, so Car's and Motorbike's own overridden Describe() methods are used. This is exactly what allows the same call v.Describe() to behave differently for each object, which is polymorphism in action.

A Level Computer Science Topic Workbooks runs to 2 volumes

Book 2 of 2 · 200 pages in the set

Each book is a separate free PDF.

Volume 1

97 pp · 102 Qs

Structure and Function of the Processor, Types of Software and Development Methodologies, Exchanging Data: Databases, Networks and Web Technologies and 7 more

Volume 2 · this book

103 pp · 89 Qs

Object-Oriented Programming, Recursion and Advanced Algorithms, Elements of Computational Thinking and 6 more

More A Level books

A Level Computer Science 10-Minute Tests

56 pp · 18 Qs

Structure and Function of the Processor, Types of Software and Development Methodologies, Exchanging Data: Databases, Networks and Web Technologies and 14 more