Section 2: Fundamentals of data structures Flashcards
What is an array?
A set of related data items stored under a single identifier
What is a “static” data structure?
A method of storing data where the amount of data stored (and memory required to store it) is fixed
What is a “dynamic” data structure?
A method of storing data where the amount of data stored(and the memory required to store it) can vary while the program is being run
What is meant by a “LIFO” structure?
Last In First Out
What is meant by a “FIFO” structure?
First In First Out
What type of structure is a “stack”?
LIFO
What is a stack?
A structure where the last item of data added is the first to be dealt with when the data is looked at/ referenced
What is a stack frame?
When a stack is used to store information about a running program. A pointer is used to identify the start point of the frame
What is an interrupt?
A signal sent by a device or program to the processor requesting its attention
What is recursion?
When a subroutine calls on itself
What type of structure is a “queue”?
FIFO
What is a queue?
A structure where the first item of data added is the first item to be looked at when the data is looked at / referenced
When are queue structures used?
Peripherals, e.g. keyboard
What is meant by a “circular” queue?
A type of queue that can be represented in a circular format, where the front of the queue is joined to the back of the queue.
What is meant by a “linear” queue?
A standard queue, the data can be represented as a line. However the maximum size of the queue is fixed in this case
What is another word for a “circular queue”?
Circular buffer
What is a “priority” queue?
A priority queue is identical to a standard queue apart from how it adds a priority to each item. This allows higher priority items to “skip” the lower priority items in the queue.
What is a graph?
A mathematical structure that models the relationship between pairs of objects
What is an “arc”?
A join or relationship between 2 nodes, aka an “edge”
What are vertex/vertices?
Objects in a graph (aka nodes)
What is an edge?
A join or relation between 2 nodesW
What is a weighted graph?
A graph where the edges (joins between nodes) have values
What is a undirected graph?
A graph with edges that have no defined direction
What is a directed graph?
A graph with edges that point in defined directions
What is meant by “latency”?
The time delay that occurs when transmitting data between devices
What is an adjacency list?
A data structure that stores a list of nodes with their adjacent nodes
What is an 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 is a node?
An object in a graph - aka a vertex
What is a tree?
A data structure similar to a graph, with no loops
What is meant by a root?
The starting node in a rooted tree structure from which all other node branch off
What is meant by a parent?
A type of node in a tree where there a further nodes beneath it
What is a child?
A node in a tree that has nodes above it in the hierarchy
What is a leaf?
A node that doesn’t have any other nodes beneath it
What is a binary tree?
A tree where each node can have up to 2 child nodes attached to it
What is a hash table?
A data structure that stores key/value pairs based on an index calculated from an algorithm
What is meant by a hashing algorithm?
Code that creates a unique index from given key items of data
What is cache?
A high speed temporary area of memory
What is a collision in hashing?
When a hashing algorithm produces the same index for two or more different keys
What is clustering in hashing?
When a hashing algorithm produces indices that are not randomly distributed
What is meant by index?
The location where values will be stored, calculated from the key
What is meant by chaining in hashing?
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 is meant by Rehashing?
The process of running a hashing algorithm again when a collision occurs
What is an associative array?
A two dimensional data structure containing key/value pairs of data
What is meant by dot product?
Multiplying two vectors together to produce a number
What is meant by “convex combination”?
A method of multiplying vectors that produces a resulting vector within the convex hull
What is meant by vector space?
A collection of elements that can be formed by adding or multiplying vectors together
