2011年考研計算機學(xué)科專業(yè)基礎(chǔ)綜合考試真題及答案詳解

1、2011 年計算機學(xué)科專業(yè)基礎(chǔ)綜合及詳解一、單項選擇題：140 小題，每小題 2 分，共 80 分。下列每題給出的四個選項中，只有一個選項是最符合題目要求的。請在答題卡上將所選項的字母涂黑。1設(shè) n 是描述x = 2;規(guī)模的非負整數(shù)，下面程序片段的時間復(fù)雜度是while ( x n/2 )x = 2*x; AO(log2n)DO(n2)BO(n)CO(n log2n)2元素a, b, c, d, e 依次進入初始為空的棧中，若元素進棧后可停留、可出棧，直到所有元素都出棧，則在所有可能的出棧序列中，以元素d 開頭的序列個數(shù)是A33已知循環(huán)隊列B4C5D6在一維數(shù)組A0.n-1 中，且隊列非空時

2、front 和rear 分別指向隊頭元素和隊尾元素。若初始時隊列為空，且要求第 1 個進入隊列的元素始時front 和rear 的值分別是在A0處，則初A0, 0B0, n-1Cn-1, 0Dn-1, n-14若一棵完全二叉樹有 768 個結(jié)點，則該二叉樹中葉結(jié)點的個數(shù)是A257B258C384D3855若一棵二叉樹的前序遍歷序列和后序遍歷序列分別為 1, 2, 3, 4 和 4, 3, 2, 1，則該二叉樹的中序遍歷序列不會是A1, 2, 3, 4B2, 3, 4, 1C3, 2, 4, 1D4, 3, 2, 16已知一棵有 2011 個結(jié)點的樹，其葉結(jié)點個數(shù)為 116，該樹對應(yīng)的二叉樹中無

3、右孩子的結(jié)點個數(shù)是A115B116C1895D18967. 對于下列關(guān)鍵字序列，不可能A95, 22, 91, 24, 94, 71C21, 89, 77, 29, 36, 388. 下列關(guān)于圖的敘述中，正確的是I. 回路是簡單路徑某二叉排序樹中一條查找路徑的序列是B92, 20, 91, 34, 88, 35D12, 25, 71, 68, 33, 34II稀疏圖，用鄰接矩陣比鄰接表更省空間III若有向圖中A僅II拓撲序列，則該圖不回路B僅I、IIC僅IIID僅I、III9. 為提高散列（Hash）表的查找效率，可以采取的正確措施是I. 增大裝填（載）因子II. 設(shè)計III. 處理（碰撞）少

4、的散列函數(shù)（碰撞）時避免產(chǎn)生（堆積）現(xiàn)象A僅IB僅IIC僅I、IID僅II、III10為實現(xiàn)快速排序算法，待排序序列宜采用的方式是A順序B散列C鏈?zhǔn)紻索引新元素 18，將其再調(diào)整為大根堆，11已知序列 25, 13, 10, 12, 9 是大根堆，在序列尾部調(diào)整過程中元A1間進行的比較次數(shù)是B2C4D512下列選項中，描述浮點數(shù)操作速度指標(biāo)的是AMIPSBCPICIPCDMFLOPS13float 型數(shù)據(jù)通常用IEEE 754 單精度浮點數(shù)格式表示。若編譯器將float 型變量 x 分配在一個 32 位浮點寄存器FR1 中，且 x = -8.25，則 FR1 的內(nèi)容是AC104 0000HBC

5、242 0000HCC184 0000HDC1C2 0000H14下列各類AEPROM15某計算機器中，不采用隨機存取方式的是BCDROMCDRAMDSRAM器按字節(jié)編址，主存地址空間大小為 64 MB，現(xiàn)用 4M 8 位的RAM組成 32 MB 的主A22 位器，則B23 位器地址寄存器MAR 的位數(shù)至少是C25 位D26 位16偏移尋址通過將某個寄存器內(nèi)容與一個形式地址相加而生成有效地址。下列尋址不屬于偏移尋址方式的是，A間接尋址B基址尋址C相對尋址D變址尋址17某有一個標(biāo)志寄存器，其中有進位/借位標(biāo)志 CF、零標(biāo)志 ZF、符號標(biāo)志 SF 和溢出標(biāo)志OF，條件轉(zhuǎn)移指令bgt（無符號整數(shù)比較

