全國碩士研究生入學(xué)統(tǒng)一考試

1、全國碩士研究生入學(xué)統(tǒng)一考試A.2B.3C. 異步通信方式中，非互鎖協(xié)議的可靠性最差D. 同步通信方式中，同步時鐘信號可由各設(shè)備提供E. 半同步通信方式中，握手信號的采樣由同步時鐘控制1. 若磁盤轉(zhuǎn)速為 7200 轉(zhuǎn)/分，平均尋道時間為 8ms，每個磁道包含 1000個扇區(qū)，貝問一個扇區(qū)的平均存取時間大約是0A. 8.1msB. 12.2msC. 16.3msD. 20.5ms2. 在采用中斷I/O 方式控制打印輸出的情況下，CPU和打印控制接口中的I/O 端口之間交換的信息不可能是 。A.打 印 字 符B. 主 存 地 址C. 設(shè) 備 狀 態(tài)D. 控 制 命 令3. 內(nèi)部異常 (內(nèi)中斷 )可分

2、為故障 (fault)、陷阱 (trap)和 終 止 ( abort)三類。下列有關(guān)內(nèi)部異 常的敘述中，錯誤的是 。A. 內(nèi)部異常的產(chǎn)生與當(dāng)前執(zhí)行指令相關(guān)B. 內(nèi)部異常的檢測由 CPU 內(nèi)部邏輯實(shí)現(xiàn)C. 內(nèi)部異常的響應(yīng)發(fā)生在指令執(zhí)行過程中D. 內(nèi)部異常處理后返回到發(fā)生異常的指令繼續(xù)執(zhí)行4. 處理外部中斷時，應(yīng)該由操作系統(tǒng)保存的是 。A. 程序計數(shù)器 (PC)的內(nèi)容B.通用寄存器的內(nèi)容C.塊 表 ( TLB)中的內(nèi)容D. Cache中的內(nèi)容5. 假定下列指令已裝入指令寄存器。則執(zhí)行時不可能導(dǎo)致CPU從用戶態(tài)變?yōu)閮?nèi)核態(tài) (系統(tǒng)態(tài) )的A.DIV R0,R1; (R0) / (Rl)ROB.INT

3、n;產(chǎn)生軟中斷C.NOT RO; 寄 存 器 RO 的內(nèi)容取非D.MOV R0,addr;把 地 址 addr處的內(nèi)存數(shù)據(jù)放入寄存器 R0 中6.下列選項中，會導(dǎo)致進(jìn)程從執(zhí)行態(tài)變?yōu)榫途w態(tài)的事件是A.執(zhí)行 P(wait)操作B.申請內(nèi)存失敗C.啟動 I/O 設(shè)備D.被高優(yōu)先級進(jìn)程搶占7. 若系統(tǒng) S1采用死鎖避免方法， S2采用死鎖檢測方法。下列敘述中，正確的是 oI. S1會限制用戶申請資源的順序，而 S2不會n. S1需要進(jìn)程運(yùn)行所需資源總量信息， 而 S2不需要 in.si 不會給可能導(dǎo)致死鎖的進(jìn)程分配資源，而 S2會A?僅 I 、 IIB.僅 II 、nic?僅 I、mD. I、n、m8

4、. 系統(tǒng)為某進(jìn)程分配了 4 個頁框，該進(jìn)程已訪問的頁號序列為 2,0,2,9,3,4,2,8,2,4,8,4。,5若進(jìn)程要 訪問的下一頁的頁號為 7,依據(jù) LRU 算法，應(yīng)淘汰頁的頁號是 。A. 2B. 3 C. 4 D. 89. 在系統(tǒng)內(nèi)存中設(shè)置磁盤緩沖區(qū)的主要目的是 。A. 減 少 磁 盤 I/O 次數(shù)B.減少平均尋道時間C.提高磁盤麵可靠性D.實(shí)現(xiàn)設(shè)備無關(guān)性10. 在文件的索引節(jié)點(diǎn)中存放直接索引指針 10 個 ,一級和二級索引指針各 1 個。磁盤塊大小為 1KB，每個索引指針占 4 個字節(jié)。若某文件的索引節(jié)點(diǎn)已在內(nèi)存中，則把該文件偏移量(按字節(jié)編址 )為 1234 和307400處所在的

