Question 1

At most, how many comparisons are required to search a sorted vector of 1023 elements using the binary search algorithm?&#10;A) 10&#10;B) 15&#10;C) 20&#10;D) 30

Accepted Answer

Binary search algorithm divides the sorted list into halves to find a target value, requiring at most $\log_2(n+1)$ comparisons. For 1023 elements, it's $\log_2(1024) = 10$.

Question 2

Which of the following is not a valid runtime description according to Big O notation? A) O(1) B) O(n) C) O(n²) D) All of the above are valid.

Accepted Answer

All the given options are valid runtime descriptions in Big O notation.

Question 3

Which of the following represents the efficiency of the insertion sort? A) O(1) B) O(n) C) O(n²) D) None of the above.

Accepted Answer

The efficiency of the insertion sort in the average and worst case is O(n^2), which is represented by the choice "C" using the encoded message "O(n²)" where the encoding likely represents O(n^2).

Question 4

Selection sort has a Big O of: A) O(2n) B) O(n²) C) O(½n²) D) O((n² - n)/2 )

Accepted Answer

Selection sort has a time complexity of O(n^2), where n is the number of elements in the array. This is because for each element, the algorithm scans the remaining elements to find the minimum (or maximum) to swap with the current position, leading to a quadratic number of comparisons.

Question 5

The merge sort algorithm:&#10;A) Can be used only on vectors of even length.&#10;B) Works by reducing vectors down to the base case of a two-element vector.&#10;C) Works by merging two sorted vectors into one larger sorted vector.&#10;D) Cannot be implemented recursively.

Accepted Answer

Merge sort works by dividing a vector into two halves, sorting each half recursively, and then merging them back together. This process continues recursively until the base case of a two-element vector is reached. The two halves are merged back together by creating a new vector and inserting elements in order from both halves. This results in a larger sorted vector. The length of the original vector does not have to be even.

Question 6

Which of the following statements about searching algorithms and their efficiency is false?&#10;A) The major difference between various searching algorithms is the amount of effort they require to complete the search.&#10;B) Big O notation is one way to describe how likely it is that a searching algorithm will find its target.&#10;C) The effort required to perform a search or a sort is particularly dependent on the number of data elements.&#10;D) A more efficient searching algorithm is usually more complex and difficult to implement.

Accepted Answer

Big O notation describes the performance or complexity of an algorithm in terms of time or space required as the input size grows, not the likelihood of finding a target.

Question 7

A merge sort operation runs in: A) O(log n) time. B) O(n) time. C) O(n log n) time. D) O(n²) time.

Accepted Answer

Merge sort has a time complexity of O(n log n) as it divides the array into two halves recursively until each subarray contains only one element and then merges the subarrays in a sorted order. The merging operation takes O(n) time and it is performed log n times. Therefore, the overall time complexity of the merge sort algorithm is O(n log n).

Question 8

An algorithm that requires __________ operations to complete its task on n data elements is said to have linear runtime. A) n³+ 9 B) 3 n²+ 3 n+ 2 C) 2 n+ 1 D) 6

Accepted Answer

The algorithm with 2n + 1 operations is linear as the number of operations increases linearly with the number of data elements.

Question 9

The choice of which sorting algorithm to use does not affect:&#10;A) How sorted the vector will be.&#10;B) The time it takes for the sorting operation to complete.&#10;C) The amount of memory used by the program.&#10;D) All of the above will be affected by the choice of sorting algorithm.

Accepted Answer

The choice of sorting algorithm affects the time it takes for the sorting operation to complete and the amount of memory used by the program, but not how sorted the vector will be, as all sorting algorithms aim to fully sort the data.

Question 10

The first step performed by the binary search algorithm at each iteration is to:&#10;A) Compare the search key with the lowest element in the current subvector.&#10;B) Compare the search key with the middle element in the current subvector.&#10;C) Compare the search key with the highest element in the current subvector.&#10;D) Count the number of elements in the current subvector.

Accepted Answer

The binary search algorithm divides the search interval in half at each step by comparing the search key with the middle element in the current subvector. This means that choice B is the correct answer as it describes the first step of each iteration.

Deck 20: Searching and Sorting