2010年計算機統(tǒng)考試題（三）_跨考網(wǎng)

二、綜合應(yīng)用題：41-47小題，共計70分

41.(10分)將關(guān)鍵字序列(7、8、11、18、9、14)散列存儲到散列列表中，散列表的存儲空間是一個下標(biāo)從0開始的一個一維數(shù)組散列函數(shù)維：H(key)=(key×3)MODT，處理沖突采用線性探測再散列法，要求裝填(載)因子為0.7

問題：

(1)請畫出所構(gòu)造的散列表;

(2)分別計算等概率情況下，查找成功和查找不成功的平均查找長度。

解答：

(1)由裝載因子0.7，數(shù)據(jù)總數(shù)7個→存儲空間長度為10→P=10

所以，構(gòu)造的散列表為：

H(7)=(7×3)MOD10=1

(2)查找成功的ASL=(1+1+1+1+2+1+1)/7=8/7

查找不成功的ASL=(7+6+5+4+3+2+1+2+1+1)/10=3.2

42.(13分)設(shè)將n(n,1)個整數(shù)存放到一維數(shù)組R中，試設(shè)計一個在時間和空間兩方面盡可能有效的算法，將R中保有的序列循環(huán)左移P(0﹤P﹤n)個位置，即將R中的數(shù)據(jù)由(X0 X1 ……Xn-1)變換為(Xp Xp+1 ……Xn-1 X0 X1 ……Xp-1)要求：

(1)給出算法的基本設(shè)計思想。

(2)根據(jù)設(shè)計思想，采用C或C++或JAVA語言表述算法，關(guān)鍵之處給出注釋。

(3)說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度

解答：

(1)前P個數(shù)依次進隊，while(1﹤n-p)A{i}-{i+p}：p個數(shù)依次出對，進入數(shù)組末尾

(2)詳細程序略

(3)時間復(fù)雜度O(N);空間復(fù)雜度o(p)

43.(11分)某計算機字長為16q位，主存地址空間大小為128KB，按字編址，采用字長指令格式，指令名字段定義如下：

轉(zhuǎn)移指令采用相對尋址方式，相對偏移是用補碼表示，尋址方式定義如下：

注：

(X)表示有儲蓄地址X或寄存器X的內(nèi)容，請回答下列問題：

(1)該指令系統(tǒng)最多可有多少條指令?該計算機最多有多少個通用寄存器?存儲器地址寄存器(MDR)至少各需多少位?

(2)轉(zhuǎn)移指令的目標(biāo)地址范圍是多少?

(3)若操作碼0010B表示加法操作(助記符為a d d)，寄存器R4和R5的編號分別為100B和101B，R4的內(nèi)容為1 2 3 4 H，R5的內(nèi)容為5 6 7 8 H，地址1 2 3 4 H中的內(nèi)容為5 6 7 8 H中的內(nèi)容為1 2 3 4 H，則匯編語言為a d d(R4).(R5)+(逗號前原操作數(shù)，都號后為目的操作數(shù))對應(yīng)的機器碼是什么(用十六進制表示)?該指令執(zhí)行后，哪些寄存器和存儲單元的內(nèi)容會改變?改變后的內(nèi)容是什么?

解答：

該題的考點是指令系統(tǒng)設(shè)計，注意操作位數(shù)與指令條數(shù)的關(guān)系，地址碼與寄存器數(shù)的關(guān)系，指令字長與MOR的關(guān)系，存儲容量與MAR的關(guān)系，注意補碼計算的偏移地址。

44.(12分)某計算機的主存地址空間為256MB，按字節(jié)編址，指令Cache分離‘均有8個Cache行，每個Cache行的大小為64MB，數(shù)據(jù)Cache采用直接映射方式，現(xiàn)有兩個功能相同的程序A和B,其偽代碼如下所示：

假定int 類型數(shù)據(jù)用32位補碼表示，程序編譯時i,j, sum 均分配在寄存器中，數(shù)據(jù)a按行優(yōu)先方式存放，其地址為320(十進制數(shù))，請回答下列問題，要求說明理由或給出計算過程。

(1)、若不考慮用于cache一致性維護和替換算法的控制位，則數(shù)據(jù)Cache的總?cè)萘渴嵌嗌?

(2)、要組元素a[0][31]和a[1][1]各自所在的主存塊對應(yīng)的Cache行號分別是多少(Cache行號從0開始)?

(3)、程序A和B的數(shù)據(jù)訪問命令中各是多少?那個程序的執(zhí)行時間更短?

