A Level Computer Science Exam Questions and Answers Latest Update 2025 Already Passed
Abstraction - Answers Representation that is arrived at by removing unnecessary details
Computational complexity of algorithms - Answers Measures how economical the algorithm is with time
and space
Time complexity of algorithms - Answers Indicates how fast an algorithm runs
Space complexity of algorithms - Answers Indicates how much memory an algorithm needs
Big O notation - Answers Order of complexity of an algorithm
Exponential time algorithm - Answers An algorithm whose execution time grows exponentially with
input size
Polynomial time algorithm - Answers An algorithm whose execution time grows as a polynomial of input
size
Linear time algorithm - Answers A polynomial time algorithm that executes in O(n) time
Non-computable problems - Answers Describes an algorithmic problem that admits no algorithm
Intractable problems - Answers Problems for which no reasonable (polynomial) time solution has yet
been found (e.g. Travelling Salesman)
Tractable problems - Answers Problems that have reasonable (polynomial) time solutions as the size of
input increases
Heuristic approach - Answers Uses know-how and experience to make informed guesses that assist in
finding a polynomial time solution as an approximation to an intractable problem
Halting problem - Answers The unsolvable problem of determining whether any program will eventually
stop given particular input
Turing Machine - Answers A Finite State Machine that control one or more tapes, where at least one
tape is of infinite length
Universal Turing Machine - Answers An interpreter that reads the description of any arbitrary Turing
Machine and faithfully executes operations on data
Finite State Automata - Answers FSM with no output
Mealey machine - Answers FSM with output, where output is associated with a transition
Moore machine - Answers FSM with output, where output is associated with a state
, State transition diagram - Answers A directed graph whose nodes represent the states, and the
transitons are labelled with the inputs and outputs (if any)
Regular expressions - Answers A notation for defining all the valid strings of a formal language or a
special text string for describing a search pattern
Backus-Naur Form - Answers A notation for expressing the rules for constructing valid strings in a regular
language
Parse tree - Answers A pictorial representation showing how a valid sentence conforms to the rules of a
BNF notation
Syntax diagrams - Answers A way of defining the syntax rules of a language
Infix notation - Answers Artithmetic expression with operator between operands
Reverse Polish notation - Answers Postfix notation - operands are followed by their operator
Procedural (Imperative) programming - Answers Programs executed by the processor in the order
defined by the programmer
Event-driven programming - Answers Subroutines are executed in response to events, e.g. clicking
buttons, choosing menu options
Object-oriented programming - Answers Breaking down a problem into smaller problems until routines
can be written that execute single tasks
Class definition - Answers A template that can be used to create objects of that class
Instantiation - Answers An object is defined based on a class
Encapsulation - Answers Combining a record with the procedures and functions that manipulate it
Inheritance - Answers Defining a class then using it to build a hierarchy of decendant classes which
inherit access to all its code and data
Recursion - Answers A routine that is defined in terms of itself
General case - Answers A recursive solution for a value n
Base case - Answers A value for a recursive routine that does involve the general case
Abstract data type - Answers A data type whose propeerties are specified independently of any
particular programming language
List - Answers A collection of elements with an inherent order
Abstraction - Answers Representation that is arrived at by removing unnecessary details
Computational complexity of algorithms - Answers Measures how economical the algorithm is with time
and space
Time complexity of algorithms - Answers Indicates how fast an algorithm runs
Space complexity of algorithms - Answers Indicates how much memory an algorithm needs
Big O notation - Answers Order of complexity of an algorithm
Exponential time algorithm - Answers An algorithm whose execution time grows exponentially with
input size
Polynomial time algorithm - Answers An algorithm whose execution time grows as a polynomial of input
size
Linear time algorithm - Answers A polynomial time algorithm that executes in O(n) time
Non-computable problems - Answers Describes an algorithmic problem that admits no algorithm
Intractable problems - Answers Problems for which no reasonable (polynomial) time solution has yet
been found (e.g. Travelling Salesman)
Tractable problems - Answers Problems that have reasonable (polynomial) time solutions as the size of
input increases
Heuristic approach - Answers Uses know-how and experience to make informed guesses that assist in
finding a polynomial time solution as an approximation to an intractable problem
Halting problem - Answers The unsolvable problem of determining whether any program will eventually
stop given particular input
Turing Machine - Answers A Finite State Machine that control one or more tapes, where at least one
tape is of infinite length
Universal Turing Machine - Answers An interpreter that reads the description of any arbitrary Turing
Machine and faithfully executes operations on data
Finite State Automata - Answers FSM with no output
Mealey machine - Answers FSM with output, where output is associated with a transition
Moore machine - Answers FSM with output, where output is associated with a state
, State transition diagram - Answers A directed graph whose nodes represent the states, and the
transitons are labelled with the inputs and outputs (if any)
Regular expressions - Answers A notation for defining all the valid strings of a formal language or a
special text string for describing a search pattern
Backus-Naur Form - Answers A notation for expressing the rules for constructing valid strings in a regular
language
Parse tree - Answers A pictorial representation showing how a valid sentence conforms to the rules of a
BNF notation
Syntax diagrams - Answers A way of defining the syntax rules of a language
Infix notation - Answers Artithmetic expression with operator between operands
Reverse Polish notation - Answers Postfix notation - operands are followed by their operator
Procedural (Imperative) programming - Answers Programs executed by the processor in the order
defined by the programmer
Event-driven programming - Answers Subroutines are executed in response to events, e.g. clicking
buttons, choosing menu options
Object-oriented programming - Answers Breaking down a problem into smaller problems until routines
can be written that execute single tasks
Class definition - Answers A template that can be used to create objects of that class
Instantiation - Answers An object is defined based on a class
Encapsulation - Answers Combining a record with the procedures and functions that manipulate it
Inheritance - Answers Defining a class then using it to build a hierarchy of decendant classes which
inherit access to all its code and data
Recursion - Answers A routine that is defined in terms of itself
General case - Answers A recursive solution for a value n
Base case - Answers A value for a recursive routine that does involve the general case
Abstract data type - Answers A data type whose propeerties are specified independently of any
particular programming language
List - Answers A collection of elements with an inherent order