6、大轉(zhuǎn)移）的轉(zhuǎn)移條件是ACF+OF1B SF+ZF 1C CF+ZF 1D CF+SF 118下列給出的指令系統(tǒng)特點中，有利于實現(xiàn)指令流水線的是I 指令格式規(guī)整且長度一致II指令和數(shù)據(jù)按邊界對齊存放III只有Load/Store 指令才能對操作數(shù)進行A僅I、II19假定不采用B僅II、IIICache 和指令預(yù)取技術(shù)，且C僅I、IIIDI、II、III處于“開中斷”狀態(tài)，則在下列有關(guān)指令執(zhí)行的敘述中，錯誤的是A每個指令周期中CPU 都至少內(nèi)存一次B每個指令周期一定大于或等于一個CPU 時鐘周期C空操作指令的指令周期中任何寄存器的內(nèi)容都被改變D當(dāng)前程序在每條指令執(zhí)行結(jié)束時都可能被外部中斷打斷20在

7、系統(tǒng)總線的數(shù)據(jù)線上，不可能傳輸?shù)氖茿指令C握手（應(yīng)答）信號21某計算機有五級中斷 L4 B操作數(shù) D中斷類型號字為 M4M3M2M1M0，Mi=1（0i4）表示對 LiL0，中斷級中斷進行。若中斷響應(yīng)優(yōu)先級從高到低的順序是 L0L1L2L3L4，且要求中斷處理優(yōu)先級從高到低的順序為 L4L0L2L1L3，則 L1 的中斷處理設(shè)置的中斷字是A11110B01101C00011D01010A 的 I/O，22某計算機處理器主頻為 50 MHz，采用定時一次所用的時鐘周期數(shù)至少為 500。在方式程序運行A 工作期間，為保證數(shù)據(jù)不丟失，每秒需對其至少 200 次，則CPU 用于A 的I/O 的時間占整

8、個CPU 時間的百分比至少是A0.02%B0.05%C0.20%D0.50%23下列選項中，滿足短任務(wù)優(yōu)先且不會發(fā)生饑餓現(xiàn)象的調(diào)度算法是A先來先服務(wù)C時間片輪轉(zhuǎn)24下列選項中，在用戶態(tài)執(zhí)行的是A命令解釋程序C進程調(diào)度程序B高響應(yīng)比優(yōu)先D非搶占式短任務(wù)優(yōu)先B缺頁處理程序D時鐘中斷處理程序25在支持多線程的系統(tǒng)中，進程P 創(chuàng)建的若干個線程不能共享的是A進程P 的代碼段B進程P 中打開的文件C進程P 的全局變量D進程P 中某線程的棧指針26用戶程序發(fā)出磁盤I/O 請求后，系統(tǒng)的正確處理流程是A. 用戶程序系統(tǒng)調(diào)用處理B. 用戶程序系統(tǒng)調(diào)用處理程序斷處理程序驅(qū)動驅(qū)動程序斷處理程序斷處理程序C用戶程序

9、D用戶程序27某時刻進程的驅(qū)動程序系統(tǒng)調(diào)用處理驅(qū)動斷處理程序系統(tǒng)調(diào)用處理程序使用情況如下表所示。此時的安全序列是AP1, P2, P3, P4 CP1, P4, P3, P2BP1, P3, P2, P4D不28在缺頁處理過程中，操作系統(tǒng)執(zhí)行的操作可能是I修改頁表II磁盤I/OIII分配頁框進程已分配尚需可用R1R2R3R1R2R3R1R2R3P1200001021P2120132P3011131P4001200A僅I、IIB僅IIC僅IIIDI、II 和III29I II發(fā)生抖動（thrashing）時，可以采取的有效措施是撤銷部分進程增加磁盤交換區(qū)的容量III提高用戶進程的優(yōu)先級A僅IB僅