5、磁盤塊讀入內(nèi)存，需訪問的磁盤塊個數(shù)分別是 oA. 1,2 B. 1,3C. 2,3D. 2,411. 在請求分頁系統(tǒng)中，頁面分配策略與頁面置換策略不能組合使用的是 。A.可變分配，全局置換 B.艘分配，局部置換 C.固定分配，全局置換 D.固定分配，局部置換12. 文件系統(tǒng)用位圖法表示磁盤空間的分配情況，位圖存于磁盤的 32? 127 號塊中，每個盤塊占 1024 個字節(jié)，盤塊和塊內(nèi)字節(jié)均從 0 開始編號。假設(shè)要釋放的織號為 409612,貝涖圖中要修改的位 所在 的盤塊號和塊內(nèi)字節(jié)序號分別是 。A. 81、 1B. 81、 2C. 82、 1D. 82、 213. 某硬盤有 200 個磁道（

6、最外側(cè)磁道號為 0），磁道訪問請求序列為： 130,42,180,15,199當(dāng), 前磁 頭位于第 58 號磁道并從外側(cè)向內(nèi)側(cè)移動。 按照 SCAN調(diào)度方法處理完上述請求后， 磁頭移過的磁道數(shù) 是 oA. 208B. 287C. 325D. 38214. 通過 POP3協(xié)議接收郵件時，使用的傳輸層服務(wù)類型是 。A. 無連接不可靠的數(shù)據(jù)傳輸服務(wù)B. 無連接可靠的數(shù)據(jù)傳輸服務(wù)C. 有連接不可靠的數(shù)據(jù)傳輸服務(wù)D. 有鏈接可靠的數(shù)據(jù)傳輸服務(wù)15. 使用兩種編碼方案對比特流 01100111進(jìn)行編碼的結(jié)果如下圖所示，編碼 1 和編碼 2 分別 是_比特流編碼1A. NRZ 和曼徹斯特編碼 B. NRZ

7、和差分曼徹斯特編碼C. NRZI 和曼徹斯特編碼 D. NRZI 和差分曼徹斯特編碼16. 主機(jī)甲通過 128kbps衛(wèi)星鏈路，采用滑動窗口協(xié)議向主機(jī)乙發(fā)送數(shù)據(jù)，鏈路單向傳播延遲為 250ms,幀長為 1000字節(jié)。不考慮確認(rèn)幀的開銷，為使鏈路利用率不小于80%,楨序號的比特數(shù)至少 是A. 3 B. 4 C. 7 D. 817. 下列關(guān)于 CSMA/CD 協(xié)議的敘述中，錯誤的是 。A. 邊發(fā)送麵幀，邊檢測是否發(fā)生沖突B. 適用于無線網(wǎng)絡(luò)，以實(shí)現(xiàn)無線鏈路共享C. 需要根據(jù)網(wǎng)絡(luò)跨距和數(shù)據(jù)傳輸速率限定最小幀長D. 當(dāng)信號傳播延遲趨近 0 時，信道利用率趨近 100%18. 下列關(guān)于交換機(jī)的敘述中，正

8、確的是 oA. 以太網(wǎng)交換機(jī)本質(zhì)上是一種多端口網(wǎng)橋B. 通過交換機(jī)互連的一組工作站構(gòu)成一個沖突域C. 交換機(jī)每個端口臟網(wǎng)絡(luò)構(gòu)成一個獨(dú)立的廣播域D. 以太網(wǎng)交換機(jī)可實(shí)現(xiàn)采用不同網(wǎng)絡(luò)層協(xié)議的網(wǎng)絡(luò)互聯(lián)19. 某路由器的路由表如下表所示：目的網(wǎng)絡(luò)下一跳接口/23S1/25/27S2S/0S4若路由器收到一個目的地址 的 IP分組，則轉(zhuǎn)發(fā)該 IP分組的接口是 。A. SIB. S2 C. S3 D. S420. 主機(jī)甲和主機(jī)乙新建

