1.4.2 Data Structures

Question 1

What is an array?

Answer 1

• Can be like a variable that can contain more than 1 item.
• It is also a collection of elements of the same data type grouped under a single identifier.
• Done by allocating contiguous (all the data stored together one after another)
• They are static

Question 2

Name an example of a 1 and 2 dimensional array

Answer 2

• 1D = Names = [“Sam”, “Lucy”, “James”, “Jack”]
• 2D = Names = [[“Sam”, “Lucy”, “James”], [“Peter”, “Sarah”, “Adam”]]

Question 3

What is a record?

Answer 3

• A record is a collection of related fields
• A record is a data structure that allows items of data of different types to be stored.
• This is useful when creating a set of related data items.

Question 4

What is field?

Answer 4

• A field is a variable, and each field in a record can have a different data type.

Question 5

What are the steps of making a record structure

Answer 5

• Step 1 : Define the record structure - what fields will be in the record
• Step 2 : Declare a variable or array to use with record structure
• Step 3: Assign and retrieve data from the variable record

Question 6

What is a Tuple

Answer 6

• Immutable (data it contains can’t be edited once assigned at runtime)
• Can contain data of different data types.
• student = (“James”, “Smith”, “30/01 / 2000”)

Question 7

What is a data structure and name a few

Answer 7

• Is simply a way of representing the data held in a computer’s memory
• 1 2 or 3 dimensional arrays, records, tuples, lists, stacks, queues, linked lists, binary trees, directed/undirected graphs, hash tables

Question 8

What does a static data structure mean and name an example

Answer 8

• Size is fixed when structure created / size cannot change during processing
• Array

Question 9

What is a dynamic data structure and name a disadvantage?

Answer 9

• Size can change during processing
• Don’t have a limited size however tend to be more complex to implement and can use a lot of memory.
• Storage required is unknown initially / more difficult to program

Question 10

What is a list?

Answer 10

• Lists is a simple data structure similar to an array. However like a tuple it can hold a range of data types

Question 11

What are the similarities and differences between an array, list or tuple

Answer 11

• Lists: Mutable - data it contains can be changed at runtime, Array: Mutable, Tuple: Immutable - can’t be changed
• Lists and Arrays: Ordered items, Tuple: Unordered
• Lists and Arrays: Items can be changed/replaced. Tuples: No
• Lists and Tuples: Store more than 1 data type, Arrays: Store only 1 data type.

Question 12

What are the similarities between constants and tuples

Answer 12

• Both are features of high-level programming languages
• Both have data defined at design time and can’t be changed at run time (immutable)
• Can both make program execution faster because a compiler can optimise code for immediate addressing

Question 13

What are the differences between constants and tuples

Answer 13

• A constant can only hold 1 value of 1 data type.
• A tuple is an unordered set of multiple values of different data types.

Question 14

What are the similarities between record structures and classes

Answer 14

• Are both features of high-level procedural languages.
• Record structures and class attributes can hold multiple data types (variables/ attributes) within 1 identifier

Question 15

What are the differences between record structures and classes

Answer 15

• Record structures are usually associated with procedural languages.
• Classes are a feature of object-oriented techniques.
• Class attributes can be encapsulated and classes can have methods.
• Classes can have inheritance to apply methods and attributes to sub classes.

Question 16

What is a doubly linked list?

Answer 16

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

Question 17

What is a circular list?

Answer 17

• Can be created by making the last node point to the first node

Question 18

What is a doubly circular linked list?

Answer 18

• Each node in a circular linked list can also have an additional pointer pointing to the previous item.

Question 19

What can be used to implement a linked list?

Answer 19

• Using a static array
• Or object-oriented techniques
  
  • Any available memory address can be used to store data doesn’t need to be adjacent. Nodes point to the next node.
• The memory footprint of data structure isnt determined at compile time and can eb changed at runtime.

Question 20

What are the applications of a linked list

Answer 20

• Operating systems, managing processor to store process blocks in ready state.
• Image viewers to switch between previous/next images.
• Music players to store tracks.
• Web browsers to navigate back/forth.
• Hash table collision - overflow
• Maintaining a file allocation table of linked clusters on secondary storage.

