A group of 15 routers is interconnected in a centralized complete binary tree…
2007
A group of 15 routers is interconnected in a centralized complete binary tree with a router at each tree node.Router i communicates with router j by sending a message to the root of the tree. The root then sends the message back down to router j.The mean number of hops per message, assuming all possible router pairs are equally likely is
Answer: C. 4.53 — A complete binary tree with 15 nodes spans four levels (depths 0 to 3). The number of nodes at each depth d is 2^d. Sum of depths = 1(0) + 2(1) + 4(2) + 8(3)…
- A.
3
- B.
4.26
- C.
4.53
- D.
5.26
Attempted by 110 students.
Show answer & explanation
Correct answer: C
A complete binary tree with 15 nodes spans four levels (depths 0 to 3). The number of nodes at each depth d is 2^d.
Sum of depths = 1(0) + 2(1) + 4(2) + 8(3) = 0 + 2 + 8 + 24 = 34.
Average depth = 34/15. Since messages route through the root, mean hops = 2 * average depth.
Mean hops = 2 * (34/15) = 68/15 ≈ 4.53.
A video solution is available for this question — log in and enroll to watch it.
Explore the full course: Iocl Engineers Officers Grade A Paper 2