萬(wàn)學(xué)海文試題：2011年考研真題及答案解析之計(jì)算機(jī)

1、2021年全國(guó)碩士研究生入學(xué)考試計(jì)算機(jī)科學(xué)與技術(shù)入學(xué)考試試題一、單項(xiàng)選擇題：140小題，每題2分，共80分。以下每題給出的四 個(gè)選項(xiàng)中， 只有一個(gè)選項(xiàng)是最符合題目要求的。 請(qǐng)?jiān)诖痤}卡上將所選項(xiàng)的字母涂 黑。1. 設(shè)n是描述問(wèn)題規(guī)模的非負(fù)整數(shù)，下面程序片段的時(shí)間復(fù)雜度是x = 2;while ( x n/2 )x = 2*x;A. O(log2n) B.O(n) C.O(n log2n) D.O(n2)2. 元素 a, b, c, d, e 依次進(jìn)入初始為空的棧中，假設(shè)元素進(jìn)棧后可停留、可 出棧，直到所有元素都出棧， 那么在所有可能的出棧序列中， 以元素 d 開(kāi)頭的序列 個(gè)數(shù)是A. 3 B.4

2、C.5 D.63. 循環(huán)隊(duì)列存儲(chǔ)在一維數(shù)組 A0.n-1 中，且隊(duì)列非空時(shí)front和rear 分別指向隊(duì)頭元素和隊(duì)尾元素。 假設(shè)初始時(shí)隊(duì)列為空， 且要求第 1 個(gè)進(jìn)入隊(duì)列的元 素存儲(chǔ)在 A0 處，那么初始時(shí) front 和 rear 的值分別是A. 0, 0 B.0, n-1 C.n-1, 0 D.n-1, n-14. 假設(shè)一棵完全二叉樹(shù)有 768 個(gè)結(jié)點(diǎn)，那么該二叉樹(shù)中葉結(jié)點(diǎn)的個(gè)數(shù)是A. 257 B.258 C.384 D.3855. 假設(shè)一棵二叉樹(shù)的前序遍歷序列和后序遍歷序列分別為1, 2, 3, 4和4, 3,2, 1 ，那么該二叉樹(shù)的中序遍歷序列不會(huì)是A.1, 2, 3, 4 B.2

3、, 3, 4, 1 C.3, 2, 4, 1 D.4, 3, 2, 16. 一棵有 2021 個(gè)結(jié)點(diǎn)的樹(shù)，其葉結(jié)點(diǎn)個(gè)數(shù)為 116，該樹(shù)對(duì)應(yīng)的二叉樹(shù) 中無(wú)右孩子的結(jié)點(diǎn)個(gè)數(shù)是A.115 B.116 C.1895 D.18967. 對(duì)于以下關(guān)鍵字序列， 不可能構(gòu)成某二叉排序樹(shù)中一條查找路徑的序列是A.95, 22, 91, 24, 94, 71 B.92, 20, 91, 34, 88, 35C.21, 89, 77, 29, 36, 38 D.12, 25, 71, 68, 33, 348. 以下關(guān)于圖的表達(dá)中，正確的選項(xiàng)是I. 回路是簡(jiǎn)單路徑II. 存儲(chǔ)稀疏圖，用鄰接矩陣比鄰接表更省空間III.

4、 假設(shè)有向圖中存在拓?fù)湫蛄校敲丛搱D不存在回路A.僅 II B.僅 I、II C.僅 III D. 僅 I、III9. 為提高散列Hash表的查找效率，可以采取的正確措施是I. 增大裝填載因子II. 設(shè)計(jì)沖突碰撞少的散列函數(shù)III. 處理沖突碰撞時(shí)防止產(chǎn)生聚集 堆積現(xiàn)象A.僅 I B.僅 II C.僅 I、II D.僅 II、III10. 為實(shí)現(xiàn)快速排序算法，待排序序列宜采用的存儲(chǔ)方式是A .順序存儲(chǔ) B. 散列存儲(chǔ) C. 鏈?zhǔn)酱鎯?chǔ) D. 索引存儲(chǔ)11. 序列 25, 13, 10, 12, 9是大根堆，在序列尾部插入新元素 18，將其再調(diào)整為大根堆，調(diào)整過(guò)程中元素之間進(jìn)行的比擬次數(shù)是A.1

