A hash table typically consists of an array of _______ and a hash function that maps _______ to indices in the array.
- Buckets, keys
- Elements, addresses
- Linked lists, keys
- Nodes, values
A hash table typically consists of an array of buckets and a hash function that maps keys to indices in the array. The array is divided into buckets, each capable of holding multiple key-value pairs. The hash function determines which bucket a key should go to.
Can DFS be used to find the shortest path in a graph?
- No
- Only in acyclic graphs
- Only in weighted graphs
- Yes
No, DFS does not guarantee finding the shortest path in a graph. It can find a path, but it may not be the shortest. BFS is more suitable for finding the shortest path as it explores nodes level by level.
Insertion Sort is particularly effective when the input array is nearly _______ sorted.
- Completely
- Partially
- Randomly
- Sequentially
Insertion Sort is particularly effective when the input array is nearly partially sorted. In such cases, the number of comparisons and swaps required is significantly reduced, making it efficient.
Suppose you are tasked with sorting a small array of integers, where most elements are already sorted in ascending order. Which sorting algorithm would be most suitable for this scenario and why?
- Insertion Sort
- Merge Sort
- Quick Sort
- Selection Sort
Insertion Sort would be the most suitable algorithm for this scenario. It has an average-case time complexity of O(n), making it efficient for small arrays, especially when elements are mostly sorted. Its linear time complexity in nearly sorted arrays outperforms other algorithms.
How does a red-black tree ensure that it remains balanced after insertions and deletions?
- By assigning different colors (red or black) to each node and enforcing specific rules during insertions and deletions.
- By limiting the height of the tree to a constant value.
- By randomly rearranging nodes in the tree.
- By sorting nodes based on their values.
A red-black tree ensures balance by assigning colors (red or black) to each node and enforcing rules during insertions and deletions. These rules include properties like no consecutive red nodes and equal black height on every path, ensuring logarithmic height and balanced structure.
The ratio of successive Fibonacci numbers approaches the _______ as n increases.
- Euler's number
- Golden ratio
- Pi
- Square root of 2
As n increases, the ratio of successive Fibonacci numbers approaches the golden ratio (approximately 1.618). This unique property is a key aspect of the Fibonacci sequence's significance in various fields, including art, architecture, and nature.
To optimize the space complexity of merge sort, one can implement it iteratively using _______.
- Heaps
- Linked lists
- Queues
- Stacks
To optimize the space complexity of merge sort, one can implement it iteratively using stacks. This avoids the need for additional memory used in recursive function calls, optimizing space usage.
In Dijkstra's algorithm, how does it select the next node to visit?
- It always selects the first node in the graph
- It chooses nodes randomly
- It picks the node with the largest tentative distance value
- It selects the node with the smallest tentative distance value
Dijkstra's algorithm selects the next node to visit based on the smallest tentative distance value. It maintains a priority queue or a min-heap to efficiently retrieve the node with the minimum distance.
What is the main advantage of using DFS over BFS in certain scenarios?
- Guaranteed shortest path
- Higher speed in most cases
- Lower memory consumption
- Simplicity of implementation
The main advantage of using DFS over BFS in certain scenarios is the simplicity of implementation. DFS is often easier to implement and requires less memory overhead compared to BFS.
Under what circumstances would you prefer to use Prim's algorithm over Kruskal's, and vice versa?
- Both algorithms are equivalent and can be used interchangeably.
- Kruskal's is preferred for dense graphs, while Prim's is suitable for sparse graphs.
- Prim's is always faster than Kruskal's regardless of the graph characteristics.
- Prim's is preferred for dense graphs, while Kruskal's is suitable for sparse graphs.
Prim's algorithm is generally preferred for dense graphs, where the number of edges is close to the maximum possible edges. On the other hand, Kruskal's algorithm tends to perform better on sparse graphs, where the number of edges is much less than the maximum possible. The choice depends on the specific characteristics of the graph.