Data Structures

Question 1

What is an array?

Answer 1

An ordered finite set of elements of a single type.

Question 2

What type of array is a linear array?

Answer 2

A one-dimensional array.

Question 3

How can you visualise a two-dimensional array?

Answer 3

As a spreadsheet or table.

Question 4

How can you visualise a three-dimensional array?

Answer 4

A three dimensional array can be visualised as a multi-page spreadsheet.

Question 5

What is a record also known as?

Answer 5

A row in a file.

Question 6

What is a record made up of?

Answer 6

A record is made up of fields.

Question 7

How can you select a field from a record using pseudocode?

Answer 7

recordName.fieldName.

Question 8

What is the definition of a list?

Answer 8

A data structure consisting of a number of items in which the items can occur more than once.

Question 9

What are the main differences between arrays and lists?

Answer 9

• Lists can store data non-contiguously whereas arrays store data in order. - Lists can store data of more than one data type.

Question 10

What is a tuple?

Answer 10

An immutable ordered set of values of any type.

Question 11

What is the difference between a tuple and an array?

Answer 11

Tuples are initialised using regular brackets instead of square brackets.

Question 12

What is a linked list?

Answer 12

A dynamic data structure used to hold an ordered set of items which are not stored in contiguous locations.

Question 13

What is the name given to the items in a linked list?

Answer 13

Nodes.

Question 14

What does each item in a linked list contain?

Answer 14

It contains a data field and another address field called a link pointer.

Question 15

What is a data field in a linked list?

Answer 15

A field that stores the actual data.

Question 16

What is a pointer field in a linked list?

Answer 16

A field that contains the address of the next item in the list.

Question 17

What is a graph?

Answer 17

A graph is a data structure consisting of a set of vertices (nodes) connected by edges (arcs).

Question 18

What is a directed graph?

Answer 18

A graph in which the edges can only be traversed in one direction.

Question 19

What is an undirected graph?

Answer 19

A graph in which the edges can be traversed in both directions.

Question 20

What is a weighted graph?

Answer 20

A graph in which the arcs (edges) have a cost to traverse.

Question 21

Give two ways of representing graphs so that they can be understood by computers.

Answer 21

Adjacency Matrix Adjacency List.

Question 22

What are the advantages of using an adjacency matrix?

Answer 22

• Convenient to work with - Easy to add new nodes.

Question 23

What are the advantages of using an adjacency list?

Answer 23

Space efficient for large sparse networks.

Question 24

What is a stack?

Answer 24

A LIFO (last in first out) data structure where items can only be removed from and added to the top of the list.

Question 25

Give an example of where stacks may be used.

Answer 25

- Back button in a web page -Undo buttons

Question 26

What is a queue?

Answer 26

A FIFO (first in first out) data structure where items are added to the end of the queue and removed from the front of the queue.

Question 27

What is a tree?

Answer 27

A data structure which has a root node and child nodes connected with branches.

Question 28

What is a node?

Answer 28

A node is any item in a tree.

Question 29

What is an edge?

Answer 29

An edge is the connection between two nodes.

Question 30

What is the root node?

Answer 30

The node which doesn't have any incoming nodes at the top of the tree.

Question 31

What is a child?

Answer 31

Any node which has an incoming edge.

Question 32

What is a parent?

Answer 32

Any node which has outgoing edges.

Question 33

What is a subtree?

Answer 33

A section of the tree which consists of a parent and all the children of that parent.

Question 34

What is a leaf?

Answer 34

A leaf is a node which has no children.

Question 35

What is a binary tree?

Answer 35

A type of tree in which each node has a maximum of two children.

Question 36

What is the purpose of a binary tree?

Answer 36

A binary tree is used to search for values quickly.

Question 37

What is a hash table?

Answer 37

A hash table is an array which is coupled with a hash function.

Question 38

What is a collision?

Answer 38

A collision is where two inputs result in the same hashed value.

Question 39

What properties does a good hashing algorithm have?

Answer 39

A good hashing algorithm must have a low chance of collision and must be fast.

Question 40

What is pre-order traversal?

Answer 40

Traversal algorithm in which you traverse the root node followed by the left subtree then the right subtree.

Question 41

What is in-order traversal?

Answer 41

Traversal algorithm in which you traverse the left subtree the root node then the right subtree.

Question 42

What is post-order traversal?

Answer 42

Traversal algorithm in which you traverse the left subtree the right subtree followed by the root node.

Question 43

What does the operation isEmpty do?

Answer 43

Checks if the list is empty.

Question 44

What does the operation append(value) do?

Answer 44

It adds the given value to the end of the list.

Question 45

What does the operation remove(value) do?

Answer 45

It finds the first instance of the given value and removes it.

Question 46

What does the operation search(value) do?

Answer 46

Searches for the given value in a list.

Question 47

What does the operation length do?

Answer 47

Returns the length of the list.

Question 48

What does the operation index(value) do?

Answer 48

Returns the index of a value in the list.

Question 49

What does the operation insert(position value) do?

Answer 49

Adds the value to the position in the list.

Question 50

What does the operation pop do?

Answer 50

Removes the item from the top of the stack.