Data Structures & Algorithms Multiple Choice Questions on “Tango Tree”.
1. Who developed the concept of tango tree?
a) Erik Demaine
b) Mihai Patrascu
c) John Lacono
d) All of the mentioned
Answer: d
Clarification: Erik Demaine is a well-known professor of Computer Science at MIT. John Lacono is an American computer scientist specialized in data structure and algorithm while Mihai Patrascu was a Romanian- American computer scientist. All of them together developed the concept of Tango tree.
2. Which type of tree is tango tree?
a) Ternary Tree
b) AVL Tree
c) Binary Search Tree
d) K-ary Tree
Answer: c
Clarification: Tango tree is an example of binary search tree which was developed by four famous scientists Erik Demaine, Mihai Patrascu, John Lacono and Harmon in the year 2004.
3. After which city is tango tree named?
a) Vatican City
b) Buenos Aires
c) New York
d) California
Answer: b
Clarification: Tango is a popular couple dance or partner dance that was originated in the 1880s somewhere between Argentina and Uruguay. Buenos Aires is a capital city off Argentina. Hence they named after Buenos Aires.
4. Which type of binary search tree or algorithm does tango tree use?
a) Online
b) Offline
c) Static
d) Dynamic
Answer: d
Clarification: Tango tree is an online binary search tree whose time complexity is O (log (log n)) when compared to the time complexity of offline binary search tree model. Online algorithm processes input or data provided piece by piece.
5. What is the time complexity of for achieving competitive ratio by tango tree?
a) O (log n)
b) O (n2)
c) O (n!)
d) O (log (log n))
Answer: d
Clarification: Tango tree is an online binary search tree whose time complexity is O (log (log n)) when compared to the time complexity of offline binary search tree model. Online algorithm processes input or data provided piece by piece.
6. Which type of binary search tree is imitated for construction of tango tree?
a) Complete Binary Search Tree
b) Perfect Binary Search Tree
c) Balanced Binary Search Tree
d) Degenerate Binary Search Tree
Answer: a
Clarification: Tango tree is constructed by simulating a complete binary search tree. This tree is also known as Reference tree, that contains all the elements of the tree. Also, the reference tree is never showed in actual implementation.
7. Which special balanced binary search tree is used to store the nodes of auxiliary tree?
a) Red – Black Tree
b) Red – Brown Tree
c) Red – Yellow Tree
d) Red – Tango Tree
Answer: a
Clarification: The path starting from the root and following the path of preferred child node till the end of leaf node is known as preferred path. Nodes are stored in Red – Black tree for the representation of the preferred path.
8. Is tango tree represented as a tree of trees.
a) True
b) False
Answer: a
Clarification: Partitioning method is used by tango tree which partitions a binary search tree into small sets of paths and then storing them to auxiliary trees. Hence tango tree is represented as a tree of trees.
9. Which operation is used to combine two auxiliary trees?
a) Join
b) Combinatorial
c) Add
d) Concatenation
Answer: a
Clarification: If the top node of one of the reference tree amongst the two, is the is the child of the bottom node of the other reference tree, then the join operation can be carried out to join the two auxiliary trees.
10. Is partitioning method used by Tango Tree.
a) True
b) False
Answer: a
Clarification: Partitioning method is used by tango tree which partitions a binary search tree into small sets of paths and then storing them to auxiliary trees. Hence tango tree is represented as a tree of trees.
11. Which operation is used to break a preferred path into two sets of parts at a particular node?
a) Differentiate
b) Cut
c) Integrate
d) Join
Answer: b
Clarification: A preferred path is broken into two parts. One of them is known as top part while other is known as bottom part. To break a preferred path into two sets, cut operation is used at a particular node.
12. What is the upper bound for a tango tree if k is a number of interleaves?
a) k+2 O (log (log n))
b) k O (log n)
c) K2 O (log n)
d) k+1 O (log (log n))
Answer: d
Clarification: Upper bound is found to analyze the work done by a tango tree on a given set of sequences. In order to connect to the tango tree, the upper bound is found to be k+1 O (log (log n)).
13. What is the time complexity for searching k+1 auxiliary trees?
a) k+2 O (log (log n))
b) k+1 O (log n)
c) K+2 O (log n)
d) k+1 O (log (log n))
Answer: d
Clarification: Since each search operation in the auxiliary tree takes O (log (log n)) time as auxiliary tree size is bounded by the height of the reference tree that is log n. So for k+1 auxiliary trees, total search time is k+1 O (log (log n)).
14. What is the time complexity for the update cost on auxiliary trees?
a) O (log (log n))
b) k-1 O (log n)
c) K2 O (log n)
d) k+1 O (log (log n))
Answer: d
Clarification: The update cost also is bounded by the upper bound. We perform one cut as well as one join operation for the auxiliary tree, so the total update cost for the auxiliary tree is found to be k+1 O (log (log n)).
15. Which of the following is the self-adjusting binary search tree?
a) AVL Tree
b) Splay Tree
c) Top Tree
d) Ternary Tree
Answer: b
Clarification: Splay tree is a self – adjusting binary search tree. It performs basic operations on the tree like insertion, deletion, loop up performing all these operations in O (log n) time.