1.4.2 Data Structures

Question 1

Arrays

Answer 1

An ordered, finite set of elements of a single type

You can make an array of tuples

Question 2

Index of arrays

Answer 2

0-based
Find a value with arrayname[index]
arrayname[row,column] for 2d

Question 3

Multi-dimensional arrays

Answer 3

You can have any number of dimensions

Question 4

Tuples

Answer 4

An ordered set of values, can have elements of mixed type and it is immutable (elements cannot change)

Question 5

Records

Answer 5

Composed of a fixed number of fields of different data types

Access a value with the name of the record

Question 6

Dynamic data structure

Answer 6

They can change size when required

Question 7

Static data structure

Answer 7

They cannot change size

Question 8

Abstract Data Type

Answer 8

A logical description of how we view the data and possible operations

Question 9

Where does the rear of the queue start at?

Answer 9

-1

Question 10

isFull() pseudocode

Answer 10

function isFull()
if size == maxSize:
return True
else:
return False
end if
end function

Question 11

isEmpty() pseudocode

Answer 11

function isEmpty()
if size == 0;
return True:
else: 
return False
end if
end function

Question 12

enQueue() pseudocode

Answer 12

function enQueue()
if size < maxSize:
rear ++
rear = rear MOD maxSize
Q[rear] = item
size ++
else:
print (queue is full)
end if
end function

Question 13

deQueue() pseudocode

Answer 13

function deQueue()
if size  == 0:
item = null
print (queue is empty)
else:
item = Q[front]
front = (front + 1) MOD maxSize
size --
end if
return item
end function

Question 14

Priority Queue

Answer 14

Items are ordered in a queue first based on their priority and then based on FIFO, items move backward to allow a higher priority item to join.

Question 15

Hash Table

Answer 15

A data structure where keys are mapped to index values, used where faster searching is needed e.g. police records

Question 16

Collisions/synonyms and how to deal with them

Answer 16

When an algorithm generates the same address for different primary keys
Methods include putting the value in the next free location or incrementing how far you skip by

Question 17

Searching in a hash table

Answer 17

Apply the hash function to the key and first check that position, if not increment by 1 and check each
If the original position is empty or you cycle back the value isn’t in the table

Question 18

Mid-square hashing algorithm

Answer 18

Square the number, extract some portion of the resulting digits (likely the middle), then mod by the size of the table

Question 19

Folding hashing algorithm

Answer 19

Divide the item into equal sized pieces (excluding maybe the last piece, sum them and carry out the mod with the size of the table

Question 20

Hashing alphanumeric data

Answer 20

Take the ASCII of each character, sum them and mod with the size

Question 21

Hash table deletion

Answer 21

When a value is deleted, a placeholder is used to represent that a value has not been deleted.

Question 22

Lists

Answer 22

A dynamic data type containing a number of ordered items that can be repeated. The elements are stored non-contiguously on the heap and can be of different types

Question 23

Linked list

Answer 23

A dynamic abstract data structure which is implemented as an array and pointers

Question 24

What is a node composed of linked list?

Answer 24

The data and a pointer to the next node

Question 25

Linked list pointers

Answer 25

A start pointer identifies the first element in a list, a nextfree pointer highlights the next free space, the last node has null

Question 26

Stack

Answer 26

A collection of elements that are retrieved on a last-in first-out basis

Question 27

Stack variables

Answer 27

Top and maxSize | Top starts at -1

Question 28

How to reverse elements?

Answer 28

Push them all onto a stack and then pop them off

Question 29

Stack isFull()

Answer 29

``` function isFull() if (top + 1) == maxSize: return True else: return False end if end function ```

Question 30

Stack isEmpty()

Answer 30

``` function isEmpty() if top == -1: return True else: return False end if end function ```

Question 31

Stack push()

Answer 31

``` procedure push(newItem) if (top + 1) == maxSize print (stack is full) else: top ++ stack[top] = newItem end if end procedure ```

Question 32

Stack pop

Answer 32

``` function pop() if top == -1: print (stack is empty) item = null else: item = stack[top] top -- end if return item end function ```

Question 33

Graph

Answer 33

A set of vertices connected by edges or arcs

Question 34

Adjacency Matrix of a weighted graph

Answer 34

Put the weight of the connecting edge and leave boxes blank instead of writing 0s

Question 35

Adjacency matrix advantages and disadvantages

Answer 35

+ convenient to work with, easy to add edges | - wastes a lot of memory space if nodes have few edges

Question 36

Adjacency list

Answer 36

A list of nodes pointing to their adjacent nodes | For weighted it has {node:weight}

Question 37

Tree

Answer 37

A connected, undirected graph with no cycles

Question 38

Root

Answer 38

The node at the top of the tree with no parents

Question 39

Child

Answer 39

A node below a parent node in a tree

Question 40

Parent

Answer 40

A node above one or more children

Question 41

Subtree

Answer 41

A part of a tree which itself is a tree

Question 42

Leaf

Answer 42

A node in a tree with no children

Question 43

Binary Tree

Answer 43

A rooted tree in which each node has a maximum of two children, each node has a left and a right pointer (-1 if there is no child on that side)

Question 44

Building a binary tree

Answer 44

Start from the root each time and trace to the left if the value is smaller than the current node and to the right if it is larger

Question 45

Pre-order searching

Answer 45

Visit the root then follow the left subtree then the right

Question 46

In-order searching

Answer 46

Follow the left subtree then visit the root then follow the right

Question 47

Post-order searching

Answer 47

Traverse the left subtree then the right then visit the root node

Question 48

Deleting a leaf node

Answer 48

Just remove the node

Question 49

Deleting a node with one child

Answer 49

The child replaces the deleted parent

Question 50

Deleting a node with two children

Answer 50

Repeatedly add 1 to the value of the node until you find the value of another node, which will replace the deleted node

Question 51

Binary tree uses

Answer 51

Mainly used for searching as you often have to rebuild the tree after deletion

Question 52

Breadth-first traversal

Answer 52

Traverses the root then the children of the root left to right then their children left to right

Question 53

Depth first traversal

Answer 53

Starts at the bottom left and at each leaf it will move up to the latest decision point and go right where it hasn’t been done before

Question 54

Record declaration

Answer 54

``` Name = record DataType FieldName DataType FieldName … End record ```

Question 55

Acessing a record

Answer 55

recordName.fieldName

Question 56

Adding a value to the end of a list

Answer 56

listName.append(value)

Question 57

Finding the first index of a value in a list

Answer 57

listName.index(value)

Question 58

List remove and return from a position

Answer 58

listName.pop(index)

Question 59

Removing the first instance of a value from a list

Answer 59

listName.remove(value)

Question 60

Initialising a tuple

Answer 60

tupleName = (“value1”, “value2”, …) | Accessed like an array

Question 61

Stack peek()

Answer 61

Returns the top element if the stack isn’t empty