Chapter 9 Test 1 PDF

Starting Out with C++: Early Objects, 10th ed. (Gaddis, Walters, and Muganda) Chapter 9 Searching, Sorting, & Algorithm Analysis Chapter 9 Test 1 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 Ans...

Starting Out with C++: Early Objects, 10th ed. (Gaddis, Walters, and Muganda) Chapter 9 Searching, Sorting, & Algorithm Analysis Chapter 9 Test 1 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: E 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: C 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: D 4) True/False: Using a linear search, you are more likely to find an item than if you use a binary search. Answer: FALSE 5) A binary search begins by examining the ________ element of an array. A) first B) last C) largest D) middle E) smallest Answer: D 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. 1 Copyright © 2020 Pearson Education, Inc. Answer: A 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: FALSE 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: E 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: E 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: B 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: C 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: D 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: A 2 Copyright © 2020 Pearson Education, Inc. 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: C 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: A 16) True/False: When sorting an array of objects or structures, one must decide which data item to sort on. Answer: TRUE 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: C 18) True/False: Bubble sort and selection sort can also be used with STL vectors. Answer: TRUE 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: C 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 than Algorithm B. Answer: FALSE 3 Copyright © 2020 Pearson Education, Inc. Chapter 9 Test 2 1) A ________ search uses a loop to sequentially step through an array. A) binary B) unary C) linear D) relative E) bubble Answer: C 2) True/False: A binary search requires that the elements be in order. Answer: TRUE 3) The ________ search is adequate for searching through small arrays, but not through large ones. A) binary B) linear C) selection D) bubble E) random Answer: B 4) True/False: Using a binary search, you are more likely to find an item than if you use a linear search. Answer: FALSE 5) If a binary search is used to search for the number 4 in the 11-element array shown here int A[] = {1, 2, 3, 4, 6, 7, 8, 9, 10, 12, 17}; which value will the 4 be compared to first? A) 1 B) 7 C) 8 D) 9 E) 17 Answer: B 6) To determine that a value is not present in an unordered array of 50 items, how many values must linear search examine on average? A) 1 B) 6 C) 25 D) 50 E) 51 Answer: D 7) To find a value that is in an unordered array of 50 items, how many values must linear search examine on average? A) 1 B) 6 C) 25 D) 50 E) 51 Answer: C 8) To find a value in an ordered array of 50 items, how many values must binary search examine at most. A) 1 B) 6 C) 10 D) 25 E) 50 Answer: B 4 Copyright © 2020 Pearson Education, Inc. 9) True/False: When searching for a particular object in an array of objects, it is necessary to compare the search key to the value in each examined object's key field. Answer: TRUE 10) A(n) ________ algorithm arranges data into some order. A) sorting B) searching C) ordering D) linear E) binary Answer: A 11) Sorted data can be ordered A) from lowest to highest value. B) from highest to lowest value. C) using a bubble sort algorithm. D) using a selection sort algorithm. E) in all of the above ways. Answer: E 12) True/False: When an array is sorted from highest to lowest, it is said to be in ascending order. Answer: FALSE 13) If a bubble sort is used to arrange the numbers 8 6 4 9 3 7 in ascending order, what order will the data be in after the first pass of the sort is completed? A) 3 4 6 7 8 9 B) 3 6 4 9 8 7 C) 6 4 8 3 7 9 D) 6 8 4 9 3 7 E) None of the above Answer: C 14) If a selection sort is used to arrange the numbers 8 6 4 9 3 7 in ascending order, what order will the data be in after the first pass of the sort is completed? A) 3 4 6 7 8 9 B) 3 6 4 9 8 7 C) 6 4 8 3 7 9 D) 6 8 4 9 3 7 E) None of the above Answer: B 15) The ________ sort usually performs more exchanges than the ________ sort. A) bubble, selection B) selection, bubble C) binary, linear D) linear, binary E) linear, bubble Answer: A 5 Copyright © 2020 Pearson Education, Inc. 16) Selection sort requires ________ passes to put n data items in order. A) n B) n / 2 C) n / 2 + 1 D) n - 1 E) n + 1 Answer: D 17) True/False: When sorting an array of objects, if the values in the data member being sorted on are out of order for two objects, those two data values should be swapped. Answer: FALSE 18) True/False: Any sorting algorithm, such as bubble sort or selection sort, that can be used on data stored in an array can also be used on data stored in a vector. Answer: TRUE 19) We can estimate the ________ of an algorithm by counting the number of basic steps it requires to solve a problem. A) number of lines of code B) efficiency C) run time D) code quality E) result Answer: B 20) 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, algorithms A and B are considered to be equally efficient. Answer: TRUE 6 Copyright © 2020 Pearson Education, Inc.