Searching, Sorting, and Algorithm Analysis

Starting Out with C++: Early Objects 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. 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 Answer: A C) 50 D) 100 E) 101 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 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 Answer: B C) 10 D) 25 E) 50