Chapter 18 Searching And Sorting Test Bank Docx - Instructor Test Bank | Java Foundations 5e Lewis by John Lewis. DOCX document preview.
Chapter 18: Searching and Sorting
Multiple Choice Questions:
1) _____________________ is the process of finding a designated target element within a group of items.
a) Sorting
b) Searching
c) Recursing
d) Helping
e) none of the above
2) As the number of items in a search pool grows, the number of comparisons required to search _______________ .
a) increases
b) decreases
c) stays the same
d) goes to 0
e) none of the above
3) A __________________ search looks through the search pool one element at a time.
a) binary
b) clever
c) insertion
d) selection
e) linear
4) A _______________ search is more efficient than a linear search.
a) binary
b) selection
c) insertion
d) bubble
e) none of the above
5) In a binary search, _______________________________ .
a) it is assumed that all of the elements are integers.
b) it is assumed that all of the elements are Strings.
c) it is assumed that the search pool is small.
d) it is assumed that the search pool is ordered.
e) it is assumed that the search pool is large.
6) ____________________ is the process of arranging a group of items into a defined order.
a) Searching
b) Sorting
c) Selecting
d) Helping
e) none of the above
7) Which of the following is not a sorting algorithm?
a) Bubble sort
b) Quick sort
c) Merge sort
d) Selection sort
e) all of the above are sorting algorithms
8) Which data structures are used by a radix sort?
a) stacks
b) queues
c) heaps
d) both a) and b) are correct
e) a), b), and c) are all correct
9) The ___________________ algorithm sorts values by repeatedly comparing neighboring elements in the list and swapping their position if they are not in order relative to each other.
a) insertion sort
b) selection sort
c) bubble sort
d) quick sort
e) merge sort
10) The __________________ algorithm sorts a list of values by repetitively inserting a particular value into a subset of the list that has already been sorted.
a) insertion sort
b) selection sort
c) bubble sort
d) quick sort
e) merge sort
11) The ___________________ is the number of possible values of the digits or characters in a sort key.
a) radix
b) asymptote
c) thread
d) order
e) none of the above
12) ________ can be used to sort the same set of objects in multiple ways
a) insertion sort
b) selection sort
c) bubble sort
d) random sort
e) Comparator objects
13) In order to compare objects of a class in different ways,
a) the class must implement the Comparable interface
b) the class must implement the Comparator interface
c) the class must inherit from the Comparator class
d) a separate class must be created that implements the Comparator interface and provides a body for the compare method
e) None of these is correct.
14) Suppose we have algorithms that solve a particular problem that have the following complexities. Which one is most efficient?
a) O(1)
b) O(log2n)
c) O(n2)
d) O(n3)
e) O(2n)
15) Which of the following algorithms has a worst case complexity of O(n log2n)?
a) insertion sort
b) selection sort
c) bubble sort
d) merge sort
e) none of the above
1) In a radix sort, the radix is the number of elements to be sorted.
2) The underlying data structure used in a radix sort is a stack
3) A linear search always requires more comparisons than a binary search.
4) If there are more items in a search pool, then it will typically require more comparisons to find an item.
5) Bubble sort is the most efficient searching algorithm.
6) Quick sort works by separating a list into two lists, and recursively sorting the two lists using quick sort.
7) The sort method of the Arrays class sorts the elements of an array by using a comparator
8) Implementing the Comparator interface requires writing a body for the compareTo method.
9) With each comparison, a binary search eliminates approximately half of the items remaining in the search pool.
10) The selection sort algorithm sorts a list of values by repeatedly putting a particular value into its final, sorted position.
1) Write a method that accepts an integer and an array of integers, and returns true if the integer is contained in the array. The method should use a linear search.
public boolean linearSearch(int a, int[] array)
{
boolean found = false;
int i = 0;
while(i < array.length && !found)
{
if(array[i] == a)
found = true;
i++;
}
return found;
}
2) Write a method that accepts an integer and an array of integers and returns true if the integer is contained in the array. You may assume that the array is sorted, and your method should use a binary search.
public boolean binarySearch(int a, int[] array)
{
int first = 0;
int last = array.length-1;
int mid;
while(first <= last)
{
mid = (first+last)/2;
if(array[mid] == a)
return true;
else if(array[mid] > a)
last = mid - 1;
else
last = mid + 1;
}
return false;
}
3) Write a method that accepts an integer array as a parameter and sorts it using the bubble sort algorithm.
public void bubbleSort(int[] array)
{
int temp;
for(int i = array.length-1; i >=0; i--)
{
for(int j = 0; j < i; j++)
{
if(array[j] > array[j+1])
{
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}//end if
}//end for j
}//end for i
}
4) Write a method that accepts an array of integers as a parameter and sorts them using the selection sort algorithm.
public void selectionSort(int [] array)
{
int minIndex, temp;
for(int i = 0; i < array.length; i++)
{
minIndex = i;
for(int j = i+1; j < array.length; j++)
{
if(array[j] < array[minIndex])
minIndex = j;
}//end for j
temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}//end for i
}
5) If binary search is more efficient than linear search, why not just sort an array and then use binary search whenever we need to search for an element in an unsorted array?
6) In the binary search algorithm, if the number of elements in the search pool is even, which value is used as the midpoint? Explain.
7) Suppose we would like to swap the elements at index i and index j in an array. Does the following code work? If so, explain how. If not, explain why it fails.
array[i] = array[j];
array[j] = array[i];
A temporary variable is required to properly swap the two elements in an array. First, the value of one element is copied into the temporary variable. Then, the value of the second element is copied into the first element. Finally, the value that was copied into the temporary variable is copied into the second element.
8) InventoryItem is a class that defines an item in the inventory of a warehouse. One of the fields, partNumber, is unique to each item in the inventory. partNumber is stored as an int, but it is comprised of 6 octal digits, that is, digits in the range 0 – 7 inclusive. If InventoryItem objects are sorted according to the partNumber field, what is the radix?
9) Explain how quick sort works.
10) Explain how merge sort works.
11) Write out the state while being sorted using the insertion sort algorithm:
91 6 3 55 110 8 1 703
6 91 3 55 110 8 1 703
3 6 91 55 110 8 1 703
3 6 55 91 110 8 1 703
3 6 55 91 110 8 1 703
3 6 8 55 91 110 1 703
1 3 6 8 55 91 110 703
1 3 6 8 55 91 110 703
12) Write out the state of the list while being sorted using the selection sort algorithm:
91 6 3 55 110 8 1 703
1 6 3 55 110 8 93 703
1 3 6 55 110 8 93 703
1 3 6 55 110 8 93 703
1 3 6 8 110 55 93 703
1 3 6 8 55 110 93 703
1 3 6 8 55 93 110 703
1 3 6 8 55 93 110 703
13) Explain how radix sort works.
The elements are moved to the queues based on the least significant field of the sort key first, then by the next-least-significant field, and so on, until the last set of moves places the elements into queues according to the most significant field. By removing the elements from the lowest-valued queue first, then the next lowest-valued queue, and on, the elements will be retrieved in sorted order.
Use the following class declaration for questions 14) and 15)
public class Frammis
{
private Integer quantity;
private String name;
// constructors, accessor, and mutator methods
// go here
}
14) Write the declaration of a class that implements the Comparator interface that would allow Frammis objects to be sorted by quantity.
public class QuantityCompare implements Comparator<Frammis>
{
public int compare(Frammis f1, Frammis f2)
{
Integer quantity1 = f1.getQuantity();
Integer quantity2 = f2.getQuantity();
return quantity1.compareTo(quantity2);
}
}
15) Write the declaration of a class that implements the Comparator interface that would allow Frammis objects to be sorted by name.
public class NameCompare implements Comparator<Frammis>
{
public int compare(Frammis f1, Frammis f2)
{
String name1 = f1.getName();
String name2 = f2.getName();
return name1.compareTo(name2);
}
}