數(shù)據(jù)與計(jì)算機(jī)通信第七版課后習(xí)題答案(編輯修改稿)
2025-07-21 06:00 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 for i := 1 to V1 for each edge (u,v) in E //examine edge (u,v) if (d[u] + w(u,v) d[v]) d[v] := d[u] + w(u,v) p[u] := u end if end for end for for each edge (u,v) in E if (w(u,v) + d[u] d[v]) return (false, , ) //edge (u,v) was not minimized else … //edge (u,v) was minimized end for return (true, p, d)另解：TL(1)L(3)L(4)L(5)L(6)1{2}332∞∞2{2,4}3323∞3{2,4,1}3323∞4{2,4,1,3}332385{2,4,1,3,5}332356{1,2,3,4,5,6,}33235 Dijstra算法和Bellman算法總是能夠得到相同的結(jié)果；（1） Dijstra算法科得到一條最小路徑，則從其源端點(diǎn)到目的點(diǎn)必有一條路經(jīng)，于是BellmanFord算法必能找出此路徑，因此由Dijstra找出的最小路徑必可由BellmanFord找到。（2） 若由BellmanFord算法可得到一最小路徑，則不論其路徑數(shù)為多少，都必須經(jīng)過(guò)一定數(shù)目的結(jié)點(diǎn)，于是Dijstra算法又將遍歷所有結(jié)點(diǎn)，所以此路徑經(jīng)過(guò)結(jié)點(diǎn)都將由Dijstra描述過(guò)，則此路徑必將包括在Dijstra算法的結(jié)果中。實(shí)際上，BellmanFord算法類似于洪泛式的算法，而Dijstra則是按部就班，步步為營(yíng)，兩者方法不同，結(jié)果卻完全吻合。 證明： （1）當(dāng)n＝0時(shí)，顯然有； （2）假設(shè)當(dāng)n=k時(shí)，對(duì) 則顯然＝，否則，設(shè)存在一條更小的路徑，其頂點(diǎn)必由出發(fā)經(jīng)n頂點(diǎn)而到達(dá)j，顯然此頂點(diǎn)n落在，不然不為最小路徑，與已知相矛盾， 綜上所述，原命題成立。 另解：A. 3+9+2=14如下圖所示，按照洪泛的思想，從節(jié)點(diǎn)1發(fā)出的一個(gè)分組沿三條路徑向下一跳傳送，也就是說(shuō)在第一跳，原來(lái)的分組有三個(gè)副本，在圖中標(biāo)識(shí)為“I”。由于每個(gè)節(jié)點(diǎn)都會(huì)丟棄掉接收到的重復(fù)的分組，因此在第二跳總共形成9個(gè)副本，在圖中標(biāo)識(shí)為“II”。在第三跳總共有2個(gè)副本，在圖中標(biāo)識(shí)為“III”。所以總的代價(jià)為3+9+2=14。B. 3+9+22+45+103=182由于使用跳數(shù)字段，且其初始值為5。在第一跳時(shí)，生成了該分組的三個(gè)分組。當(dāng)這三個(gè)分組經(jīng)過(guò)第二跳時(shí)，共計(jì)生成9個(gè)副本。這9個(gè)副本經(jīng)過(guò)第三跳后，共計(jì)生成22個(gè)副本。這22個(gè)副本經(jīng)過(guò)第四跳后，共計(jì)生成45個(gè)副本。同樣這45個(gè)分組再經(jīng)過(guò)第五跳后共生成103個(gè)分組。所以總的代價(jià)為3+9+22+45+103=182。第10章補(bǔ)充作業(yè)：1. 對(duì)下圖采用Dijkstra算法計(jì)算節(jié)點(diǎn)1到節(jié)點(diǎn)6的最短通路樹，給出計(jì)算過(guò)程。TL(2)L(3)L(4)L(5)L(6){1}1,124,13{1,2}1,124,132,1244,125{1,2,4}1,123,1242,1243,12456,1246{1,2,3,4}1,123,1242,1243,12456,1246{1,2,3,4,5}1,123,1242,1243,12455, 12456{1,2,3,4,5,6}1,123,1242,1243,12455, 124562. 、三層都有流量控制，這一機(jī)制是否必要或者冗余呢？解答：兩者都是必要的。因?yàn)樵诘谌龑臃纸M中采用的流控和差錯(cuò)控制雖然在格式與處理上與HDLC相似，但因其分組中具有的D字段可以實(shí)現(xiàn)對(duì)于本地的或者是端對(duì)端的流控。而第二層的鏈路層則采用LAPB（HDLC的子集）來(lái)實(shí)現(xiàn)大多數(shù)的鏈路控制與數(shù)據(jù)傳輸，但不提供分組層中D字段具有的功能。3．，實(shí)際上是否需要這一機(jī)制來(lái)確保數(shù)據(jù)包被正確的傳遞了？解答：，但它作為PDU被傳遞到鏈路層是由鏈路層協(xié)議將其封裝為L(zhǎng)APB幀，從而加上了FSC字段，這樣可以確保傳輸LAPB幀中的數(shù)據(jù)域。4．，畢竟它們使用的是同一條全雙工的虛電路？解答：，同時(shí)建立4095條虛電路，所以兩個(gè)通信地站點(diǎn)雖然使用不同的虛電路號(hào)，但實(shí)際上是通過(guò)同一條虛電路進(jìn)行的通信，即使用復(fù)用的方法使一條物理鏈路為多個(gè)站點(diǎn)所使用。第13章的參考答案 什么叫擁塞控制？引起擁塞的原因以及需要進(jìn)行擁塞控制的原因有哪些？擁塞控制是指網(wǎng)絡(luò)中的分組數(shù)量維持在一定的水平之下，超過(guò)這個(gè)水平，網(wǎng)絡(luò)的性能就會(huì)急劇變化。擁塞的原因：在每一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)中，如果分組到達(dá)和排隊(duì)的速率超出分組能夠被傳輸?shù)乃俾剩?duì)列的長(zhǎng)度就
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1