10、IIC僅IIID僅I、II30在虛擬內(nèi)存管理中，地址變換機構(gòu)將邏輯地址變換為物理地址，形成該邏輯地址的階段是A編輯B編譯CD裝載31. 某文件占 10 個磁盤塊，現(xiàn)要把該文件磁盤塊逐個讀入主存緩沖區(qū)，并送用戶區(qū)進行分析。假設(shè)一個緩沖區(qū)與一個磁盤塊大小相同，把一個磁盤塊讀入緩沖區(qū)的時間為 100 s， 將緩沖區(qū)的數(shù)據(jù)傳送到用戶區(qū)的時間是50 s，CPU 對一塊數(shù)據(jù)進行分析的時間為50 s。在單緩沖區(qū)和雙緩沖區(qū)結(jié)構(gòu)下，讀入并分析完該文件的時間分別是A1500 s、1000 sB1550 s、1100 s C1550 s、1550 s D2000 s、2000 s32. 有兩個并發(fā)執(zhí)行的進程P1 和

11、P2，共享初值為 1 的變量 x。P1 對 x 加 1，P2 對 x 減 1。加 1 和減 1 操作的指令序列分別如下所示。/ 加 1 操作load R1, x/ 減 1 操作load R2, x decR2store x, R2取x 到寄存器R1 中/incR1將R1 的內(nèi)容存入xstore x, R1兩個操作完成后，x 的值A(chǔ)可能為-1 或 3 C可能為 0、1 或 2/B只能為 1D可能為-1、0、1 或 233TCP/IP 參考模型的層提供的是A無連接不可靠的數(shù)據(jù)報服務(wù)C有連接不可靠的虛電路服務(wù)B無連接可靠的數(shù)據(jù)報服務(wù)D有連接可靠的虛電路服務(wù)34若某通信鏈路的數(shù)據(jù)傳輸速率為 2400

12、bps，采用 4 相位調(diào)制，則該鏈路的率是A600B1200C4800D9600了 0 3 號數(shù)據(jù)幀，現(xiàn)已35數(shù)據(jù)鏈路層采用選擇重傳協(xié)議（SR）傳輸數(shù)據(jù)，方已收到 1 號幀的確認(rèn)，而 0、2 號幀依次超時，則此時需要重傳的幀數(shù)是A1B2C3D436下列選項中，對正確接收到的數(shù)據(jù)幀進行確認(rèn)的MAC 協(xié)議是ACSMABCDMACCSMA/CDDCSMA/CA37某拓撲如下圖所示，路由器R1 只有到達子網(wǎng) /24 的路由。為使R1 可以將IP 分組正確地路由到圖中所有子網(wǎng)，則在 R1 中需要增加的一條路由（目的網(wǎng)掩碼，下一跳）是，子R1192.168.1.

13、0/24R228/25/2530A， B， C，D，28，，28，，38在子網(wǎng) /30 中，能接收目的地址為 的IP 分組的最大主機數(shù)是A0B1C2D439主機甲向

14、主機乙一個(SYN = 1, seq = 11220)的TCP 段，期望與主機乙建立TCP 連接，若主機乙接受該連接請求，則主機乙向主機甲A(SYN = 0, ACK = 0, seq = 11221, ack = 11221)B(SYN = 1, ACK = 1, seq = 11220, ack = 11220)C(SYN = 1, ACK = 1, seq = 11221, ack = 11221)D(SYN = 0, ACK = 0, seq = 11220, ack = 11220)的正確的TCP 段可能是40主機甲與主機乙之間已建立一個TCP 連接，主機甲向主機乙了 3 個連續(xù)的T

15、CP 段，分別包含 300 字節(jié)、400 字節(jié)和 500 字節(jié)的有效載荷，第 3 個段的序號為 900。若主機乙僅正確接收到第 1 和第 3 個段，則主機乙給主機甲的確認(rèn)序號是A300B500C1200D1400二、綜合應(yīng)用題：4147 小題，共 70 分。請將寫在答題紙指定位置上。41（8 分）已知有 6 個頂點（頂點編號為 0 5）的有向帶G，其鄰接矩陣A 為上三角矩陣，按行為主序（行優(yōu)先）保如下的一維數(shù)組中。要求：（1）寫出圖G 的鄰接矩陣A。（2）畫出有向帶G。（3）求圖G 的關(guān)鍵路徑，并計算該關(guān)鍵路徑的長度。42（15 分）一個長度為 L（L1）的升序序列 S，處在第 L/2 個位置

