Component 1

Question 1

What is the opcode and operand?

Answer 1

The opcode is the first part of a binary instruction and is the actual operation we need to do such as ADD, STA, DAT or whatever it may be. The operand is the second half of the binary instruction and is the actual data to be dealt with say ADD 0011 would be the instruction to add 3 to the current value of the ACC

Question 2

What is the purpose of DAT in assembly?

Answer 2

DAT is used to name a data location, sort of like naming a variable in a high level language apart from the fact that it is often done at the end of the program

Question 3

What is the purpose of STA, LDA and BRP in assembly language?

Answer 3

STA = Store and will store the contents of the value of the ACC in the given memory address in the operand. LDA = Load what is referenced by the given memory address into the accumulator and BRP = Branch is positive or negative meaning jump to the address given if the accumulator value is >= 0

Question 4

What does it mean for a data structure to be mutable?

Answer 4

A mutable data structure is one that can have it’s contents changed during runtime

Question 5

Is an array static or dynamic and what do they both mean?

Answer 5

An array is static meaning it’s length cannot be changed during runtime and dynamic means the length of the data structure can be changed during runtime

Question 6

Give an advantage of an immutable data structure and an example of one

Answer 6

It has no opportunity to introduce runtime errors if the contents of the data structure cannot be changed. An example of this is a tuple

Question 7

What is immediate addressing?

Answer 7

Immediate addressing is where the actual value of the operand is the bit of data that we want

Question 8

What is direct addressing?

Answer 8

Direct addressing is where the opcode is a pointer to a memory address which contains the value of the data that we want

Question 9

What is indirect addressing?

Answer 9

Indirect addressing is where the operand is a pointer to a memory location which is then another pointer to a final memory location which contains the data or instruction that we want

Question 10

What is an advantage of indirect addressing?

Answer 10

It allows us to use more memory addresses than with direct addressing as there may be more bits available

Question 11

What is indexed addressing?

Answer 11

Indexed addressing is where the operand value + some constant in the index register is the pointer for the memory address that we want

Question 12

What is an advantage of indexed addressing?

Answer 12

It is very useful for large data structures like arrays as we only need to specify the start with the constant in the index register

Question 13

What is the time complexity of searching through, an array, a list

Answer 13

They are both O(n) normally as we check each individual element but O(1) at the best case which is when we know where the value we are looking for is

Question 14

What is the time complexity of a binary search

Answer 14

It is O(logn) as it uses a divide and conquer algorithm

Question 15

How does a hash table work?

Answer 15

An input is run through a hashing algorithm to give a unique hash which then corresponds to a given index in an array which the data can then be put into

Question 16

What is the time complexity of a hash table and why?

Answer 16

O(1) constant as it only takes a constant amount of time to run an input through a hash table which gives the index we need. This only changes to O(n) if we have collisions as we would need to check through the overflow list

Question 17

What are collisions in a hash table?

Answer 17

Collisions are where two inputs with two distinct hashes correspond to the same array index meaning we need to put two items into one array index which isn’t possible, so we fix this by creating an overflow list which any overflows are put into

Question 18

What is the algorithm for adding and removing from a hash table?

Answer 18

Adding an item: first we run the input through a hash algorithm and correspond that to an array index, then we check if that array index is free and if it is then we simply add that value to the given index. If it isn’t then we go to the overflow array and add it to the next free index in that array.

Removing an item: first we run the input through the hash algorithm and get a corresponding array index, then we check if the value in that index is the one we want to remove and if it is then simply remove it, if not we start traversing the overflow array until we find the one we want

Question 19

What is a stack?

Answer 19

A stack is a last in first out data structure where items are pushed to the top of the stack and popped off the top, and so only the top of it can be accessed at any given time.

Question 20

What is a queue?

Answer 20

A queue is a first in first out data structure meaning, you enqueue items to the back of a queue, and dequeue them from the front. This means it consists of a head and tail pointer which indicate the back and front a queue

Question 21

What are the applications of a stack?

Answer 21

Anything that requires stepping back like the undo function or back button on a web browser, also a function call so we know which line number to return to

Question 22

What are the applications of a queue?

Answer 22

Print queues, or process scheduling in the CPU

Question 23

What is a graph?

Answer 23

A graph is a data structure consisting of vertices and edges where each node is connected with a pointer to any number of other nodes, a node with only one connection is known as an edge, we can have undirected graphs where connections go both ways, or directed where you can only traverse between two nodes in one way

Question 24

