【正文】 256]。 ...... int sum_array2() { int i, j, sum = 0。 for (j = 0。 j 256。 j++) for (i= 0。 i 256。 i++) sum += a[i][j]。 return sum。 } 假定 int 類型數(shù)據(jù)用 32 位補(bǔ)碼表示，程序編譯時 i， j， sum 均分配在寄存器中，數(shù)組 a 按行優(yōu)先方式存放，其地址為 320(十進(jìn)制 )。請回答，要求說明理由或給出計算過程。 (1)、若不考慮用于 Cache 一致維護(hù)和替換算法的控制位，則數(shù)據(jù) Cache 的總?cè)萘繛槎嗌?? (2)、數(shù)組元素 a[0][31]和 a[1][1]各自所在的主存塊對應(yīng)的 Cache 行號分別是多少 (Cache 行號從 0 開始 ) (3)、程序 A 和 B 得數(shù)據(jù)訪問命中率各是多少？哪個程序的執(zhí)行時間短？ 4（ 7 分）假設(shè)計算機(jī) 系統(tǒng)采用 CSCAN(循環(huán)掃描 )磁盤調(diào)度策略 ,使用 2KB 的內(nèi)存空間記錄 16384 個磁盤的空閑狀態(tài) (1)、請說明在上述條件如何進(jìn)行磁盤塊空閑狀態(tài)的管理。 (2)、設(shè)某單面磁盤的旋轉(zhuǎn)速度為每分鐘 6000 轉(zhuǎn)，（勤思教育）每個磁道有 100 個扇區(qū)，相臨磁道間的平均移動的時間為 1ms. 若在某時刻，磁頭位于 100 號磁道處，并沿著磁道號增大的方向移動 (如下圖所示 ),磁道號的請求隊(duì)列為 50，90， 30， 120 對請求隊(duì)列中的每個磁道需讀取 1 個隨機(jī)分布的扇區(qū)，則讀完這個扇區(qū)點(diǎn)共需要多少時間？需要給出計算過程。 46.(8 分 )設(shè)某計算機(jī)的邏輯地址空間和物理地址空間均為 64KB，按字節(jié)編址。（勤思教育）某進(jìn)程最多需要 6 頁數(shù)據(jù)存儲空間，頁的大小為 1KB，操作系統(tǒng)采用固定分配局部置換策略為此進(jìn)程分配 4 個頁框。 頁號 頁框號 裝入時間 訪問位 0 7 130 1 1 4 230 1 2 2 200 1 3 9 160 1 當(dāng)該進(jìn)程執(zhí)行到時刻 260 時，要訪問邏輯地址為 17CAH 的數(shù)據(jù)。請回答下列問題： (1)、該邏輯地址對應(yīng)的頁號時多少 ? (2)、若采用先進(jìn)先出 (FIFO)置換算法，該邏輯地址對應(yīng)的物理地址？要求給出計 算過程。 (3)、采用時鐘 (Clock)置換算法，該邏輯地址對應(yīng)的物理地址是多少？要求給出計算過程。（設(shè)搜索下一頁的指針按順時針方向移動，且指向當(dāng)前 2 號頁框，示意圖如下） 4（ 9 分）某局域網(wǎng)采用 CSMA/CD 協(xié)議實(shí)現(xiàn)介質(zhì)訪問控制，數(shù)據(jù)傳輸率為 100M/S，主機(jī)甲和主機(jī)已的距離為 2KM，信號傳播速速時 202200M/S 請回答下列問題，并給出計算過程。 （ 1） 、若主機(jī)甲和主機(jī)已發(fā)送數(shù)據(jù)時發(fā)生沖突，則從開始發(fā)送數(shù)據(jù)時刻起，到兩臺主機(jī)均檢測到?jīng)_突時刻為止，最短經(jīng)過多長時間？最長經(jīng)過多長時間？ (假設(shè)主機(jī)甲 和主機(jī)已發(fā)送數(shù)據(jù)時，其它主機(jī)不發(fā)送數(shù)據(jù) ) （ 2）、若網(wǎng)絡(luò)不存在任何沖突與差錯，主機(jī)甲總是以標(biāo)準(zhǔn)的最長以太數(shù)據(jù)幀 (1518 字節(jié) )向主機(jī)已發(fā)送數(shù)據(jù)，主機(jī)已每成功收到一個數(shù)據(jù)幀后，立即發(fā)送下一個數(shù)據(jù)幀，（勤思教育）此時主機(jī)甲的有效數(shù)據(jù)傳輸速率是多少？ (不考慮以太網(wǎng)幀的前導(dǎo)碼 ) 第二部分：勤思教育計算機(jī)教研組整理 2022 年計算機(jī)考研答案真題 ********************************************************************************* 第一題： 選擇題答案： 15 D C B C B 610 A A B A D 1115 A D C B D 1620 A D B A D 2125 A D A C B 2630 A A B B C 3135 C B C A A 3640 C B C A A 第二題：綜合題答案 4 (1)因?yàn)檠b填因子為 ，數(shù)據(jù)總數(shù)為 7，所以存儲空間長度為 L = 7/ = 10 因此可選 T=10，構(gòu)造的散列函數(shù)為 H(key) = (key*3) MOD 10 線性探測再散列函數(shù)為： Hi = ( H(key)+ di ) MOD 10 , (di = 1,2,3...9) 因此，各數(shù)據(jù)的下標(biāo)為 H(7) = (7*3) MOD 10 = 1 H(8) = (8*3) MOD 10 = 4 H(30) = (30*3) MOD 10 = 0 H(11) = (11*3) MOD 10 = 3 H(18) = (18*3) MOD 10 = 4 H1 = ( H(18) +1) MOD 10 = 5 H(9) = (9*3) MOD 10 = 7 H(14) = (14*3) MOD 10 = 2 所構(gòu)造的散列表如下： 0 1 2 3 4 5 6 7 8 9 30 7 14 11 8 18 9 (2)查找成功的平均查找長度為： ASL1 = (1+1+1+1+2+1+1)/7 = 8/7 查找不成功的平均查找長度為： ASL2 =(7+6+5+4+3+2+1+2+1+1) = 4 （ 1）建立一個可以放下 p 個整數(shù)的輔助隊(duì)列，將數(shù)組 R 中的前 p 個整數(shù)依次進(jìn)入輔助隊(duì)列，將 R 中后面的 np 個整數(shù)依次前移 p 個位置，將輔助隊(duì)列中的數(shù)據(jù)依次出隊(duì)，依次放入 R 中第 np 個整數(shù)開始的位置。 （ 2）使用 c 語言描述算法如下： void Shift(int *pR, int n, int p) //pR 是指向數(shù)組 R 的指針， n 為存放的整 數(shù)個數(shù)， //p 為循環(huán)左移的個數(shù) { int temp[p]。 // 輔助數(shù)組，存放要移出的整數(shù)。 int i=0。 while(ip) { //將 R 中前 p 個數(shù)據(jù)存入輔助數(shù)組中。 temp[i] = pR[i]。 i++。 } i = 0。 while(i np) { //將 R 中從第 p 個整數(shù)開始的整數(shù)前移 p 個位置。 pR[i] = pR[p+i]。 i++。 } i = 0。 while(i p) { //將輔助數(shù)組中的 p 個數(shù)據(jù)放到 R 中第 np 個 數(shù)據(jù)的后面。 pR[np+i] = temp[i]。 i++。 } return。 } （ 3）所設(shè)計的算法的時間復(fù)雜度為 O(n),空間復(fù)雜度為 O(p) 4 （ 1） OP 字段占 4 個 bit 位，因此該指令系統(tǒng)最多有 2^4 = 16 條指令； Rs/Rd 為 3 個 bit，因此最多有 2^3 = 8 個通用寄存器； 128K/2 = 64k = 2^16,所以存儲器地址寄存器位數(shù)至少為 16 位，（ 勤思考研 ）指令字長度為 16 位，所以存儲器數(shù)據(jù)寄存 器至少為 16 位。 （ 2）因?yàn)?Rn 是 16 位寄存器，所以可以尋址的目標(biāo)地址范圍是 64K，即整個存儲器空間。 （ 3）對應(yīng)的機(jī)器碼是 230DH，該指令執(zhí)行后 R5 的內(nèi)容變?yōu)?5679H，地址 5678H 的內(nèi)容變?yōu)?68AC。 ： （ 1） cache 總?cè)萘康扔?cache 每一行的容量乘以 cache 的行數(shù)。（ 勤思考研 ）大家需要注意的是，本題 cache 總?cè)萘糠謩e等于數(shù)據(jù) cache 和指令 cache 的總和。 （ 2）分別計算出 A[0][31]A[1][1]的地址的值，然后根據(jù)直接映射方式除以 cache 行的大小，與 cache 行數(shù)求余，所得的余數(shù)就是所映射的 cache 塊。 （ 3） cache 的命中率等于訪問 cache 的次數(shù)除以 cache 的次數(shù)加上訪問內(nèi)存的次數(shù)。本題通過計算得知，命中率高的計算速度快。 4 （ 1） 2KB = 2*1024*8bit = 16384bit。因此可以使用位圖法進(jìn)行磁盤塊空閑狀態(tài)管理，（ 勤思考研 ）每 1bit 表示一個磁盤塊是否空閑。 （ 2）每分鐘 6000 轉(zhuǎn)，轉(zhuǎn)一圈的時間為 ，通過一個扇區(qū)的時間為 。 根據(jù) CSCAN 算法，被訪問的磁道號順序?yàn)?100 ?120 ? 30? 50 ? 90,因此，尋道用去的總時間為：（ 20 + 90 + 20 + 40） * 1ms = 170ms 總共要隨機(jī)讀取四個扇區(qū)，用去的時間為：（ * + ） *4 = = 所以，讀完這個扇區(qū)點(diǎn)共需要 170ms + = 。 4 （ 1） 17CAH 轉(zhuǎn)換為二進(jìn)制為： 0001 0111 1100 1010, 頁的大小為 1KB，（ 勤思考研 ）所以頁內(nèi)偏移為 10 位，于是前 6 位是頁號，所以其頁號為 0001 01，轉(zhuǎn)換為 10 進(jìn)制為 5，所以， 17CA 對應(yīng)的頁號為 5。 （ 2）若采用先進(jìn)先出置換算法，則被置換出的頁號對應(yīng)的頁框號是 7，因此對應(yīng)的二進(jìn)制物理地址為： 0001 1111 1100 1010，轉(zhuǎn)換為 16 進(jìn)制位的物理地址為 1FCAH。 （ 3）若采用時鐘算法，且當(dāng)前指針指向 2 號頁框，則第一次循環(huán)時，訪問位都被置為 0，在第二次循環(huán)時 ，將選擇置換 2 號頁框?qū)?yīng)的頁，因此對應(yīng)的二進(jìn)制物理地址為： 0000 1011 1100 1010，轉(zhuǎn)換為 16 進(jìn)制物理地址為 0BCAH。 4 (1)當(dāng)甲乙兩臺主機(jī)同時向?qū)Ψ桨l(fā)送數(shù)據(jù)時，兩臺主機(jī)均檢測到?jīng)_突的時間最短： Tmin = 1KM/202200KM/S*2 = 10us 當(dāng)一臺主機(jī)發(fā)送的數(shù)據(jù)就要到達(dá)另一臺主機(jī)時，另一臺主機(jī)才發(fā)送數(shù)據(jù)，（ 勤思考研 ）兩臺主機(jī)均檢測到?jīng)_突的時間最長： Tmax = 2KM/202200KM/S*2 = 20us (2)主機(jī)甲發(fā)送一幀數(shù)據(jù)所需的時間為： T1 = 1518B/10Mbps = 數(shù)據(jù)在傳輸過程中所需的時間： T2 = 2KM/202200KM/S = 因此，主機(jī)甲的有效數(shù)據(jù)傳輸速率為： V= 10Mbps*(T1/(T1+T2)) = 10Mbps*((+) )=