Deck 16: Searching and Sorting

Question 1

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

Answer 1

B

Question 2

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

Answer 2

C

Question 3

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 3

D

Question 4

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

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

A sequential search is much faster than a binary search.

Question 7

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 8

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 9

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

Question 10

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 11

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

Question 12

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

Question 13

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 14

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

Question 15

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

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

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

Question 18

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

Question 19

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

Question 20

The bubble sort makes fewer item assignments than comparisons.

Question 21

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 22

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 23

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 24

Which statement 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 25

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

Question 26

The code shown represents the ____________________ search algorithm.

Question 27

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 28

Which statement declares intList to be an empty vector?

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

Question 29

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 30

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

Question 31

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

Question 32

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

Question 33

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 34

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 35

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

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

Question 36

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 37

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

Question 38

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

Question 39

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

Question 40

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

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

Question 41

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

Question 42

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

Question 43

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

Question 44

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

Question 45

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

Question 46

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