清華大學計算機系統(tǒng)結(jié)構(gòu)課后習題解答

1、計算機系統(tǒng)結(jié)構(gòu)習題解答目錄第一章 (P33)1.7-1.9（透明性概念），1.12-1.18（Amdahl 定律）， 1.19 、1.21 、 1.24 （CPI/MIPS）第二章 (P124)2.3 、2.5 、2.6 （浮點數(shù)性能） ，2.13 、2.15 （指令編碼）第三章 (P202)3.3 （存儲層次性能） ， 3.5 （并行主存系統(tǒng)） ，3.15-3.15 加 1 題（堆棧模擬）， 3.19 中(3)(4)(6)(8) 問（地址映象 / 替換算法 - 實存狀況圖）第四章 (P250)4.5 （中斷屏蔽字表 / 中斷過程示意圖） ， 4.8 （通道流量計算/ 通道時間圖）第五章 (P

2、343)5.9 （流水線性能 / 時空圖），5.15 （ 2 種調(diào)度算法）第六章 (P391)6.6 （向量流水時間計算） ， 6.10 （Amdahl 定律 /MFLOPS）第七章 (P446)7.3 、7.29 （互連函數(shù)計算） ，7.6-7.14（互連網(wǎng)性質(zhì)）， 7.4 、7.5 、7.26 （多級網(wǎng)尋徑算法） ，7.27 （尋徑 / 選播算法）第八章 (P498)8.12 （SISD/SIMD 算法）第九章 (P562)9.18 （SISD/ 多功能部件 /SIMD/MIMD 算法）( 注：每章可選1-2 個主要知識點，每個知識點可只選1 題。有下劃線者為推薦的主要知識點。)1第一章

3、(P33)1.7(1) 從指定角度來看，不必要了解的知識稱為透明性概念。(2) 見下表，“”為透明性概念， “ P”表示相關(guān)課文頁數(shù)。模 m 交叉，浮點數(shù)據(jù)，×， P4通道與 I/O 處理機，×， P4總線寬度，陣列運算部件，×，結(jié)合型與獨立型通道，單總線，訪問保護，×，中斷，×，指令控制方式，堆棧指令，×，最小編址單位，×，Cache 存儲器，1.8 見下表，“”為透明性概念， “P”表示相關(guān)課文頁數(shù)。指令地址寄存器，×，指令緩沖器，時標發(fā)生器，條件碼寄存器，×，乘法器，主存地址寄存器，磁盤，×

4、;，先行進位鏈，移位器，通用寄存器 ，×，中斷字寄存器，×，1.9 見下表，“”表示都透明， “應(yīng)”表示僅對應(yīng)用程序員透明，“×”表示都不透明。數(shù)據(jù)通路寬度，虛擬存儲器，應(yīng)，Cache 存儲器，程序狀態(tài)字，×，“啟動 I/O ”指令，應(yīng)，“執(zhí)行”指令，×，指令緩沖寄存器，1.12 已知 Se=20 , 求作 Fe-Sn 關(guān)系曲線。Sn將 Se 代入 Amdahl 定律得201Sn1 19 Fe1201.13 上式中令 Sn=2，解出 Fe=10/19 0.52601 Fe1.14上式中令Sn=10，解出 Fe=18/19 0.9471.15已知

5、兩種方法可使性能得到相同的提高，問哪一種方法更好。(1) 用硬件組方法，已知 Se=40， Fe=0.7 ，解出 Sn=40/12.7 3.1496 （兩種方法得到的相同性能）(2) 用軟件組方法，已知 Se=20， Sn=40/12.7 ，解出 Fe=27.3/38 0.7184 （第二種方法的百分比）(3) 結(jié)論：軟件組方法更好。 因為硬件組需要將Se 再提高 100%（2040），而軟件組只需將Fe 再提高 1.84%（0.7 0.7184 ）。1.17Sn153.570.91.40.1521.18記 f時鐘頻率， T=1/f時鐘周期， B 帶寬（ Byte/s ）。方案一： B1144

6、 f (Byte / s)T方案二： B275% 2 25% 1 4 3.5 f (Byte / s)2T1.19由各種指令條數(shù)可以得到總條數(shù)，以及各百分比，然后代公式計算。4105ICIC ii14IC i(1)CPI(CPI i)10.4520.322 0.15 2 0.08 1.55i1IC(2)MIPSf401064025.806CPI1061.5510 61.55(3)TIC1.550.003876（秒）MIPS 1064001.21(1)CPI10.620.1840.1280.12.24(2)MIPSf4010617.86CPI1062.2410 61.24記 Tc 新方案時鐘周期

7、，已知CPI = CPI i = 1原時間 = CPI× IC× 0.95Tc = 0.95IC× Tc新時間 =（ 0.3 × 2/3+0.7 ）× IC× Tc = 0.9IC×Tc二者比較，新時間較短。第二章 (P124)2.3 （忽略 P124 倒 1 行 P125 第 8 行文字，以簡化題意）已知2 種浮點數(shù)，求性能指標。此題關(guān)鍵是分析階碼、尾數(shù)各自的最大值、最小值。原圖為數(shù)據(jù)在內(nèi)存中的格式，階碼的小數(shù)點在其右端，尾數(shù)的小數(shù)點在其左端，遵守規(guī)格化要求。由于尾數(shù)均為原碼，原碼的絕對值與符號位無關(guān)，所以最大正數(shù)與最小負

8、數(shù)的絕對值相同，可用“±最大絕對3值”回答；最小正數(shù)與最大負數(shù)的絕對值相同，可用“±最小絕對值”回答。第 1 小問中，階碼全部位數(shù)為8，作無符號數(shù)看待真值為0 255，作移 -127 碼看待真值為 -127 +128；尾數(shù)（不計符號位）有23 位小數(shù)，另加1 位整數(shù)隱藏位，所以尾數(shù)絕對值為1.02.02 -23 ，有效位數(shù) p=24；第 2 小問中，階碼全部位數(shù)為11，作無符號數(shù)看待真值為0 2047，作移 -1023碼看待真值為 -1023 +1024；尾數(shù)（不計符號位）有 52 位小數(shù)，另加 1 位整數(shù)隱藏位，所以尾數(shù)絕對值為1.0 2.0 2 -52 ，有效位數(shù) p=

9、53。最大絕對值為最大階碼與最大尾數(shù)絕對值的組合，最小絕對值為最小階碼與最小尾數(shù)絕對值的組合。代入相關(guān)公式后得最終結(jié)果如下表。32 位64 位±最大絕對值± (1-2 -24 ) ·2129±(1-2-53 ) · 21025±最小絕對值-127-1023± 2±2表數(shù)精度 -24-5322表數(shù)效率 100%100%2.5(1) r m = 2 ，r e = 2， p = 24 （隱藏最高位） ,q = 7。(2) N max = 1.7 ×1038 ，-|N| min = -1.47× 10-

10、39 5.96 ×10-8 10 -7.22， = 100%2.6(1) 0.2 = 0.333333H×1601 位7 位6 位設(shè)階碼為移 -63 碼（即 -2 6+1，原題未指明）001111113333330.2 = 0.110011001100110011001101B × 2-2（其中最高有效位需隱藏）1 位8 位23 位階碼為移 -127碼（即 -2 7+1）00111110110011001100110011001101(2) 符號位不變，（階碼 63 ）× 4 + 127 ；尾數(shù)左規(guī)，除去最高位；(3)符號位不變，（階碼127 ）/ 4

