Tango Tree Multiple Choice Questions and Answers (MCQs)

«
»

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses 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
View Answer

Answer: d
Explanation: 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.
advertisement

2. Which type of tree is tango tree?
a) Ternary Tree
b) AVL Tree
c) Binary Search Tree
d) K-ary Tree
View Answer

Answer: c
Explanation: 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
View Answer

Answer: b
Explanation: 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.
advertisement
advertisement

4. Which type of binary search tree or algorithm does tango tree use?
a) Online
b) Offline
c) Static
d) Dynamic
View Answer

Answer: d
Explanation: 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))
View Answer

Answer: d
Explanation: 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.
advertisement

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
View Answer

Answer: a
Explanation: 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
View Answer

Answer: a
Explanation: 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.
advertisement

8. Is tango tree represented as a tree of trees.
a) True
b) False
View Answer

Answer: a
Explanation: 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
View Answer

Answer: a
Explanation: 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.
advertisement

10. Is partitioning method used by Tango Tree.
a) True
b) False
View Answer

Answer: a
Explanation: 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
View Answer

Answer: b
Explanation: 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))
View Answer

Answer: d
Explanation: 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))
View Answer

Answer: d
Explanation: 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))
View Answer

Answer: d
Explanation: 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
View Answer

Answer: b
Explanation: 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.

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter