2018年408統考真題及答案(含綜合題解析)

1、2018 年全國碩士研究生入學統一考試計算機科學與技術學科聯考計算機學科專業基礎綜合試題一、單項選擇題（第 140 小題，每小題 2 分，共 80 分。下列每題給出的四個選項中，只有一個選項最符合試題要求）1. 若棧 S1 中保存整數，棧 S2 中保存運算符，函數 F()依次執行下述各步操作：（1）從 S1 中依次彈出兩個操作數 a 和 b；（2）從 S2 中彈出一個運算符 op；（3）執行相應的運算 b op a；（4）將運算結果壓入 S1 中。假定 S1 中的操作數依次是 5, 8, 3, 2（2 在棧頂），S2 中的運算符依次是*, -, +（+在棧頂）。調用 3 次 F()后，S1 棧

2、頂保存的值是。A. -15B. 15C. -20D. 202. 現有隊列 Q 與棧 S，初始時 Q 中的元素依次是 1, 2, 3, 4, 5, 6（1 在隊頭），S 為空。若僅允許下列 3 種操作：出隊并輸出出隊元素；出隊并將出隊元素入棧；出棧并輸出出棧元素，則不能得到的輸出序列是。A. 1, 2, 5, 6, 4, 3B. 2, 3, 4, 5, 6, 1C. 3, 4, 5, 6, 1, 2D. 6, 5, 4, 3, 2, 13. 設有一個 1212 的對稱矩陣 M，將其上三角部分的元素 mi, j（1ij12）按行優先存入 C 語言的一維數組 N 中，元素 m6, 6 在 N 中的下

3、標是。A. 50B. 51C. 55D. 664. 設一棵非空完全二叉樹 T 的所有葉結點均位于同一層，且每個非葉結點都有 2 個子結點。若 T 有 k 個葉結點，則 T 的結點總數是。A. 2k - 1B. 2kC. k2D. 2k - 15. 已知字符集a, b, c, d, e, f，若各字符出現的次數分別為 6, 3, 8, 2, 10, 4，則對應字符集中各字符的哈夫曼編碼可能是。A. 00, 1011, 01, 1010, 11, 100B. 00, 100, 110, 000, 0010, 01C. 10, 1011, 11, 0011, 00, 010D. 0011, 10,

4、11, 0010, 01, 0006. 已知二叉排序樹如下圖所示，元素之間應滿足的大小關系是。A. x1 x2 x5B. x1 x4 x5C. x3 x5 x4D. x4 x3 x57. 下列選項中，不是如下有向圖的拓撲序列的是。A. 1, 5, 2, 3, 6, 4B. 5, 1, 2, 6, 3, 4C. 5, 1, 2, 3, 6, 4D. 5, 2, 1, 6, 3, 48. 高度為 5 的 3 階 B 樹含有的關鍵字個數至少是。A. 15B. 31C. 62D. 2429. 現有長度為 7、初始為空的散列表 HT，散列函數 H(k) = k % 7，用線性探測再散列法解決沖突。將關鍵

5、字 22, 43, 15 依次插入到 HT 后，查找成功的平均查找長度是。A. 1.5B. 1.6C. 2D. 310. 對初始數據序列(8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6)進行希爾排序。若第一趟排序結果為(1, 3, 7, 5, 2, 6, 4, 9, 11, 10, 8)，第二趟排序結果為(1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9)，則兩趟排序采用的增量（間隔）依次是。A. 3, 1B. 3, 2C. 5, 2D. 5, 311. 在將數據序列(6, 1, 5, 9, 8, 4,7)建成大根堆時，正確的序列變化過程是。A. 6, 1