Question 21

What operations can be performed on a linked list?

Answer 21

• Add: Add a node to a linked list
• Delete: Remove a node from a linked list
• Next: Moves to the next item in the list
• Previous: Moves to the previous item in the list.
• Traverse: A linear search through the linked list

Question 22

State an explain an advantage and a disadvantage of the linked list data structure?

Answer 22

• Advantage: Dynamic data structure - a linked list can grow/shrink at run time as items aren’t held contiguously in memory.
• Disadvantage: Can be slow to search - doesn’t allow random access to the elements. Searching - requires starting at the beginning and following every pointer until item is reached.

Question 23

Describe what is meant by the term “Linked list”

Answer 23

• A dynamic data structure
• Each node/item consists of data and a pointer
• Pointer gives location of the next node

Question 24

Describe the difference between an array and a linked list?

Answer 24

• A linked list is a dynamic data structure whereas an array is static.
• An array can have any element accessed directly whereas a linked list needs to be traversed from start.
• Contents of an array are stored contiguously in memory whereas linked list may not be.

Question 25

What is a graph and how does it differ from a linked list and binary tree?

Answer 25

* Data structure consisting of vertices (nodes) and edges (pointers) * It differs from a linked list and binary tree because each vertex can have more than 2 edges and point to any vertex in the data structure.

Question 26

The edges in a graph can either:

Answer 26

* Point in 1 direction (directed graph) * Not specify a direction (undirected graph) * They can also be weighted with each edge given a value (can represent distance/time) representing a relationship between vertices.

Question 27

How are graphs usually stored as

Answer 27

* Store graphs as objects or using a dictionary known as adjacency lists * Can store using an array with rows and columns representing vertices and edges.

Question 28

What are the applications of a graph?

Answer 28

* Mapping road networks for navigation systems. * Storing social network data. * Resource allocation in Operating systems. * Representing molecular structures in geometry.

Question 29

What are some of the standard operations that can be performed on a graph?

Answer 29

* Adjacent: Returns whether there is an edge between 2 vertices. * Neighbours: Returns all vertices between 2 vertices. * Add: Adds a new vertex to the graph. * Remove: Removes a vertex from a graph. * Get Vertex Value/Set Vertex Value.

Question 30

What are the search operations that can be performed on a graph?

Answer 30

* Depth-First Search - Starts at the root vertex, visits each vertex and explores each branch before backtracking. * Breadth-First Search - Starts at the root vertex and visits each neighbouring node before moving to the vertices at the next depth.

Question 31

What are the Traversal operations that can be performed on a graph?

Answer 31

* Pre-Order Traversal * In-Order Traversal * Post-Order Traversal

Question 32

What is a stack?

Answer 32

. * Items are pushed onto the top of the stack when they are added to it and popped off the top when they are deleted. * Known as Last-In-First-Out Structure. * A stack has a pointer that always points to the node at the top.

Question 33

What is pushing an item to a full stack called and what is pooping an item from an empty stack called?

Answer 33

* Pushing an item onto a full stack is called stack overflow * Popping an item off an empty stack is called stack underflow.

Question 34

How can a stack be implemented?

Answer 34

* Often using an array or object-oriented technique.

Question 35

What are the applications of a stack?

Answer 35

* Used by processors to track the flow of programs. * When a procedure or function is called, it changes the value of the program counter to the first instruction of the subroutine * When the subroutine ends, the processor must return to the previous value. Allows subroutine calls to be nested. * Performing depth-first searches * Keeping track of undo operations * Backtracking algorithms * Evaluating mathematical expressions without brackets.

Question 36

What operations can be performed on a stack?

Answer 36

* Push - Adding an item to the top of the stack * Pop - Removing an item from the top of the stack * Peek - Returning the value from the top of the stack without removing it

Question 37

What is a queue?

Answer 37

* It is a linear data structure * Items are enqueued at the back and dequeued from the front. Can peek at front items without removing it * Known as First-In-First-Out structure * A queue has a back pointer that points to the last item and a front pointer that points to the first item.

Question 38

What is it called when you enqueue an item to a full queue and dequeue an item from an empty queue called?

Answer 38

* An attempt to enqueue an item in a full queue is called queue overflow * An attempt to dequeue an item from an empty queue is called a queue overflow.

Question 39

How is a queue implemented?

Answer 39

* Queues can be implemented using an array or object-oriented technique.

Question 40

Why is implementing an array create a problem?

Answer 40

* The back and front pointers are moving in the same direction as items are added and removed from the queue, the array will run out of space * Solution: cycle the back pointer to the front of the array when it reaches the end - circular queue.

Question 41

When is a circular queue good?

Answer 41

* An array with a circular queue is ideal if you want to restrict the number of items and have a known memory footprint. * Useful in game design where number of sprites affect framerate.

Question 42

What are the operations of a queue?

Answer 42

* Enqueue: Adding an item to the back of a 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 43

What are the applications of a queue?

Answer 43

* Processing schedule * Transferring data between processors and printer spooling * Performing breadth-first searches on graph data structures.

Question 44

What is a Tree?

Answer 44

* A data structure that consists of nodes and pointers * Each tree has a root node * Nodes at the bottom of the tree are called leaf nodes * Nodes are connected with pointers called edges

Question 45

What are the applications of a tree

Answer 45

* Storing and managing file and folder structure * Implementation of the A\* pathfinding algorithm * Storing/manipulating any form of hierarchal data and requires a parent node to have o, 1 or more child nodes

Question 46

What is a binary tree?

Answer 46

* Similar to the standard tree structure but each node can only have 0, 1 or 2 pointers. * Also the left branch of the tree must be less than the root node and right side greater

Question 47

How is a binary tree implemented?

Answer 47

* Can be represented in memory with dictionaries * Can be stored as arrays * Can be represented as objects - nodes with a left/right pointer

Question 48

What are the applications of a binary tree?

Answer 48

* Database applications where efficient searching and sorting is required * Wireless networking and router table * Operating systems and scheduling processes * Huffman coding, used for compression algorithms.

Question 49

What operations can be performed on a tree?

Answer 49

* Add, Delete a node from the tree * Binary Search, Pre-order traversal, In-order traversal, Post-order traversal, Breadth-first search

Question 50

Give 1 advantage of storing the words in a binary tree over an array?

Answer 50

* Can be searched quicker than an array

Question 51

What is a hash table?

Answer 51

* Has 2 components a table where the actual data is stored and a mapping function (hash function) * A hashing function is used to calculate the position of an item in a hash table.

Question 52

What is the goal of a hash table?

Answer 52

* Is to immediately find an item in a sorted or unsorted list without the need to compare other items in the data set.

Question 53

What is a collision?

Answer 53

* A hash table needs to be large enough to store all the data but is usually significantly larger to minimise the chance of the algorithm returning the same value for more than 1 item. * Since 2 data items can't occupy the same position - a collision has occured.

Question 54

What is the properties of a good hashing function?

Answer 54

* Be calculated quickly * Result in as few collisions as possible * Use as little memory as possible.

Question 55

What are the simplest solutions to resolve a collision?

Answer 55

* Repeatedly check the next available space in the hash table until an empty position is found and store the item there - open addressing

Question 56

What is linear probing?

Answer 56

* To find the item in hash table later, the hashing function delivers the start position from which a linear search can then be applied until the item is found

Question 57

What is a disadvantage of linear probing/open addressing?

Answer 57

* It prevents other items from being stored in their correct locations in the hash table. * It also results in clustering - several positions being filled around collision values.

Question 58

What is rehashing?

Answer 58

* The process of finding an alternative position for items in the hash table

Question 59

What are alternative methods for resolving collisions and what is separate chaining?

Answer 59

* To use a 2 dimensional hash table * It is then possible for more than 1 item to be stored at the same position. * Use a 2nd table for collisions, known as an overflow table which can be searched sequentially * Separate chaining - uses the original table to store dynamic data structure. When new item creates the same hash value. A new node on the linked list in that location is created to hold the data.

Question 60

What are the applications of a hash table?

Answer 60

* Used in situations where items in a large data set need to be found quickly: * File system linking a file name to the path of the file. * Identifying the keywords in a programming language during compilation

Question 61

