Deck 12: Searching and Sorting

Question 1

____________________ 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

Answer 1

B
Explanation: Sorting is the process of arranging a group of items into a defined order.

Question 2

A _______________ search is more efficient than a linear search.

A) binary
B) selection
C) insertion
D) bubble
E) none of the above

Answer 2

A
Explanation: A binary search is more efficient than a linear search, but it assumes that the search pool is ordered.

Question 3

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

Answer 3

E
Explanation: All of the algorithms listed are examples of sorting algorithms.

Question 4

Which of the following algorithms is most easily expressed recursively?

A) linear search
B) quick sort
C) bubble sort
D) selection sort
E) none of the above algorithms are easily expressible recursively

Question 5

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

Question 6

Bubble sort is the most efficient searching algorithm.

Question 7

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

Question 8

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

Question 9

The ___________________ algorithm sorts values by repeatedly comparing neighboring elements in the list and swapping their position if the are not in order relative to each other.

A) insertion sort
B) selection sort
C) bubble sort
D) quick sort
E) merge sort

Question 10

Which of the following algorithms has a time complexity of O(log₂ n)?

A) insertion sort
B) selection sort
C) bubble sort
D) linear search
E) binary search

Question 11

If there are more items in a search pool, then it will typically require more comparisons to find an item.

Question 12

A linear search always requires more comparisons than a binary search.

Question 13

Every algorithm for a problem has the same efficiency.

Question 14

A __________________ search looks through the search pool one element at a time.

A) binary
B) clever
C) insertion
D) selection
E) linear

Question 15

Which of the following algorithms has a worst-case complexity of O(n²)?

A) insertion sort
B) selection sort
C) bubble sort
D) all of the above
E) neither a, b, nor c

Question 16

The ___________________ of an algorithm shows the relationship between the size of the problem and the value we hope to optimize.

A) growth function
B) growth analysis
C) size function
D) size analysis
E) none of the above

Question 17

A linear search is more efficient than a binary search.

Question 18

_____________________ 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

Question 19

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.

Question 20

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ⁿ)

Question 21

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

Question 22

To represent constant time complexity we use O(c).

Question 23

The selection sort algorithm sorts a list of values by repeatedly putting a particular value into its final, sorted position.

Question 24

Explain how merge sort works.

Question 25

Write out the state while being sorted using the insertion sort algorithm:
91 6 3 55 110 8 1 703

Question 26

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

Question 27

Write out the state of the list while being sorted using the selection sort algorithm:
91 6 3 55 110 8 1 703

Question 28

What is the complexity of the following code (in terms of the length of the array)?
for(int i = 0; i < 5; i++)
System.out.println(array[i]);

Question 29

What is the complexity of the following code (in terms of the length of the array), assuming someMethod has a complexity of O(1)?
for(int i = 0; i < array.length; i++)
for(int j = 0; j < array.length; j++)
someMethod(array[j]);

Question 30

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.

Question 31

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

Question 32

In the binary search algorithm, if the number of elements in the search pool is even, which value is used as the midpoint? Explain.

Question 33

Bubble sort works by separating a list into two lists, recursively sorting the two lists using bubble sort, and then combining the sorted sublists into a sorted list.

Question 34

Quick sort works by separating a list into two lists, and recursively sorting the two lists using quick sort.

Question 35

Explain why a faster computer can never make an exponential time algorithm run faster than a polynomial time algorithm on all inputs.

Question 36

Explain what O(1) means.

Question 37

How many times will the following code print out Hello World (in terms of the length of the array)?
for(int i = 0; i < array.length; i++) {
for(int j = 0; j < array.length; j++) {
for(int k = 0; k < array.length; k++) {
System.out.println("Hello World!");
}
}
}

Question 38

Explain how quick sort works.

Question 39

With each comparison, a binary search eliminates approximately half of the items remaining in the search pool.

Question 40

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