Deck 9: Searching, Sorting, Algorithm Analysis

Question 1

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

Answer 1

False

Question 2

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

A) first
B) last
C) largest
D) middle
E) smallest

Answer 2

D

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

Answer 3

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

Question 5

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

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

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.

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.

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

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.

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

Question 12

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

Question 13

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

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

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.

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

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

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.

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

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.

Question 21

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.

Question 22

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

A) bubble, selection
B) selection, bubble
C) binary, linear
D) linear, binary
E) linear, bubble

Question 23

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

A) sorting
B) searching
C) ordering
D) linear
E) binary

Question 24

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

A) 1
B) 6
C) 25
D) 50
E) 51

Question 25

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.

Question 26

Sorted data can be ordered

A) from lowest to highest value.
B) from highest to lowest value.
C) using a bubble sort algorithm.
D) using a selection sort algorithm.
E) in all of the above ways.

Question 27

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

A) binary
B) unary
C) linear
D) relative
E) bubble

Question 28

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?

A) 3 4 6 7 8 9
B) 3 6 4 9 8 7
C) 6 4 8 3 7 9
D) 6 8 4 9 3 7
E) None of the above

Question 29

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

Question 30

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

A) binary
B) linear
C) selection
D) bubble
E) random

Question 31

A binary search requires that the elements be in order.

Question 32

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?

A) 1
B) 7
C) 8
D) 9
E) 17

Question 33

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?

A) 3 4 6 7 8 9
B) 3 6 4 9 8 7
C) 6 4 8 3 7 9
D) 6 8 4 9 3 7
E) None of the above

Question 34

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

A) number of lines of code
B) efficiency
C) run time
D) code quality
E) result

Question 35

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.

Question 36

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

A) 1
B) 6
C) 10
D) 25
E) 50

Question 37

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

Question 38

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

A) n
B) n / 2
C) n / 2 + 1
D) n - 1
E) n + 1

Question 39

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

A) 1
B) 6
C) 25
D) 50
E) 51

Question 40

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.