11、+ 63；尾數(shù)補最高位，按除法余數(shù)右移若干位，左補0。2.13已知 10 條指令使用頻度，求3 種編碼方法的平均碼長與信息冗余量。(1) 此問中的“最優(yōu)Huffman 編碼法”實際是指碼長下限，即信源的平均信息量熵，代公式得H=2.9566。(2)Huffman編碼性能如下表；(3)2/8擴展編碼是8/64/512法的變種，第一組2 條指令，碼長為2（1 位擴展標志， 1 位編碼） , 第二組 8 條指令，碼長為4（ 1 位擴展標志，與第一組區(qū)別，加3 位編碼），編碼性能如下表；(4)3/7擴展編碼是15/15/15法的變種，第一組3 條指令，碼長為2（共有 4 種組合，其中3 種組合分別代表

12、3條指令， 留 1 種組合作為擴展前綴標志）, 第二組 7 條指令，碼長為 5（ 2 位固定的前綴擴展標志，與第一組區(qū)別，加 3 位編碼，只用其中7 種組合），編碼性能如下表。Huffman 編碼2/8 擴展編碼3/7 擴展編碼平均碼長 L2.993.13.2信息冗余量R1.10%4.61%7.59%42.15(1) 15 條/63 條/64 條(2) 14 條/126 條 /128 條第三章 (P202)3.3直接代公式計算存儲層次性能指標。(1)74ns ，38ns， 23.6ns(2)0.258，0.315 ，0.424(3)T256K < T128K < T64Kc256K

13、 > c128K > c64K(4)19.092， 11.97 ，10.0064 。答案是256K 方案最優(yōu)。1(1 g )n3.5 已知 K ng，其中 g=0.11(1g)n 1K n 0.21 (1 g)n依題意有 K n 1gg0.2整理得 0.9 n 0.2 ，解出 nlg 0.215.28，向下取整，得15；lg 0.9按另一種題意理解是向上取整，得16，也對。3.15 欲知可能的最高命中率及所需的最少主存頁數(shù)，較好的辦法是通過“堆棧模擬法”，求得命中次數(shù)隨主存頁數(shù)變化的函數(shù)關(guān)系。下圖就是“堆棧模擬圖”，其中“”表示命中。P=453251323513命中次數(shù)453251

14、3235134532513235145325112354432551224444444n=10n=21n=33n=47n=57(1)H max=7/12 58.3%(2)n=4(3) 當 1 次頁面訪問代表連續(xù)1024次該頁內(nèi)存儲單元訪問時，后1023 次單元訪問肯定是命中的，而第1 次單元5訪問的命中情況與這1 次頁面訪問的命中情況相同。根據(jù)上圖中最高命中情況，共有 7 次頁命中（折算為 7× 1024次單元命中），5 次頁不命中 （折算為 5× 1023 次單元命中， 也可寫為5×1024-5 ），單元訪問總次數(shù)為12× 1024，故有：Hcell

15、=(12 ×1024-5)/(12×1024)=12283/12288 99.96%3.15 加 1 題 一個二級存儲層次，采用全相聯(lián)映象與最久沒有使用算法，實存共5 頁，為 2 道程序分享，頁地址流分別如下P1=12341321P2=12342233試作 2 個實存分配方案，分別使2 道程序滿足(1) 命中率相同；(2) 命中次數(shù)之與最大。解：分別為2 道程序作“堆棧模擬圖” ，其中“”表示命中。112341321(1)P =命中次數(shù) N12341321123413212341312244n1 = 1010n = 221n = 3n1 = 44P2 =12342233命中

16、次數(shù) N(2)1234223312344221233441111122n = 122n = 2n2 = 3424n = 4將兩圖結(jié)果綜合，得到4 個分配方案的命中率情況表如下112346n0024N(1)+N(2)(1)5N4n243213N(1)N(2)N(2)44222(2)12+33+24+1(1)44461+4N +N結(jié)論如下(1) 命中率相同的方案是n1= 3 而 n2= 2；6(2) 命中次數(shù)之與最大的方案是n1= 4 而 n2 = 1。3.19 中(3)(4)(6)(8)問(3)虛存實頁0123虛組 0001實存1虛組 12·0實組 023·1虛 3虛組 24

17、·2實組 1頁 45·35虛組 36677(a) 虛頁集合與實頁集合的對應(yīng)關(guān)系(b) 對應(yīng)關(guān)系表（為有關(guān)系）(4) 通過作“實存狀況圖”模擬各虛塊的調(diào)度情況，可獲得Cache 的塊地址流序列。P=624146304573C044*4444*44*4*4*C111*1*1*00*555C266*6*6*6*66*6*6*6*77*C322222*33333*3入入入入中中替替中替替中C=230102310123此問最容易出錯的地方是忽略“組相聯(lián)”地址約束，將虛頁裝錯實組。另外沒有及時標注“* ”號也容易導(dǎo)致淘汰對象錯誤。(6)H=4/12 33%(8)做法同 3.15題 (3

18、) 問， Hcell =(12 × 16-8)/(12 × 16) 95.8%第四章 (P250)4.5已知中斷服務(wù)次序為3-2-4-1 ，。(1)中斷屏蔽字表如下圖；時間中斷請求主程序1 級2 級3 級4 級(2)中斷過程示意圖如右圖。D1 ，D2D1D2D3D4D3 ，D4D10111D20010D30000D4011074.8(1)f=2 × 105 字節(jié) / 秒， T=5us(2)Ts+Td=5us ，通道時間圖如下。作圖時注意： 至少要畫到最慢設(shè)備的第二次請求出現(xiàn)，才能確定是否丟失數(shù)據(jù)（因為響應(yīng)優(yōu)先級低的設(shè)備較易丟失數(shù)據(jù)）。設(shè)優(yōu)備先號級D11D24D32

19、D43時間(us)0102030405060708090100110120130140150160170(3)5 ，160， 20， 40；(4)D2 丟失第一次請求的數(shù)據(jù)；(5) 參見 P245。第五章 (P343)5.9為了縮短運算時間，首先應(yīng)考慮“最少切換算法”，即先執(zhí)行完所有乘法（任務(wù)編號1-6 ）再執(zhí)行加法（任務(wù)編號 7-11 ），其次在加法中采用“最少相關(guān)算法”（即二叉樹算法） 。記 c 1=A1×B1 ， ，c6 =A6×B6，下圖 (a) 是加法的計算順序二叉樹，注意任務(wù)10 應(yīng)該用前一級最早完成的任務(wù)7 與 8 的結(jié)果，如果用任務(wù)9 的結(jié)果則要推遲1 拍啟

20、動，使總時間增加1 拍。F=c1+c2+c3+c4+c5+c6 6123456789101151234567894123456378910111027891011112345678910111101234567891214 151822(a)(b)8根據(jù)時空圖 (b) 得TP = 11/(22t) = 1/(2t)S=(6×4t + 5× 4t)/(22t) = 2E=(6×4t + 5× 4t)/(6×22 t) = 1/35.15t=10ns=10 -8 秒(1)F=1 ，2， 5 ， C=(10011)(2) 狀態(tài)轉(zhuǎn)移圖如下圖 (a) 所

21、示。(3) 最小啟動循環(huán) =（3）, 最小平均啟動距離 =3 t 。(4) 插入 2 個延遲，最小啟動循環(huán) =（ 2） , 最小平均啟動距離 =2 t 。(5) 新預(yù)約表如下圖 (b) 所示。(6)F=1 ，3， 7 ， C=(1000101) ，狀態(tài)轉(zhuǎn)移圖如下圖(c) 所示。12345678初態(tài)4， 6， 8S1×12 ×初態(tài)3，4， 6S2×1 ×1000101S3×4， 6， 84， 6， 810011S41 × ×2 5D1×10101011000111D2×25(a)(b)(c)(7) 插入前

