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.”