5、B.2 C.4 D.512. 以下選項(xiàng)中，描述浮點(diǎn)數(shù)操作速度指標(biāo)的是A.MIPS B.CPI C.IPC D.MFLOPS13. float 型數(shù)據(jù)通常用 IEEE 754單精度浮點(diǎn)數(shù)格式表示。假設(shè)編譯器將 float型變量x分配在一個(gè)32位浮點(diǎn)存放器FR1中，且x = -8.25 ，那么FR1的內(nèi)容是A.C104 0000H B.C242 0000H C.C184 0000H D.C1C2 0000H14. 以下各類存儲(chǔ)器中，不采用隨機(jī)存取方式的是A.EPROM B.CDROM C.DRAM D.SRAM15. 某計(jì)算機(jī)存儲(chǔ)器按字節(jié)編址，主存地址空間大小為 64 MB現(xiàn)用4M X 8 位的R

6、AM芯片組成32 MB的主存儲(chǔ)器，那么存儲(chǔ)器地址存放器 MAF的位數(shù)至少是A.22 位 B.23 位 C.25 位 D.26 位16. 偏移尋址通過(guò)將某個(gè)存放器內(nèi)容與一個(gè)形式地址相加而生成有效地址。 以下尋址方式中，不屬于偏移尋址方式的是A. 間接尋址 B. 基址尋址 C. 相對(duì)尋址 D. 變址尋址17. 某機(jī)器有一個(gè)標(biāo)志存放器，其中有進(jìn)位/借位標(biāo)志CF、零標(biāo)志ZF、符號(hào) 標(biāo)志SF和溢出標(biāo)志OF條件轉(zhuǎn)移指令bgt無(wú)符號(hào)整數(shù)比擬大于時(shí)轉(zhuǎn)移的轉(zhuǎn)移 條件是A.CF+OF=1 B. =1 C. =1 D. =118. 以下給出的指令系統(tǒng)特點(diǎn)中，有利于實(shí)現(xiàn)指令流水線的是I. 指令格式規(guī)整且長(zhǎng)度一致 II

7、. 指令和數(shù)據(jù)按邊界對(duì)齊存放III. 只有 Load/Store 指令才能對(duì)操作數(shù)進(jìn)行存儲(chǔ)訪問(wèn)A.僅 I、II B.僅 II、III C. 僅 I、III D.l 、II、III19. 假定不采用Cache和指令預(yù)取技術(shù)，且機(jī)器處于“開(kāi)中斷狀態(tài)，那么在 以下有關(guān)指令執(zhí)行的表達(dá)中，錯(cuò)誤的選項(xiàng)是A. 每個(gè)指令周期中CPU都至少訪問(wèn)內(nèi)存一次B. 每個(gè)指令周期一定大于或等于一個(gè) CPU時(shí)鐘周期C. 空操作指令的指令周期中任何存放器的內(nèi)容都不會(huì)被改變D. 當(dāng)前程序在每條指令執(zhí)行結(jié)束時(shí)都可能被外部中斷打斷20. 在系統(tǒng)總線的數(shù)據(jù)線上，不可能傳輸?shù)氖茿. 指令 B. 操作數(shù)C.握手應(yīng)答信號(hào)D.中斷類型號(hào)21

8、. 某計(jì)算機(jī)有五級(jí)中斷 L4 L0,中斷屏蔽字為 M4M3M2M1，0=10 i 1)的升序序列S,處在第e L/2個(gè)位置的數(shù)稱 為S的中位數(shù)。例如，假設(shè)序列 S仁(11, 13, 15, 17, 19)，那么S1的中位數(shù)是15。 兩個(gè)序列的中位數(shù)是含它們所有元素的升序序列的中位數(shù)。例如，假設(shè) S2=(2, 4, 6, 8, 20)，那么S1和S2的中位數(shù)是11。現(xiàn)有兩個(gè)等長(zhǎng)升序序列 A和B,試設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面都盡可能高效的算法，找出兩個(gè)序列A 和 B 的中位數(shù)。要求：(1) 給出算法的根本設(shè)計(jì)思想。(2) 根據(jù)設(shè)計(jì)思想，采用C或C+或 JAVA語(yǔ)言描述算法，關(guān)鍵之處給出注釋。(3)

