An efficient way to handle deletions in a hash table is to use a _______ value to mark deleted entries, allowing for proper rehashing.
- Null
- Sentinel
- Special marker
- Unique key
An efficient way to handle deletions in a hash table is to use a special marker value to mark deleted entries. This allows for proper rehashing and ensures that the deleted entries are correctly accounted for during subsequent operations.
Which of the following best describes the selection sort algorithm?
- Algorithm based on priority queues
- In-place algorithm with no comparisons
- Recursive algorithm using subproblems
- Sorting algorithm that divides the list into two parts: sorted and unsorted
The selection sort algorithm is a simple sorting algorithm that divides the input list into two parts: a sorted and an unsorted portion. It repeatedly selects the smallest (or largest) element from the unsorted part and swaps it with the first element of the unsorted part.
In A* search, what role do heuristic functions play in guiding the search process?
- Heuristic functions are applied only to the start node
- Heuristic functions determine the optimal path
- Heuristic functions have no impact on the search process
- Heuristic functions provide an estimate of the remaining cost
Heuristic functions in A* search provide an estimate of the remaining cost from a given node to the goal. This estimate guides the algorithm to prioritize paths that seem more promising in reaching the goal efficiently.
Explain how matrix exponentiation can be utilized to compute Fibonacci numbers in logarithmic time complexity.
- By representing the problem in terms of matrix exponentiation, Fibonacci numbers can be computed in logarithmic time complexity.
- Matrix exponentiation can be used to compute Fibonacci numbers in linear time complexity.
- Matrix exponentiation has no relevance to computing Fibonacci numbers.
- Matrix exponentiation is only applicable to square matrices.
Matrix exponentiation offers an efficient way to compute Fibonacci numbers in logarithmic time complexity. By expressing the problem as a matrix multiplication and leveraging exponentiation properties, the computation becomes more efficient compared to traditional recursive approaches.
Discuss the advantages and disadvantages of using arrays in programming.
- Dynamic size, easy to insert and delete elements, cache-friendly.
- Efficient for random access, fixed size, memory-friendly.
- Flexible size, efficient for small datasets, cache-unfriendly.
- Limited size, inefficient for dynamic resizing, contiguous memory.
Arrays in programming offer advantages such as efficient random access, fixed size, and memory-friendly characteristics. However, they have disadvantages like a fixed size, inefficient dynamic resizing, and the requirement for contiguous memory.
Explain the rotation operations used in AVL trees and their significance in maintaining balance.
- Primary and secondary rotations; Primary rotations adjust immediate subtrees, while secondary rotations modify distant subtrees.
- Simple and complex rotations; Simple rotations involve basic adjustments, while complex rotations involve intricate reconfigurations.
- Single and double rotations; Single rotations involve left or right rotations, while double rotations involve combinations of single rotations.
- Triple and quadruple rotations; Triple rotations involve three consecutive rotations, while quadruple rotations involve four rotations simultaneously.
Rotation operations used in AVL trees are single and double rotations. Single rotations include left rotations and right rotations, which help maintain balance by adjusting the heights of subtrees. Double rotations are combinations of single rotations performed to restore balance in specific cases, such as the double rotation involving left-right or right-left rotations.
Selection sort's time complexity can be improved to _______ by implementing certain optimizations.
- O(log n)
- O(n log n)
- O(n)
- O(n^2)
Selection sort's time complexity can be improved to O(n log n) by implementing certain optimizations, such as using more advanced data structures or algorithms to perform the selection in a more efficient manner.
Merge sort is a _______ sorting algorithm that follows the _______ strategy.
- Bubble
- Divide and Conquer
- Dynamic Programming
- Greedy
Merge sort is a Divide and Conquer sorting algorithm that follows the Divide and Conquer strategy. It recursively divides the array into two halves, sorts them, and then merges them back together.
Explain why binary search is more efficient than linear search for large datasets.
- Binary search always finds the element in the first comparison
- Binary search can only be used with small datasets
- Binary search divides the search space in half at each step, reducing the time complexity to O(log n)
- Linear search has a time complexity of O(n^2)
Binary search is more efficient for large datasets because it divides the search space in half at each step, resulting in a time complexity of O(log n), which is significantly faster than linear search (O(n)).
BFS guarantees finding the shortest path in an unweighted graph because it explores nodes in _______ order.
- Increasing
- Lexicographical
- Non-decreasing
- Non-increasing
BFS guarantees finding the shortest path in an unweighted graph because it explores nodes in increasing order. As it systematically traverses nodes level by level, the first time a node is encountered, it is reached through the shortest path.