What is a weighted graph?

Answer 24

A graph in which traversal between nodes has a value associated with it often called a weight or a cost, this could represent distances if we’re considering nodes as locations

Question 25

How would you implement a graph in pseudo code?

Answer 25

Edges{(A,B),(A,C),(B,A),(C,A)…} which is a dictionary showing all the possible paths between nodes, showing them BOTH ways
OR
With an adjacency matrix where each element like [1,2] shows whether that path exists in the graph

Question 26

What is the difference between breadth first and depth first traversal?

Answer 26

Breath first traversal visits the neighbours of the root node first and then all the ones parallel to the node currently being visited, this uses a queue to implement
Depth first traversal explores all the way down a branch first before going back up to explore all the way down another branch, this uses a stack

Question 27

What is the algorithm for a breadth first search?

Answer 27

1) Set the root node as the current node
2) Add the current node to the list of visited nodes if it’s not already there
3) Visit every node linked to that current node and enqueue
4) Dequeue the first node and set the removed node as the current node
5) Repeat steps 2->5 until there’s none left to visit
6) Output the visited nodes

Question 28

What is the algorithm for the depth first search?

Answer 28

1) Set the root node as the current node
2) Add the current node to the list if it’s not already on it
3) For every edge connected to the current node, push it onto the stack
4) Pop off the top item, and set it to the current node
5) Repeat from step 2 until there’s no nodes left
6) Output all the visited nodes

Question 29

What is a gay tree?

Answer 29

A tree is a data structure similar to a graph but each parent node can only have no, one or two child nodes and no cycles can exist, and all paths are directed meaning there exists some distinct parent node.

Question 30

What is a binary search tree?

Answer 30

A binary search tree is a tree such that all nodes left of a given node are less than that node, so everything less than the root node is less than it and everything right of the root node is greater than it.

Question 31

What is the use of a tree and binary search tree?

Answer 31

A tree is used, for file directories or path finding, essentially anything with a hierarchical structure. A binary search tree can be used for efficient searching in a data base, wireless networking or OS scheduling

Question 32

What are the 3 types of traversal of a binary tree and how do they work?

Answer 32

1) Pre order which visits the root node, left branch then right branch- dot goes left of node
2) In order which visits left branch, root node then right branch - dot goes under node
3) Post order which visits left branch, right branch then root node - dot goes right of node

Question 33

What are the 4 ACID rules

Answer 33

Atomicity - A change is either completely done or not at all done to a database

Consistency - All changes must retain the overall state of the database

Isolation - A transaction must not be interrupted by other transactions

Durability - Once a change is done, it must not be lost due to system failure

Question 34

What are the conditions for first normal form?

Answer 34

All field names must be unique, all values in the fields must be atomic, meaning each field must only have one piece of data in it. The values in each field must be of the same type (In the same domain). No two records can be identical and each table needs a primary key

Question 35

What are the conditions for second normal form?

Answer 35

The database must already be in first normal form and also must have removed all partial dependencies which are where one or more fields depend only on only part of the primary key

Question 36

What are the conditions for third normal form?

Answer 36

Already in second normal form and removed any transitive dependencies, meaning all fields must be dependant on the primary key

Question 37

What is polymorphism?

Answer 37

Polymorphism is where one process runs on two different sets of inputs and so will give 2 different outputs say adding two values together with a set of integers and a set of strings, same process, different inputs and outputs

Question 38

What is listed in the data protection act?

Answer 38

• Personal Data must be fairly and lawfully processed
• Personal data must be obtained for specific purposes
• Data must be adequate and relevant
• Data must be accurate and up to date
• Data must not be kept longer than required
• Dat must be handled in a secure way

Question 39

What is listed in the computer misuse act?

Answer 39

• Prohibits access to computer systems without prior permission
• Prohibits unauthorised modification to computer systems

Question 40

What is listed in the copright design and patents act?

Answer 40

• Protects all intellectual
  -Automatically applied to original works
  -Expires 25 to 70 years after authors death

Question 41

What is listed in RIPA? (Regulation of investigatory powers act)

Answer 41

• Public organisations are able to gain access to things like phone lines to monitor someone but only with good and lawful intent

Question 42

What is an issue with RIPA?

Answer 42

Some may consider it an invasion of privacy as it allows corporations to access personal information that they shouldn’t have access to and it raises the question of what are they using this data for

Question 43

What are the two types of memory management within RAM?

Answer 43

