Data structures

Question 1

What is a 1D array?

Answer 1

• An ordered, static set of elements
• Can only store one data type
• A 1D array is a linear array

Question 2

How would you create, access and modify a 1D array?

Answer 2

array = [1, 2, 3, 4, 5]
value = array[1]
print(value) #would print “2”
array[1] = 10
print(array) #would print “2, 10, 3, 4, 5”

Question 3

What is a 2D array?

Answer 3

• A 2D array can be visualised as a table
• Arrays within an array
• When navigating the table, you first go DOWN the rows and then ACROSS the columns

Question 4

What do the indices represent in a 2D array?

Answer 4

• Left index: how many down (the row)
• Right index: how many across (the column)

Question 5

What is a 3D array?

Answer 5

• Can be visualised as a multi-page spreadsheet
• Multiple 2D arrays
• When navigating, you first go through the pages (arrays), then down the rows, then across the columns

Question 6

What do the indices represent in a 3D array?

Answer 6

• First index: which page (which 2D array)
• Second index: how many down (the row)
• Third index: how many across (the column)

Question 7

What is a record?

Answer 7

• A row in a file, and is made up of fields
• The horizontal headers at the top, which identify the columns
• They are used in databases

Question 8

What is a list?

Answer 8

• A data structure which consists of a number of items where the items can occur more than once
• Lists are similar to 1D arrays and can be accessed in the same way

Question 9

What is the difference between a list and a 1D array?

Answer 9

• List values are stored non-contiguously
• Which means that they do not have to be stored next to each other in memory
• While values in a 1D array must be stored next to each other in memory

Question 10

What does isEmpty() do (lists)?

Answer 10

• Checks if a list is empty
• E.G: list.isEmpty()

Question 11

What does append(value) do?

Answer 11

• Adds the new value onto the end of the list

Question 12

What does remove(value) do?

Answer 12

• Removes the value the first time it appears in the list

Question 13

What does insert(position, value) do?

Answer 13

• Inserts the new value at the given position

Question 14

What does pop() do (lists)?

Answer 14

• Returns and removes the last value
  list = [1, 2, 3, 4, 5]
  list.pop() #returns “5”
  #new list = [1, 2, 3, 4]

Question 15

What is a tuple?

Answer 15

• An ordered set of values of any type
• It is immutable: this means that it cannot be changed
• Elements cannot be added, removed or changed after the tuple has been created
• Tuples are created using regular brackets instead of square brackets

Question 16

What is a linked list?

Answer 16

• A linked list is a dynamic data structure that is used to hold an ordered sequence
• The items that form the sequence do NOT have to be in contiguous data locations (do not have to be adjacent)

Question 17

What is an item in a linked list, and what does it contain?

Answer 17

• Each item in a linked list is called a node
• Each node contains a data field along with another address, which is called a pointer
• The pointer points to the data address of the next node

Question 18

How do you traverse a linked list?

Answer 18

• Check if the linked list is empty
• Start at the node the pointer is pointing to (start = 1)
• Output the item at the current node
• Follow the pointer to the next node, repeating through each node until the end of the list is reached
• When the pointer field is empty/null, it signals that the end of the linked list has been reached

Question 19

What is an advantage of using linked lists?

Answer 19

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

Question 20

How do you remove a node from a linked list?

Answer 20

• You do not remove the node from memory, you rather bypass it during the list
• Update the previous node to point to the node after the item you want to delete
• The node is not truly removed, but rather just ignored
• This wastes memory

Question 21

What is a stack?

Answer 21

• Stacks are a last in first out (LIFO) data structure
• Items can only be added or removed from the top of the stack
• They are used to reverse actions, such as go back a page

Question 22

What is a static stack?

Answer 22

• Where the maximum size required is known in advance, static stacks are preferred
• They are easier to implement and make more efficient use of memory

Question 23

What does isEmpty() do (stacks)?

Answer 23

• Checks if the stack is empty by checking the value of the top pointer

Question 24

What does push(value) do?

Answer 24

• This adds a new value to the top of the stack
• It will need to check the stack is not full before pushing to the stack

Question 25

What does peek() do?

Answer 25

- This returns the top value of the stack

Question 26

What does pop() do (stacks)?

Answer 26

- This returns and removes the top value of the stack

Question 27

What does size() do?

Answer 27

- Returns the size of the stack

Question 28

What does isFull() do?

Answer 28

- Checks if the stack is full and returns the Boolean value - Does this by comparing the stack size to the top pointer

Question 29

Why do stacks use pointers?

Answer 29

- The pointer in a stack points to the top of the stack - This is where the next piece of data will be added or the current piece of data can be removed

Question 30

What happens when pushing data onto a stack?

Answer 30

- When pushing data onto a stack, the data is pushed to the position of the pointer - Once pushed, the pointer will increment by 1, signifying the top of the stack - Since the stack is a static data structure, an attempt to push an item onto a full stack is called a stack overflow

Question 31

What is a stack overflow?

Answer 31

- Attempting to push data onto a full stack

Question 32

What happens when popping data from a stack?

Answer 32

- When popping data from a stack, the data is popped from the position of the pointer - Once popped, the pointer will decrement by 1 to point to the new top of the stack - Since the stack is a static data structure, an attempt to pop an item from an empty stack is called a stack underflow

Question 33

What is a stack underflow?

Answer 33

- Attempting to pop data from an empty stack

Question 34

What is a static data structure?

Answer 34

- A data structure which has a fixed size and can't change at run time

Question 35

What is a dynamic data structure?

Answer 35

- A data structure which can adapt and accommodate changes to the data inside so it doesn't waste as much space in memory

Question 36

What is a queue?

Answer 36

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

Question 37

What is a queue overflow?

Answer 37

- Attempting to enqueue an item to a full queue

Question 38

What is a queue underflow?

Answer 38

- Attempting to dequeue an item from an empty queue

Question 39

What does enQueue(value) do?

Answer 39

- Adds the value onto the back of the queue

Question 40

What does deQueue() do?

Answer 40

- Returns and removes the item at the front of the queue

Question 41

What does peek() do (queue)?

Answer 41

- Returns the first value in the queue without removing it

Question 42

What is a linear queue?

Answer 42

- A data structure that consists of an array - Items are added to the next available space in the queue, starting from the front - Items are then removed from the front of the queue

Question 43

What pointers does a queue have?

Answer 43

- Head pointer: points to the first value - Tail pointer: points to the last value

Question 44

What is a circular queue?

Answer 44

- A circular queue is a static array that has a fixed capacity - It would take time to move items to the start of the array to free up space at the end, so a circular queue is implemented - It reuses empty slots at the front of the array that are caused when items are dequeued