2021年考研計(jì)算機(jī)408統(tǒng)考真題及答案解析

1、20212021年計(jì)算機(jī)408統(tǒng)考真題第3頁，共9頁003 -0020022021年計(jì)算機(jī)408統(tǒng)考真題第 016 016 -【解析差分曼徹斯特編碼常用于局域網(wǎng)傳輸，其規(guī)則是；若碼元為1.則前半個(gè)碼元的電平與上 一碼元的后半個(gè)碼元的電平相同；若碼元為0,則情形相反。差分曼徹斯特編碼的特點(diǎn)在 于，在每個(gè)時(shí)鐘周期的起始處，跳變則說明該比特是0,不跳變則說明該比特是1。根據(jù)題34圖，第1個(gè)碼元的信號(hào)波形因缺乏上一碼元的信號(hào)波形，無法判斷是。還是1, 但根據(jù)后面的信號(hào)波形，可以求出第28個(gè)碼元為011 1001,因此選A【解析】根據(jù)題意，將IP網(wǎng)絡(luò)劃分為3個(gè)子網(wǎng)。其中一個(gè)是192.1689128/26

2、?？梢院唽懗蓌.x.x.10/26 （其中10是128的二進(jìn)制1000 0000的前兩位，因?yàn)?6-24 = 2）.A選項(xiàng)可以簡寫成x.x.x.0/25；B選項(xiàng)可以簡寫成x.x.x.00/26；C選項(xiàng)可以簡寫成x.x.x.11/26：D選項(xiàng)可以簡寫成x.x.x.110/27。對(duì)于A和C,可以組成x.x.x.0/25、x.x.x.10/26、x.x.x.11/26這樣3個(gè)互不重疊的子網(wǎng)。 對(duì)于D,可以組成x.x.x.10/26、x.x.x.l 10/27. x.x.x.111/27這樣3個(gè)互不重疊的子網(wǎng).但對(duì)于B,要想將一個(gè)IP網(wǎng)絡(luò)劃分為幾個(gè)互不重疊的子網(wǎng)，3個(gè)是不夠的，至少需要?jiǎng)澐?為 4 個(gè)

3、子網(wǎng)：x.x.x.00/26、x.x.x.01/26、x.x.x.10/26、x.x.x.11/26.【解析】鏈路層MTU = 800Bo IP分組首部長20B。片偏移以8個(gè)字節(jié)為偏移單位，因此除最后一 個(gè)分片，其他每個(gè)分片的數(shù)據(jù)部分長度都是8B的整數(shù)倍。所以，最大IP分片的數(shù)據(jù)部分 長度為776B。忌長度1580B的IP數(shù)據(jù)報(bào)中，數(shù)據(jù)部分占1560B, 1560B/776B = 2.01， 需要分成3片。故第2個(gè)分片的總長度字段為796, MF為1 （表示還有后續(xù)的分片）。【解析】根據(jù)距離向量蹺由算法，E收到相鄰路由器的距離向量后，更新它的路由表：當(dāng)原路由表中沒有目的網(wǎng)絡(luò)時(shí)，把該項(xiàng)目添加到路

4、由表中.發(fā)來的路由信息中有一條到達(dá)某個(gè)目的網(wǎng)絡(luò)的路由，該路由與當(dāng)前使用的路由相比，有 較短的距離，就用經(jīng)過發(fā)送路由信息的結(jié)點(diǎn)的新路由替換。分析題意可知，E與鄰居路由器A、B、C和D之間的直接鏈路距離分別是8,10,12和6。 到達(dá)NetlNet4沒有直接鏈路，需要通過鄰居路由器。從上述算法可知，E到達(dá)目的網(wǎng)絡(luò) 一定是經(jīng)過A,B,C和D中距離最小的。根據(jù)題中所給的距離信息，計(jì)算E經(jīng)鄰居路由器 到達(dá)目的網(wǎng)絡(luò)NetlNet4的距離，如下表所示，選擇到達(dá)每個(gè)目的網(wǎng)絡(luò)距離的最短值。目的網(wǎng)絡(luò)性過A需要的距離經(jīng)過B需要的距髙經(jīng)過CIJ要的距離經(jīng)過D需要的距髙Netl2333228Net220454234Ne

