Data Structures Chapter 9 Test 1 and 2

The advantage of a linear search is that

A(n) ______ search is more efficient than a(n) ______ search.

The linear search is adequate for searching through ______ arrays, but not through ______ ones.

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

A binary search begins by examining the ______ element of an array.

If the item being searched for is not in the array, binary search stops looking for it and reports that it is not there when

When searching for an item in an unordered set of data, binary search can find the item more quickly than linear search.

A search can be performed on an array of

A sorting algorithm can be used to arrange a set of ______ in ______ order.

The ______ sort usually performs fewer exchanges than the ______ sort.

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

To determine that an item is not in an unordered array of 100 items, how many values must linear search examine on average?

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

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

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

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.

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.

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.

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

A binary search requires that the elements be in order.

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

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

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?

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

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

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

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.

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

Sorted data can be ordered

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

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?

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?

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

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

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.

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.

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

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.