1
Q
What are Data Structures?
A
- A way of organising and storing data to perform operations upon effectively
2
Q
What is an Array?
A
- An ordered, finite set of elements of a single type
3
Q
What is a Linear Array?
A
- A one-dimensional Array
4
Q
How can Two-Dimensional Arrays be visualised?
A
- Tables or Spreadsheets
5
Q
What can a three-Dimensional Array be visualised as?
A
- A multi-page spreadsheet
6
Q
What is a Record?
A
- A row (entry) in a file, made up of fields
- Used in databases
7
Q
What is a List?
A
- A data structure consisting of a number of ordered items where the items can occur more than once
8
Q
How do Lists differ from Arrays?
A
- Lists are stored non-contiguously in memory, while Arrays store data in order
- Lists can contain more than one data type, while Arrays store data of one type
9
Q
What is a Linked List?
A
- A dynamic data structure used to hold an ordered set of items which are not stored in contiguous locations
10
Q
How are Linked Lists set up?
A
- Each item is a node, and contains a Data Field alongside the Link, or Pointer Field
11
Q
What does the Data Field hold in a Linked List?
A
- Contains the value of the actual data which is part of the List
12
Q
What does the Pointer Field contain in a Linked List?
A
- The address of the next item in the List
- The index of the first item is also a pointer
- A pointer identifying the index of the next available space is also stored
13
Q
How is a Linked List traversed?
A
- The algorithm begins at the index given by the ‘Start’ pointer and outputs the values at each node until it finds that the pointer is empty or null - Signals the end of the linked list
14
Q
What is an advantage of using a Linked List?
A
- Values can be easily added or removed by editing pointers
15
Q
How can a value be added to a Linked List?
A
- Add the new value to the end of the linked list and update the ‘NextFree’ Pointer
- The pointer field of the value before where the value is to be inserted is updated to point to the inserted value
- The pointer field of the value just inserted is updated to point to the next value
- When traversed, the Linked List should contain the newly inserted value
16
Q
How can a value be removed?
A
- The pointer field of the node before the the node being removed should be updated to point to the node after
- When traversed, the Linked List will omit the node that no longer has pointer fields leading to it
17
Q
What is the disadvantage of Linked Lists?
A
- A node is not truly removed from the List, it is only ignored, which wastes memory
- Linked Lists can only be traversed in order; an item cannot be directly accessed
18
Q
What does isEmpty() do to a List?
A
- Checks if the List is empty
- Example: listName.isEmpty()»_space; False
19
Q
What does append(value) do to a List?
A
- Adds a new value to the end of the List
- Example: listName.append(15)
20
Q
What does remove(value) do to a List?
A
- Removes the value the first time it appears in the List
- Example: listName.remove(23)
21
Q
What does search(value) do to a List?
A
- Searches for a value in the List
- Example: listName.search(38)»_space; False
22
Q
What does length() do to a List?
A
- Returns the length of the List
- Example: listName.length()»_space; 7
23
Q
What does index(value) do to a List?
A
- Returns the position of the item
- Example: listName.index(23)»_space; 0
24
Q
What does insert(position, value) do to a List?
A
- Inserts a value at a given position
- Example: listName.insert(4, 25)
25
What does pop() do to a List?
- Returns and removes the last value in the List
- Example: listName.pop() >> 12
26
What does pop(position) do to a List?
- Returns and removes the value in the List at the given position
27
What is a Tuple?
- An immutable (unchangeable), ordered set of values of any type
28
How are Tuples initialised?
- Using regular brackets ( ) instead of square brackets
29
What is a Graph?
- A set of vertices/nodes connected by edges/arcs
30
What is a Directed Graph?
- The edges can only be traversed in one direction
31
What is an Undirected Graph?
- The edges can be traversed in both directions
32
What is a Weighted Graph?
- A cost is attached to each edge
33
How do Graphs differ from Linked Lists and Binary Trees?
- Each vertex is able to have more than two edges and point to any vertex in the data structure
34
What are the advantages of an Adjacency Matrix?
- Convenient to work with due to quicker access time
- Easy to add nodes
35
What is the advantage of an Adjacency List?
- More space efficient for large, sparse networks
36
What is Breadth-First?
- Node-based method of finding the shortest path through a Graph
- Makes use of a Queue and FIFO
- One Node at a time is selected, visited, and marked: Adjacent Nodes are visited and stored in a Queue
37
What is the process of a Breadth-First traversal?
1. Set the Root Vertex as the current vertex
2. Add the current Vertex to the list of visited Vertices if not already on the list
3. For every Edge connected to the Vertex
a) If the linked Vertex is not in the visited List:
i. Enqueue the listed Vertex
ii. Add the linked Vertex to the visited List
4. Dequeue and set the Vertex removed as the current Vertex
5. Repeat step 2 until the Queue is empty
6. Output all the visited Vertices
38
What is Depth-First?
- Edge-based technique that makes use of a Stack and LIFO
39
What are the two main stages of a Depth-First search?
- Visited Nodes are pushed onto the Stack
- When there are no Nodes left to visit, the Nodes are popped off the Stack
40
What is the process of a Depth-First traversal?
1. Set the Root Node as the current Node
2. Add the current Node to the list of visited Nodes, if it isn't already on the list
3. For every Edge connected to the Node:
a) If the connected Node is not in the visited List, push the linked Node onto the Stack
4. Pop the Stack and set the removed item as the current Node
5. Repeat from step 2 until there are no Nodes left to visit
6. Output all the visited Nodes
41
What are the main points of a Breadth-First traversal?
- Uses a Queue to find the shortest path through an Unweighted Graph
- Reaches a Node with the minimum number of Edges from the source Node
- More suitable for searching Nodes that are closer to the source Node
- Considers all neighbours first, so isn't suitable for decision-making Trees used in games or puzzles
42
What are the main points of a Depth-First traversal?
- Uses a Stack
- May traverse through more Edges to reach a destination Node from the source
- More suitable when there are solutions further away from a source
- More suitable for game or puzzle problems: A decision is made, all paths of the decision are explored, and if the decision leads to a win situation, it is stopped
43
What is a Stack?
- A Last In First Out (LIFO) Data Structure
44
What is the key feature of a Stack?
- Items can only be added or removed from the top of the stack
45
What are Stacks used for?
- Reversing actions, such as going back a page in web browsers, and undo buttons
46
How can Stacks be implemented?
- As either a static structure or a dynamic structure
- Using a pointer that points to the top of the stack, where the next piece of data will be inserted
47
When are static Stacks preferred?
- When the maximum size required is known in advance, as they are easier to implement and make more efficient use of memory
48
What does isEmpty() do to a Stack?
- Checks if the Stack is empty
- works by checking the value of the top pointer
- Example: stackName.isEmpty() >> True
49
What does push(value) do to a Stack?
- Adds a new value to the end of the Stack
- Needs to check that the Stack is not full before pushing to the Stack
- Example: stackName.push("Jay")
50
What does peek() do to a Stack?
- Returns the top value from the Stack
- First checks the Stack is not empty by looking at the value of the top pointer
- Example: stackName.peek() >> "Jay"
51
What does pop() do to a Stack?
- Removes and returns the top value of the Stack
- First checks the Stack is not empty by looking at the value of the top pointer
- Example: stackName.pop() >> "Jay"
52
What does size() do to a Stack?
- Returns the size of the Stack
- Example: stackName.size() >> 2
53
What does isFull() do to a Stack?
- Checks if the Stack is full
- works by comparing stack size to the top pointer
- Example: stackName.isFull() >> False
54
What is Underflow?
- If the Stack Pointer is at -1
- An attempt to pop() will result in an Underflow Error
55
What is Overflow?
- An attempt to push() another item onto the Stack when the Stack has reached maximum size
56
What is a Queue?
- A First In First Out (FIFO) Data Structure
57
What is the key feature of a Queue?
- Items are added to the end of the Queue and are removed from the front of the Queue
58
Where are Queues commonly used?
- In printers, keyboards, and simulators
59
What is a Linear Queue?
- A Data Structure consisting of an Array
- Items are added to the next available space in the Queue, starting from the front
- Items are removed from the front of the Queue
60
How do Queues make use of Pointers?
- Two pointers: One pointing to the front of the Queue, and one pointing to the back where the next item can be added
61
What is the disadvantage of a Linear Queue?
- As the Queue removes items, there are addresses in the Array which cannot be used again, making a Linear Queue an ineffective implementation of a Queue
62
What is a Circular Queue?
- A Queue where once the rear pointer is equal to the maximum size of the queue, it can loop back to the front of the Array to store values, provided it is empty
- Use space in an Array more effectively, but can be harder to implement
63
What does enQueue(value) do to a Queue?
- Adds a new item to the end of the Queue
- Increments the back pointer
- Example: queueName.enQueue("Jay")
64
What does deQueue() do to a Queue?
- Removes the item from the front of the Queue
- Increments the front pointer
- Example: queueName.deQueue()
65
What does isEmpty () do to a Queue?
- Checks if the Queue is empty by comparing the front and back pointer
- Example: queueName.isEmpty() >> False
66
What does isFull() do to a Queue?
- Checks if the Queue is full by comparing the back pointer and Queue size
- Example: queueName.isFull() >> False
67
What is a Tree?
- A connected form of a Graph
68
How are Trees laid out?
- Contain a Root Node, the top of the Tree, connected to other Nodes using branches, with the lower-level nodes being the children of the higher-level Nodes
69
What is a Node?
- An item in a Tree
70
What is an Edge?
- Connector of two Nodes
- Also known an a Branch, or Arc
71
What is a Root?
- A single Node which does not have any incoming Nodes
72
What is a Child?
- A Node with incoming Edges
73
What is a Parent?
- A Node with outgoing Edges
74
What is a Subtree?
- A subsection of a Tree consisting of a Parent and all the Children of the Parent
75
What is a Leaf?
- A Node with no Children
76
What is a Binary Tree?
- A type of Tree in which each Node has a maximum of two Children
77
What are Binary Trees used for?
- To represent information for Binary Searches, as information in these Trees is easy to search through
78
What is the most common way of representing a Binary Tree?
- Storing each Node with a left Pointer and a right Pointer in a two-dimensional Array
79
What is a Hash Table?
- An Arrays that is coupled with a Hash Function that takes in data (a key) and releases an output (the Hash)
80
What is the role of the Hash Function?
- To map the key to an index in the Hash Table
81
What is a Collision in a Hash Table?
- When two inputs result in the same Hash value
82
What is the feature of a good Hashing Algorithm?
- Low probability of Collisions
83
What is Collision Resolution?
- Placing an item that has had a Collision into the next available location
84
What are Hash Tables used for?
- Indexing as they provide fast access to data due to keys having a unique, one-to-one relationship with the address at which they are stored
85
Decks in class (3)
# Cards
