Unit 7 - Data Structures Flashcards
1
Q
Why do abstract data types make it easier to manage data?
A
We do not have to be concerned with how the data is stored or how operation work on the data we just need to know the outcome
2
Q
How is an abstract data type an example of encapsulation?
A
It self contains all of the data and the methods associated with that data within one object
3
Q
How is an abstract data type an example of abstraction?
A
The user is not concerned with how the methods associated with the data work they just need to know how to initialise them
4
Q
Give an example of an abstract data type
A
Queue, tree, stack, list, graph
5
Q
Describe the principles of operation of a queue
A
When you add an item to a queue it is added at the back, you cannot add an item at the front of a queue. When an item is deleted from a queue it is not removed from the data structure the pointer just moves on to the next one
6
Q
Describe how a queue works
A
- When an item is added it is added to the back of the queue
- There is a front pointer and an end pointer
- The item being processed is the one in the same position as front pointer
- Once it has been processed the front pointer moves up one but the item remains in the queue
7
Q
What are the four operations performed on a queue?
A
- enQueue()
- deQueue()
- isEmpty()
- isFull()
8
Q
What is the front pointer?
A
It indicates which item is next to be processed
9
Q
What is the rear pointer?
A
Indicates which item was last added to the queue
10
Q
T/F: Queues do not shuffle data
A
True
11
Q
What is the disadvantage of linear queues?
A
They only have a finite number of blocks in the queue and once they have been filled no more can even be added because queues do not shuffle or remove data
12
Q
How do circular queues work?
A
In a circular queue the front and rear pointers are able to double back on themselves meaning that they can loop around the queue and write over data in previous slots that has already been processed even though it cannot be deleted
13
Q
What function enables you to determine the location of an item in a circular queue from the beginning?
A
The MOD function
14
Q
How do priority queues work without shuffling data and still using the ‘first in first out’ principle?
A
They work by organising the elements added into priorities which are effectively sub-queues. This means that the first in first out principle does still apply but just within a priority
15
Q
Why can you not add infinitely to any data structure?
A
Because the memory heap for that data structure will always have a finite size
15
Q
Describe how to find the position of an item in a circular queue
A
(Position of front pointer + Number of items in the queue) + (Change in time/Time taken to deQueue an item) (%)
15
Q
Define memory heap
A
A section of memory that is reserved for use by a data structure
15
Q
Define array
A
A set of related data items stored under a single identifier
15
Q
What are the 9 programming operations used on lists?
A
- isEmpty()
- append(item)
- remove(item)
- count(item)
- len(list)
- index(item)
- insert(pos, item)
- pop() < last item in the list
- pop(pos)
15
Q
Why is a list an abstract data type?
A
We can perform operations on a list and on the data in the list without needing to know how they work .e.g. append
15
Q
How does a memory heap contribute to the management of a list?
A
A memory heap is allocated to the list and when an item is added it is added to a location designated to the heap assigned to the list, when it is removed the empty location is returned to the heap
15
Q
Why is a stack useful?
A
When using recursive algorithms it is used to unravel the recursion when the function is returned .e.g. depth-first searches of trees
16
Q
Define stack
A
A data structure where the last item added is the first item removed
16
Q
Why is a stack useful for reversing strings?
A
The order of insertion is the opposite of the order of removal
17
What are the 6 basic operations used with stacks?
1. push(item)
2. pop() < removes the top item and removes it
3. isFull()
4. isEmpty()
5. peek() < returns the top item without removing it
6. size()
18
How can a stack be implemented as a list?
Use the list commands to refer to stack commands .e.g. append refers to push
19
Define overflow in terms of a stack
When you try to push an item onto a stack and it is full
20
Define underflow in terms of a stack
When you try to pop and item from a stack and it is empty
21
Define system level data structure
A data structure that dictates how computational processes are carried out
22
Give an example of a system level data structure
A call stack or stack frame
23
What is a stack frame?
A stack frame consists of an individual subprogram's local variables, arguments and return address
24
How is a call stack formed?
Multiple stack frames are combined
25
What does a stack frame do with regards to subprograms?
It dictates how parameters and return addresses are passed to subroutines
26
Define a return address
The address to the point in the program execution is to return to after a subprogram has been executed
27
What are the two stages of running a subprogram?
Subroutine call and subroutine execution
28
What happens during the subroutine call?
The computer saves the parameters to the stack, saves the local variables to the stack, saves the return address to the stack and then transfer execution to the subroutine code
29
What happens during the subroutine execution?
The computer allocates a stack space for local variables, executes the subroutine code, retrieves the return address from the stack, pops the parameters from the stack (used in the return) and transfers execution back to the return address
30
Define hash table
A data structure that stores key:value pairs based on an index calculated from an algorithm
31
What is the purpose of a hash function?
To calculate the position of a data item within an abstract data type called a hash table dependent on the value of the data item
32
What is the typical format for a hash function?
Address = key % No.slots
33
Why is the MOD function used in hash functions?
To ensure that the address location for a key does not exceed the maximum size of the hash table
34
Define collision/synonym
When two values end up with the same memory location within a hash table
35
What is the simplest solution when a collision or synonym occurs?
To put the second item in the next available slot
36
Define load factor
The percentages of the hash table that has values stored in it
37
What is a cluster?
When the majority of items in a hash table are located in one area of the table
38
How does a cluster arise in a hash table?
When collisions are resolved by just placing the second item in the next available slot
39
What is the solution to clustering?
Introducing a skip factor
40
What does a skip factor do?
Spreads values involved in collisions across the hash table
41
What happens when the load factor gets too high?
Collisions increase which decreases efficiency
42
What is the best way to reduce the load factor on a table?
Remove the data, increase the size of the hash table and rehash the data
43
Why is rehashing the data better than trying to work with a high load factor?
The time taken to rehash the data is less than the time lost through data collisions with a high load factor
44
Describe the mid-square method
The item to be stored is squared and a portion of these digits are selected and the MOD function is applied to them
45
Describe the folding method
The item to be stored is split into equal parts (the last part may be uneven if the number of digits is a prime number) and the MOD function is applied to the sum of these parts
46
What are the mid-square method and folding method examples of?
A hash function
47
How is alphanumeric data stored in a hash table?
Characters are converted to their binary equivalent in the ASCII tables and then treated the same as digits
48
How is a dictionary different to a list?
Each value is assigned to a key and referenced from the main program using that key
49
Why is a dictionary more efficient than a list?
The whole list does not need to be searched each time one item needs to be located
50
What can you do if you want to store multiple items under one key?
Assign a key to another ADT such as a list
51
What is one thing you can never do with a dictionary?
Store multiple values under one key
52
What are the 6 main operations used when working with a dictionary?
1. Adding a new pair
2. Deleting a pair
3. Amending a pair
4. Returning a value associated with a key
5. Returning True or False depending on whether the key is in the dictionary
6. Returning the length of the dictionary
53
How do dictionaries used hash functions?
Hash functions are used to determine the location of each key:value pair within the memory heap
54
Why does a dictionary not need to be sorted?
Values are referenced using their key and not using any other form of search such as a binary search
55
What is a graph used for?
A graph represents complex relationships between data points
56
Define node
An element of a graph or tree that represents a piece of data
57
Define edge
An element of a graph or tree that represents the relationship between two nodes
58
Define edge weight
The cost of travelling an edge between two nodes
59
Define a directed graph
A graph where the relationship between nodes is unidirectional
60
Define an undirected graph
A graph where the relationship between nodes is bidirectional
61
Define a weighted graph
A graph that has weights attached to edges
62
Define an unweighted graph
A graph that does not have weights attached to edges
63
What are two other ways of representing a graph?
An adjacency list or an adjacency matrix
64
How is an adjacency matrix structure?
Each row or column represents a node
A directed graph: the y-axis is the node the relationship is going to and the x-axis is the node the relationship is going to (need to change this)
A weighted graph: the edge weight is placed in the box corresponding to the relationship
An unweighted graph: a one is placed in the box corresponding to the relationship
65
T/F: an adjacency matrix for an undirected graph is symmetrical across the line y = -x
True
66
What are the advantages of an adjacency matrix?
1. Easy to work with
2. Adding an edge is easy
67
What are the disadvantages of an adjacency matrix?
1. A sparse graph takes up unnecessary memory space as empty cells still have to be allocated
68
How does an adjacency list work?
Each node is linked to a list of adjacent nodes (a dictionary is typically used to do this)
69
How is a dictionary used for an adjacency list in a weighted graph?
Key:value pairs are nested in a sub-dictionary with the main key being the node and the sub-keys being the nodes adjacent to it with the values being the weight of the edges
70
What are the advantages of an adjacency list?
1. Storage efficient
2. Effective for large and sparse graphs
3. Useful for implementing graphs in programming languages
71
What are the disadvantages of an adjacency list?
1. Can be complicated to work with
2. Not efficient for large and full graphs
72
List some of the applications of graphs
Computer networks, chemistry, project management and web pages
73
Define tree
A graph that is unidirectional and has no cycles
74
Define rooted tree
A tree that has one node identified as the root and every node has a parent except for the root
75
Define root
The node upon which all others are dependent in a rooted tree
76
Define child
A node which has other nodes above it in the hierarchy
77
Define parent
A node which has other nodes below it in the hierarchy
78
Define subtree
A tree that falls below a node in the hierarchy
79
Define leaf
A node that does not have any other beneath it in the hierarchy
80
Define binary tree
A rooted tree in which each node has a maximum of two children and is ordered to ease the searching processes
81
Define traversal
The process of reading data from a tree by visiting all of the nodes
82
Describe pre-order traversal
Visiting the root, traversing the left subtree and then the right and repeating this until the whole tree has been traversed
83
Describe in-order traversal
Traversing the left subtree, then visiting the root and the traversing the right subtree
84
Describe post-order traversal
Traversing the left subtree, then traversing the right subtree and then visiting the root
85
What is the easy way to remember the order of visiting nodes in each traversal?
A dot to the left of the node is pre-order, a dot under the node is in-order and a dot to the right of the node is post-order; the order in which you pass the dots moving from left to right around the tree is the order the nodes are visited
86
How are items added to a binary tree?
If the value of the child is less than the value of the parent it is added to the left of the parent, if it is greater it is added to the right of the parent
87
Why is a binary tree beneficial?
It is easier to search for an item in a binary tree because it is conducted in a similar way to a binary search, being able to discard half of the items with each evaluation
88
Define a balanced binary tree
A binary tree where each node has exactly two children
89
Why is a balanced binary tree ideal?
It is the most efficient as the height is kept to a minimum
90
How is a binary tree represented as an array of records?
Each node is associated with three piece of information [right pointer, data, left pointer] and these sublists can be added to a larger list representing the whole tree
91
Define vector
A mathematical quantity that has both magnitude and direction
92
List three ways a vector can be represented in a program
A function (S → R where S = {0, 1} and R = [2.55, -3.88]), a list of real numbers ([5.77, 2.4]) or in a dictionary ({0: 9.22, 1: 3.41, 2: 5.67})
93
Why can't 4D vectors be illustrated on graphs?
They involve the curvature of spacetime
94
How are vectors added together?
Pairs of corresponding numbers in each mathematical function are added together or you can graphically top and tail them
95
What happens to vectors in scalar multiplication?
The magnitude of the scalar is increased as each value in the mathematical expression is multiplied by a constant
96
Describe convex combination of vectors
This is the method used to derive an equation for a vector that will lie anywhere in an area enclosed by two other vectors
97
What is the equation for the convex combination of vectors?
w = au + bv
(u and v are the original vectors and a and b are constants)
98
What are the requirements for a and b in the equation for the convex combination of vectors?
a > 0, b > 0 and a + b = 1
99
What is one real world application of the convex combination of vectors?
Defining the field of view for first person perspective shooter games
100
What is the dot product used for?
It is used to calculate the angle formed by a vector
101
What is the general formula for the dot product of two vectors?
u x v = u1v1 + u2v2 + u3v3 ...
102
Define dynamic data structure
A data structure with a variable size
103
Define static data structure
A data structure with a fixed size
104
Define abstract data type
A mathematical model for a data structure
105
What are the advantages of a dynamic data structure?
1. No wasted memory
2. No limit on the number of items that can be added unless there are hardware limitations
3. Resources only allocated as they are needed
106
What are the disadvantages of a dynamic data structure?
1. Additional memory needed for pointer
2. Can result in a memory leak if memory that is no longer needed is returned to the heap
107
What is the MOD function to identify the position of pointer for a circular queue?
Number of pieces of data added % the number of slots available (this means it will loop back round to the start when the size of the circular queue has been reached)
108
Define cycle with respect to graphs
A closed path that starts and ends at the same node
109
Define path with respect to graphs
A sequence of nodes connected by edges
110
What are the common uses of a hash table?
1. Creating indices for databases to enable quick storage and retrieval of data
2. Generate memory addresses for data to be stored, particularly used in cache memory
3. Indexing keywords and identifiers in programming to enable quick access
4. Producing a checksum to check if transmitted data it corrupted
111
What is the ideal load factor for a hash table?
0.75
112
T/F: Keys in dictionaries can be any data type
False: they must be a primitive data type