22、TPmax = 1/3t = 1/30ns，插入后 TPmax = 1/2t = 1/20ns。(8) 插入前 TP = 10/33t = 1/33ns，插入后 TP = 10/26t = 1/26ns，如下圖所示。9S41122310 10S312310S2112231010S11213210103t(a)9× 36D 212311D 1123410S411223310 10S3123410S2121324351010S1123415210102t(b)9× 2810第六章 (P391)6.6 （注意閱讀P372 倒數(shù)第 9 行倒數(shù)第6 行）已知 n=32，k 加=6，k

23、 乘 =7，k 訪存 =6， k 倒數(shù) =14，啟動、輸出延遲各1。求各小題總拍數(shù)。(1) V0 存儲器(2) V2 V0 * V1并行V1 V2+V3并行V3 存儲器V4 V5 * V6V4 V2 + V3串行（ P372）訪存乘加訪存乘加9319318 31總拍數(shù) =40（并行執(zhí)行，以最長指令為準）總拍數(shù) =79（第 3 條錯過時機，不能鏈接）(3) V0 存儲器并行(4) V0 存儲器鏈接V3 V1+V2鏈接V1 1/V0鏈接V4 V0*V3V3 V1+V2鏈接V6 V4+V5串行V5 V3*V4訪存訪存加倒數(shù)乘加8 931831乘8168931總拍數(shù) =87（第 4 條功能部件沖突）總

24、拍數(shù) =72（各條依次鏈接）11(5) V0 存儲器(6) V3 存儲器并行V1 V2+V3并行V2 V0+V1串行V4 V5 * V6s0 s2 + s3并行s0 s1 + s2串行V3 V1 * V4訪存訪存加加乘乘9318831931總拍數(shù) =48（標量看成1 個分量的向量）總拍數(shù) =79（標量看成1 個分量的向量）(7) V3 存儲器并行(8) V0 存儲器鏈接V2 V0+V1鏈接V2 V0+V1V4 V2*V3V3 V2* V1串行存儲器 V4串行V5 V3* V4串行訪存訪存加加乘乘89318318831931931總拍數(shù) =87（第 4 條功能部件沖突）總拍數(shù) =127（ Vi

25、沖突，功能部件沖突）6.10已知向量速率Rv = 10MFLOPS，標量速率Rs = 1MFLOPS，并記 為可向量化百分比。(1) 推導(dǎo)法 1：使用 Amdahl 定律，在這里可將標量速率Rs 作為原速率，局部加速后的速率為向量速率Rv，于是局部加速比 Se=10，全局加速比為Sn1(1)SeR，所以有 RRsRs1再根據(jù)加速比的定義， SnSn1MIPS 。Rs(1 )0.9Se12（若將向量速率Rv 作為原速率，局部減速后的速率為標量速率Rs，則局部加速比Se=0.1 ，推出的全局加速比Sn 同上式。）推導(dǎo)法 2：為了推導(dǎo)，定義T 為總時間， N為總?cè)蝿?wù)數(shù)。于是有平均速率Ra = 吞吐率

26、 TP = N/T。記 N = Nv + Ns，且N vNv，則1N sN s，于是有 Nv = · N 與 Ns = (1- ) · NN N vN sNN vN s顯然：總時間 TTvTsNvN sN(1) NRvRsRvRsNN1所以：RaN(1) N11T(1RvRs)RvRs或者：11(1)1RaRvRs(2)已知 Rv = 10MFLOPS，Rs = 1MFLOPS，Ra(MFLOPS)11010RaMFLOPSMFLOPS(190.1)10Ra 與 的關(guān)系圖如右圖所示。1(3)已知 Ra = 7.5MFLOPS，解出01 10110130.9696%(1)91