5、t3322S42Net444402030所以距離分別是9, 20,28,20.38.【解析】38.TCP連接釋放的過程如下圖所示。當(dāng)客戶機(jī)收到服務(wù)器發(fā)送的riN段并向服務(wù)器發(fā)送ACK 段后，客戶機(jī)的TCP狀態(tài)變?yōu)門IME_WAIT,此時(shí)TCP連接還未釋放，必須經(jīng)過時(shí)間等待計(jì) 時(shí)將設(shè)置的時(shí)何2MSL （最長報(bào)文段壽命）后，客廣機(jī)才進(jìn)入CLOSED （連接大閉狀志。【解析】應(yīng)用層數(shù)據(jù)交給傳輸層時(shí)，放在報(bào)文段的數(shù)據(jù)部分。UDP首部有8B, TCP首部最短有20B。 為了達(dá)到最大傳輸效率，通過UDP傳輸時(shí)，總長度為20B,最大傳輸效率是12B/20B = 60%o 通過TCP傳輸時(shí)，總長度為32B,最

6、大傳輸效率是12B/32B = 37.5%?！窘馕觥恳李}念，甲發(fā)送亢2U0B報(bào)義后，繼埃發(fā)送的報(bào)義段屮序號(hào)字段seq= /Ulo由于乙告知接收窗 口為500,且甲未收到乙對(duì)seq = 501報(bào)文段的確認(rèn)，那么甲還能發(fā)送的報(bào)文段字節(jié)數(shù)為 50U- 2UU = 33B,因此甲在木收到新的確認(rèn)段之前，還能發(fā)送的數(shù)據(jù)序號(hào)范圍是7011000。二、綜合應(yīng)用題【解析】1）算法的基K設(shè)計(jì)思想本算法題屬于送分題，題干己經(jīng)告訴我們算法的思想。對(duì)于采用鄰接矩陣存儲(chǔ)的無向 圖，在鄰接矩陣的每一行（列）中，非零元素的個(gè)數(shù)為本行（列）對(duì)應(yīng)頂點(diǎn)的度?？?以依次計(jì)算連通圖G中各頂點(diǎn)的度，并記錄度為奇數(shù)的頂點(diǎn)個(gè)數(shù)，若個(gè)數(shù)為。

7、或2,則 返回1,否則返回0。2）算法實(shí)現(xiàn)int IsExistEL（MGraph G）（/采莊鄰接矩陣存儲(chǔ)，判斷圖是否存在EL路徑int degree,i,j z count-0;for（i-0;iG.numvertices;i+）（degree-0;for (j-0;jG.numvertices;j+)degree+-G.Edgei j;依次計(jì)算各個(gè)頂點(diǎn)的度if(degree%2!-0)count+;/對(duì)度為奇數(shù)的頂點(diǎn)計(jì)數(shù)if (count0| I count2)return 1;存在EL路徑，返回1elsereturn 0;/不存在EL路徑，返回0I時(shí)間復(fù)雜度和空間復(fù)雜度算法需要遍歷整個(gè)

