通信网络基础模拟试题五简答题（共 3 小题，每小题 20 分，共 60 分）1. 请写出生成树的定义，并简述生成树的构造过程。答案：【1】定义：对于图，包含了图 G 中所有顶点的树称为生成树。【2】对于一个给定的图 G = (V, E) ，其生成树的构造算法如下： （1）令 n 是 V 中的任意一个顶点，构造子图 G’= (V’,E’)，其中，V’={n}, E’=Æ｛空集｝；（2）如果 V’=V 则停止。此时 G’= (V’,E’)就是一个生成树。否则进行第 3）步；（3 ）令(i,j)ÎE，其中 iÎV’ , jÎV-V’ ，并 采 用下列方 式更新 V 和 V’ ：V’:=V’È{ j} ，E’:=E’È{(i, j)} ，转到第 2）步。 【3】该算法是从仅有一个顶点、0 条边的子图开始，以后每执行一次第 3）步就增加一个顶点和一条边。这就意味着最终生成的树有|v|个节点，|v|－1 条链路。评分标准：【1】、【3】各 4 分，【2】中（1）、（2）、（3）各 4 分。2. 请简要说明树形分裂算法。答案：【1】假设在第 k 个时隙发生碰撞，碰撞节点的集合为 S。所有未介入碰撞的节点进入等待状态。S 被随机的分成两个子集，用左集（L）和右集（R）表示。【2】左集（L）先在第k+1 时隙传输。如果第 k+1 时隙中传输成功或空闲，则 R 在第 k+2 时隙中传输。【2】如果在第 k+1 时隙中发生碰撞，则将 L 再分为左集（LL）和右集（LR），LL 在第 k+2 个时隙总传输。【3】如果第 k+2 时隙中传输成功或空闲，则 LR 在第 k+3 个时隙中传输。【4】以此类推，直至集合 S 中所有分组传输成功。【5】从碰撞的时隙（第 k 个时隙）开始，直至 S 集合中所有的分组成功传输结束的时隙称为一个冲突分解期（CRP）。以上过程可以用下图来加以说明。 评分标准：【1】、【2】、【3】、【4】、【5】各 3 分，示例图 5 分。3. 请简述漏斗式速率控制算法。答案：【1】假设有一个漏斗，不管水的流量如何，只要漏斗中有水，漏斗将以恒定的速率向外流水。而且，当漏斗装满水后，如果还向其注水，将导致注入的水从漏斗中溢出。只有当漏斗为空时，输出的速率才为 0。【2】这种思想也可以应用到分组传输的过程中。每台主机都可以通过一个类似于漏斗的接口与网络相连，即漏斗是一个容量有限的内部队列。如果分组到达队列时，队列满，则分组将被丢弃。只要队列的长度不为 0，分组就会以恒定的速率进入网络。【3】这种策略相当于将用户产生的非平稳的分组流变成了一个平稳的分组流，从而平滑了用户数据分组的突发性，进而大大降低了拥塞的机会。这种算法就被称为漏斗算法。【4】漏斗算法有两种实现方式：一种是针对分组长度固定的情况；另一种是针对可变长度分组的情况。如果分组长度固定，漏斗算法每隔一个固定的时间间隔输出一个分组。当分组的长度可变时，则漏斗算法每隔一个固定的间隔，输出一各固定数目的字节（或比特）。漏斗算法可以用下图来加以表示： 评分标准：【1】、【2】、【3】、【4】各 4 分，示例图 4 分。三、计算题（共 1 小题，每小题 20 分，共 20 分）1.一个通信链路的传输速率为 50kb/s，设分组到达该链路的过程服从 Poisson 分布，平均到达率为 600 分组/分钟，分组长度固定为 1000bit。求分组的平均等待时间。答：【1】由题意，该链路符合 M/D/1 排队模型，且=600 分组/分钟=10 分组/秒，分组的传输时间固定为 1/=1000/50000=0.02 秒，所以信道利用率=/=0.2，代入下式可求得分组的平均等待时间：【2】【3】 代入求得评分标准：答出【1】给 5 分，写出公式【2】给 5 分，正确计算【3】得 10 分，计算过程正确但是结果错误给 5 分，只有结果没有计算过程只能给 5 分。注：最后计算结果也可以写成 0.0025。