Topic 2 - Fundamentals of data structures

Question 1

Define data structure?

Answer 1

Is the format used to efficiently store & organise a collection of related data items

Question 2

Define array?

Answer 2

A data structure made up of a list of data elements that are the same data type or size

Question 3

Example of a one-dimensional & two-dimensional array?

Answer 3

List

Table

Question 4

Define text files?

Answer 4

Store data in humanly readable format

Question 5

Define binary files?

Answer 5

Store data which is not in a humanly readable format, must be interpreted by a program or hardware.

Question 6

Define static data structure?

Answer 6

Data storage method where the amount of data and memory allocated is fixed. e.g. an array

Question 7

Define dynamic data structure?

Answer 7

Data storage method where the amount of data and memory allocated is varied to meet the needs of the application using it. e.g. a vector

Question 8

One advantage of static data structures?

Answer 8

Memory addresses will be allocated at compile time, so will be fixed and contiguous, permitting faster access

Question 9

One advantage of dynamic data structures?

Answer 9

Meets the needs of the application, effiecient use of memory

Question 10

Define a queue?

Answer 10

Is used as a temporary storage space for data.

An abstract data structure which operates on FIFO.

Question 11

Define a linear queue?

Answer 11

Is a FIFO data structure organised as a list of data

Question 12

Define a circular queue?

Answer 12

Is a FIFO data structure organised in a ring formation

Question 13

Define a priority queue?

Answer 13

Is similar to a regular queue except that each element is assigned a priority and the highest-priority are served first

Question 14

Define a stack?

Answer 14

Is an abstract data type which uses FILO

Question 15

What are the 3 operations which can be performed on a stack?

Answer 15

• Push
• Pop
• Peek (or top)

Question 16

What does the push operation do on a stack?

Answer 16

Adds items of data to the top of the stack

Question 17

What does the pop operation do on a stack?

Answer 17

Removes the last item of data from the stack

Question 18

What does the peek operation do on a stack?

Answer 18

Reads the top element in the stack without removing it from the stack

Question 19

Define a graph?

Answer 19

Used to represent complex relationships such as computer interconnection drawings.

Question 20

What are the 4 parts to a graph?
V/N
E/A
W/UW
D/UD

Answer 20

• Vertex/node
• Edge/arc
• Weighted/Unweighted graph
• Directed/Undirected graph

Question 21

Define a vertex/node?

Answer 21

Is a value or node (with a circle around it)

Question 22

Define an edge/arc?

Answer 22

Is used to connect two nodes or vertices

Question 23

Define weighted to an unweighted graph?

Answer 23

Weighted - Is a graph that has labels on each edge/arc to indicate a data value.

Unweighted - is a graph that has no labels on each edge/arc to indicate its data value.

Question 24

Define directed and an undirected graph?

Answer 24

Directed - Is a graph where the direction of travel between vertices can only be one-way, as directed by the arrow.

Undirected - Is a graph where there is no set direction of travel from each node.

Question 25

Define an adjacency list?

Answer 25

Used to represent a graph by listing each node and the nodes directly connected to it

Question 26

State 2 comparisons of adjacency list & matrix?

Answer 26

Adjacency list stores details of graphs where an edge exists

Matrix stores details of all node adjacencies, where an edge exists as a 1 and where it doesn’t as a 0

Question 27

Was is the difference between a sparse and dense graph?

Answer 27

Sparse - With few edges, makes it faster and saves memory to use an adjacency list to store the data set.

Dense - With many edges, since all permutations of adjacencies are identified, it’s faster to store the data set as an adjacency matrix.

Question 28

Define a tree graph?

Answer 28

Is an abstract data type based on undirected graphs that don’t contain cycles. Each node can only be reached through one path.

Question 29

What are 4 parts of a tree graph?
R
P
C
L

Answer 29

• Root
• Parent
• Child
• Leaf

Question 30

Define a root in a tree graph?

Answer 30

Is the starting node that has no parents, all other nodes branch off from it.

Question 31

Define a parent in a tree graph?

Answer 31

This node has further nodes branching from it, which are called children.

Question 32

Define a child in a tree graph?

Answer 32

This node has nodes above it in the tree, which are called parents.

Question 33

Define a leaf in a tree graph?

Answer 33

This node has no nodes below it, is the last node on the tree edge

Question 34

Define a binary tree?

Answer 34

A tree structure where each node has a maximum of two child nodes is unordered since there are no relationships between a parent node and its child node.

Question 35

Define a binary search tree?

Answer 35

This is an ordered or sorted binary tree with the recursive relationships that for each node the left child is less than the parent node and the right node is more than the parent node.

Question 36

What are binary trees used for?

Answer 36

• Routing the best path in a network, such as a telephone network.
• Storing data in an easy-to-find, searchable format using standard tree traversal methods.
• Storing hierarchal data, such as a dictionary tree for file management purposes.

Question 37

Define a hash table?

Answer 37

Is a data structure that stores data in an associative way.

The table is created using a hash function which maps a key to an index in an array to find the value of an array element.

Question 38

Define hash function?

Answer 38

Takes the data input known as a key and outputs an integer known as a hash value; this value maps the key to a particular index in the hash table.

Question 39

Define collision?

Answer 39

Is where two keys are applied to the hash function and create an identical hash value; hash functions are chosen with the aim of minimising the chance of collisions.

Question 40

Define linear probing?

Answer 40

Is where a key is assigned to the next available slot in the hash table if there is a collision.

Question 41

Define a linked list?

Answer 41

Is a linear data structure in which a group of nodes contain data and make use of a pointer to link with the next data element.

Question 42

Define separate chaining?

Answer 42

Is where the hash table index is a pointer to a linked list data structure that contains the data.

There are no collisions the linked list contains on element and the linked list will contain all of the collisions for a particular slot.

Question 43

Define a dictionary?

Answer 43

Is a data structure that contains a collection of ‘key-value’ elements where the data value is accessed by the associated data.

Question 44

What 3 operations can a dictionary perform?

Answer 44

• Find: or search for a key returns the value
• Add: or insert a key-value pair, unordered data
• Delete: removes the key and its associated value

Question 45

Define a vector?

Answer 45

Vectors can automatically grow to store additional elements. The individual elements of a vector can be assessed efficiently via an index.
Similar to arrays

Question 46

What are the 3 ways vectors can be stored in?

Answer 46

• List of real numbers
• Functional interpretation
• Geometric vector

Question 47

What is the list of real numbers in a vector?

Answer 47

e.g. 4-vector over R (R^4)

[1.2, 5.25, -4.3, 1.75]

Question 48

What is the functional interpretation in a vector?
0 = 1.2
1 = 5.25
2 = -4.3
3 = 1.75

Answer 48

S —> R

S = {0,1,2,3} R = {1.2, 5.25, -4.3, 1.75}