Question 1. Which of the following is not a search algorithm or technique?
Sequential search
Binary search
Linear search
Recursive search
Question 2. Why can't a binary search be applied on the list below?
17, 22, 31, 19, 39, 43, 16
The list is too small.
The list is not sorted.
The size of the list is not a power of 2.
A binary search can be applied on the list as it appears.
Question 3. When designing a hash function, we try to _____ the number of collisions.
maximize
minimize
double
increment
Question 4. In separate chaining, the keys that map to the same hash value are stored in a _____.
class
vector
array
linked list
Question 5. The hash table allows for insertions, deletions, and searches in _____.
O(n3 )
O(n log n)
average constant time
O(2n)
Question 6. In hashing, when two keys produce the same value of the hash function, we say that we have a key _____.
identification
assignment
collision
comparison
Question 7. Searching for an element based on using a unique key is _____.
slower
faster and more convenient
unusual
inefficient
Question 8. One of the main operations associated with the dictionary ADT is _____.
insert a value as the first item in the dictionary
given a value, insert or add a new entry to the dictionary
given a key and a value, insert or add a new entry to the dictionary
return the hash value of a key
Question 9. Suppose that the first 100,000 odd numbers are stored in a linked list, sorted in increasing order: 1, 3, 5, 7, . . . . Which searching method would you implement? Assume that only one search is to be conducted.
Sequential search
Sorted search
Binary search on an unsorted linked list
Binary search on a sorted linked list
Question 10. The worst-case time efficiency of a sequential search on an array a withn elements is _____.
when the item you are searching is not present in the array
when the item you are searching is the first item, a[0]
when the item you are searching is the second item in the array, a[1]
when the item you are searching is the one in the middle of the array, a[n/2]
Question 11. Given the following array, how many comparisons to an array entry are performed to search for the number 22 if you use the binary search algorithm?
11 13 15 19 22 27 31 39 46
1
2
4
22