Question 1

The choice of which sorting algorithm to use does not affect:&#10;A) How thoroughly 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

All sorting algorithms will result in a thoroughly sorted vector, but they differ in time complexity and memory usage.

Question 2

Which of the following represents the efficiency of the insertion sort? A) O1) B) On) C) On²) 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 3

Selection sort has a Big O of: A) O2n) B) On²) C) O½n²) D) On² - 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 4

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 5

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

Accepted Answer

Merge sort has a time complexity of O(n log n) because it divides the list in half recursively, sorts each half, and then merges the sorted halves back together, and the splitting takes O(log n) time while merging takes O(n) time.

Question 6

The merge sort algorithm:&#10;A) Can only be used 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

The merge sort algorithm works by merging two sorted vectors into one larger sorted vector. It can be implemented recursively to repeatedly divide the vector into halves until each half consists of only one or two elements, which are then merged back together to form a sorted vector. The length of the vector does not have to be even for this algorithm to work.

Question 7

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 iteration and compares the search key with the middle element in the current subvector to determine which half the key lies in. Therefore, the first step at each iteration is to compare the search key with the middle element in the current subvector.

Question 8

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

Accepted Answer

The answer of Which of the following is not a...

Question 9

Which of the following is not true about searching algorithms and their efficiency?&#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 time complexity or efficiency of an algorithm, not the likelihood of finding a target.

Question 10

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

Accepted Answer

The algorithm with 2 n+ 1 operations has a runtime that is directly proportional to the number of data elements, n. This is the definition of linear runtime. Options A and B have additional operations that are not linearly proportional to n, and option D is not a valid choice as it does not refer to any specific algorithm.

Deck 19: Searching and Sorting