1.4.2 Data Structures

Question 1

What’s an array?

Answer 1

An ordered, static set of elements that can only store 1 data type.

Question 2

What is a 1D array?

Answer 2

A linear array.

Question 3

1. Create a 1D array called fruits with 5 elements in psuedocode.
2. Write code to access an element in the array.
3. Write code to change an element in the array.
4. Write code to print the length of the array.
5. Write code to iterate over the array

Answer 3

1. array fruits[5]
   fruits[0] = “banana”
   fruits[1] = “apple”
   fruits[2] = “orange”
   fruits[3] = “blueberry”
   fruits[4] = “cherry”
2. print(fruits[0])
   print(fruits[2])
3. fruits[1] = pear
4. length = len(fruits)
   print(length)
5. for element in fruits
   print(element)

Question 4

What’s a record?

Answer 4

A group of related fields which is a single entity.

Question 5

1. In psuedocode define a record type called “personDataType” with fields: “ID”, “firstName” and “surname”.
2. Declare an instance of the Person record.
3. Assign values to that variable’s fields.
4. Access the fields of the Person record.

Answer 5

1. personDataType = record
   integer ID
   string firstName
   string surname
   endRecord
2. DECLARE person1:personDataType
3. person1.ID = 101
   person1.firstName = “John”
   person1.surname = “Smith”
4. OUTPUT person1.firstName

Question 6

How can a 2D array be visualised?

Answer 6

As a table.

Question 7

1. Write psuedocode for a 2D array named “board” with rows 8, and columns 9.
2. Write code to assign “rook” to the element in the first row, first column.

Answer 7

1. Array board[8,9]
2. board[0,0]=“rook”

Question 8

How can a 3D array be visualised?

Answer 8

A multi-page spreadsheet.

Question 9

What is a list?

Answer 9

A data structure that consists of a number of items where the items can occur more than once. And can store elements of more than one data type and each element is stored non-contiguously.

Question 10

Give 1 difference of lists and arrays

Answer 10

Lists can contain elements of more than one data type, arrays can only contain elements of one data type.

Question 11

1. Create a list named “pets” in pseudocode with elements “dog”, “cat” and “fish”.
2. Write a for loop that runs through the whole list, printing each element individually.

Answer 11

1. list pets = [“dog”, “cat”, “rabbit”, “fish”]
2. for pet in pets:
   print pet

Question 12

What do these list operations do:
1. isEmpty()
2. append(value)
3. remove(value)
4. length()
5. index(value)
6. insert(position, value)
7. pop()

Answer 12

1. isEmpty() checks if the list is empty.
2. append(value) adds a new value to the end of the list.
3. remove(value) removes the value the first time it appears in the list.
4. length() returns the length of the list.
5. index(value) returns the position of the list.
6. insert(position, value) inserts a value at a given position.
7. pop() returns and removes the last value.

Question 13

What is a tuple?

Answer 13

An immutable data structure that stores an ordered set of values of any type.

Question 14

What is a linked list?

Answer 14

A dynamic data structure that is used to hold an ordered sequence of items.
The items which form the sequence do not have to be in contiguous data locations.

Question 15

What does a node contain?

Answer 15

A data field and a point field.

Question 16

What’s a data field contain?

Answer 16

The value of the actual data which is part of the list.

Question 17

What’s a pointer field contain?

Answer 17

The address of the next item in the list.

Question 18

Give 1 advantage of linked lists

Answer 18

Values can easily be added or removed by editing the pointers.

Question 19

Give 2 disadvantages of linked lists compared to arrays

Answer 19

1. Linked lists store pointers which means that more memory is required compared to an array.
2. Items in a linked list are stored in a sequence, meaning they can only be traversed within that order so an item cannot be directly accessed as is possible in an array.

Question 20

What’s a stack?

Answer 20

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

Question 21

Give 2 examples of stacks in a computer

Answer 21

1. Undo button
2. Back page button

Question 22

What do these stack operations do:
1. isEmpty()
2. push(value)
3. peek()
4. pop()
5. size()
6. isFull()

Answer 22

1. isEmpty() checks if the stack is empty by checking the value of the top pointer.
2. push(value) adds a new value to the top of the stack.
3. peek() returns the top value of the stack.
4. pop() removes and returns the top value of the stack.
5. size() returns the size of the stack.
6. isFull() checks if the stack is full and returns the boolean value.

Question 23

What is a queue?

Answer 23

A First in First out (FIFO) data structure where items are added to the end of the queue and removed from the front, that holds an ordered sequence of items.

Question 24

What are 3 types of queues?

Answer 24

1. Linear Queue
2. Circular Queue
3. Priority Queue

Question 25

What do these queue operations do: 1. enQueue(value) 2. deQueue(value) 3. peek() 4. isEmpty() 5. isFull()

Answer 25

1. enQueue(value) adds an element to the back of the queue. 2. deQueue(value) removes an element from the front of the queue. 3. peek() return the value of the item from the front of the queue. 4. isEmpty() check whether the queue is empty. 5. isFull() check whether the queue is full (if the size has a constraint).

Question 26

What is a linear queue?

Answer 26

A FIFO data structure that consists of an array.

Question 27

What is a circular queue?

Answer 27

A static array that has a fixed capacity

Question 28

What is a graph?

Answer 28

A set of vertices/nodes that are connected by edges/pointers.

Question 29

What are 3 types of graph? Explain each

Answer 29

1. Directed Graph: The edges can only be traversed in one direction. 2. Undirected Graph: The edges can be traversed in both directions. 3. Weighted Graph: A value is attached to each edge.

Question 30

What are 2 ways computers are able to process graphs?

Answer 30

1. Adjacency matrix 2. Adjacency

Question 31

What are 2 ways of traversing a graph?

Answer 31

1. Breadth first search 2. Depth first search

Question 32

What happens in breadth-first traversal?

Answer 32

1. Visit the root node. 2. Move to the left-most node under the root. 3. Output each node, moving from left to right. 4. Continue through each level of the tree.

Question 33

What happens in depth-first traversal?

Answer 33

Depth first goes to the left node, this becomes a new tree. It continues going to the left until a leaf. It then returns this, then goes right and repeats from the start. Follow left, follow right, take root.

Question 34

Identify 2 differences between a graph and a tree

Answer 34

1. A graph has cycles, a tree doesn’t. 2. A tree has a hierarchy (e.g. Parent/Child), a graph doesn’t.

Question 35

What is a tree?

Answer 35

A connected form of graph that has a root node at the top of the tree and leaves at the bottom. Nodes are connected to others nodes using branches/edges.

Question 36

What is a binary tree?

Answer 36

A rooted tree where every node has a maximum of 2 nodes.

Question 37

What’s a node?

Answer 37

An item in a tree.

Question 38

What is an edge?

Answer 38

Connects two nodes together and is also known as a branch or pointer.

Question 39

What is a root node?

Answer 39

A single node which does not have any incoming nodes.

Question 40

What is a child node?

Answer 40

A node with incoming edges.

Question 41

What is a parent node?

Answer 41

A node with outgoing edges

Question 42

What is a subtree?

Answer 42

A subsection of a tree consisting of a parent and all the children of a parent.

Question 43

What’s a leaf node?

Answer 43

A node with no children.

Question 44

What is a hash table?

Answer 44

An associative array which is coupled with a hash function.