6、, 7, 9, 8, 4, 5 6, 9, 7, 1, 8, 4, 5 9, 6, 7, 1, 8, 4, 5 9, 8, 7, 1, 6, 4, 5B. 6, 9, 5, 1, 8, 4, 7 6, 9, 7, 1, 8, 4, 5 9, 6, 7, 1, 8, 4, 5 9, 8, 7, 1, 6, 4, 5C. 6, 9, 5, 1, 8, 4, 7 9, 6, 5, 1, 8, 4, 7 9, 6, 7, 1, 8, 4, 5 9, 8, 7, 1, 6, 4, 5D. 6, 1, 7, 9, 8, 4, 5 7, 1, 6, 9, 8, 4, 5 7, 9, 6, 1, 8, 4,

7、5 9, 7, 6, 1, 8, 4, 5 9, 8, 6, 1, 7, 4, 512. 馮諾依曼結構計算機中數據采用二進制編碼表示，其主要原因是。I. 二進制的運算規則簡單II. 制造兩個穩態的物理器件較容易 III. 便于用邏輯門電路實現算術運算A. 僅 I、IIB. 僅 I、IIIC. 僅 II、IIID.I、II 和 III13. 假定帶符號整數采用補碼表示，若 int 型變量 x 和 y 的機器數分別是 FFFF FFDFH 和0000 0041H，則 x、y 的值以及 x - y 的機器數分別是。A. x = -65, y = 41，x - y 的機器數溢出B. x = -33,

8、y = 65，x - y 的機器數為 FFFF FF9DHC. x = -33, y = 65，x - y 的機器數為 FFFF FF9EHD. x = -65, y = 41，x - y 的機器數為 FFFF FF96H14. IEEE 754 單精度浮點格式表示的數中，最小的規格化正數是。A. 1.02126B. 1.02127C. 1.02128D. 1.0214915. 某 32 位計算機按字節編址，采用小端（Little Endian）方式。若語句“int i = 0;”對應指令的機器代碼為“C7 45 FC 00 00 00 00”，則語句“int i = 64;”對應指令的機器代

9、碼是。A. C7 45 FC C0 FF FF FFB. C7 45 FC 0C FF FF FFC. C7 45 FC FF FF FF C0D. C7 45 FC FF FF FF 0C16. 整數 x 的機器數為 1101 1000，分別對 x 進行邏輯右移 1 位和算術右移 1 位操作，得到的機器數分別是。222018年全國碩士研究生入學統一考試計算機科學與技術學科聯考計算機學科專業基礎綜合試題A. 1110 1100，1110 1100B.0110 1100，1110 1100C. 1110 1100，0110 1100D.0110 1100，0110 110017. 假定 DRAM

10、 芯片中存儲陣列的行數為 r、列數為 c，對于一個 2K1 位的 DRAM 芯片，為保證其地址引腳數最少，并盡量減小刷新開銷，則 r、c 的取值分別是。A. 2048、1B. 64、32C. 32、64D. 1、204818. 按字節編址的計算機中，某 double 型數組 A 的首地址為 2000H，使用變址尋址和循環結構訪問數組 A，保存數組下標的變址寄存器初值為 0，每次循環取一個數組元素，其偏移地址為變址值乘以 sizeof(double)，取完后變址寄存器內容自動加 1。若某次循環所取元素的地址為 2100H，則進入該次循環時變址寄存器的內容是。A. 25B. 32C. 64D. 1

11、0019. 減法指令“sub R1, R2, R3”的功能為“(R1) - (R2)R3”，該指令執行后將生成進位/借位標志 CF 和溢出標志 OF。若(R1) = FFFF FFFFH，(R2) = FFFF FFF0H，則該減法指令執行后，CF 與 OF 分別為。A. CF = 0, OF = 0B. CF = 1, OF = 0C. CF = 0, OF = 1D. CF = 1, OF = 120. 若某計算機最復雜指令的執行需要完成 5 個子功能，分別由功能部件 AE 實現，各功能部件所需時間分別為 80ps、50ps、50ps、70ps 和 50ps，采用流水線方式執行指令，流水段

