Non-Linear Data Structures: Trees, Binary Search Trees (BST), Heaps, Graphs & Sorting/Searching Algorithms - 2024 - Computer Application | Agrigyan

• Phylogenetic Tree Terminology:
• Branches or Edges: The connecting lines in a phylogenetic tree representing evolutionary lineages over time. (True)
• Internal Branch: A branch connecting two internal nodes (representing an ancestral lineage prior to subsequent divergence events). (True)
• Root: The basal node representing the unique common ancestor of all operational taxonomic units (taxa) present in the tree. (True)
• Conclusion: All (A), (B) and (C) are true (Option 4).

Correct option: (4) All (A), (B) and (C) are true.

• Number of Possible Unrooted Trees:
• For $n$ operational taxonomic units (taxa), the number of distinct unrooted bifurcating phylogenetic trees ($N_u$) is given by the double factorial formula:

$$N_u = (2n - 5)!! = 1 \times 3 \times 5 \times \dots \times (2n - 5)$$

• For $n = 5$ taxa:

$$N_u = (2 \times 5 - 5)!! = 5!! = 1 \times 3 \times 5 = 15$$

• (By comparison, the number of rooted trees for $n = 5$ is $(2n - 3)!! = 7!! = 105$).
• Conclusion: The number of unrooted trees for 5 OTUs is 15 (Option 2).

Correct option: (2) 15

• Linear vs. Non-linear Data Structures:
• Linear Data Structures: Elements are arranged sequentially where each element has a unique predecessor and successor (except first and last):
• Arrays, Lists, Linked Lists, Stacks, Queues.
• Non-linear Data Structures: Elements are arranged hierarchically or interconnected arbitrarily without a single sequential sequence:
• Tree: Hierarchical parent-child relationship.
• Graphs: Interconnected network of vertices and edges.
• Hash tables: Associative key-value mapping indexed via hash functions (non-sequential).
• List: Classic sequential linear data structure.
• Conclusion: (A), (B) and (C) only are non-linear data structures (Option 1).

Correct option: (1) (A), (6) and (C) only.