并行计算(陈国良版)课后答案

第三章 互连网络3.1 对于一颗K级二叉树（根为0级，叶为k-1级），共有N=2^k-1个节点，当推广至m-元树时（即每个非叶节点有m个子节点）时，试写出总节点数N的表达式。 答： 推广至M元

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