9、 說(shuō)明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。43. (11分)假定在一個(gè)8位字長(zhǎng)的計(jì)算機(jī)中運(yùn)行如下類 C程序段：unsigned int x = 134;unsigned int y = 246;int m = x;int n = y;unsigned int z1 = x - y;unsigned int z2 = x+y;int k1 = m - n;int k2 = m+n;假設(shè)編譯器編譯時(shí)將 8 個(gè) 8 位存放器 R1 R8 分別分配給變量 x、y、m、n、 z1、z2、k1和k2。請(qǐng)答復(fù)以下問(wèn)題。(提示：帶符號(hào)整數(shù)用補(bǔ)碼表示)(1) 執(zhí)行上述程序段后，存放器 R1、R5和R6的內(nèi)容分

10、別是什么？(用十六進(jìn) 制表示 )(2) 執(zhí)行上述程序段后，變量 m和k1的值分別是多少?(用十進(jìn)制表示)(3) 上述程序段涉及帶符號(hào)整數(shù)加 / 減、無(wú)符號(hào)整數(shù)加 / 減運(yùn)算，這四種運(yùn)算 能否利用同一個(gè)加法器及輔助電路實(shí)現(xiàn) ?簡(jiǎn)述理由。(4) 計(jì)算機(jī)內(nèi)部如何判斷帶符號(hào)整數(shù)加 /減運(yùn)算的結(jié)果是否發(fā)生溢出 ?上述程 序段中，哪些帶符號(hào)整數(shù)運(yùn)算語(yǔ)句的執(zhí)行結(jié)果會(huì)發(fā)生溢出 ?44. (12 分)某計(jì)算機(jī)存儲(chǔ)器按字節(jié)編址， 虛擬(邏輯)地址空間大小為 16 MB， 主存(物理)地址空間大小為1 MB,頁(yè)面大小為4 KB;Cache采用直接映射方式， 共8行;主存與Cache之間交換的塊大小為32 B。系統(tǒng)運(yùn)

11、行到某一時(shí)刻時(shí)，頁(yè)表 的局部?jī)?nèi)容和Cache的局部?jī)?nèi)容分別如題44-a圖、題44-b圖所示，圖中頁(yè)框號(hào) 及標(biāo)記字段的內(nèi)容為十六進(jìn)制形式。虛頁(yè)號(hào)有效位頁(yè)框號(hào)行號(hào)有效位標(biāo)記0106 01020 1104- 10 -2115 2101D 3102 31105 40-41064 512B5114D 60 -60 -7132 7127A 題 44-a 圖 頁(yè)表的局部?jī)?nèi)容 題 44-b 圖 Cache 的局部?jī)?nèi)容請(qǐng)答復(fù)以下問(wèn)題。(1) 虛擬地址共有幾位， 哪幾位表示虛頁(yè)號(hào) ?物理地址共有幾位， 哪幾位表示 頁(yè)框號(hào)(物理頁(yè)號(hào))?(2) 使用物理地址訪問(wèn)Cache時(shí)，物理地址應(yīng)劃分成哪幾個(gè)字段？要求說(shuō)明每 個(gè)

12、字段的位數(shù)及在物理地址中的位置。(3) 虛擬地址001C60H所在的頁(yè)面是否在主存中？假設(shè)在主存中，那么該虛擬地址 對(duì)應(yīng)的物理地址是什么？訪問(wèn)該地址時(shí)是否Cache命中？要求說(shuō)明理由。假定為該機(jī)配置一個(gè)4路組相聯(lián)的TLB,該TLB共可存放8個(gè)頁(yè)表項(xiàng)， 假設(shè)其當(dāng)前內(nèi)容(十六進(jìn)制)如題44-c圖所示，那么此時(shí)虛擬地址024BACH所在的頁(yè) 面是否在主存中 ?要求說(shuō)明理由。組號(hào)有效位標(biāo)記頁(yè)框號(hào)有效位標(biāo)記頁(yè)框號(hào)有效位標(biāo)記頁(yè)框號(hào)有效位標(biāo)記頁(yè) 框號(hào)00- - 1001150- - 10121F110132D0- 10087E0-題 44-c 圖 TLB 的局部?jī)?nèi)容45. (8 分)某銀行提供 1 個(gè)效勞窗

