Question 1

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

Accepted Answer

Binary search works only on ordered sets of data (either in ascending or descending order) and can find the item more quickly than linear search. However, when searching for an item in an unordered set of data, binary search cannot guarantee that the item will be found more quickly than linear search. In fact, in some cases, linear search may be faster because it does not require the data to be sorted beforehand.

Question 2

A binary search begins by examining the ________ element of an array.
A) first
B) last
C) largest
D) middle
E) smallest

Accepted Answer

Binary search operates on a sorted array by repeatedly dividing the search interval in half, the starting point of time complexity analysis. If the value of the search key is less than the item in the middle of the interval, narrow the search to the lower half. Otherwise, if the search key is greater than or equal to the middle item, narrow the search to the upper half.

Question 3

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?
A) 2 5 3 9 7 6
B) 5 7 3 9 2 6
C) 5 3 7 2 6 9
D) 2 3 5 6 7 9
E) none of the above

Accepted Answer

C

Question 4

To find a value that is in an unordered array of 100 items, how many values must linear search examine on average?
A) 7
B) 10
C) 50
D) 100
E) 101

Accepted Answer

In linear search, we examine each element of the array until we find the value we are looking for. Therefore, in the worst case scenario, we might have to examine all the 100 elements of the array. 
However, since the array is unordered, the value we are looking for could be located anywhere within the array with equal probability. Therefore, on average, we only need to examine half of the array, which is 50 elements. Thus, the answer is C.

Question 5

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

Accepted Answer

Using a binary search, the time complexity is O(log n), whereas using a linear search, the time complexity is O(n), which means the binary search is faster and more likely to find an item.

Question 6

The advantage of a linear search is that
A) it is simple.
B) it is efficient.
C) it is fast.
D) it can be used on unordered data.
E) both A and D

Accepted Answer

Linear search is simple to implement and can be used on unordered data, making it advantageous when dealing with unsorted datasets. Efficiency and speed are not its strong suits, especially compared to other search algorithms for large datasets.

Question 7

A(n) ________ search is more efficient than a(n) ________ search.
A) string, double
B) integer, double
C) binary, linear
D) linear, binary
E) None of the above. All searches are equally efficient.

Accepted Answer

Binary search is a more efficient search than linear search for sorted arrays or lists. This is because binary search operates by halving the search space with each comparison, while linear search must check each element in turn. Therefore, as the size of the dataset increases, the time taken for binary search to find the desired element will increase logarithmically, whereas with linear search it will increase linearly. Therefore, binary search is a better choice when dealing with large datasets.

Question 8

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, algorithm A is considered to be more efficient than Algorithm B.

Accepted Answer

Algorithm A requires 2n + 1 basic operations, while Algorithm B requires 3n + 2 basic operations. For large values of n, 3n + 2 will be greater than 2n + 1, making Algorithm B less efficient than Algorithm A.

Question 9

The ________ sort usually performs fewer exchanges than the ________ sort.
A) bubble, selection
B) selection, bubble
C) binary, linear
D) linear, binary
E) linear, bubble

Accepted Answer

The selection sort performs fewer exchanges than the bubble sort. In the bubble sort, each pair of adjacent elements is compared, and if they are in the wrong order, they are swapped. This process is repeated until the list is sorted. The selection sort, on the other hand, finds the smallest element in the unsorted portion of the list and swaps it with the first element. This process is repeated until the entire list is sorted. Therefore, the selection sort performs fewer exchanges than the bubble sort, making option B the correct choice.

Question 10

A sorting algorithm can be used to arrange a set of ________ in ________ order.
A) numeric values, ascending
B) numeric values, descending
C) strings, ascending
D) strings, descending
E) All of the above.

Accepted Answer

A sorting algorithm can be used to arrange both numeric values and strings in either ascending or descending order, so all of the choices are correct.

Question 11

To determine that an item is not in an unordered array of 100 items, how many values must linear search examine on average?
A) 7
B) 10
C) 50
D) 100
E) 101

