Chapter 8

Question 1

1. Why is the linear search also called “sequential search”?

Answer 1

Because it uses a loop to sequentially step through an array, starting with the first
element. It compares each element with the value being searched for, and stops
when either the value is found or the end of the array is encountered

Question 2

If a linear search function is searching for a value that is stored in the last element of a 10,000-
element array, how many elements will the search code have to read to locate the value?

Answer 2

It will have to read all 10,000 elements of the array.

Question 3

In an average case involving an array of N elements, how many times will a linear search
function have to read the array to locate a specific value?

Answer 3

N/2 times

Question 4

A binary search function is searching for a value that is stored in the middle element of an
array. How many times will the function read an element in the array before finding the value?

Answer 4

One time.

Question 5

What is the maximum number of comparisons that a binary search function will make when
searching for a value in a 1,000-element array?

Answer 5

Ten

Question 6

6. Why is the bubble sort inefficient for large arrays?

Answer 6

Because it moves the items in the array only by one element at a time.

Question 7

7. Why is the selection sort more efficient than the bubble sort on large arrays?

Answer 7

The selection sort usually performs fewer exchanges because it moves items
immediately to their final position in the array.

Question 8

The _________ search algorithm steps sequentially through an array, comparing each item
with the search value

Answer 8

linear (or sequential)

Question 9

The _________ search algorithm repeatedly divides the portion of an array being searched in
half

Answer 9

binary

Question 10

10. The _________ search algorithm is adequate for small arrays but not large arrays.

Answer 10

linear

Question 11

11. The _________ search algorithm requires that the array’s contents be sorted.

Answer 11

binary

Question 12

12. If an array is sorted in _________ order, the values are stored from lowest to highest.

Answer 12

ascending

Question 13

13. If an array is sorted in _________ order, the values are stored from highest to lowest.

Answer 13

descending

Question 14

If data are sorted in ascending order, it means they are ordered from lowest value to
highest value

Answer 14

true

Question 15

If data are sorted in descending order, it means they are ordered from lowest value to
highest value.

Answer 15

false

Question 16

The average number of comparisons performed by the linear search on an array of N
elements is N/2 (assuming the search values are consistently found)

Answer 16

true

Question 17

The maximum number of comparisons performed by the linear search on an array of
N elements is N/2 (assuming the search values are consistently found)

Answer 17

false