02 Fundamentals of Data Structures Flashcards
Describe queues.
A queue is an abstract data structure with a first-in-first-out policy.
It maintains a front pointer for the first element in the queue and a rear pointer for the last item in the queue.
Items are enqueued to the position after the rear pointer and it increments and dequeued from the front pointer and front pointer increments.
Describe stacks and applications of them.
Stack is an abstract data structure which follows a last-in-first-out policy.
- Stacks are also used to facilitate recursive subroutines where the state of each call is stored in a stack frame and placed on a stack.
- can be used to maintain a list of operations for an ‘undo’ function in a piece of software, where the most recent operation is the first to be undone
Describe graphs.
A graph is an abstract data type that can be used to represent complex, non-linear relationships between objects.
- Consists of nodes and edges
- Neighbours are two nodes connected
- A loop is an edge that connects a node to itself
- Path is a sequence of nodes connected by edges
- A cycle is a path that starts and ends at the same node and doesn’t visit any node more than once
Uses: internet (nodes are routers and edge is hop), social networks, transport networks, WWW (nodes are webpages)
Describe trees.
A tree is a connected, undirected graph with no cycles.
- The root is the start node for traversals
- Branch is a path from the root to a leaf (endpoint)
- Height is the number of nodes from root to furthest away leaf (longest branch)
- Root has no parent and leaf nodes have no children
- Binary tree is a tree where each node has no more than 2 children
Describe hash tables.
- A hash table is a data structure that implements an associative array (a dictionary).
- In an associative array, data is stored as a collection of key-value pairs.
- The position of the data within the array is determined by applying a hashing algorithm to the key - a process called hashing.
- The hashing algorithm is called a hash function.
Describe dictionaries.
A dictionary is an abstract data type that defines an unordered collection of data as a set of key-value pairs.
Describe vectors.
A vector is an abstract data type used to represent properties that have both direction and magnitude.
- Dot product is the sum of the products of each item in both vectors
- cos x = (a DOTPRODUCT b)/ (|a|x|b|)
What is the difference between static and dynamic data structures?
STATIC
- Reserve memory for a set amount of data in memory
- Fixed in size and only one data type
- Inefficient for memory use
- Efficient for searching through structure
DYNAMIC
- Memory capacity allocated is not fixed
- Efficient memory use
Compare uses and benefits of static and dynamic data structures.
STATIC
- ADV 1: The memory allocation is fixed and so there will be no problem with adding and removing data items.
- ADV 2: Easier to program as there is no need to check on data structure size at any point.
- DIS: Can be very inefficient as the memory for the data structure has been set aside regardless of whether it is needed or not
DYNAMIC
- ADV 1: Makes the most efficient use of memory as the data structure only uses as much memory as it needs
- DIS 1: Because the memory allocation is dynamic, it is possible for the structure to ‘overflow’ should it exceed its allowed limit. It can also ‘underflow’ should it become empty.
- DIS 2: Harder to program as the software needs to keep track of its size and data item locations at all times
Outline linear queues
- A linear queue is where items are removed from the front of queue and items are added to the rear of the queue.
- As items are removed from the front of the queue the front of the queue will move further and further back.
- If we simply add to the rear of the queue and remove from the front in a linear fashion we would eventually reach the maximum limit of the queue and have no more space to add items.
- Also, there will be wasted empty space at the front of the queue.
Outline circular queues.
- When either pointer reaches queuemax it will next move to position 1.
- A circular queue reuses the empty slots at the front of the array that are caused when elements are removed from the queue.
Describe the steps involved when adding an
item to a priority queue, implemented as a
static data structure using an array,
- Starting with the item at the rear of the queue move each item back one place in the array until you (reach the start of the queue or) find an item with the same or higher priority than the item to add
- Add new item in the position before that item
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 indicated by the rear pointer;
Discuss the advantages and disadvantages of
dynamic data structures compared to static
data structures. [4 marks]
Advantages
- No wasted memory;
- Can grow as more data is added to the data structure // no limit on number of
items that can be added (except due to hardware limitations); - Resources only allocated as they are needed (with static data structures they are
allocated at creation even if not needed until later);
Disadvantages
- Additional memory needed for pointers;
- Can result in memory leak (if memory that is no longer needed is not returned to
the heap); - Can take longer to access an item directly
Principles of operation of queues and applications.
- enqueue(data)
- dequeue()
- is_empty()
- is_full()
- print tasks are stored on a print queue while waiting to be printed
- simulation for a proposed road scheme could model the behaviour of traffic queueing at junctions
