Consider using radix sort for sorting the following numbers: 477, 744, 447, 774

Question

Consider using radix sort for sorting the following numbers:
477, 744, 447, 774
After the second pass, the order of the numbers is:
(A) 774, 477, 744, 447 (B) 447, 477, 774, 744 (C) 447, 477, 744, 774
(D) 774, 744, 447, 477
(E) 744, 447, 774, 477
(F) the correct order is not listed
18. Let n be the count of numbers in a collection of positive, base10 numbers. Let m be the number of digits in the largest number in the collection. Suppose the auxiliary sort works in (n) time. Then radix sorting takes time:
(A) (n + m)
(B) (nlogn)
(C) (nlogm)
(D) (mn ) (E) (mlogn) (F) (nm)
19. T or F: Suppose during one pass of radix sort, there is a tie between two numbers. Since they are considered the same number, it does not matter if those two numbers swap positions.
20. Suppose you use log n buckets to bucket sort n numbers, uniformly distributed. What would be the expected running time of bucket sort if you used mergesort to sort the individual buckets?
(A) (logn)(log(logn))
(B) (log (log n))(log n)2
(C) (log (log n))2
(D) n(logn)2
(E) nlogn
(F) the correct answer is not given
(G) n2 log n
(H) (logn)2
21. Consider using bucket sort to sort n numbers evenly distributed over the range 0 to m. Roughly, how many buckets
should you use if you wish to have sort in linear time?
(A) n (C) m
(B) n (D) m mn
22. Consider using bucket sort to sort n numbers evenly distributed over the range 0 to n3. The expected bucket count and the overall expected running time of the sort, respectively, is:
(A) (n) and linear (B) (n) and cubic (C) (1) and quadratic
(D) (1) and cubic
(E) (1) and linear
(F) (n) and quadratic
23. Suppose a dynamic array was implemented so that growing the array increased the capacity by 10000 elements. What is the amortized cost of the append operation? The append operation extends the illed portion by one slot (at the back).
(A) constant (C) quadratic (B) log linear (D) linear
24. Consider a dynamic illable array which grows by tripling in size. Let S represent the number of illed slots and E, the number of empty slots, and C, the capacity of the array. Which is a valid potential function for proving the amortized cost of an insert is a constant 3? Assume the actual cost of an insert when there is room is 1 and the actual cost of an insert when there is no room is S+1.
(A) 2SC (C) 2SC 23
(B) 2SC
4
25. Consider a dynamic illable array which grows by tripling in size. Which is a valid equation for calculating the total cost incurred when insertion 3i + 1 is made (e.g. insertions 1, 4, 10, etc)? Assume the individual cost of an insert when there is room is 1 and the individual cost of an insert when there is no room is 3i + 1. For example, the cost of inserting the 9th item is 1, while the cost of inserting the 10th item is 10. Assume the initial capacity of the array is 1.
(A) 5n4 (D) 5n2 23
(B) 5n3 (E) 5n3 32
(C) 5n4 (F) 5n2 32
26. Suppose a data structure has operation A with a real cost of 2n + 1 and operation B with a real cost of 3n + 1. After an A operation, n decreases to n while after a B operation, n decreases to n .
Which of the following potential functions can be used to show an amortized bound of (1) for operations A and B on this data structure?
(A) = 3n (C) none of the other answers work (B) = n (D) = 4n
2
27. Suppose a data structure has operation A with a real cost of 1, operation B with a real cost of 1, and operation C with a real cost of n. After an A operation, n increases by 1, while after a B operation, n stays the same. After a C operation, n goes to zero.
Which of the following potential functions can be used to show an amortized bound of (1) for A, B, and C operations? (A) none of the other answers work (C) = 3n
(B) =n (D) =2n
Assume min-heaps unless otherwise directed. For binomial heaps, assume that root lists (and child lists) are ordered left-to- right from low degree to high degree. Also assume when a child list is merged with a root list, the child list is placed to the left of the root list (i.e. the child list is scanned before the root list during the consolidation phase).
28. Which operations of a binomial heap are asymptotically faster than a binary heap, in the worst case?
24
(A) none of the other answers are correct (B) insertion, extractMin, deletion
(C) insertion, deletion
(D) extractMin, deletion
(E) extractMin (F) deletion
(G) insertion, extractMin (H) insertion
29. Suppose you wish to show that the amortized cost of an insertion into a binomial heap is constant? Which amortization example in the textbook would best serve as an analogy?
(A) multipop stack (C) dynamic array (size increases by a constant when full) (B) dynamic array (size doubles when full) (D) binary counter
30. Merging two binary heaps takes how much time compared to merging two binomial heaps?
(A) log linear versus linear
(B) log linear versus logarithmic (C) logarithmic versus logarithmic
(D) log linear versus log linear (E) linear versus linear
(F) linear versus logarithmic
31. After 15 consecutive inserts into an empty binomial heap, how many subheaps are in the root list?
(A) none of the other answers are correct (B) 4
(C) 1
(D) 2
(E) 6 (F) 7 (G) 5 (H) 3
5
32. After 18 insertions into an empty binomial heap, how many subheaps are in the root list?
(A) 7 (B) 8 (C) 3 (D) 4
this point, the number of subheaps in the root list can be calculated from n.
34. Consider inserting the following values, in the order given:
32956417
into an empty binomial heap. The value 9 is found in a subheap whose root has which value?
(H) none of the other answers are correct
33. T or F: Consider a sequence of n insertions into an empty binomial heap, followed by a single extractMin operation. At
(A) 7 (B) 6 (C) 3 (D) 4
(E) 1 (F) 5 (G) 2
(H) none of the other answers are correct
35. Consider inserting the consecutive integers from 0 to 12, inclusive and in increasing order, into an empty binomial heap. After deleting the value 5, the value 12 can be found in the subheap whose root has value:
(A) 6 (B) 3 (C) 5 (D) 2
(E) 0
(F) none of the other answers are correct
(G) 4 (H) 1
36. One expects to ind the minimum value in a binomial heap in time that is:
(A) constant (D) linear
(B) log (C) log log
(E) log linear
37. Consider inserting the consecutive integers from 1 to 12, inclusive and not necessarily in order, into an empty binomial heap. What are the largest root value possible, after all values have been inserted?
(A) 8 (B) 7 (C) 11 (D) 12
(E) 10
(F) none of the other answers are correct
(G) 9 (H) 6

Explanation / Answer

Solution:

17. (E) 744, 447, 774, 477

18. (F) (nm)

19. T

Suppose during one pass of radix sort, there is a tie between two numbers. Since they are considered the same number, it does not matter if those two numbers swap positions.

20. (E) nlogn

21. (C) m

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.