1.2 Fundamentals of data structures Flashcards
What is a data structure?
A data structure is any method used to store data in an organised and accessible format
What is an abstract data type?
A conceptual model of how the data is stored and the operations that can be performed upon them
Define queue
A data structure where the first item added is the first item removed
Define stack
A data structure where the last item added is the first item removed
What is a static data structure?
A method of storing data where the amount of data stored and the memory used to store it is fixed
What is a dynamic data structure?
A method of storing data where the amount of data stored and memory used to store it will vary as the program is being run
Define heap
A pool of unused memory that can be allocated to a dynamic data structure
Define stack frame
A collection of data about a subroutine call
Define call stack
A special type of stack used to store information about active subroutines and functions within a program
Define interrupt
A signal sent by a device or program to the processor requesting its attention
Define recursion
The process of a subroutine calling itself
Define the 3 different types of queue
- Linear: a first in first out structure organised as a line of data such as a list
- Circular: a first in first out structure implemented as a ring where the front and rear pointers can wrap around from the end to the start of the array
- Priority: a variation of a first in first out structure where some data may leave out of sequence if it has a higher priority than other items
Define graph
A mathematical structure which models the relationship between pairs of objects
Define vertex
An object in a graph, this can also be known as a node
Define arc
A join or relationship between two nodes, this can also be known as an edge
What is a weighted graph?
A graph that has a data value labelled on each edge
Define directed graph
A directed graph is a graph where the relationship between nodes is one way
Define unirected graph
A graph where the relationship between vertices is two way
Define adjacency list
A data structure that stores a list of nodes with their adjacent nodes
Define adjacency matrix
A data structure set up as a two dimensional array or grid that shows whether there is an edge between each pair of nodes
What are the differences between an adjacency list and an adjacency matrix?
- An adjacency list only stores data when there is an edge so it requires less memory than an adjacency matrix which stores a value for every combination of adjacencies
- In an adjacency matrix it is faster to check if an adjacency exists as all possible adjacencies are stored, whereas in adjacency list you have to check the whole list to see if it exists
- Adjacency lists are more suitable for graphs with few nodes (sparse graphs) and adjacency matrices are more suitable for graphs with more nodes (dense graphs)
Define tree
A data structure similar to a graph with no loops
Define root
The starting node in a rooted tree structure from which all other nodes branch off
Define parent
A type of node in a tree where there are further nodes below it
Define child
A node in a tree that has nodes above it in the hierarchy
Define leaf
A node that does not have any other nodes beneath it
What is a binary tree?
A tree where each node can only have up to 2 child nodes attached to it
What are the uses of a tree?
- Can be used to store data that has an inherent hierarchical structure
- Are dynamic so it is easy to add and delete nodes
- Easy to search and sort with traversal algorithms
- Can process syntax of statements so commonly used in compiling code
Define hash table
A data structure that stores key / value pairs based on an index calculated from an algorithm
Define key / value pair
The key and its associated data
What is a hashing algorithm?
Code that creates a unique index from given items of key data
How do hash tables function?
A hashing algorithm is carried out on the piece of data / key, which gives a value that acts as an index for that data item within the array of data. The same key can then be put through the hashing algorithm to look up and locate data within the hash table
What are some uses of hashing algorithms?
- Used to create indices for databases for quick storage and retrieval of data
- Used to generate memory addresses where data will be stored
- Used to encrypt data
- Used to index keywords and identifiers so the compiler can easily access them during compilation
Define collision
When a hashing algorithm produces the same index for two or more different keys
Define clustering
When a hashing algorithm produces indices that are not randomly distributed
Define load factor
The ratio of how many indices are available to how many there are in total
Define index
The location where values will be stored, calculated from the key
Define chaining
A technique for generating a unique index when there is a collision by adding the key / value to a list stored at the same index
What are the criteria for a suitable hashing algorithm?
- Numeric value generated to act as the index
- Generates unique indices
- Generates a uniform spread of indices to reduce clustering
- Enough possible indices to store the volume of data
- Balance issues of speed with complexity
What are the methods for handling collisions?
- Chaining: A list is created at that index which contains all key / value pairs which are to be stored at that index
- Rehashing: The algorithm is run again or a new algorithm is run until a new, unique index is created
Define rehashing
The process of running the hashing algorithm again when a collision occurs
Define magnitude of a vector
One of the two components of its vector, refers to the size of the vector
Define scalar
A real value used to multiply a vector to scale the vector
Define the dot product
The process of combining 2 vectors to calculate a single number, for vectors (a,b) and (c,d), the dot product is given by ac + bd
Define convex combination
A method of multiplying vectors that produces a resulting vector within the convex hull. For 2 vectors a and b, this is given by c (convex combination) = pa + qb, where p and q are both greater than 0, and p + q = 1
Define vector space
A collection of elements that can be formed by adding or multiplying vectors together
Define convex hull
A spatial representation of the vector space between two vectors