16、的數(shù)稱為S 的中位數(shù)。例如，若序列S1=(11, 13, 15, 17, 19)，則S1 的中位數(shù)是 15。兩個序列的中位數(shù)是含它們所有元素的升序序列的中位數(shù)。例如，若S2=(2, 4, 6, 8, 20)，則S1 和S2 的中位數(shù)是 11。現(xiàn)有兩個等長升序序列 A 和 B，試設(shè)計一個在時間和空間兩方面都盡可能高效的算法， 找出兩個序列A 和B 的中位數(shù)。要求：（1） 給出算法的基本設(shè)計思想。（2） 根據(jù)設(shè)計思想，采用C 或C+或JAVA 語言描述算法，關(guān)鍵之處給出注釋。（3） 說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度。43（11 分）假定在一個 8 位字長的計算機中運行如下類C 程序段：un

17、signed intunsigned int intm = x;intn = y; unsigned intunsigned intx = 134;y = 246;z1 = xy;z2 = x+y;intk1 = mn;intk2 = m+n;若編譯器編譯時將 8 個 8 位寄存器 R1 R8 分別分配給變量 x、y、m、n、z1、z2、k1和 k2。請回答下列。（提示：帶符號整數(shù)用補碼表示）（1） 執(zhí)行上述程序段后，寄存器 R1、R5 和R6 的內(nèi)容分別是什么？（用十六進制表示）（2） 執(zhí)行上述程序段后，變量 m 和 k1 的值分別是多少？（用十進制表示）（3） 上述程序段涉及帶符號整數(shù)加/

18、減、無符號整數(shù)加/減運算，這四種運算能否利用同一個加法器及輔助電路實現(xiàn)？簡述理由。（4）計算機內(nèi)部如何帶符號整數(shù)加/減運算的結(jié)果是否發(fā)生溢出？上述程序段中，哪些帶符號整數(shù)運算語句的執(zhí)行結(jié)果會發(fā)生溢出？44（12 分）某計算機器按字節(jié)編址，虛擬（邏輯）地址空間大小為 16 MB，主存（物理）地址空間大小為 1 MB，頁面大小為 4 KB；Cache 采用直接方式，共 8 行；主存與Cache 之間交換的塊大小為 32 B。系統(tǒng)運行到某一時刻時，頁表的部分內(nèi)容和Cache的部分內(nèi)容分別如題 44-a 圖、題 44-b 圖所示，圖中頁框號及標(biāo)記字段的內(nèi)容為十六進制形式。頁號有效位頁框號行號有效位標(biāo)記

19、0011223344556610200-101D11051064114D0-1061041151020-12B0題 44-a 圖 頁表的部分內(nèi)容題 44-b 圖 Cache 的部分內(nèi)容請回答下列。（1）虛擬地址共有幾位，哪幾位表示虛頁號？物理地址共有幾位，哪幾位表示頁框號（物理頁號）？（2）使用物理地址Cache 時，物理地址應(yīng)劃分成哪幾個字段？要求說明每個字段的位數(shù)及在物理地址中的位置。（3）虛擬地址 001C60H 所在的頁面是否在主存中？若在主存中，則該虛擬地址對應(yīng)的物理地址是什么？（4）假定為該機配置一個 4該地址時是否Cache 命中？要求說明理由。相聯(lián)的 TLB，該 TLB 共可存

20、放 8 個頁表項，若其當(dāng)前內(nèi)容（十六進制）如題 44-c 圖所示，則此時虛擬地址 024BACH 所在的頁面是否在主存中？要求說明理由。組號 有效位 標(biāo)記 頁框號 有效位 標(biāo)記 頁框號 有效位 標(biāo)記 頁框號 有效位 標(biāo)記 頁框號01題 44-c 圖 TLB 的部分內(nèi)容提供 1 個服務(wù)窗口和 10 個供顧客等待的座位。顧客到達45.（8 分）某時，若有空座位，則到取號機上領(lǐng)取一個號，等待叫號。取號機每次僅一位顧客使用。當(dāng)營業(yè)員空閑時，通過叫號選取一位顧客，并為其服務(wù)。顧客和營業(yè)員的活動過程描述如下：cobeginprocess 顧客i從取號機獲得一個號碼； 等待叫號；獲得服務(wù)；process 營