8、鄰接矩陣，所以時(shí)間復(fù)雜度是。(請(qǐng))，空間復(fù)雜度是0(1)?！窘馕觥縞mpCountSort:算法基于計(jì)數(shù)排序的思想，對(duì)序列進(jìn)行排序。cmpCountSort算法遍歷數(shù)組 中的元素，count數(shù)組記錄比對(duì)應(yīng)待排序數(shù)組元素下標(biāo)大的元素個(gè)數(shù)，例如，count 1-3 的意思是數(shù)組a中有3個(gè)元素比al大，即al是第4大元素,a 1 的正確位置應(yīng)是b3.排序結(jié)果為 b6 = -10,10,11,19,25,25.由代碼 for(i-0;in-l;i+)和 for (j=i+l; jn; j+)可知，在循環(huán)過程中，每 個(gè)元素都與它后面的所有元素比較一次(即所有元素都兩兩比較一次)，比較次數(shù)之和 為(n-l

9、)+(w-2)+ +!，故總的比較次數(shù)是戒_1)/2.不是。需要將程序中的if語句修改如下：if(ai-a(j) count(j+；else count(i)+;如果不加等號(hào)，兩個(gè)相等的元素比較時(shí)，前面元素的count值會(huì)加1,導(dǎo)致原序列中 靠前的元素在排序后的序列中處于靠后的位置?！窘馕觥緼LU的寬度為16位，ALU的寬度即ALU運(yùn)算對(duì)象的寬度，通常與字長相同。地址線 為20位.按字節(jié)編址，可尋址主存空間大小為220字節(jié)(或1MB)。指令寄存器有16 位，和單條指令長度相同。MAR有20位，和地址線位數(shù)相同。MDR有8位，和數(shù)據(jù) 線寬度相同。R型格式的操作碼有4位，最多有24 (或16)種操

10、作。I型和J型格式的操作碼有6位, 因?yàn)樗鼈兊牟僮鞔a部分重疊，所以共享這6位的操作碼空間，且前6位全0的編碼己 被R型格式占用，因此I和J型格式最多有28-1=63種操作。從R型和I型格式的寄 存器編號(hào)部分可知，只用2位對(duì)寄存器編碼，囚此通用寄存器最多有4個(gè)。指令01B2H = 000000 01 10 11 0010B為一條R型指令，操作碼0010表示帶符號(hào)整數(shù)減法 指令，其功能為 R(3-R(l-R(2o 執(zhí)行指令 01B2H 后，R3 = B052H -0008H = B04AH. 結(jié)果未溢出。指令01B3H = 000000 01 1011 00I1B.操作碼0011表示帶符號(hào)整數(shù)乘法

11、指令, 執(zhí)行指令 01B3H 后，R3 = RlxR2 = B052Hx0008H = 8290H,結(jié)果溢出。在進(jìn)行指令的跳轉(zhuǎn)時(shí)，可能向前跳轉(zhuǎn)，也可能向后跳轉(zhuǎn)，偏移最是一個(gè)帶符號(hào)整數(shù)， 因此在地址計(jì)算時(shí)，應(yīng)對(duì)imm進(jìn)行符號(hào)擴(kuò)展。無條件轉(zhuǎn)移指令可以釆用J型格式，將target部分寫入PC的低10位，完成跳轉(zhuǎn)?！窘馕觥孔⒁猓簩?duì)于本題的TLB,需要采用處理Cache的方式求解。1）按字節(jié)編址，頁面大小為4 KB = 2,2B,頁內(nèi)地址為12位。虛擬地址中高30-12 = 18 位表示虛頁號(hào)，虛擬地址中低12位表示頁內(nèi)地址。2）TLB采用2路組相聯(lián)方式，共8 = 2,組，用3位來標(biāo)記組號(hào)。虛擬地址（或

12、虛頁號(hào)）中 高18-3 = 15位為TLB標(biāo)記，虛擬地址中隨后3位（或虛頁號(hào)中低3位）為TLB組號(hào)。3）虛頁號(hào)4對(duì)應(yīng)的TLB表項(xiàng)被替換。因?yàn)樘擁撎?hào)與TLB組號(hào)的映射關(guān)系為TLB組號(hào)=虛 頁號(hào)mod TLB組數(shù)=虛頁號(hào)mod 8,因此，虛頁號(hào)10, 12, 16, 7, 26, 4, 12, 20映射到的 TLB組號(hào)依次為2,4,0,7,2,4,4,4。TLB采用2路組相聯(lián)方式，從上述映射到的TLB組號(hào) 序列可以看出，只有映射到4號(hào)組的虛頁號(hào)數(shù)量大于2,相應(yīng)虛頁號(hào)依次是12,4,12和20。 根據(jù)LRU替換策略，當(dāng)訪問第20頁時(shí)，虛頁號(hào)4對(duì)應(yīng)的TLB表項(xiàng)被替換出來。4）虛擬地址位數(shù)增加到32位時(shí)

13、，虛頁號(hào)増加了 32-30 = 2位，使得每個(gè)TLB表項(xiàng)中的標(biāo) 記字段增加2位，因此，每個(gè)TLB表項(xiàng)的位數(shù)増加2位。【解析】1）信號(hào)量S是能被多個(gè)進(jìn)程共享的變量，多個(gè)進(jìn)程都可通過wait（）和signal。對(duì)S 進(jìn)行讀、寫操作。所以，waitO和signal。操作中對(duì)S的訪問必須是互斥的。2）方法1錯(cuò)誤。在wait （）中，當(dāng)S = 0時(shí)，關(guān)中斷后，其他進(jìn)程無法修改S的值，while 語句陷入死循環(huán)。方法2正確。方法2在循環(huán)體中有一個(gè)開中斷操作，這樣就可以使 具他進(jìn)程修改S的值，從而避Awhile句陷入死循環(huán)。3）用戶程序入能使用開/關(guān)中斷指令實(shí)現(xiàn)臨界區(qū)互斥。因?yàn)殚_中斷和關(guān)中斷指令都是特權(quán) 指

