Paper 1 Theory Flashcards
Master 30 cards per day (294 cards)
1
Q
What is the concept of a data type?
A
Defined by the values it can take and the operations that can be performed on it.
2
Q
What is the definition of an integer data type?
A
A whole number, positive or negative, including zero.
3
Q
What is the definition of a real/float data type?
A
A positive or negative number which can have a fractional part.
4
Q
What is the definition of a Boolean data type?
A
A value which is either true or false.
5
Q
What is the definition of a character data type?
A
A single number, letter or symbol.
6
Q
What is the definition of a string data type?
A
A collection of characters.
7
Q
What is the definition of a date/time data type?
A
A way of storing a point in time, many different formats are used.
8
Q
What is the definition of a pointer/reference data type?
A
A way of storing memory addresses.
9
Q
What is the definition of a records data type?
A
A collection of fields, each of which could have a different data type.
10
Q
What is the definition of an arrays data type?
A
A finite, indexed set of related elements each of which has the same data type.
11
Q
What is a user-defined data type based on built-in types?
A
A data type derived from existing language-defined data types.
12
Q
In programming concepts, what is variable declaration?
A
Creating a variable for the first time, giving it a name and sometimes a data type.
13
Q
In programming concepts, what is constant declaration?
A
Creating a constant for the first time, similar to variable declaration.
14
Q
In programming concepts, what is assignment?
A
Giving a constant or variable a value.
15
Q
In programming concepts, what is iteration?
A
Repeating an instruction.
16
Q
In programming concepts, what is selection?
A
Comparing values and choosing an action based on those values.
17
Q
What is a subroutine in programming?
A
A named block of code containing a set of instructions for a frequently used operation.
18
Q
What is definite iteration?
A
Iteration where the number of repetitions is known before the loop starts.
19
Q
What is indefinite iteration?
A
Iteration where the number of repetitions is not known before the loop starts.
20
Q
What are nested structures in programming?
A
Selection or iteration structures placed within another structure.
21
Q
Why is indentation important in nested structures?
A
It makes the code easier for humans to understand.
22
Q
Why are meaningful identifier names important for constants, variables, and subroutines?
A
It makes it easier for others to understand the named object’s purpose.
23
Q
What is addition in programming?
A
Adding together two numbers.
24
Q
What is subtraction in programming?
A
Taking one number away from another.
25
What is multiplication in programming?
Timesing two numbers together.
26
What is real/float division?
Dividing one number by another.
27
What is integer division?
Real/float division, but only the whole number part is given.
28
What does the modulo operation return?
The remainder of an integer division.
29
What is exponentiation?
Raising one value to the power of another.
30
What is rounding?
Limiting the degree of accuracy of a number.
31
What is truncation?
Removing the decimal part of a number, never rounding up.
32
What is the relational operation 'equal to'?
Checking if two values are the same (e.g., = or ==).
33
What is the relational operation 'not equal to'?
Checking if two values are different (e.g., <> or !=).
34
What is the relational operation 'less than'?
Checking if one value is smaller than another (e.g., <).
35
What is the relational operation 'greater than'?
Checking if one value is larger than another (e.g., >).
36
What is the relational operation 'less than or equal to'?
Checking if one value is smaller than or the same as another (e.g., <= or =<).
37
What is the relational operation 'greater than or equal to'?
Checking if one value is larger than or the same as another (e.g., >= or =>).
38
What does the Boolean operator NOT do?
Returns the opposite of a Boolean value.
39
What does the Boolean operator AND do?
Returns true only if both input Boolean values are true.
40
What does the Boolean operator OR do?
Returns true if at least one input Boolean value is true.
41
What does the Boolean operator XOR do?
Returns true if strictly one of two input Boolean values is true.
42
What is the difference between a variable and a constant?
Variables can change value during execution; constants cannot change value once assigned.
43
What is an advantage of using named constants?
Makes code easier to understand and allows easy updates in one place.
44
What is the length string-handling operation?
Returns the number of characters in a specified string.
45
What is the position string-handling operation?
Returns the position of a specified character within a string.
46
What is the substring string-handling operation?
Returns a portion of a string given a start position and length.
47
What is concatenation?
Joining two or more strings together to form a new, longer string.
48
In string handling, what is character to character code?
Converting a character to its numerical representation (e.g., ASCII).
49
In string handling, what is character code to character?
Converting a numerical character code to its character representation.
50
What are string conversion operations?
Operations to convert between different data types and strings (e.g., integer to string).
51
How do high-level languages generate random numbers?
Using a built-in function with a seed value and mathematical operations.
52
Are computer-generated random numbers truly random?
No, they are pseudorandom, generated by an algorithm.
53
What is exception handling?
The process of dealing with unexpected events (exceptions) to avoid program crashing.
54
How does a computer handle an exception?
By pausing execution, saving state on the stack, and running a catch block.
55
What happens after an exception is handled?
The program uses the system stack to restore its state and resume execution.
56
What is a subroutine?
A named 'out of line' block of code that can be called/executed.
57
What is a procedure (subroutine type)?
A subroutine that may or may not return a value.
58
What is a function (subroutine type)?
A subroutine that is required to return a value.
59
What are advantages of using subroutines?
Reduces code repetition, makes code more compact and easier to read.
60
What is the purpose of parameters in subroutines?
To pass data between subroutines.
61
Where are parameters specified when calling a subroutine?
Within brackets after the subroutine name.
62
What is the actual value passed by a parameter called?
An argument.
63
How can subroutines that return values be used?
They can appear in expressions or be assigned to variables/parameters.
64
What are local variables?
Variables declared within a subroutine.
65
When do local variables exist?
Only while the subroutine in which they are declared is executing.
66
Where are local variables accessible?
Only within the subroutine in which they are declared.
67
Why is it good practice to use local variables?
They limit scope and avoid naming conflicts.
68
What are global variables?
Variables accessible from any part of a program.
69
How long do global variables exist in memory?
For the entire duration of the program's execution.
70
What is the role of stack frames in subroutine calls?
To store return addresses, parameters, and local variables.
71
What happens to a stack frame when a subroutine is called?
It is pushed onto the computer's call stack.
72
What happens to a stack frame when a subroutine finishes executing?
It is popped from the call stack.
73
What does a computer use stack frame information for?
To return to execution of the previous subroutine.
74
What are recursive techniques in programming?
Using subroutines defined in terms of themselves.
75
What must any recursive subroutine have?
A stopping condition (base case) that doesn't use recursion.
76
What happens if a recursive algorithm doesn't meet its base case?
It will cause a stack overflow.
77
How can problems solvable recursively often also be solved?
Using iteration.
78
Compare iterative and recursive solutions regarding ease of programming.
Iterative solutions are often easier to program.
79
Compare iterative and recursive solutions regarding code compactness.
Recursive solutions can be more compact in code.
80
What are the characteristics of the procedural programming paradigm?
Programs are sequences of instructions executed in order; uses procedures/functions, constants/variables.
81
In procedural programming, what is global scope?
Data accessible from all parts of the program.
82
In procedural programming, what is local scope?
Data accessible only within the structure where it's declared.
83
What is the structured approach to program design?
Breaking down problems into smaller tasks (modules) designed top-down.
84
What are the four basic structures used in structured programming?
Assignment, Sequence, Selection, Iteration.
85
What is an advantage of the structured approach?
Makes programs easy to understand, manage, maintain, and test.
86
What are hierarchy charts used for in programming?
To graphically represent the structure of a structured program.
87
In a hierarchy chart, what does a rectangle represent?
A procedure.
88
In a hierarchy chart, what do lines between rectangles show?
Relationships between procedures (which ones call others).
89
What are objects in object-oriented programming (OOP)?
Containers of both data (properties) and instructions (methods).
90
How are objects created from classes?
In a process called instantiation.
91
An object is defined as an...
...instance of a class.
92
What are classes in OOP?
Blueprints for objects, specifying properties and methods.
93
In a class definition, what does 'private' mean?
Method or property accessible only from within the object.
94
In a class definition, what does 'public' mean?
Method allowing access/modification of private properties from outside.
95
What is encapsulation in OOP?
Combining properties and methods into a single object entity.
96
What does an object encapsulate?
Its contents: properties and methods.
97
What is a benefit of encapsulation for large programs?
Allows development to be split across a team.
98
What is inheritance in OOP?
Allows one class to share properties and methods of another class.
99
Classes using inheritance have an 'is a' relationship. Give an example.
A 'DeLorean' *is a kind of* 'Car'.
100
What is polymorphism in OOP?
Objects are processed differently depending on their class ('many forms').
101
What is overriding in OOP?
A method in an inherited class with the same name but different implementation than the parent class.
102
What does the keyword 'override' indicate in class descriptions?
That a method's implementation differs from the inherited class.
103
What is association in OOP?
A relationship where one object forms part of another ('has a' relationship).
104
Give an example of an 'has a' relationship.
A 'Car' *has a* 'Driver'.
105
What are the two specific types of association?
Aggregation and Composition.
106
Which type of association is weaker: Aggregation or Composition?
Aggregation.
107
In aggregation, what happens to the associated object if the container object is destroyed?
It will still exist.
108
In composition, what happens to the associated object if the container object is destroyed?
It is also destroyed.
109
Why is OOP used?
Provides clear structure, makes development/testing easier, allows large projects to be divided.
110
How does OOP improve code efficiency?
Allows code (classes) to be reused.
111
What are the three main object-oriented design principles?
Encapsulate what varies, Favour composition over inheritance, Program to interfaces, not implementation.
112
According to OOP design principles, where should things likely to change be put?
Encapsulated in a class.
113
According to OOP design principles, composition is favoured over inheritance. When is inheritance still used?
In situations where composition isn't appropriate.
114
What is an interface in programming (related to OOP design)?
A collection of abstract procedures implemented by unrelated classes.
115
What is the purpose of programming to interfaces?
Allows unrelated classes to use similar methods.
116
In OOP, what are abstract methods?
Declared in abstract classes, no implementation, serve as blueprint for subclasses.
117
In OOP, what are virtual methods?
Methods in a base class that can be overridden by derived classes, supporting polymorphism.
118
In OOP, what are static methods?
Methods belonging to the class itself, called directly without needing an object instance.
119
What do class diagrams visually represent?
Relationships that exist between classes.
120
In a class diagram, how are classes represented?
By boxes.
121
What do different connectors represent in a class diagram?
Different kinds of relationships between classes.
122
How are inheritance relationships shown in class diagrams?
With unfilled arrows.
123
Which direction do inheritance arrows point in a class diagram?
From the inherited class towards the class which inherits it (upwards).
124
How is association shown in class diagrams?
With diamond headed arrows.
125
In a class diagram showing association, what does an unfilled diamond headed arrow represent?
Aggregation.
126
In a class diagram showing association, what does a filled diamond headed arrow represent?
Composition.
127
How can class diagrams contain more information than just class names?
By including properties and methods in separate boxes.
128
In a class diagram property/method box, what does a plus sign '+' indicate?
Public visibility.
129
In a class diagram property/method box, what does a minus sign '-' indicate?
Private visibility.
130
In a class diagram property/method box, what does a pound symbol '#' indicate?
Protected visibility.
131
Where are protected properties/methods accessible?
From within the declaring object and any inherited objects.
132
What is a data structure?
A container within which information is stored.
133
Why do programmers choose different data structures?
Some are better suited to different types of data or problems.
134
What is an array?
An indexed set of related elements.
135
What are characteristics of an array?
Must be finite, indexed (often starts from zero), contain elements of the same data type, can be multi-dimensional.
136
How is information typically stored by computers?
As a series of files.
137
What is a file composed of?
Records.
138
What is a record composed of?
Fields.
139
What is an Abstract Data Type (ADT)?
Doesn't exist as a data structure itself, uses other data structures to store data.
140
What does FIFO stand for?
First In, First Out.
141
Which ADT is described as FIFO?
Queue.
142
Give a typical use of a queue in computers.
Keyboard buffers.
143
What are the two pointers in a linear queue?
Front pointer and Rear pointer.
144
How is emptiness detected in a linear queue?
By comparing the front and rear pointers.
145
What is a circular queue?
A type of queue where front and rear pointers wrap around the ends.
146
What is an advantage of a circular queue over a linear queue?
More memory efficient.
147
What characterises a priority queue?
Items are assigned a priority.
148
How are items dequeued from a priority queue?
High priority items before low priority items.
149
If items in a priority queue have the same priority, in what order are they removed?
In the usual first in, first out order.
150
What does FILO stand for?
First In, Last Out.
151
Which ADT is described as FILO?
Stack.
152
How many pointers does a stack typically have?
Just one pointer: a top pointer.
153
What operations can be performed on a stack?
Push, Pop, Peek/Top, IsEmpty, IsFull.
154
What is the 'Push' operation on a stack?
Adding an item to the top.
155
What is the 'Pop' operation on a stack?
Removing the item from the top.
156
What is the 'Peek' or 'Top' operation on a stack?
Returns the value of the top item without removing it.
157
What is a stack overflow error?
Occurs if a push command is executed on a full stack.
158
What is a stack underflow error?
Occurs if a pop command is attempted on an empty stack.
159
What is a graph data structure used to represent?
Complex relationships between items within datasets.
160
What are the components of a graph?
Nodes (vertices) joined by edges (arcs).
161
What is a weighted graph?
A graph where edges have a value (weight) representing cost, distance, etc.
162
What are two ways to represent a graph?
Adjacency matrices and Adjacency lists.
163
What is an adjacency matrix?
A tabular representation where rows and columns represent nodes.
164
In an unweighted adjacency matrix, what indicates an edge exists?
1
165
In an unweighted adjacency matrix, what indicates no connection?
166
In a weighted adjacency matrix, what indicates the weight of a connection?
The value assigned to the edge.
167
In a weighted adjacency matrix, what value indicates no connection?
An arbitrarily large value (often infinity).
168
What is a characteristic visual property of adjacency matrices?
A diagonal line of 0s and diagonal symmetry (for undirected graphs).
169
What is an adjacency list?
A list representing a graph, where each node has a list of adjacent nodes.
170
Compare adjacency matrix and adjacency list regarding memory efficiency.
Matrix is less efficient (stores every possible edge), List is more efficient (stores only existing connections).
171
Compare adjacency matrix and adjacency list regarding querying a specific edge.
Matrix is time efficient (lookup by row/column), List is time inefficient (sequential search).
172
When is an adjacency matrix well suited?
For dense graphs (many edges).
173
When is an adjacency list well suited?
For sparse graphs (few edges).
174
What is a tree data structure?
A connected, undirected graph with no cycles.
175
What is a rooted tree?
A tree with one designated vertex as the root.
176
In a rooted tree, which node has no parent?
The root node.
177
In a rooted tree, what are nodes from which others stem called?
Parent nodes.
178
In a rooted tree, what are nodes with a parent called?
Child nodes.
179
In a rooted tree, what are child nodes with no children called?
Leaf nodes.
180
What is a binary tree?
A rooted tree where each node has at most two children.
181
What is a hash table?
A way of storing data allowing retrieval with constant time complexity.
182
What does a hashing algorithm do?
Takes an input and returns a hash value.
183
Is a hash unique to its input and reversible?
Unique but cannot be reversed to get the input value.
184
What do hash tables store?
Key-value pairs.
185
What is a collision in a hash table?
When different inputs produce the same hash value.
186
How are collisions handled in hash tables?
Using rehashing techniques.
187
What is rehashing?
A technique to find an available position when a collision occurs.
188
What is a dictionary data structure?
A collection of key-value pairs.
189
How are values accessed in a dictionary?
By their associated key.
190
What is an application of dictionaries?
Information retrieval or dictionary-based compression.
191
What is a vector (in data structures)?
A quantity having magnitude and direction, represented as a sequence of numbers.
192
Give one way a vector can be represented notationally.
As a list of numbers in square brackets, e.g., [12, 7, 3, 55].
193
Give another way a vector can be represented notationally.
As a function mapping indices to values, e.g., 0 -> 12.
194
Give a third way a vector can be represented notationally.
As a point in space coordinates, e.g., (12, 7, 3, 55).
195
In vector notation, what does the symbol -> mean?
Maps to.
196
What property must all entries in a vector share?
Must be drawn from the same field (e.g., real numbers R).
197
What is vector addition?
Adding corresponding components of two vectors to achieve translation.
198
What is scalar-vector multiplication?
Multiplying each component of a vector by a scalar (number).
199
How does scalar-vector multiplication affect a vector?
Changes its magnitude but not its direction.
200
What is a convex combination of two vectors a and b?
ax + by where x and y are non-zero, less than one, and add to 1.
201
What is a dot product of two vectors?
A single number derived from the components of vectors.
202
What can the dot product be used to determine?
The angle between two vectors.
203
What is the notation for the dot product of vectors a and b?
a . b (said "a dot b").
204
What are static data structures?
Structures with a fixed size, often stored in sequential memory.
205
What are dynamic data structures?
Structures that can change size, storing data alongside references.
206
Compare static and dynamic data structures regarding setup effort.
Dynamic structures require more work to set up.
207
What is graph traversal?
The process of visiting each vertex in a graph.
208
What is Depth First Search (DFS)?
Graph traversal that explores a branch fully before backtracking.
209
What data structure does Depth First Search (DFS) typically use?
A stack.
210
Give a typical use for Depth First Search (DFS).
Navigating a maze.
211
What is Breadth First Search (BFS)?
Graph traversal that explores nodes level by level before moving to the next depth.
212
What data structure does Breadth First Search (BFS) typically use?
A queue.
213
Give a typical use for Breadth First Search (BFS).
Determining the shortest path on an unweighted graph.
214
What is tree traversal?
The process of visiting/updating/outputting each node in a tree.
215
Is tree traversal an algorithm unique to trees?
Yes, it is unique to trees.
216
What shape do tree traversal paths follow visually?
Anticlockwise around the tree, starting at the root.
217
What are the three types of tree traversal algorithms?
Prefix (Pre-order), Infix (In-order), and Postfix (Post-order).
218
What does Pre-order traversal mark?
The left of each node.
219
Give a typical use for Pre-order traversal.
Copying a tree.
220
What does In-order traversal mark?
The bottom of each node.
221
For what type of tree is In-order traversal only well defined?
Binary trees.
222
Give a typical use for In-order traversal on a binary search tree.
Outputting the contents in ascending order.
223
What does Post-order traversal mark?
The right of each node.
224
Give a typical use for Post-order traversal.
Emptying a tree or converting infix to RPN.
225
What is Reverse Polish Notation (RPN)?
A way of writing expressions where operators are placed after their operands.
226
How can infix expressions be converted to RPN using tree traversal?
By traversing the expression tree using postorder traversal.
227
For simpler expressions, how can conversion to RPN be done?
By observation.
228
What is an advantage of RPN?
Eliminates the need for brackets, simplifying expressions.
229
Why is RPN well suited for computer manipulation?
It is well suited to manipulation by a stack.
230
Where is RPN used?
In interpreters based on stacks, like for Bytecode or PostScript.
231
What is a searching algorithm used for?
To find a specified data item within a set of data.
232
What is Linear Search?
Checking every item in a list one by one until the target is found.
233
Does Linear Search require the data to be in order?
No, it can be conducted on any list.
234
What is the time complexity of Linear Search?
O(n).
235
What is Binary Search?
Finding a target by repeatedly halving an *ordered* list.
236
Does Binary Search require the data to be in order?
Yes, it can only be used on ordered lists.
237
How does Binary Search locate the target?
By looking at the midpoint and comparing it to the target.
238
What is the time complexity of Binary Search?
O(log n).
239
What is Binary Tree Search?
Searching for a target by traversing a binary tree.
240
Is Binary Tree Search performed on any tree?
No, it is conducted on a binary tree.
241
What is the time complexity of Binary Tree Search?
O(log n), same as binary search.
242
What is a sorting algorithm used for?
To put the elements of an array into a specific order.
243
Why might a sorting algorithm be used before a search?
Binary search requires data to be sorted.
244
What is Bubble Sort?
Swapping adjacent items repeatedly until the array is in order.
245
What is the time complexity of Bubble Sort?
O(n^2).
246
Is Bubble Sort an efficient sorting algorithm?
No, it is considered particularly inefficient.
247
What is Merge Sort?
A 'divide and conquer' sorting algorithm.
248
How does Merge Sort work?
Divides the array into single-element arrays, then merges them back sorted.
249
What is the time complexity of Merge Sort?
O(nlogn).
250
Is Merge Sort an efficient sorting algorithm?
Yes, it is an efficient algorithm.
251
What is Dijkstra's algorithm used for?
Finding the shortest path from a starting node to every other node in a network.
252
Is Dijkstra's algorithm for weighted or unweighted graphs?
Weighted graphs.
253
What data structure is used with Dijkstra's algorithm to keep track of visited nodes?
A priority queue.
254
Give an application of Dijkstra's algorithm.
Satellite navigation systems to find shortest routes.
255
Give another application of Dijkstra's algorithm.
Used in routers to send packets via the fastest route.
256
What is problem-solving?
The process of finding a solution to a difficult or complex issue.
257
What is an algorithm?
A sequence of steps that can be followed to complete a task.
258
What is a key property of an algorithm regarding termination?
It must always terminate (not run forever in a loop).
259
What is pseudocode?
A way of describing instructions independent of a specific programming language.
260
What are the standard constructs used in pseudocode?
Sequence, assignment, selection, iteration.
261
What does a hand-trace of an algorithm involve?
Stepping through the algorithm's execution manually.
262
What is the process of converting pseudocode to program code?
Implementing the algorithm in a high-level language.
263
What is abstraction (in computations)?
Removing unnecessary details to focus on essential characteristics.
264
What is representational abstraction?
Abstraction achieved by removing unnecessary details from a representation.
265
What is abstraction by generalisation or categorisation?
Grouping common characteristics to form a hierarchical 'is a kind of' relationship.
266
What is information hiding?
Hiding details of an object that don't contribute to its essential characteristics.
267
What is procedural abstraction?
Representing a computational method by breaking down a complex model into procedures.
268
What is functional abstraction?
Abstracting the result of a procedural abstraction, disregarding the specific method.
269
What is data abstraction?
Hiding details of how data is represented, allowing new data types from existing ones.
270
What is problem abstraction/reduction?
Removing details until a problem is represented in a solvable way, often similar to a known problem.
271
What is decomposition (procedural decomposition)?
Breaking a problem into smaller, identifiable sub-problems.
272
What is composition (combining procedures)?
Combining procedures to form a larger system or compound procedure.
273
What is composition (combining data objects)?
Combining data objects to form compound data structures (e.g., tree).
274
What is automation?
Putting abstract models of real-world phenomena into action to solve problems.
275
How is automation achieved?
By creating algorithms, implementing them in code/data structures, and executing the code.
276
What is a Turing machine?
A formal model of computation representing a computer with a single fixed program.
277
What are the components of a Turing machine?
Finite states, finite alphabet, infinite tape, read/write head.
278
What is a halting state in a Turing machine?
A state with no outgoing transitions.
279
What defines the rules followed by a Turing machine?
Transition functions (or state transition diagrams).
280
What form do Turing machine transition rules take?
δ(current state, read) = (new state, write, move).
281
What is a Universal Turing Machine?
A Turing machine that can simulate any other finite state machine.
282
How can a Universal Turing Machine read the description of another machine?
From the same tape as the input data.
283
Why are Turing machines important?
They provide a definition of what is computable and can prove problems are unsolvable.
284
What is Backus-Naur Form (BNF)?
A way of notating context-free languages.
285
What do context-free grammars describe?
Which strings are possible in a language using production rules.
286
What is a production rule in BNF?
A simple rule like replacing one character for another (e.g., a -> ab).
287
In BNF, what do text inside angle brackets <> represent?
A non-terminal (meta-component or syntactic variable).
288
In BNF, what do text without brackets represent?
A terminal (cannot be broken down further).
289
In BNF, what does the vertical bar | represent?
The OR operator.
290
Why can BNF represent some languages that regular expressions cannot?
BNF can make use of recursion.
291
What is a syntax diagram?
A visual representation of a regular language.
292
In syntax diagrams, what do rectangles represent?
Non-terminals.
293
In syntax diagrams, what do ellipses represent?
Terminals.
294
In syntax diagrams, what do arrows indicate?
How strings can be formed from the definitions.
