Engineering Questions with Answers - Multiple Choice Questions

# Tango Tree MCQ’s

1 - Question

Who developed the concept of tango tree?
a) Erik Demaine
b) Mihai Patrascu
c) John Lacono
d) All of the mentioned

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.

2 - Question

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

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 - Question

After which city is tango tree named?
a) Vatican City
b) Buenos Aires
c) New York
d) California

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.

4 - Question

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

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 - Question

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))

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.

6 - Question

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

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 - Question

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

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.

8 - Question

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

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 - Question

Which operation is used to combine two auxiliary trees?
a) Join
b) Combinatorial
d) Concatenation

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.

10 - Question

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

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 - Question

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

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 - Question

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))

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 - Question

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))

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 - Question

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))

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 - Question

Which of the following is the self-adjusting binary search tree?
a) AVL Tree
b) Splay Tree
c) Top Tree
d) Ternary Tree