1 第三章 互连网络 3.1 对于一颗K 级二叉树（根为0 级，叶为k-1 级），共有N=2^k-1 个节点，当推广至m-元树时（即每个非叶节点有m 个子节点）时，试写出总节点数N 的表达式。 答： 推广至M 元树时，k 级M 元树总结点数N 的表达式为： N=1+m^1+m^2+...+m^（k-1）=(1-m^k)*1/(1-m); 3.2 二元胖树如图 3.46 所示，此时所有非根节点均有2 个父节点。如果将图中的每个椭圆均视为单个节点，并且成对节点间的多条边视为一条边，则他实际上就是一个二叉树。试问：如果不管椭圆，只把小方块视为节点，则他从叶到根形成什么样的多级互联网络？ 答：8 输入的完全混洗三级互联网络。 3.3 四元胖树如图 3.47 所示，试问：每个内节点有几个子节点和几个父节点？你知道那个机器使用了此种形式的胖树？ 答：每个内节点有4 个子节点，2 个父节点。CM-5 使用了此类胖树结构。 3.4 试构造一个N=64 的立方环网络，并将其直径和节点度与 N=64 的超立方比较之，你的结论是什么？ 答：A N=64 的立方环网络,为4 立方环（将 4 维超立方每个顶点以 4 面体替代得到），直径d=9，节点度 n=4 B N=64 的超立方网络，为六维超立方（将一个立方体分为8 个小立方，以每个小立方作为简单立方体的节点，互联成 6 维超立方），直径 d=6，节点度 n=6 3.5 一个N=2^k 个节点的 de Bruijin 网络如图 3.48 所示，令ak 1 ak 2 ak 3 。。。a1 a0 ，是一个节点的二进制表示，则该节点可达如下两个节点：ak 2 ak 3 。。。a1 a0 0，ak 2 ak 3 。。。a1 a0 1。试问：该网络的直径和对剖宽度是多少？ 答：N=2^k 个节点的 de Bruijin 网络 直径 d=k 对剖宽带 w =2^(k-1) 3.6 一个N=2^n 个节点的洗牌交换网络如图 3.49 所示。试问：此网络节点度==？网络直径==？网络对剖宽度==？ 答：N=2^n 个节点的洗牌交换网络，网络节点度为=2 ，网络直径=n-1 ，网络对剖宽度=4 3.7 一个N=（k+1）2^k 个节点的蝶形网络如图 3.50 所示。试问：此网络节点度=？网络直径=？网络对剖宽度=？ 答：N=（k+1）2^k 个节点的蝶形网络，网络节点度=4 ，网络直径=2*k ，网络对剖宽度=2^k 3.9 对于如下列举的网络技术，用体系结构描述，速率范围，电缆长度等填充下表中的各项。（提示：根据讨论的时间年限，每项可能是一个范围） 答： 网络技术 网络结构 带宽 铜线距离 光纤距离 2 Myr...
VIP
