Question 1

Bubble sort is the most efficient searching algorithm.

Accepted Answer

A) True 
 B)False

Question 2

Suppose we have algorithms that solve a particular problem that have the following complexities. Which one is most efficient?

Accepted Answer

A)   O(1) 
B)   O(log2n) 
C)   O(n2) 
D)   O(n3) 
E)   O(2n) F) A) and C)
G) A) and E)

Question 3

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

Accepted Answer

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

Question 4

A _______________ search is more efficient than a linear search.

Accepted Answer

A)   binary
B)   selection
C)   insertion
D)   bubble
E)   none of the aboveF) B) and C)
G) A) and B)

Question 5

_____________________ is the process of finding a designated target element within a group of items.

Accepted Answer

A)   Sorting
B)   Searching
C)   Recursing
D)   Helping
E)   none of the aboveF) A) and B)
G) A) and C)

Question 6

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.

Accepted Answer

public boolean linearSearch(in...

Question 7

____________________ is the process of arranging a group of items into a defined order.

Accepted Answer

A)   Searching
B)   Sorting
C)   Selecting
D)   Helping
E)   none of the aboveF) A) and B)
G) A) and C) B

Question 8

Explain what O(1) means.

Accepted Answer

An algorithm's growth rate is ...

Question 9

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

Accepted Answer

While a faster computer may make a polyn...

Question 10

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

Accepted Answer

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

Question 11

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!");
}
}
}

Accepted Answer

If n is the length o...

Question 12

A linear search is more efficient than a binary search.

Accepted Answer

A) True 
 B)False

Question 13

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

Accepted Answer

The comple...

Question 14

Which of the following is not a sorting algorithm?

Accepted Answer

A)   Bubble sort
B)   Quick sort
C)   Merge sort
D)   Selection sort
E)   all of the above are sorting algorithmsF) B) and E)
G) D) and E)

Question 15

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

Accepted Answer

If the number of elements in the search ...

Question 16

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.

Accepted Answer

A)   insertion sort
B)   selection sort
C)   bubble sort
D)   quick sort
E)   merge sortF) D) and E)
G) None of the above

Question 17

Write out the state while being sorted using the insertion sort algorithm:

Accepted Answer

6 91 3 55 110 8 1 703
3 6 91 5...

Question 18

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

Accepted Answer

This fails because the first step overwr...

Question 19

As the number of items in a search pool grows, the number of comparisons required to search _______________ .

Accepted Answer

A)   increases
B)   decreases
C)   stays the same
D)   goes to 0
E)   none of the aboveF) A) and E)
G) All of the above

Question 20

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

Accepted Answer

A)   binary
B)   clever
C)   insertion
D)   selection
E)   linearF) B) and E)
G) A) and B)

Exam 12: Searching and Sorting

Bubble sort is the most efficient searching algorithm.

Correct AnswerverifiedShow Answer

Suppose we have algorithms that solve a particular problem that have the following complexities. Which one is most efficient?

Correct AnswerverifiedShow Answer

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

Correct Answerverifiedpublic 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; }

A _______________ search is more efficient than a linear search.

Correct AnswerverifiedShow Answer

_____________________ is the process of finding a designated target element within a group of items.

Correct AnswerverifiedShow Answer

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.

Correct Answerverifiedpublic boolean linearSearch(in...View AnswerShow Answer

____________________ is the process of arranging a group of items into a defined order.

Correct AnswerverifiedB

Explain what O(1) means.

Correct AnswerverifiedAn algorithm's growth rate is ...View AnswerShow Answer

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

Correct AnswerverifiedWhile a faster computer may make a polyn...View AnswerShow Answer

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

Correct AnswerverifiedShow Answer

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!"); } } }

Correct Answerverified11eddcf1_9996_d01d_8512_fbd29aaab956_TB2841_00

A linear search is more efficient than a binary search.

Correct AnswerverifiedShow Answer

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

Correct AnswerverifiedThe comple...View AnswerShow Answer

Which of the following is not a sorting algorithm?

Correct AnswerverifiedShow Answer

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

Correct AnswerverifiedIf the number of elements in the search ...View AnswerShow Answer

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.

Correct AnswerverifiedShow Answer

Write out the state while being sorted using the insertion sort algorithm:

Correct Answerverified6 91 3 55 110 8 1 7033 6 91 5...View AnswerShow Answer

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

Correct AnswerverifiedThis fails because the first step overwr...View AnswerShow Answer

As the number of items in a search pool grows, the number of comparisons required to search _______________ .

Correct AnswerverifiedShow Answer

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

Correct AnswerverifiedShow Answer

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified
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; }

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified
public boolean linearSearch(in...
View Answer

Correct Answer
verified
B

Correct Answer
verified
An algorithm's growth rate is ...
View Answer

Correct Answer
verified
While a faster computer may make a polyn...
View Answer

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

Correct Answer
verified

Correct Answer
verified
11eddcf1_9996_d01d_8512_fbd29aaab956_TB2841_00

Correct Answer
verified

Correct Answer
verified
The comple...
View Answer

Correct Answer
verified

Correct Answer
verified
If the number of elements in the search ...
View Answer

Correct Answer
verified

Correct Answer
verified
6 91 3 55 110 8 1 703
3 6 91 5...
View Answer

Correct Answer
verified
This fails because the first step overwr...
View Answer

Correct Answer
verified

Correct Answer
verified