Question 1

If algorithm A requires 2n + 1 basic operations to process an input of size n, and Algorithm B requires 3n + 2 basic operations to process the same input, algorithms A and B are considered to be equally efficient.

Accepted Answer

The answer of If algorithm A requires 2n + 1...

Question 2

The ________ sort usually performs more exchanges than the ________ sort.

Accepted Answer

The bubble sort algorithm works by repeatedly swapping adjacent elements if they are in the wrong order. This means that in the worst case, where the array is in reverse order, the bubble sort performs n*(n-1)/2 swaps, which is more than the selection sort algorithm. The selection sort algorithm, on the other hand, works by repeatedly finding the minimum element from the unsorted portion of the array and putting it at the beginning. This requires n-1 swaps at most, which is less than the bubble sort. Therefore, the correct answer is A.

Question 3

A(n) ________ algorithm arranges data into some order.

Accepted Answer

The term "sorting algorithm" specifically refers to an algorithm that arranges data in a specific order, making choice A the correct answer. A searching algorithm, on the other hand, looks for a particular item in a collection of data. The terms "ordering" and "linear" are not specific enough to refer to a particular type of algorithm. "Binary" refers to a specific type of searching algorithm that is used when the data is already sorted.

Question 4

To find a value that is in an unordered array of 50 items, how many values must linear search examine on average?

Accepted Answer

Linear search examines each item in the array until it finds the desired value, so on average it will examine half of the array before finding the value. Therefore, the number of values it must examine on average is 50/2 = 25.

Question 5

When searching for a particular object in an array of objects, it is necessary to compare the search key to the value in each examined object's key field.

Accepted Answer

When searching for a particular object in an array of objects, it is necessary to compare the search key to the value in each examined object's key field, in order to find the matching object or determine that it does not exist in the array.

Question 6

Sorted data can be ordered

Accepted Answer

Sorted data refers to organizing data in a specific sequence, and it can indeed be ordered from lowest to highest (ascending order) or from highest to lowest (descending order). Additionally, sorting algorithms such as bubble sort and selection sort are methods used to arrange data in a sorted order, making all the provided options correct ways to sort data.

Question 7

A ________ search uses a loop to sequentially step through an array.

Accepted Answer

A linear search, also known as a sequential search, uses a loop to sequentially go through an array to find a specific element. It is not as efficient as a binary search, but it works well for small arrays or unsorted data.

Question 8

If a selection sort is used to arrange the numbers 8 6 4 9 3 7 in ascending order, what order will the data be in after the first pass of the sort is completed?

Accepted Answer

Selection sort works by selecting the minimum element from the unsorted segment of the array and swapping it with the leftmost unsorted element, moving the boundary of the unsorted segment one step to the right. After the first pass, the smallest number (3) is swapped with the first element (8), resulting in the sequence 3 6 4 9 8 7.

Question 9

Using a binary search, you are more likely to find an item than if you use a linear search.

Accepted Answer

The likelihood of finding an item does not depend on the search algorithm (binary or linear search) but on whether the item is present in the data set. Both methods will find the item if it exists.

Question 10

The ________ search is adequate for searching through small arrays, but not through large ones.

Accepted Answer

Linear search is adequate for small arrays because it checks each element in the array one by one, which becomes inefficient as the size of the array increases.

Question 11

A binary search requires that the elements be in order.

Accepted Answer

A binary search algorithm assumes that the list of elements is in order (ascending or descending) to perform efficiently. By checking the middle element of the list and comparing to the search value, the algorithm can eliminate half of the elements and repeat the process until the target value is found or the list is exhausted.

Question 12

If a binary search is used to search for the number 4 in the 11-element array shown here int A[] = {1, 2, 3, 4, 6, 7, 8, 9, 10, 12, 17};
Which value will the 4 be compared to first?

Accepted Answer

In a binary search, the array is divided into halves to find the target value. The first comparison is with the middle element of the array. Since the array has 11 elements, the middle element is the 6th element (considering 0-based indexing), which is 7.

Question 13

If a bubble sort is used to arrange the numbers 8 6 4 9 3 7 in ascending order, what order will the data be in after the first pass of the sort is completed?

Accepted Answer

The answer of If a bubble sort is used to...

Question 14

We can estimate the ________ of an algorithm by counting the number of basic steps it requires to solve a problem.

Accepted Answer

The efficiency of an algorithm is determined by the number of basic steps it requires to solve a problem. The fewer basic steps an algorithm requires, the more efficient it is. Counting the number of lines of code, run time, code quality, and result do not directly measure the efficiency of an algorithm.

Question 15

When sorting an array of objects, if the values in the data member being sorted on are out of order for two objects, those two data values should be swapped.

Accepted Answer

Sorting an array of objects typically involves comparing the objects based on a specific property or multiple properties, but the actual sorting algorithm may not necessarily swap just the values of the data members. Instead, it swaps the objects themselves to maintain the integrity of the objects.

Question 16

To find a value in an ordered array of 50 items, how many values must binary search examine at most.

Accepted Answer

Binary search operates by dividing the search interval in half each time. For an array of 50 items, the maximum number of values it needs to examine to find a value or conclude it's not present is $\log_2{50}$, which is approximately 5.64. This rounds up to 6, making option B correct.

Question 17

When an array is sorted from highest to lowest, it is said to be in ascending order.

Accepted Answer

When an array is sorted from highest to lowest, it is said to be in descending order, not ascending.

Question 18

Selection sort requires ________ passes to put n data items in order.

Accepted Answer

Selection sort works by selecting the smallest element in each pass and swapping it with the element in the proper position. Since we need to perform n-1 swaps to put n elements in their proper positions, selection sort also requires n-1 passes. Therefore, the correct answer is D.

Question 19

To determine that a value is not present in an unordered array of 50 items, how many values must linear search examine on average?

Accepted Answer

In the worst-case scenario, the value may not be present in any of the 50 items, so we need to examine all 50 items to confirm its absence. Therefore, on average, linear search needs to examine 50/2 = 25 values. However, the question only asks for the number of values on average, so the best answer is D) 50.

Question 20

Any sorting algorithm, such as bubble sort or selection sort, that can be used on data stored in an array can also be used on data stored in a vector.

Accepted Answer

This is true as vectors are essentially dynamic arrays and support all operations that can be performed on an array, including sorting algorithms like bubble sort or selection sort.

Quiz 9: Searching, Sorting, Algorithm Analysis