14、令，不能在用戶態(tài)下執(zhí)行，只能在內(nèi)核態(tài)下執(zhí)行【解析】1）執(zhí)行順序依次是ROM中的引導(dǎo)程序、磁盤引導(dǎo)程序、分區(qū)引導(dǎo)程序、操作系統(tǒng)的初始 化程序。啟動(dòng)系統(tǒng)時(shí)，首先運(yùn)行ROM中的引導(dǎo)代碼（bootstrap）。為執(zhí)行某個(gè)分區(qū)的 操作系統(tǒng)的初始化程序，需要先執(zhí)行磁盤引導(dǎo)程序以指示引導(dǎo)到哪個(gè)分區(qū)，然后執(zhí)行 該分區(qū)的引導(dǎo)程序，用于引導(dǎo)該分區(qū)的操作系統(tǒng)。2）4個(gè)操作的執(zhí)行順序依次是磁盤的物理格式化、對(duì)磁盤進(jìn)行分區(qū)、邏輯格式化、操作系 統(tǒng)的安裝。磁盤只有通過分區(qū)和邏輯格式化后才能安裝系統(tǒng)和存儲(chǔ)信息。物理格式化 （又稱低級(jí)格式化，通常出廠時(shí)就己完成）的作用是為每個(gè)磁道劃分扇區(qū)，安排扇區(qū)在 磁道中的排列順序，并對(duì)己

15、損壞的磁道和扇區(qū)做“壞”標(biāo)記等。隨后將磁盤的整體存 儲(chǔ)空間劃分為相互獨(dú)立的多個(gè)分區(qū)（如Windows中劃分C盤、D盤等），這些分區(qū)可以 用作多種用途，如安裝不同的操作系統(tǒng)和應(yīng)用程序、存儲(chǔ)文件等。然后進(jìn)行邏輯格式 化（又稱高級(jí)格式化），其作用是對(duì)扇區(qū)進(jìn)行邏輯編號(hào)、建立邏輯盤的引導(dǎo)記錄、文件 分配表、文件目錄表和數(shù)據(jù)區(qū)等。最后才是操作系統(tǒng)的安裝。3）由上述解析知，磁盤扇區(qū)的劃分是在磁盤的物理格式化操作中完成的，文件系統(tǒng)根目 錄的建立是在邏輯格式化操作中完成的?！窘馕觥?）從而到4期間，除了 HTTP, Hl還運(yùn)行了 DNS應(yīng)用層協(xié)議，以將域名轉(zhuǎn)換為IP地址。DNS運(yùn)行在UDP之上，UDP將應(yīng)用層交

16、下來的DNS報(bào)文添加首部后，向下交付給IP 層，IP層使用IP數(shù)據(jù)報(bào)進(jìn)行封裝，封裝好后，向下交付給數(shù)據(jù)鏈路層，數(shù)據(jù)鏈路層使 用CSMA/CD幀進(jìn)行封裝。因此，逐層封裝關(guān)系如下：DNS報(bào)文一UDP數(shù)據(jù)報(bào)一IP數(shù) 據(jù)報(bào)-*CSMA/CD 幀。2）命時(shí)刻，H1的ARP表和S的交換表為空。H1利用瀏覽器通過域名請(qǐng)求訪問Web服務(wù)器。 由于要先解析域名，所以會(huì)發(fā)送DNS報(bào)義到本地域名服務(wù)器，查詢?cè)撚蛎麘?yīng)的IP地址， 所以要先向本地域名服務(wù)器發(fā)送請(qǐng)求。ARP表為空，所以需要先發(fā)送ARP請(qǐng)求分組，査 詢本地域名服務(wù)器對(duì)應(yīng)的MAC地址。這些幀的目的MAC地址均是FF-FF-FF-FF-FF-FF.S接收到這個(gè)

17、幀，在交換表中記錄下MAC地址為（XM1-22-334UC,位于端口 4,然后廣 播該幀。當(dāng)本地域名服務(wù)器接收到ARP請(qǐng)求后，向H1發(fā)送響應(yīng)ARP分組。S接收到這個(gè) 幀，在交換表中記錄下MAC地址為00-11-22-33-44-bb,位于端口 1,然后把該幀從端口 4 發(fā)送出去。得到了域名對(duì)應(yīng)的IP地址，發(fā)現(xiàn)不在本局域網(wǎng)中，需要通過路由表轉(zhuǎn)發(fā)。H1的ARP表中并沒有路由器對(duì)應(yīng)的MAC地址，因此需要先發(fā)送ARP請(qǐng)求分組，負(fù) 詢路由器對(duì)應(yīng)的MAC地址。這些幀的目的MAC地址均是FF-FF-FF-FF- FF-FF。S接 收到這個(gè)幀，廣播該幀。當(dāng)路由器收到ARP請(qǐng)求后，向H1發(fā)送響應(yīng)ARP分組。S接 收到這個(gè)幀，在交換表中記錄下MAC地