1.4.2 Data structures - Nathan

Question 1

Define the term ‘array’

Answer 1

An array is a data structure that holds a number of elements of the same data type

Question 2

Where does array indexing start?

Answer 2

Array indexes start at ‘0’.

ADDITIONAL EXPLANATION:
So in the following array:
[“toast”, “eggs”, “ketchup”]

The ‘0th’ element is “toast”, the ‘1st’ element is “eggs” and the ‘2nd’ element is “ketchup”

Question 3

How are the contents of an array stored in memory?

Answer 3

The contents of arrays are stored contiguously in memory (meaning one after another). This means that the position of each element of the array can be computer from the array’s base address.

Question 4

Can the contents of an array be changed while the program is running?

Answer 4

The contents of an array are mutable - so they can be changed while the program is running

Question 5

What’s the difference between a one dimensional array and a two dimensional one?

Answer 5

One dimensional array: an array containing data types such as integers, strings, etc

Two dimensional array: an array containing arrays: e.g:
my2dArray = [[1, 65, 3, 2],
[62, 7, 1, 6],
[6, 3, 76, 2]]

Where the first element of this array is, [1, 65, 3, 2]

Question 6

What is a record?

Answer 6

A record is a data structure containing a fixed number of variables, called fields. Each field has an identifier (a name) and a data type. Each field can have a different data type.

PSEUDOCODE EXAMPLE:
PlayerRecord = RECORD
player_number: Integer
first_name: String
last_name: String
date_of_birth: Date
position: String
injured: Boolean
ENDRECORD

Question 7

What is a list?

Answer 7

A list is an abstract data type. It describes a linear collection of data items in an order.

Question 8

What operations can be done on a list?

Answer 8

create - create a new list
add - add a new element to the list
delete - delete an element from the list
traverse - visit the elements in the list one at a time

Question 9

What is a tuple?

Answer 9

A tuple is an ordered sequence of of immutable elements (meaning the elements can’t be changed while the program is running).

Question 10

Do elements in a tuple all have to be the same data type?

Answer 10

No, the elements of a tuple can all be different data types - e.g a mix of integers and strings

Question 11

What is a linked list?

Answer 11

A linked list is a dynamic data structure - where each node points to the next one, forming a sequence with a start and end.

Question 12

Why is it important that a linked list is dynamic?

Answer 12

Because a linked list is dynamic, it’s size can be changed at runtime.

Question 13

What does a node in a linked list contain?

Answer 13

Nodes in a linked list contain the data relating to the element, and a pointer to the next node.

Question 14

What is a graph?

Answer 14

A graph is an abstract data type that can be used to represent complex, non-linear relationships between objects. They can be undirected, or directed (contain arrows).

Question 15

What is a stack?

Answer 15

A stack is an abstract data type that holds an ordered, linear sequence of items. It is LIFO (last-in-first-out), similar to a stack of plates.

Question 16

What are the main operations of a stack?

Answer 16

Push() - add element to top of stack
Pop() - remove element from top of stack
Peek() - return copy of element on top of stack (without removing it)
is_empty() - check whether the stack is empty
is_full() - check whether stack is at maximum capacity (if stored in a static (fixed-size) structure)

Question 17

Name an application of a stack

Answer 17

One application of a stack is maintaining an ‘undo’ list

Question 18

What is a queue

Answer 18

A queue is an abstract data type that holds an ordered, linear sequence of items. It is FIFO (first-in-first-out), similar to a queue of people at a cafe.

Question 19

What are the main operations of a stack?

Answer 19

enqueue(data) - add element to queue
dequeue() - return an element from front of queue & remove it
is_empty() - check whether the stack is empty
is_full() - check whether stack is at maximum capacity (if the size of the queue is constrained)

Question 20

What are some applications of a queue

Answer 20

Queues can be used for queuing up print tasks, or for simulations (e.g traffic or shopping simulations)

Question 21

What is a tree?

Answer 21

A tree is a type of graph that’s undirected, and doesn’t contain cycles

Question 22

What’s a binary tree?

Answer 22

A binary tree is a tree where each node has at most 2 children

Question 23

What are some applications of trees?

Answer 23

• Syntax trees in compilers
• Used to represent boolean expressions to simplify them

Question 24

What is a hash table?

Answer 24

A hash table is a type of data structure in which information is stored in an easy-to-retrieve and efficient manner, using key-value pairs