13、口和 1 0個(gè)供顧客等待的座位。 顧客到達(dá)銀 行時(shí)，假設(shè)有空座位，那么到取號(hào)機(jī)上領(lǐng)取一個(gè)號(hào)，等待叫號(hào)。取號(hào)機(jī)每次僅允許一位顧客使用。當(dāng)營(yíng)業(yè)員空閑時(shí)，通過(guò)叫號(hào)選取一位顧客，并為其效勞。顧客和營(yíng) 業(yè)員的活動(dòng)過(guò)程描述如下：cobeginprocess 顧客 i從取號(hào)機(jī)獲得一個(gè)號(hào)碼 ;等待叫號(hào);獲得效勞;process 營(yíng)業(yè)員while (TRUE)叫號(hào);為顧客效勞 ; coend請(qǐng)?zhí)砑颖匾男盘?hào)量和 P、V( 或 wait() 、 signal() 操作，實(shí)現(xiàn)上述過(guò)程中 的互斥與同步。要求寫(xiě)出完整的過(guò)程，說(shuō)明信號(hào)量的含義并賦初值。46. (7 分) 某文件系統(tǒng)為一級(jí)目錄結(jié)構(gòu)，文件的數(shù)據(jù)一次性寫(xiě)入磁盤(pán)

14、，已寫(xiě) 入的文件不可修改，但可屢次創(chuàng)立新文件。請(qǐng)答復(fù)如下問(wèn)題。(1) 在連續(xù)、 鏈?zhǔn)健⑺饕N文件的數(shù)據(jù)塊組織方式中， 哪種更適宜 ?要求說(shuō) 明理由。為定位文件數(shù)據(jù)塊，需在 FCB中設(shè)計(jì)哪些相關(guān)描述字段？(2) 為快速找到文件，對(duì)于FCB是集中存儲(chǔ)好，還是與對(duì)應(yīng)的文件數(shù)據(jù)塊 連續(xù)存儲(chǔ)好 ?要求說(shuō)明理由。47. (9分)某主機(jī)的 MAC地址為00-15-C5-C1-5E-28，IP地址為 00( 私有地址 )。題 47-a 圖是網(wǎng)絡(luò)拓?fù)?，題 47-b 圖是該主機(jī)進(jìn)行 Web 請(qǐng)求的 1 個(gè)以太網(wǎng)數(shù)據(jù)幀前 80 個(gè)字節(jié)的十六進(jìn)制及 ASCII 碼內(nèi)容。題 47-a 圖 網(wǎng)絡(luò)拓?fù)?/p>

15、題 47-b 圖 以太網(wǎng)數(shù)據(jù)幀 ( 前 80 字節(jié) )請(qǐng)參考圖中的數(shù)據(jù)答復(fù)以下問(wèn)題。(1)Web效勞器的IP地址是什么？該主機(jī)的默認(rèn)網(wǎng)關(guān)的 MAC地址是什么？ 該主機(jī)在構(gòu)造題47-b圖的數(shù)據(jù)幀時(shí)，使用什么協(xié)議確定目的MAC地址？封裝該協(xié)議請(qǐng)求報(bào)文的以太網(wǎng)幀的目的MAC地址是什么？(3) 假設(shè) HTTP/1.1 協(xié)議以持續(xù)的非流水線方式工作，一次請(qǐng)求 -響應(yīng)時(shí)間為 RTT rfc.html頁(yè)面引用了 5個(gè)JPEG小圖像，那么從發(fā)出題47-b圖中的Web請(qǐng)求 開(kāi)始到瀏覽器收到全部?jī)?nèi)容為止，需要多少個(gè) RTT?(4) 該幀所封裝的IP分組經(jīng)過(guò)路由器R轉(zhuǎn)發(fā)時(shí)，需修改IP分組頭中的哪些 字段?注：以太網(wǎng)

16、數(shù)據(jù)幀結(jié)構(gòu)和 IP 分組頭結(jié)構(gòu)分別如題 47-c 圖、題 47-d 圖所示。題 47-c 圖 以太網(wǎng)幀結(jié)構(gòu)題 47-d 圖 IP 分組頭結(jié)構(gòu)2021 年全國(guó)碩士研究生入學(xué)考試計(jì)算機(jī)科學(xué)與技術(shù)入學(xué)考試答案及詳解一、單項(xiàng)選擇題：140小題，每題2分，共80分。以下每題給出的四 個(gè)選項(xiàng)中， 只有一個(gè)選項(xiàng)是最符合題目要求的。 請(qǐng)?jiān)诖痤}卡上將所選項(xiàng)的字母涂 黑。1.【答案】A2.【答案】B4.【答案】 C5.【答案】 C6.【答案】 D7.【答案】 A8.【答案】 C9.【答案】 B10.【答案】 A11.【答案】 B12.【答案】 D13.【答案】 A14.【答案】D16.【答案】 A17.【答案】

