2 - Fundamentals of Data Structures Flashcards
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 also 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 item must be moved down in the array and moving items is time consuming.
Why is a circular queue often a better choice of data structure than a shuffling 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 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.
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
