Topic 2 - Fundamentals of data structures Flashcards
Define data structure?
Is the format used to efficiently store & organise a collection of related data items
Define array?
A data structure made up of a list of data elements that are the same data type or size
Example of a one-dimensional & two-dimensional array?
List
Table
Define text files?
Store data in humanly readable format
Define binary files?
Store data which is not in a humanly readable format, must be interpreted by a program or hardware.
Define static data structure?
Data storage method where the amount of data and memory allocated is fixed. e.g. an array
Define dynamic data structure?
Data storage method where the amount of data and memory allocated is varied to meet the needs of the application using it. e.g. a vector
One advantage of static data structures?
Memory addresses will be allocated at compile time, so will be fixed and contiguous, permitting faster access
One advantage of dynamic data structures?
Meets the needs of the application, effiecient use of memory
Define a queue?
Is used as a temporary storage space for data.
An abstract data structure which operates on FIFO.
Define a linear queue?
Is a FIFO data structure organised as a list of data
Define a circular queue?
Is a FIFO data structure organised in a ring formation
Define a priority queue?
Is similar to a regular queue except that each element is assigned a priority and the highest-priority are served first
Define a stack?
Is an abstract data type which uses FILO
What are the 3 operations which can be performed on a stack?
- Push
- Pop
- Peek (or top)
What does the push operation do on a stack?
Adds items of data to the top of the stack
What does the pop operation do on a stack?
Removes the last item of data from the stack
What does the peek operation do on a stack?
Reads the top element in the stack without removing it from the stack
Define a graph?
Used to represent complex relationships such as computer interconnection drawings.
What are the 4 parts to a graph? V/N E/A W/UW D/UD
- Vertex/node
- Edge/arc
- Weighted/Unweighted graph
- Directed/Undirected graph
Define a vertex/node?
Is a value or node (with a circle around it)
Define an edge/arc?
Is used to connect two nodes or vertices
Define weighted to an unweighted graph?
Weighted - Is a graph that has labels on each edge/arc to indicate a data value.
Unweighted - is a graph that has no labels on each edge/arc to indicate its data value.
Define directed and an undirected graph?
Directed - Is a graph where the direction of travel between vertices can only be one-way, as directed by the arrow.
Undirected - Is a graph where there is no set direction of travel from each node.
Define an adjacency list?
Used to represent a graph by listing each node and the nodes directly connected to it
State 2 comparisons of adjacency list & matrix?
Adjacency list stores details of graphs where an edge exists
Matrix stores details of all node adjacencies, where an edge exists as a 1 and where it doesn’t as a 0
Was is the difference between a sparse and dense graph?
Sparse - With few edges, makes it faster and saves memory to use an adjacency list to store the data set.
Dense - With many edges, since all permutations of adjacencies are identified, it’s faster to store the data set as an adjacency matrix.
Define a tree graph?
Is an abstract data type based on undirected graphs that don’t contain cycles. Each node can only be reached through one path.
What are 4 parts of a tree graph? R P C L
- Root
- Parent
- Child
- Leaf
Define a root in a tree graph?
Is the starting node that has no parents, all other nodes branch off from it.
Define a parent in a tree graph?
This node has further nodes branching from it, which are called children.
Define a child in a tree graph?
This node has nodes above it in the tree, which are called parents.
Define a leaf in a tree graph?
This node has no nodes below it, is the last node on the tree edge
Define a binary tree?
A tree structure where each node has a maximum of two child nodes is unordered since there are no relationships between a parent node and its child node.
Define a binary search tree?
This is an ordered or sorted binary tree with the recursive relationships that for each node the left child is less than the parent node and the right node is more than the parent node.
What are binary trees used for?
- Routing the best path in a network, such as a telephone network.
- Storing data in an easy-to-find, searchable format using standard tree traversal methods.
- Storing hierarchal data, such as a dictionary tree for file management purposes.
Define a hash table?
Is a data structure that stores data in an associative way.
The table is created using a hash function which maps a key to an index in an array to find the value of an array element.
Define hash function?
Takes the data input known as a key and outputs an integer known as a hash value; this value maps the key to a particular index in the hash table.
Define collision?
Is where two keys are applied to the hash function and create an identical hash value; hash functions are chosen with the aim of minimising the chance of collisions.
Define linear probing?
Is where a key is assigned to the next available slot in the hash table if there is a collision.
Define a linked list?
Is a linear data structure in which a group of nodes contain data and make use of a pointer to link with the next data element.
Define separate chaining?
Is where the hash table index is a pointer to a linked list data structure that contains the data.
There are no collisions the linked list contains on element and the linked list will contain all of the collisions for a particular slot.
Define a dictionary?
Is a data structure that contains a collection of ‘key-value’ elements where the data value is accessed by the associated data.
What 3 operations can a dictionary perform?
- Find: or search for a key returns the value
- Add: or insert a key-value pair, unordered data
- Delete: removes the key and its associated value
Define a vector?
Vectors can automatically grow to store additional elements. The individual elements of a vector can be assessed efficiently via an index.
Similar to arrays
What are the 3 ways vectors can be stored in?
- List of real numbers
- Functional interpretation
- Geometric vector
What is the list of real numbers in a vector?
e.g. 4-vector over R (R^4)
[1.2, 5.25, -4.3, 1.75]
What is the functional interpretation in a vector? 0 = 1.2 1 = 5.25 2 = -4.3 3 = 1.75
S —> R
S = {0,1,2,3} R = {1.2, 5.25, -4.3, 1.75}
