**1) Consider the Red Black Tree given below, given that the node containing key value 35 is red, how many black nodes are there in the red black tree?(Do not count the nils)**

A). 3

B). 2

C). 5

D). 6

Answer(s) : C). 5

**2) Which of the following is not a property of a Red Black Tree?**

A). Every

node is either red or black

B). Every

leaf is black

C). The

root is red

D). If

the node is red, its parent is black

Answer(s) : C).The root is red

**3) Given the following numbers, arrange them into a Binary Search Tree. Let the root be at position 1. If a node is at position is i, the right child will be at position 2i+1 and left child at 2i ( i.e. the right child of root will be at position 3).While forming a binary search tree by inserting 9, 5,1,12,6,7,8 in order, which positions will be filled?**

a) A). 1,2,3,4,5,11,23

b) B). 1,2,3,6,5,10,20

c) C). 1,2,4,8,3,6,12

d) D). 1,2,3,4,5,6,12

Answer(s) : A).1,2,3,4,5,11,23

**4) What is the expected runtime of Randomly Built Binary Search Tree Sort?**

A) O( n.log n)

B) O(n^{2})

C). O(log n)

D). None of the above

Answer(s) : A) O( n.log n)

**5) In the red black tree given below, the node that contains key value 2 is black, which of the nodes will be red, for it to be a valid red black tree? (Remember to add the nils with black colour below all leaves)**

A). The node that contains key value -4

B). The node that contains key value 3

C). Both of A and B

D). There will be no node that is coloured red

Answer(s) : C). Both of A and B

**6) In an interval tree, what has been stored in each node along with the interval? Note that here m(left[x]) means maximum value of interval on left of node x, similarly m(right[x]) means maximum value of interval on right of x, int x means interval x.**

A). max{high(int x),m(left[x]),m(right[x])}

B). High(int x)

C) m(right[x])

D). None of these

Answer(s) : A). max{high(int x),m(left[x]),m(right[x])}

**7) A binary search tree is given below. From the methods given below, which ones could possibly convert this BST into a Red Black Tree? (Remember to add nils in the tree) **

a) Colour all nodes except the one with key value 77 as black

b) Colour the node with key value 55, red

c) Colour node with key value 33 and 77 both red

d) None of these methods would make it a valid Red Black Tree

Answer(s) : c) Colour node with key value 33 and 77 both red

**8) What is returned when the call OS-select(x,i) is made to the Order Statistic Select algorithm?**

A). The i^{th} smallest element in the subtree rooted at x

B). The first i elements in subtree rooted at x

C). The sum of first i elements in subtree rooted at x

D). None of these

Answer(s) : A). The ithsmallest element in the subtree rooted at x

**9) In the Order Statistic Tree, along with the key, what other information is stored in the nodes? (Here size(left[x] ) is size of left subtree of node x and similarly size(right[x]) is size of right subtree of node x.)**

A). size(left[x])

B). size(right[x])+1

C). size(left[x])+size(right[x])+1

D). None of these

Answer(s) : C). size(left[x])+size(right[x])+1

**10) What is the black height of the given Red Black Tree from the root node? Remember to count the NILs as well.**

A). 2

B). 3

C). 4

D). 1

Answer(s) : A). 2

## 2 Comments

## Dhruvin · September 17, 2017 at 10:22 AM

Thank you very much for this

Please upload solution for Introduction to Algorithm and Analysis week 7 MCQs

## Raja Mandal · September 18, 2017 at 5:48 PM

week 7?