Q1. How many edges does a leaf cluster contain?.
A. 0.
B. 1.
C. 2.
D. 3.
Answer= 0
Q2. How many edges are present in Edge cluster?.
A. 0.
B. 1.
C. 2.
D. 4.
Answer= 1
Q3. Which data structure is used to maintain a dynamic forest using a link or cut operation?.
A. Top Tree.
B. Array.
C. Linked List.
D. Stack.
Answer= Top Tree
Q4. Is Top tree used for maintaining Dynamic set of trees called forest..
A. TRUE.
B. FALSE.
C. Nothing can be said.
D. None of the mentioned.
Answer= TRUE
Q5. What is the time complexity for the initialization of top tree?.
A. O (n).
B. O (n2).
C. O (log n).
D. O (n!).
Answer= O (n)
Q6. How many top trees are there in a tree with single vertex?.
A. 0.
B. 1.
C. 2.
D. 3.
Answer= 0
Q7. 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= All of the mentioned
Q8. 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= All of the mentioned
Q9. Which of the following are used as an internal operation in Top tree?.
A. Merge.
B. Cut.
C. Expose.
D. Link.
Answer= Merge
Q10. 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= O (log n)
Q11. Which of the following is not the self balancing binary search tree?.
A. AVL Tree.
B. 2-3-4 Tree.
C. Red - Black Tree.
D. Splay Tree.
Answer= 2-3-4 Tree
Q12. 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= self adjusting binary search trees
Q13. 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= any sequence of j operations starting from an empty tree with h nodes atmost, takes O(jlogh) time complexity
Q14. 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= easier to program and faster access to recently accessed items
Q15. Is it true that splay trees have O(logn) amortized complexity ?.
A. TRUE.
B. FALSE.
C. Nothing can be said.
D. None of the mentioned.
Answer= TRUE
Q16. 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= moving a node to root
Q17. Which of the following options is an application of splay trees?.
A. cache Implementation.
B. networks.
C. send values.
D. receive values.
Answer= cache Implementation
Q18. 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= In real time it is estimated that 80% access is only to 20% data, hence most used ones must be easily available
Q19. 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= height of a splay tree can be linear when accessing elements in non decreasing order.
Q20. What is the complexity of searching for a particular element in a Singly Linked List?.
A. O(n).
B. O(1).
C. logn.
D. nlogn.
Answer= O(n)
Q21. What is the space complexity of a treap algorithm?.
A. O(N).
B. O(log N).
C. O(log N).
D. O(N2).
Answer= O(N)
Q22. A treap is a combination of a tree and a heap..
A. FALSE.
B. TRUE.
C. Nothing can be said.
D. None of the mentioned.
Answer= TRUE
Q23. Which is the simplest of all binary search trees?.
A. AVL tree.
B. Treap.
C. Splay tree.
D. Binary heap.
Answer= Treap
Q24. What is the reason behind the simplicity of a treap?.
A. Each node has data and a pointer.
B. Each node is colored accordingly.
C. It is a binary search tree following heap principles.
D. Each node has a fixed priority field.
Answer= Each node has a fixed priority field
Q25. What is the condition for priority of a node in a treap?.
A. a node's priority should be greater than its parent.
B. a node's priority should be at least as large as its parent.
C. the priority is randomly assigned and can have any value.
D. a node's priority is always given in decreasing order.
Answer= a node's priority should be at least as large as its parent
Q26. Several other operations like union set difference and intersection can be done in treaps..
A. TRUE.
B. FALSE.
C. Nothing can be said.
D. None of the mentioned.
Answer= TRUE
Q27. What is the average running time of a treap?.
A. O(N).
B. O(N log N).
C. O(log N).
D. O(M log N).
Answer= O(log N)
Q28. Which node has the lowest priority in a treap?.
A. root node.
B. leaf node.
C. null node.
D. centre node.
Answer= root node
Q29. What is the priority of a null node?.
A. 1.
B. 0.
C. random number.
D. infinity.
Answer= infinity
Q30. Who invented treaps?.
A. Cecilia and Raimund.
B. Arne Andersson.
C. Donald Shell.
D. Harris and Ross.
Answer= Cecilia and Raimund
Q31. What is a threaded binary tree traversal?.
A. a binary tree traversal using stacks.
B. a binary tree traversal using queues.
C. a binary tree traversal using stacks and queues.
D. a binary tree traversal without using stacks and queues.
Answer= a binary tree traversal without using stacks and queues
Q32. What are the disadvantages of normal binary tree traversals?.
A. there are many pointers which are null and thus useless.
B. there is no traversal which is efficient.
C. complexity in implementing.
D. improper traversals.
Answer= there are many pointers which are null and thus useless
Q33. What may be the content of a node in threaded binary tree?.
A. leftchild_pointer, left_tag, data, right_tag, rightchild_pointer.
B. leftchild_pointer, left_tag.
C. leftchild_pointer, left_tag, right_tag, rightchild_pointer.
D. leftchild_pointer, left_tag, data.
Answer= leftchild_pointer, left_tag, data, right_tag, rightchild_pointer