精品文档第三章互连网络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的超立方比较之，你的结论是什么？答：AN=64的立方环网络,为4立方环（将4维超立方每个顶点以4面体替代得到），直径d=9，节点度n=4BN=64的超立方网络，为六维超立方（将一个立方体分为8个小立方，以每个小立方作为简单立方体的节点，互联成6维超立方），直径d=6，节点度n=6所示，令网络如图3.483.5一个N=2^k个节点的deBruijinaaaaa，是一个。。。10k?2?k13k?aaaaaaaa1。。0，。节点的二进制表示，则该节点可达如下两个节点：。。。。11030?k3k?k?2k?2试问：该网络的直径和对剖宽度是多少？答：N=2^k个节点的deBruijin网络直径d=k对剖宽带w=2^(k-1)3.6一个N=2^n个节点的洗牌交换网络如图3.49所示。试问：此网络节点度==？网络直径==？网络对剖宽度==？答：N=2^n个节点的洗牌交换网络，网络节点度为=2，网络直径=n-1，网络对剖宽度=43.7一个N=（k+1）2^k个节点的蝶形网络如图3.50所示。试问：此网络节点度=？网络直径=？网络对剖宽度=？答：N=（k+1）2^k个节点的蝶形网络，网络节点度=4，网络直径=2*k，网络对剖宽度=2^k3.9对于如下列举的网络技术，用体系结构描述，速率范围，电缆长度等填充下表中的各项。（提示：根据讨论的时间年限，每项可能是一个范围）答：网络技术光纤距离铜线距离带宽网络结构精品文档．精品文档Myrinet1LDW21314LDW5LDW215专用机群互联网络STW0顾客秒200MB/远程主机25mSTW7500mHiPPI23如果高速缓存行不在本地，则确定位用于异构计算机和其外设的组网LDW6置，发送请求800Mbps~1.6GbpsLDW2LDW725m300m~10kmSCI45通常独立可扩展一致性接口，于拓扑结构LDW2接收回答，访问数据250Mbps~8GbpsLDW0STW2接收请求，发送高速缓存行光纤通信67多处理器和其外围设备之间，直连结构LDW2STW2100Mbps~800MbpsLDW550mLDW510kmATM89主要应用于因特网主干线中STW525Mbps~10GbpsLDW3LDW7FDDI101112所有结采用双向光纤令牌环，点联接在该环中LDW7100-200MbpsLDW6LDW2100mLDW2STW72KM占。此时片0C，D要分别去向目的地2，3A，B，3.10如图3.51所示，信包的片0，1，BA。试问：，片3占据信道1占据信道DC，片2占据信道AD据信道CB，片）这将会发生什么现象？1）如果采用X-Y选路策略，可避免上述现象吗？为什么？2）通路中形成环，发生死锁答：1策略时其实质是对资源（这里X-Y）如果采用X-Y策略则不会发生死锁。因为采用2，方向）方向优先于x方向优先于y方向，反方向路由是y进行按序分配是通道）（永远是x因此根据死锁避免的原则判断，此时不会发生死锁。选路等价的查表路由。在二维网孔中，试构造一个与X-Y3.12所构造路由表描述如下：答：y表x1）每个节点包括两张路由表表和表】y3，2:【2，2】【】2）每个节点包含其以后节点信息，如节点【1，2x表内容为】1，3内容为：【选路方法：方向路由，如果查表能指明下一跳方向则直xx表即进行节点路由时进行查表：先查表，直到到达目的地。接进入下一跳。如果不能则继续查y对称多处理机系统第四章PP策略将包策略进程从时，或采用迁移到WB4.1参照图4.20，试解释为什么采用WT12PP迁移到时，会造成高速缓存的不一致。含共享变量X的进程从12处理器PPPPPP221112XX'X高速缓存XX'总线共享XXX'存储器之前迁移写过写通回进程迁移所造成的不一致性图4.20精品文档．精品...