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
2022考研初復(fù)試已經(jīng)接近尾聲,考研學(xué)子全面進(jìn)入2023屆備考,跨考為23考研的考生準(zhǔn)備了10大課包全程準(zhǔn)備、全年復(fù)習(xí)備考計(jì)劃、目標(biāo)院校專業(yè)輔導(dǎo)、全真復(fù)試模擬練習(xí)和全程針對(duì)性指導(dǎo);2023考研的小伙伴針也已經(jīng)開始擇校和復(fù)習(xí)了,跨考考研暢學(xué)5.0版本全新升級(jí),無論你在校在家都可以更自如的完成你的考研復(fù)習(xí),暑假集訓(xùn)營帶來了院校專業(yè)初步選擇,明確方向;考研備考全年規(guī)劃,核心知識(shí)點(diǎn)入門;個(gè)性化制定備考方案,助你贏在起跑線,早出發(fā)一點(diǎn)離成功就更近一點(diǎn)!
考研院校專業(yè)選擇和考研復(fù)習(xí)計(jì)劃 | |||
2023備考學(xué)習(xí) | 2023線上線下隨時(shí)學(xué)習(xí) | 34所自劃線院校考研復(fù)試分?jǐn)?shù)線匯總 | |
2022考研復(fù)試最全信息整理 | 全國各招生院??佳袕?fù)試分?jǐn)?shù)線匯總 | ||
2023全日制封閉訓(xùn)練 | 全國各招生院校考研調(diào)劑信息匯總 | ||
2023考研先知 | 考研考試科目有哪些? | 如何正確看待考研分?jǐn)?shù)線? | |
不同院校相同專業(yè)如何選擇更適合自己的 | 從就業(yè)說考研如何擇專業(yè)? | ||
手把手教你如何選專業(yè)? | 高校研究生教育各學(xué)科門類排行榜 |
相關(guān)推薦
跨考考研課程
班型 | 定向班型 | 開班時(shí)間 | 高定班 | 標(biāo)準(zhǔn)班 | 課程介紹 | 咨詢 |
秋季集訓(xùn) | 沖刺班 | 9.10-12.20 | 168000 | 24800起 | 小班面授+專業(yè)課1對(duì)1+專業(yè)課定向輔導(dǎo)+協(xié)議加強(qiáng)課程(高定班)+專屬規(guī)劃答疑(高定班)+精細(xì)化答疑+復(fù)試資源(高定班)+復(fù)試課包(高定班)+復(fù)試指導(dǎo)(高定班)+復(fù)試班主任1v1服務(wù)(高定班)+復(fù)試面授密訓(xùn)(高定班)+復(fù)試1v1(高定班) | |
2023集訓(xùn)暢學(xué) | 非定向(政英班/數(shù)政英班) | 每月20日 | 22800起(協(xié)議班) | 13800起 | 先行階在線課程+基礎(chǔ)階在線課程+強(qiáng)化階在線課程+真題階在線課程+沖刺階在線課程+專業(yè)課針對(duì)性一對(duì)一課程+班主任全程督學(xué)服務(wù)+全程規(guī)劃體系+全程測(cè)試體系+全程精細(xì)化答疑+擇校擇專業(yè)能力定位體系+全年關(guān)鍵環(huán)節(jié)指導(dǎo)體系+初試加強(qiáng)課+初試專屬服務(wù)+復(fù)試全科標(biāo)準(zhǔn)班服務(wù) |