21、業(yè)員while (TRUE)叫號；為顧務(wù)； coend請?zhí)砑颖匾男盘柫亢蚉、V（或wait()、signal()）操作，實現(xiàn)上述過程中的互斥與同0-1001150-10121F10132D0-10087E0-71327127A步。要求寫出完整的過程，說明信號量的含義并賦初值。46.（7 分）某文件系統(tǒng)為一級目錄結(jié)構(gòu)，文件的數(shù)據(jù)寫入磁盤，已寫入的文件不可修改，但可多次創(chuàng)建新文件。請回答如下。（1）在連續(xù)、鏈?zhǔn)?、索引三種文件的數(shù)據(jù)塊組織，哪種更合適？要求說明理由。為定位文件數(shù)據(jù)塊，需在FCB 中設(shè)計哪些相關(guān)描述字段？（2）為快速找到文件，對于 FCB，是集中好？要求說明理由。好，還是與對應(yīng)的文件

22、數(shù)據(jù)塊連續(xù)47（9 分）某主機的 MAC 地址為 00-15-C5-C1-5E-28，IP 地址為 00（私有地址）。題47-a 圖是拓撲，題 47-b 圖是該主機進行Web 請求的 1 個以太網(wǎng)數(shù)據(jù)幀前 80 個字節(jié)的十六進制及ASCII 碼內(nèi)容。MTU=1500 BR005Internet題 47-a 圖拓撲題 47-b 圖 以太網(wǎng)數(shù)據(jù)幀（前 80 字節(jié)）請參考圖中的數(shù)據(jù)回答以下。（1） Web 服務(wù)器的IP 地址是什么？該主機的默認(rèn)網(wǎng)關(guān)的MAC 地址是什么？（2） 該主機在構(gòu)造題 47-b 圖的數(shù)據(jù)幀時，

23、使用什么協(xié)議確定目的 MAC 地址？封裝該協(xié)議請求報文的以太網(wǎng)幀的目的MAC 地址是什么？（3） 假設(shè) HTTP/1.1 協(xié)議以持續(xù)的非流水線方式工作，一次請求-響應(yīng)時間為RTT，rfc.html頁面了 5 個JPEG 小圖像，則從發(fā)出題 47-b 圖中的Web 請求開始到瀏覽器收到全部內(nèi)容為止，需要多少個RTT？（4）該幀所封裝的IP 分組經(jīng)過路由器R 轉(zhuǎn)發(fā)時，需修改IP 分組頭中的哪些字段？注：以太網(wǎng)數(shù)據(jù)幀結(jié)構(gòu)和 IP 分組頭結(jié)構(gòu)分別如題 47-c 圖、題 47-d 圖所示。6 B6 B2 B46-1500 B4 B題 47-c 圖 以太網(wǎng)幀結(jié)構(gòu)比特 08162431頭部長度服務(wù)類型版本總

24、長度標(biāo)識標(biāo)志片偏移生存時間(TTL)協(xié)議頭部校驗和源IP地址目的IP地址題 47-d 圖 IP 分組頭結(jié)構(gòu)目的MAC地址源MAC地址類型數(shù)據(jù)CRC及詳解一、單項選擇題：140 小題，每小題 2 分，共 80 分。下列每題給出的四個選項中，只有一個選項是最符合題目要求的。請在答題卡上將所選項的字母涂黑。1. 【2. 【3. 【4. 【5. 【6. 【7. 【8. 【9. 【10. 【11. 【12. 【13. 【14. 【15. 【16. 【17. 【18. 【19. 【20. 【21. 【22. 【23. 【24. 【25. 【26. 【27. 【】A】B】B】C】C】D】A】C】B】A】B】

25、D】A】B】D】A】C】D】C】C】D】C】B】A】D】B】D28. 【29. 【30. 【31. 【32. 【】D】A】B】B】C33. 【34. 【35. 【36. 【37. 【】A】B】B】D】D38【】C39【】C40【】B二、綜合應(yīng)用題：4147 小題，共 70 分。請將41寫在答題紙指定位置上。【】此題的知識點是圖的以及關(guān)鍵路徑求解的綜合知識。（1）由題可以畫出待定上三角矩陣的結(jié)構(gòu)圖如下（圖中“？”待定元素） 0? ?0? 0? 0? 0 ? ? 0 可以看出，第一行至第五行主對角線上方的元素分別 5、4、3、2、1 個，由此可以畫出壓縮數(shù)組中的元素所屬行的情況，如下圖所示：第三行