17、C18.【答案】 D19.【答案】 C20.【答案】 C21.【答案】 D22.【答案】 C23.【答案】 B24.【答案】 A25.【答案】 D26.【答案】D28.【答案】 D29.【答案】 A30.【答案】 B31.【答案】 B32.【答案】 C33.【答案】 A34.【答案】 B35.【答案】 B36.【答案】 D37.【答案】 D38.【答案】 C39.【答案】C40.【答案】 B二、綜合應(yīng)用題：4147小題，共70分。請(qǐng)將答案寫(xiě)在答題紙指定位置上。41.【答案解析】此題考察的知識(shí)點(diǎn)是圖的存儲(chǔ)以及關(guān)鍵路徑求解的綜合知識(shí)。1由題可以畫(huà)出待定上三角矩陣的結(jié)構(gòu)圖如下 圖中“ ?待定元素 可

18、以看出，第一行至第五行主對(duì)角線上方的元素分別 5、 4、 3、 2、 1 個(gè)，由 此可以畫(huà)出壓縮存儲(chǔ)數(shù)組中的元素所屬行的情況，如以下圖所示：第五行第一行第二行第三行第四行將個(gè)元素填入各行即得鄰接矩陣： 2 分A= 根據(jù)第一步所得矩陣A容易做出有向帶權(quán)圖G,如下：2分01234654333(3)以下圖中粗線箭頭所標(biāo)識(shí)的4個(gè)活動(dòng)組成G的關(guān)鍵路徑(3分)0123454654333由上圖容易求得圖的關(guān)鍵路徑長(zhǎng)度為： 4+5+4+3=16。答案解析】此題考察的知識(shí)點(diǎn)是根本算法的靈活運(yùn)用(1) 算法的根本設(shè)計(jì)思想： (5 分)1) 比擬笨的方法：將兩升序序列歸并排序，然后求其中位數(shù)，時(shí)間復(fù)雜度是 O(n)

19、 ，空間復(fù)雜 度 O(n) 。2)高效的方法：分別求兩個(gè)升序序列 A和B的中位數(shù)，設(shè)為a和bo如果a=b,那么a或者b即為所求的中位數(shù)。原因：如果將兩序列歸并排序，那么最終序列中，排在子序列 ab 前邊的元素 為先前兩序列中排在a和b前邊的元素；排在子序列ab后邊的元素為先前兩序列 a和b后邊的元素。所以子序列ab 一定位于最終序列的中間，有因?yàn)閍=b,顯然 a 就是中位數(shù)。如果a b(假設(shè)a原因：同樣可以用歸并排序后的序列來(lái)驗(yàn)證，歸并后排序后必然有形 如ab的序列出現(xiàn)，中位數(shù)必然出現(xiàn)在(a , b)范圍內(nèi)。因此可以做如下處 理：舍棄a所在序列A之中比擬小的一半，同時(shí)舍棄b所在序列B之中比擬大

20、的一半。在保存的兩個(gè)升序序列中求出新的中位數(shù)a和b,重復(fù)上述過(guò)程，直到兩個(gè)序列只含一個(gè)元素為止，那么較小者即為所求中位數(shù)。(2) 算法實(shí)現(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(Amid1 / 分別考慮奇數(shù)和偶數(shù)，保持兩個(gè)子數(shù)組元素個(gè)數(shù)相等 if(s1+e1)%2=0)/ 假設(shè)元素個(gè)數(shù)為

21、奇數(shù)s1=mid1;/ 舍棄 A 中間點(diǎn)以前局部且保存中間點(diǎn)e2=mid2; / 舍棄 B 中間點(diǎn)以后局部且保存中間點(diǎn)else/ 假設(shè)元素個(gè)數(shù)為偶數(shù)s1=mid1+1;/ 舍棄 A 中間點(diǎn)以前局部且保存中間點(diǎn) e2=mid2; / 舍棄 B 中間點(diǎn)以后局部且保存中間點(diǎn) elseif(s1+e1)%2=0)/ 假設(shè)元素個(gè)數(shù)為奇數(shù)個(gè)e1=mid1;/ 舍棄 A 中間點(diǎn)以后局部且保存中間點(diǎn)s2=mid2;/ 舍棄 B 中間點(diǎn)以前局部且保存中間點(diǎn)else / 假設(shè)元素個(gè)數(shù)為偶數(shù)個(gè)e1=mid1+1;/ 舍棄 A 中間點(diǎn)以后局部且保存中間點(diǎn)s2=mid2;/ 舍棄 B 中間點(diǎn)以前局部且保存中間點(diǎn)retu

22、rn (As1 (3) 上述所給算法的時(shí)間、空間復(fù)雜度分別是 O(log2n) 和 O(1)。 (2 分) 因?yàn)槊看慰偟脑貍€(gè)數(shù)變?yōu)樵瓉?lái)的一半，所以有：第一次：元素個(gè)數(shù)為 n/2=n/(21)第二次：元素個(gè)數(shù)為 n/4=n/(22)第 k 次：元素個(gè)數(shù)為 n/(2k) 最后元素個(gè)數(shù)為 2 那么有 n/(2k)=2解得 k= Iog2n - 1因此：時(shí)間復(fù)雜度為 O(log2n) ，而空間復(fù)雜度從上述程序中可看出為 O(1) 。 43.【答案解析】此題考察的知識(shí)點(diǎn)是程序編譯運(yùn)行時(shí)各存放器的運(yùn)用與變化。(1) 存放器R1存儲(chǔ)的是134,轉(zhuǎn)換成二進(jìn)制為1000 0110B,即86耳 存放器 R5存儲(chǔ)

