Paper 4 Flashcards
Binary search
Reprated checking of the middle item in an ordered search list and discarding the half of the list which does not contain the search item.
Abstract data type
A collection of data eith associated operations.
Node
Element of a list
Pointer
A variable that stores the address of the node it points to.
Null pointer
A pointer that does not point at anything.
Start pointer
A variable that stores the address of the first element of a linked list.
Decision table
A precise way of modelling logic
Finite State Machine (FSM)
A machine that consists of a fixed set of possible states with a set of inputs that change the state and a set of possible outputs.
State-transition table
A table that gives information about the states of an FSM.
State-transition diagram
A diagram that describes the behaviour of an FSM.
Recursive routine
A function or procedure defined in terms of itself.
Base case
An explicit solution to a recursive function.
General case
A definition of a recursive function in terms of itself.
Random file
A file that stores records at specific addresses that can be accessed directly.
Encapsulation
Combining data and subroutines into a class.
Class
A type that combines a record with the methods that operate on the properties in the record.
Attributes
The data items of a class.
Methods
The subroutines of a class.
Object
An instance of a class.
Constructor
A special type of method that is called to create a new object and initialise its attributes.
Inheritance
All attributes and methods of the base class are copied to the subclass.
Abstract class
A base class that is never used to create objects directly.
Polymorphism
The method behaves differently for different classes in the hierarchy.
Containment
A relationship in which one class has a component that is of another class type.