Overview Lesson #5

Below is a list of all the lessons this overview lesson will cover.

1. ArrayLists
2. Recursion
3. Sorting and Searching
4. Common Sorting Methods
5. Common Searching
6. Mergesort
7. Quicksort

Lesson Quiz

The first two questions in this quiz cover ArrayLists and Recursion. The remaining questions cover material taught in lessons 3-7 above.

1. Which of the following is an advantage of arrays over ArrayLists?

a. Arrays are primitive whereas ArrayLists are objects.
b. Arrays are slightly faster in performance compared to ArrayLists when dealing with a fixed amount of data.
c. Arrays are able to increase in size to fit more data.
d. Array uses .length whereas ArrayLists use .size().

2. Which of the following is not a common use of recursion?

b. Searching through all possible answer choices.
c. Solving problems using backtracking.
d. Generating all possible combinations.

3. What is the time complexity of the following code?

``````    public void temp(int n) {
for (int i = 0; i < n; i++) {
System.out.println(n);
temp(n-1);
}
}
``````
a. O(n)
b. O(n^2)
c. O(n!)
d. O(n^n)

4. Which of the sorting methods would be the most efficient in finding the top 5 scores in a competition with 500 thousand participants?

a. Selection Sort terminated after five iterations
b. Insertion Sort terminated after five iterations
c. Merge Sort
d. Quicksort

5. Which of the sorting methods would be most efficient in sorting an array of one million integers where each integer is a number between 1 and 3?

a. Selection Sort
b. Insertion Sort
c. Merge Sort
d. Quicksort

6. What is one advantage Quicksort has over Merge Sort?

a. Quicksort’s best, average, and worst case scenario are all better than Merge Sort.
b. Quicksort performs better when all elements are the same.
c. Quicksort can have O(1) space complexity whereas Merge Sort always has O(n).
d. Quicksort has a best case scenario of O(log n) compared to Merge Sort’s O(n log n).

7. The following code is an incorrect implementation of binary search. Which line contains the mistake?

``````    public static int binarySearch(int[] arr, int val) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {             // Line 1
int mid = left + right / 2;     // Line 2
if (arr[mid] == val) {
return mid;
} else if (val < arr[mid]) {    // Line 3
right = mid - 1;
} else {
left = mid + 1;             // Line 4
}
}
return -1;                          // Line 5
}
``````
a. Line 1
b. Line 2
c. Line 3
d. Line 4
e. Line 5

Written by Alan Bi

Notice any mistakes? Please email us at [email protected] so that we can fix any inaccuracies.