Programming - Data structures Flashcards
1
Q
what are static data structures
A
organisation or collection of data in memory that is fixed in size
eg arrays
2
Q
features of static data structures
A
- fixed memory allocation
- predictable memory usage
- elements are stored in consecutive memory locations
3
Q
what is an array
A
a list with a fixed size
4
Q
what is a dynamic data structure
A
a collection of data in memory that has the ability to grow or shrink in size
eg lists
5
Q
features of dynamic data structures
A
- variable memory allocation
- can adjust size based on the needs of the program
- unused memory is allocated or reallocated as needed
6
Q
advantages of dynamic structures
A
- makes efficient use of memory because the data structure only uses as much memory as it needs
- Can grow as more data is added to the data structure
- no limit on number of items
that can be added - Resources only allocated as they are needed
7
Q
disadvantages of dynamic structures
A
- runs the risk of overflow. can also have under flow if empty
- Additional memory needed for pointers;
- can lead to memory leak
- Can take longer to access an item directly
8
Q
advantages of static structures
A
- memory allocation is fixed so there will be no issues with adding and removing items from the data structure
- easier to program as there isn’t a requirement to check on the size of the data structure at any point before accessing it
- predictable memory usage, easy to estimate and manage memory requirements
- Faster access time - elements are stored in contiguous memory, allowing for quick access
9
Q
features of a stack
A
LIFO - last in first out structure,
10
Q
features of a queue structure
A
FIFO - first in first out
- you can add items onto the back of the queue and remove items from the front
11
Q
What does a queue need to be able to do?
A
- add items to the back - enqueue()
- remove items from the front - dequeue()
- test if the queue is empty or full isEmpty() or isFull()
12
Q
what does a stack need to be able to do
A
- add items to the stack, from the back
- remove items from the stack from the back
- look at the top item
- test if stack is empty or full
13
Q
Describe the steps involved in adding a record to a hash table.
A
-Hash algorithm applied;
to key value ;
- result is location in table where the record should be stored (key % number of slots)
- if location is not empty;
then use next free location by incrementing by one
14
Q
Describe the process that should be followed to add an item to a circular queue
implemented as a static data structure using an array.
A
1. Check the queue is not already full;
2. Compare the value of the (rear) pointer with the maximum size of the array;
3. If equal then (rear) pointer becomes zero;
4. Otherwise, add one to the (rear) pointer;
5. Insert new item in position indicated by (rear) pointer;
15
Q
what are abstract data types
A
a logical description of how the data is viewed and the operations that can be performed on it
16
Q
where are queues used
A
- output waiting to be printed/print spooling
- characters typed at a keyboard are held in a queue in a keyboard buffer
- simulation programs
17
Q
what is a stack?
how does a stack operate?
what are some of the common uses of a stack?
A
- a stack is a linear data structure which follows the Last in first out principle
- elements are added (pushed) and removed (pop) from the top
- used in text editing, call management
18
Q
uses of static data structures
A
- arrays, static stacks and queues
- used when max size of the data structure is known in advance
- when memory usage needs to be predictable and consistent
eg implementing simple buffers
19
Q
uses of dynamic data structures
A
- linked lists, dynamic stacks and queues, trees, graphs
- used in situations where the size of the data structure may change during runtime
- where flexibility and efficient memory usage are required
- eg, implementing dta structures like trees and graphs
20
Q
How do you add an item to a linear queue
A
check the queue is not full.
- if full, report an overflow error and stop
- else, increment the rear pointer
- insert new data item into the location pointed to by the rear pointer
21
Q
How do you remove an item from a linear queue?
A
- Check queue is not empty
- if its empty report an underflow error and stop
- copy data item in the front pointer
- increment front pointer
22
Q
How do you test for an empty linear queue
How do you test for a full linear queue
A
- Check if the front pointer is greater than the rear pointer or if the queue size is 0
- Condition: Check if the rear pointer is at the last index of the array (size - 1)
23
Q
disadvantages of static data structures
A
- cannot grow or shrink during runtime, which could lead to wasted memory or insufficient space
- not suitable for applications where data size can vary significantly
24
Q
How do you perform a push(insertion) operation on a stack
A
- Check that stack is not full
- if the stack is full, report error and stop
- increment the stack pointer
- insert new data item into location pointed to by the new pointer
25
How do you perform a pop operation on a stack?
- check if stack is not empty
- if it is report an error and stop
- copy data item in location pointed to by the stack pointer
- decrement the stack pointer
26
How do you perform a peek or top operation on a stack
Check Empty: Ensure the stack is not empty.
Retrieve: Access and return the item at the top of the stack without removing it.
27
How do you test if a stack is empty?
Check if the top pointer is at the initial position (usually -1 or 0 depending on implementation)
28
How do you test if a stack is full?
Check if the top pointer is at the last index of the stack (size - 1)
29
what is a hash table
A hash table is a data structure that creates a mapping between keys and values.
30
uses of a hash table
Fast Lookup: Efficiently retrieve data by key.
- Useful in implementing sets, maps, and dictionaries.
Database Indexing: Quick access to database records.
Caching: Store frequently accessed data for quick retrieval.
Symbol Tables: Used in compilers and interpreters for storing variables and function names
31
What is a collision in a hash table?
- Occurs when two different keys produce the same hash code, resulting in the same index in the hash table
32
How are collisions handled using rehashing
Linear Probing: If a collision occurs, check the next slot (index + 1) until an empty slot is found
- Quadratic Probing: If a collision occurs, check slots at intervals of i^2
- Double Hashing: Use a second hash function to determine the step size
- Separate Chaining: Store a list of all values that hash to the same index.
33
What is a graph as a data structure?
A graph is a collection of vertices (or nodes) and edges (or arcs) that connect pairs of vertices
34
What are some typical uses for graphs?
Social Networks: Represent relationships between people.
Computer Networks: Model the connections between devices.
Transportation Networks: Map out routes and connections.
Web Graphs: Illustrate hyperlinks between web pages.
Dependency Graphs: Show dependencies between tasks or modules
35
Define the following terms:
- Graph
- Weighted Graph
- Vertex/Node
- Edge/Arc
- Undirected Graph
- Directed Graph
Graph: A collection of vertices connected by edges.
Weighted Graph: A graph where edges have weights representing costs or distances.
Vertex/Node: part of a graph representing an object.
Edge/Arc: A connection between two vertices in a graph.
Undirected Graph: A graph where edges have no direction (bidirectional).
Directed Graph: A graph where edges have a direction (unidirectional)
36
why might a queue be implemented as a circular queue
It uses memory more efficiently because it can reuse the space that becomes available when elements are dequeued
37
How do you decide whether to use a linear queue, circular queue, or priority queue?
Linear Queue:
- Simple FIFO processing.
- Suitable when space is not a concern, and elements are processed strictly in order of arrival
Priority Queue:
- Suitable for systems where some tasks or data have higher importance than others
Circular Queue:
- Suitable for scenarios with a static data structure being used, so items leave the front of the queue and new items can take their place as the rear pointer “warps round” to the front
38
What is a circular queue?
A circular queue is a linear queue that connects the end of the queue back to the front, forming a circle
39
What is a priority queue?
- a type of queue where each element has a priority.
- Elements are removed based on priority rather than the order they were added
40
the rear pointer in a stack always points to
the last element in the stack
41
uses of stacks
storing info abt active subroutines while a computer is running
42
differences between static and dynamic structures
- static data structures have storage size determined before program is run, dynamic data structures can grow or shrink during runtime
- static data structures can waste storage space if number of data items stored is small, relative to the size of the structure. dynamic structures only take up the amount of storage space required for the actual data
- static data structures have fixed size, size of dynamic structures can change
- dynamic structures require more memory to store pointers , static data structures typically do not need
- static data structures store data in consecutive memory, dynamic structures typically do not
43
explain how a single stack can be used in the implementation of the repeat action and undo action
- stack/data structure is used to store the users action
- each time an action is completed, it’s pushed on top of the stack
- unless it is an undo or repeat action
- when repeat action is used, the top item from the stack is used to indicate the action to complete
- when undo action is used, the top item is popped from the stack of actions
44
Describe the steps involved when adding an item to a priority queue, implemented as a static data structure using an array, that were 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 you (reach the start of the queue or) find an item with the same or higher priority than item
- Add the new item in the position before that item;
45
when should you use static or dynamic data structure
dynamic
- when the maximum number of items is not known.
- The heap is a portion of memory which can be allocated or deallocated as required.
46
When a player gives up a card it is returned to the bottom of the deck.
(a) Explain why a queue is a suitable data structure to represent the deck of cards in this game.
Values/cards need to be removed in the same order that they are added
47
Which tree traversal algorithm is used to output the contents of a binary search tree in ascending order?
in order
48
Name two applications of depth-first search and breadth-first search
DFS: Navigating a maze, topological sorting
BFS: Finding the shortest path in an unweighted graph, web crawlers