12、寄存器延時為 20ps，則 CPU 時鐘周期至少為。A. 60psB. 70psC. 80psD. 100ps21.下列選項中，可提高同步總線數據傳輸率的是。I. 增加總線寬度II. 提高總線工作頻率III.支持突發傳輸IV. 采用地址/數據線復用A.僅 I、IIB. 僅 I、II、IIIC. 僅 III、IVD.I、II、III 和 IV22.下列關于外部 I/O 中斷的敘述中，正確的是。A. 中斷控制器按所接收中斷請求的先后次序進行中斷優先級排隊B. CPU 響應中斷時，通過執行中斷隱指令完成通用寄存器的保護C. CPU 只有在處于中斷允許狀態時，才能響應外部設備的中斷請求D. 有中斷請求

13、時，CPU 立即暫停當前指令執行，轉去執行中斷服務程序23. 下列關于多任務操作系統的敘述，正確的是。I. 具有并發和并行的特點II. 需要實現對共享資源的保護III. 需要運行在多 CPU 的硬件平臺上A. 僅 IB. 僅 IIC. 僅 I、IID.I、II、III24. 某系統采用基于優先權的非搶占式進程調度策略，完成一次進程調度和進程切換的系統時間開銷為 1s。在 T 時刻就緒隊列中有 3 個進程 P1、P2 和 P3，其在就緒隊列中的等待時間、需要的 CPU 時間和優先權如下表所示。進程等待時間需要的 CPU 時間優先權P130s12s10P215s24s30P318s36s20若優先

14、權值大的進程優先獲得 CPU，從 T 時刻起系統開始進程調度，系統的平均周轉時間為。23A. 54sB. 73sC. 74sD. 75s25. 屬于同一進程的兩個線程 thread1 和 thread2 并發執行，共享初值為 0 的全局變量 x。 thread1 和 thread2 實現對全局變量 x 加 1 的機器級代碼描述如下。thread1thread2mov R1, x/(x) R1mov R2, x/(x) R2inc R1/(R1) + 1 R1inc R2/(R2) + 1 R2mov x, R1/(R1) xmov x, R2/(R2) x在所有可能的指令執行序列中，使 x 的

15、值為 2 的序列個數是。A. 1B. 2C. 3D. 426. 假設系統中有 4 個同類資源，進程 P1, P2 和 P3 需要的資源數分別為 4, 3 和 1，P1, P2 和P3 已申請到的資源數分別為 2, 1 和 0，則執行安全性檢測算法的結果是。A. 不存在安全序列，系統處于不安全狀態B. 存在多個安全序列，系統處于安全狀態C. 存在唯一安全序列 P3, P1, P2，系統處于安全狀態D. 存在唯一安全序列 P3, P2, P1，系統處于安全狀態27. 下列選項中，可能導致當前進程 P 阻塞的事件是。I. 進程 P 申請臨界資源 II. 進程 P 從磁盤讀數據III. 系統將 CPU

16、 分配給高優先權的進程A.僅 IB. 僅 IIC. 僅 I、IID. I、II、III28.若 x 是管程內的條件變量，則當進程執行 x.wait()時所做的工作是。A. 實現對變量 x 的互斥訪問B. 喚醒一個在 x 上阻塞的進程C. 根據 x 的值判斷該進程是否進入阻塞狀態D. 阻塞該進程，并將之插入 x 的阻塞隊列中29. 當定時器產生時鐘中斷后，由時鐘中斷服務程序更新的部分內容是。I. 內核中時鐘變量的值II. 當前進程占用 CPU 的時間III. 當前進程在時間片內的剩余執行時間A. 僅 I、IIB. 僅 II、IIIC. 僅 I、IIID. I、II、III30. 系統總是訪問磁盤

17、的某個磁道而不響應對其他磁道的訪問請求，這種現象稱為磁臂黏著。下列磁盤調度算法中，不會導致磁臂黏著的是。A. 先來先服務（FCFS）B. 最短尋道時間優先（SSTF）C. 掃描算法（SCAN）D. 循環掃描算法（CSCAN）31. 下列優化方法中，可以提高文件訪問速度的是。I. 提前讀II. 為文件分配連續的簇III. 延遲寫IV. 采用磁盤高速緩存A. 僅 I、IIB. 僅 II、IIIC. 僅 I、III、IVD. I、II、III、IV32. 下列同步機制中，可以實現讓權等待的是。A. Peterson 方法B. swap 指令C. 信號量方法D. TestAndSet 指令33. 下列

