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
[quads id=1]
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
[quads id=1]
4) What is the expected runtime of Randomly Built Binary Search Tree Sort?
A) O( n.log n)
B) O(n2)
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
[quads id=1]
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
[quads id=1]
8) What is returned when the call OS-select(x,i) is made to the Order Statistic Select algorithm?
A). The ith 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
[quads id=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
