Searching And Sorting Exam Questions Chapter 18

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(log₂n)

c) O(n²)

d) O(n³)

e) O(2ⁿ)

15) Which of the following algorithms has a worst case complexity of O(n log₂n)?

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.

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..

3) Write a method that accepts an integer array as a parameter and sorts it using the bubble sort algorithm.

4) Write a method that accepts an array of integers as a parameter and sorts them using the selection sort algorithm.

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];

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

12) Write out the state of the list while being sorted using the selection sort algorithm:

91 6 3 55 110 8 1 703

13) Explain how radix sort works.

14) Write the declaration of a class that implements the Comparator interface that would allow Frammis objects to be sorted by quantity.

15) Write the declaration of a class that implements the Comparator interface that would allow Frammis objects to be sorted by name.