Fundamentals Of Data Structures Flashcards
Paper 1
What are data structures?
Data structures are used by computers as the containers within which information is stored.
What is an Array
An array is an indexed set of related elements.
What are abstract data types/data structures
Abstract data structures don’t exist as data structures in their own right, instead they make use of other data structures such as arrays to form a new way of storing data.
What is a Queue
A queue is an abstract data structure based on an array(it is referred to as a First In First Out data structure(FIFO)).
What are Linear Queues
A linear queue is a queue with two pointers(FRONT and REAR pointer) these pointers can be used to identify where to place a new item or used to identity the item at the front of the queue.
Operations that can be performed on a queue
Enqueue => add an item to a queue
Dequeue => to remove from a queue
IsEmpty => checks whether a queue is empty or not
IsFull => checks if queue is full
What are circular queues
They are queues where both the front and rare pointers can move to both ends of the queue making the queue more memory efficient.
Describe the method that would need to be followed to attempt to remove an item from a circular queue implemented as a static data structure using an array.
- Check the queue is (not already) empty;
- Add one to the front pointer;
- Compare the value of the front pointer with the maximum size of the array;
- If equal then front pointer becomes zero.
Describe the method that would need to be followed to remove an item from a linear queue implemented as a static array.
Check if the queue is empty by comparing front and rear pointers.
If front == rear, the queue is empty → Report error
If not empty, increment the front pointer by 1.
Describe the method that would need to be followed to add an item to a linear queue implemented as a static array.
Check if the queue is not already full
If queue is full report error message
If it isn’t full, add 1 to the value of the rear pointer;
Then add the new item to the position indicated by the rear pointer.
What are Priority Queues?
In a priority queue, items are assigned a priority. Items with the highest priority are dequeued before low priority items.
What is a stack?
A stack is a first in, last out (FILO) abstract data structure.
Operations that can be performed on a stack
Push – Adds an item to the top of the stack.
Pop – Removes and returns the item from the top of the stack.
Peek / Top – Returns the item at the top without removing it.
IsEmpty – Checks if the stack has no items.
IsFull – Checks if the stack is full
What is a graph?
A graph is an abstract data structure used to represent complex relationships between items within datasets.
Graphs can be used to represent networks such as transport networks, IT networks and the Internet.
Describe a graph
A graph consists of nodes (sometimes called vertices) which are joined by edges (sometimes called arcs).
– A weighted graph is one in which edges are assigned a value, representing a value such as time, distance or cost.
– An unweighted graph is a graph where all edges are considered equal, with no numerical values or weights assigned to them.
What are Adjacency matrices and Adjacency lists.
Adjacency List – A way of representing a graph where each vertex stores a list of its connected vertices.(Rather than using a table to represent a graph, a list could be used.)
An adjacency matrix 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.
an adjacency list only records existing connections in a graph, unlike an adjacency matrix which stores even those edges that don’t exist.
Difference between an adjacency list and adjacency matrix.
- Adjacency Matrix => Stores every possible edge between nodes, even those that don’t exist. Almost half of the matrix is repeated data. (Memory Inefficient).
Where as
Adjacency List => Only stores the edges that exist in the graph.(Memory efficient) - Adjacency Matrix => Allows a specific edge to be queried very quickly, as it can be looked up by its row and column. (Time efficient)
Where as
Adjacency List => Slow to query, as each item in a list must be searched sequentially until the desired edge is found. (Time Inefficient)
Adjacency Matrix => Well suited to dense graphs, where there are a large number of edges.
Adjacency List => Well suited to sparse graphs, where there are few edges.
What is a tree
A tree is a connected, undirected graph with no cycles.
A rooted tree has a root node from which all other nodes stem. When displayed as a diagram, the root node is usually at the top of the tree.
What are parent nodes
Nodes from which other nodes stem are called parent nodes
What are child nodes
Nodes with a parent are called child nodes and child 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.
Rooted trees (which include Binary trees) can be used to represent family trees or file systems on a computer’s hard drive.
What are hash tables?
Hash tables are a way of storing data that allows data to be retrieved with a constant time complexity of O(1).
What does an hashing algorithm do?
A hashing algorithm takes an input and returns a hash.
What is collision?
This is when two pieces of data produce the same hash value.
