1. What are splay trees?
a) self adjusting binary search trees
b) self adjusting binary trees
c) a tree with strings
d) a tree with probability distributions
Answer: a
Explanation:
Splay trees are height balanced, self adjusting BST’s.
2. 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
Answer: b
Explanation:
This is a property of splay tree that ensures faster access. we push the most recently used nodes to top which leads to faster access to recently used values.
3. Why to prefer splay trees?
a) easier to program
b) space efficiency
c) easier to program and faster access to recently accessed items
d) quick searching
Answer: c
Explanation:
Whenever you insert an element or remove or read an element that will be pushed or stored at the top which facilitates easier access or recently used stuff.
4. Is it true that splay trees have O(logn) amortized complexity ?
a) true
b) false
Answer: a
Explanation:
We go with amortized time complexity when we feel that not all operations are worst and some can be efficiently done. in splay trees not all splay operations will lead to O(logn) worst case complexity.
5. 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
Answer: b
Explanation:
Splay trees mainly work using splay operations. wheneve we insert, delete and search for a node we splay the respective nodes to root. we have zig-zag and zig-zig operations.
6. Which of the following options is an application of splay trees?
a) cache Implementation
b) networks
c) send values
d) receive values
Answer: a
Explanation:
Splay trees can be used for faster access to recently accessed items and hence used for cache implementations.
7. 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?
a) no there is no special usage
b) In real time it is estimated that 80% access is only to 20% data, hence most used ones must be easily available
c) redblack and avl are not upto mark
d) they are just another type of self balancing binary search trees
Answer: a
Explanation:
If A ꓵ B is a singleton set where A and B are two clusters, that is there are only one node that is common between the clusters then they are known as Merge able cluster.
8. 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
Answer: a
Explanation:
When a right rotation is done the parent of the rotating node becomes it’s right node and it’s child becomes it’s left child.
9. What is the disadvantage of using splay trees?
a) height of a splay tree can be linear when accessing elements in non decreasing order.
b) splay operations are difficult
c) no significant disadvantage
d) splay tree performs unnecessary splay when a node is only being read
Answer: a
Explanation:
This will be the case after accessing all n elements in non-decreasing order. Since the height of a tree corresponds to the worst-case access time, this means that the actual cost of an operation can be high. However the amortized access cost of this worst case is logarithmic O(log n).
10. How many top trees are there in a tree with single vertex?
a) 0
b) 1
c) 2
d) 3
Answer: a
Explanation:
Tree having a single vertex has no clusters of tree present in the structure. Therefore, there are empty top trees in a tree having a single vertex. Trees with one node are single node.
11. Which property makes top tree a binary tree?
a) Nodes as Cluster
b) Leaves as Edges
c) Root is Tree Itself
d) All of the mentioned
Answer: d
Explanation:
Top tree can be considered as a binary tree if the nodes form a cluster, leaves act as an edge and the root of the top tree acts as a tree itself. Then the top tree is called binary tree.
12. Which of the dynamic operations are used in Top Tree data structure implementation?
a) Link
b) Cut
c) Expose
d) All of the mentioned
Answer: d
Explanation:
Link returns a single tree having different vertices from top trees. Cut removes the edge from the top tree. Expose is used to implement queries on top trees. Hence all of the options are used as dynamic operations.
13. Which of the following are used as an internal operation in Top tree?
a) Merge
b) Cut
c) Expose
d) Link
Answer: a
Explanation:
Link returns a single tree having different vertices from top trees. Cut removes the edge from the top tree. Expose is used to implement queries on top trees. While merge is an internal operation used to merge two clusters and return as a parent cluster.
14. What is the time complexity for maintaining a dynamic set of weighted trees?
a) O (n)
b) O (n2)
c) O (log n)
d) O (n!)
Answer: c
Explanation:
A lot of applications have been implemented using Top tree interface. Maintaining a dynamic set of weighted trees is one such application which can be implemented with O (log n) time complexi
15. What is the time complexity of the juggling algorithm to rotate an array?
a) O(1)
b) O(n)
c) O(d)
d) O(n*d)
Answer: b
Explanation:
Time complexity of juggling algorithm is O(n). Its auxiliary space complexity is O(1).
16. Reversal algorithm and juggling algorithm for array rotation have the same time complexity.
a) True
b) False
Answer: a
Explanation:
Time complexity of juggling algorithm is O(n) which like that of reversal algorithm. They also have the same space complexity
