9. In what scenario will constructing a max-heap from N elements (added one at a
ID: 3740706 • Letter: 9
Question
9. In what scenario will constructing a max-heap from N elements (added one at a time) be carried out most efficiently?
(a) when the elements are added in ascending order
(b) when the elements are added in descending order
(c) when the elements are added in random order
(d) when a separate min-heap is used to simultaneously keep track of the smallest element
(e) all the above yield the same runtime efficiency
10. For this and the next problem, consider the following definition of a circular, doubly-linked list with a sentinel head, in which we have defined a set_cursor method, which sets the cursor attribute to a specified index in the linked list where subsequent operations can be performed.
class LinkedList:
def set_cursor(self, idx):
assert(idx < len(self))
self.cursor = self.head.next
for _ in range(idx):
self.cursor = self.cursor.next
def cursor_insert(self, val):
n = LinkedList.Node(val, prior=self.cursor.prior, next=self.cursor)
_________________________________________________
self.length += 1
def cursor_delete(self):
_________________________________________________
_________________________________________________
self.cursor = self.cursor.next self.length -= 1
cursor_insert should insert the given value val at the current cursor position, and cursor_delete should delete the value at the current cursor position. In both cases, the cursor should refer to the same index as it did before the operation (except in the case of deletion of the last node, which will invalidate the cursor).
Which correctly completes the implementation of cursor_insert?
(a) self.cursor.prior.next = self.cursor.next.prior = n
(b) self.cursor = self.cursor.next = self.cursor.prior = n
(c) self.cursor = self.cursor.prior = self.cursor.next.prior = n
(d) self.cursor.next.prior = self.cursor.prior = self.cursor = n
(e) self.cursor.prior.next = self.cursor.prior = self.cursor = n
11. Which correctly completes the implementation of cursor_delete?
(a) self.cursor.prior = self.cursor.next self.cursor.next = self.cursor.prior
(b) self.cursor = self.cursor.next self.cursor.prior = self.cursor
(c) self.cursor.prior.next = self.cursor.next.prior self.cursor.next.prior = self.cursor.prior.next
(d) self.cursor.prior.next = self.cursor.next self.cursor.next.prior = self.cursor.prior
(e) self.cursor.next = self.cursor.next.prior self.cursor.prior = self.cursor.prior.next
12. Consider the following definition of a hashtable with a partially implemented rehash method, which will either grow or shrink the buckets array to the provided value n_buckets (while keeping all existing key/value mappings).
class Hashtable:
def rehash(self, n_buckets):
new_buckets = [None] * n_buckets
for b in self.buckets:
while b: b_next = b.next
________________________________
________________________________
________________________________
b = b_next
self.buckets = new_buckets
Which correctly completes the rehash method?
(a) idx = hash(b.key) % n_buckets
b.next = new_buckets[idx]
new_buckets[idx] = b
(b) idx = hash(b.key) % len(self.buckets)
b.next = new_buckets[idx]
self.buckets[idx] = b
(c) idx = hash(b.key) % len(self.buckets)
self.buckets[idx] = new_buckets[idx]
b.next = new_buckets[idx]
(d) idx = hash(b.key) % n_buckets
new_buckets[idx].next = b
b.next = new_buckets[idx]
(e) idx = hash(b.key) % n_buckets
b.next = new_buckets[idx].next
new_buckets[idx].next = b
Explanation / Answer
According to Chegg's policy, please find the answer to the first question:
Solution to Question 9:
In an array implementation of the heap, the data sorted in decending order will be effective for creating a max-heap since in that case, the nodes are all nodes at the internal levels are greater than those below it. Thus, no requirement for changing the positions of numbers will be required. So, option (b) is correct.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.