23、的是x-y的內(nèi)容，x-y=-112，轉(zhuǎn)換成二進(jìn)制為1001 0000B,即90耳 寄 存器R6存儲(chǔ)的是x+y的內(nèi)容，x+y=380,轉(zhuǎn)換成二進(jìn)制為1 0111 1100B(前面的 進(jìn)位舍棄)，即7CH由于計(jì)算機(jī)字長(zhǎng)為8位，所以無(wú)符號(hào)整數(shù)能表示的范圍為 0255。而 x+y=380,故溢出。(2) m二進(jìn)制表示為1000 0110B，由于m是int型，所以最高位為符號(hào)位， 所以可以得出m的原碼為：1111 1010(對(duì)1000 0110除符號(hào)位取反加1)，即-122。 同理n的二進(jìn)制表示為1111 0110B，故n的原碼為：1000 1010，轉(zhuǎn)成十進(jìn)制為 -10。所以 k1=-122-(-10

24、)=-112.(3) 可以利用同一個(gè)加法器及輔助電路實(shí)現(xiàn)。因?yàn)闊o(wú)符號(hào)整數(shù)都是以補(bǔ)碼形 式存儲(chǔ)，所以運(yùn)算規(guī)那么都是一樣的。 但是有一點(diǎn)需要考慮， 由于無(wú)符號(hào)整數(shù)和有 符號(hào)整數(shù)的表示范圍是不一樣的，所以需要設(shè)置不一樣的溢出電路。(4) 帶符號(hào)整數(shù)只有 k2 會(huì)發(fā)生溢出。分析： 8位帶符號(hào)整數(shù)的補(bǔ)碼取值范圍 為：-128+127,而 k2=m+n=-122-10=-132,超出范圍，而 k=-112，在范圍-128+127 之內(nèi)。三種方法可以判斷溢出：雙符號(hào)位、最高位進(jìn)位、符號(hào)相同操作數(shù)的運(yùn)算 后與原碼操作數(shù)的符號(hào)不同那么溢出。44.【答案解析】此題考察的知識(shí)點(diǎn)是計(jì)算機(jī)的地址管理。(1)由于虛擬地址