Paging, this is where we split up memory into discrete and evenly sized chunks so each bit of data can be put into each page where it will fit. To access these the OS indexes a page table to find the index of the page we want.

Segmentation which is where memory is split up into uneven chunks called segments which are split up into logical divisions given the current data we need to store. This means we avoid splitting up programs which generally slows things down as we have to rebuild them when calling from memory. The name also implies that we can segment functions into segments so that if two programs need it they can both access it easily

Question 44

What is disk thrashing

Answer 44

This is when memory is swapped too quickly around using paging, segmentation or Virtual memory and so the CPU cannot get the data it needs when it needs it and so the computing freezes

Question 45

What is an interrupt?

Answer 45

An interrupt is a command given to the CPU to halt whatever it is currently doing to execute the task it is about to be given. This means stopping the FDE cycle using the ISR (interrupt service routine)

Question 46

How does the ISR work?
When is it used?

Answer 46

The current state of all registers are added to a stack frame
The registers are all wiped and the PC gets updated with the address of the interrupt
The interrupt is then executed on the CPU as any normal cycle
The registers are then all cleared and the previous states are loaded from the stack frame
The FDE cycle can then continue as normal

It is used when we have a job that is of a higher priority than the one being executed. This is decided by its place in the priority queue as all incoming jobs are added to the priority queue

Question 47

What is the round robin?

Answer 47

It is a scheduling algorithm where each job is given a set time slice (a quantum) and if it isn’t complete in this time then it gets added to the back of the queue and repeat until it is done. If it is completed then it is removed from the queue

Question 48

What is first come first served in scheduling

Answer 48

This is simply a scheduling algorithm where the job at the start of the queue is completely run first and as soon as that is done we do every successive job in the priority queue

Question 49

What is multi level feedback queues

Answer 49

This is where we can use multiple cores and so we have multiple queues waiting so we can swap jobs between queues to optimize it

Question 50

What is shortest job first?

Answer 50

This is a scheduling algorithm where we look for the job with the shortest time and run this first on the CPU then do every job in order of increasing job time.

Question 51

What is shortest remaining time?

Answer 51

It is a scheduling algorithm where we look at the priority of the job and how long it has left and choose which one to execute based on it’s priority and time remaining

Question 52

List 2 eviction algorithms and how they work

Answer 52

1) Clairvoyant, this uses statistical analysis to remove the most optimal set of instructions from L1 cache if we don’t need it
2) LRU (Least recently used) This simply removes the instructions that are used the least as we don’t need them
3) Random replacement which just randomly picks one instruction to remove from cache which is incredibly inefficient

Question 53

Describe the FDE cycle in detail

Answer 53

In the fetch phase:
1)The address in the PC is copied to the MAR
2)It is then sent over to memory via the address bus
3)The control unit sends a read signal via the control bus
4)The result is then sent over the data bus to the MDR
5) It is removed from the CIR and the PC is incremented by one for the next instruction

In the decode phase:
1) The instruction is made up of the opcode and operand
2) This is loaded into the accumulator depending on the contents of the opcode and operand

Execute phase:
1) The data is then sent across the data bus to the MDR if it needs to be stored into memory
2) If not it is sent to the accumulator and the cycle can start again

Question 54

What is the difference between Harvard and Von Neumann architecture

Answer 54

Von Neumann is where all instructions and data are stored physically together. A single control unit follows the FDE and cycle and only one instruction at a time due to one set of buses

Harvard Architecture is where Instructions and data are physically separated and so 2 sets of buses are needed. This then means reading and writing can be done more efficiently as we can do it at the same time

Question 55

What is an advantage of Harvard architecture

Answer 55

Harvard can read and write to memory at the same time and so is incredibly quick given no interrupts and so is useful in an embedded system

Question 56

What is a CISC and RISC processor?

Answer 56

A complex instruction set computer (CISC) is an instruction set with relatively complicated instructions such as multiply, each CISC command corresponds to multiple RISC commands.

A reduced instruction set computer (RISC) has only the fundamental instructions such as load, add and store and so each RISC command corresponds to one machine code command

Question 57

Give 1 advantage and 1 disadvantages of RISC and CISC

Answer 57

CISC:
+ Less RAM is required since code is shorter
+ Often used in x86 as it has multiple addressing modes
-They use much more energy as pipelining isn’t possible as some instructions need multiple cycles

RISC:
+Each instruction only needs 1 cycle to complete
+The physical board is a lot smaller
-The compiler has to do more work
-More RAM is required to store the code