Question 1 |

Let A be a priority queue for maintaining a set of elements. Suppose A is
implemented using a max-heap data structure. The operation Extract-Max(A)
extracts and deletes the maximum element from A. The operation Insert(A,key)
inserts a new element key in A. The properties of a max-heap are preserved at the
end of each of these operations.

When A contains n elements, which one of the following statements about the worst case running time of these two operations is TRUE?

When A contains n elements, which one of the following statements about the worst case running time of these two operations is TRUE?

Both Extract-Max(A) and Insert(A,key) run in O(1). | |

Both Extract-Max(A) and Insert(A,key) run in O(log(n)). | |

Extract-Max(A) runs in O(1) whereas Insert(A,key) runs in O(n). | |

Extract-Max(A) runs in O(1) whereas Insert(A,key) runs in O(log(n)). |

Question 1 Explanation:

Question 2 |

Which one of the following sequences when stored in an array at locations
A[1], . . . , A[10] forms a max-heap?

23, 17, 10, 6, 13, 14, 1, 5, 7, 12 | |

23, 17, 14, 7, 13, 10, 1, 5, 6, 12 | |

23, 17, 14, 6, 13, 10, 1, 5, 7, 15 | |

23, 14, 17, 1, 10, 13, 16, 12, 7, 5 |

Question 2 Explanation:

Question 3 |

Let H be a binary min-heap consisting of n elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in H?

\Theta (1) | |

\Theta (\log n) | |

\Theta ( n) | |

\Theta (n \log n) |

Question 3 Explanation:

Question 4 |

Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is ___________.

512 | |

511 | |

1022 | |

10 |

Question 4 Explanation:

Question 5 |

Consider the following statements:

I. The smallest element in a max-heap is always at a leaf node.

II. The second largest element in a max-heap is always a child of the root node.

III. A max-heap can be constructed from a binary search tree in \Theta (n) time.

IV. A binary search tree can be constructed from a max-heap in \Theta (n) time.

Which of the above statements is/are TRUE?

I. The smallest element in a max-heap is always at a leaf node.

II. The second largest element in a max-heap is always a child of the root node.

III. A max-heap can be constructed from a binary search tree in \Theta (n) time.

IV. A binary search tree can be constructed from a max-heap in \Theta (n) time.

Which of the above statements is/are TRUE?

I, II and III | |

I, II and IV | |

I, III and IV | |

II, III and IV |

Question 5 Explanation:

There are 5 questions to complete.

Please give question no 20 first then 19.

It will be in sequence