What operations can be performed on a hash table?

Answer 61

* Add: Adds a new item to the hash table * Delete: Removes an item from the hash table * Retrieve: Retrieves an item from a hash table using its hash value.

Question 62

How can an array/ linked list be implemented through the use of a hash table and explain an advantage of each?

Answer 62

* Array: Store items before collisions * Advantage: Allows for random access by using the index * Disadvantage: Static, lots of unused space in the structure * Linked List: Store items after collisions * Advantage: Dynamic data structure * Disadvantage: Can be slow to search. Start from beginning.

Question 63

a) Explain why Police use a hash table than a linked list of objects to store data. b) Explain why modulus is used in hashing algorithms

Answer 63

a) There are a large number of motor vehicles. Accessing records must be quick b) Can take a large number and turn it into a smaller number creating an even spread of values across the data range.

Question 64

Explain why a hash table is better suited than a linked list to store the customer records, particularly as the customer acquires more customers.(4)

Answer 64

* A linked list requires every node to be checked (until the desired record is found) * A linked list will take longer to search (as more nodes are added) * A hash table enables direct access to the location * A hash table will take the same time to search as more nodes are added.

Question 65

What are the 2 types of searches used for traversing a graph

Answer 65

* Breadth-first search * Depth-first search

Question 66

What are the key steps for breadth-first search - uses a queue structure

Answer 66

* Set the root node as the current node * For every edge connected to the node (if not in the visited list) enqueue * Set the first item in the queue as the current node. Deque this item and enqueue anything linked to this that hasn't been visited. * Repeat until all nodes have been visited.

Question 67

What are the key steps for a depth-first search

Answer 67

* Set the root node as the current node * For every edge connected to the node - If the connected node is not in the visited list, push onto stack. * Pop the last item off the stack - set as current node and repeat from step 2 until no nodes left to visit - output all visited nodes.

Question 68

What type of data structure does breadth and depth search use?

Answer 68

* Breadth-first search uses queue structure that reaches a node with the minimum number of edges from the source node * whilst depth-first uses the stack structure. Traversing through more edges to reach the source.

Question 69

When is each of the traversing searches on graphs most suitable?

Answer 69

* Breadth-first search - searching nodes closer to the source node * Depth-first search - when there are solutions further away from a source.

Question 70

Which of the traversing a graph methods is most suitable for games/puzzles

Answer 70

* Depth-first search - explore all the paths through that decision. If the decision leads to a win situation. We stop.

Question 71

What are the key steps of adding an item to a linked list

Answer 71

* Check for free memory for a new node * Create a new node and insert data into it * If the new node should be inside the linked list: * Start at first node * If the data in the current node is less than the new node * Follow pointer to next node. once found * New node points to where previous node pointed * Node before points to new node

Question 72

What are the key steps of removing an item from a linked list?

Answer 72

* Check if the linked list is empty * If the item to delete is in the linked list * Start at the first node * If the current node is to be deleted : the previous node's pointer is set to point to the next node * If not then go to next node and repeat * Update the free pointer. Deleted item points to free node

Question 73

Explain how Birmingham is removed and York added London → Oxford → Birmingham → Manchester(null)

Answer 73

* Oxford pointer changed to bypass Birmingham and point to Manchester * A node is created holding the data York is placed in the next free space * Manchester remains in original position and pointer changed to point to York node * The York node points to null

Question 74

What are the key steps of traversing a linked list?

Answer 74

* Check if the linked list is empty * Start at the first node - starter pointer points to * Output the item * Follow the pointer to the next node * Repeat from step 3 until the end of list

Question 75

How do you add an item to a stack?

Answer 75

* Check if the stack is already full * Increment the stack pointer so it points to the next available space in the array. * Insert the new item into the space pointed by the stack pointer.

Question 76

How do you add an item to a queue

Answer 76

* Check if the queue is already full * Increment the back/tail pointer so it points to the next available space. * Insert the new data item into the location pointed by the back pointer.

Question 77

What are the key steps of removing an item from a stack?

Answer 77

* Check if the stack is empty * Copy the item pointed to by the pointer out of the stack - store in a variable * Decrement the pointer so it points back to the top.