25、空間大小為16MB且按字節(jié)編址，所以虛擬地址共有 24 位(224=16M)。由于頁(yè)面大小為4KB(212=4K),所以虛頁(yè)號(hào)為前12位。由于主存 (物理)地址空間大小為1MB所以物理地址共有20位(220=1M)。由于頁(yè)內(nèi)地址 12 位，所以 20-12=8，即前 8 位為頁(yè)框號(hào)。 由于Cache采用直接映射方式，所以物理地址應(yīng)劃分成3個(gè)字段，如下：12位 3 位 5 位主存字塊標(biāo)記Cache字塊標(biāo)記字塊內(nèi)地址分析：由于塊大小為32B,所以字塊內(nèi)地址占5位。Cache共8行，故字塊 標(biāo)記占 3 位，所以主存字塊標(biāo)記占 20-5-3=12 位。(3)虛擬地址001C60H的虛頁(yè)號(hào)為前12位，即

26、001H=1查表可知，其有效 位為1,故在內(nèi)存中。虛頁(yè)號(hào)為1對(duì)應(yīng)頁(yè)框號(hào)為04H,故物理地址為04C60H由 于采用的是直接映射方式，所以對(duì)應(yīng) Cache行號(hào)為4。盡管有效位為1,但是由 于標(biāo)記位04C卡064H,故不命中。 由于采用了 4路組相聯(lián)的，所以Cache被分為2組，每組4行。所以物 理地址應(yīng)劃分成 3 個(gè)字段，如下：11位 1 位 12 位標(biāo)記位組號(hào)頁(yè)內(nèi)地址將 024BACH專成二進(jìn)制為：0000 0010 010 0 1011 1010 1100，可以看出組 號(hào)為 0，標(biāo)記為 0000 0010 010 ，換成十六進(jìn)制為 0000 0001 0010( 高位補(bǔ)一個(gè) 0)，即012H

27、,從圖44-c中的0組可以看出，標(biāo)記為012H頁(yè)面的頁(yè)框號(hào)為1F, 故虛擬地址024BACH所在的頁(yè)面在主存中。45.【答案解析】此題考察的知識(shí)點(diǎn)是共享資源的使用與P、V操作以防止死鎖。Semaphore seets =10;/ 表示空余座位數(shù)量的資源信號(hào)量，初值為 10Semaphore mutex = 1; / 管理取號(hào)機(jī)的互斥信號(hào)量，初值為 1 ，表示取號(hào) 機(jī)空閑Semaphore custom = 0; / 表示顧客數(shù)量的資源信號(hào)量，初值為 0Process 顧客P(seets); / 找個(gè)空座位P(mutex); / 在看看取號(hào)機(jī)是否空閑從取號(hào)機(jī)取號(hào) ;V(mutex) / 放開(kāi)那個(gè)

28、取號(hào)機(jī)V(custom); / 取到號(hào)，告訴營(yíng)業(yè)員有顧客等待叫號(hào) ;V(seets) / 被叫號(hào)，離開(kāi)座位接受效勞;Process 營(yíng)業(yè)員While(true)P(custom); / 看看有沒(méi)有等待的顧客叫號(hào);為顧客效勞 ;46.【答案解析】 此題考察的知識(shí)點(diǎn)是文件系統(tǒng)中數(shù)據(jù)的組織方式， 及文件的查 找。(1) 連續(xù)更適宜。因?yàn)橐淮螌?xiě)入不存在插入問(wèn)題，而且寫(xiě)入文件之后不需要 修改，連續(xù)的數(shù)據(jù)塊組織方式很適合一次性寫(xiě)入磁盤(pán)不再修改的情況， 同時(shí)連續(xù) 存儲(chǔ)相對(duì)鏈?zhǔn)胶退饕∪チ酥羔樀目臻g開(kāi)銷，支持隨機(jī)查找，查找速度最快。(2) FCB集中存儲(chǔ)較好。FCB#儲(chǔ)有文件的很多重要信息，同時(shí)是文件目錄的 重要組成局部，在檢索時(shí)，通常會(huì)訪問(wèn)對(duì)應(yīng)文件的 FCB如果將FCB集中存儲(chǔ)， 那么可以減少在檢索過(guò)程中產(chǎn)生的訪盤(pán)次數(shù)，提高檢索速度。47.【答案解析】此題考察的知識(shí)點(diǎn)是網(wǎng)絡(luò)層的ARP協(xié)議與路由算法。解題之前， 首先說(shuō)明圖 47-b 中每行前面的 0000、0010、0020等等都不屬于 以太網(wǎng)幀的內(nèi)