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