18、 TCP/IP 應用層協議中，可以使用傳輸層無連接服務的是。242018年全國碩士研究生入學統一考試計算機科學與技術學科聯考計算機學科專業基礎綜合試題A. FTPB. DNSC. SMTPD. HTTP34. 下列選項中，不屬于物理層接口規范定義范疇的是。A. 接口形狀B. 引腳功能C. 物理地址D. 信號電平35. IEEE 802.11 無線局域網的 MAC 協議 CSMA/CA 進行信道預約的方法是。A. 發送確認幀B. 采用二進制指數退避C. 使用多個 MAC 地址D. 交換 RTS 與 CTS 幀36. 主機甲采用停-等協議向主機乙發送數據，數據傳輸速率是 3kbps，單向傳播延時是

19、200ms，忽略確認幀的傳輸延時。當信道利用率等于 40%時，數據幀的長度為。A. 240 比特B. 400 比特C. 480 比特D. 800 比特37. 路由器 R 通過以太網交換機 S1 和 S2 連接兩個網絡，R 的接口、主機 H1 和 H2 的 IP 地址與 MAC 地址如下圖所示。若 H1 向 H2 發送 1 個 IP 分組 P，則 H1 發出的封裝 P 的以太網幀的目的 MAC 地址、H2 收到的封裝 P 的以太網幀的源 MAC 地址分別是。A. 00-a1-b2-c3-d4-62, 00-1a-2b-3c-4d-52B. 00-a1-b2-c3-d4-62, 00-a1-b2-

20、c3-d4-61C. 00-1a-2b-3c-4d-51, 00-1a-2b-3c-4d-52D. 00-1a-2b-3c-4d-51, 00-a1-b2-c3-d4-6138. 某路由表中有轉發接口相同的 4 條路由表項，其目的網絡地址分別為 /21,/21, /21 和 /21，將該 4 條路由聚合后的目的網絡地址為。A. /19B. /20C. /19D. /2039. UDP 協議實現分用（demultiplexin

21、g）時所依據的頭部字段是。A. 源端口號B. 目的端口號C. 長度D. 校驗和40. 無須轉換即可由 SMTP 協議直接傳輸的內容是。A. JPEG 圖像B. MPEG 視頻C. EXE 文件D. ASCII 文本二、綜合應用題（第 4147 小題，共 70 分）41. （13 分）給定一個含 n（n1）個整數的數組，請設計一個在時間上盡可能高效的算法，找出數組中未出現的最小正整數。例如，數組-5, 3, 2, 3中未出現的最小正整數是 1；數組1, 2, 3中未出現的最小正整數是 4。要求：（1）給出算法的基本設計思想。（2）根據設計思想，采用 C 或 C+語言描述算法，關鍵之處給出注釋。（

22、3）說明你所設計算法的時間復雜度和空間復雜度。42. （12 分）擬建設一個光通信骨干網絡連通 BJ、CS、XA、QD、JN、NJ、TL 和 WH 8 個城市，題 42 圖中無向邊上的權值表示兩個城市間備選光纖的鋪設費用。25題 42 圖請回答下列問題。（1）僅從鋪設費用角度出發，給出所有可能的最經濟的光纖鋪設方案（用帶權圖表示），并計算相應方案的總費用。（2）題 42 圖可采用圖的哪種存儲結構？給出求解問題（1）所使用的算法名稱。（3）假設每個城市采用一個路由器按（1）中得到的最經濟方案組網，主機 H1 直接連接在 TL 的路由器上，主機 H2 直接連接在 BJ 的路由器上。若 H1 向 H

