# Problem Set #3 Quiz Answer

In this article i am gone to share Coursera Course Graph Search, Shortest Paths, and Data Structures Week 3 | Problem Set #3 Quiz Answer with you..

## Graph Search, Shortest Paths, and Data Structures

### Problem Set #3 Quiz Answer

Question 1)
Suppose you implement the functionality of a priority queue using a sorted array (e.g., from biggest to smallest). What is the worst-case running time of Insert and Extract-Min, respectively? (Assume that you have a large enough array to accommodate the Insertions that you face.)ย

• ำจ(n) and ำจ(n)
• ำจ(n) and ำจ(1)
• ำจ(log n) and ำจ(1)
• ำจ(1) and ำจ(n)

Question 2)
Suppose you implement the functionality of a priority queue using an unsorted array. What is the worst-case running time 1/1 point of Insert and Extract-Min, respectively? (Assume that you have a large enough array to accommodate the Insertions that you face.)

• ำจ(1) and ำจ(log n)
• ำจ(n) and ำจ(n)
• ำจ(n) and ำจ(1)
• ำจ(1) and ำจ(n)

Question 3)
You are given a heap with n elements that supports Insert and Extract-Min. Which of the following tasks can you achieve in O(log n) time?ย

• Find the fifth-smallest element stored in the heap.ย
• Find the largest element stored in the heap.ย
• Find the median of the elements stored in the heap.ย
• None of these.

Question 4)
You are given a binary tree (via a pointer to its root) with n nodes. As in lecture, let size(x) denote the number of nodes in the subtree rooted at the node x. How much time is necessary and sufficient to compute size(x) for every node x of the tree?

• ำจ(n)
• ำจ(n2)
• ำจ(height)ย
• ำจ(n log n)

Question 5)
Suppose we relax the third invariant of red-black trees to the property that there are no three reds in a row. That is, if a node and its parent are both red, then both of its children must be black. Call these relaxed red-black trees. Which of the following statements is not true?ย

• Every red-black tree is also a relaxed red-black tree.ย
• There is a relaxed red-black tree that is not also a red-black tree.ย
• The height of every relaxed red-black tree with n nodes is O(log n).ย
• Every binary search tree can be turned into a relaxed red-black tree (via some coloring of the nodes as black or red).