# 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

**Also Visit This Link:** Problem Set #2 Quiz Answer

### 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).**