9、一個 TCP連接，甲的擁塞控制初始閾值為 32KB，甲向乙始終以 MSS=1KB 大小的段發(fā)送數(shù)據(jù)，并一直有數(shù)據(jù)發(fā)送；乙為該連接分配 16KB 接收緩存，并對每個數(shù)據(jù)段進(jìn)行確認(rèn)， 忽 略段傳輸延遲。若乙收到的數(shù)據(jù)全部存入緩存，不被取走，則甲從連接建立成功時刻起，未發(fā)送超時 的 情況下，經(jīng)過 4 個 RTT后，甲的發(fā)送窗口是 。A. 1KBB. 8KB C. 16KB D. 32KB21. 某瀏覽器發(fā)出的 HTTP請求報文如下 : CTT /index.html HTTP/1.1Host: Connection: CloseCookie: 123456 下列敘述中，錯誤的是 。A.該瀏覽器請求瀏

10、覽 indexJitml B IndexJitml 存放在 _hC. 該瀏覽器請求使用持續(xù)連接A. 該瀏覽器曾經(jīng)瀏覽過 www.tesL二、綜合應(yīng)用題：第 41? 47小題，共 70分。22. （ 15分）用單鏈表保存 m個整數(shù)，結(jié)點(diǎn)的結(jié)構(gòu)為： datalink,且 Idatal彡 n （n為正整數(shù)）現(xiàn)要求設(shè)計一個時間復(fù)雜度盡可能高效的算法，對于鏈表中data的絕對值相等的結(jié)點(diǎn)，僅保留第一次出現(xiàn)的結(jié)點(diǎn)而刪除其余絕對值相等的結(jié)點(diǎn)。例如，若給定的單鏈表head如下：HEADI- 21 - 15 - -15 |- -7 - 15 A貝咖！ 1除結(jié)點(diǎn)后的 head為：HEAD-121-15 7要求：1

11、）給出算法的基本設(shè)計思想。2）使用 C或 C+語言，給出單鏈表結(jié)點(diǎn)的數(shù)據(jù)類型定義。3）根據(jù)設(shè)計思想，采用 C或 C+語言描述算法，關(guān)鍵之處給出注釋。4）說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度。23. （8分）已知含有 5 個頂點(diǎn)的圖 G如下圖所示。請回答下列問題：1) 寫出圖 G的鄰接矩陣 A (行、列下標(biāo)從 0開始)。2) 求 A2,矩 陣 A2中位于 0行 3列元素值的含義是什么？3) 若已知具有 n (n2)個頂點(diǎn)的圖的鄰接矩陣為 B， 則 浐 ( 2 mn)中 4 曝元素的含義是什 么？24. (13分)某 16位計龍的主存按字節(jié)編碼，存取單位為 16 位；采用 16位定長指令字格式

12、； CPU 采用單總線結(jié)構(gòu)，主要部分如下圖所示。圖中R0? R3為通用寄存器； T為暫存器； SR為移位寄 存器，可實(shí)現(xiàn)直送(mov)、左移一位 (left)和 右移一 位( right) 3種操作，控制信號為 SRop，SR的 輸出由信號 SRout控制；ALU可實(shí)現(xiàn)直送 A (mova)、A加B (add)、A減B (sub)、A與B (and)、 A或B (or)、非 A (not)、 A 加 1 (inc) 7 種操作，控制信號為 ALUop。請回答下列問題。1) 圖中哪些寄存器是程序員可見的？為何要設(shè)置暫存器 T?2) 控制信號 ALUop 和 SRop的位數(shù)至少各是多少？3) 控制