23、2 發送一個 TTL = 5 的 IP 分組，則 H2 是否可以收到該 IP 分組？43. （8 分）假定計算機的主頻為 500MHz，CPI 為 4?，F有設備 A 和 B，其數據傳輸速率分別為 2MB/s 和 40MB/s，對應 I/O 接口中各有一個 32 位數據緩沖寄存器。請回答下列問題，要求給出計算過程。（1）若設備 A 采用定時查詢 I/O 方式，每次輸入/輸出都至少執行 10 條指令。設備 A 最多間隔多長時間查詢一次才能不丟失數據？CPU 用于設備 A 輸入/輸出的時間占 CPU 總時間的百分比至少是多少？（2）在中斷 I/O 方式下，若每次中斷響應和中斷處理的總時鐘周期數至少為

24、 400，則設備 B 能否采用中斷 I/O 方式？為什么？（3）若設備 B 采用 DMA 方式，每次 DMA 傳送的數據塊大小為 1000B，CPU 用于 DMA 預處理和后處理的總時鐘周期數為 500，則 CPU 用于設備 B 輸入/輸出的時間占 CPU 總時間的百分比最大是多少？44. （15 分）某計算機采用頁式虛擬存儲管理方式，按字節編址。CPU 進行存儲訪問的過程如題 44 圖所示。根據題 44 圖回答下列問題。（1）主存物理地址占多少位?（2）TLB 采用什么映射方式？TLB 是用 SRAM 還是用 DRAM 實現？（3）Cache 采用什么映射方式？若 Cache 采用 LRU

25、替換算法和回寫（Write Back）策略，則 Cache 每行中除數據（Data）、Tag 和有效位，還應有哪些附加位？Cache 的總容量是多少？ Cache 中有效位的作用是什么？（4）若 CPU 給出的虛擬地址為 0008 C040H，則對應的物理地址是多少？是否在 Cache 中命中？說明理由。若 CPU 給出的虛擬地址為 0007 C260H，則該地址所在主存塊映射到的 Cache 組號是多少？262018年全國碩士研究生入學統一考試計算機科學與技術學科聯考計算機學科專業基礎綜合試題題 44 圖45. （8 分）請根據題 44 圖給出的虛擬存儲管理方式，回答下列問題。（1）某虛擬地

26、址對應的頁目錄號為 6，在相應的頁表中對應的頁號為 6，頁內偏移量為 8，該虛擬地址的十六進制表示是什么？（2）寄存器 PDBR 用于保存當前進程的頁目錄起始地址，該地址是物理地址還是虛擬地址？進程切換時，PDBR 的內容是否會變化？說明理由。同一進程的線程切換時，PDBR 的內容是否會變化？說明理由。（3）為了支持改進型 CLOCK 置換算法，需要在頁表項中設置哪些字段？46. （7 分）某文件系統采用索引結點存放文件的屬性和地址信息，簇大小為 4KB。每個文件索引結點占 64B，有 11 個地址項，其中直接地址項 8 個，一級、二級和三級間接地址項各 1 個，每個地址項長度為 4B。請回答

27、下列問題。（1）該文件系統能支持的最大文件長度是多少？（給出計算表達式即可。）（2）文件系統用 1M（1M = 220）個簇存放文件索引結點，用 512M 個簇存放文件數據。若一個圖像文件的大小為 5600B，則該文件系統最多能存放多少個圖像文件？（3）若文件 F1 的大小為 6KB，文件 F2 的大小為 40KB，則該文件系統獲取 F1 和 F2 最后一個簇的簇號需要的時間是否相同？為什么？47. （7 分）某公司的網絡如題 47 圖所示。IP 地址空間 /24 被均分給銷售部和技術部兩個子網，并已分別為部分主機和路由器接口分配了 IP 地址，銷售部子網的 MTU =