Accepted Answer

The answer of To determine that an item is not...

Question 12

Bubble sort and selection sort can also be used with STL vectors.

Accepted Answer

Both bubble sort and selection sort can be implemented with STL vectors in C++ programming language.

Question 13

When sorting an array of objects or structures, one must decide which data item to sort on.

Accepted Answer

When sorting an array of objects or structures, one must decide which data item to sort on. This is because different data items may have different values and priorities, and sorting on one item may result in a different order than sorting on another item. Therefore, the sorting algorithm needs to know which data item to compare and use as the basis for sorting.

Question 14

We can measure the complexity of an algorithm that solves a computational problem by determining the number of ________ for an input of size n.
A) output statements it has
B) times it loops
C) basic steps it requires
D) variables it uses
E) operations it performs

Accepted Answer

The complexity of an algorithm is typically measured by the number of basic steps it requires, which often correlates with the number of operations it performs.

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, it is necessary to
A) examine a different data member.
B) swap these two data values.
C) swap the entire two objects.
D) swap one-by-one all data members in the two objects.
E) stop the sort.

Accepted Answer

Swapping the entire two objects ensures that the array remains consistent with the sorted order based on the specific data member. Swapping only the data values or individual data members could disrupt the integrity of the objects.

Question 16

The linear search is adequate for searching through ________ arrays, but not through ________ ones.
A) int, double
B) char, string
C) ascending, descending
D) small, large
E) any regular, vector

Accepted Answer

The linear search algorithm has a time complexity of O(n), meaning it searches through every element in the array until it finds the desired value. This makes it suitable for small arrays, but as the array size grows the search time becomes impractical, which is why larger arrays are better searched using more efficient algorithms like binary search. Therefore, the linear search algorithm is adequate for searching through small arrays but not through large ones.

Question 17

To find a value in an ordered array of 100 items, how many values must binary search examine at most?
A) 7
B) 10
C) 50
D) 100
E) 101

Accepted Answer

Binary search examines at most log2(100) = 6.64 values. Since it must examine an integer number of values, the answer is 7.

Question 18

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
A) array index first > array index last.
B) Boolean variable found equals false.
C) Boolean variable found equals True.
D) it finds a value larger than the search key.
E) it has examined all the elements in the array.

Accepted Answer

Binary search uses the principle of divide and conquer to search for an item in an array. If the item being searched for is not in the array, the search ends when the upper index (array index last) becomes less than the lower index (array index first). This means that the search has narrowed down to a subarray with zero elements, indicating that the item is not in the array. Therefore, option A is the correct choice.

Question 19

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?
A) 2 5 3 9 7 6
B) 5 7 3 9 2 6
C) 5 3 7 2 6 9
D) 2 3 5 6 7 9
E) none of the above

Accepted Answer

In the first pass of selection sort, the smallest element (2) is found and swapped with the first element (7), resulting in the order 2 5 3 9 7 6.

Question 20

A search can be performed on an array of
A) integers.
B) strings.
C) objects.
D) all of the above, but only if the data is in order.
E) all of the above whether the data is in order or not.

Accepted Answer

A search can be performed on an array of integers, strings, or objects regardless of whether the data is in order or not. The algorithm used for the search may be different depending on the type of data and its organization within the array, but the search itself is still possible.

Quiz 9: Searching, Sorting, Algorithm Analysis

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

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

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?

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

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

The advantage of a linear search is that

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

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, algorithm A is considered to be more efficient than Algorithm B.

The sort usually performs fewer exchanges than the sort.

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

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

Bubble sort and selection sort can also be used with STL vectors.

When sorting an array of objects or structures, one must decide which data item to sort on.

We can measure the complexity of an algorithm that solves a computational problem by determining the number of ________ for an input of size n.

When sorting an array of objects, if the values in the data member being sorted on are out of order for two objects, it is necessary to

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

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

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

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?

A search can be performed on an array of