2 - Fundamentals of Data Structures Flashcards
What is the difference between an abstract data type and a data stucture?
An abstract data type is a theoretical description of a way of organising data, with particular features and access restrictions.
A data structure is a concrete realisation of an abstract data type in code.
Explain the circumstances in which it is more appropriate to represent a graph using an adjacency list instead of an adjacency matrix.
Adjacency list appropriate when
* the graph is sparse
* when edges are rarely changed
* when the presence of specific edges does not need to be tested frequently.
Explain what an abstraction is.
Omitting unnecessary details from a representation, storing only those details which are necessary in the context of the problem being solved.
Explain the differences between static and dynamic data structures.
- Static data structures have fixed size at runtime, whereas the size of dynamic data structures can change at runtime.
- Static data structures typically store data in consecutive memory locations whereas dynamic structures typically do not.
Explain why a static implementation of a priority queue is less efficient than a dynamic implementation.
For a static implementation, when an item is inserted all items that come after must be moved down/shuffled back in the array.
With a dynamic implementation pointers can be changed so that the item in front points to the inserted item and the inserted item points to the next item (or is null)
Explain how a value is stored in a hash table.
The hashing algorithm is applied to the key.
The result is an index of where to store the value in an array.
It is possible that the hashing algorithm might generate the same key for two different values
A collision handling method is used, for example by storing the value at the next empty index in the array.
Describe the steps involved in rehashing.
A larger hash table is created.
Each value in the existing table is inserted into the new table in a position determined by a new hashing algorithm.
Why is hashing used?
So that searching, adding and deleting can be done efficiently.
In the context of storing data in a file, explain what a hash function is.
A hash function is a function that computes a record position within a specified range from a key field value.
Explain what a collision is and how one might be dealt with.
A collision is when two keys compute the same hash value. They can be dealt with by storing the record in the next available location in the file.
Why is a circular queue often a better choice of data structure than a linear queue?
Items in a linear queue are all shuffled forward when an item is deleted from the front of the queue, whereas items don’t need to shuffle forward in a circular queue. This makes circular queues more time efficient when removing an item.
What are the advantages and disadvantages of dynamic data structures over static data structures?
Advantages:
• No wasted memory
• Can grow as more data is added to the data structure
• Resources only allocated as they are needed
Disadvantages:
• Additional memory needed for pointers
• Can result in memory leak
• Can take longer to access an item directly
Describe the steps involved in adding an item to a linear queue that has been implemented as a static data structure using an array.
Check that the queue is not already full, if it isn’t, then add 1 to the value of the rear pointer then add the new item to the position in the array indicated by the rear pointer.
Describe the steps involved when adding an item to a priority queue, implemented as a static data structure using an array, that are not required when adding an item to a linear queue.
Starting with the item at the rear of the queue, move each item back one place in the array until find an item with the same or higher priority than the new item. Then add the new item in the position before that item.
What is a graph?
A graph is a collection of vertices and a collection of edges connecting these vertices.
What is a weighted graph?
A graph with a weight associated with each edge.
What is a vertex/node?
An object in a graph.
What is an edge/arc?
A line representing a connection between two vertices in a graph.
What is a directed graph?
A graph where the edges have a direction.
What is an undirected graph?
A graph where no edges have a direction.
What is a tree?
A connected, undirected graph with no cycles.
What are the main operations that can be performed on a stack and what do they do?
- Push - adds an element to the top of the stack
- Pop - removes an element from the top of the stack and returns it
- Peek - returns a copy of the element from the top of the stack
- Is Empty - Checks whether the stack is empty
- Is Full - Checks whether a stack is at maximum capacity
What are the main operations that can be performed on a queue and what do they do?
- Enqueue - adds an element to the back of the queue
- Dequeue - removes the element at the front of the queue and returns it
- Is Empty - checks whether the queue is empty
- Is full - checks whether the queue is at maximum capacity
What is a hash table
an abstract data structure that implements an associative array (dictionary)
What is a hash function
A hash function is an algorithm that converts a hash key to a hash value
What is a hash key
The plain text inputted into the hashing function
Define Hash value
The result of a hashing algorithm
What is a collision
This occurs when the hash function produces the same hash value for 2 or more keys
What is open addressing?
a collision resolution technique where collisions are resolved by probing sequentially or using an interval in order find a free position for the hash value
What is closed addressing?
a collision resolution technique where collisions are resolved by using linked lists. In this way a pointer is stored in the position instead of a hash value which links to a list containing: the key value/ data and the pointer to the next node.
What are the requirements for a hash function
Must be repeatable/ provide a uniform distribution of hash values/ minimize clustering/collisions and must be fast to compute.
Give three different applications of hashing
Protection of data such as passwords/ comparing images/ databases
How would a computer retrieve data from a hash table that uses open addressing where a collision has occurred.
The hash table indexes to the position. It will then iterate until an empty position is found the hash value in question is found.
How would a computer retrieve data from a hash table that uses closed addressing where a collision has occurred.
The hash table indexes to the position. It will then follow the pointer to the linked list and then iterate until the hash value of interest is found or the list ends.
What problem might occur with open addressing
Deleted items can be seen as empty positions and hence the collided hash value may never be reached. There needs to be a a distinction between the empty and deleted positions.
What is a graph
An abstract data type that can be used to represent complex/ non linear relationships between objects
What is a meant by a sparse graph
A graph where there are very few connections between nodes
What is a meant by a dense graph
A graph where there are many connections between nodes
What is an adjacency matrix
A 2D array of vertices containing the connections between all nodes in a graph
Advantages of adjacency matrix
Ease of access (indexing) allows for swift and efficient testing of nodes.
Disadvantages of adjacency matrices
Static amount of memory/Can waste space if graph is sparse
Best application of adjacency matrices
Dense graphs
Adjacency List
A list that stores all relationships between nodes in the heap.
Advantages of adjacency list
Easy to add nodes/Memory cannot be wasted as it is only assigned when needed./Dynamically assigned memory
Disadvantages of adjacency list
Cannot be indexed so has to be iterated through which task more processing time
Best application of adjacency list
Sparse graph
Root Node
Starting node in a tree
Branch
A path from a root to an end point
Child
A node that comes directly after a node when tracing a path from a root node
Parent
A node that comes directly before a node when tracing a path from a root node
Subtree
A tree that is part of another tree.
Leaf Node
A node that has no children
Cycle
A closed path that starts and ends at the same node when it only visits a node once
Circuit
A closed path that starts and ends at the same node but it can visit a node multiple times
Loop
Edge that starts and finishes at the same vertex
Rooted Tree
A tree with one node that has been designated as the root
Binary Tree
A tree where every node has at most 2 children nodes
Uses of a trees
Pathfinding Family trees Syntax trees
What is a stack
A stack is an abstract data type that holds an ordered/ linear sequence of items. In contrast to a queue/ a stack is a last in/ first out (LIFO) structure. Stack only needs one pointer
What is a queue
A queue is an abstract data type that holds an ordered/ linear sequence of items. You can describe it as a first in/ first out (FIFO) structure; the first element to be added to the queue will be the first element to be removed from the queue. Needs two pointers
Uses of stacks
recursion / Reversing queues / RPN (reverse polish notation)
What the three different types of queue
Linear/ circular / priority
What is a linear queue
items are added to the end and removed from the back. Space is not reused
What is a circular queue
reuses empty space at the front cause by elements being removed. It does this by moving the end pointer to the start and iterating through.
What is a priority queue
one where each element in the queue has a priority. When new elements are added to the queue/ they are inserted ahead of those of lower priority and behind elements of equal priority.
Uses of queues
Interrupt buffers Printer queues CPU time management
