ADS_3

Which of the following is TRUE about splay trees?

• Splay trees implement the move-to-front heuristi

• Splay trees are perfectly balanced

• Inserting an entry into a splay tree has worst-case cost of O(logn)

• Splay trees are proper binary trees

Which one of the following data structures are preferred in database-system implementation?

• AVL tree

• B-tree

• B+ - tree

• Splay tree

When a node N is accessed it is splayed to make it the

• Root node

• Parent node

• Child node

• Sibling node

Why do we impose restrictions like

. root property is black

. every leaf is black

. children of red node are black

. all leaves have same black

• to get logarithm time complexity

• to get linear time complexity

• to get exponential time complexity

• to get constant time complexity

What are the operations that could be performed in O(logn) time complexity by red-black tree?

• insertion, deletion, finding predecessor, successor

• only insertion

• only finding predecessor, successor

• for sorting

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

• used to store strings efficiently

• used to store integers efficiently

• can be used in process schedulers, maps,

• sets

  for efficient sorting

When it would be optimal to prefer Red-black trees over AVL trees?

• when there are more insertions or deletions

• when more search is needed

• when tree must be balanced

• when log(nodes) time complexity is needed

When to choose Red-Black tree, AVL tree and B-trees?

• many inserts, many searches and when managing more items respectively

• many searches, when managing more items respectively and many inserts respectively

• sorting, sorting and retrieval respectively

• retrieval, sorting and retrieval respectively

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

• insert a new node

• delete a node

• search a node

• count the number of nodes

What are AVL trees?

• self balanced

• height balanced

• both height balanced and self balanced

• none