2018年計(jì)算機(jī)考研真題及參考答案.pdf

2018 年全國(guó)碩士研究生入學(xué)統(tǒng)一考試 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題 一 單項(xiàng)選擇題 第1 40 小題 每小題2 分 共 80 分 下列每題給出的四個(gè)選項(xiàng)中 只有一個(gè)選項(xiàng)最符合試題要求 1 若棧 S1中保存整數(shù) 棧S2中保存運(yùn)算符 函數(shù)F 依次執(zhí)行下述各步操作 1 從 S1中依次彈出兩個(gè)操作數(shù)a 和 b 2 從 S2中彈出一個(gè)運(yùn)算符op 3 執(zhí)行相應(yīng)的運(yùn)算b op a 4 將運(yùn)算結(jié)果壓人S1中 假定 S1中的操作數(shù)依次是 5 8 3 2 2 在棧頂 S2中的運(yùn)算符依次是 在棧頂 調(diào) 用 3 次 F 后 S1棧頂保存的值是 A 15 B 15 C 20 D 20 2 現(xiàn)有隊(duì)列Q 與棧 S 初始時(shí) Q 中的元素依次是1 2 3 4 5 6 1 在隊(duì)頭 S 為空 若僅允 許下列 3 種操作 出隊(duì)并輸出出隊(duì)元素 出隊(duì)并將出隊(duì)元素人棧 出棧并輸出出棧元素 則不能得到的輸出序列是 A 1 2 5 6 4 3 B 2 3 4 5 6 1 C 3 4 5 6 1 2 D 6 5 4 3 2 1 3 設(shè)有一個(gè)12 12 的對(duì)稱矩陣M 將其上三角部分的元素mi j 1 i j 12 按行優(yōu)先存人C 語(yǔ)言的一維數(shù)組N 中 元素m6 6在 N 中的下標(biāo)是 A 50 B 51 C 55 D 66 4 設(shè)一棵非空完全二叉樹(shù)T 的所有葉結(jié)點(diǎn)均位于同一層 且每個(gè)非葉結(jié)點(diǎn)都有2 個(gè)子結(jié)點(diǎn) 若 T 有 k 個(gè)葉結(jié)點(diǎn) 則T 的結(jié)點(diǎn)總數(shù)是 A 2k 1 B 2k C k 2 D 2 k 1 5 已知字符集 a b c d e f 若各字符出現(xiàn)的次數(shù)分別為6 3 8 2 10 4 則對(duì)應(yīng)字符集中 各字符的哈夫曼編碼可能是 A 00 1011 01 1010 11 100 B 00 100 110 000 0010 01 C 10 1011 11 0011 00 010 D 0011 10 11 0010 01 000 6 已知二叉排序樹(shù)如下圖所示 元素之間應(yīng)滿足的大小關(guān)系是 A x1 x2 x5B x1 x4 x5C x3 x5 x4D x4 x3 x5 7 下列選項(xiàng)中 不是如下有向圖的拓?fù)湫蛄械氖?A 1 5 2 3 6 4 B 5 1 2 6 3 4 C 5 1 2 3 6 4 D 5 2 1 6 3 4 8 高度為 5 的 3 階 B 樹(shù)含有的關(guān)鍵字個(gè)數(shù)至少是 A 15 B 31 C 62 D 242 9 現(xiàn)有長(zhǎng)度為7 初始為空的散列表HT 散列函數(shù)H k k 7 用線性探測(cè)再散列法解決 沖突 將關(guān)鍵字22 43 15 依次插人到HT 后 查找成功的平均查找長(zhǎng)度是 A 1 5 B 1 6 C 2 D 3 10 對(duì)初始數(shù)據(jù)序列 8 3 9 11 2 1 4 7 5 10 6 進(jìn)行希爾排序 若第一趟排序結(jié)果為 1 3 7 5 2 6 4 9 11 10 8 第二趟排序結(jié)果為 1 2 6 4 3 7 5 8 11 10 9 則兩趟排序采用的 增量 間隔 依次是 A 3 1 B 3 2 C 5 2 D 5 3 11 在將數(shù)據(jù)序列 6 1 5 9 8 4 7 建成大根堆時(shí) 正確的序列變化過(guò)程是 A 6 1 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 5 B 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 5 C 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 5 D 6 1 7 9 8 4 5 7 1 6 9 8 4 5 7 9 6 1 8 4 5 9 7 6 1 8 4 5 9 8 6 1 7 4 5 12 馮 諾依曼結(jié)構(gòu)計(jì)算機(jī)中數(shù)據(jù)采用二進(jìn)制編碼表示 其主要原因是 二進(jìn)制的運(yùn)算規(guī)則簡(jiǎn)單 制造兩個(gè)穩(wěn)態(tài)的物理器件較容易 便于用邏輯門電路實(shí)現(xiàn)算術(shù)運(yùn)算 A 僅 B 僅 C 僅 D 和 13 假定帶符號(hào)整數(shù)采用補(bǔ)碼表示 若 int 型變量 x 和 y 的機(jī)器數(shù)分別是FFFF FFDFH 和 0000 0041H 則 x y 的值以及x y 的機(jī)器數(shù)分別是 A x 65 y 41 x y的機(jī)器數(shù)溢出 B x 33 y 65 x y的機(jī)器數(shù)為FFFF FF9DH C x 33 y 65 x y的機(jī)器數(shù)為FFFF FF9EH D x 65 y 41 x y的機(jī)器數(shù)為FFFF FF96H 14 IEEE 754 單精度浮點(diǎn)格式表示的數(shù)中 最小的規(guī)格化正數(shù)是 A 1 0 2 126 B 1 0 2 127C 1 0 2 128D 1 0 2 149 15 某 32 位計(jì)算機(jī)按字節(jié)編址 采用小端 Little Endian 方式 若語(yǔ)令 int i 0 對(duì)應(yīng)指令的 機(jī)器代碼為 C7 45 FC 00 00 00 00 則語(yǔ)句 int i 64 對(duì)應(yīng)指令的機(jī)器代碼是 A C7 45 FC C0 FF FF FF B C7 45 FC 0C FF FF FF C C7 45 FC FF FF FF C0 D C7 45 FC FF FF FF 0C 16 整數(shù) x 的機(jī)器數(shù)為1101 1000 分別對(duì) x 進(jìn)行邏輯右移1 位和算術(shù)右移1 位操作 得到的 機(jī)器數(shù)各是 A 1110 1100 1110 1100 B 0110 1100 1110 1100 C 1110 1100 0110 1100 D 0110 1100 0110 1100 17 假定 DRAM芯片中存儲(chǔ)陣列的行數(shù)為r 列數(shù)為c 對(duì)于一個(gè)2K 1 位的 DRAM 芯片 為保證其地址引腳數(shù)最少 并盡量減少刷新開(kāi)銷 則r c 的取值分別是 A 2048 1 B 64 32 C 32 64 D 1 2048 18 按字節(jié)編址的計(jì)算機(jī)中 某double 型數(shù)組 A 的首地址為2000H 使用變址尋址和循環(huán)結(jié) 構(gòu)訪問(wèn)數(shù)組A 保存數(shù)組下標(biāo)的變址寄存器初值為0 每次循環(huán)取一個(gè)數(shù)組元素 其偏移地址為 變址值乘以sizeof double 取完后變址寄存器內(nèi)容自動(dòng)加1 若某次循環(huán)所取元素的地址為2100H 則進(jìn)入該次循環(huán)時(shí)變址寄存器的內(nèi)容是 A 25 B 32 C 64 D 100 19 減法指令 sub R1 R2 R3 的功能為 R1 R2 R3 該指令執(zhí)行后將生成進(jìn)位 借 位標(biāo)志 CF 和溢出標(biāo)志OF 若 R1 FFFF FFFFH R2 FFFF FFF0H 則該減法指令執(zhí)行 后 CF 與 OF 分別為 A CF 0 OF 0 B CF 1 OF 0 C CF 0 0F 1 D CF 1 OF 1 20 若某計(jì)算機(jī)最復(fù)雜指令的執(zhí)行需要完成5 個(gè)子功能 分別由功能部件A E 實(shí)現(xiàn) 各功能 部件所需時(shí)間分別為80ps 50ps 50ps 70ps 和 50ps 采用流水線方式執(zhí)行指令 流水段寄存器 延時(shí)為 20ps 則CPU 時(shí)鐘周期至少為 A 60 ps B 70 ps C 80 ps D 100 ps 21 下列選項(xiàng)中 可提高同步總線數(shù)據(jù)傳輸率的是 增加總線寬度 提高總線工作頻率 支持突發(fā)傳輸 采用地址 數(shù)據(jù)線復(fù)用 A 僅 B 僅 C 僅 D 和 22 下列關(guān)于外部I O 中斷的敘述中 正確的是 A 中斷控制器按所接收中斷請(qǐng)求的先后次序進(jìn)行中斷優(yōu)先級(jí)排隊(duì) B CPU 響應(yīng)中斷時(shí) 通過(guò)執(zhí)行中斷隱指令完成通用寄存器的保護(hù) C CPU 只有在處于中斷允許狀態(tài)時(shí) 才能響應(yīng)外部設(shè)備的中斷請(qǐng)求 D 有中斷請(qǐng)求時(shí) CPU 立即暫停當(dāng)前指令執(zhí)行 轉(zhuǎn)去執(zhí)行中斷服務(wù)程序 23 下列關(guān)于多任務(wù)操作系統(tǒng)的敘述中 正確的是 具有并發(fā)和并行的特點(diǎn) 需要實(shí)現(xiàn)對(duì)共享資源的保護(hù) 需要運(yùn)行在多CPU 的硬件平臺(tái)上 A 僅 B 僅 C 僅 D 24 某系統(tǒng)采用基于優(yōu)先權(quán)的非搶占式進(jìn)程調(diào)度策略 完成一次進(jìn)程調(diào)度和進(jìn)程切換的系統(tǒng) 時(shí)間開(kāi)銷為1 s 在 T 時(shí)刻就緒隊(duì)列中有3 個(gè)進(jìn)程 P1 P2和 P3 其在就緒隊(duì)列中的等待時(shí)間 需 要的 CPU 時(shí)間和優(yōu)先權(quán)如下表所示 進(jìn)程等待時(shí)間需要的 CPU 時(shí)間優(yōu)先權(quán) P130 s 12 s 10 P215 s 24 s 30 P318 s 36 s 20 若優(yōu)先權(quán)值大的進(jìn)程優(yōu)先獲得CPU 從 T 時(shí)刻起系統(tǒng)開(kāi)始進(jìn)程調(diào)度 則系統(tǒng)的平均周轉(zhuǎn)時(shí)間 為 A 54 s B 73 s C 74 s D 75 s 25 屬于同一進(jìn)程的兩個(gè)線程thread1 和 thread2 并發(fā)執(zhí)行 共享初值為0的全局變量x thread1 和 thread2 實(shí)現(xiàn)對(duì)全局變量x 加 1 的機(jī)器級(jí)代碼描述如下 thread1 thread2 mov R1 x x R1 inc R1 R1 1 R1 mov x R1 R1 x mov R2 x x R2 inc R2 R2 1 R2 mov x R2 R2 x 在所有可能的指令執(zhí)行序列中 使x 的值為 2 的序列個(gè)數(shù)是 A 1 B 2 C 3 D 4 26 假設(shè)系統(tǒng)中有4 個(gè)同類資源 進(jìn)程P1 P2和 P3需要的資源數(shù)分別為4 3 和 1 P1 P2 和 P3已申請(qǐng)到的資源數(shù)分別為 2 1 和 0 則執(zhí)行安全性檢測(cè)算法的結(jié)果是 A 不存在安全序列 系統(tǒng)處于不安全狀態(tài) B 存在多個(gè)安全序列 系統(tǒng)處于安全狀態(tài) C 存在唯一安全序列P3 P1 P2 系統(tǒng)處于安全狀態(tài) D 存在唯一安全序列P3 P2 P1 系統(tǒng)處于安全狀態(tài) 27 下列選項(xiàng)中 可能導(dǎo)致當(dāng)前進(jìn)程P 阻塞的事件是 進(jìn)程 P 申請(qǐng)臨界資源 進(jìn)程 P 從磁盤(pán)讀數(shù)據(jù) 系統(tǒng)將 CPU 分配給高優(yōu)先權(quán)的進(jìn)程 A 僅 B 僅 C 僅 D 28 若 x 是管程內(nèi)的條件變量 則當(dāng)進(jìn)程執(zhí)行x wait 時(shí)所做的工作是 A 實(shí)現(xiàn)對(duì)變量x 的互斥訪問(wèn) B 喚醒一個(gè)在x 上阻塞的進(jìn)程 C 根據(jù) x 的值判斷該進(jìn)程是否進(jìn)人阻塞狀態(tài) D 阻塞該進(jìn)程 并將之插入x 的阻塞隊(duì)列中 29 當(dāng)定時(shí)器產(chǎn)生時(shí)鐘中斷后 由時(shí)鐘中斷服務(wù)程序更新的部分內(nèi)容是 內(nèi)核中時(shí)鐘變量的值 當(dāng)前進(jìn)程占用CPU 的時(shí)間 當(dāng)前進(jìn)程在時(shí)間片內(nèi)的剩余執(zhí)行時(shí)間 A 僅 B 僅 C 僅 D 30 系統(tǒng)總是訪問(wèn)磁盤(pán)的某個(gè)磁道而不響應(yīng)對(duì)其他磁道的訪問(wèn)請(qǐng)求 這種現(xiàn)象稱為磁臂黏著 下列磁盤(pán)調(diào)度算法中 不會(huì)導(dǎo)致磁臂粘著的是 A 先來(lái)先服務(wù) FCFS B 最短尋道時(shí)間優(yōu)先 SSTF C 掃描算法 SCAN D 循環(huán)掃描算法 CSCAN 31 下列優(yōu)化方法中 可以提高文件訪問(wèn)速度的是 提前讀 為文件分配連續(xù)的簇 延遲寫(xiě) 采用磁盤(pán)高速緩存 A 僅 B 僅 C 僅 D 32 在下列同步機(jī)制中 可以實(shí)現(xiàn)讓權(quán)等待的是 A Peterson 方法B swap 指令 C 信號(hào)量方法D TestAndSet 指令 33 下列 TCP IP 應(yīng)用層協(xié)議中 可以使用傳輸層無(wú)連接服務(wù)的是 A FTP B DNS C SMTP D HTTP 34 下列選項(xiàng)中 不屬于物理層接口規(guī)范定義范疇的是 A 接口形狀B 引腳功能C 物理地址D 信號(hào)電平 35 IEEE 802 11 無(wú)線局域網(wǎng)的MAC 協(xié)議 CSMA CA進(jìn)行信道預(yù)約的方法是 A 發(fā)送確認(rèn)幀B 采用二進(jìn)制指數(shù)退避 C 使用多個(gè)MAC 地址D 交換 RTS 與 CTS 幀 36 主機(jī)甲采用停 等協(xié)議向主機(jī)乙發(fā)送數(shù)據(jù) 數(shù)據(jù)傳輸速率是3 kbps 單向傳播延時(shí)是200 ms 忽略確認(rèn)幀的傳輸延時(shí) 當(dāng)信道利用率等于40 時(shí) 數(shù)據(jù)幀的長(zhǎng)度為 A 240 比特B 400 比特C 480 比特D 800 比特 37 路由器 R 通過(guò)以太網(wǎng)交換機(jī)S1 和 S2 連接兩個(gè)網(wǎng)絡(luò) R 的接口 主機(jī)H1 和 H2 的 IP 地 址與 MAC 地址如下圖所示 若H1 向 H2 發(fā)送 1 個(gè) IP 分組 P 則 H1 發(fā)出的封裝P 的以太網(wǎng)幀的 目的 MAC 地址 H2 收到的封裝P 的以太網(wǎng)幀的源MAC 地址分別是 A 00 a1 b2 c3 d4 62 00 1a 2b 3c 4d 52 B 00 a1 b2 c3 d4 62 00 a1 b2 c3 d4 61 C 00 1a 2b 3c 4d 51 00 1a 2b 3c 4d 52 D 00 1a 2b 3c 4d 51 00 a1 b2 c3 d4 61 38 某路由表中有轉(zhuǎn)發(fā)接口相同的4 條路由表項(xiàng) 其目的網(wǎng)絡(luò)地址分別為35 230 32 0 21 35 230 40 0 21 35 230 48 0 21 和 35 230 56 0 21 將該 4 條路由聚合后的目的網(wǎng)絡(luò)地址為 A 35 230 0 0 19 B 35 230 0 0 20 C 35 230 32 0 19 D 35 230 32 0 20 39 UDP 協(xié)議實(shí)現(xiàn)分用 demultiplexing 時(shí)所依據(jù)的頭部字段是 A 源端口號(hào)B 目的端口號(hào)C 長(zhǎng)度D 校驗(yàn)和 40 無(wú)需轉(zhuǎn)換即可由SMTP 協(xié)議直接傳輸?shù)膬?nèi)容是 A JPEG 圖像B MPEG 視頻C EXE 文件D ASCII 文本 二 綜合應(yīng)用題 第41 47 小題 共70 分 41 13 分 給定一個(gè)含n n 1 個(gè)整數(shù)的數(shù)組 請(qǐng)?jiān)O(shè)計(jì)一個(gè)在時(shí)間上盡可能高效的算法 找出數(shù) 組中未出現(xiàn)的最小正整數(shù) 例如 數(shù)組 5 3 2 3 中未出現(xiàn)的最小正整數(shù)是1 數(shù)組 1 2 3 中未出 現(xiàn)的最小正整數(shù)是4 要求 1 給出算法的基本設(shè)計(jì)思想 2 根據(jù)設(shè)計(jì)思想 采用C 或 C 語(yǔ)言描述算法 關(guān)鍵之處給出注釋 3 說(shuō)明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度 42 12 分 擬建設(shè)一個(gè)光通信骨干網(wǎng)絡(luò)連通BJ CS XA QD JN NJ TL 和 WH 等 8 個(gè) 城市 題42 圖中無(wú)向邊上的權(quán)值表示兩個(gè)城市間備選光纜的鋪設(shè)費(fèi)用 請(qǐng)回答下列問(wèn)題 1 僅從鋪設(shè)費(fèi)用角度出發(fā) 給出所有可能的最經(jīng)濟(jì)的光纜鋪設(shè)方案 用帶權(quán)圖表示 并 計(jì)算相應(yīng)方案的總費(fèi)用 2 題 42 圖可采用圖的哪一種存儲(chǔ)結(jié)構(gòu) 給出求解問(wèn)題 1 所使用的算法名稱 3 假設(shè)每個(gè)城市采用一個(gè)路由器按 1 中得到的最經(jīng)濟(jì)方案組網(wǎng) 主機(jī)H1 直接連接在 TL 的路由器上 主機(jī)H2 直接連接在BJ 的路由器上 若H1 向 H2 發(fā)送一個(gè) TTL 5 的 IP 分組 則 H2 是否可以收到該IP 分組 43 8 分 假定計(jì)算機(jī)的主頻為500MHz CPI 為 4 現(xiàn)有設(shè)備A 和 B 其數(shù)據(jù)傳輸率分別為 2MB s 和 40MB s 對(duì)應(yīng) I O 接口中各有一個(gè)32 位數(shù)據(jù)緩沖寄存器 請(qǐng)回答下列問(wèn)題 要求給出 計(jì)算過(guò)程 1 若設(shè)備A 采用定時(shí)查詢I O 方式 每次輸入 輸出都至少執(zhí)行10 條指令 設(shè)備A 最多 間隔多長(zhǎng)時(shí)間查詢一次才能不丟失數(shù)據(jù) CPU 用于設(shè)備 A 輸入 輸出的時(shí)間占CPU 總時(shí)間的百分 比至少是多少 2 在中斷 I O 方式下 若每次中斷響應(yīng)和中斷處理的總時(shí)鐘周期數(shù)至少為400 則設(shè)備B 能否采用中斷I O 方式 為什么 3 若設(shè)備 B 采用 DMA 方式 每次 DMA 傳送的數(shù)據(jù)塊大小1000B CPU 用于 DMA 預(yù)處 理和后處理的總時(shí)鐘周期數(shù)為500 則 CPU 用于設(shè)備 B 輸人 輸出的時(shí)間占CPU 總時(shí)間的百分比 最多是多少 44 15 分 某計(jì)算機(jī)采用頁(yè)式虛擬存儲(chǔ)管理方式 按字節(jié)編址 CPU 進(jìn)行存儲(chǔ)訪問(wèn)的過(guò)程如 題 44 圖所示 題 44 圖 根據(jù)題 44 圖回答下列問(wèn)題 1 主存物理地址占多少位 2 TLB 采用什么映射方式 TLB 用 SRAM 還是 DRAM實(shí)現(xiàn) 3 Cache 采用什么映射方式 若Cache 采用 LRU 替換算法和回寫(xiě) Write Back 策略 則 Cache 每行中除數(shù)據(jù) Data Tag 和有效位外 還應(yīng)有哪些附加位 Cache 總?cè)萘渴嵌嗌?Cache 中有效位的作用是什么 4 若 CPU 給出的虛擬地址為0008 C040H 則對(duì)應(yīng)的物理地址是多少 是否在Cache 中命 中 說(shuō)明理由 若CPU 給出的虛擬地址為0007 C260H 則該地址所在主存塊映射到的Cache 組 號(hào)是多少 45 8 分 請(qǐng)根據(jù)題44 圖給出的虛擬儲(chǔ)管理方式 回答下列問(wèn)題 1 某虛擬地址對(duì)應(yīng)的頁(yè)目錄號(hào)為6 在相應(yīng)的頁(yè)表中對(duì)應(yīng)的頁(yè)號(hào)為6 頁(yè)內(nèi)偏移量為8 該虛擬地址的十六進(jìn)制表示是什么 2 寄存器 PDBR 用于保存當(dāng)前進(jìn)程的頁(yè)目錄起始地址 該地址是物理地址還是虛擬地址 進(jìn)程切換時(shí) PDBR 的內(nèi)容是否會(huì)變化 說(shuō)明理由 同一進(jìn)程的線程切換時(shí) PDBR 的內(nèi)容是否 會(huì)變化 說(shuō)明理由 3 為了支持改進(jìn)型CLOCK 置換算法 需要在頁(yè)表項(xiàng)中設(shè)置哪些字段 46 7 分 某文件系統(tǒng)采用索引節(jié)點(diǎn)存放文件的屬性和地址信息 簇大小為4KB 每個(gè)文件索 引節(jié)點(diǎn)占64B 有 11 個(gè)地址項(xiàng) 其中直接地址項(xiàng)8 個(gè) 一級(jí) 二級(jí)和三級(jí)間接地址項(xiàng)各1 個(gè) 每 個(gè)地址項(xiàng)長(zhǎng)度為4B 請(qǐng)回答下列問(wèn)題 1 該文件系統(tǒng)能支持的最大文件長(zhǎng)度是多少 給出計(jì)算表達(dá)式即可 2 文件系統(tǒng)用1M 1M 2 20 個(gè)簇存放文件索引節(jié)點(diǎn) 用 512M 個(gè)簇存放文件數(shù)據(jù) 若一 個(gè)圖像文件的大小為5600B 則該文件系統(tǒng)最多能存放多少個(gè)這樣的圖像文件 3 若文件F1 的大小為6KB 文件F2 的大小為40KB 則該文系統(tǒng)獲取F1 和 F2 最后一 個(gè)簇的簇號(hào)需要的時(shí)間是否相同 為什么 47 7 分 某公司網(wǎng)絡(luò)如題47 圖所示 IP 地址空間 192 168 1 0 24 被均分給銷售部和技術(shù)部?jī)?個(gè)子網(wǎng) 并已分別為部分主機(jī)和路由器接口分配了IP 地址 銷售部子網(wǎng)的MTU 1500B 技術(shù)部 子網(wǎng)的 MTU 800B 請(qǐng)回答下列問(wèn)題 1 銷售部子網(wǎng)的廣播地址是什么 技術(shù)部子網(wǎng)的子網(wǎng)地址是什么 若每個(gè)主機(jī)僅分配一 個(gè) IP 地址 則技術(shù)部子網(wǎng)還可以連接多少臺(tái)主機(jī) 2 假設(shè)主機(jī)192 168 1 1 向主機(jī) 192 168 1 208 發(fā)送一個(gè)總長(zhǎng)度為1500B 的 IP 分組 IP 分 組的頭部長(zhǎng)度為20B 路由器在通過(guò)接口F1 轉(zhuǎn)發(fā)該 IP 分組時(shí)進(jìn)行了分片 若分片時(shí)盡可能分為 最大片 則一個(gè)最大IP 分片封裝數(shù)據(jù)的字節(jié)數(shù)是多少 至少需要分為幾個(gè)分片 每個(gè)分片的片偏 移量是多少 2018 年計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題參考答案 一 單項(xiàng)選擇題 1 B 2 C 3 A 4 A 5 A 6 C 7 D 8 B 9 C 10 D 11 A 12 D 13 C 14 A 15 A 16 B 17 C 18 B 19 A 20 D 21 B 22 C 23 C 24 D 25 B 26 A 27 C 28 D 29 D 30 A 31 D 32 C 33 B 34 C 35 D 36 D 37 D 38 C 39 B 40 D 二 綜合應(yīng)用題 41 解析 1 題目要求算法時(shí)間上盡可能高效 因此采用空間換時(shí)間的辦法 分配一個(gè)用于標(biāo)記的數(shù) 組 B n 用來(lái)記錄A 中是否出現(xiàn)了1 n 中的正整數(shù) B 0 對(duì)應(yīng)正整數(shù)1 B n 1 對(duì)應(yīng)正整數(shù)n 初 始化 B 中全部為0 由于 A 中含有 n 個(gè)整數(shù) 因此可能返回的值是1 n 1 當(dāng) A 中 n 個(gè)數(shù)恰好為 1 n 時(shí)返回 n 1 當(dāng)數(shù)組 A 中出現(xiàn)了小于等于0 或者大于n 的值時(shí) 會(huì)導(dǎo)致 1 n 中出現(xiàn)空余位置 返回結(jié)果必然在1 n 中 因此對(duì)于A 中出現(xiàn)了小于等于0 或者大于n 的值可以不采取任何操作 經(jīng)過(guò)以上分析可以得出算法流程 從A 0 開(kāi)始遍歷A 若 0 A i n 則令 B A i 1 1 否 則不做操作 對(duì)A 遍歷結(jié)束后 開(kāi)始遍歷數(shù)組B 若能查找到第一個(gè)滿足B i 0的下標(biāo) i 返回 i 1 即為結(jié)果 此時(shí)說(shuō)明A 中未出現(xiàn)的最小正整數(shù)在1 n 之間 若 B i 全部不為0 返回 i 1 跳 出循環(huán)時(shí)i n i 1 等于 n 1 此時(shí)說(shuō)明A 中未出現(xiàn)的最小正整數(shù)是n 1 int findMissMin int A int n int i B 標(biāo)記數(shù)組 B int malloc sizeof int n 分配空間 memset B 0 sizeof int n 賦初值為 0 for i 0 i0 for i 0 i n i 掃描數(shù)組 B 找到目標(biāo)值 if B i 0 break return i 1 返回結(jié)果 3 時(shí)間復(fù)雜度 遍歷A 一次 遍歷B 一次 兩次循環(huán)內(nèi)操作步驟為O 1 量級(jí) 因此時(shí)間復(fù) 雜度為 O n 空間復(fù)雜度 額外分配了B n 空間復(fù)雜度為O n 42 解析 1 為了求解最經(jīng)濟(jì)的方案 可以把問(wèn)題抽象為求無(wú)向帶權(quán)圖的最小生成樹(shù) 可以采用手動(dòng) prim 算法或 kruskal 算法作圖 注意本題最小生成樹(shù)有兩種構(gòu)造 如下圖所示 方案的總費(fèi)用為16 2 存儲(chǔ)題中的圖可以采用鄰接矩陣 或鄰接表 構(gòu)造最小生成樹(shù)采用Prim 算法 或 kruskal 算法 3 TTL 5 即 IP 分組的生存時(shí)間 最大傳遞距離 為5 方案 1 中 TL 和 BJ 的距離過(guò)遠(yuǎn) TTL 5 不足以讓IP 分組從 H1 傳送到 H2 因此 H2 不能收到IP 分組 而方案 2 中 TL 和 BJ 鄰近 H2 可以收到IP 分組 43 解析 1 程序定時(shí)向緩存端口查詢數(shù)據(jù) 由于緩存端口大小有限 必須在傳輸完端口大小的數(shù)據(jù) 時(shí)訪問(wèn)端口 以防止部分?jǐn)?shù)據(jù)沒(méi)有被及時(shí)讀取而丟失 設(shè)備A準(zhǔn)備32 位數(shù)據(jù)所用時(shí)間為 4B 2MB 2us 所以最多每隔2us 必須查詢一次 每秒的查詢次數(shù)至少是1s 2us 5 10 5 每秒 CPU 用于設(shè)備A 輸入 輸出的時(shí)間至少為5 105 10 4 2 107個(gè)時(shí)鐘周期 占整個(gè) CPU 時(shí)間的百分比至 少是 2 107 500M 4 2 中斷響應(yīng)和中斷處理的時(shí)間為400 1 500M 0 8us 這時(shí)只需判斷設(shè)備B 準(zhǔn)備 32 位數(shù) 據(jù)要多久 如果準(zhǔn)備數(shù)據(jù)的時(shí)間小于中斷響應(yīng)和中斷處理的時(shí)間 那么數(shù)據(jù)就會(huì)被刷新 造成丟 失 經(jīng)過(guò)計(jì)算 設(shè)備B 準(zhǔn)備 32 位數(shù)據(jù)所用時(shí)間為4B 40MB 0 1us 因此 設(shè)備B 不適合采用中 斷 I O 方式 3 在 DMA 方式中 只有預(yù)處理和后處理需要CPU 處理 數(shù)據(jù)的傳送過(guò)程是由DMA 控制 設(shè)備 B 每秒的 DMA次數(shù)最多為40MB 1000B 40000 CPU 用于設(shè)備B 輸入 輸出的時(shí)間最多為 40000 500 2 107個(gè)時(shí)鐘周期 占 CPU 總時(shí)間的百分比最多為2 107 500M 4 44 解析 1 物理地址由實(shí)頁(yè)號(hào)和頁(yè)內(nèi)地址拼接 因此其位數(shù)為16 12 28 或直接可得20 3 5 28 2 TLB 采用全相聯(lián)映射 可以把頁(yè)表內(nèi)容調(diào)入任一塊空TLB 項(xiàng)中 TLB 中每項(xiàng)都有一個(gè)比 較器 沒(méi)有映射規(guī)則 只要空閑就行 TLB 采用靜態(tài)存儲(chǔ)器SRAM 讀寫(xiě)速度快 但成本高 多 用于容量較小的高速緩沖存儲(chǔ)器 3 圖中可以看到 Cache 中每組有兩行 故采用2 路組相聯(lián)映射方式 因?yàn)槭?2 路組相聯(lián)并采用LRU 替換算法 所以每行 或每組 需要1 位 LRU 位 因?yàn)椴捎?回寫(xiě)策略 所以每行有1 位修改位 臟位 根據(jù)臟位判斷數(shù)據(jù)是否被更新 如果臟位為1 則需 要寫(xiě)回內(nèi)存 28 位物理地址中Tag 字段占 20 位 組索引字段占3 位 塊內(nèi)偏移地址占5 位 故 Cache 共 有 23 8 組 每組 2 行 每行有 25 32B 故 Cache 總?cè)萘繛?8 2 20 1 1 1 32 8 4464 位 558 字節(jié) Cache中有效位用來(lái)指出所在Cache 行中的信息是否有效 4 虛擬地址分為兩部分 虛頁(yè)號(hào) 頁(yè)內(nèi)地址 物理地址分為兩部分 實(shí)頁(yè)號(hào) 頁(yè)內(nèi)地址 利用虛擬地址的虛頁(yè)號(hào)部分去查找TLB 表 缺失時(shí)從頁(yè)表調(diào)入 將實(shí)頁(yè)號(hào)取出后和虛擬地址的 頁(yè)內(nèi)地址拼接 就形成了物理地址 虛頁(yè)號(hào)008CH 恰好在 TLB 表中對(duì)應(yīng)實(shí)頁(yè)號(hào)0040H 有效位 為 1 說(shuō)明存在 虛擬地址的后3 位為頁(yè)內(nèi)地址040H 則對(duì)應(yīng)的物理地址是0040040H 物理地址為0040040H 其中高20 位 00400H 為標(biāo)志字段 低5 位 00000B 為塊內(nèi)偏移量 中間 3 位 010B 為組號(hào) 2 因此將 00400H 與 Cache 中的第 2 組兩行中的標(biāo)志字段同時(shí)比較 可以 看出 雖然有一個(gè)Cache 行中的標(biāo)志字段與00400H 相等 但對(duì)應(yīng)的有效位為0 而另一Cache 行的標(biāo)志字段與00400H 不相等 故訪問(wèn)Cache 不命中 因?yàn)槲锢淼刂返牡?2 位與虛擬地址低12 位相同 即為0010 0110 0000B 根據(jù)物理地址的 結(jié)構(gòu) 物理地址的后八位01100000B 的前三位011B 是組號(hào) 因此該地址所在的主存映射到Cache 組號(hào)為 3 45 解析 1 由圖可知 地址總長(zhǎng)度為32 位 高 20 位為虛頁(yè)號(hào) 低12 位為頁(yè)內(nèi)地址 且虛頁(yè)號(hào)高10 位為頁(yè)目錄號(hào) 低10 位為頁(yè)號(hào) 展開(kāi)成二進(jìn)制則表示為 故十六進(jìn)制表示為0180 6008H 2 PDBR 為頁(yè)目錄基址地址寄存器 Page Directory Base Register 其存儲(chǔ)頁(yè)目錄表物理內(nèi) 存基地址 進(jìn)程切換時(shí) PDBR 的內(nèi)容會(huì)變化 同一進(jìn)程的線程切換時(shí) PDBR 的內(nèi)容不會(huì)變化 每個(gè)進(jìn)程的地址空間 頁(yè)目錄和PDBR 的內(nèi)容存在一一對(duì)應(yīng)的關(guān)系 進(jìn)程切換時(shí) 地址