13、信號 SRout所控制部件的名稱或作用是什么？4) 端點(diǎn) ?中，哪些端點(diǎn)須連接到控制部件的輸出端？5) 為完善單總線數(shù)據(jù)通路，需要在端點(diǎn) ?中相應(yīng)的端點(diǎn)之間添加必要的連線。寫出連線 的起點(diǎn)和終點(diǎn)，以正確表示數(shù)據(jù)的流動方向。6) 為什么二路選擁 MUX 的一僧入端是 2?25. (10分)題 43中描述的計籠，其部分指令執(zhí)行過程的控制信號如下圖所示。題圖 a部分指令控制信號該機(jī)指令格式如下圖所示，支持寄存器直接和寄存器間接兩種尋址方式，尋址方式位分別為 和 1, 通用寄存器 R0? R3 的編號分別為 0、1、2 和 3。指令掻詐碼 目的操指數(shù) 源換作數(shù) 1 源 搡 傷 數(shù)OPMd-Rd“Msl

14、RslMs2Rs2其中： Md, Msl 、Ms2 為尋灶方式位 .Rd 、Rsl, Rs2 為寄存器 _號 ：P三艦指令: 滿 操作欺 1 OP 源操? ;纜 2 - g 的操作 數(shù)地址 v 二 地赴指令 (末 3 叵均 為 0.;:O P 源 搡 作 數(shù) 1 - 目 的 操 數(shù) 地 組 y單 遠(yuǎn) S 指 令 R1shl R21; (R1)?1R2sub R3,(R1)2; (R1)-(R2)R33) 假設(shè)寄存器 X 的輸入和輸出控制信號分別為Xin 和 Xout，其值為 1表示有效，為 0表示 無效(例如， PCout=l 表示 PC 內(nèi)容送總線 )；存儲器控制信號為 MEMop ，用于控

15、制存儲器的讀(read)和寫 ( write)操作。寫出題圖 a中標(biāo)號 ?處的控制信號或控制信號的取值4) 指令“ subRlJO) ”和“ incRl ”的執(zhí)行階段至少各需要多少個時鐘周期？26. (9分)有 A、B 兩人通過信箱進(jìn)行辯論，每個人都從自己的信箱中取得對方的問題。將答案和 向?qū)Ψ教岢龅男聠栴}組成一個郵件放入對方的郵箱中- 假設(shè) A 的信箱最多放 M 個郵件， B 的信箱 最多 放 N 個郵件。初始時 A 的信箱中有 x 個郵件 (0xM), B 的信箱中有 y 個 (Xylink; p-link=r-li nk free(r); free(q);void func (PNODE

16、 h7int n)for(inti=0;ilink!=NULL) 數(shù)組元素初 o m=p-link-data0? p- if(*(q+m)=0) * (q+m) =1; p=p-link;-link-data:-p-link-data;/ 判斷該結(jié)點(diǎn)的 data 是否已出現(xiàn)過 首次出現(xiàn)/保留 PNODE p=h 7 r; int *q,m;q= (int *)malloc (sizeof (int) * (n+1);/ 申 請 n+1 個位置的輔助空間重復(fù)出現(xiàn)/ 刪除12【評分說明】若考生設(shè)計的算法滿足題目的功會腰求且正確，則酌情給分。4）參考答案所給算法的時間復(fù)雜度為0（ m），空間復(fù)雜度為

17、（ Xu）?！驹u分說明】若考生所估計的時間復(fù)雜度和空間復(fù)雜度與考生實(shí)現(xiàn)的算法一致，可給分42. 解答：1）圖 G 的鄰 g 陣 A 如下： 01 r10o I ,1f)0 1 0191I 0 |11o 1 0.2) A2如下 :3 I0 3Jj丨丨 3 2 J2 4 :D 2 2（J2丨3103 1r I22 1 J0行 3列的元素值 3表示從頂點(diǎn) 0到頂點(diǎn) 3之間長度為 2的路徑共有 3條。3）Bm （ 2mn）中 位 于 i行j列（ Oi, jn-1）的#元素的含義是：圖中從頂點(diǎn) i到頂點(diǎn) j 長度 為 m 的路徑條數(shù)。43. 解答：1）程序員可見寄存器為通用寄存器 （R0? R3）和 P