28、1500B，技術部子網的 MTU = 800B。請回答下列問題。（1）銷售部子網的廣播地址是什么？技術部子網的子網地址是什么？若每個主機僅分配一個 IP 地址，則技術部子網還可以連接多少臺主機？27題 47 圖（2）假設主機 向主機 08 發送一個總長度為 1500B 的 IP 分組，IP 分組的頭部長度為 20B，路由器在通過接口 F1 轉發該 IP 分組時進行了分片。若分片時盡可能分為最大片，則一個最大 IP 分片封裝數據的字節數是多少？至少需要分為幾個分片？每個分片的片偏移量是多少？2018 年計算機學科專業基礎綜合試題參考答案一、單項選擇題

29、1 B2 C3 A4 A5 A6 C7 D8 B9 C10 D11 A12 D13 C14 A15 A16 B17 C18 B19 A20 D21 B22 C23 C24 D25 B26 A27 C28 D29 D30 A31 D32 C33 B34 C35 D36 D37 D38 C39 B40 D41解答：1）題目要求算法時間上盡可能高效，因此采用空間換時間的辦法。分配一個用于標記的數組 Bn，用來記錄 A 中是否出現了 1n 中的正整數，B0對應正整數 1，Bn-1對應正整數n，初始化 B 中全部為 0。由于 A 中含有 n 個整數，因此可能返回的值是 1n + 1，當 A 中 n 個數

30、恰好為 1n 時返回 n + 1。當數組 A 中出現了小于等于 0 或大于 n 的值時，會導致 1n中出現空余位置，返回結果必然在 1n 中，因此對于 A 中出現了小于等于 0 或大于 n 的值可以不采取任何操作。經過以上分析可以得出算法流程：從 A0開始遍歷 A，若 0 Ai = n，則令 BAi-1 = 1；否則不進行操作。對 A 遍歷結束后，開始遍歷數組 B，若能查找到第一個滿足 Bi = 0 的下標i，返回 i + 1 即為結果，此時說明 A 中未出現的最小正整數在 1n 之間。若 Bi全部不為 0，返回 i + 1（跳出循環時 i = n，i + 1 等于 n + 1），此時說明 A

31、 中未出現的最小正整數是 n + 1。int findMissMin(int A,int n)/標記數組int i,*B;B=(int *)malloc(sizeof(int)*n);/分配空間memset(B,0,sizeof(int)*n);/賦初值為 0282018年全國碩士研究生入學統一考試計算機科學與技術學科聯考計算機學科專業基礎綜合試題for(i=0;i0&Ai=n)BAi-1=1;/掃描數組 B，找到目標值for(i=0;in;i+)if (Bi=0) break;/返回結果return i+1;2）時間復雜度：遍歷 A 一次，遍歷 B 一次，兩次循環內操作步驟為 O(1)量級，

32、因此時間復雜度為 O(n)?？臻g復雜度：額外分配了 Bn，空間復雜度為 O(n)。42解答：1）為了求解最經濟的方案，可以把問題抽象為求無向帶權圖的最小生成樹?？梢圆捎檬謩?Prim 算法或 Kruskal 算法作圖。注意本題最小生成樹有兩種構造，如下圖所示。方案的總費用為 16。2）存儲題中的圖可以采用鄰接矩陣（或鄰接表）。構造最小生成樹采用 Prim 算法（或 Kruskal 算法）。3）TTL = 5，即 IP 分組的生存時間（最大傳遞距離）為 5，方案 1 中 TL 和 BJ 的距離過遠， TTL = 5 不足以讓 IP 分組從 H1 傳送到 H2，因此 H2 不能收到 IP 分組。而

33、方案 2 中 TL 和 BJ 鄰近，H2 可以收到 IP 分組。43解答：1）程序定時向緩存端口查詢數據，由于緩存端口大小有限，必須在傳輸完端口大小的數據時訪問端口，以防止部分數據未被及時讀取而丟失。設備 A 準備 32 位數據所用的時間為 4B/2MB = 2s，所以最多每隔 2s 必須查詢一次，每秒的查詢次數至少是 1s/2s = 5105，每秒 CPU 用于設備 A 輸入/輸出的時間至少為 5105104 = 2107 個時鐘周期，占整個 CPU 時間的百分比至少是 2107/500M = 4%。2）中斷響應和中斷處理的時間為 400(1/500M) = 0.8s，這時只需判斷設備 B

