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

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

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

問題：

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

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

解答：

(1)由裝載因子0.7，數(shù)據(jù)總數(shù)7個(gè)→存儲(chǔ)空間長度為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)個(gè)整數(shù)存放到一維數(shù)組R中，試設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面盡可能有效的算法，將R中保有的序列循環(huán)左移P(0﹤P﹤n)個(gè)位置，即將R中的數(shù)據(jù)由(X0 X1 ……Xn-1)變換為(Xp Xp+1 ……Xn-1 X0 X1 ……Xp-1)要求：

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

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

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

解答：

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

(2)詳細(xì)程序略

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

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

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

注：

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

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

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

(3)若操作碼0010B表示加法操作(助記符為a d d)，寄存器R4和R5的編號(hào)分別為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)+(逗號(hào)前原操作數(shù)，都號(hào)后為目的操作數(shù))對(duì)應(yīng)的機(jī)器碼是什么(用十六進(jìn)制表示)?該指令執(zhí)行后，哪些寄存器和存儲(chǔ)單元的內(nèi)容會(huì)改變?改變后的內(nèi)容是什么?

解答：

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

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

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

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

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

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

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

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

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

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

若在某時(shí)刻，磁頭位于100號(hào)磁道處，并沿著磁道號(hào)大的方向移動(dòng)(如下圖所示)，磁道號(hào)請(qǐng)求隊(duì)列為50.90.30.120.對(duì)請(qǐng)求隊(duì)列中的每個(gè)磁道需讀取1個(gè)隨機(jī)分布的扇區(qū)，則讀完這個(gè)扇區(qū)點(diǎn)共需要多少時(shí)間?要求給出計(jì)算過程。

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

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

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

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

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

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

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

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

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

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

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

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

解答：

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

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

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

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

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

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