Chapter 9

Question 1

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

Answer 1

(E)

Question 2

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

Answer 2

(C)

Question 3

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

Answer 3

(D)

Question 4

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

Answer 4

False

Question 5

A binary search begins by examining the ________ element of an array.
A) First
B) Last
C) Largest
D) Middle
E) Smallest

Answer 5

(D)

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) 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

Answer 6

(A)

Question 7

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

Answer 7

False

Question 8

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

Answer 8

(E)

Question 9

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

Answer 9

(E)

Question 10

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

Answer 10

(B)

Question 11

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

Answer 11

(C)

Question 12

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

Answer 12

(D)

Question 13

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

Answer 13

(A)

Question 14

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 14

(C)

Question 15

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

Answer 15

(A)

Question 16

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

Answer 16

True

Question 17

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

Answer 17

(C)

Question 18

True/False: Bubble sort and selection sort can also be used with STL vectors.

Answer 18

True

Question 19

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

Answer 19

(C)

Question 20

True/False: 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 that Algorithm B.

Answer 20

False