27、597.5(4) 已知 Ra = 2MFLOPS， = 0.7 ，解出Rv0.73.5( MFLOPS )111(1 )Rs0.3 1Ra2第七章 (P446)7.3已知輸入端編號13 = 1101B 。(1)Cube3(1101B) = 0101B = 5(2)PM2 +3(13)= (13+ 23 )mod 16= 21 mod 16 = 5(3)PM2 +0(13)= (13- 20 )mod 16= 12(4)Shuffle(1101B) = 1011B = 11(5)Shuffle(Shuffle(1101B) = Shuffle(1011B) = 0111B = 77.4用多級混洗

28、交換網(wǎng)絡(luò)，n = 4 ，拓撲結(jié)構(gòu)同教材P410 圖 7.21(e) ，控制信號 =1010B，自左向右各級交換開13關(guān)狀態(tài)依次為交換直連交換直連。7.5輸入結(jié)點編號j = 9，f(j) = j控制信號= 1001B 1100B = 0101B = 5，答為 5 號處理機。7.6直連狀態(tài)時：編號在第 i 位不同的結(jié)點之間不能通信；交換狀態(tài)時：編號在第 i 位相同的結(jié)點之間不能通信。7.7 用單級混洗交換網(wǎng)可實現(xiàn)，總共混洗3 步。證：設(shè)矩陣 A = (a ij )8× 8 按行展開依次存放在64 個單元中，則任意元素aij 的地址為 8i +j ，而 aji的地址為 8j+i 。按混洗函

29、數(shù)的定義， 3 次混洗后， shuffle3 (8i + j) = 8×(8i + j) mod 63 = i + 8j，也就說將元素 aij地址變換成 aji 的地址。由于 aij 是矩陣中的任意元素，所以3 次混洗可實現(xiàn)矩陣轉(zhuǎn)置(a ij ) T8× 8=(a ji ) 8× 8 。7.8 最多 5 級，因為對于任給的輸入結(jié)點編號j=X 6 X5 X4 X3X2X1X0，PM2I 多級網(wǎng)絡(luò)中 i=2級的功能是 PM2± 2(j)=j ± 22 mod128 ，± 22 運算只有可能改變j 中的 X6 X2，所以最多使用Cube6

30、Cube2 就能實現(xiàn)代換了。7.9 由于 N = 16 ，即 n = 4，每個結(jié)點編號用4 位二進制數(shù)表示。 PM2± 0 函數(shù)功能是對結(jié)點編號加1 或減 1，其結(jié)果最多可將編號的4 位都取反（如 1111B + 1 = 0000B），所以用每步只能對1 位取反的單級立方體網(wǎng)絡(luò)來模仿，最差情況下要 4步。7.10用混洗交換網(wǎng)絡(luò)模擬Cube網(wǎng)。當模擬 Cube0 功能時，只需一次交換即可完成；而模擬Cubei 且 i 0 時，需先作n i 步混洗，再作1 步交換，最后作 i 步混洗才能完成，共計n + 1步。綜上所述，下限為1 步，上限為n + 1步。7.11求單級立方體網(wǎng)絡(luò)與單級混洗

31、交換網(wǎng)絡(luò)的最大廣播步數(shù)，這兩種網(wǎng)絡(luò)的最大廣播步數(shù)與最大距離（即直徑）相同。(1) 單級立方體網(wǎng)絡(luò)直徑 = n （ Cuben-1 Cube0 各 1 次）；(2) 單級混洗交換網(wǎng)絡(luò)直徑 = 2n-1 （n-1 次混洗， n 次交換）。7.12 已知 N = 16 ，用多級立方體網(wǎng)絡(luò)或者多級混洗交換網(wǎng)絡(luò)均能實現(xiàn)，兩者可以互相模擬，對同一置換的尋徑算法相同，控制信號也相同，下面以多級立方體網(wǎng)絡(luò)為例分析。4 組 4 元交換： f 1 = Cube 1Cube0 ；2 組 8 元交換： f 2 = Cube 2Cube1 Cube0；1 組 16 元交換： f 3 = Cube 3Cube2 Cube

32、1Cube0 ；利用 Cube 函數(shù)的結(jié)合律、交換律以及同一律（又稱自反律）可以推得f = f1 f 2 f 3= Cube 3Cube1 Cube0拓撲結(jié)構(gòu)圖略（可參考7.26 題的多級混洗交換網(wǎng)絡(luò)拓撲結(jié)構(gòu)圖）。網(wǎng)絡(luò)開關(guān)使用級控方式，控制信號為1011B（其中 bit i 控制級 i ，“0”表示直連， “ 1”表示交換）。147.13 N = 8的蝶式置換。(1) f(X2X1 X0) = X0 X1 X2；(2) 至少需 2 次通過，每次都是 N 個數(shù)據(jù)同時發(fā)送，同時接收，中途不儲存；(3) 控制信號的設(shè)置有 4 種方案，如下所示。其中“ 0”表示直連， “ 1”表示交換。1011000

33、011010000000000000000000000001011000011010000000000001011000011011011000011010000000000007.14(1)共 N!種；N(2)一次通過有 N 2種不同；N(3)N=8 時，百分比 = N 2100%84100% 10.16%N !8!7.26(1)(3) ；(1) 見下圖實線。(2) 見下圖虛線；不會阻塞，因為兩條路徑的控制信號都是1110，形成級控模式，所以不會阻塞。(3) 一次通過實現(xiàn)的置換數(shù)為16 8 = 4294967296 ，全部置換數(shù)為N! = 20922789888000 ，前者約占后者的0.0

34、2%。15級 3級 2級 1級 0000000000001000100100010001100110100010001010101011001100111011110001000100110011010101010111011110011001101110111101110111111117.27(1)已知 N = 64 ，n = 6 ，源結(jié)點 s = 101101B ，目的結(jié)點d = 011010B ，方向矢量r = s d = 110111B ，以低維度優(yōu)先順序?qū)剑窂綖閟 = 101101B 101100B 101110B 101010B 111010B 011010B = d（下劃線

