1.4.2 Data Structures Flashcards
1
Q
What is an array?
A
- 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
2
Q
Name an example of a 1 and 2 dimensional array
A
- 1D = Names = [“Sam”, “Lucy”, “James”, “Jack”]
- 2D = Names = [[“Sam”, “Lucy”, “James”], [“Peter”, “Sarah”, “Adam”]]
3
Q
What is a record?
A
- 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.
4
Q
What is field?
A
- A field is a variable, and each field in a record can have a different data type.
5
Q
What are the steps of making a record structure
A
- 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
6
Q
What is a Tuple
A
- 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”)
7
Q
What is a data structure and name a few
A
- 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
8
Q
What does a static data structure mean and name an example
A
- Size is fixed when structure created / size cannot change during processing
- Array
9
Q
What is a dynamic data structure and name a disadvantage?
A
- 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
10
Q
What is a list?
A
- Lists is a simple data structure similar to an array. However like a tuple it can hold a range of data types
11
Q
What are the similarities and differences between an array, list or tuple
A
- 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.
12
Q
What are the similarities between constants and tuples
A
- 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
13
Q
What are the differences between constants and tuples
A
- A constant can only hold 1 value of 1 data type.
- A tuple is an unordered set of multiple values of different data types.
14
Q
What are the similarities between record structures and classes
A
- Are both features of high-level procedural languages.
- Record structures and class attributes can hold multiple data types (variables/ attributes) within 1 identifier
15
Q
What are the differences between record structures and classes
A
- 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.
16
Q
What is a doubly linked list?
A
- By adding an extra pointer, nodes can point to the next and previous items
17
Q
What is a circular list?
A
- Can be created by making the last node point to the first node
18
Q
What is a doubly circular linked list?
A
- Each node in a circular linked list can also have an additional pointer pointing to the previous item.
19
Q
What can be used to implement a linked list?
A
- 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.
20
Q
What are the applications of a linked list
A
- 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.
21
Q
What operations can be performed on a linked list?
A
- 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
22
Q
State an explain an advantage and a disadvantage of the linked list data structure?
A
- 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.
23
Q
Describe what is meant by the term “Linked list”
A
- A dynamic data structure
- Each node/item consists of data and a pointer
- Pointer gives location of the next node
24
Q
Describe the difference between an array and a linked list?
A
- 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.
25
What is a graph and how does it differ from a linked list and binary tree?
* 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.
26
The edges in a graph can either:
* 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.
27
How are graphs usually stored as
* 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.
28
What are the applications of a graph?
* Mapping road networks for navigation systems.
* Storing social network data.
* Resource allocation in Operating systems.
* Representing molecular structures in geometry.
29
What are some of the standard operations that can be performed on a graph?
* 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.
30
What are the search operations that can be performed on a graph?
* 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.
31
What are the Traversal operations that can be performed on a graph?
* Pre-Order Traversal
* In-Order Traversal
* Post-Order Traversal
32
What is a stack?
.
* 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.
33
What is pushing an item to a full stack called and what is pooping an item from an empty stack called?
* Pushing an item onto a full stack is called stack overflow
* Popping an item off an empty stack is called stack underflow.
34
How can a stack be implemented?
* Often using an array or object-oriented technique.
35
What are the applications of a stack?
* 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.
36
What operations can be performed on a stack?
* 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
37
What is a queue?
* 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.
38
What is it called when you enqueue an item to a full queue and dequeue an item from an empty queue called?
* 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.
39
How is a queue implemented?
* Queues can be implemented using an array or object-oriented technique.
40
Why is implementing an array create a problem?
* 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.
41
When is a circular queue good?
* 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.
42
What are the operations of a queue?
* 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.
43
What are the applications of a queue?
* Processing schedule
* Transferring data between processors and printer spooling
* Performing breadth-first searches on graph data structures.
44
What is a Tree?
* 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
45
What are the applications of a tree
* 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
46
What is a binary tree?
* 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
47
How is a binary tree implemented?
* Can be represented in memory with dictionaries
* Can be stored as arrays
* Can be represented as objects - nodes with a left/right pointer
48
What are the applications of a binary tree?
* 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.
49
What operations can be performed on a tree?
* Add, Delete a node from the tree
* Binary Search, Pre-order traversal, In-order traversal, Post-order traversal, Breadth-first search
50
Give 1 advantage of storing the words in a binary tree over an array?
* Can be searched quicker than an array
51
What is a hash table?
* 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.
52
What is the goal of a hash table?
* Is to immediately find an item in a sorted or unsorted list without the need to compare other items in the data set.
53
What is a collision?
* 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.
54
What is the properties of a good hashing function?
* Be calculated quickly
* Result in as few collisions as possible
* Use as little memory as possible.
55
What are the simplest solutions to resolve a collision?
* Repeatedly check the next available space in the hash table until an empty position is found and store the item there - open addressing
56
What is linear probing?
* 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
57
What is a disadvantage of linear probing/open addressing?
* 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.
58
What is rehashing?
* The process of finding an alternative position for items in the hash table
59
What are alternative methods for resolving collisions and what is separate chaining?
* 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.
60
What are the applications of a hash table?
* 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
61
What operations can be performed on a hash table?
* 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.
62
How can an array/ linked list be implemented through the use of a hash table and explain an advantage of each?
* 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.
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
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.
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)
* 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.
65
What are the 2 types of searches used for traversing a graph
* Breadth-first search
* Depth-first search
66
What are the key steps for breadth-first search - uses a queue structure
* 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.
67
What are the key steps for a depth-first search
* 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.
68
What type of data structure does breadth and depth search use?
* 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.
69
When is each of the traversing searches on graphs most suitable?
* Breadth-first search - searching nodes closer to the source node
* Depth-first search - when there are solutions further away from a source.
70
Which of the traversing a graph methods is most suitable for games/puzzles
* Depth-first search - explore all the paths through that decision. If the decision leads to a win situation. We stop.
71
What are the key steps of adding an item to a linked list
* 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
72
What are the key steps of removing an item from a linked list?
* 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
73
Explain how Birmingham is removed and York added
London → Oxford → Birmingham → Manchester(null)
* 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
74
What are the key steps of traversing a linked list?
* 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
75
How do you add an item to a stack?
* 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.
76
How do you add an item to a queue
* 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.
77
What are the key steps of removing an item from a stack?
* 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.
78
What are the key steps of removing an item from a queue?
* 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.
79
What are the 3 operations that a stack and queue support?
* Push/enqueue
* Pop/dequeue
* Peek
80
How can you expose elements in the middle of a stack or a queue?
* Use peek to look at the top/front item to see what it is without altering it
* Repeatedly Pop/dequeue items to output contents.
81
How do you add a new item to a binary tree?
* 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.
82
How do you remove an item from a binary tree?
* 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.
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.
* The node is a leaf node - no children
* The node has 1 child
* The node has 2 children
84
How do you delete the node from a binary tree if they have no children?
* 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)
85
How do you delete the node from a binary tree if they have 1 child?
* 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.
86
How do you delete a node from a binary tree if they have 2 children?
* 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.
87
What are the methods of traversing a binary tree?
* Pre-order
* In-order
* Post-order
88
How do you do a Pre-order traversal on a binary tree?
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.
89
How do you do an in-order traversal of a binary tree?
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.
90
How do you do a post-order traversal
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.
91
What are the steps of adding an item to a hash table?
* 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.
92
What are the steps of removing an item from a hash table?
* 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.
93
What are the steps of traversing an item from a hash table?
* 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”
94
Exam Question: What is the similarities between a tree and a graph data structure?
* Both consists of nodes
* Both are connected by edges/links
* Both are non-linear data structures
* Both are dynamic data structures
95
Exam Question: What is the differences between a graph and a tree data structure?
* 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
