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

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