Q1. Consider a sequence of numbers to have repetitions, how a cartesian tree can be constructed in such situations without violating any rules?.
A. use any tie-breaking rule between repeated elements.
B. cartesian tree is impossible when repetitions are present.
C. construct a max heap in such cases.
D. construct a min heap in such cases.
Answer= use any tie-breaking rule between repeated elements
Q2. After applying the below operations on a input sequence, what happens? i. construct a cartesian tree for input sequence ii. put the root element of above tree in a priority queue iii. if( priority queue is not empty) then .search and delete minimum value in priority queue .add that to output .add cartesian tree children of above node to priority queue.
A. constructs a cartesian tree.
B. sorts the input sequence.
C. does nothing.
D. produces some random output.
Answer= sorts the input sequence
Q3. Cartesian trees are most suitable for?.
A. searching.
B. finding nth element.
C. minimum range query and lowest common ancestors.
D. self balancing a tree.
Answer= minimum range query and lowest common ancestors
Q4. A treap is a cartesian tree with.
A. additional value, which is a priority value to the key generated randomly.
B. additional value, which is a priority value to the key generated sequentially.
C. additional heap rule.
D. additional operations like remove a range of elements.
Answer= additional value, which is a priority value to the key generated randomly
Q5. Cartesian trees solve range minimum query problem in constant time.
A. TRUE.
B. FALSE.
C. Nothing can be said.
D. None of the mentioned.
Answer= TRUE
Q6. What is a weight balanced tree?.
A. A binary tree that stores the sizes of subtrees in nodes.
B. A binary tree with an additional attribute of weight.
C. A height balanced binary tree.
D. A normal binary tree.
Answer= A binary tree that stores the sizes of subtrees in nodes
Q7. What are the applications of weight balanced tree?.
A. dynamic sets, dictionaries, sequences, maps.
B. heaps.
C. sorting.
D. storing strings.
Answer= dynamic sets, dictionaries, sequences, maps
Q8. A node of the weight balanced tree has.
A. key, left and right pointers, size.
B. key, value.
C. key, size.
D. key.
Answer= key, left and right pointers, size
Q9. What is the condition for a tree to be weight balanced. where a is factor and n is a node?.
A. weight[n.left] >= a*weight[n] and weight[n.right] >= a*weight[n]..
B. weight[n.left] >= a*weight[n.right] and weight[n.right] >= a*weight[n]..
C. weight[n.left] >= a*weight[n.left] and weight[n.right] >= a*weight[n]..
D. weight[n] is a non zero.
Answer= weight[n.left] >= a*weight[n] and weight[n.right] >= a*weight[n].
Q10. What are the operations that can be performed on weight balanced tree?.
A. all basic operations and set intersection, set union and subset test.
B. all basic operations.
C. set intersection, set union and subset test.
D. only insertion and deletion.
Answer= all basic operations and set intersection, set union and subset test
Q11. Consider a weight balanced tree such that, the number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on k nodes can be described as.
A. log2 n.
B. log4/3 n.
C. log3 n.
D. log3/2 n.
Answer= log3/2 n
Q12. What does the below definations convey? i. A binary tree is balanced if for every node it is gonna hold that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1. ii. A binary tree is balanced if for any two leaves the difference of the depth is at most 1..
A. weight balanced and height balanced tree definations.
B. height balanced and weight balanced tree definations.
C. definations of weight balanced tree.
D. definations of height balanced tree.
Answer= weight balanced and height balanced tree definations
Q13. Elements in a tree can be indexed by its position under the ordering of the keys and the ordinal position of an element can be determined, both with good efficiency..
A. True.
B. False.
C. Nothing can be said.
D. None of the mentioned.
Answer= True
Q14. 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.
Answer= a color which is either red or black and root should always be black color only
Q15. 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.
A. to get logarithm time complexity.
B. to get linear time complexity.
C. to get exponential time complexity.
D. to get constant time complexity.
Answer= to get logarithm time complexity
Q16. What are the operations that could be performed in O(logn) time complexity by red-black tree?.
A. insertion, deletion, finding predecessor, successor.
B. only insertion.
C. only finding predecessor, successor.
D. for sorting.
Answer= insertion, deletion, finding predecessor, successor
Q17. 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.
Answer= can be used in process schedulers, maps, sets
Q18. When it would be optimal to prefer Red-black trees over AVL trees?.
A. when there are more insertions or deletions.
B. when more search is needed.
C. when tree must be balanced.
D. when log(nodes) time complexity is needed.
Answer= when there are more insertions or deletions
Q19. Why Red-black trees are preferred over hash tables though hash tables have constant time complexity?.
A. no they are not preferred.
B. because of resizing issues of hash table and better ordering in redblack trees.
C. because they can be implemented using trees.
D. because they are balanced.
Answer= because of resizing issues of hash table and better ordering in redblack trees
Q20. How can you save memory when storing color information in Red-Black tree?.
A. using least significant bit of one of the pointers in the node for color information.
B. using another array with colors of each node.
C. storing color information in the node structure.
D. using negative and positive numbering.
Answer= using least significant bit of one of the pointers in the node for color information
Q21. When to choose Red-Black tree, AVL tree and B-trees?.
A. many inserts, many searches and when managing more items respectively.
B. many searches, when managing more items respectively and many inserts respectively.
C. sorting, sorting and retrieval respectively.
D. retrieval, sorting and retrieval respectively.
Answer= many inserts, many searches and when managing more items respectively
Q22. Which algorithm is used in the top tree data structure?.
A. Divide and Conquer.
B. Greedy.
C. Backtracking.
D. Branch.
Answer= Divide and Conquer
Q23. For how many vertices in a set, is top tree defined for underlying tree?.
A. 3.
B. 4.
C. 5.
D. 2.
Answer= 2
Q24. How many edges are present in path cluster?.
A. 2.
B. 3.
C. 6.
D. 1.
Answer= 2