26、第一行第二行第四行第五行將個元素填入各行即得鄰接矩陣：（2 分）4030 040650 A= 3 3 0(2)根據(jù)第一步所得矩陣A 容易做出有向帶G，如下：（2 分）0363445233514(3)下圖中粗線箭頭所標(biāo)識的 4 個活動組成G 的關(guān)鍵路徑（3 分）0363442533514由上圖容易求得圖的關(guān)鍵路徑長度為：4+5+4+3=16。42【】此題的知識點是基本算法的靈活運用。（1）算法的基本設(shè)計思想：（5 分）1)比較笨的：將兩升序序列歸并排序，然后求其中位數(shù)，時間復(fù)雜度是O(n)，空間復(fù)雜度O(n)。2) 高效的：分別求兩個升序序列A 和B 的中位數(shù)，設(shè)為a 和b。如果a=b，則 a

27、或者b 即為所求的中位數(shù)。：如果將兩序列歸并排序，則最終序列中，排在子序列 ab 前邊的元素為先前兩序列中排在a 和b 前邊的元素；排在子序列ab 后邊的元素為先前兩序列a 和b 后邊的元素。所以子序列ab 一定位于最終序列的中間，有因為a=b，顯然 a 就是中位數(shù)。如果ab（假設(shè)ab），中位數(shù)只能出現(xiàn)在（a，b）范圍內(nèi)。：同樣可以用歸并排序后的序列來，歸并后排序后必然有形如ab的序列出現(xiàn)，中位數(shù)必然出現(xiàn)在（a，b）范圍內(nèi)。因此可以做如下處理：舍棄a 所在序列A 之中比較小的一半，同時舍棄 b 所在序列B 之中比較大的一半。在保留的兩個升序序列中求出新的中位數(shù)a 和b，重復(fù)上述過程，直到兩個序

28、列只含一個元素為止，則較小者即為所求中位數(shù)。（2）算法實現(xiàn)（高效）：（8 分）int Search(int A, int B, int n)int s1,e1,mid1,s2,e2,mid2;s1=0;e1=n-1;s2=1;e2=n-1;while(s1!=e1|s2!=e2)mid1=(s1+e1)/2;mid2=(s2+e2)/2;if(Amid1=Bmid2)return Amid1;if(Amid1Bmid2)/分別考慮奇數(shù)和偶數(shù)，保持兩個子數(shù)組元素個數(shù)相等if（s1+e1）%2=0）/若元素個數(shù)為奇數(shù)s1=mid1;/舍棄A 中間點以前部分且保留中間點e2=mid2; /舍棄B 中

29、間點以后部分且保留中間點else/若元素個數(shù)為偶數(shù)s1=mid1+1;/舍棄A 中間點以前部分且保留中間點e2=mid2; /舍棄B 中間點以后部分且保留中間點elseif(s1+e1)%2=0)/若元素個數(shù)為奇數(shù)個e1=mid1;/舍棄A 中間點以后部分且保留中間點s2=mid2;/舍棄B 中間點以前部分且保留中間點else/若元素個數(shù)為偶數(shù)個e1=mid1+1；/舍棄A 中間點以后部分且保留中間點s2=mid2；/舍棄B 中間點以前部分且保留中間點您所獲取的資料來源于資料，請資料中心return （As1Bs2 ? As1:Bs2）;(3)上述所給算法的時間、空間復(fù)雜度分別是O(log2n

30、)和O(1)。（2 分）因為每次總的元素個數(shù)變?yōu)樵瓉淼囊话?，所以有?第一次：元素個數(shù)為n/2=n/(21)第二次：元素個數(shù)為n/4=n/(22)第k 次：元素個數(shù)為n/(2k) 最后元素個數(shù)為 2則有n/(2k)=2解得k= log2n 1因此：時間復(fù)雜度為O(log2n)，而空間復(fù)雜度從上述可看出為O(1)。43【】此題的知識點是程序編譯運行寄存器的運用與變化。（1）寄存器R1的是 134，轉(zhuǎn)換成二進制為 1000 0110B，即 86H。寄存器R5的是xy 的內(nèi)容，xy=-112，轉(zhuǎn)換成二進制為 1001 0000B，即 90H。寄存器R6 的是 x+y 的內(nèi)容，x+y=380，轉(zhuǎn)換成二

