Chapter 19
Self-Test
Top of Form
1. The term _____ is used to describe the study of the function f as n becomes larger and larger without bound. (p.1198)
1. A:mathematic
2. B:asymptotic
3. C:circular
4. D:rhythmic
2. The special member associated with each item in a data set that uniquely identifies an individual item in the data set is called the ____. (p.1185)
1. A:name
2. B:field
3. C:key
4. D:ID
3. Given the unordered list [10, 7, 19, 5, 16], which of the following sequences represents the result of the second iteration of the bubble sort algorithm? (p.1204)
1. A:[7, 10, 19, 5, 16]
2. B:[16, 7, 5, 10, 19]
3. C:[7, 5, 10, 16, 19]
4. D:[7, 10, 5, 16, 19]
4. The selection sort algorithm sorts a list by ____. (p.1208)
1. A:partitioning the list into two sorted lists
2. B:partitioning the list into two lists that are approximately the same size
3. C:moving each element to its proper place in the sorted portion of the list
4. D:None of the above
5. With the exception of the last time through the loop, the binary search algorithm makes ____ key comparisons each time the loop is executed. (p.1189)
1. A:1
2. B:2
3. C:3
4. D:n - 2, where n is the number of items in the list
6. The binary search algorithm ____. (p.1189)
1. A:restricts the search to half of the list each time through the loop
2. B:can be written iteratively or recursively
3. C:is efficient for large lists
4. D:all of the above
7. Assume a block of code consists of two nested for loops containing an output statement. If the loops each iterate over the same range of indexes, the section of code is ____. (p.1201)
1. A:O(1)
2. B:O(log2n)
3. C:O(n)
4. D:O(n2)
8. In a comparison tree, the ____ represents the final ordering of the nodes. (p.1217)
1. A:leaf
2. B:root
3. C:branch
4. D:binary tree
9. Assume that the quick sort algorithm has been executed a few times on a list. The list now looks like [52, 13, 32, 48, 22, 11, 87, 55, 78, 96, 58, 66, 88, 45]. Which item will be the next item to be moved into a sublist? (p.1221)
1. A:11
2. B:45
3. C:58
4. D:98
10. A binary tree is a comparison tree in which ____. (p.1217)
1. A:each comparison has two outcomes
2. B:each comparison can have one or more outcomes
3. C:some comparisons may have zero outcomes
4. D:some paths do not lead to leaf nodes
11. The selection sort algorithm sorts a list by selecting the ____ element in the unsorted portion of the list and then moving this element to the top of the unsorted list. (p.1208)
1. A:largest
2. B:smallest
3. C:empty
4. D:None of the above
12. Consider the list [35, 28, 18, 45, 62, 48, 30, 38]. Using the merge sort algorithm, after the first partition, which of the following elements are in the first sublist? (p.1225)
1. A:35, 28, 18, 45
2. B:35, 28, 18, 38
3. C:18, 45, 62, 48
4. D:62, 48, 60, 38
13. Which of the following best describes the level of contribution that operations that are only performed once make to an algorithm's performance? (p.1195|1196)
1. A:they contribute significantly to performance
2. B:these operations are not dominant operations
3. C:they do not significantly impact the algorithm's performance
4. D:both b and c
14. In the insertion sort algorithm on array-based lists, the firstOutOfOrder index is typically initialized to ____. (p.1215)
1. A:0
2. B:1
3. C:n - 1, where n is the number of items in the list
4. D:n, where n is the number of items in the list
15. The sequential search is also called a _____. (p.1185)
1. A:linear search
2. B:circular search
3. C:single search
4. D:selective search
16. Sequential and binary search algorithms are called ____-based search algorithms. (p.1202)
1. A:code
2. B:comparison
3. C:analytical
4. D:integer
17. Which of the following best describes when the sorting work is done in the merge sort algorithm? (p.1226)
1. A:when the list is partitioned into the first sublist and the second sublist
2. B:when the first sublist and the second sublist are merged
3. C:when swaps are performed
4. D:when the data are input
18. In the bubble sort, if the list is already sorted, how many assignments are performed? (p.1207)
1. A:0
2. B:1
3. C:2
4. D:n
19. Assume that the quick sort algorithm has been executed a few times on a list. The list now looks like [52, 10, 23, 35, 17, 88, 65, 54, 2, 98, 33]. Which item is the pivot? (p.1220)
1. A:17
2. B:52
3. C:88
4. D:98
20. Given the unordered list [10, 7, 19, 5, 16], which of the following sequences represents the result of the first iteration of the bubble sort algorithm? (p.1203)
1. A:[7, 10, 19, 5, 16]
2. B:[10, 7, 5, 16, 19]
3. C:[19, 10, 7, 5, 16]
4. D:[7, 10, 5, 16, 19]
21. A binary search ____. (p.1187)
1. A:can be performed on an unsorted list
2. B:requires that the list be sorted
3. C:sorts the elements in the list prior to searching the list
4. D:is usually less efficient than a sequential search
22. In a sequential search, the search item is called the ____. (p.1187)
1. A:value
2. B:target
3. C:node
4. D:None of the above
23. In the best case for the insertion sort, the list is ____. (p.1216)
1. A:already sorted
2. B:not sorted
3. C:sorted in reverse order
4. D:partially sorted
24. Let f be a function of n. Asymptotic means the study of the function f as n ____. (p.1198)
1. A:varies from input file to input file
2. B:varies with the number of coding statements in the program
3. C:becomes larger and larger without bound
4. D:remains constant
25. Using the binary search algorithm, in a successful search, how many comparisons are performed during the last iteration of the loop? (p.1189)
1. A:0
2. B:1
3. C:2
4. D:n, where n is the number of items in the list
26. The growth rate of g(n) = nlog2n is ____ g(n) = n. (p.1202)
1. A:slower than
2. B:faster than
3. C:constant compared to
4. D:about the same as
27. Consider the list [63, 45, 32, 98, 46, 57, 28, 100]. Using the sequential search algorithm, how many comparisons are required to determine if the item 90 is in the list? (p.1186)
1. A:0
2. B:7
3. C:8
4. D:9
28. For the bubble sort, the total number of comparisons is O(____). (p.1206)
1. A:n
2. B:n2
3. C:log2n
4. D:nlog2n
29. The average number of comparisons for the merge sort algorithm is O(____). (p.1234)
1. A:n
2. B:n2
3. C:log2n
4. D:nlog2n
30. Consider the list [45, 82, 25, 94, 50, 60, 78, 32, 92]. To begin using the quick sort algorithm, which item would be labeled the pivot? (p.1218)
1. A:25
2. B:50
3. C:60
4. D:94
31. Consider the list [5, 7, 24, 30, 25, 62, 45, 16, 65, 50], which resulted after a few swaps during the selection sort. Which element is the leftmost element in the unsorted part of the list? (p.1209)
1. A:16
2. B:24
3. C:25
4. D:50
32. The performance of the selection sort algorithm ____. (p.1212)
1. A:depends on the initial arrangement of the data
2. B:is always O(n2) for the # of comparisons
3. C:is O(n) for the number of assignments
4. D:all of the above
33. Consider the list [63, 45, 32, 98, 46, 57, 28, 100]. Using the sequential search algorithm, how many comparisons are required to determine if the item 32 is in the list? (p.1186)
1. A:0
2. B:1
3. C:3
4. D:8
34. On average, the sequential search algorithm makes how many comparisons? (p.1187)
1. A:n/3
2. B:n
3. C:n2
4. D:(n+1)/2
35. In the binary search algorithm, in a successful search, the last time through the loop ____ key comparison(s) are made. (p.1189)
1. A:0
2. B:1
3. C:2
4. D:3
36. The average case for the quick sort algorithm is O(____). (p.1225)
1. A:n
2. B:n2
3. C:log2n
4. D:nlog2n
37. The merge sort algorithm is always O(____). (p.1234)
1. A:O(1)
2. B:O(n)
3. C:O(log2n)
4. D:O(nlog2n)
38. The first key comparison preformed during the binary search algorithm is on the ____ item of the list. (p.1187)
1. A:first
2. B:second
3. C:last
4. D:None of the above
39. The sequential search algorithm stops iterating when ____. (p.1185|1186)
1. A:the target item has been found
2. B:the entire list was searched unsuccessfully, that is, the item was not found
3. C:the first item less than the target is found
4. D:both a and b
40. The _____ search algorithm uses the ‘‘divide and conquer'' technique to search the list. (p.1187)
1. A:sequential
2. B:linear
3. C:binary
4. D:division
41. Using the binary search algorithm, in an unsuccessful search, how many key comparisons are performed during the last iteration of the loop? (p.1189)
1. A:0
2. B:1
3. C:2
4. D:n, where n is the number of items in the list
42. The quick sort algorithm partitions a list into an upper sublist and a lower sublist. The upper sublist contains all items in the list that ____. (p.1218)
1. A:have array indices larger than the index for the pivot element
2. B:have a value greater than 47
3. C:are greater than or equal to the pivot element
4. D:have indices between 6 and 12
43. The number of key comparisons refers to ____. (p.1185)
1. A:the number of times the key of the search item is compared with the keys of the items in the list
2. B:the number of swaps (or exchanges) that occur during execution
3. C:the number of items in the list
4. D:the number of temp variables
44. The selection sort algorithm is good for ____. (p.1212)
1. A:small lists
2. B:medium size lists
3. C:large lists
4. D:lists of any size
45. The ____ search algorithm is an optimal worst-case algorithm for solving search problems by the comparison method. (p.1202)
1. A:sequential
2. B:unary
3. C:binary
4. D:None of the above
46. The ____ search algorithm sorts the elements in the list prior to searching the list. (p.1187)
1. A:quadratic
2. B:linear
3. C:binary
4. D:None of the above
47. Which of the following best describes when the sorting work is done in the quick sort algorithm? (p.1218)
1. A:when the list is partitioned into the lowerSublist and the upperSublist
2. B:when the lowerSublist and the upperSublist are combined
3. C:when swaps are performed
4. D:when the data are input
48. The worst case for the quick sort algorithm is O(____). (p.1225)
1. A:n
2. B:n2
3. C:log2n
4. D:nlog2n
49. Which of the following is true about the quick sort and the merge sort algorithms? (p.1225)
1. A:both algorithms partition the list in the same way
2. B:the algorithms both partition the list but do not partition the list in the same way
3. C:the merge sort partitions the list, but the quick sort does not
4. D:the quick sort partitions the list, but the merge sort does not