Question 78

What are the key steps of removing an item from a queue?

Answer 78

* Check if the queue is empty * Copy the item pointed to by the front pointer out of the queue - store in a variable. * Increment the front pointer so it points back to the front of the queue.

Question 79

What are the 3 operations that a stack and queue support?

Answer 79

* Push/enqueue * Pop/dequeue * Peek

Question 80

How can you expose elements in the middle of a stack or a queue?

Answer 80

* Use peek to look at the top/front item to see what it is without altering it * Repeatedly Pop/dequeue items to output contents.

Question 81

How do you add a new item to a binary tree?

Answer 81

* Check if there is free memory for a new node * Create a new node and insert data into it. * Starting at the root node, check of the new node should be placed before or after the current node. * Work out if the item should be placed before or after the leaf node.

Question 82

How do you remove an item from a binary tree?

Answer 82

* Start at the root node and set as the current * Check if we need to enter a while loop * While the current node exists and is not the 1 to be deleted - while loop is entered. * Set the previous node to be the same as the current node * Check if the item to be deleted is less than or greater than the current node. * If less follow left pointer * If more follow right pointer * Check again if a while loop should be entered.

Question 83

Once the node has been found to be removed from a binary tree. What are the 3 different possibilities in which that node can be deleted.

Answer 83

* The node is a leaf node - no children * The node has 1 child * The node has 2 children

Question 84

How do you delete the node from a binary tree if they have no children?

Answer 84

* Delete the node and set the parent's pointer to null. (Can compare if the node to be deleted is greater/smaller than previous node)

Question 85

How do you delete the node from a binary tree if they have 1 child?

Answer 85

* You must update the pointer of the parent of the one to be removed to point to the child of the one to be deleted.

Question 86

How do you delete a node from a binary tree if they have 2 children?

Answer 86

* First you use in-order traversal to find the smallest node beneath the one to be deleted - successor node. * The successor node's left, right and parent pointers are updated so they are the same as the node to be deleted. * Only then is the target node is deleted.

Question 87

What are the methods of traversing a binary tree?

Answer 87

* Pre-order * In-order * Post-order

Question 88

How do you do a Pre-order traversal on a binary tree?

Answer 88

2 options: 1. Start at the root node - output this, traverse the left sub tree - do root, left, right, then traverse right subtree - do root, left, right. 2. Put dots on left of all nodes and draw around all points and output the order.

Question 89

How do you do an in-order traversal of a binary tree?

Answer 89

2 options 1. Traverse the left sub tree - do left, node, right, visit the root node - output this, traverse the right subtree - left, node, right. 2. Draw dots underneath all the nodes in the binary tree and draw around them.

Question 90

How do you do a post-order traversal

Answer 90

2 options 1. Go to left subtree. Do left-right-node. Go to right subtree. Do left-right-node. Output the root node last. 2. Draw dots on the right side of all nodes and draw around them. Write the output.

Question 91

What are the steps of adding an item to a hash table?

Answer 91

* Calculate the position of the item in the hash table using the hashing function * If the calculated position is empty insert and stop * If not, check the first position in the overflow table, if empty insert and stop or increment the position to find next available space.

Question 92

What are the steps of removing an item from a hash table?

Answer 92

* Calculate the position of the item in the hash table using the hashing function * If the calculated position contains the item to delete, delete + stop * If not check the first position of the overflow table + increment to next position to the next position if not already found.

Question 93

What are the steps of traversing an item from a hash table?

Answer 93

* Calculate the position of the item using the hashing function * Check the position if its the item * If it doesn't move to next position in the overflow table. If not increment and repeat. * If found output the item, If not: output “not found”

Question 94

Exam Question: What is the similarities between a tree and a graph data structure?

Answer 94

* Both consists of nodes * Both are connected by edges/links * Both are non-linear data structures * Both are dynamic data structures

Question 95

Exam Question: What is the differences between a graph and a tree data structure?

Answer 95

* Tree is 1-directional whereas a graph is 2-directional * Tree has a root node whereas a graph does not have a (clear) root node * Tree will not have cycles whereas graphs can contain cycles * Tree will not be weighted whereas edges in a graph can be weighted