Deck 9: Searching, Sorting, and Algorithm Analysis

Question 1

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

A)char, string
B)any regular, vector
C)int, double
D)ascending, descending
E)small, large

Answer 1

E

Question 2

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

A)numeric values, ascending
B)strings, ascending
C)strings, descending
D)numeric values, descending
E)All of the above.

Answer 2

E

Question 3

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

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

Answer 3

D

Question 4

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

A)ascending
B)forward
C)downward
D)reverse
E)descending

Question 5

If a binary search is used to search for the number 4 in the 11- element array shown below, which value will the 4 be compared to first?

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

Question 6

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

Question 7

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

A)integer, double
B)string, double
C)binary, linear
D)linear, binary
E)None of the above. All searches are equally efficient.

Question 8

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

Question 9

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

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

Question 10

To locate a value that is in an ordered array of 50 items, linear search must examine at most values.

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

Question 11

A(n)algorithm arranges data into some order.

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

Question 12

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)times it loops
B)basic steps it requires
C)operations it performs
D)variables it uses
E)output statements it has

Question 13

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 14

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

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

Question 15

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

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

Question 16

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

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

Question 17

Sorted data can be ordered

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

Question 18

A search can be performed on an array of

A)strings.
B)integers.
C)objects.
D)all of the above.
E)A and B, but not C.

Question 19

The sort usually performs fewer exchanges than the sort.

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

Question 20

The sort usually performs more exchanges than the sort.

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

Question 21

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

Question 22

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

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

Question 23

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 24

To determine that a item is not in an unordered array of 100 items, linear search must examine an average of values.

A)7
B)10
C)50
D)100
E)101

Question 25

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

Question 26

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 27

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

Question 28

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

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

Question 29

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

A)7
B)10
C)50
D)100
E)101

Question 30

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

A)key field, search key.
B)search key, public member data.
C)key field, public member data.
D)search key, private member data.
E)search key, key field.

Question 31

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.

Question 32

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 33

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

Question 34

To locate a value in an ordered array of 100 items, binary search must examine at most values.

A)7
B)10
C)50
D)100
E)101

Question 35

A binary search requires that the elements be in order.

Question 36

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