2009-2010年計(jì)算機(jī)統(tǒng)考考研試題及答案.pdf

2009 年計(jì)算機(jī)統(tǒng)考考研試題年計(jì)算機(jī)統(tǒng)考考研試題 一 單項(xiàng)選擇題 每小題一 單項(xiàng)選擇題 每小題2分 共分 共80分 分 1 為解決計(jì)算機(jī)與打印機(jī)之間速度不匹配的問題 通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū) 主機(jī)將要 輸出的數(shù)據(jù)依次寫入該緩沖區(qū) 而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù) 該緩沖區(qū)的邏輯結(jié) 構(gòu)應(yīng)該是 A 棧 B 隊(duì)列 C 樹 D 圖 2 設(shè)棧S 和隊(duì)列Q 的初始狀態(tài)均為空 元素a b c d e f g 依次進(jìn)入棧S 若每個(gè)元素出棧后立即進(jìn)入 隊(duì)列Q 且7 個(gè)元素出隊(duì)的順序是b d c f e a g 則棧S 的容量至少是 A 1 B 2 C 3 D 4 3 給定二叉樹圖所示 設(shè)N 代表二叉樹的根 L 代表根結(jié)點(diǎn)的左子樹 R 代表根結(jié)點(diǎn)的右子樹 若遍歷后的結(jié)點(diǎn)序列為3 1 7 5 6 2 4 則其遍歷方式是 A LRN B NRL C RLN D RNL 4 下列二叉排序樹中 滿足平衡二叉樹定義的是 A B C D 5 已知一棵完全二叉樹的第6 層 設(shè)根為第1 層 有8 個(gè)葉結(jié)點(diǎn) 則完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最 多是 A 39 B 52 C 111 D 119 6 將森林轉(zhuǎn)換為對(duì)應(yīng)的二叉樹 若在二叉樹中 結(jié)點(diǎn)u 是結(jié)點(diǎn)v 的父結(jié)點(diǎn)的父結(jié)點(diǎn) 則在原來 的森林中 u 和v 可能具有的關(guān)系是 I 父子關(guān)系 I I 兄弟關(guān)系 I I I u 的父結(jié)點(diǎn)與v 的父結(jié)點(diǎn)是兄弟關(guān)系 A 只有I I B I 和I I C I 和I I I D I I I 和I I I 7 下列關(guān)于無向連通圖特性的敘述中 正確的是 I 所有頂點(diǎn)的度之和為偶數(shù) I I 邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1 I I I 至少有一個(gè)頂點(diǎn)的度為1 A 只有I B 只有I I C I 和I I D I 和I I I 8 下列敘述中 不符合m 階B 樹定義要求的是 A 根節(jié)點(diǎn)最多有m 棵子樹 B 所有葉結(jié)點(diǎn)都在同一層上 C 各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列 D 葉結(jié)點(diǎn)之間通過指針鏈接 9 已知關(guān)鍵序列5 8 1 2 1 9 2 8 2 0 1 5 2 2 是小根堆 最小堆 插入關(guān)鍵字3 調(diào)整 后得到的小根堆是 A 3 5 12 8 28 20 15 22 19 B 3 5 12 19 20 15 22 8 28 C 3 8 1 2 5 2 0 1 5 2 2 2 8 1 9 D 3 1 2 5 8 2 8 2 0 1 5 2 2 1 9 1 0 若數(shù)據(jù)元素序列1 1 1 2 1 3 7 8 9 2 3 4 5 是采用下列排序方法之一得到的第二 趟排序后的結(jié)果 則該排序算法只能是 A 起泡排序 B 插入排序 C 選擇排序 D 二路歸并排序 1 1 馮諾依曼計(jì)算機(jī)中指令和數(shù)據(jù)均以二進(jìn)制形式存放在存儲(chǔ)器中 C P U 區(qū)分它們的依據(jù) 是 A 指令操作碼的譯碼結(jié)果 B 指令和數(shù)據(jù)的尋址方式 C 指令周期的不同階段 D 指令和數(shù)據(jù)所在的存儲(chǔ)單元 1 2 一個(gè)C 語(yǔ)言程序在一臺(tái)3 2 位機(jī)器上運(yùn)行 程序中定義了三個(gè)變量x y z 其中x 和z 是i n t 型 y 為s h o r t 型 當(dāng)x 1 2 7 y 9 時(shí) 執(zhí)行賦值語(yǔ)句z x y 后 x y z 的值分別是 A X 0 0 0 0 0 0 7 F H y F F F 9 H z 0 0 0 0 0 0 7 6 H A X 0 0 0 0 0 0 7 F H y F F F 9 H z F F F F 0 0 7 6 H A X 0 0 0 0 0 0 7 F H y F F F 7 H z F F F F 0 0 7 6 H A X 0 0 0 0 0 0 7 F H y F F F 7 H z 0 0 0 0 0 0 7 6 H 1 3 浮點(diǎn)數(shù)加減運(yùn)算過程一般包括對(duì)階 尾數(shù)運(yùn)算 規(guī)格化 舍入和判溢出等步驟 設(shè)浮點(diǎn) 數(shù)的階碼和尾數(shù)均采用補(bǔ)碼表示 且位數(shù)分別為5 位和7 位 均含2 位符號(hào)位 若有兩個(gè)數(shù) X 2 7 2 9 3 2 Y 2 5 5 8 則用浮點(diǎn)加法計(jì)算X Y 的最終結(jié)果是 A 00111 1100010 B 00111 0100010 C 01000 0010001 D 發(fā)生溢出 1 4 某計(jì)算機(jī)的C a c h e 共有1 6 塊 采用2 路組相聯(lián)映射方式 即每組2 塊 每個(gè)主存塊大小 為3 2 字節(jié) 按字節(jié)編址 主存1 2 9 號(hào)單元所在主存塊應(yīng)裝入到的C a c h e 組號(hào)是 A 0 B 2 C 4 D 6 1 5 某計(jì)算機(jī)主存容量為6 4 K B 其中R O M 區(qū)為4 K B 其余為R A M 區(qū) 按字節(jié)編址 現(xiàn)要用2 K 8 位的R O M 芯片和4 K 4 位的R A M 芯片來設(shè)計(jì)該存儲(chǔ)器 則需要上述規(guī)格的R O M 芯片數(shù)和R A M 芯片 數(shù)分別是 A 1 1 5 B 2 1 5 C 1 3 0 D 2 3 0 1 6 某機(jī)器字長(zhǎng)1 6 位 主存按字節(jié)編址 轉(zhuǎn)移指令采用相對(duì)尋址 由兩個(gè)字節(jié)組成 第一字 節(jié)為操作碼字段 第二字節(jié)為相對(duì)位移量字段 假定取指令時(shí) 每取一個(gè)字節(jié)P C 自動(dòng)加1 若某轉(zhuǎn)移指令所在主存地址為2 0 0 0 H 相對(duì)位移量字段的內(nèi)容為0 6 H 則該轉(zhuǎn)移指令成功轉(zhuǎn)以 后的目標(biāo)地址是 A 2006H B 2007H C 2008H D 2009H 1 7 下列關(guān)于R I S C 的敘述中 錯(cuò)誤的是 A R I S C 普遍采用微程序控制器 B R I S C 大多數(shù)指令在一個(gè)時(shí)鐘周期內(nèi)完成 C R I S C 的內(nèi)部通用寄存器數(shù)量相對(duì)C I S C 多 D R I S C 的指令數(shù) 尋址方式和指令格式種類相對(duì)C I S C 少 1 8 某計(jì)算機(jī)的指令流水線由四個(gè)功能段組成 指令流經(jīng)各功能段的時(shí)間 忽略各功能段之 間的緩存時(shí)間 分別是9 0 n s 8 0 n s 7 0 n s 和6 0 n s 則該計(jì)算機(jī)的C P U 時(shí)鐘周期至少是 A 9 0 n s B 8 0 n s C 7 0 n s D 6 0 n s 1 9 相對(duì)于微程序控制器 硬布線控制器的特點(diǎn)是 A 指令執(zhí)行速度慢 指令功能的修改和擴(kuò)展容易 B 指令執(zhí)行速度慢 指令功能的修改和擴(kuò)展難 C 指令執(zhí)行速度快 指令功能的修改和擴(kuò)展容易 D 指令執(zhí)行速度快 指令功能的修改和擴(kuò)展難 2 0 假設(shè)某系統(tǒng)總線在一個(gè)總線周期中并行傳輸4 字節(jié)信息 一個(gè)總線周期占用2 個(gè)時(shí)鐘周 期 總線時(shí)鐘頻率為1 0 M H z 則總線帶寬是 A 1 0 M B s B 2 0 M B S C 4 0 M B S D 8 0 M B S 2 1 假設(shè)某計(jì)算機(jī)的存儲(chǔ)系統(tǒng)由C a c h e 和主存組成 某程序執(zhí)行過程中訪存1 0 0 0 次 其中訪 問C a c h e 缺失 未命中 5 0 次 則C a c h e 的命中率是 A 5 B 9 5 C 50 D 95 2 2 下列選項(xiàng)中 能引起外部中斷的事件是 A 鍵盤輸入 B 除數(shù)為0 C 浮點(diǎn)運(yùn)算下溢 D 訪存缺頁(yè) 2 3 單處理機(jī)系統(tǒng)中 可并行的是 I 進(jìn)程與進(jìn)程 I I 處理機(jī)與設(shè)備 I I I 處理機(jī)與通道 I V 設(shè)備與設(shè)備 A I I I 和I I I B I I I 和I V C I I I I 和I V D I I I I I 和I V 2 4 下列進(jìn)程調(diào)度算法中 綜合考慮進(jìn)程等待時(shí)間和執(zhí)行時(shí)間的是 A 時(shí)間片輪轉(zhuǎn)調(diào)度算法 B 短進(jìn)程優(yōu)先調(diào)度算法 C 先來先服務(wù)調(diào)度算法 D 高響應(yīng)比優(yōu)先調(diào)度算法 2 5 某計(jì)算機(jī)系統(tǒng)中有8 臺(tái)打印機(jī) 有K 個(gè)進(jìn)程競(jìng)爭(zhēng)使用 每個(gè)進(jìn)程最多需要3 臺(tái)打印機(jī) 該 系統(tǒng)可能會(huì)發(fā)生死鎖的K 的最小值是 A 2 B 3 C 4 D 5 2 6 分區(qū)分配內(nèi)存管理方式的主要保護(hù)措施是 A 界地址保護(hù) B 程序代碼保護(hù) C 數(shù)據(jù)保護(hù) D 棧保護(hù) 2 7 一個(gè)分段存儲(chǔ)管理系統(tǒng)中 地址長(zhǎng)度為3 2 位 其中段號(hào)占8 位 則最大段長(zhǎng)是 A 2 的8 次方字節(jié) B 2 的1 6 次方字節(jié) C 2 的2 1 次方字節(jié) D 2 的3 2 次方字節(jié) 2 8 下列文件物理結(jié)構(gòu)中 適合隨機(jī)訪問且易于文件擴(kuò)展的是 A 連續(xù)結(jié)構(gòu) B 索引結(jié)構(gòu) C 鏈?zhǔn)浇Y(jié)構(gòu)且磁盤塊定長(zhǎng) D 鏈?zhǔn)浇Y(jié)構(gòu)且磁盤塊變長(zhǎng) 2 9 假設(shè)磁頭當(dāng)前位于第1 0 5 道 正在向磁道序號(hào)增加的方向移動(dòng) 現(xiàn)有一個(gè)磁道訪問請(qǐng)求 序列為3 5 4 5 1 2 6 8 1 1 0 1 8 0 1 7 0 1 9 5 采用S C A N 調(diào)度 電梯調(diào)度 算法得到的磁道 訪問序列是 A 110 170 180 195 68 45 35 12 B 110 68 45 35 12 170 180 195 C 1 1 0 1 7 0 1 8 0 1 9 5 1 2 3 5 4 5 6 8 D 1 2 3 5 4 5 6 8 1 1 0 1 7 0 1 8 0 1 9 5 3 0 文件系統(tǒng)中 文件訪問控制信息存儲(chǔ)的合理位置是 A 文件控制塊 B 文件分配表 C 用戶口令表 D 系統(tǒng)注冊(cè)表 3 1 設(shè)文件F 1 的當(dāng)前引用計(jì)數(shù)值為1 先建立F 1 的符號(hào)鏈接 軟鏈接 文件F 2 再建立F 1 的 硬鏈接文件F 3 然后刪除F 1 此時(shí) F 2 和F 3 的引用計(jì)數(shù)值分別是 A 0 1 B 1 1 C 1 2 D 2 1 3 2 程序員利用系統(tǒng)調(diào)用打開I O 設(shè)備時(shí) 通常使用的設(shè)備標(biāo)識(shí)是 A 邏輯設(shè)備名 B 物理設(shè)備名 C 主設(shè)備號(hào) D 從設(shè)備號(hào) 3 3 在O S I 參考模型中 自下而上第一個(gè)提供端到端服務(wù)的層次是 A 數(shù)據(jù)鏈路層 B 傳輸層 C 會(huì)話層 D 應(yīng)用層 3 4 在無噪聲情況下 若某通信鏈路的帶寬為3 k H z 采用4 個(gè)相位 每個(gè)相位具有4 種振幅的 Q A M 調(diào)制技術(shù) 則該通信鏈路的最大數(shù)據(jù)傳輸速率是 A 1 2 k b p s B 2 4 k b p s C 4 8 k b p s D 9 6 k b p s 3 5 數(shù)據(jù)鏈路層采用了后退N 幀 G B N 協(xié)議 發(fā)送方已經(jīng)發(fā)送了編號(hào)為0 7 的幀 當(dāng)計(jì)時(shí)器超 時(shí)時(shí) 若發(fā)送方只收到0 2 3 號(hào)幀的確認(rèn) 則發(fā)送方需要重發(fā)的幀數(shù)是 A 2 B 3 C 4 D 5 3 6 以太網(wǎng)交換機(jī)進(jìn)行轉(zhuǎn)發(fā)決策時(shí)使用的P D U 地址是 A 目的物理地址 B 目的I P 地址 C 源物理地址 D 源I P 地址 3 7 在一個(gè)采用C S M A C D 協(xié)議的網(wǎng)絡(luò)中 傳輸介質(zhì)是一根完整的電纜 傳輸速率為1 G b p s 電 纜中的信號(hào)傳播速度是2 0 0 0 0 0 k m s 若最小數(shù)據(jù)幀長(zhǎng)度減少8 0 0 比特 則最遠(yuǎn)的兩個(gè)站點(diǎn)之 間的距離至少需要 A 增加1 6 0 m B 增加8 0 m C 減少1 6 0 m D 減少8 0 m 3 8 主機(jī)甲和主機(jī)乙間已建立一個(gè)T C P 連接 主機(jī)甲向主機(jī)乙發(fā)送了兩個(gè)連續(xù)的T C P 段 分別 包含3 0 0 字節(jié)和5 0 0 字節(jié)的有效載荷 第一個(gè)段的序列號(hào)為2 0 0 主機(jī)乙正確接收到兩個(gè)段后 發(fā)送給主機(jī)甲的確認(rèn)序列號(hào)是 A 500 B 700 C 800 D 1000 3 9 一個(gè)T C P 連接總是以1 K B 的最大段發(fā)送T C P 段 發(fā)送方有足夠多的數(shù)據(jù)要發(fā)送 當(dāng)擁塞窗 口為1 6 K B 時(shí)發(fā)生了超時(shí) 如果接下來的4 個(gè)R T T 往返時(shí)間 時(shí)間內(nèi)的T C P 段的傳輸都是成功 的 那么當(dāng)?shù)? 個(gè)R T T 時(shí)間內(nèi)發(fā)送的所有T C P 段都得到肯定應(yīng)答時(shí) 擁塞窗口大小是 A 7KB B 8KB C 9KB D 16KB 4 0 F T P 客戶和服務(wù)器間傳遞F T P 命令時(shí) 使用的連接是 A 建立在 TCP 之上的控制連接 B 建立在 TCP 之上的數(shù)據(jù)連接 C 建立在U D P 之上的控制連接 D 建立在U D P 之上的數(shù)據(jù)連接 二 綜合應(yīng)用題 共7 0 分 二 綜合應(yīng)用題 共7 0 分 4 1 1 0分 帶權(quán)圖 權(quán)值非負(fù) 表示邊連接的兩頂點(diǎn)間的距離 的最短路徑問題是找出 從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間的一條最短路徑 假定從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間存在路徑 現(xiàn) 有一種解決該問題的方法 設(shè)最短路徑初始時(shí)僅包含初始頂點(diǎn) 令當(dāng)前頂點(diǎn)u 為初始頂點(diǎn) 選擇離u 最近且尚未在最短路徑中的一個(gè)頂點(diǎn)v 加入到最短路徑中 修改當(dāng)前頂點(diǎn) u v 重復(fù)步驟 直到u 是目標(biāo)頂點(diǎn)時(shí)為止 請(qǐng)問上述方法能否求得最短路徑 若該方法可行 請(qǐng)證明之 否則 請(qǐng)舉例說明 4 2 1 5 分 已知一個(gè)帶有表頭結(jié)點(diǎn)的單鏈表 結(jié)點(diǎn)結(jié)構(gòu)為 d a t a l i n k 假設(shè)該鏈表只給出了頭指針l i s t 在不改變鏈表的前提下 請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法 查找鏈表中倒數(shù)第k 個(gè)位置上的結(jié)點(diǎn) k 為正整數(shù) 若查找成功 算法輸出該結(jié)點(diǎn)的d a t a 值 并返回1 否則 只返回0 要求 1 描述算法的基本設(shè)計(jì)思想 2 描述算法的詳細(xì)實(shí)現(xiàn)步驟 3 根據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟 采用程序設(shè)計(jì)語(yǔ)言描述算法 使用C 或C 或J A V A 語(yǔ)言 實(shí)現(xiàn) 關(guān)鍵之處請(qǐng)給出簡(jiǎn)要注釋 43 8 分 某計(jì)算機(jī)的 CPU 主頻為 500MHz CPI 為 5 即執(zhí)行每條指令平均需 5 個(gè)時(shí)鐘周 期 假定某外設(shè)的數(shù)據(jù)傳輸率為 0 5MB s 采用中斷方式與主機(jī)進(jìn)行數(shù)據(jù)傳送 以 32 位為 傳輸單位 對(duì)應(yīng)的中斷服務(wù)程序包含 18 條指令 中斷服務(wù)的其他開銷相當(dāng)于 2 條指令的執(zhí) 行時(shí)間 請(qǐng)回答下列問題 要求給出計(jì)算過程 1 在中斷方式下 C P U 用于該外設(shè)I O 的時(shí)間占整個(gè)C P U 時(shí)間的百分比是多少 2 當(dāng)該外設(shè)的數(shù)據(jù)傳輸率達(dá)到5 M B s 時(shí) 改用D M A 方式傳送數(shù)據(jù) 假設(shè)每次D M A 傳送 大小為5 0 0 0 B 且D M A 預(yù)處理和后處理的總開銷為5 0 0 個(gè)時(shí)鐘周期 則C P U 用于該外設(shè)I O 的時(shí) 間占整個(gè)C P U 時(shí)間的百分比是多少 假設(shè)D M A 與C P U 之間沒有訪存沖突 4 4 1 3 分 某計(jì)算機(jī)字長(zhǎng)1 6 位 采用1 6 位定長(zhǎng)指令字結(jié)構(gòu) 部分?jǐn)?shù)據(jù)通路結(jié)構(gòu)如圖所示 圖中所有控制信號(hào)為1 時(shí)表示有效 為0 時(shí)表示無效 例如控制信號(hào)M D R i n E 為1 表示允許數(shù)據(jù) 從D B 打入M D R M D R i n 為1 表示允許數(shù)據(jù)從內(nèi)總線打入M D R 假設(shè)M A R 的輸出一直處于使能狀態(tài) 加法指令 A D D R 1 R 0 的功能為 R 0 R 1 R 1 即將R 0 中的數(shù)據(jù)與R 1 的內(nèi) 容所指主存單元的數(shù)據(jù)相加 并將結(jié)果送入R 1 的內(nèi)容所指主存單元中保存 數(shù)據(jù)通路結(jié)構(gòu) 下表給出了上述指令取值和譯碼階段每個(gè)節(jié)拍 時(shí)鐘周期 的功能和有效控制信號(hào) 請(qǐng)按 表中描述方式用表格列出指令執(zhí)行階段每個(gè)節(jié)拍的功能和有效控制信號(hào) 功能和控制信號(hào) 時(shí)鐘 功能 有效控制信號(hào) C 1 M A R P C P C o u t M A R i n C 2 M D R M M A R P C P C 1 M e m R M D R i n E P C 1 C 3 I R M D R M D R o u t I R i n C 4 指令譯碼 無 4 5 7 分 三個(gè)進(jìn)程P 1 P 2 P 3 互斥使用一個(gè)包含N N 0 個(gè)單元的緩沖區(qū) P 1 每次用p r o d u c e 生成一個(gè)正整數(shù)并用p u t 送入緩沖區(qū)某一空單元中 P 2 每次用g e t o d d 從該緩沖 區(qū)中取出一個(gè)奇數(shù)并用c o u n t o d d 統(tǒng)計(jì)奇數(shù)個(gè)數(shù) P 3 每次用g e t e v e n 從該緩沖區(qū)中取 出一個(gè)偶數(shù)并用c o u n t e v e n 統(tǒng)計(jì)偶數(shù)個(gè)數(shù) 請(qǐng)用信號(hào)量機(jī)制實(shí)現(xiàn)這三個(gè)進(jìn)程的同步與互 斥活動(dòng) 并說明所定義的信號(hào)量的含義 要求用偽代碼描述 4 6 8 分 請(qǐng)求分頁(yè)管理系統(tǒng)中 假設(shè)某進(jìn)程的頁(yè)表內(nèi)容如下表所示 頁(yè)表內(nèi)容 頁(yè)號(hào) 頁(yè)框 P a g e F r a m e 號(hào) 有效位 存在位 0 1 0 1 H 1 1 0 2 2 5 4 H 1 頁(yè)面大小為4 K B 一次內(nèi)存的訪問時(shí)間是1 0 0 n s 一次快表 T L B 的訪問時(shí)間是1 0 n s 處理 一次缺頁(yè)的平均時(shí)間為1 0 8 n s 已含更新T L B 和頁(yè)表的時(shí)間 進(jìn)程的駐留集大小固定為2 采用最近最少使用置換算法 L R U 和局部淘汰策略 假設(shè) T L B 初始為空 地址轉(zhuǎn)換時(shí)先 訪問T L B 若T L B 未命中 再訪問頁(yè)表 忽略訪問頁(yè)表之后的T L B 更新時(shí)間 有效位為0 表示頁(yè)面不在內(nèi)存 產(chǎn)生缺頁(yè)中斷 缺頁(yè)中斷處理后 返回到產(chǎn)生缺頁(yè)中斷的指令處重新執(zhí) 行 設(shè)有虛地址訪問序列2 3 6 2 H 1 5 6 5 H 2 5 A 5 H 請(qǐng)問 1 依次訪問上述三個(gè)虛地址 各需多少時(shí)間 給出計(jì)算過程 2 基于上述訪問序列 虛地址1 5 6 5 H 的 物理地址是多少 請(qǐng)說明理由 4 7 9 分 某公司網(wǎng)絡(luò)拓?fù)鋱D如下圖所示 路由器R 1 通過接口E 1 E 2 分別連接局域網(wǎng)1 局 域網(wǎng)2 通過接口L 0 連接路由器R 2 并通過路由器R 2 連接域名服務(wù)器與互聯(lián)網(wǎng) R 1 的L 0 接口 的I P 地址是2 0 2 1 1 8 2 1 R 2 的L 0 接口的I P 地址是2 0 2 1 1 8 2 2 L 1 接口的I P 地址是 1 3 0 1 1 1 2 0 1 E 0 接口的I P 地址是2 0 2 1 1 8 3 1 域名服務(wù)器的I P 地址是2 0 2 1 1 8 3 2 R 1 和R 2 的路由表結(jié)構(gòu)為 目的網(wǎng)絡(luò)I P 地址 子網(wǎng)掩碼 下一跳I P 地址 接口 1 將I P 地址空間2 0 2 1 1 8 1 0 2 4 劃分為兩個(gè)子網(wǎng) 分配給局域網(wǎng)1 局域網(wǎng)2 每個(gè)局 域網(wǎng)分配的地址數(shù)不少于1 2 0 個(gè) 請(qǐng)給出子網(wǎng)劃分結(jié)果 說明理由或給出必要的計(jì)算 過程 2 請(qǐng)給出R 1 的路由表 使其明確包括到局域網(wǎng)1 的路由 局域網(wǎng)2 的路由 域名服務(wù)器 的主機(jī)路由和互聯(lián)網(wǎng)的路由 3 請(qǐng)采用路由聚合技術(shù) 給出R 2 到局域網(wǎng)1 和局域網(wǎng)2 的路由 2009 年計(jì)算機(jī)統(tǒng)考試題參考答案年計(jì)算機(jī)統(tǒng)考試題參考答案 一 選擇題 1 2 3 4 5 6 7 8 9 10 B C D B C B A D A B 11 12 13 14 15 16 17 18 19 20 C D D C D C A A D B 21 22 23 24 25 26 27 28 29 30 D A D D C A C B A A 31 32 33 34 35 36 37 38 39 40 B A B B C A D D C A 選擇題部分答案解析 1 此題考察各數(shù)據(jù)結(jié)構(gòu)的特點(diǎn) 棧的特點(diǎn)是先進(jìn)后出 隊(duì)列的特點(diǎn)是先進(jìn)先出 樹的特點(diǎn)是 節(jié)點(diǎn)的前驅(qū)只能有一個(gè)的數(shù)據(jù)結(jié)構(gòu) 圖是最復(fù)雜的數(shù)據(jù)結(jié)構(gòu) 它是前驅(qū)和后繼都可以有多個(gè) 的網(wǎng)狀結(jié)構(gòu) 2 元素 abcdefg 依次進(jìn)入棧 bdcfeag 依次出隊(duì) 那么他們?cè)跅Ｖ胁僮黜樞蛞来螢?a 入棧 b 入棧 b 出棧 c 入棧 d 入棧 d 出棧 c 出棧 e 入棧 f 入棧 f 出棧 e 出棧 a 出棧 g 入棧 g 出棧 這其間棧中數(shù)據(jù)最多有 3 個(gè) 3 一看第一個(gè)遍歷出來的元素是 3 所以后序遍歷 4 平衡二叉樹 又稱 AVL 樹 它或者是一棵空樹 或者是具有下列性質(zhì)的二叉樹 它的左 子樹和右子樹都是平衡二叉樹 且左子樹和右子樹的高度之差之差的絕對(duì)值不超過 1 5 第 6 層有 8 個(gè)葉節(jié)點(diǎn) 說明這個(gè)完全二叉樹最多共 7 層 所以樹的節(jié)點(diǎn)數(shù)為 1 2 4 8 16 32 48 111 8 B 樹是一種多叉平衡查找樹 一棵 m階的 B 樹 或?yàn)榭諛?或?yàn)闈M足下列特性的 m叉樹 樹中每個(gè)結(jié)點(diǎn)至多有 m棵子樹 若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn) 則它至少有兩棵子樹 除根之外的所有非葉子結(jié)點(diǎn)至少有 m 2 棵子樹 所有的非葉子結(jié)點(diǎn)中包含卞列數(shù)據(jù)信息 n A0 K1 A1 K2 A2 Kn An 其中 Ki i 1 2 n 為關(guān)鍵字 且 Kik 時(shí) 指針 p 隨著 每次遍歷 也向前移動(dòng)一個(gè)節(jié)點(diǎn) 當(dāng)遍歷完成時(shí) p 或者指向表頭就節(jié)點(diǎn) 或者指向鏈表中 倒數(shù)第 K 個(gè)位置上的節(jié)點(diǎn) 3 算法描述 Int LocateElement linklist list int k P1 list link P list i 1 while P1 P1 P1 link i if i k p p next 如果 i k 則 p 也往后移 if p list return 0 說明鏈表沒有 k 個(gè)結(jié)點(diǎn) else printf d n p data return 1 43 1 在中斷方式下 每 32 位 4B 被中斷一次 故每秒中斷 0 5MB 4B 0 5 106 4 12 5 104 次 要注意的是 這里是數(shù)據(jù)傳輸率 所以 1MB 106B 因?yàn)橹袛喾?wù)程序包含 18 條指令 中 斷服務(wù)的其他開銷相當(dāng)于 2 條指令的執(zhí)行時(shí)間 且執(zhí)行每條指令平均需 5 個(gè)時(shí)鐘周期 所以 1 秒內(nèi)用于中斷的時(shí)鐘周期數(shù)為 18 2 5 12 5 104 12 5 106 2 在 DMA 方式下 每秒進(jìn)行 DMA 操作 5MB 5000B 5 106 5000 1 103 次因?yàn)?DMA 預(yù)處理和后處理的總開銷為 500 個(gè)時(shí)鐘周 期 所以 1 秒鐘之內(nèi)用于 DMA 操作的時(shí)鐘周期數(shù)為 500 1 103 5 105 故在 DMA 方式下 占整個(gè) CPU 時(shí)間的百分比是 5 105 500 106 100 0 1 44 指令執(zhí)行階段每個(gè)節(jié)拍的功能和有效控制信號(hào)如下所示 時(shí)鐘 功能 有效控制信號(hào) C5 MAR R1 PCout MARin C6 MDR M MAR MemR MDRinE C7 A R0 R0out Ain C8 AC MDR A MDRout Addr ACin C9 MDR AC ACout MDRin C10 M MAR MDR MDRoutE MemW 45 定義信號(hào)量 S1 控制 P1 與 P2 之間的同步 S2 控制 P1 與 P3 之間的同步 empty 控制生 產(chǎn)者與消費(fèi)者之間的同步 mutex 控制進(jìn)程間互斥使用緩沖區(qū) 程序如下 Var s1 0 s2 0 empty N mutex 1 Parbegin P1 begin X produce 生成一個(gè)數(shù) P empty 判斷緩沖區(qū)是否有空單元 P mutex 緩沖區(qū)是否被占用 Put If x 2 0 V s2 如果是偶數(shù) 向 P3 發(fā)出信號(hào) else V s1 如果是奇數(shù) 向 P2 發(fā)出信號(hào) V mutex 使用完緩沖區(qū) 釋放 end P2 begin P s1 收到 P1 發(fā)來的信號(hào) 已產(chǎn)生一個(gè)奇數(shù) P mutex 緩沖區(qū)是否被占用 Getodd Countodd countodd 1 V mutex 釋放緩沖區(qū) V empty 向 P1 發(fā)信號(hào) 多出一個(gè)空單元 end P3 begin P s2 收到 P1 發(fā)來的信號(hào) 已產(chǎn)生一個(gè)偶數(shù) P mutex 緩沖區(qū)是否被占用 Geteven Counteven counteven 1 V mutex 釋放緩沖區(qū) V empty 向 P1 發(fā)信號(hào) 多出一個(gè)空單元 end Parend 46 1 根據(jù)頁(yè)式管理的工作原理 應(yīng)先考慮頁(yè)面大小 以便將頁(yè)號(hào)和頁(yè)內(nèi)位移分解出來 頁(yè) 面大小為 4KB 即 212 則得到頁(yè)內(nèi)位移占虛地址的低 12 位 頁(yè)號(hào)占剩余高位 可得三個(gè) 虛地址的頁(yè)號(hào) P 如下 十六進(jìn)制的一位數(shù)字轉(zhuǎn)換成 4 位二進(jìn)制 因此 十六進(jìn)制的低三位 正好為頁(yè)內(nèi)位移 最高位為頁(yè)號(hào) 2362H P 2 訪問快表 10ns 因初始為空 訪問頁(yè)表 100ns 得到頁(yè)框號(hào) 合成物理地址后 訪問主存 100ns 共計(jì) 10ns 100ns 100ns 210ns 1565H P 1 訪問快表 10ns 落空 訪問頁(yè)表 100ns 落空 進(jìn)行缺頁(yè)中斷處理 108ns 合 成物理地址后訪問主存 100ns 共計(jì) 10ns 100ns 108ns 100ns 108ns 25A5H P 2 訪問快表 因第一次訪問已將該頁(yè)號(hào)放入快表 因此花費(fèi) 10ns 便可合成物 理地址 訪問主存 100ns 共計(jì) 10ns 100ns 110ns 2 當(dāng)訪問虛地址 1565H 時(shí) 產(chǎn)生缺頁(yè)中斷 合法駐留集為 2 必須從頁(yè)表中淘汰一個(gè)頁(yè) 面 根據(jù)題目的置換算法 應(yīng)淘汰 0 號(hào)頁(yè)面 因此 1565H 的對(duì)應(yīng)頁(yè)框號(hào)為 101H 由此可得 1565H 的物理地址為 101565H 47 1 無類 IP 地址的核心是采用不定長(zhǎng)的網(wǎng)絡(luò)號(hào)和主機(jī)號(hào) 并通過相應(yīng)的子網(wǎng)掩碼來表示 即網(wǎng)絡(luò)號(hào)部分為 1 主機(jī)號(hào)部分為 0 本題中網(wǎng)絡(luò)地址位數(shù)是 24 由于 IP 地址是 32 位 因此其主機(jī)號(hào)部分就是 8 位 因此 子網(wǎng)掩碼就是 11111111 11111111 11111111 00000000 即 255 255 255 0 根據(jù)無類 IP 地址的規(guī)則 每個(gè)網(wǎng)段中有兩個(gè)地址是不分配的 主機(jī)號(hào)全 0 表示網(wǎng)絡(luò)地址 主機(jī)號(hào)全 1 表示廣播地址 因此 8 位主機(jī)號(hào)所能表示的主機(jī)數(shù)就是 2 的 8 次方 2 即 254 臺(tái) 該網(wǎng)絡(luò)要?jiǎng)澐譃閮蓚€(gè)子網(wǎng) 每個(gè)子網(wǎng)要 120 臺(tái)主機(jī) 因此主機(jī)位數(shù) X 應(yīng)該滿足下面三個(gè)條 件 X120 因?yàn)楦鶕?jù)題意需要容納 120 臺(tái)主機(jī) X 是整數(shù) 解上述方程 得到 X 7 子網(wǎng)掩碼就是 11111111 11111111 11111111 10000000 即 255 255 255 128 所以劃分的兩個(gè)網(wǎng)段是 202 118 1 0 25 與 202 118 1 128 25 2 填寫 R1 的路由表 填寫到局域網(wǎng) 1 的路由 局域網(wǎng) 1 的網(wǎng)絡(luò)地址和掩碼在問題 1 已經(jīng)求出來了 為 202 118 1 0 25 則 R1 路由表應(yīng)填入的網(wǎng)絡(luò)地址為 202 118 1 0 掩碼為 255 255 255 128 由 于局域網(wǎng) 1 是直接連接到路由器 R1 的 E1 口上的 因此 下一跳地址填寫直接路由 Direct 接口填寫 E1 填寫到局域網(wǎng) 2 的路由表 1 局域網(wǎng) 2 的網(wǎng)絡(luò)地址和掩碼在問題 1 中已經(jīng)求出來了 為 202 118 1 128 25 則R1路由表應(yīng)該填入的網(wǎng)絡(luò)地址為202 118 1 128 掩碼為255 255 255 128 由于局域網(wǎng) 2 是直接連接到路由器 R1 的 E2 口上的 因此 下一跳地址填寫直接路由 接 口填寫 E2 填寫到域名服務(wù)器的路由 由于域名服務(wù)器的 IP 地址為 202 118 3 2 而該地址為主機(jī)地址 因此掩碼為 255 255 255 255 同時(shí) 路由器 R1 要到 DNS 服務(wù)器 就需要通過路由器 R2 的 接口 L0 才能到達(dá) 因此下一跳地址填寫 L0 的 IP 地址 202 118 2 2 填寫互聯(lián)網(wǎng)路由 本題實(shí)質(zhì)是編寫默認(rèn)路由 默認(rèn)路由是一種特殊的靜態(tài)路由 指的是當(dāng) 路由表中與包的目的地址之間沒有匹配的表項(xiàng)時(shí)路由器能夠做出的選擇 如果沒有默認(rèn)路由 器 那么目的地址在路由表中沒有匹配表項(xiàng)的包將被丟棄 默認(rèn)路由在某些時(shí)候非常有效 當(dāng)存在末梢網(wǎng)絡(luò)時(shí) 默認(rèn)路由會(huì)大大簡(jiǎn)化路由器的配置 減輕管理員的工作負(fù)擔(dān) 提高網(wǎng)絡(luò) 性能 默認(rèn)路由叫做 0 0 路由 因?yàn)槁酚傻?IP 地址 0 0 0 0 而子網(wǎng)掩碼也是 0 0 0 0 同 時(shí)路由器 R1 連接的網(wǎng)絡(luò)需要通過路由器 R2 的 L0 口才能到達(dá)互聯(lián)網(wǎng)絡(luò) 因此下一跳地址填 寫 L0 的 IP 為 202 118 2 2 綜上 填寫的路由表如下 R1 路由表 目的網(wǎng)絡(luò) IP 地址 子網(wǎng)掩碼 下一跳 IP 地址 接口 202 118 1 0 255 255 255 128 Direct E1 202 118 1 128 255 255 255 128 Direct E2 202 118 3 2 255 255 255 255 202 118 2 2 L0 0 0 0 0 0 0 0 0 202 118 2 2 L0 3 填寫 R2 到局域網(wǎng) 1 和局域網(wǎng) 2 的路由表 2 局域網(wǎng) 1 和局域網(wǎng) 2 的地址可以聚合為 202 118 1 0 24 而 R2 去往局域網(wǎng) 1 和局域網(wǎng) 2 都是同一條路徑 因此 路由表里面只需要 填寫到 202 118 1 0 24 網(wǎng)絡(luò)的路由即可 如下表所示 R2 路由表 目的網(wǎng)絡(luò) IP 地址 子網(wǎng)掩碼 下一跳 IP 地址 接口 202 118 1 0 255 255 255 0 202 118 2 1 L0 2010 年全國(guó)研究生考試計(jì)算機(jī)統(tǒng)考試 題及答案 年全國(guó)研究生考試計(jì)算機(jī)統(tǒng)考試 題及答案 一 單選題 1 若元素 a b c d e f 依次進(jìn)棧 允許進(jìn)棧 退棧操作交替進(jìn)行 但不允 許連續(xù)三次進(jìn)行退棧工作 則不可能得到的出棧序列是 D A dcebfa B cbdaef C dbcaef D afedcb 2 某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作 但僅允許在一端進(jìn)行出隊(duì)操作 則不可能得到的順序是 C A bacde B dbace C dbcae D ecbad 3 下列線索二叉樹中 用虛線表示線索 符合后序線索樹定義的是 B 4 在下列所示的平衡二叉樹中插入關(guān)鍵字 48 后得到一棵新平衡二叉樹 在新平衡二叉樹中 關(guān)鍵字 37 所在結(jié)點(diǎn)的左 右子結(jié)點(diǎn)中保存的關(guān)鍵字 分別是 C A 13 48 B 24 48 C 24 53 D 24 90 5 在一棵度為 4 的樹 T 中 若有 20 個(gè)度為 4 的結(jié)點(diǎn) 10 個(gè)度為 3 的結(jié) 點(diǎn) 1 個(gè)度為 2 的結(jié)點(diǎn) 10 個(gè)度為 1 的結(jié)點(diǎn) 則樹 T 的葉節(jié)點(diǎn)個(gè)數(shù)是 B A 41 B 82 C 113 D 122 6 對(duì) n n 大于等于 2 個(gè)權(quán)值均不相同的字符構(gòu)成哈夫曼樹 關(guān)于該樹的 敘述中 錯(cuò)誤的是 B A 該樹一定是一棵完全二叉樹 B 樹中一定沒有度為 1 的結(jié)點(diǎn) C 樹中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn) D 樹中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一任一結(jié)點(diǎn)的權(quán)值 7 若無向圖 G V E 中含 7 個(gè)頂點(diǎn) 則保證圖 G 在任何情況下都是連 通的 則需要的邊數(shù)最少是 A A 6 B 15 C 16 D 21 8 對(duì)下圖進(jìn)行拓補(bǔ)排序 可以得到不同的拓補(bǔ)序列的個(gè)數(shù)是 B A 4 B 3 C 2 D 1 9 已知一個(gè)長(zhǎng)度為 16 的順序表 L 其元素按關(guān)鍵字有序排列 若采用 折半查找法查找一個(gè)不存在的元素 則比較次數(shù)最多是 A A 4 B 5 C 6 D 7 10 采用遞歸方式對(duì)順序表進(jìn)行快速排序 下列關(guān)于遞歸次數(shù)的敘述中 正確的是 D A 遞歸次數(shù)與初始數(shù)據(jù)的排列次序無關(guān) B 每次劃分后 先處理較長(zhǎng)的分區(qū)可以減少遞歸次數(shù) C 每次劃分后 先處理較短的分區(qū)可以減少遞歸次數(shù) D 遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無關(guān) 11 對(duì)一組數(shù)據(jù) 2 12 16 88 5 10 進(jìn)行排序 若前三趟排序結(jié) 果如下 A 第一趟 2 12 16 5 10 88 第二趟 2 12 5 10 16 88 第三趟 2 5 10 12 16 88 則采用的排序方法可能是 A 起泡排序 B 希爾排序 C 歸并排序 D 基數(shù)排序 12 下列選項(xiàng)中 能縮短程序執(zhí)行時(shí)間的措施是 D I 提高 CPU 時(shí)鐘頻率 II 優(yōu)化數(shù)據(jù)通過結(jié)構(gòu) III 對(duì)程序進(jìn)行編譯優(yōu)化 A 僅 I 和 II B 僅 I 和 III C 僅 II 和 III D I II III 13 假 定 有4個(gè) 整 數(shù) 用8位 補(bǔ) 碼 分 別 表 示 r1 FEH r2 F2H r3 90H r4 F8H 若將運(yùn)算結(jié)果存放在一個(gè)8 位的寄存 器中 則下列運(yùn)算會(huì)發(fā)生溢出的是 C A r1 r2 B r2 r3 C r1 r4 D r2 r4 14 假定變量 I f d 數(shù)據(jù)類型分別為 int float 和 double int 用補(bǔ)碼表示 float 和 double 分別用 IEEE754 單精度和雙精度浮點(diǎn)數(shù)據(jù)格式表示 已 知 i 785 f 1 5678 d 1 5 若在 32 位機(jī)器中執(zhí)行下列關(guān)系表達(dá)式 則結(jié) 果為真是 C I f int float I II f float int f III f float double IV d f d f A 僅 I 和 II B 僅 I 和 III C 僅 II 和 III D 僅 III 和 IV 15 假定用若干個(gè) 2k 4 位芯片組成一個(gè) 8 8 位存儲(chǔ)器 則地址 0B1FH 所在芯片的最小地址是 D A 0000H B 0600H C 0700H D 0800H 16 下列有關(guān) RAM 和 ROM 的敘述中 正確的是 A I RAM 是易失性存儲(chǔ)器 ROM 是非易失性存儲(chǔ)器 II RAM 和 ROM 都是采用隨機(jī)存取的方式進(jìn)行信息訪問 III RAM 和 ROM 都可用作 Cache IV RAM 和 ROM 都需要進(jìn)行刷新 A 僅 I 和 II B 僅 II 和 III C 僅 I II III D 僅 II III IV 17 下列命令組合情況中 一次訪存過程中 不可能發(fā)生的是 D A TLB 未命中 Cache 未命中 Page 未命中 B TLB 未命中 Cache 命中 Page 命中 C TLB 命中 Cache 未命中 Page 命中 D TLB 命中 Cache 命中 Page 未命中 18 下列存儲(chǔ)器中 匯編語(yǔ)言程序員可見的是 B A 存儲(chǔ)器地址寄存器 MAR B 程序計(jì)數(shù)器 PC C 存儲(chǔ)器數(shù)據(jù)寄存器 MDR D 指令寄存器 IR 19 下列不會(huì)引起指令流水阻塞的是 A A 數(shù)據(jù)旁路 B 數(shù)據(jù)相關(guān) C 條件轉(zhuǎn)移 D 資源沖突 20 下列選項(xiàng)中的英文縮寫均為總線標(biāo)準(zhǔn)的是 D A PCI CRT USB EISA B ISA CPI VESA EISA C ISA SCSI RAM MIPS D ISA EISA PCI PCI Express 21 單級(jí)中斷系統(tǒng)中 中斷服務(wù)程序執(zhí)行順序是 A I 保護(hù)現(xiàn)場(chǎng) II 開中斷 III 關(guān)中斷 IV 保存斷點(diǎn) V 中斷事件處理 VI 恢復(fù)現(xiàn)場(chǎng) VII 中斷返回 A I V VI II VII B III I V VII C III IV V VI VII D IV I V VI VII 22 假定一臺(tái)計(jì)算機(jī)的顯示存儲(chǔ)器用 DRAM 芯片實(shí)現(xiàn) 若要求顯示分辨 率為 1600 1200 顏色深度為 24 位 幀頻為 85Hz 顯示總帶寬的 50 用來刷新屏幕 則需要的顯存總帶寬至少約為 D A 245 Mbps B 979 Mbps C 1958 Mbps D 7834Mbps 23 下列選項(xiàng)中 操作 S 提供的給應(yīng)用程序的接口是 A A 系統(tǒng)調(diào)用 B 中斷 C 庫(kù)函數(shù) D 原語(yǔ) 24 下列選項(xiàng)中 導(dǎo)致創(chuàng)進(jìn)新進(jìn)程的操作是 C I 用戶成功登陸 II 設(shè)備分配 III 啟動(dòng)程序執(zhí)行 A 僅 I 和 II B 僅 II 和 III C 僅 I 和 III D I II III 25 設(shè)與某資源相關(guān)聯(lián)的信號(hào)量初值為 3 當(dāng)前值為 1 若 M 表示該資 源的可用個(gè)數(shù) N 表示等待資源的進(jìn)程數(shù) 則 M N 分別是 B A 0 1 B 1 0 C 1 2 D 2 0 26 下列選項(xiàng)中 降低進(jìn)程優(yōu)先權(quán)級(jí)的合理時(shí)機(jī)是 A A 進(jìn)程的時(shí)間片用完 B 進(jìn)程剛完成 Z O 進(jìn)入就緒隊(duì)列 C 進(jìn)程長(zhǎng)期處于就緒隊(duì)列中 D 就緒從就緒狀態(tài)轉(zhuǎn)為運(yùn)行態(tài) 27 進(jìn)行 P0 和 P1 的共享變量定義及其初值為 A boolean flag 2 int turn 0 flag 0 faulse flag 1 faulse 若進(jìn)行 P0 和 P1 訪問臨界資源的類 C 代碼實(shí)現(xiàn)如下 Void p0 進(jìn)程 p0 Void p1 進(jìn)程 p1 while TURE while TURE Flag 0 TURE ture 1 Flag 1 TURE ture 1 While flag 1 Flag 1 FALSE 則并發(fā)執(zhí)行進(jìn)程 P0 和 P1 時(shí)產(chǎn)生的情況是 A 不能保證進(jìn)程互斥進(jìn)入臨界區(qū) 會(huì)出現(xiàn) 饑餓 現(xiàn)象 B 不能保證進(jìn)程互斥進(jìn)入臨界區(qū) 不會(huì)出現(xiàn) 饑餓 現(xiàn)象 C 能保證進(jìn)程互斥進(jìn)入臨界區(qū) 會(huì)出現(xiàn) 饑餓 現(xiàn)象 D 能保證進(jìn)程互斥進(jìn)入臨界區(qū) 不會(huì)出現(xiàn) 饑餓 現(xiàn)象 28 某基于動(dòng)態(tài)分區(qū)存儲(chǔ)管理的計(jì)算機(jī) 其主存容量為 55mb 初試為 空間 采用最佳適配 Best fit 算法 分配和釋放的順序?yàn)?分配 15mb 分配 30mb 釋放 15mb 分配 8mb 此時(shí)主存中最大空閑分區(qū)的大小是 B A 7mb B 9mb C 10mb D 15mb 29 某計(jì)算機(jī)采用二級(jí)頁(yè)表的分頁(yè)存儲(chǔ)管理方式 按字節(jié)編制 頁(yè)大小 為 216 字節(jié) 頁(yè)表項(xiàng)大小為 2 字節(jié) 邏輯地址結(jié)構(gòu)為 頁(yè)目編號(hào) 頁(yè)號(hào) 頁(yè)內(nèi)偏移量 邏輯地址空間大小為 216 頁(yè) 則表示整個(gè)邏輯地址空間的頁(yè)目錄表中包 含表項(xiàng)的個(gè)數(shù)至少是 B A 64 B 128 C 256 D 512 30 設(shè)文件索引節(jié)點(diǎn)中有 7 個(gè)地址項(xiàng) 其中 4 個(gè)地址項(xiàng)為直接地址索引 2 個(gè)地址項(xiàng)是一級(jí)間接地址索引 1 個(gè)地址項(xiàng)是二級(jí)間接地址索引 每個(gè) 地址項(xiàng)大小為 4 字節(jié) 若磁盤索引塊和磁盤數(shù)據(jù)塊大小均為 256 字節(jié) 則可表示的單個(gè)文件的最大長(zhǎng)度是 C A 33kb B 519kb C 1057kb D 16513kb 31 設(shè)置當(dāng)前工作目錄的主要目的是 C A 節(jié)省外存空間 B 節(jié)省內(nèi)容空間 C 加快文件的檢索速度 D 加快文件的讀寫速度 32 本地用戶通過鍵盤登錄系統(tǒng)時(shí) 首先獲得鍵盤輸入信息的程序是 B A 命令解釋程序 B 中斷處理程序 C 系統(tǒng)調(diào)用程序 D 用戶登錄程序 33 下列選項(xiàng)中 不屬于網(wǎng)絡(luò)體系結(jié)構(gòu)中所描述的內(nèi)容是 C A 網(wǎng)絡(luò)的層次 B 每一層使用的協(xié)議 C 協(xié)議的內(nèi)部實(shí)現(xiàn)細(xì)節(jié) D 每一層必須完成的功能 34 在下圖所示的采用 存儲(chǔ) 轉(zhuǎn)發(fā) 方式分組的交換網(wǎng)絡(luò)中 所有鏈路的 數(shù)據(jù)傳輸速度為 100mbps 分組大小為 1000B 其中分組頭大小 20B 若主機(jī) H1 向主機(jī) H2 發(fā)送一個(gè)大小為 980000B 的文件 則在不考慮分 組拆裝時(shí)間和傳播延遲的情況下 從 H1 發(fā)送到 H2 接收完為止 需要的 時(shí)間至少是 A A 80ms B 80 08ms C 80 16ms D 80 24ms 35 某自治系統(tǒng)采用 RIP 協(xié)議 若該自治系統(tǒng)內(nèi)的路由器 R1 收到其鄰 居路由器 R2 的距離矢量中包含信息 net1 16 則可能得出的結(jié)論是 A A R2 可以經(jīng)過 R1 到達(dá) net1 跳數(shù)為 17 B R2 可以到達(dá) net1 跳數(shù)為 16 C R1 可以經(jīng)過 R2 到達(dá) net1 跳數(shù)為 17 D R1 不能進(jìn)過 R2 到達(dá) net1 36 若路由器 R 因?yàn)閾砣麃G棄 IP 分組 則此時(shí) R 可以向發(fā)出該 IP 分組 的源主機(jī)發(fā)送的 ICMP 報(bào)文件類型是 C A 路由重定向 B 目的不可達(dá) C 源抑制 D 超時(shí) 37 某網(wǎng)絡(luò)的 IP 地址為 192 168 5 0 24 采用長(zhǎng)子網(wǎng)劃分 子網(wǎng)掩碼為 255 255 255 248 則該網(wǎng)絡(luò)的最大子網(wǎng)個(gè)數(shù) 每個(gè)子網(wǎng)內(nèi)的最大可分配 地址個(gè)數(shù)為 B A 32 8 B 32 6 C 8 32 D 8 30 38 下列網(wǎng)絡(luò)設(shè)備中 能夠抑制網(wǎng)絡(luò)風(fēng)暴的是 C 中繼器 集線器 網(wǎng)橋 路由器 A 僅 和 B 僅 C 僅 和 D 僅 39 主機(jī)甲和主機(jī)乙之間已建立一個(gè) TCP 連接 TCP 最大段長(zhǎng)度為 1000 字節(jié) 若主機(jī)甲的當(dāng)前擁塞窗口為 4000 字節(jié) 在主機(jī)甲向主機(jī)乙連接發(fā) 送 2 個(gè)最大段后 成功收到主機(jī)乙發(fā)送的第一段的確認(rèn)段 確認(rèn)段中通 告的接收窗口大小為 2000 字節(jié) 則此時(shí)主機(jī)甲還可以向主機(jī)乙發(fā)送的最 大字節(jié)數(shù)是 A A 1000 B 2000 C 3000 D 4000 40 如果本地域名服務(wù)無緩存 當(dāng)采用遞歸方法解析另一網(wǎng)絡(luò)某主機(jī)域 名時(shí) 用戶主機(jī)本地域名服務(wù)器發(fā)送的域名請(qǐng)求條數(shù)分別為 A A 1 條 1 條 B 1 條 多條 C 多條 1 條 D 多條 多條 二 綜合應(yīng)用題 二 綜合應(yīng)用題 41 47 小題 共計(jì)小題 共計(jì) 70 分分 41 10 分 將關(guān)鍵字序列 7 8 11 18 9 14 散列存儲(chǔ)到散列列 表中 散列表的存儲(chǔ)空間是一個(gè)下標(biāo)從 0 開始的一個(gè)一維數(shù)組散列函數(shù) 維 H key key 3 MODT 處理沖突采用線性探測(cè)再散列法 要 求裝填 載 因子為 0 7 問題 1 請(qǐng)畫出所構(gòu)造的散列表 2 分別計(jì)算等概率情況下 查找成功和查找不成功的平均查找長(zhǎng)度 解答 1 由裝載因子 0 7 數(shù)據(jù)總數(shù) 7 個(gè) 存儲(chǔ)空間長(zhǎng)度為 10 P 10 所以 構(gòu)造的散列表為 0 1 2 3 4 5 6 7 8 9 30 7 14 11 8 18 9 H 7 7 3 MOD10 1 2 查找成功的 ASL 1 1 1 1 2 1 1 7 8 7 查找不成功的 ASL 7 6 5 4 3 2 1 2 1 1 10 3 2 42 13 分 設(shè)將 n n 1 個(gè)整數(shù)存放到一維數(shù)組 R 中 試設(shè)計(jì)一個(gè)在時(shí) 間和空間兩方面盡可能有效的算法 將 R 中保有的序列循環(huán)左移 P 0 P n 個(gè)位置 即將 R 中的數(shù)據(jù)由 X0 X1 Xn 1 變換為 Xp Xp 1 Xn 1 X0 X1 Xp 1 要求 1 給出算法的基本設(shè)計(jì)思想 2 根據(jù)設(shè)計(jì)思想 采用 C 或 C 或 JAVA 語(yǔ)言表述算法 關(guān)鍵之處給 出注釋 3 說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度 解答 1 前 P 個(gè)數(shù)依次進(jìn)隊(duì) while 1 n p A i i p p 個(gè)數(shù)依次出對(duì) 進(jìn)入數(shù)組末尾 2 詳細(xì)程序略 3 時(shí)間復(fù)雜度 O N 空間復(fù)雜度 o p 43 11 分 某計(jì)算機(jī)字長(zhǎng)為 16q 位 主存地址空間大小為 128KB 按字編 址 采用字長(zhǎng)指令格式 指令名字段定義如下 轉(zhuǎn)移指令采用相對(duì)尋址方式 相對(duì)偏移是用補(bǔ)碼表示 尋址方式定義如 下 Ms Md 尋址方式 助記符 含義 000B 寄存器直接 Rn 操作數(shù) Rn 001B 寄存器間接 Rn 操作數(shù) Rn 010B 寄存器間接 自增 Rn 操作數(shù) Rn Rn 1 Rn 011B 相對(duì) D Rn 轉(zhuǎn)移目標(biāo)地址 PC Rn 注 X 表示有儲(chǔ)蓄地址 X 或寄存器 X 的內(nèi)容 請(qǐng)回答下列問題 1 該指令系統(tǒng)最多可有多少條指令 該計(jì)算機(jī)最多有多少個(gè)通用寄存 器 存儲(chǔ)器地址寄存器 MDR 至少各需多少位 2 轉(zhuǎn)移指令的目標(biāo)地址范圍是多少 3 若操作碼 0010B 表示加法操作 助記符為 a d d 寄存器 R4 和 R5 的編號(hào)分別為 100B 和 101B R4 的內(nèi)容為 1 2 3 4 H R5 的內(nèi)容為 5 6 7 8 H 地址 1 2 3 4 H 中的內(nèi)容為 5 6 7 8 H 中的內(nèi)容為 1 2 3 4 H 則匯編語(yǔ)言為 a d d R4