SLR4 Data structures Flashcards
Text file
“A computer file that is structured as a sequence of lines of electronic text (usually using the ASCII or UNICODE character set). Quite often the end of a text file is denoted by a special End of File (EoF) marker.”
Binary (non-text file)
“A computer file stored in a binary format. It is computer-readable but not human-readable. All executable programs are stored as binary files.”
Queue
“A dynamic data structure of the form First In First Out (FIFO).”
Stack
“A dynamic data structure of the form Last In First Out (LIFO).”
Graph
“A dynamic data structure used to often represent more complex relationships. Typically used to store routing, mapping or network style relationships and their data.”
Tree
“A non-linear dynamic data structure where data items can be thought of as occurring at different levels. There are links between items at one level and their descendants at the next. Each data item has data that relates in some way to its unique parent node. The data items are usually called nodes with the links known as branches. The top-level node is called the root node.”
Hash table
“A data structure where the calculated value is used to mark the position in the table where the data item should be stored, enabling it to be accessed directly, rather than forcing a sequential search.”
Dictionary
“A collection of key-value pairs in which the value is accessible via the associated key.”
Vector
“A list of numbers, a function, or a way of representing a geometric point in space.”
Static data structure
“A data structure which is a fixed size when in memory; this means the maximum size needs to be known in advance, as memory cannot be allocated at a later point.”
Dynamic data structure
“A data structure which, when in memory, has the flexibility to grown and shrink; this allows a programmer to control exactly how much memory is utilised at run time.”
Linear queue
“A straightforward implementation of a queue data structure. It holds a sequence of items.”
Circular queue
“An implementation of a queue in which the last node is connected back to the first node to make it circular in nature.”
Priority queue
“An abstract data type which is similar in many ways to a regular queue. However, in addition, each element in the queue has a priority associated with it.”
Push
“A process which adds an item to a data structure. Typically, you would ____(add) an item to a queue or stack.”
Pop
“A process which removes an item from a data structure. Typically, you would ___ (read/remove) an item from a queue or stack.”
Peek/top
“A process which allows you to inspect a data structure like a stack or queue and returns the item at the front or ‘top’ of the data structure without removing it.”
Weighted graph
“An edge-labelled graph where the labels where the labels can be operated on by the usual arithmetic operators, including comparisons like less than and greater than.”
Vertex/node
“A point on a graph which holds a data value.”
Edge/arc
“A connection between two vertices/nodes on a graph.”
Undirected graph
“A graph where the order of the vertices in the pairs in the edge set doesn’t matter.”
Directed graph
“A graph where the order of the vertices in the pairs in the edge set matters.”
Adjacency matrix
“A square matrix used to represent a finite graph. The elements of the matrix show you whether pairs of vertices (nodes) are adjacent or not in the graph.”
Adjacency list
“A collection of unordered lists used to represent a finite graph. Each list describes the set of neighbours of a vertex (node) in the graph.”
Rooted tree
“A tree data structure in which a special (labelled) node is singled out. The node is called the root.”
Binary tree
“A data structure similar to a tree with additional restrictions. Each node can have only 0, 1 or 2 leaf nodes. All left nodes and all of its descendants have smaller values that the root node, while all right nodes and all of its descendants have larger values than the root node.”
Tree node
“A point on a tree/binary tree which holds a data value.”
Child node
“Any node on a tree/binary tree which has a parent node.”
Collision
“When two different inputs to a hash function produce the same output as a hash value.”
Rehashing
“Increasing the size of a hash table’s arrays and restoring all of the items into the array using the hash; this typically happens when a hash table starts to become full or when an insertion fails.”
Vector addition
“The operation of adding two or more vectors together into a vector sum.”
Scalar-vector multiplication
“The process of multiplying a vector by a scalar. To perform scalar multiplication, you need to multiply the scalar by each component of the vector. A scalar is just a fancy word for a real number.”
Dot/scalar product
“An algebraic operation that takes two equal-length sequences of numbers (usually coordinate vectors) and returns a single number.”
“A computer file that is structured as a sequence of lines of electronic text (usually using the ASCII or UNICODE character set). Quite often the end of a text file is denoted by a special End of File (EoF) marker.”
Text file
“A computer file stored in a binary format. It is computer-readable but not human-readable. All executable programs are stored as binary files.”
Binary (non-text file)
“A dynamic data structure of the form First In First Out (FIFO).”
Queue
“A dynamic data structure of the form Last In First Out (LIFO).”
Stack
“A dynamic data structure used to often represent more complex relationships. Typically used to store routing, mapping or network style relationships and their data.”
Graph
“A non-linear dynamic data structure where data items can be thought of as occurring at different levels. There are links between items at one level and their descendants at the next. Each data item has data that relates in some way to its unique parent node. The data items are usually called nodes with the links known as branches. The top-level node is called the root node.”
Tree
“A data structure where the calculated value is used to mark the position in the table where the data item should be stored, enabling it to be accessed directly, rather than forcing a sequential search.”
Hash table
“A collection of key-value pairs in which the value is accessible via the associated key.”
Dictionary
“A list of numbers, a function, or a way of representing a geometric point in space.”
Vector
“A data structure which is a fixed size when in memory; this means the maximum size needs to be known in advance, as memory cannot be allocated at a later point.”
Static data structure
“A data structure which, when in memory, has the flexibility to grown and shrink; this allows a programmer to control exactly how much memory is utilised at run time.”
Dynamic data structure
“A straightforward implementation of a queue data structure. It holds a sequence of items.”
Linear queue
“An implementation of a queue in which the last node is connected back to the first node to make it circular in nature.”
Circular queue
“An abstract data type which is similar in many ways to a regular queue. However, in addition, each element in the queue has a priority associated with it.”
Priority queue
“A process which adds an item to a data structure. Typically, you would ____(add) an item to a queue or stack.”
Push
“A process which removes an item from a data structure. Typically, you would ___ (read/remove) an item from a queue or stack.”
Pop
“A process which allows you to inspect a data structure like a stack or queue and returns the item at the front or ‘top’ of the data structure without removing it.”
Peek/top
“An edge-labelled graph where the labels where the labels can be operated on by the usual arithmetic operators, including comparisons like less than and greater than.”
Weighted graph
“A point on a graph which holds a data value.”
Vertex/node
“A connection between two vertices/nodes on a graph.”
Edge/arc
“A graph where the order of the vertices in the pairs in the edge set doesn’t matter.”
Undirected graph
“A graph where the order of the vertices in the pairs in the edge set matters.”
Directed graph
“A square matrix used to represent a finite graph. The elements of the matrix show you whether pairs of vertices (nodes) are adjacent or not in the graph.”
Adjacency matrix
“A collection of unordered lists used to represent a finite graph. Each list describes the set of neighbours of a vertex (node) in the graph.”
Adjacency list
“A tree data structure in which a special (labelled) node is singled out. The node is called the root.”
Rooted tree
“A data structure similar to a tree with additional restrictions. Each node can have only 0, 1 or 2 leaf nodes. All left nodes and all of its descendants have smaller values that the root node, while all right nodes and all of its descendants have larger values than the root node.”
Binary tree
“A point on a tree/binary tree which holds a data value.”
Tree node
“Any node on a tree/binary tree which has a parent node.”
Child node
“When two different inputs to a hash function produce the same output as a hash value.”
Collision
“Increasing the size of a hash table’s arrays and restoring all of the items into the array using the hash; this typically happens when a hash table starts to become full or when an insertion fails.”
Rehashing
“The operation of adding two or more vectors together into a vector sum.”
Vector addition
“The process of multiplying a vector by a scalar. To perform scalar multiplication, you need to multiply the scalar by each component of the vector. A scalar is just a fancy word for a real number.”
Scalar-vector multiplication
“An algebraic operation that takes two equal-length sequences of numbers (usually coordinate vectors) and returns a single number.”
Dot/scalar product
