Fundamental of Data Structures - C2 Flashcards
(20 cards)
Define an array
An array is a fixed-size, indexed data structure that stores a collection of elements of the same data type, in contiguous memory locations.
Describe a static data structure, name a disadvantage, and list two examples
- They allocated a set amount of memory, which is fixed and cannot be changed, usually defined by the programmer.
- Accessing individual elements of data within the data structure are very quick because their memory location is fixed.
- They will still take up memory even if the data structure is empty and not holding any data.
- Records and arrays.
Describe a dynamic data structure, name a advantage, and list three examples
- The amount of memory they use varies based on their need.
- They take memory as and when needed from a heap.
- Much more efficient and flexible, elements can be add/removed quicker.
- Stacks, queues, binary trees.
Compare static and dynamic data structures
Static data structures:
-Memory is allocated at compile-time and may be wasted (inefficient).
-Fast access: memory addresses are fixed and contiguous.
-Fixed size: easier to predict and manage.
-The relationship between elements is fixed and doesn’t change.
Dynamic data structures:
- Memory is allocated at runtime, making it more efficient.
-Slower access: memory may be scattered (non-contiguous).
-Can grow/shrink: need extra mechanisms to track size.
-Relationships between elements can change during execution.
Describe a stack
A stack is a Last In, First Out (LIFO) data structure where the most recently added item is the first to be removed.
Data is added using pushing and removed using popping.
- Pushing = adding an item to the top of the stack
- Popping = removing the top item from the stack
- Peek = viewing the top item without removing it
- A stack pointer keeps track of the index of the current top item
- Stacks are used in recursion, undo features, and expression evaluation (RPN).
Describe stack overflow vs underflow
A stack overflow or underflow typically occurs in a static stack, where the size is fixed in advance.
-Overflow happens when pushing to a full stack.
- Underflow happens when popping from an empty stack.
In a dynamic stack (like one using a linked list), overflow usually doesn’t occur unless system memory is exhausted.
Describe a queue
A queue is a First In, First Out (FIFO) data structure where the first item added is the first to be removed.
Data is added at the rear and removed from the front.
- Enqueue = adding an item to the rear of the queue.
- Dequeue = removing an item from the front of the queue.
- A queue pointer keeps track of the front and rear positions.
- Queues can be linear, circular, or priority-based.
- Used in scheduling, buffering, and print queues.
What should you look out for when making an adjacency matrix for weighted graph?
Remember, instead of writing 0s you write the infinity sign for weighted graphs, and instead of 1s you write the weights (e.g. 30)
Adjacency list vs Adjacency Matrix
Adjacency List:
- Only stores data where there is an adjacency (edge), so requires less memory.
- The list has to be parsed to identify whether particular adjacencies exist, which increases the time taken to process the data.
- Where there are not that many edges (few adjacencies), this method would be more suitable for the reasons stated above. This is known as a sparse graph.
Adjacency Matrix:
- Stores a value for every combination of node adjacencies, so requires more memory.
- Adjacencies can be identified more quickly as every combination is already stored. Effectively, the matrix forms a look-up table of each node to every other node.
- Where there are many edges (lots of adjacencies), this method would be more suitable for the reasons stated above. This is known as a dense graph.
Describe a ‘tree’, and what are they useful for?
- Graph where every node must be connected, and all connections are undirected. There must be no cycles or loops.
- They are useful for storing data with an inherent hierarchical structure, e.g. family trees, file directories.
- They are dynamic, so it’s easy to add/delete nodes.
What is a binary tree and how is it implemented?
- A binary tree is a hierarchical data structure where each node has at most two children: a left and a right child.
- It is commonly used for searching, sorting, and hierarchical storage.
Describe a circular queue
- The rear and front wrap around to the beginning of the queue when they reach the end of the allocated space.
- A front and rear pointer keep track of positions and wrap around using modulo arithmetic
- Prevents unused slots after dequeues — perfect for systems with constant cycling data.
- Makes efficient use of fixed-size memory (no wasted space when queue wraps)
- Used in memory-limited systems, buffering, and real-time scheduling
What is a hash table and key?
- A hash table is a data structure that stores key–value pairs.
- It uses a hash function to convert a key into an index in an array, allowing fast access, insertion, and deletion.
- Key is the input value for the hash function.
What are collisions in hash tables, and how are they handled?
- When two keys hash into the same index, unavoidable when number of keys > array size.
- List list: items which can’t be place in main table, move to separate table (e.g. overflow table).
- Chaining: This is used to place more than 1 item at the same position, but different elements, so a list is created in that slot.
- Rehashing: This uses a technique called probing, where the algorithm searches for an empty slot. An example is linear probing, which looks for the next empty slot.
How do you choose a suitable hashing algorithm?
- Numeric data must be generated from the data to use as a key, e.g. letters turn into their ASCII numbers.
- It must generate unique indices to avoid collisions.
- Should have a good mechanism to cope with collisions.
- Should have a uniform spread of indices, and not be clustered. This reduces the likely good in the event of linear probing to avoid a collision that the sequential index is also occupied.
- Must be enough indices to store all keys.
- Must balance speed and complexity.
What is a dictionary, its main operations, and what is it used in?
- A dictionary is a data structure that stores key–value pairs, where each key maps to a specific value, implemented with a hash table.
- It allows fast lookup, insertion, and deletion using the key.
Insert(key, value)
Delete(key)
Search(key)
Update(key, value)
KeyExists(key)
- Symbol tables, databases.
What is the convex combination of two vectors?
- The region between any two vectors (straight line drawn between the tip of the arrows)
- Any vector represented by αP + ßQ lies between this region, given:
α+ ß <= 1
α and ß >= 0
Calculation and application of the dot/scalar product of two vectors, and calculation of angle between 2 vectors
- Multiply each matching component of both vectors, then add everything.
- a1* b1 + a2 * b2 + a3 * b3
- Can be used to find the angle between two vectors.
- cosθ = A * B / ( |A| * |B| )
|A| is length of vector A
How can vectors be represented?
- As a data structure, e.g. a 1D array.
- As a function, e.g f(x) = x²:
F = the function to create the vector
S = the set of values that the function can be applied to
R = the potential outputs of the function.
Therefore F: S → R - As arrows, geometrically.
When should you use an adjacency list over a matrix?
- When there are a small amount of edges.
- When the edges rarely change.
