Chapter 7

Question 1

What is an array?

Answer 1

An array is defined as a finite, ordered set of elements of the same type, such as an integer, real or char.

Question 2

How to write an array?

Answer 2

my Array = [51, 72, 35, 37, 0, 100]

X = myArray [2]

Question 3

2D array?

Answer 3

A two dimensional array can be visualised as a table rather than a spreadsheet.

Question 4

Records

Answer 4

A ​record ​is more commonly referred to as a​ row in a file​ and is made up of ​fields​. Records are used in databases.

Question 5

Lists

Answer 5

A list is a data structure consisting of a number of ​ordered ​items where the items can occur more than once​. Lists are similar to 1D arrays and elements can be accessed in the same way. The difference is that list values are stored ​non-contiguously​. This means they do not have to be stored next to each other in memory, as data in arrays is stored. Lists can also contain elements of ​more than one data type​, unlike arrays.

Question 6

Empty

Answer 6

List.isEmpty()
» False

Question 7

Add

Answer 7

List.append(15)

Question 8

Remove

Answer 8

List.remove(23)
»

Question 9

Search

Answer 9

List.search(38)
» False

Question 10

Length

Answer 10

List.length()
» 7

Question 11

Index

Answer 11

List.index(23)
» 0

Returns the position of the item

Question 12

Insert

Answer 12

insert(position, value)

Question 13

Pop

Answer 13

pop()
pop(position)

Returns and removes the last value in the list

Question 14

Tuples

Answer 14

An ​ordered set of values of any type​ is called a tuple. A tuple is ​immutable​, which means it cannot be changed​: elements cannot be added or removed once it has been created. Tuples are initialised using regular brackets instead of square brackets.

Question 15

Linked Lists

Answer 15

A linked list is a ​dynamic data structure​ used to hold an ordered sequence. The items which form the sequence do not have to be in contiguous data locations. Each item is called a ​node​, and contains a ​data field​ alongside another address called a ​link ​or ​pointer field

Question 16

Graphs

Answer 16

A graph is a set of ​vertices/nodes​ connected by ​edges/arcs​. Graphs can be placed into the following categories:
- Directed Graph: The edges can only be traversed in one direction.
- Undirected Graph: The edges can be traversed in both directions.
- Weighted Graph: A cost is attached to each edge.

Question 17

Static

Answer 17

Structure size cannot change at runtime

Question 18

Dynamic

Answer 18

Structure size can change at runtime

Question 19

Immutable

Answer 19

Structure/data cannot be changed at runtime

Question 20

Mutable

Answer 20

Structure/data can be changed at runtime

Question 21

Adjacency Matrix Advantages

Answer 21

Easy to add nodes

Convenient to work with due to quicker access times

Question 22

Adjacency List Advantages

Answer 22

More space efficient for large, sparse network

Question 23

Stacks

Answer 23

A stack is a ​last in first out (LIFO)​ data structure. Items can only be added to or removed from the top of the stack. Stacks are key data structures in computer science; they are used to reverse an action​, such as to go back a page in web browsers. The ‘undo’ buttons that applications widely make use of also utilise stacks. A stack can be implemented as either a static structure or a dynamic structure. Where the maximum size required is known in advance, static stacks are preferred, as they are easier to implement and make more efficient use of memory.

Question 24

Stack operations

Answer 24

isEmpty()
push(value)
peek()
pop()
size()
isFull()

Question 25

Queues

Answer 25

A queue is a​ first in first out (FIFO)​ data structure; items are added to the end of the queue and are removed from the front of the queue. Queues are commonly used in printers, keyboards and simulators. There are a few different ways in which a queue can be implemented, but they all follow the same basic principles.

Question 26

linear queue​

Answer 26

A ​linear queue​ is a data structure consisting of an array. Items are added into the next available space in the queue, starting from the front. Items are removed from the front of the queue. Queues make use of two pointers: one pointing to the front of the queue and one pointing to the back of the queue, where the next item can be added.

Question 27

Circular queues​

Answer 27

A circular queue operates in a similar way to a linear queue in that it is a FIFO structure. However, it is coded in a way that once the queue’s rear pointer​ is equal to the maximum size of the queue, it can loop back to the front of the array and store values here, provided that it is empty. Therefore, circular queues can use space in an array more effectively, although they are harder to implement.

Question 28

Queue operations

Answer 28

enQueue(value)
deQueue()
isEmpty()
isFull()

Question 29

Trees

Answer 29

A tree is a connected ​form of a graph​. Trees have a ​root node​ which is the top node in any tree. Nodes are connected to other nodes using branches, with the lower-level nodes being the children of the higher-level nodes.

Question 30

Trees

Answer 30

A tree is a connected ​form of a graph​. Trees have a ​root node​ which is the top node in any tree. Nodes are connected to other nodes using branches, with the lower-level nodes being the children of the higher-level nodes.

Question 31

Binary Tree

Answer 31

A binary tree is a type of tree in which each node has a​ maximum of two children. ​These are used to represent information for binary searches​, ​as information in these trees is​ easy to search​ through. The most common way to represent a binary tree is storing each node with a​ left pointer​ and a ​right pointer​. This information is usually implemented using two-dimensional arrays.

Question 32

Traversing a binary tree

Answer 32

There are three methods of traversing a binary tree: Pre-order, In-order and Post-order.
A simple way of remembering these is using the ​outline method​, which is described below.

Question 33

Pre-order Traversal

Answer 33

Pre-order traversal follows the order: root node, left subtree, then right subtree.
Using the outline method, nodes are traversed in the order in which you pass them on the left, beginning at the left-hand side of the root node.

Question 34

In-order Traversal

Answer 34

In-order traversal follows the order: left subtree, root node, right subtree.
Using the outline method, nodes are traversed in the order in which you pass under them, beginning at the first node from the left which does not have two child nodes.
This is useful for traversing the nodes in sequential order.

Question 35

Post-order Traversal

Answer 35

Post order traversal follows the order: left subtree, right subtree, root node.
Using the outline method, nodes are traversed in the order in which you pass them on the right.

Question 36

Hash Tables

Answer 36

A hash table is an array which is coupled with a ​hash function.​ The hash function takes in data (​a key​) and releases an output (​the hash​). The role of the hash function is to ​map the key to an index​ in the hash table.
Each piece of data is mapped to a unique value using the hash function. However, it is sometimes possible for two inputs to result in the same hashed value. This is known as a
collision​. A ​good hashing algorithm​ should have a ​low probability of collisions​ occurring but in the event that it does occur, the item is typically placed in the next available location. This is called collision resolution.
Hash tables are normally used for ​indexing​, as they provide fast access to data due to keys having a unique, one-to-one relationship with the address at which they are stored.

Question 37

Overflow

Answer 37

Attempting to push onto a stack that is full

Question 38

Underflow

Answer 38

Attempting to pop from a stack that is empty

Question 39

Elementary data type

Answer 39

integer, real, Boolean, char

Question 40

Composite data type

Answer 40

string, array
[list may also be in this section, depending on programming language]

Question 41

Abstract data type

Answer 41

list, stack, queue