Fundamentals of Data Structures Flashcards
What is an array
An array is an indexed set of elements. An array must be finite, indexed and must only contain elements with the same data types.
What is a queue
A queue is an abstract data structure based on an array. Queues are FIFO abstract data structures (First in First out)
What is a Linear Queue
A linear queue has two pointers, a front pointer and a rear pointer. The queue is full if there are no available positions on or after the rear pointer.
What is a Circular Queue
A circular queue is a queue in which the front and rear pointers can move over the two ends of the queue, making for a more memory efficient data structure.
What is a Priority Queue
In a priority queue, items are assigned a priority. Items with the highest priority are dequeued before low priority items. If two items have the same priority, FIFO is used.
Name 3 operations that can be performed on a queue
Enqueue
Dequeue
IsEmpty
IsFull
What is a stack
A stack is a FILO (first in last out) abstract data structure. Stacks have just one pointer, a top pointer.
Name 3 operations that can be performed on a stack
Push
Pop
PeekIsFull
IsEmpty
What is a stack overflow error
When you attempt to add an item to a stack with no available spaces
What is a stack underflow error
When you attempt to pop an item from an empty stack
What is a graph
A graph is an abstract data structure used to represent complex relationships between items within datasets. A graph consists of nodes (vertices) which are joined by edges (arcs).
What is the difference between a graph and a weighted graph.
A weighted graph is one in which edges are assigned a value, representing a value such as time, distance, cost, etc.
What is an Adjacency Matrix
An adjacency matric is a tabular representation of a graph, each of the nodes in the graph is assigned both a row and a column in the table, a 1 is used to show an edge exists between 2 nodes and a 0 indicates that there is no connection. (if the graph is weighted, use the weight instead of 1, and infinity instead of 0)
What is an Adjacency List
Rather than using a table to represent a graph, a list can be used. For each node in the graph, a list of adjacent nodes is created, this means that only existing connections are stored, which is more memory efficient.
What is a tree
A tree is a connected, undirected graph with no cycles.
What is a rooted tree
a rooted tree has a root node from which all the other nodes stem. When displayed as a diagram, the root node is usually at the top of the tree. Nodes with children are called parent nodes, nodes with a parent are called child nodes, and nodes with no children are called leaf nodes.
What is a binary tree
A binary tree is a rooted tree in which each parent node has no more than two child nodes.
What is a Hash Table
hash tables are a way of storing data that allows data to be retrieved with a constant time complexity of O(1). A hashing algorithm takes an input and returns a unique irreversible hash. The has is used as an index in the hash table which stores key-value pairs.
How do you deal with collisions in a hash table
There are many techniques to deal with collisions, one is to keep on moving to the next position until an available one is found.
What is a dictionary
A dictionary is a collection of key-value pairs in which the value is accessed by its associated key.
What is Convex combination of two vectors.
If you have two vectors, a and b, then a convex combination of the two would be ax + by where x and y are both non-zero numbers less than 1 that add to 1
What is the dot product of two vectors
The dot product is a single number derived from the components of two vectors that can be used to determine the angle between them.
What is the difference between a static and dynamic data structure.
Static data structures have a fixed size (stores items as a series of sequential memory locations) whereas dynamic data structures can be any size, instead of being stored sequentially, each item is stored alongside a reference to where the next item is stored. The advantage to dynamic structures is the dynamic size, however a downside is that they require more work on the part of the computer to set up and use.
Define “Abstract data structure”
Data structures that dont exist as data structures in their own right, by make use of other data structures to form a new way of storing data.
Which are best suited to dense graphs, adjacency matrices or adjacency lists
adjacency matrices are better for dense graphs, adjacency lists are better for sparse graphs.
