Q21. The binary search algorithm is the optimal ____ case algorithm for solving
ID: 3847583 • Letter: Q
Question
Q21. The binary search algorithm is the optimal ____ case algorithm for solving search problems by the comparison method.
a. best
b. average
c. worst
d. second best
Q22. The sequential search algorithm is the optimal worst-case algorithm for solving search problems by the comparison method.
a. true
b. false
Q23. Both random and quadratic probing eliminate ____.
a. primary clustering
b. secondary clustering
c. rehashing
d. random probing
Q24. In chaining, the average number of comparisons for an unsuccessful search is equal to the load factor.
a. true
b. false
Q25. What is usually returned if the search item is found during a search of a list?
a. the location of the element
b. the element
c. -1
d. true
Q26. What is the maximum number of key comparisons made when searching a list L of length n for an item using binary search?
a. log n
b. 2 * log2n + 2
c. 2
d. n
Q27. In the binary search algorithm, two key comparisons are made through every iteration of the loop.
a. true
b. false
Q28. One way to solve secondary clustering is with double hashing.
a. true
b. false
Q29. Binary search can be performed on both sorted and unsorted lists.
a. true
b. false
Q30. Comparison-based search algorithms search the list by comparing the target element with the list elements.
a. true
b. false
Explanation / Answer
Q21. The binary search algorithm is the optimal ____ case algorithm for solving search problems by the comparison method.
a. best b. average c. worst d. second best
Binary search is a fast search algorithm with run-time complexity of (log n). This search algorithm works on the principle of divide and conquer. For this algorithm to work properly, the data collection should be in the sorted form. Binary search looks for a particular item by comparing the middle most item of the collection. If a match occurs, then the index of item is returned. If the middle item is greater than the item, then the item is searched in the sub-array to the left of the middle item. Otherwise, the item is searched for in the sub-array to the right of the middle item. This process continues on the sub-array as well until the size of the sub-array reduces to zero.
Q22. The sequential search algorithm is the optimal worst-case algorithm for solving search problems by the comparison method.
a. true b. false
The sequential search starting at the first item in the list, then simply move from item to item, following the underlying sequential ordering until either find what we are looking for or run out of items. If we run out of items, we have discovered that the item we were searching for was not present.
Q23. Both random and quadratic probing eliminate ____.
a. primary clustering b. secondary clustering c. rehashing d. random probing
Both pseudo-random probing and quadratic probing eliminate primary clustering, which is the name given to the situation when keys share substantial segments of a probe sequence. If two keys hash to the same home position, however, then they will always follow the same probe sequence for every collision resolution method that we have seen so far. The probe sequences generated by pseudo-random and quadratic probing are entirely a function of the home position, not the original key value. This is because function p ignores its input parameter KK for these collision resolution methods. If the hash function generates a cluster at a particular home position, then the cluster remains under pseudo-random and quadratic probing. This problem is called secondary clustering.
Q24. In chaining, the average number of comparisons for an unsuccessful search is equal to the load factor.
a. true b. false
The average number of table elements examined in a successful search is approximately 1 + /2 using chained hashing. The average number of searches during a successful search as a function of the load factor .
Q25. What is usually returned if the search item is found during a search of a list?
a. the location of the element b. the element c. -1 d. true
while ((i < a.length) && !found){
if (a[i].getKey() == target)
found = true;
else i++;
Q26. What is the maximum number of key comparisons made when searching a list L of length n for an item using binary search?
a. log n b. 2 * log2n + 2 c. 2 d. n
In the worst case, binary search requires O(log n) time on a sorted array with n elements. Note that in Big O notation, we do not usually specify the base of the logarithm. (It’s usually 2.)
Q27. In the binary search algorithm, two key comparisons are made through every iteration of the loop.
a. true b. false
The number of primitive operations executed in an iteration of the loop is if data[mid] > key, if data[mid] = = key, and if data[mid] < key.
Q28. One way to solve secondary clustering is with double hashing.
a. true b. false
Secondary clustering increases average search time, even quadratic probing is susceptible to secondary clustering since keys that have the same hash value also have the same probe sequence. Clustering may be minimized with double hashing.
Q29. Binary search can be performed on both sorted and unsorted lists.
a. true b. false
Binary search is a fast search algorithm with run-time complexity of (log n). This search algorithm works on the principle of divide and conquer. For this algorithm to work properly, the data collection should be in the sorted form.
Q30. Comparison-based search algorithms search the list by comparing the target element with the list elements.
a. true b. false
Binary search looks for a particular item by comparing the middle most item of the collection. If a match occurs, then the index of item is returned. If the middle item is greater than the item, then the item is searched in the sub-array to the left of the middle item. Otherwise, the item is searched for in the sub-array to the right of the middle item. This process continues on the sub-array as well until the size of the sub-array reduces to zero.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.