Top Tree Multiple Choice Questions and Answers (MCQs)

«
»

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Top Tree”.

1. Which algorithm is used in the top tree data structure?
a) Divide and Conquer
b) Greedy
c) Backtracking
d) Branch
View Answer

Answer: a
Explanation: Top tree is a type of data structure which is based on unrooted dynamic binary tree and is used to solve path related problems. It allows an algorithm called divide and conquer.
advertisement

2. For how many vertices in a set, is top tree defined for underlying tree?
a) 3
b) 4
c) 5
d) 2
View Answer

Answer: d
Explanation: Top tree is defined for a set having a maximum of 2 vertices for its underlying tree. Those sets having at maximum 2 vertices is called External Boundary Vertices.

3. How many edges are present in path cluster?
a) 2
b) 3
c) 6
d) 1
View Answer

Answer: a
Explanation: There are at least 2 edges present in path cluster. Cluster in data structure is defined as the subtree that is connect having maximum of 2 vertices known as Boundary Vertices.
advertisement
advertisement

4. How many edges does a leaf cluster contain?
a) 0
b) 1
c) 2
d) 3
View Answer

Answer: a
Explanation: If a cluster has no edges and contains only one vertex known as boundary vertex then, it is known as leaf cluster. So a leaf cluster doesn’t contain any edges. It is also known as Point cluster.

5. How many edges are present in Edge cluster?
a) 0
b) 1
c) 2
d) 4
View Answer

Answer: b
Explanation: A cluster containing only single edge is known as Edge cluster. So there are in total 1 edge present in edge cluster. Cluster in data structure is defined as the subtree that is connect having maximum of 2 vertices known as Boundary Vertices.
advertisement

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

Answer: a
Explanation: Top tree data structure is used to maintain a dynamic forest using link or cut operations. Top tree is a type of data structure which is based on unrooted dynamic binary tree and is used to solve path related problems.

7. If A ꓵ B (A and B are two clusters) is a singleton set then it is a Merge able cluster.
a) True
b) False
View Answer

Answer: a
Explanation: If A ꓵ B is a singleton set where A and B are two clusters, that is there are only one node that is common between the clusters then they are known as Merge able cluster.
advertisement

8. Is Top tree used for maintaining Dynamic set of trees called forest.
a) True
b) False
View Answer

Answer: a
Explanation: Top tree data structure is used to maintain a dynamic forest using link or cut operations. Top tree is a type of data structure which is based on unrooted dynamic binary tree and is used to solve path related problems.

9. What is the time complexity for the initialization of top tree?
a) O (n)
b) O (n2)
c) O (log n)
d) O (n!)
View Answer

Answer: a
Explanation: Generally, trees have weight on its edges. Also there is one to one correspondence of the edges with the top trees. Therefore, top trees can be initialized in O (n) time.
advertisement

10. How many top trees are there in a tree with single vertex?
a) 0
b) 1
c) 2
d) 3
View Answer

Answer: a
Explanation: Tree having a single vertex has no clusters of tree present in the structure. Therefore, there are empty top trees in a tree having a single vertex. Trees with one node are single node.

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

Answer: d
Explanation: Top tree can be considered as a binary tree if the nodes form a cluster, leaves act as an edge and the root of the top tree acts as a tree itself. Then the top tree is called binary tree.

12. Which of the dynamic operations are used in Top Tree data structure implementation?
a) Link
b) Cut
c) Expose
d) All of the mentioned
View Answer

Answer: d
Explanation: Link returns a single tree having different vertices from top trees. Cut removes the edge from the top tree. Expose is used to implement queries on top trees. Hence all of the options are used as dynamic operations.

13. Which of the following are used as an internal operation in Top tree?
a) Merge
b) Cut
c) Expose
d) Link
View Answer

Answer: a
Explanation: Link returns a single tree having different vertices from top trees. Cut removes the edge from the top tree. Expose is used to implement queries on top trees. While merge is an internal operation used to merge two clusters and return as a parent cluster.

14. 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!)
View Answer

Answer: c
Explanation: A lot of applications have been implemented using Top tree interface. Maintaining a dynamic set of weighted trees is one such application which can be implemented with O (log n) time complexity.

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