CS 310代做、java/c++编程代做、代做lower-order terms、CS/python, C/C++代写

日期：2018-12-19 10:52

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: