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
- Subroutines make programs shorter as well as easier to read and understand, because they break program code into smaller sections.
- You can test procedures or functions separately, rather than having to test the whole program. This makes programs easier to debug.
- If something needs to be changed in a subroutine, it only needs to be changed once, within the subroutine code
- Data that is passed to a subroutine can be customised, so a subroutine can perform the same action on different data.
- You can add subroutines to a library so that you can use them in other programs.
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.
- A circular queue is considered better because it efficiently utilizes memory. - in a circular queue, when the front reaches the end of the array, it wraps around to the beginning, allowing the space to be reused and preventing wasted memory.
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 if the queue is empty: If the front and rear pointers are the same,
- Retrieve the item: Access/remove the item at the front pointer of the queue
- increment the front pointer to point to the next item in the queue.
- compare pointer value to size of array, if front pointer = length of array, pointer = 0
- If the queue becomes empty (front equals rear), reset both pointers to indicate the queue is empty.