31、進制為 1 0111 1100B（前面的進位舍棄），即 7CH。由于計算機字長為 8 位，所以無符號整數(shù)能表示的范圍為 0255。而x+y=380，故溢出。（2）m 二進制表示為 1000 0110B，由于 m 是 int 型，所以最為符號位，所以可以得出m 的原碼為：1111 1010（對 1000 0110 除符號位取反加 1），即-122。同理 n的二進制表示為 1111 0110B，故n 的原碼為：1000 1010，轉(zhuǎn)成十進制為-10。所以k1=-122-（-10）=-112.（3）可以利用同一個加法器及輔助電路實現(xiàn)。因為無符號整數(shù)都是以補碼形式，所以運算規(guī)則都是一樣的。但是有一點需

32、要考慮，由于無符號整數(shù)和有符號整數(shù)的表示范圍是不一樣的，所以需要設(shè)置不一樣的溢出電路。（4）帶符號整數(shù)只有 k2 會發(fā)生溢出。分析：8 位帶符號整數(shù)的補碼取值范圍為：-128+127，而 k2=m+n=-122-10=-132，超出范圍，而 k=-112，在范圍-128+127之內(nèi)。三種可以溢出：雙符號位、最進位、符號相同操作數(shù)的運算后與原碼操作數(shù)的符號不同則溢出。44【】此題的知識點是計算機的地址管理。（1）由于虛擬地址空間大小為16MB，且按字節(jié)編址，所以虛擬地址共有24 位（224=16M）。由于頁面大小為 4KB（212=4K），所以虛頁號為前 12 位。由于主存（物理）地址空間大小為

33、 1MB，所以物理地址共有 20 位（220=1M）。由于頁內(nèi)地址 12 位，所以 20-12=8，即前 8 位為頁框號。（2）由于Cache 采用直接方式，所以物理地址應(yīng)劃分成 3 個字段，如下：12 位3 位5 位分析：由于塊大小為 32B，所以字塊內(nèi)地址占 5 位。Cache 共 8 行，故字塊標(biāo)記占 3 位，所以主存字塊標(biāo)記占 20-5-3=12 位。（3）虛擬地址 001C60H 的虛頁號為前 12 位，即 001H=1。查表可知，其有效位為 1， 故在內(nèi)存中。虛頁號為 1 對應(yīng)頁框號為 04H，故物理地址為 04C60H。由于采用的是直接方式，所以對應(yīng) Cache 行號為 4。盡管

34、有效位為 1，但是由于標(biāo)記位 04CH064H，故不命中。（4）由于采用了 4應(yīng)劃分成 3 個字段，如下：相聯(lián)的，所以 Cache 被分為 2 組，每組 4 行。所以物理地址11 位1 位12 位將 024BACH 轉(zhuǎn)成二進制為：0000 0010 010 0 1011 1010 1100，可以看出組號為 0，標(biāo)記為0000 0010 010，換成十六進制為 0000 0001 0010（補一個 0），即 012H，從圖 44-c 中的 0 組可以看出，標(biāo)記為 012H 頁面的頁框號為 1F，故虛擬地址 024BACH 所在的頁面在主存中。45.【】此題的知識點是共享的使用與 P、V 操作以防

35、止死鎖。Semaphore seets =10;/表示空余座位數(shù)量的信號量，初值為 10Semaphore mutex = 1; /管理取號機的互斥信號量，初值為 1，表示取號機空閑Semaphore custom = 0; /表示顧客數(shù)量的Process 顧客P(seets); /找個空座位P(mutex); /在看看取號機是否空閑從取號機取號；V(mutex) /放開那個取號機信號量，初值為 0標(biāo)記位組號頁內(nèi)地址主存字塊標(biāo)記Cache 字塊標(biāo)記字塊內(nèi)地址V(custom); /取到號，告訴營業(yè)員有顧客等待叫號；V(seets) /被叫號，離開座位接受服務(wù)；Process 營業(yè)員While(true)P(custom); /看看有沒有等待的顧客叫號；為顧務(wù)；46.【】此題的知識點是文件系統(tǒng)中數(shù)據(jù)的組織方式，及文件的查找。（1）連續(xù)更合適。因為一次寫入不，而且寫入文件之后不需要修改，連續(xù)的數(shù)據(jù)塊組織方式很適合寫入磁盤不