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 and 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 maximum size, whereas the size of dynamic data structures can change. 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.
The items that come after the new process must be moved down in the array and moving items is time consuming.
Explain how a value is stored in a hash table.
The hashing algorithm is applied to the key where 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 and 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.