34、準備 32 位數據要多久，如果準備數據的時間小于中斷響應和中斷處理的時間，那么數據就會被刷新，造成丟失。經過計算，設備 B 準備 32 位數據所用的時間為 4B/40MB = 0.1s，因此設備 B 不適合采用中斷 I/O 方式。3）在 DMA 方式中，只有預處理和后處理需要 CPU 處理，數據的傳送過程是由 DMA 控制的。設備 B 每秒的 DMA 次數最多為 40MB/1000B = 40000，CPU 用于設備 B 輸入/輸出的時間最多為 40000500 = 2107 個時鐘周期，占 CPU 總時間的百分比最大為 2107/500M = 4%。44解答：1）物理地址由實頁號和頁內地址拼

35、接，因此其位數為 16 + 12 = 28 或直接可得 20 + 3 +5 = 28。2）TLB 采用全相聯映射，可以把頁表內容調入任一塊空 TLB 項中，TLB 中每項都有一個29比較器，沒有映射規則，只要空閑就行。TLB 采用靜態存儲器 SRAM，讀寫速度快，但成本高，多用于容量較小的高速緩沖存儲器。3）從圖中可以看到，Cache 中每組有兩行，故采用 2 路組相聯映射方式。因為是 2 路組相聯并采用 LRU 替換算法，所以每行（或每組）需要 1 位 LRU 位；因為采用回寫策略，所以每行有 1 位修改位（臟位），根據臟位判斷數據是否被更新，若臟位為 1 則需要寫回內存。28 位物理地址中

36、 Tag 字段占 20 位，組索引字段占 3 位，塊內偏移地址占 5 位，故 Cache 共有 23 = 8 組，每組 2 行，每行有 25 = 32B，故 Cache 總容量為 82(20 + 1 + 1 + 1+328) = 4464位 = 558 字節。Cache 中有效位用來指出所在 Cache 行中的信息是否有效。4）虛擬地址分為兩部分：虛頁號、頁內地址；物理地址分為兩部分：實頁號、頁內地址。利用虛擬地址的虛頁號部分去查找 TLB 表（缺失時從頁表調入），將實頁號取出后和虛擬地址的頁內地址拼接，就形成了物理地址。虛頁號 008CH 恰好在 TLB 表中對應實頁號 0040H（有效位為

37、 1，說明存在），虛擬地址的后 3 位為頁內地址 040H，則對應的物理地址是 0040040H。物理地址為 0040040H，其中高 20 位 00400H 為標志字段，低 5 位 00000B 為塊內偏移量，中間 3 位 010B 為組號 2，因此將 00400H 與 Cache 中的第 2 組兩行中的標志字段同時比較，可以看出，雖然有一個 Cache 行中的標志字段與 00400H 相等，但對應的有效位為 0，而另一 Cache 行的標志字段與 00400H 不相等，故訪問 Cache 不命中。因為物理地址的低 12 位與虛擬地址低 12 位相同，即為 001001100000B。根據物

38、理地址的結構，物理地址的后八位 01100000B 的前三位 011B 是組號，因此該地址所在的主存映射到 Cache 的組號為 3。45解答：1）由圖可知，地址總長度為 32 位，高 20 位為虛頁號，低 12 位為頁內地址，且虛頁號高10 位為頁目錄號，低 10 位為頁號。展開成二進制表示為故十六進制表示為 0180 6008H。2）PDBR 為頁目錄基址地址寄存器（Page-Directory Base Register），其存儲頁目錄表物理內存基地址。進程切換時，PDBR 的內容會變化；同一進程的線程切換時，PDBR 的內容不會變化。每個進程的地址空間、頁目錄和 PDBR 的內容存在一一對應的關系。進程切換時，地址空間發生了變