more paper 1 stuff Flashcards
How does a hash function contribute to the performance of a hash table
A hash function maps keys to indices in the hash table, ensuring even distribution of elements and efficient retrieval
Explain how a priority queue can be implemented using an array
A priority queue can be implemented using arrays where elements are sorted based on their priority levels, allowing efficient insertion and removal
Discuss the impact of hash collisions on the performance of a hash table
Hash collisions can degrade performance by increasing lookup time and necessitating collision resolution techniques like chaining or open addressing
Explain how dynamic arrays handle resizing when they run out of space.
Dynamic arrays resize by allocating a larger block of memory, copying existing elements, and deallocating the old memory block, ensuring efficient resizing.
Discuss the advantages and disadvantages of using a dictionary for key-value storage
ADV:
- Fast Lookup Time: Dictionaries offer constant-time (O(1)) average-case lookup time for retrieving values based on their keys.
- Flexible Key Types: Dictionaries allow keys to be of various types, including strings, integers, tuples
- Dynamic Resizing: Many dictionary implementations automatically resize themselves as more elements are added,
DISADV:
- Memory Overhead: Dictionaries can consume more memory compared to other data structures
- Hash collisions
-
What is representational abstraction?
Removing (unnecessary) details;
What is abstraction by generalisation?
Grouping by common characteristics /
Explain what is meant by procedural decomposition
Breaking a problem into smaller sub-problems;
- Each of which solves an identifiable task;
Each of which might be further subdivided;
explain how a single stack can be used to reverse the order of the items in a queue
repeatedly remove the front item from the queue and push it into the stack
repeatedly pop items from the stack and add them to the rear of the queue
state two characteristics that make a tree a binary tree
- has a root node
- each node has a maximum of 2 children
advantages of using subroutines
Easier to test/debug as each subroutine can be tested separately;
Easier to understand the code if sensible identifiers are used for subroutine names;
Code can be easily reused as each subroutine is independent of rest of program;
Makes it easier to work as a team of programmers as each subroutine can be worked on independently;
Can be used as often as needed without having to write the code each time;
Makes program easier to maintain/update (in future) as fewer changes will need to
be made to make an update;
Allows the use of recursive techniques because subroutines can call themselves;
Easier to understand the code as each subroutine can be considered in isolation;
Less likely to be errors in the code due to reuse of code;
Reduces/eliminates side effects (eg unexpected change to value in global variable)
through use of local variables;
what is the cardinality of a set
- refers to the number of elements in a set. - Cardinality is usually expressed using double vertical bars:|A| is the number of elements of A
Explain why, when implemented using a fixed-length array, a circular queue is usually considered to be a better choice of data structure than a linear queue.
When an item is removed from a linear queue, all other items need to be shuffled up one, and this can result in unusable space in the array
Describe the steps that must be completed to remove (dequeue) an item from a circular queue that has been implemented using a fixed-length array
- Check that the queue is not already empty
R. reference to array instead of queue - if it is then deal with (underflow) error // (If it is not then) process/dequeue the
front item in the queue;3. Reduce the value of the variable used to store the current size by 1; - Check if the front is in the last position of the array and if it is set it to the first
position in the array - (Else) add 1 to the value of the front pointer;
what is the dot product rule
A⋅B=AxBx+AyBy
advantages of dynamic structures
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);
advantages of static structures
predictable memory allocation, faster access times, and simpler implementation
properties of a graph that make it a tree
unweighted and undirected