35、為當前尋徑維）(2) 求給定無向圖中 2 棵選播樹（即生成樹） 。(i) 求最小成本生成樹（通道數(shù)最少） ，可考慮 Prim 算法、 Kruskal 算法或標記法。一個參考操作方法是：先對臨近結(jié)點群分別構(gòu)造最短子樹，然后在子樹之間作最短互連。(ii)求由結(jié)點 (3,5) 出發(fā)的單源最短路徑生成樹（各距離最短），可考慮貪心算法。對X-Y 網(wǎng)格圖來說，從樹根到某一樹葉的任何路徑只要在各維均無反向移動即為最短路徑（滿足此條件的最短路徑有多條）。要得到單一樹根對于多片樹葉的綜合最短路徑，可以先分別作出各條單播最短路徑，然后在不增加各路徑長度的前提下，盡可能地進行路段合并。16這兩小問結(jié)果如下圖所示（其

36、中b 圖第一步必須選擇向下，而不能向右）。0,71,72,73,74,75,76,77,70,71,72,73,74,75,76,77,70,61,62,63,64,65,66,67,60,61,62,63,64,65,66,67,60,51,52,53,54,55,56,57,50,51,52,53,54,55,56,57,50,41,42,43,44,45,46,47,40,41,42,43,44,45,46,47,40,31,32,33,34,35,36,37,30,31,32,33,34,35,36,37,30,21,22,23,24,25,26,27,20,21,22,23,24,25,26,27,2Y 0,11,12,13,14,15,16,17,1Y 0,11,12,13,14,15,16,17,10,01,02,03,04,05,06,07,00,01,02,03,04,05,06,07,0XX(a)(b)(3) 求作超立方體貪心選播樹。7.29 已知 N = 256 ，n = 8 ，起始結(jié)點編號 j = 123 = 01111011B 。根據(jù)混洗函數(shù)的循環(huán)移位性質(zhì)， Shuffle 10(j) = Shuffle 2 (j) = 11101101B = 237第八章 (P498)8.12問題為 S=A1× B1+A32× B3