Chapter 19 - Searching Test Bank Docx

Chapter 19 - Searching

True/False (19)

1. A binary search is usually slower than a sequential search on sorted array of data.
2. A binary search is usually much faster than a sequential search on unsorted data stored in a chain of linked nodes.
3. Sorting data typically takes more time than searching it.
4. If you have a list object to search that is an instance of ADT list, you search it by using the list operation contains.
5. The implementation of the ADT list method contains is dependent on how the entries in the list are stored.
6. A search can only be performed iteratively.
7. An empty array can never be a base case for a recursive search algorithm because it never contains the desired item.
8. A sequential search can be more efficient if the data is sorted.
9. You use fewer comparisons in a recursive search than a sequential search on an unsorted array.
10. A sequential search on a very large array is very inefficient.
11. In a sequential search of a sorted array, you must examine the entire array if an item is not present in the array.
12. Classes that implement the Comparable interface should define an equals method.
13. All objects have the method equals.
14. All objects have the method compareTo.
15. You can implement an iterative sequential search of a chain of linked nodes with the same efficiency as that of a sequential search of an array.
16. You can implement a recursive sequential search of a chain of linked nodes with the same efficiency as that of a sequential search of an array.
17. Sequentially searching a sorted linked chain of nodes is completely different than sequentially searching a sorted array.
18. A binary search of a chain of linked nodes is impractical.
19. The recursive sequential search algorithm is tail recursive.

Short Answer (5)

1. How do we shield the client from the details of handling the first and last indexes of the array to search in a recursive search on an unsorted array?

public static <T> boolean inArray(T[] inArray, t anEntry)
and implement the algorithm as a private method search that inArray invokes.

1. Given the following array, show the comparisons to an array entry that are performed to search for the number 23 if you use the binary search algorithm.
   2 3 5 7 11 13 17 19 23 29 31 37
2. Given the following array, show the comparisons to an array entry that are performed to search for the number 11 if you use the binary search algorithm.
   2 3 5 7 11 13 17 19 23 29 31 37
3. What is the difference between the calculation of the midpoint in the Java computation and the one given in the binarySearch method? Show the impact, if any on a search between the indexes 26 and 50.
4. Explain why a binary search implementation of a sorted chain is impractical.

Multiple Choice (30) WARNING: CORRECT ANSWERS ARE IN THE SAME POSITION AND TAGGED WITH . YOU SHOULD RANDOMIZE THE LOCATION OF THE CORRECT ANSWERS IN YOUR EXAM.

1. If you have a list object to search that is an instance of ADT list, you search it by using the list operation
   1. contains
   2. search
   3. inList
   4. has
2. The implementation of the ADT list method contains is dependent on
   1. how we store the list entries
   2. whether the list entries are in ascending order
   3. whether the list entries are in descending order
   4. how we handle empty lists
3. Given the following dataset, which sorting method would be recommended?
   3 7 9 4 2 5
   1. iterative sequential search on an unsorted array
   2. iterative sequential search on a sorted array
   3. binary search on an unsorted array
   4. none of the above
4. Assume you have an array of unsorted items that allows duplicate entries and that the item you are searching for is present. Using an iterative sequential search on an unsorted array, the loop exits when
   1. it locates the first entry in the array that matches the item being searched for
   2. it locates the last entry in the array that matches the item being searched for
   3. when it reaches the end of the array
   4. none of the above
5. Using an iterative sequential search on an unsorted array, what happens when the inArray method does not find the entry we are searching for?
   1. it returns false
   2. it returns 0
   3. it returns null
   4. it throws an ElementNotFoundException
6. Using a recursive search on an unsorted array, a reasonable base case would be
   1. an empty array
   2. an array index of -1
   3. when first index < last index
   4. none of the above
7. In a recursive sequential search of an unsorted array we search elements from
   1. 0 to n-1
   2. 0 to n
   3. 1 to n-1
   4. 1 to n
8. A sequential search can be ______ if the data is sorted.
   1. more efficient
   2. less efficient
   3. a bad choice
   4. impossible
9. The best-case time efficiency of a sequential search on an array is
   1. O(1)
   2. O(log n)
   3. O(n)
   4. O(n2)
10. The average-case time efficiency of a sequential search on an array is
    1. O(n)
    2. O(log n)
    3. O(1)
    4. O(n2)
11. The worst-case time efficiency of a sequential search on an array is
    1. O(n)
    2. O(log n)
    3. O(1)
    4. O(n2)
12. When searching an unsorted array of items, the recursive search performs ______ comparisons the iterative search.
    1. the same number of comparisons as
    2. fewer comparisons than
    3. more comparisons than
    4. almost as many comparisons as
13. A sequential search of a sorted array can tell whether an item is present in the array in _____ a sequential search of an unsorted array.
    1. fewer comparisons than
    2. more comparisons than
    3. the same number of comparisons as
    4. none of the above
14. A search on a data set that divides the data roughly in half every iteration is called a(n) _____ search
    1. binary
    2. sequential
    3. sorted
    4. divided
15. In an array of 100 items sorted in ascending order, if you are searching for the number 165 and the entry at array index [50] has a value of 72, what can we conclude?
    1. the value will not be found at indexes [0] through [50]
    2. if the value is in the array, it will be found somewhere at indexes [51] through [99]
    3. one half of the array can be ignored in the next step
    4. all of the above
16. What is the base case in the recursive algorithm for a binary search of a sorted array?
    1. first index > last index
    2. first index < last index
    3. first index == last index
    4. the array is empty
17. Given the following array, how many comparisons to an array entry are performed to search for the number 13 if you use the binary search algorithm?
    2 3 5 7 11 13 17 19 23 29 31 37
    1. 1
    2. 2
    3. 6
    4. 12
18. Given the following array, how many comparisons to an array entry are performed to search for the number 2 if you use the binary search algorithm?
    2 3 5 7 11 13 17 19 23 29 31 37
    1. 5
    2. 1
    3. 3
    4. 0
19. Given the following array, how many comparisons to an array entry are performed to search for the number 37 if you use the binary search algorithm?
    2 3 5 7 11 13 17 19 23 29 31 37
    1. 7
    2. 12
    3. 2
    4. 24
20. Given the following array, how many comparisons to an array entry are performed to search for the number 11 if you use the binary search algorithm?
    2 3 5 7 11 13 17 19 23 29 31 37
    1. 7
    2. 5
    3. 10
    4. 2
21. Given the following array, how many comparisons to an array entry are performed to search for the number 23 if you use the binary search algorithm?
    2 3 5 7 11 13 17 19 23 29 31 37
    1. 3
    2. 4
    3. 9
    4. 5
22. Classes that implement the Comparable interface must define
    1. compareTo
    2. equals
    3. lessThan
    4. notEquals
23. When you truncate a positive real number to an integer, you are computing the number’s
    1. floor
    2. ceiling
    3. truncation factor
    4. fractional portion
24. The best-case time efficiency of a binary search on a sorted array is
    1. O(1)
    2. O(log n)
    3. O(n)
    4. O(n2)
25. The average-case time efficiency of a binary search on a sorted array is
    1. O(log n)
    2. O(1)
    3. O(n)
    4. O(n2)
26. The worst-case time efficiency of a binary search on a sorted array is
    1. O(log n)
    2. O(1)
    3. O(n)
    4. O(n2)
27. The best-case time efficiency of a sequential search on an unsorted chain of linked nodes is
    1. O(1)
    2. O(log n)
    3. O(n)
    4. O(n2)
28. The average-case time efficiency of a sequential search on an unsorted chain of linked nodes is
    1. O(n)
    2. O(log n)
    3. O(1)
    4. O(n2)
29. The worst-case time efficiency of a sequential search on an unsorted chain of linked nodes is
    1. O(n)
    2. O(log n)
    3. O(1)
    4. O(n2)
30. A binary search of a sorted chain of nodes is _____ than a sequential search of a sorted chain.
    1. less efficient
    2. more efficient
    3. faster
    4. easier to implement