14: Data Structures

Question 1

What is meant by a static data structure?

Answer 1

Structure size cannot change at runtime

Question 2

What is meant by a dynamic data structure?

Answer 2

Structure size can change at runtime

Question 3

What is meant by an immutable data structure?

Answer 3

Structure/data cannot be changed at runtime

Question 4

What is meant by a mutable data structure?

Answer 4

Structure/data can be changed at runtime

Question 5

What is a record?

Answer 5

A collection of related fields. A field is a variable, and each field in a record can have a different data type

Question 6

What is meant by continguous?

Answer 6

All the data is stored together, one element after the other

Question 7

Are arrays contiguous?

Answer 7

yes

Question 8

Are lists contiguous?

Answer 8

no

Question 9

What are the features of an array? (5)

Answer 9

• static
• mutable
• ordered collection of items
• items can be changed or replaced
• can only store one data type

Question 10

What are the features of a list? (5)

Answer 10

• dynamic
• mutable
• ordered collection of items
• items can be changed or replaced
• can store more than one data type

Question 11

What are the features of a tuple? (5)

Answer 11

• static
• immutable
• ordered collection of items
• items cannot be changed or replaced
• can store more than one data type

Question 12

What is a stack?

Answer 12

• A data structure that is essential for the operation of a computer
• Items can be pushed onto the top of the stack when added to it and popped off the top when they are deleted from it
• Known as a LIFO structure

Question 13

What is meant by a LIFO structure?

Answer 13

• Last-in-first-out

- The last item to be pushed onto the stack must also be the first item to be popped off

Question 14

What is the purpose of a stack pointer?

Answer 14

Always point to the node at the top

Question 15

What is a stack overflow?

Answer 15

Any attempt to push an item onto a full stack

Question 16

What is a stack underflow?

Answer 16

Any attempt to pop an item off an empty stack

Question 17

How is a stack implemented?

Answer 17

• using an array

- object oriented techniques

Question 18

What are stacks used for?

Answer 18

• keeping track of user inputs for Undo operations

- Backtracking algorithms - e.g. pathfinding maze solutions

Question 19

What operations can be performed on a stack?

Answer 19

• Push: Adding an item to the top of the stack
• Pop: Removing an item from the top of the stack
• Peek: Returning a value from the top of the stack without removing it

Question 20

What is a queue?

Answer 20

• A linear data structure
• items are enqueued at the back of the queue and dequeued from the front of the queue
• Known as a FIFO structure

Question 21

what is a FIFO structure?

Answer 21

• First-in-first-out

- First item in the queue is the first item to be dequeued

Question 22

What is the purpose of the back pointer of a queue?

Answer 22

Always points to the last item

Question 23

What is the purpose of the front pointer of a queue?

Answer 23

Always points to the first item

Question 24

What is a queue overflow?

Answer 24

An attempt to enqueue an item in a full queue

Question 25

What is a queue underflow?

Answer 25

An attempt to dequeue an item from an empty queue

Question 26

How are queues implemented?

Answer 26

- an array | - object-oriented technique

Question 27

What are the applications of a queue?

Answer 27

- Process scheduling | - Transferring data between processors and printer spooling

Question 28

What operations can be performed on a queue?

Answer 28

- Enqueue: Adding an item to the back of the queue - Dequeue: Removing an item from the front of the queue - Peek: Returning the value from the front of the queue without removing it

Question 29

What is a linked list?

Answer 29

a data structure that provides a foundation upon which other structures can be built, such as stacks, queues, graphs and trees

Question 30

How is a linked list constructed?

Answer 30

- nodes and pointers - A start pointer identifies the first time - each node contains data and a pointer to the next node - data in lists can be stored anywhere in memory, with pointers indicating the address of the next item

Question 31

How can you make a doubly linked list?

Answer 31

By adding an extra pointer, nodes can point to the previous and next items

Question 32

How do you create a circular linked list?

Answer 32

- making the last node point to the first node

Question 33

How do you implement linked lists using an array?

Answer 33

- being static data structures, arrays are stored contiguously in memory, requiring the use of an index register to determine where a specific index is in relation to a book address

Question 34

What are the applications of a linked list?

Answer 34

- operating systems managing a processor to store process blocks in a ready state - Image viewers to switch between previous and next images - music players to store tracks in a playlist - web browsers to navigate backwards and forwards

Question 35

What operations can be performed on a linked list?

Answer 35

- Adds: adds a node to the linked list - Delete: Removes a node from the linked list - Next: Moves to the next item in the list - Previous: Moves to the previous item in a doubly linked list - Traverse: A linear search through the linked list

Question 36

What are the advantages of linked lists?

Answer 36

- Dynamic data structure, so no need to give initial size - No memory wastage as size can change at runtime - Good for linear data structures, such as stacks and queues - Easy to implement insertion and deletion operations

Question 37

What are the disadvantages of linked lists?

Answer 37

- pointers need to be stored, which requires more memory - Direct access to an element is not possible so searching can be time consuming - Reverse traversal is only possible in doubly linked lists

Question 38

How do you add an item to a linked list?

Answer 38

1. Check there is free memory for a new node. Output an error if not 2. Create a new node and insert data into it/insert data in the node indicated by the free storage pointer 3. If the linked list is empty: - The new node becomes the first item. Create a start pointer to it 4. If the new node should be placed before the first node: - The new node becomes the first node. Change the start pointer to it - The new node points to the second node 5. If the new node is to be placed inside the linked list: - Start at the first node - If the data in the current node is less than the value of the new node: ---- Follow the pointer to the next node ---- Repeat from step 5b until the correct position is found or the end of the linked list is reached - The new node is set to point where the previous node pointed - The previous node is set to point to the new node 6. Update the free pointer to the next available storage space

Question 39

How do you delete an item from a linked list?

Answer 39

1. Check if the linked list is empty and output an error if there is no start node 2. If the first item is the item to delete, set the start pointer to the next node 3. If the item to delete is inside the linked list: - Start at the first node - If the current node is the item to delete then the previous node's pointer is set to point to the next node - Follow the pointer to the next node - Repeat from step 3b until the item is found or the end of the linked list is reached 4. Update the free pointer

Question 40

How to traverse a linked list

Answer 40

1. Check if the linked list is empty 2. Start at the node the start pointer is pointing to 3. Output the item 4. Follow the pointer to the next node 5. Repeat from step 3 until the end of the linked list is reached