Deck 16: Searching, Sorting and the Vector Type

Question 1

The sequential search algorithm does not assume that the list is sorted.

Answer 1

True

Question 2

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

A) list[index] = list[index + 1]
List[index + 1] = list[index]
B) list[index + 1] = list[index]
List[index] = list[index + 1]
C) list[index] = temp;
List[index] = list[index + 1];
Temp = list[index + 1];
D) temp = list[index];
List[index] = list[index + 1];
List[index + 1] = temp;

Answer 2

D

Question 3

A sequential search is much faster than a binary search.

Answer 3

False

Question 4

All of the values in a list have the same type.

Question 5

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

A) int
B) bool
C) char
D) double

Question 6

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

Question 7

In a bubble sort, the smaller elements move toward the bottom, and the larger elements move toward the top of the list.

Question 8

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

Question 9

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

A) n(n-1)/2
B) n(n-1)/3
C) n(n-1)/4
D) (n-1)/2

Question 10

Assuming that list consists of the following elements, what is the result after bubble sort completes? int list[] = {2, 56, 34, 25, 73, 46, 89, 10, 5, 16};

A) 89 73 56 46 34 25 16 10 5 2
B) 2 56 34 25 5 16 89 46 73
C) 2 5 10 16 25 34 46 56 73 89
D) 2 10 16 25 34 46 56 73 89

Question 11

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

A) 1
B) n - 1
C) n
D) n + 1

Question 12

____ is one of the basic operations that may be performed on a list.

A) Searching the list
B) Reversing the order of the elements
C) Finding the maximum element
D) Displaying the elements

Question 13

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

Question 14

The insertion sort algorithm sorts the list by moving each element to its proper place.

Question 15

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

A) 100
B) 1000
C) 10,000
D) 100,000

Question 16

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

A) list[0] and list[n]
B) list[0] and list[n-1]
C) list[0] and list[1]
D) list[n-1] and list[n+1]

Question 17

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

A) 100
B) 900
C) 9000
D) 90,000

Question 18

The bubble sort makes fewer item assignments than comparisons with a list of 1000 elements.

Question 19

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

A) element
B) two elements
C) three elements
D) n-2

Question 20

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

Question 21

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

A) 10,000
B) 100,000
C) 250,000
D) 500,000

Question 22

The statement ____ returns the element at the position index in vector vecList.

A) vecList[index]
B) vecList.get(index)
C) vecList.front(index)
D) vecList

Question 23

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

A) vector intList[5];
B) vector intList(5);
C) vector intList();
D) vector(int) intList[5];

Question 24

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

Question 25

A(n) ____________________ search uses the "divide and conquer" technique to search the list.

Question 26

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

A) vector element
B) vector array
C) vector list
D) vector container

Question 27

Which of the following statements declares intList to be an empty vector?

A) vector intList();
B) vector intList(0);
C) vector intList(10);
D) vector intList;

Question 28

The statement vector____________________; creates the vector object vecList of size n.

Question 29

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

Question 30

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

A) one
B) two
C) n-2
D) n

Question 31

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

A) list[0]...list[6]
B) list[0]...list[7]
C) list[5]...list[11]
D) list[6]...list[11]

Question 32

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 ____.

A) 4
B) 25
C) 39
D) 95

Question 33

Sequential search typically searches ____.

A) one quarter of the list
B) one third of the list
C) one half of the list
D) the entire list

Question 34

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

A) n(n-1)/4
B) n(n-1)/2
C) n2
D) n3

Question 35

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

A) vector[elemType] vecList(size);
B) vector vecList(size);
C) vector(size) vecList
D) vector{ele

Question 36

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;
}

Question 37

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

A) (mid + last)/2
B) (first + last) - 2
C) (first + last) / 2
D) (first + mid ) * 2

Question 38

Which of the following statements declares intList to be a vector object of size 10?

A) vector intList();
B) vector intList(0);
C) vector intList(10);
D) vector intList;

Question 39

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

A) move list[2] to list[3]
B) delete list[2]
C) move list[4] to list[3]
D) copy list[4] into temp

Question 40

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

A) 0
B) 1
C) n - 1
D) n

Question 41

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

Question 42

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

Question 43

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

Question 44

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

Question 45

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

Question 46

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

Question 47

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

Question 48

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

Question 49

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

Question 50

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 ____________________.