CS 310讲解、java/c++编程讲解、讲解lower-order terms、CS/python, C/C++辅导
- 首页 >> Java编程CS 310: Worksheet 05 San Diego State University
Name: Section:
Due Date: 2018-NOV-06/07 Score:
Answer the questions in the spaces provided on the question sheets. If you run out
of room for an answer, continue on the back of the page.
Complexity Analysis: Heaps
Give the run-time complexity of the following code segments. The input size is n. Give the tightest
possible bound. Remember to ignore coefficients and lower-order terms.
1. (2 points) After inserting n items into a maximum heap in sequential order, what is the worst
case performance for finding the single largest item in the tree?
Answer:
2. (2 points) After inserting n items into a minimum heap in random order, what is the worst
case performance for finding the single largest item in the tree?
Answer:
3. (2 points) In a minimum heap of n items, what is the worst case performance for finding the
most frequently occurring item inside?
Answer:
4. (2 points) Given an array of n items, what is the worst case performance for putting the array
in heap-order through heapification?
Answer:
5. (2 points) What is the worst case performance for removing the smallest item from a minimum
heap of size n?
Answer:
Heapsort
6. (2 points) The heapsort algorithm is not , but you can make it appear so by
using a on items inserted into the heap.
A. In-Place, Comparator B. Stable, Comparator C. Stable, Wrapper D. In-Place,
Wrapper E. None of the above.
Answer:
7. (4 points) What is the complexity of heapsort when sorting an array already in sorted order?
A. ω(1) B. ?(n log(n)) C. O(n log(n)) D. O(2n
) E. All of the above.
Answer:
CS 310: Worksheet 05 San Diego State University
Heap Construction
8. (2 points) In Priority Queues, the item with the highest priority, or importance, exits the data
structure before anything less important. By convention, lower numbers represent items of
priority, so one frequently uses a for this behavior.
A. lower, min-heap B. lower, max-heap C. higher, min-heap D. higher, max-heap
9. (6 points) In the space provided, create a heap by inserting each of the items in the following
list into the heap, one item at a time, as if the numbers represented priorities for a queue of
customers arriving in real time.
Priorities: 55, 0, 0, 92, 1, -82, -8, 0, 2, 11, 13, 37
10. (2 points) A heap containing 1, 048, 576 items must have, at most, how many edges from its
root to its farthest leaf?
Answer:
11. (2 points) What is the array index for the parent of an item located at index 12 in a heap?
The heap’s root uses index 0.
Answer: