Question 1

A portion of your program includes the loop shown in the code snippet below to examine the elements of an array arr:
Int count = 0;
Int targetVal = 70;
For (int i = 0; i < arr.length; i++)
{
If (arr[i] >= targetVal)
{
Count++;
}
}
What can you conclude about the running time of this section of code?

Accepted Answer

The loop iterates through the array once, checking each element against the target value, and increments a counter if the element is greater than or equal to the target value. This is a linear search, with a running time of O(n), as the time required increases linearly with the size of the input array.

Question 2

If an element is present in an array of length n, how many element visits, on average, are necessary to find it using a linear search?

Accepted Answer

The answer of If an element is present in an...

Question 3

Binary search is an ____ algorithm.

Accepted Answer

Binary search has a time complexity of O(log n), which is much faster than linear search (O(n)) and divide-and-conquer algorithms such as quicksort (O(n log n)). Option A and B are not valid time complexities.

Question 4

The analysis for the number of visits in a binary search begins with the equation,
T(n) = T(n / 2) + 1. What does the number 1 represent in this equation?

Accepted Answer

The number 1 represents the visit to the middle element of the array before making a recursive call on one half of the array. It is the cost of visiting the middle element that is necessary to determine which half of the array to search next.

Question 5

Which of the following statements about running times of algorithms is correct?

Accepted Answer

The answer of Which of the following statements about running...

Question 6

Given an ordered array with 31 elements, how many elements must be visited in the worst case of binary search?

Accepted Answer

The answer of Given an ordered array with 31 elements,...

Question 7

A portion of your program implements a loop in which each step contains a fixed number of actions. What can you conclude about the running time of this section of code?

Accepted Answer

If each step contains a fixed number of actions, then the number of actions performed in the loop will be proportional to the size of the input (n), resulting in a linear running time (O(n)).

Question 8

If you implement a recursive linear search, its performance will be ____.

Accepted Answer

Recursive linear search has a time complexity of O(n), as it needs to traverse through the entire list/array to find the element being searched. This is because it checks each element one by one, making it a linear searching method. Therefore, the best choice is A.

Question 9

An algorithm that tests whether the first array element is equal to any of the other array elements would be an ____ algorithm.

Accepted Answer

Since the algorithm needs to compare the first element to all the other elements in the array, the time complexity is proportional to the size of the array, making it O(n).

Question 10

Can you search the following array using binary search?
Int[] A = {6, 5, 4, 2, 0, 1, -1, -17};

Accepted Answer

Binary search can only be applied to a sorted array. Since the given array is not sorted, binary search cannot be used.

Question 11

An algorithm that cuts the work in half in each step is an ____ algorithm.

Accepted Answer

An algorithm that cuts the work in half in each step is a binary search algorithm, which has a time complexity of O(log (n)). The other choices (A, B, and D) do not represent a binary search algorithm.

Question 12

A binary search is generally ____ a linear search.

Accepted Answer

Binary search divides the search range in half with each iteration, so it is faster than linear search which checks every element in the search range.

Question 13

Another name for linear search is ____ search.

Accepted Answer

Linear search is also known as sequential search because it sequentially checks each element in a list until the desired element is found or the end of the list is reached. Sorted, random, and binary search refer to different algorithms for searching in lists or arrays.

Question 14

A search technique where, in each step, you split the size of the search in half is called a____ search.

Accepted Answer

A binary search is the most efficient when searching for a specific element in a sorted list, as it eliminates half of the remaining search space with each step, resulting in a logarithmic time complexity. Random search is not a specific technique and does not have a defined algorithm. Linear search has a time complexity of O(n), which is not efficient for large lists. Merging search is not a common search technique.

Question 15

A portion of your program includes the loops shown in the code snippet below to examine the elements of two arrays, arr1 and arr2, both of length n:
Int matches = 0;
For (int i = 0; i < arr1.length; i++)
{
For (int j = 0; j < arr2.length; j++)
{
If (arr1[i].equals(arr2[j]))
{
Matches++;
}
}
}
What can you conclude about the running time of this section of code?

Accepted Answer

The answer of A portion of your program includes the...

Question 16

The method checkArray examines an array arr:
Public static boolean checkArray(int[] arr)
{
If (arr[0] >= arr[arr.length -1])
{
Return true;
}
Return false;
}
What can you conclude about the running time of this section of code?

Accepted Answer

The running time of the section of code is constant since it only checks the first and last elements of the array and does not depend on the size of the array. Therefore, the best choice is D, which has a running time of O(1).

Question 17

A portion of your program includes the method shown in the code snippet below to examine the elements of an array arr:
Private int findElement(int[] arr, int newVal)
{
Int pos = Arrays.binarySearch(arr, newVal);
Return pos;
}
What can you conclude about the running time of this section of code?

Accepted Answer

The method uses the binary search algorithm to find the position of the element in the array, which has a running time complexity of O(log (n)).

Question 18

Suppose we are using binary search on an array with approximately 1,000,000 elements. How many visits should we expect to make in the worst case?

Accepted Answer

The answer of Suppose we are using binary search on...

Question 19

Given an ordered array with 15 elements, how many elements must be visited in the worst case of binary search?

Accepted Answer

The answer of Given an ordered array with 15 elements,...

Question 20

The method findLargest examines the elements of an array arr which contains non-negative values
Public static int findLargest(int[] arr)
{
Int curLargest = -1;
For (int i = 0; i < arr.length; i++)
{
If (arr[i] >= curLargest)
{
CurLargest = arr[i];
}
}
Return curLargest;
}
What can you conclude about the running time of this section of code?

Accepted Answer

The code iterates through the array once, and at each iteration it only performs a constant number of operations (comparing the value at the current index to the current largest value and update if necessary), so the running time is proportional to the size of the array, i.e. O(n).

Quiz 14: Sorting and Searching

A portion of your program includes the loop shown in the code snippet below to examine the elements of an array arr: Int count = 0; Int targetVal = 70; For (int i = 0; i < arr.length; i++) { If (arr[i] >= targetVal) { Count++; } } What can you conclude about the running time of this section of code?