Unit 7 - ADTs Flashcards
(124 cards)
1
Q
Elementry Data Types Examples
A
Boolean, char, integer, real
2
Q
Composite Data Types
A
Array, String
3
Q
Abstract Data Types examples
A
Stacks, Queues, Dictionaries
4
Q
Abstract Data Types (definition)
A
A logical description of how we view data and possible operations
5
Q
Static Data Types Definition
A
Fixed in size, cannot change size once program is running
6
Q
Dynamic Data types defininition
A
Can grow/shrink in size once program is running as it uses the heap
7
Q
The heap (memory)
A
A portion of memory which space is automatically allocated/ deallocated to as required
8
Q
Dynamic Data Structure Uses
A
Queues, as maximum size is not known before implementation
9
Q
Record Structure
A
Consists of a fixed number of variables called fields, each field can have a different data type
10
Q
Records in C#
A
Must be defined using a dictionary or using a class
11
Q
Tuples
A
Tuples are mutable data structures –> declared like a list
12
Q
Array Limitations
A
Size must be declared when created, cannot grow in size, one data type (in some languages including C#)
13
Q
Array Benefits
A
Can be any dimension, uses 0 based indexing, values are mutable
14
Q
Mutable Definition
A
Values can be changed whilst the programming is running
15
Q
enqueue(data)
A
Adds an element to the queue
16
Q
dequeue()
A
Removes (and returns) element from the queue
17
Q
peek()
A
returns element from queue without removing it from queue
18
Q
is_empty()
A
Checks if queue is empty
19
Q
is_full()
A
Check if queue is full (if it is static)
20
Q
What is a Queue
A
It is a mutable fifo data structure, meaning that items are added at the back and removed from the front
21
Q
Why circular queues exist?
A
When an item is dequeued, a space of memory is left however this is left at the front of the queues and data in a queue is only added at the back, this leaves memory being wasted and queues filling up fast, circular queues solve this problem
22
Q
How do circular queues work?
A
Let the queue be defined as an array. If the end is pointer is at the end of the array, however the start pointer is not at the front, a circular queue means that the next item to be enqueued will be added to the first slot on the array. The pointer for the end also points to here, this means that whilst the array is not full, data can keep being enqueued and it will go around in circles
23
Q
Application of Queues
A
Printer Queues, the thing that was printed first will be the first to be printed.
Simulations of actual queues eg in a supermarket
24
Q
How do priority queues work?
A
Each data is given a priority, the ones with the higher priorities are nearer to the front of the queue which means they are more likely to get dequeued sooner. When data is added it is added as the last one with that priority making it possible for it to be added at the front or in the middle
25
Why use a list instead of an array?
Lists are dynamic, arrays are static.
26
Similarity between Lists and Arrays
Both use zero based indexing,
27
Name of elements in linked list
Node
28
What must each node in a linked list store?
The data relating to that element, and a pointer, pointing to the next node
29
Advantages of linked lists
Dynamic, contiguous memory locactions are not required, can be used to implememtn stacks and queues, easy to insert data
30
Disadvantages of linked lists
Random access is not allowed so you have to sequencially access each element starting from the first one, extra memory space is required for each pointer, reverse traversing is difficult (unless a second pointer is used)
31
How to add data into a linked list? (simple)
Where the data is wanting to be added, change the pointer of the one before to point to that one and make the pointer of that element point to the next one.
32
How do you traverse a linked list?
Starting at the head, follow the pointers of each node until you reach a pointer pointing to null which means that you have reached the end of the list.
33
How hard is deleting data in a linked list?
Very easy as you just have to change the pointer in the node before it.
34
What is a doubly linked list?
A linked list with pointers pointing both forward and backwards.
35
What are graphs used to represent?
Complex, non-linear relashonships between objects.
36
What is the degree of a node on a graph?
The number of other nodes it is connected to. (the number of neighbours)
37
What is are neighbours on a graph?
Two nodes that are connected by an edge
38
What is a loop on a graph?
It is an edge that connects a node to itself.
39
What is a path on a graph?
A sequence of nodes that are connected by edges.
40
What is a cycle on a graph?
A cycle is a closed path, a path that starts and ends at the same node. However no iterim node can be visisted more than once.
41
Examples of what graphs can represent.
Social networks (whos friends with who etc), transport networks (the London Underground), the internet (each router is a node), the world wide web (each node is a webpage, edges show which ones are linked)
42
What is an undirected graph?
A graph which means that you can travel both to and from each node.
43
What is a directed graph?
Each edge of the graph has a direction (showing that you can only move in the specified direction between nodes).
44
What is a weighted graph?
On each edge of a weighted graph, there is a value. This can be used to represent many thing eg the distance between towns etc. Weights enable you to find the shortest paths.
45
Ways to implement a graph in code:
Adjacency matrix or adjacency list
46
What is an adjaceny matrix?
An adjaceny matrix is a two dimensional array where each node is represented by the index. If the data stored at [x,y] is not 0, eg in an unweighted graph it will be 1, in a weighted graph it will be the weight, there is an edge between x and y. If the graph is undirectionaly, the matrix will be simetrical.
47
What is an adjaceny list?
An adjacency list stores each node, and then what it is connected too. This could be implemented using a linked list or an array.
48
How are weights stored in an adjacency list?
Each list has both the node and the weight of that node eg. B links to D,15; H,40; F,46.
49
Pros of Adjacency Lists (compared to adjacency matrix)
They are space efficient for graphs with few edges and many nodes, it is easier to frequently add/ delete nodes from an adjacency list
50
Pros of Adjaceny Matrix (compared to adjacency list)
Easier to test for the presence/ absence of edges as each piece of infomation can be easily accessed by an index, it is also easier to remove edges from an adjacency matrix (not add them, they are the same)
51
What is a tree?
A tree is a connected, undirected graph with no cycles.
52
What is the root of the tree?
It is the start node for traverals, it also has no parents, if a tree has a root, it is rooted.
53
What is a branch on a tree?
A branch is a path from the root to an end point.
54
What is a leaf on a tree?
A leaf is an end point on a tree (a node which has no children)
55
How many edges does a tree have in terms of nodes?
N - 1, where N = number of nodes.
56
What are the relashonsips between nodes on a rooted tree?
They have parent-child relashonships.
57
What is a parent node?
It is a node which comes directly before another adjacent node (which is considered the child)
58
What is special about a binary tree?
In a binary tree, each node has a maximum of two children.
59
What is a binary search tree?
A rooted tree where the nodes of the tree are ordered.
60
If the nodes are ordered low to high, where are the lower values in relation to the root.
The lower values are on the left of the root.
61
In what order will an algerbraic expression tree give expressions?
It will give them in reverse polish notation, also known as post-fix.
62
Uses of binary trees:
Binary trees are used in compilers to build syntax trees, and are used within routers to store routing tables.
63
Uses of expression trees:
Represent boolean and algerbraix expressions in a way that simplifies the processing of the expression.
64
Unique way that binary trees can be implemented:
An array of records
65
What does each record represent in an array of records?
Each record represents a node.
66
What does each record store in an array of records?
Each records stores an index, the data for the node, the left child node, the right child node
67
Types of tree traversals:
Pre-order, post-order, in-order
68
What is the first node "visisted" in pre order traversal?
The root
69
Which branch do you traverse first in a pre order traversal?
Left
70
Uses of pre order traversals:
Can be used to duplicate the data to create an identical binary tree as parents are always read before children.
71
What would be the first node you visit using an in order traversal?
The leftest most node on the tree.
72
Uses of in order data:
Used to read data in order.
73
First node in a post order traversal:
Leftest most node.
74
Uses of post order tree traversals;
Used to delete data, as children are deleted first to avoid "hanging" children.
75
2+3 in post fix notation
2 3 +
76
Advantages of reverse polish notation (RPN)
RPN expressions do not need brackets, RPN is simpler for machines to calculate, there is need for backtracking
77
What is a stack?
Stacks are LIFO structures (last in first out), meaning data is added at the top AND taken from the top.
78
push(data)
This pushes the data onto the top of the stack (adds data to the stack)
79
pop()
This returns and removes data from the top of the stack
80
peek()
This returns the data from the top of the stack without removing it from the stack
81
is_empty()
Checks whether the stack is empty
82
is_full()
Checks whether the stack is full
83
Applications of stacks
Converting postfix notation to infix notation, used to maintain a list of operations on an undo button, stacks are used in call stacks
84
What is overflow in a stack?
When a stack is full and another item is attempted to be pushed, this causes overflow.
85
What is underflow?
When the stack is empty but something is attempted to by popped.
86
What is the function of a call stack?
A call stack holds information about active subroutines whilst a program is running (the details are hidden from the user)
87
What can the called stack hold?
Return addresses, parameters, and local variables.
88
Why are return addresses held in call stacks?
They are held so that when they are popped, they are returned, severat subroutines can be within one.
89
What is a hash table?
A hash table is a data structure that implements an associative array
90
What is an associative array?
(A dictionary) It is where data is stored as key, value pairs.
91
How is the position data in a hash determined?
It is determined by applying a hashing function (algorithm) to the key,
92
How to find data stored in the hash table?
You use the same hashing algorithm as the output will be the same if the input is the same.
93
Why use a hash table?
Hash tables are VERY efficient at searching, (best case constant time!!) So is adding and deleting.
94
What would you use to implement a hash function?
You must use an array so that you can use the index,
95
What size should a hash table be?
It should be large enough to store the values but not too large so that there is too much empty space but there should also be some empty space.
96
What is the load factor?
The load factor is n/k, where n is the number of occupied positions and k is the number of total positions.
97
What is the optimal load factor for a hash table?
0.75
98
99
What is a collision in a hash function?
This is where two keys will give the same index in the hash function.
100
What happens after a collision in a hash table?
Open Addressing (linear probing) or Closed Addressing (Seperate Chaining)
101
What is open addressing (linear probing)?
Placing data in the next free position or in the 2nd next position until a free position is found and so on depending on the algorithm.
102
What is seperate chaining (closed addressing)?
At each index, rather than the data being stored, there is a pointer to where the data is stored, if there is only one piece of data stored, it will point to null, however if a collision happens it will point to another piece of data stored at that index, creating a chain of nodes with the same index.
103
When are collisions more likely to happen?
As the size increases.
104
How to retrieve data if linear addressing has happened?
Hash the key, check if data in position is correct, if not use probing method to check the next locaction, keep going until correct data is found or an empty position is found (which means that the data is not in the hash table) .
105
How to retrieve data if closed chaining has happened?
Hash key to generate index, exam key to find head of the list, go through each piece of the list until you find the data or an empty position. If there is an empty position, the data is not in the hash table.
106
What is rehashing?
Rehashing is when a new hash table is created, the key for each item in the existing table is rehashed, and the item will be inserted into the new hash table. If the new table is larger, the hash function may need to be changed as it will need to generate a larger range of values.
107
Why can hashing be considered a type of encryption?
The hash function will be very easy to carry out one way, however almost impossible to do the reverse.
108
Why is hashing not foolproof for passwords?
Most hashing algorithms are well known, and hackers can use rainbow tables to store pre-hashed values, when a match is found, the password is revealed.
109
What can be used to prevent hackers from being able to use rainbow tables?
A salt- which is a random piece of data added to the password before it is hashed, therefore the same password on different systems may have different hash values.
110
What is a dictionary?
A data structure that holds data as a key-value pair.
111
What must keys be in a dictionary?
Keys must be unique and are normally simple data types (integers or strings)
112
Why should you use keys?
Keys are good to use as they provide direct access to the values even if they are unordered --> which is much quicker than othwise having to linear search through every one.
113
What is a vector?
A vector is an ADT that can represent both direction and magnitude, they are commonly used to represent movement.
114
How are vectors represented in maths and physics?
They are represented as arrow, the length is the magnitude the arrow is the direction.
115
How can a vector be represented?
A list, a 1-d array, a dictionary, graphically, using set notation.
116
What is set notation for a vector?
Using the set they are drawn from eg R for real numbers, N for natrual numbers etc, and the number of dimensions in the array = y, it would be written as R^y (if it is from the real set).
117
How would you say R^2?
A 2 vector over R
118
What is a position vector?
A position vector represents a point in space in relation to an origin.
119
What is the convex combination of two vectors?
It is a line that goes from a point where two vectors meet, to the line between the heads of two vectors.
120
What is the equation for the convex combination of two vectors u and v?
αu + βv, where u and v are vectors, α and β are both greater than 0 and add to1
121
What is the dot product used for?
Multiplying to vectors together.
122
Equation for dot product.
u * v = u_1*v_1 + u_2*v_2, u_3*v_3 +.. + u_n*v_n
123
Useage of the dot product:
If x holds price of products and y holds number of products sold, xy is the total revenue.
Can be used to calculate angle between vectors.
124
Equation of angle between vectors:
cosθ = (u*v)/ |u||v|
