Chapter 16

Question 1

True or false:
All of the values in a list have the same type.

Answer 1

True

Question 2

True or false:
The size of a list is fixed and cannot be increased or decreased.

Answer 2

False

Question 3

True or false:
The sequential search algorithm does not assume that the list is sorted.

Answer 3

True

Question 4

True or false:
In a bubble sort, the smaller elements move towards the bottom, and the larger elements move toward the top of the list.

Answer 4

False

Question 5

True or false:
The bubble sort makes fewer item assignments than comparisons.

Answer 5

True

Question 6

True or false:
The performance of bubble sort can be improved if we stop the sorting process as soon as we find than, in an iteration, no swapping of elements takes place.

Answer 6

True

Question 7

True or false:
The insertion sort algorithm sorts the list by moving each element into its proper place.

Answer 7

True

Question 8

True or false:
During the sorting phase of insertion sort, the array containing the list is divided into two sublists, sorted and unsorted.

Answer 8

True

Question 9

True or false:
Assume that n = 1000. To sort the list, insertion sort makes about 250,000 item assignments.

Answer 9

True

Question 10

True or false:
A sequential search is much faster than a binary search.

Answer 10

False

Question 11

The sequential search algorithm uses a(n) _______ variable to track whether the item is found.

Answer 11

bool

Question 12

If the search item is the 900th item in the list, the sequential search makes _______ key comparisons to determine whether the search item is on the list

Answer 12

900

Question 13

In a sequential search, if a search item is not in a list of 1000 elements, then ______ key comparisons will be made.

Answer 13

1000

Question 14

For sorting a list of length n, a bubble sort uses ______ iterations.

Answer 14

n - 1

Question 15

In a bubble sort for list of length n, the first step is to compare elements ________.

Answer 15

list[0] and list[n - 1]

Question 16

After the second iteration of a bubble sort for a list of length n, the last _______ are sorted.

Answer 16

two elements

Question 17

In the bubble sort algorithm, which code accomplishes swapping values in elements at positions index and index + 1?

Answer 17

temp = list[index];
list[index] = list[index + 1];
list[index + 1] = temp;

Question 18

For a list of length n, the bubble sort makes exactly _____ key comparisons

Answer 18

n(n - 1) / 2

Question 19

Assume that n = 1000. To sort the list, a bubble sort makes about ____ item comparisons.

Answer 19

250,000

Question 20

When moving array values for insertion sort, to move list[4] into list[2], first ______.

Answer 20

copy list[4] into temp

Question 21

In the insertion sort function, the variable firstOutOfOrder is initialized to _______, assuming n is the length of the list.

Answer 21

1

Question 22

For a list of length n, insertion sort makes _____ item assignments.

Answer 22

n(n - 1) /4

Question 23

Sequential search typically searches _______.

Answer 23

one half of the list

Question 24

Consider the following list:
int list[] = {4, 8, 19, 25, 34, 39, 45, 48, 66, 75, 89, 95}
When performing a binary search, the element to be found is first compared with _______.

Answer 24

39

Question 25

nt list[] = {4, 8, 19, 25, 34, 39, 45, 48, 66, 75, 89, 95}
When performing a binary search for75, after the first comparison, the search is restricted to _______.

Answer 25

list[6] … list[11]

Question 26

The formula to find the index of the middle element of a list is ______.

Answer 26

(first + last) / 2

Question 27

With the binary search algorithm, _______ key comparison(s) is/are made in the successful case - the last time through the loop.

Answer 27

one

Question 28

The statement _____ creates the vector object vecList of size size.

Answer 28

vector<elemType> vecList(size);</elemType>

Question 29

A variable declared using the vector type is called a ________.

Answer 29

vector container

Question 30

The statement _____ returns the element at the positon index in the vector vecList.

Answer 30

vecList[index]

Question 31

Which statement declares intList to be an empty vector?

Answer 31

vector<int> intList;</int>

Question 32

Which statement declares intList to be a vector of size 5 and the element to be of type int?

Answer 32

vector<int> intList(5);</int>

Question 33

The code below represents the _____ search algorithm.
int unknownSearch(const int list[], int listLength, int searchItem){
int loc;
bool found = false;
loc = 0;
while(loc < listLength && !found)
if(list[loc] == searchItem)
found = true;
else
loc++;
if(found)
return loc;
else
return - 1;
}

Answer 33

sequential

Question 34

For a list size of 1000, on average, the sequential search makes about ________ key comparisons.

Answer 34

500

Question 35

A(n) _________ search uses the “divide and conquer” technique to search the list.

Answer 35

binary

Question 36

In order to apply a(n) _________ search, the list must be sorted.

Answer 36

binary

Question 37

The type vector provides the function ________, which returns the first element in the vector object.

Answer 37

front()

Question 38

The type vector provides the function ___________, which deletes all elements from the object.

Answer 38

clear()

Question 39

The type vector provides the expression _________, which returns the last element of the object.

Answer 39

back()

Question 40

The type vector provides the expression _________, which inserts a copy of elem into vecList at the end.

Answer 40

push_back(elem)

Question 41

The type vector provides the expression _________, which deletes the last element of vecList.

Answer 41

pop_back()

Question 42

The type vector provides the expression _________, which returns true if the object vecList is empty and false otherwise.

Answer 42

empty()

Question 43

The type vector provides the expression _________, which returns the maximum number of elements that can be inserted into the object vecList.

Answer 43

max_size()

Question 44

If you initially declare a vector object and do not specify its size, then in order to add elements to the vector object, we use the function ________.

Answer 44

push_back(elem)

Question 45

The first element in a vector object is at location ____.

Answer 45

0

Question 46

If you want to use the class vector in your program you must include the following statement:

Answer 46

include <vector></vector>