Fundamentals of Data Structures Flashcards
What is a data structure?
Any method used to stored data in an organised and accessible format.
What is an abstract data type?
A conceptual model of how data can be stored and the operations that can be carried out on it.
What is a list/array?
A set of related data items stored under one identifier.
What are static data structures?
When the size and amount of memory put aside for it doesn’t change.
What are dynamic data structures?
When the size and amount of memory used to store it can vary as the program runs.
What are the advantages of static data structures?
Fast access, as memory locations are fixed
Easy to implement and use
What are the advantages of dynamic data structures?
Can optimize storage as size can change
Adaptable.
What are the disadvantages of static data structures?
Will take up memory even if it doesn’t need to. (Inefficient)
Limited adaptability.
What are the disadvantages of dynamic data structures?
More complex to implement
Slower access, as memory locations aren’t fixed.
How do dynamic data structures work?
It uses a heap, which is a pool of unused memory. It can take more memory off the heap if needed and put blocks of unused memory back onto the heap.
What is a stack?
A Last In First Out structure, meaning the last item to be added is the first to be removed.
What is pushing in terms of a stack?
Adding a new item of data to the stack.
What is popping in terms of a stack?
Taking an item off the top of the stack.
What is peeking in terms of a stack?
Used to identify the item at the top of the stack.
What is a stack overflow error?
If an item is added and the stack has run out of memory.
What is a stack underflow error?
If the stack is empty and you try to pop an item.
What is a stack frame?
Uses stacks to stored information about a running program. (Removes its from the stack when it completes).
What does a stack frame contain?
Function arguments (parameters/data)
Return address
Saved frame pointer
What is a call stack?
A stack that keeps track of all active stack fames in a program.
When are stack frames used?
If an interrupt occurs the program details are stored in a stack frame until the interrupt has been dealt with and then the program can carry on from where it left off.
What is recursion?
The process of a subroutine calling itself.
What is a queue?
A first-in-first-out structure.
What are uses of queues?
Sending data to the CPU
Print queues.
What does enqueue do?
Adds an item to the rear of a queue.
What does dequeue do?
Removes and returns the item from the front of the queue.
What is a linear queue?
A queue organised as a line of data sequentially, where if the rear pointer is at the last position the queue is full.
What are the disadvantages of linear queues?
Can only add or remove a certain number of items.
Once elements are dequeued the empty slots are wasted ( inefficient).
Underflow and overflow errors.
What are the advantages of linear queues?
Easy to implement
Predictable behaviour
What is a circular queue?
A queue implemented as a circle, where the front and rear pointers can wrap around from the end to the start.
What are the disadvantages of circular queues?
Complex implementation
Additional isEmpty and isFull logic
Harder to debug
What are the advantages of circular queues?
Efficient memory utilization, as empty spaces are reused.
Efficiently allocates memory
Consistent performance
How does the isFull function of a circular queue work?
IF (rear+1) MOD maxSize == front THEN
Queue is full.
How are new indexes calculated for circular queues?
newIndex = (oldIndex + 1 ) MOD maxSize
What is a priority queue?
When each item in a queue has a priority associated with it, meaning higher priority items “jump” the queue.
What happens in a priority queue when two items have then same priority?
They are handled according to their position in the queue.
What is a graph?
A mathematical structure that models the relationships between pairs of objects.
What components make up graphs?
Objects called nodes/vertices
Connections called edges/arcs.
What is a weighted graph?
A graph with a data value labelled on each edge.
What is a undirected graph?
When the relationships between vertices are two-way.
What is a directed graph?
When the relationships between vertices are one-way.
What are the uses of graphs?
Model complex real-life problems, such as transport networks and the Internet.
What is an adjacency list?
A data structure that stores a list of nodes with their adjacent nodes to represent graphs.
What is an adjacency matrix?
A two-dimensional array, showing when an edge is between a pair of nodes.
What are the advantages of adjacency lists?
Only stores data when there is an edge so less memory.
Good for sparsely connected graphs. (not many edges)
What are the disadvantages of adjacency lists?
Has to identify all adjacencies so increased processing time.
What are the advantages of adjacency matrixes?
Adjacencies identified quickly as every combination is stored.
Good for dense graphs (many edges)
What are the disadvantages of adjacency matrixes?
More memory, as a value for every combination is stored.
What is a tree
A rooted, undirected graph with no cycles (unique path from each node to any other node).
What is a root?
A starting node, from which other nodes branch off.
What is a parent in trees?
A node with further nodes below it.
What is a child in trees?
A node with nodes above it in the heirarchy.
What is a leaf in trees?
A node without any nodes beneath it.
What are the uses of trees?
Inherent hierarchical structure
Search and sort algorithms.
What is a binary tree?
A rooted, directed tree with no more than two branches off each node.
What are the uses of binary trees?
Stored data input in a random order in a sorted order.
How do binary trees store data?
The first item of data it the root, if the value of the next data item is less than the node branch less, otherwise branch right.
What is a hash table?
A data structure that stores key/value pairs based on an index calculated by an algorithm.
What is a hashing algorithm?
An algorithm used on the keys to calculate the index where they should be stored, allowing for data to be retrieved in one step. (efficient).
What are the uses of hash tables?
Databases
Generates memory addresses for cache memory.
What are the 3 hashing algorithms?
index = key MOD NumberOfSlots.
index = key^2 -> middle two digits MOD NumberOfSlots.
index = add the digits of the key MOD NumberOfSlots.
How is the hashing algorithm performed on non-numerical keys?
The ASCII or Unicode values of the keys is used to generate a numerical index.
What is a collision in hash tables?
When a hashing algorithm produces the same index for two or more different keys.
What is clustering in hash tables?
When indices are not randomly distributed.
What is a load factor in hash tables?
The ratio of NumberOfKeys / NumberOfSlots, the higher the value the harder it is to produce a unique result.
What is chaining in hash tables?
If a collision occurs a list is created at that slot and the key/value pairs become elements of that list.
What is the simplest way of dealing with collisions in hash tables?
Put the key/value pair in the next available slot, however this could lead to clustering. To prevent this increment the “ship” value.
What is rehashing?
If a collision occurs a different hashing algorithm is run on the key until a unique address is created.
What is a dictionary?
An abstract data type that maps key to data.
2-dimensional structure containing key/value pairs.
How are dictionaries implemented?
Requires random access, meaning you can directly access the key without iteration. (can be implemented with a hash table)
How can vectors be implemented?
As values stored in a list or elements in a one-dimensional array.
What is a function?
A mathematical construct that maps an input to an output.
What components make up vectors?
Tail
Head
Magnitude
Direction
What is a scaler in context of vectors?
The number representing the amount to scale a vector by.
Scaling changes the magnitude, not direction.
What is the dot product of vectors?
Combining two vectors to find the angle between them.
What is the formula for dot product?
A.B = AxBx + AyBy
cos = A.B/ |A|.|B|
What is a convex combination?
Multiplying vectors to produce a resulting vector within the convex hull.
What is the convex hull?
A spatial representation of the vector space between two vectors.
What is the formula for a convex combination?
D = αAB + βAC
α, β > 0
α+β=1
