1.2 Fundamentals of data structures Flashcards
(47 cards)
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