TREES

Which of the following data structure can provide efficient searching of the elements?

• a) unordered lists

• b) binary search tree

• c) tree

• d) 2-3 tree

Consider a B+-tree in which the maximum number of keys in a node is 5. What is the minimum number of keys in any non-root node? (GATE CS 2010)

• 4

• 3

• 2

• 1

Consider a B+-tree in which the maximum number of keys in a node is 5. What is the minimum number of keys in any non-root node? (GATE CS 2010)

• a) logn (k+1) – 1

• b) nk

• c) logk (n+1) – 1

• d) klogn

Which of the following is true?

• a) larger the order of B-tree, less frequently the split occurs

• b) larger the order of B-tree, more frequently the split occurs

• c) smaller the order of B-tree, more frequently the split occurs

• d) smaller the order of B-tree, less frequently the split occurs

What is the special property of red-black trees and what root should always be?

• a) a color which is either red or black and root should always be black color only
  

• b) height of the tree
  

• c) pointer to next node
  

• d) a color which is either green or black

Which of the following is an application of Red-black trees and why?

• a) used to store strings efficiently
  

• b) used to store integers efficiently
  

• c) can be used in process schedulers, maps, sets
  

• d) for efficient sorting

What is the below pseudo code trying to do, where pt is a node pointer and root pointer?

redblack(Node root, Node pt) :

if (root == NULL)

return pt  

if (pt.data < root.data)

{

root.left = redblack(root.left, pt); root.left.parent = root }

else if (pt.data > root.data)

{ root.right = redblackt(root.right, pt)

root.right.parent = root }

return root

• a) insert a new node
  

• b) delete a node
  

• c) search a node
  

• d) count the number of nodes

Which of the following property of splay tree is correct?

• a) it holds probability usage of the respective sub trees
  
  

• b) any sequence of j operations starting from an empty tree with h nodes atmost, takes O(jlogh) time complexity

• c) sequence of operations with h nodes can take O(logh) time complexity
  

• d) splay trees are unstable trees

What is a splay operation?

• a) moving parent node to down of child
  

• b) moving a node to root
  

• c) moving root to leaf
  

• d) removing leaf node

What output does the below pseudo code produces?

Tree_node function(Tree_node x)

{

Tree_node y = x.left;

x.left = y.right;

y.right = x;

return y;

}

• a) right rotation of subtree
  

• b) left rotation of subtree
  

• c) zig-zag operation
  

• d) zig-zig operation