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)
  2. A:mathematic
  3. B:asymptotic
  4. C:circular
  5. D:rhythmic
  6. 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)
  7. A:name
  8. B:field
  9. C:key
  10. D:ID
  11. 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)
  12. A:[7, 10, 19, 5, 16]
  13. B:[16, 7, 5, 10, 19]
  14. C:[7, 5, 10, 16, 19]
  15. D:[7, 10, 5, 16, 19]
  16. The selection sort algorithm sorts a list by ____. (p.1208)
  17. A:partitioning the list into two sorted lists
  18. B:partitioning the list into two lists that are approximately the same size
  19. C:moving each element to its proper place in the sorted portion of the list
  20. D:None of the above
  21. 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)
  22. A:1
  23. B:2
  24. C:3
  25. D:n - 2, where n is the number of items in the list
  26. The binary search algorithm ____. (p.1189)
  27. A:restricts the search to half of the list each time through the loop
  28. B:can be written iteratively or recursively
  29. C:is efficient for large lists
  30. D:all of the above
  31. 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)
  32. A:O(1)
  33. B:O(log2n)
  34. C:O(n)
  35. D:O(n2)
  36. In a comparison tree, the ____ represents the final ordering of the nodes. (p.1217)
  37. A:leaf
  38. B:root
  39. C:branch
  40. D:binary tree
  41. 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)
  42. A:11
  43. B:45
  44. C:58
  45. D:98
  46. A binary tree is a comparison tree in which ____. (p.1217)
  47. A:each comparison has two outcomes
  48. B:each comparison can have one or more outcomes
  49. C:some comparisons may have zero outcomes
  50. D:some paths do not lead to leaf nodes
  51. 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)
  52. A:largest
  53. B:smallest
  54. C:empty
  55. D:None of the above
  56. 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)
  57. A:35, 28, 18, 45
  58. B:35, 28, 18, 38
  59. C:18, 45, 62, 48
  60. D:62, 48, 60, 38
  61. 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)
  62. A:they contribute significantly to performance
  63. B:these operations are not dominant operations
  64. C:they do not significantly impact the algorithm's performance
  65. D:both b and c
  66. In the insertion sort algorithm on array-based lists, the firstOutOfOrder index is typically initialized to ____. (p.1215)
  67. A:0
  68. B:1
  69. C:n - 1, where n is the number of items in the list
  70. D:n, where n is the number of items in the list
  71. The sequential search is also called a _____. (p.1185)
  72. A:linear search
  73. B:circular search
  74. C:single search
  75. D:selective search
  76. Sequential and binary search algorithms are called ____-based search algorithms. (p.1202)
  77. A:code
  78. B:comparison
  79. C:analytical
  80. D:integer
  81. Which of the following best describes when the sorting work is done in the merge sort algorithm? (p.1226)
  82. A:when the list is partitioned into the first sublist and the second sublist
  83. B:when the first sublist and the second sublist are merged
  84. C:when swaps are performed
  85. D:when the data are input
  86. In the bubble sort, if the list is already sorted, how many assignments are performed? (p.1207)
  87. A:0
  88. B:1
  89. C:2
  90. D:n
  91. 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)
  92. A:17
  93. B:52
  94. C:88
  95. D:98
  96. 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)
  97. A:[7, 10, 19, 5, 16]
  98. B:[10, 7, 5, 16, 19]
  99. C:[19, 10, 7, 5, 16]
  100. D:[7, 10, 5, 16, 19]
  1. A binary search ____. (p.1187)
  2. A:can be performed on an unsorted list
  3. B:requires that the list be sorted
  4. C:sorts the elements in the list prior to searching the list
  5. D:is usually less efficient than a sequential search
  6. In a sequential search, the search item is called the ____. (p.1187)
  7. A:value
  8. B:target
  9. C:node
  10. D:None of the above
  11. In the best case for the insertion sort, the list is ____. (p.1216)
  12. A:already sorted
  13. B:not sorted
  14. C:sorted in reverse order
  15. D:partially sorted
  16. Let f be a function of n. Asymptotic means the study of the function f as n ____. (p.1198)
  17. A:varies from input file to input file
  18. B:varies with the number of coding statements in the program
  19. C:becomes larger and larger without bound
  20. D:remains constant
  21. Using the binary search algorithm, in a successful search, how many comparisons are performed during the last iteration of the loop? (p.1189)
  22. A:0
  23. B:1
  24. C:2
  25. 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)
  27. A:slower than
  28. B:faster than
  29. C:constant compared to
  30. D:about the same as
  31. 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)
  32. A:0
  33. B:7
  34. C:8
  35. D:9
  36. For the bubble sort, the total number of comparisons is O(____). (p.1206)
  37. A:n
  38. B:n2
  39. C:log2n
  40. D:nlog2n
  41. The average number of comparisons for the merge sort algorithm is O(____). (p.1234)
  42. A:n
  43. B:n2
  44. C:log2n
  45. D:nlog2n
  46. 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)
  47. A:25
  48. B:50
  49. C:60
  50. D:94
  51. 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)
  52. A:16
  53. B:24
  54. C:25
  55. D:50
  56. The performance of the selection sort algorithm ____. (p.1212)
  57. A:depends on the initial arrangement of the data
  58. B:is always O(n2) for the # of comparisons
  59. C:is O(n) for the number of assignments
  60. D:all of the above
  1. 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)
  2. A:0
  3. B:1
  4. C:3
  5. D:8
  6. On average, the sequential search algorithm makes how many comparisons? (p.1187)
  7. A:n/3
  8. B:n
  9. C:n2
  10. D:(n+1)/2
  11. In the binary search algorithm, in a successful search, the last time through the loop ____ key comparison(s) are made. (p.1189)
  12. A:0
  13. B:1
  14. C:2
  15. D:3
  16. The average case for the quick sort algorithm is O(____). (p.1225)
  17. A:n
  18. B:n2
  19. C:log2n
  20. D:nlog2n
  21. The merge sort algorithm is always O(____). (p.1234)
  22. A:O(1)
  23. B:O(n)
  24. C:O(log2n)
  25. D:O(nlog2n)
  26. The first key comparison preformed during the binary search algorithm is on the ____ item of the list. (p.1187)
  27. A:first
  28. B:second
  29. C:last
  30. D:None of the above
  31. The sequential search algorithm stops iterating when ____. (p.1185|1186)
  32. A:the target item has been found
  33. B:the entire list was searched unsuccessfully, that is, the item was not found
  34. C:the first item less than the target is found
  35. D:both a and b
  36. The _____ search algorithm uses the ‘‘divide and conquer'' technique to search the list. (p.1187)
  37. A:sequential
  38. B:linear
  39. C:binary
  40. 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)
  42. A:0
  43. B:1
  44. C:2
  45. D:n, where n is the number of items in the list
  1. 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)
  2. A:have array indices larger than the index for the pivot element
  3. B:have a value greater than 47
  4. C:are greater than or equal to the pivot element
  5. D:have indices between 6 and 12
  6. The number of key comparisons refers to ____. (p.1185)
  7. A:the number of times the key of the search item is compared with the keys of the items in the list
  8. B:the number of swaps (or exchanges) that occur during execution
  9. C:the number of items in the list
  10. D:the number of temp variables
  1. The selection sort algorithm is good for ____. (p.1212)
  2. A:small lists
  3. B:medium size lists
  4. C:large lists
  5. D:lists of any size
  1. The ____ search algorithm is an optimal worst-case algorithm for solving search problems by the comparison method. (p.1202)
  2. A:sequential
  3. B:unary
  4. C:binary
  5. D:None of the above
  6. The ____ search algorithm sorts the elements in the list prior to searching the list. (p.1187)
  7. A:quadratic
  8. B:linear
  9. C:binary
  10. D:None of the above
  1. Which of the following best describes when the sorting work is done in the quick sort algorithm? (p.1218)
  2. A:when the list is partitioned into the lowerSublist and the upperSublist
  3. B:when the lowerSublist and the upperSublist are combined
  4. C:when swaps are performed
  5. D:when the data are input
  6. The worst case for the quick sort algorithm is O(____). (p.1225)
  7. A:n
  8. B:n2
  9. C:log2n
  10. D:nlog2n
  11. Which of the following is true about the quick sort and the merge sort algorithms? (p.1225)
  12. A:both algorithms partition the list in the same way
  13. B:the algorithms both partition the list but do not partition the list in the same way
  14. C:the merge sort partitions the list, but the quick sort does not
  15. D:the quick sort partitions the list, but the merge sort does not