18、C。因為采用了單總線結(jié)構(gòu)， 因此，若無暫存 器 T,則 ALU 的 A、B 端口會同時獲得兩個相同的 ?，使數(shù)據(jù)通路不能正常工作?！驹u分說明】回答通用寄存器（ R0? R3），給分；回答 PC，給分；部分正確，酌情給分。設(shè)置暫 存 器T 的原因若回答用于暫時存放端口 A 的裁據(jù)，則給分，其他答案，酌情給分。2）ALU 共有 7種娜，麟操作控制信號 ALUop至少需要 3位；齡寄存器有 3 種_，其操 作控制信 號 SRop至少需要 2 位。3）信號 SRout所控制的部件是 4 三態(tài)門，用于控制移位器與總線之間數(shù)據(jù)通路的連接與斷開。 【評分說明】只要回答出三態(tài)門或者控制連接 /斷開，即給分。4

19、）端口、（ M 連接到控制部件輸出端?！驹u分 明】答案包含 S）、中任意一個，不給分；答案不全酌情給分。5）孅 1, ，；纖 2, 【評分說明】回答除上述連線以外的其他連線，酌情給分。6）因為每條指令的長度為 16 位，按字節(jié)編址，所以每條指令占用 2 個內(nèi)存單元，順序執(zhí)行時， T4?tt （PC）+2. MUX 的一僧廟為 2,可便于術(shù)（ PQ+2 操作。44. 解答：1）指令操作碼有 7 位，因雌多可定義 27=128條指令。2）令的機(jī)撕碼分別如下：010- “inc R1” 的機(jī)額為： 0000001 0 01 0 00 0 0,即 0240H。 “shl R2, R1 ”的 機(jī)器碼為：

20、 0000010 0 10 0 01 0 0,即 0488H。 “sub R3, （R1） ,R2 ” 的機(jī)器碼為： 0000011 0 11 1 01 0 10,即 06EAH3）各標(biāo)號處的控制信號或控制信號取值如下： 0; mov; taova； left; read; sub; mov; Srout。評分說明】答對兩個給分4）指令“sub Rl, R3, （R2）” 的執(zhí)行階段至少包含 4個時鐘周期；指令“ inc R1 ”的執(zhí)行階段至 少包含 2 個時鐘周期。45. 解答：semaphore Full_A=x;semaphore Empty_A=M-x; semaphore Full_

21、B = y; semaphore Empty_B = N-y; semaphore mutex_A= 1;/FulI_A表示 A的信箱中的郵件數(shù)量 /Empty_A表示A 的信箱中還可存放的郵 4數(shù)量 /FulI_B表示 B的信箱中的郵件數(shù)量 /Empty_B表示 B 的信箱 中還可存放的郵件數(shù)量 /mutex_A用于 A的信箱 互斥 /mutex_B用于 B的信箱互斥semaphore mutex B = 1;AwMe(TRUE)BwMe(TRUE)P(Fun_A);P(FuH_B);P（mutex_A）;從 A 的信箱中取出一個郵件；P（mutex_B）;從 B的信箱中取出一個郵件；V(mutex_A);V(mutex_B);V（Eii5）ty_A）; 回答問題并提出一個新問題；V（Empty_B）; 回答問題并提出一個新問題；P(Einpty_B);P(Empty_A);P（mutex_B）; 將新郵件放入 B 的信箱；P（mutex_A）; 將新郵件放入 A 的信箱；V(mutex_B);V(FuU_B);V(mutex_A);V(FuU_A);【評分說明】1）每對信號量的定義及初值正確，給分。2）每個互斥信號量的 P、V 操作使用正確，各給分。3）每個同步信號