CPS02-Day2-NWC -Set01

What is a splay operation?

• moving parent node to down of child
• moving a node to root
• moving root to leaf
• removing leaf node

Which of the following options is an application of splay trees?

• cache Implementation
• networks
• send values
• receive values

What are splay trees?

• self adjusting binary search trees
• self adjusting binary trees
• a tree with strings
• a tree with probability distributions

Which of the following property of splay tree is correct?

• it holds probability usage of the respective sub trees
• any sequence of j operations starting from an empty tree with h nodes at most, takes O(jlogh) time complexity
• sequence of operations with h nodes can take O(logh) time complexity
• splay trees are unstable trees

Why to prefer splay trees?

• easier to program
• space efficiency
• easier to program and faster access to recently accessed items
• quick searching

When we have red-black trees and AVL trees that can perform most of operations in logarithmic times, then what is the need for splay trees?

• no there is no special usage
• In real time it is estimated that 80% access is only to 20% data, hence most used ones must be easily available
• redblack and avl are not upto mark
• they are just another type of self balancing binary search trees

Is it true that splay trees have O(logn) amortized complexity?

• true
• false

What is the disadvantage of using splay trees?

• height of a splay tree can be linear when accessing elements in non-decreasing order.
• splay operations are difficult
• no significant disadvantage
• splay tree performs unnecessary splay when a node is only being read

What does the other nodes of an expression tree(except leaves) contain?

• only operands
• only operators
• both operands and operators
• expression

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