1.4

Question 1

Define annulment

Answer 1

When an input is nullified

Question 2

Define identity

Answer 2

When a single input determines the output

Question 3

Define idempotent

Answer 3

When the same input is used more than once for one expression

Question 4

Define complement

Answer 4

When a value and the opposite of that value are both inputted

Question 5

Define double negation

Answer 5

When an input goes through a NOT gate twice

Question 6

Define commutative

Answer 6

When 2 values can be inputted multiple ways to give the same result

Question 7

Define associative

Answer 7

When 3 values can be inputted multiple ways using the same symbols to give the same result

Question 8

Define distributive

Answer 8

When 3 values have to be inputted using different symbols to return the same value

Question 9

What does n left shifts do to a binary value

Answer 9

Multiplied the value by 2^n

Question 10

What does n right shifts do to a binary value

Answer 10

Divides the value by 2^n

Question 11

What does an AND MASK do

Answer 11

Only bits corresponding with 1 in the mask are retained

Question 12

What does an OR mask do

Answer 12

Turns specific bits on and leaves the rest unchanged

Question 13

What does an XOR mask do

Answer 13

If the mask value equals the corresponding bit value, the bit value is switched to 0

Question 14

What is a linked list

Answer 14

Dynamic data structure used to hold an ordered sequence (do not have to be in contiguous data locations). Each item is a node containing a data field and an address called a link or pointer

Question 15

What is an advantage of a linked list

Answer 15

Values can easily be added or removed by editing pointers.

Question 16

What are disadvantages of linked lists

Answer 16

Nodes are not removed they are just ignored (wastes memory)
Storing pointers requires memory
Items can not be directly accessed, it has to go through the order

Question 17

What is a linked list

Answer 17

Data structure that provides a foundation upon which other structures can be built, such as stacks, queues, graphs and trees

Question 18

Name some characteristics of a linked list

Answer 18

Can go backwards and forwards
Each node contains data and a pointer to the next node
Data in lists can be stored anywhere in memory

Question 19

Features of a linked list

Answer 19

Dynamic
Ordered
Pointers
More memory
Items can not be directly accessed

Question 20

Applications of a linked list

Answer 20

Store music
Web browsers
Viewing images

Question 21

What does the term hashing mean

Answer 21

Applying a hashing algorithm to the value in the key field of each record to transform it into an address

Question 22

What characteristics should a hashing algorithm have

Answer 22

Needs to calculate quickly
Few collisions
Take up least amount of memory

Question 23

How is the index decided for each value

Answer 23

For numbers, divide the value to be stored by the side of the array and take the remainder
For strings convert the values of the whole string into ASCII

Question 24

What is a hash table

Answer 24

Creates indexes for databases

Question 25

What is the term collision meant (hashing)

Answer 25

When two record keys hash to the same index

Question 26

Describe some of the different methods that a hash table data structure might deal with collisions

Answer 26

Store the item in the next available slot (linear probing : checking the values after the one at the index)

Question 27

Define clustering

Answer 27

Several positions being filled around common collision values

Question 28

Explain the process to delete from a hash table

Answer 28

Same process as searching for a value

Question 29

What does rehashing refer to

Answer 29

Creating a new hashing algorithm (e.g increasing the size of the table), if there are too many collisions

Question 30

Define chaining

Answer 30

Using a 2D hash table so it is possible for more than one value to be stored at the same position (takes extra resource time and extra memory)

Question 31

Define a graph

Answer 31

Set of vertices/nodes connected by edges/arcs

Question 32

What is a directed graph

Answer 32

Graph with edges that can only be traversed in one direction

Question 33

What is an undirected graph

Answer 33

Graph with edges that can be traversed in both directions

Question 34

What is a weighted graph

Answer 34

A graph that has a cost attached to each edge

Question 35

What is an adjacency list

Answer 35

Used to show the weight of each edge connecting a node to every other node in a graph. A -> {B:4, C:18, D:12}

Question 36

What is an adjacency matrix

Answer 36

Used to store the weight of an edge between two nodes in a graph. Uses a table with all the nodes listed in the x and y axis

Question 37

Advantages of an adjacency matrix (graphs)

Answer 37

Quicker access times Easy to add nodes

Question 38

Advantage of an adjacency list (graphs)

Answer 38

Space efficient for larger , sparse networks

Question 39

Define a tree

Answer 39

Connected form of a graph Contain a root node (top node in a tree) Nodes are connected using branches Lower level nodes are the children of higher level nodes A leaf is a node with no children

Question 40

Define a binary tree

Answer 40

Tree in which each node has a maximum of two children Used to represent information for binary searches as information is easy to search for

Question 41

What is the most common way to represent a binary tree

Answer 41

Each node has a left pointer (child node on the left) and a right pointer (child node on the right) Information is implemented using a 2D array

Question 42

What is preorder traversal (trees)

Answer 42

Root node -> left subtree ->right subtree

Question 43

What is in order traversal (tree)

Answer 43

Left subtree -> root node -> right subtree Values should be returned in the correct order

Question 44

What is post order traversal (trees)

Answer 44

Left subtree -> right subtree -> root node Nodes are traversed in the order that u pass them on the right