簡答：考點：Cache容量計算，直接映射方式的地址計算，以及命中率計算(行優(yōu)先遍歷與列優(yōu)先遍歷命中率分別很大)

45、(7分)假設(shè)計算機系統(tǒng)采用CSCAN(循環(huán)掃描)磁盤調(diào)度策略，使用2KB的內(nèi)存空間記錄16384個磁盤塊的空間狀態(tài)

(1)、請說明在上述條件下如何進行磁盤塊空閑狀態(tài)管理。

(2)、設(shè)某單面磁盤旋轉(zhuǎn)速度為每分鐘6000轉(zhuǎn)。每個磁道有100個扇區(qū)，相臨磁道間的平均移動時間為1ms.

若在某時刻，磁頭位于100號磁道處，并沿著磁道號大的方向移動(如下圖所示)，磁道號請求隊列為50.90.30.120.對請求隊列中的每個磁道需讀取1個隨機分布的扇區(qū)，則讀完這個扇區(qū)點共需要多少時間?要求給出計算過程。

46.(8分)設(shè)某計算機的邏輯地址空間和物理地址空間均為64KB.按字節(jié)編址。若某進程最多需要6頁(Page)數(shù)據(jù)存儲空間，頁的大小為1KB.操作系統(tǒng)采用固定分配局部置換策略為此進程分配4個頁框(Page Fame).

當(dāng)該進程執(zhí)行到時刻260時，要訪問邏輯地址為17CAH的數(shù)據(jù)，請問答下列問題：

(1)、該邏輯地址對應(yīng)的頁號是多少?

(2)、若采用先進先出(FIFO)置換算法，該邏輯地址對應(yīng)的物理地址是多少?要求給出計算過程。

(3)、若采用時鐘(CLOCK)置換算法，該邏輯地址對應(yīng)的物理地址是多少?要求給出計算過程。(設(shè)搜索下一頁的指針沿順時針方向移動，且當(dāng)前指向2號頁框，示意圖如下。)

解答：17CAH=(0001 0111 1100 1010)2

(1)頁大小為1K，所以頁內(nèi)偏移地址為10位，于是前6位是頁號，所以第一間的解為：5

(2)FIFO，則被置換的頁面所在頁框為7，所以對應(yīng)的物理地址為(0001 1111 1100 1010)2-IFCAH

(3)CLOCK,則被置換的頁面所在頁框為2，所以對應(yīng)的物理地址為(0000 1011 1100 1010)2-OBCAH

47、(9分)某局域網(wǎng)采用CSMA/CD協(xié)議實現(xiàn)介質(zhì)訪問控制，數(shù)據(jù)傳輸速率為10MBPS,主機甲和主機乙之間的距離為2KM，信號傳播速度是200 000KMS.請回答下列問題，并給出計算過程。

(1)若主機甲和主機乙發(fā)送數(shù)據(jù)時發(fā)生沖突，則從開始發(fā)送數(shù)據(jù)時刻起，到兩臺主機均檢測到?jīng)_突時刻止，最短需經(jīng)多長時間?最長需經(jīng)過多長時間?(假設(shè)主機甲和主機乙發(fā)送數(shù)據(jù)過程中，其他主機不發(fā)送數(shù)據(jù))

(2)若網(wǎng)絡(luò)不存在任何沖突與差錯，主機甲總是以標(biāo)準(zhǔn)的最長以大網(wǎng)數(shù)據(jù)鎖(1518字節(jié))向主機乙發(fā)送數(shù)據(jù)，主機乙每成功收到一個數(shù)據(jù)鎖后，立即發(fā)送下一個數(shù)據(jù)鎖，此時主機甲的有效數(shù)據(jù)傳輸速率是多少?(不考慮以大網(wǎng)鎖的前導(dǎo)碼)

解答：

(1)當(dāng)甲乙同時向?qū)Ψ桨l(fā)送數(shù)據(jù)時，兩臺主機均檢測到?jīng)_突所需時間最短;

1KM/200000KM/S*2=1*10(-5)S

當(dāng)一方發(fā)送的數(shù)據(jù)馬上要到達另一方時，另一方開始發(fā)送數(shù)據(jù)，兩臺主機均檢測到?jīng)_突所需時間最長;

2KM/2000000KM/S*2=2*10(-5)S

(2)發(fā)送一鎖所需時間;1518B/10MBPS=1.2144MS

數(shù)據(jù)傳播時間;2KM/200 000KM/S=1*10(-5)S=0.01MS