王道計(jì)算機(jī)統(tǒng)考模擬試卷(pdf 47頁).pdf

1 王道計(jì)算機(jī)統(tǒng)考模擬試題 1 一 單項(xiàng)選擇題 第 1 40 小題 每小題 2 分 共 80 分 下列每題給出的四個(gè)選項(xiàng)中 只有一個(gè)選 項(xiàng)最符合試題要求 1 6 個(gè)元素以 6 5 4 3 2 1 的順序進(jìn)棧 下列不合法的出棧序列是 A 5 4 3 6 1 2 B 4 5 3 1 2 6 C 3 4 6 5 2 1 D 2 3 4 1 5 6 2 利用棧求表達(dá)式的值時(shí) 設(shè)立運(yùn)算數(shù)棧 OPEN 假設(shè) OPEN 只有兩個(gè)存儲(chǔ)單元 則在下列表達(dá)式中 不會(huì)發(fā)生溢出的是 A A B C D B A B C D C A B C D D A B C D 3 在一棵三叉樹中度為 3 的結(jié)點(diǎn)數(shù)為 2 個(gè) 度為 2 的結(jié)點(diǎn)數(shù)為 1 個(gè) 度為 1 的結(jié)點(diǎn)數(shù)為 2 個(gè) 則度為 0 的結(jié)點(diǎn)數(shù)為 個(gè) A 4 B 5 C 6 D 7 4 已知某二叉樹的中序 層序序列為 DBAFCE FDEBCA 則該二叉樹的后序序列為 A BCDEAF B ABDCEF C DBACEF D DABECF 5 以下關(guān)于二叉排序樹的說法中 錯(cuò)誤的有 個(gè) I 對一棵二叉排序樹按前序遍歷得出的結(jié)點(diǎn)序列是從小到大的序列 II 每個(gè)結(jié)點(diǎn)的值都比它左孩子的值大 比它右孩子結(jié)點(diǎn)的值小 則這樣的一棵二叉樹就是二叉排序 樹 III 在二叉排序樹中 新插入的關(guān)鍵字總是處于最底層 IV 刪除二叉排序樹中的一個(gè)結(jié)點(diǎn)再重新插入 得到的二叉排序樹和原來的相同 A 1 B 2 C 3 D 4 6 如右圖所示為一棵平衡二叉樹 字母不是關(guān)鍵字 在結(jié)點(diǎn) D 的右子樹上插入結(jié) 點(diǎn) F 后 會(huì)導(dǎo)致該平衡二叉樹失去平衡 則調(diào)整后的平衡二叉樹應(yīng)為 7 若 G 是一個(gè)具有 36 條邊的非連通無向圖 不含自回路和多重邊 則圖 G 的結(jié)點(diǎn)數(shù)至少是 A 11 B 10 C 9 D 8 8 已知有向圖 G V A 其中 V a b c d e A 對該 圖進(jìn)行拓?fù)渑判?下面序列中不是拓?fù)渑判虻氖?A a d c b e B d a b c e C a b d c e D a b c d e 9 折半查找有序表 2 10 25 35 40 65 70 75 81 82 88 100 若查找元素 75 需依次與表中元素 進(jìn)行比較 A 65 82 75 B 70 82 75 C 65 81 75 D 65 81 70 75 10 對一組數(shù)據(jù) 84 47 25 15 21 排序 數(shù)據(jù)在排序的過程中的變化如下 1 84 47 25 15 21 2 21 47 25 15 84 3 15 215 251 47 84 4 1521 2115 25 47 84 則所采用的排序方法是 A 堆排序 B 冒泡排序 C 快速排序 D 插入排序 11 若對 29 個(gè)記錄只進(jìn)行三趟多路平衡歸并 則選取的歸并路數(shù)至少是 A 2 B 3 C 4 D 5 1 模擬題中的問題請?jiān)谕醯来鹨蓪^(qū)提問 標(biāo)題請注明 模擬試題 第 X 套 第 x 題 第第1套套 C A B DE 2 12 下列關(guān)于配備 32 位微處理器的計(jì)算機(jī)說法正確的是 A 該機(jī)器的通用寄存器一般為 32 位 B 該機(jī)器的地址總線寬度為 32 位 C 該機(jī)器能支持 64 位操作系統(tǒng) D 以上說法均不正確 13 設(shè) x 補(bǔ) 1 x1x2x3x4 當(dāng)滿足 時(shí) x 1 m 右移一位 則在執(zhí)行完該段程序后 m 的值為 A 50DBH B FFB6H C A1B6H D D0DBH 15 某存儲(chǔ)系統(tǒng)中 主存容量是 Cache 容量的 4096 倍 Cache 被分為 64 個(gè)塊 當(dāng)主存地址和 Cache 地址 采用直接映像方式時(shí) 地址映射表的大小應(yīng)為 假設(shè)不考慮一致維護(hù)位 A 6 4097 bit B 64 12 bit C 6 4096 bit D 64 13 bit 16 下列關(guān)于 Cache 和虛擬存儲(chǔ)器的說法中 錯(cuò)誤的有 I 當(dāng)Cache失效 即不命中 時(shí) 處理器將會(huì)切換進(jìn)程 以更新Cache中的內(nèi)容 II 當(dāng)虛擬存儲(chǔ)器失效 如缺頁 時(shí) 處理器將會(huì)切換進(jìn)程 以更新主存中的內(nèi)容 III Cache和虛擬存儲(chǔ)器由硬件和OS共同實(shí)現(xiàn) 對應(yīng)用程序員均是透明的 IV 虛擬存儲(chǔ)器的容量等于主存和輔存的容量之和 A I和IV B III和IV C I II和III D I III和IV 17 在通用計(jì)算機(jī)指令系統(tǒng)的二地址指令中 操作數(shù)的物理位置可安排在 I 一個(gè)主存單元和緩沖存儲(chǔ)器 II 兩個(gè)數(shù)據(jù)寄存器 III 一個(gè)主存單元和一個(gè)數(shù)據(jù)寄存器 IV 一個(gè)數(shù)據(jù)寄存器和一個(gè)控制存儲(chǔ)器 V 一個(gè)主存單元和一個(gè)外存單元 A II III 和 IV B II III C I II 和 III D I II III 和 V 18 指令 從主存中讀出 A 總是根據(jù)程序計(jì)數(shù)器 PC B 有時(shí)根據(jù) PC 有時(shí)根據(jù)轉(zhuǎn)移指令 C 根據(jù)地址寄存器 D 有時(shí)根據(jù) PC 有時(shí)根據(jù)地址寄存器 19 流水線計(jì)算機(jī)中 下列語句發(fā)生的數(shù)據(jù)相關(guān)類型是 ADD R1 R2 R3 R2 R3 R1 ADD R4 R1 R5 R1 R5 R4 A 寫后些 B 讀后寫 C 寫后讀 D 讀后讀 20 間址尋址第一次訪問內(nèi)存所得到信息經(jīng)系統(tǒng)總線的 傳送到 CPU A 數(shù)據(jù)總線 B 地址總線 C 控制總線 D 總線控制器 21 傳輸一幅分辨率為 640X480 6 5 萬色的照片 圖像 假設(shè)采用數(shù)據(jù)傳輸速度為 56kb s 大約需要的 時(shí)間是 A 34 82s B 42 86s C 85 71s D 87 77s 22 當(dāng)有中斷源發(fā)出請求時(shí) CPU 可執(zhí)行相應(yīng)的中斷服務(wù)程序 以下可以提出中斷的是 I 外部事件 II Cache III 虛擬存儲(chǔ)器失效 IV 浮點(diǎn)運(yùn)算下溢 V 浮點(diǎn)運(yùn)算上溢 A I III 和 IV B I 和 V C I II 和 III D I III 和 V 23 相對采用單一內(nèi)核結(jié)構(gòu) 采用微內(nèi)核結(jié)構(gòu)設(shè)計(jì)和實(shí)現(xiàn)操作系統(tǒng)有諸多好處 但是 不是微內(nèi)核 的優(yōu)勢 A 使系統(tǒng)更高效 B 想添加新任務(wù)時(shí) 不必修改內(nèi)核 C 使系統(tǒng)更安全 D 使系統(tǒng)更可靠 3 24 支持多道程序設(shè)計(jì)的操作系統(tǒng)在運(yùn)行過程中 會(huì)不斷選擇新進(jìn)程來運(yùn)行 共享 CPU 資源 但是下面 哪個(gè)不是操作系統(tǒng)選擇新進(jìn)程的直接原因 A 運(yùn)行進(jìn)程的時(shí)間片用完 B 運(yùn)行進(jìn)程出錯(cuò) C 運(yùn)行進(jìn)程等待某個(gè)事件的發(fā)生 D 有新的進(jìn)程被創(chuàng)建進(jìn)入就緒隊(duì)列 25 設(shè)有 3 個(gè)作業(yè) 它們的到達(dá)時(shí)間和運(yùn)行時(shí)間如下表所示 并在一臺處理機(jī)上按單道方式運(yùn)行 如按高 響應(yīng)比優(yōu)先算法 則作業(yè)執(zhí)行的次序和平均周轉(zhuǎn)時(shí)間依次為 作業(yè)提交時(shí)間和運(yùn)行時(shí)間表 作業(yè)號 提交時(shí)間 運(yùn)行時(shí)間 小時(shí) 1 8 00 2 2 8 30 1 3 9 30 0 25 A J1 J2 J3 1 73 B J1 J3 J2 1 83 C J1 J3 J2 2 08 D J1 J2 J3 1 83 26 設(shè)有兩個(gè)進(jìn)程 P1 和 P2 counter 為共享變量 描述如下 int counter 6 P1 computing counter counter 1 P2 printing counter counter 2 兩個(gè)進(jìn)程并發(fā)執(zhí)行 運(yùn)行完成后 counter 的值不可能為 A 4 B 5 C 6 D 7 27 設(shè) m 為同類資源數(shù) n 為系統(tǒng)中并發(fā)進(jìn)程數(shù) 當(dāng) n 個(gè)進(jìn)程共享 m 個(gè)互斥資源時(shí) 每個(gè)進(jìn)程的最大需求 是 w 則下列情況會(huì)出現(xiàn)系統(tǒng)死鎖的是 A m 2 n 1 w 2 B m 2 n 2 w 1 C m 4 n 3 w 2 D m 4 n 2 w 3 28 有一請求分頁式存儲(chǔ)管理系統(tǒng) 頁面大小為每頁 100 字節(jié) 有一個(gè) 50 50 的整型數(shù)組按行為主序連續(xù) 存放 每個(gè)整數(shù)占兩個(gè)字節(jié) 將數(shù)組初始化為 0 的程序描述如下 int A 50 50 for int i 0 i 50 i for int j 0 j1 的單鏈表 L 從第一個(gè)結(jié)點(diǎn)開始計(jì)數(shù) 當(dāng)計(jì)數(shù)到 m m 1 時(shí) 將這第 m 個(gè)結(jié)點(diǎn)從單鏈表上摘除 然后從被摘除的下一個(gè)結(jié)點(diǎn)開始重新計(jì)數(shù) 當(dāng)計(jì)數(shù)到表尾時(shí) 接著表的第一 個(gè)結(jié)點(diǎn)繼續(xù)計(jì)數(shù) 試設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面都盡可能高效的算法 完成上述過程 要求 1 給出算法的基本設(shè)計(jì)思想 2 根據(jù)設(shè)計(jì)思想 采用 C 或 C 或 Java 語言描述算法 關(guān)鍵之處給出注釋 3 說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度 43 11 分 已知兩個(gè)實(shí)數(shù) x 68 y 8 25 它們在 C 語言中定義為 float 型變量 分別存放在寄存器 A 和 B 中 另外 還有兩個(gè)寄存器 C 和 D A B C D 都是 32 位的寄存器 請問下列問題 要求用 十六進(jìn)制表示二進(jìn)制序列 1 寄存器 A 和 B 中的內(nèi)容分別是什么 2 x 和 y 相加后的結(jié)果存放在 C 寄存器中 寄存器 C 中的內(nèi)容是什么 3 x 和 y 相減后的結(jié)果存放在 D 寄存器中 寄存器 D 中的內(nèi)容是什么 44 12 分 某 16 位機(jī)器所使用的指令格式和尋址方式如下所示 該機(jī)有四個(gè) 20 位基址寄存器 十六個(gè) 16 位通用寄存器 可用做變址寄存器 指令匯編格式中的 S 源 D 目標(biāo) 都是通用寄存器 M 是主存的一個(gè)單元 三種指令的操作碼分別是 MOV OP A H STA OP 1B H LDA OP 3C H MOV 是傳送指令 STA 為寫數(shù)指令 LDA 為讀數(shù)指令 1 分析三種指令的指令格式和尋址方式特點(diǎn) 2 處理機(jī)完成哪一種操作所花時(shí)間最短 哪一種最長 第二種指令的執(zhí)行時(shí)間有時(shí)會(huì)等于第三種 指令的執(zhí)行時(shí)間嗎 3 下列情況中 每個(gè)十六進(jìn)制指令字分別代表什么操作 若有指令編碼不正確 如何改正才能成 為合法指令 F0F1 H 3CD2 H 2856 H 6DC6 H 1C2 H 45 7 分 有三個(gè)進(jìn)程 PA PB 和 PC 合作解決文件打印問題 PA 將文件記錄從磁盤讀入主存的緩沖區(qū) 1 每執(zhí)行一次讀一個(gè)記錄 PB 將緩沖區(qū) 1 的內(nèi)容復(fù)制到緩沖區(qū) 2 每執(zhí)行一次復(fù)制一個(gè)記錄 PC 將 緩沖區(qū) 2 的內(nèi)容打印出來 每執(zhí)行一次打印一個(gè)記錄 緩沖區(qū)的大小等于一個(gè)記錄的大小 請用 P V 操作來保證文件的正確打印 46 8 分 某一個(gè)計(jì)算機(jī)系統(tǒng)采用虛擬頁式存儲(chǔ)管理方式 當(dāng)前在處理機(jī)上執(zhí)行的某一個(gè)進(jìn)程的頁表如 下所示 所有的數(shù)字均為十進(jìn)制 每一項(xiàng)的起始編號是 0 并且所有的地址均按字節(jié)編址 每頁的大 小為 1024 字節(jié) 邏輯頁號 存在位 引用位 修改位 頁框號 0 1 1 0 94 1 1 1 1 3 2 0 0 0 3 1 0 0 1 4 0 0 0 5 1 0 1 5 1 將下列邏輯地址轉(zhuǎn)換為物理地址 寫出計(jì)算過程 對不能計(jì)算的說明為什么 0793 1197 2099 3320 4188 5332 6 2 假設(shè)程序欲訪問第 2 頁 頁面置換算法為改進(jìn)的 CLOCK 算法 請問該淘汰哪頁 頁表如何修 改 上述地址的轉(zhuǎn)換結(jié)果是否改變 變成多少 47 9 分 TCP 的擁塞窗口 cwnd 大小與傳輸輪次 n 的關(guān)系如下所示 cwnd n 1 1 2 2 4 3 8 4 16 5 32 6 33 7 34 8 35 9 36 10 37 11 38 12 39 13 cwnd n 40 14 41 15 42 16 21 17 22 18 23 19 24 20 25 21 26 22 1 23 2 24 4 25 8 26 1 畫出 TCP 的擁塞窗口與傳輸輪次的關(guān)系曲線 2 分別指明 TCP 工作在慢開始階段和擁塞避免階段的時(shí)間間隔 3 在第 16 輪次和第 22 輪次之后發(fā)送方是通過收到三個(gè)重復(fù)的確認(rèn)還是通過超時(shí)檢測到丟失了報(bào) 文段 4 在第 1 輪次 第 18 輪次和第 24 輪次發(fā)送時(shí) 門限 ssthresh 分別被設(shè)置為多大 5 在第幾輪次發(fā)送出第 70 個(gè)報(bào)文段 6 假定在第 26 輪次之后收到了三個(gè)重復(fù)的確認(rèn) 因而檢測出了報(bào)文段的丟失 那么擁塞窗口 cwnd 和門限 ssthresh 應(yīng)設(shè)置為多大 7 第1套 答案與解析 一 單項(xiàng)選擇題 1 2 3 4 5 6 7 8 9 10 C B C B D B B D D A 11 12 13 14 15 16 17 18 19 20 C A D A D D B A C A 21 22 23 24 25 26 27 28 29 30 D D A D B C D B B D 31 32 33 34 35 36 37 38 39 40 A C C B B A B C B C 1 分析 單科書 P53 本題考查出棧序列的合法性 這類題通常采用手動(dòng)模擬法 解答 A 選項(xiàng) 6 入 5 入 5 出 4 入 4 出 3 入 3 出 6 出 2 入 1 入 1 出 2 出 B 選項(xiàng) 6 入 5 入 4 入 4 出 5 出 3 入 3 出 2 入 1 入 1 出 2 出 6 出 D 選項(xiàng) 6 入 5 入 4 入 3 入 2 入 2 出 3 出 4 出 1 入 1 出 5 出 6 出 CD 選項(xiàng) 無對應(yīng)的合法出入棧順序 另解 對于已入棧且尚未出棧的序列 要保證先入棧的一定不能在后入棧的前面出棧 C 選項(xiàng)中的 6 在 5 前入棧 5 沒有出棧 6 卻出棧了 所以不合法 其他都符合規(guī)律 2 分析 單科書 P64 本題考查棧在表達(dá)式求值中的應(yīng)用 棧通常可以解決括號匹配 表示式求值 迷宮問題 遞歸等應(yīng)用 解答 利用棧求表達(dá)式的值時(shí) 可以分別設(shè)立運(yùn)算符棧和運(yùn)算數(shù)棧 但其原理不變 選項(xiàng) B 中 A 入棧 B 入棧 計(jì)算得 R1 C 入棧 計(jì)算得 R2 D 入棧 計(jì)算得 R3 由此得棧深為 2 A C D 依次計(jì) 算得棧深為 4 3 3 3 分析 單科書 P90 本題考查樹的度與結(jié)點(diǎn)數(shù)的關(guān)系 將二叉樹的相關(guān)性質(zhì)推廣到樹 解答 設(shè) B 為分支數(shù) N 為結(jié)點(diǎn)總數(shù) 則 B N 1 N n0 n1 n2 n3 已知 n3 n2 n1 2 1 2 5 B 3 2 2 1 1 2 10 所以 n0 11 5 6 另解 畫草圖 畫出一個(gè)滿足題設(shè)條件的特定樹 然后計(jì)算其中葉結(jié)點(diǎn)的數(shù)量 4 分析 單科書 P96 本題考查由遍歷序列確定二叉樹 二叉樹的先序 中序和后序遍歷 訪問左 右子樹的順序不變的 層序遍歷先訪問第 1 層的結(jié)點(diǎn) 樹根 然后從左到右依次訪問第 2 層上的結(jié)點(diǎn) 依次類推 自上而下 自左向右逐層訪問各層上的結(jié)點(diǎn) 解答 由層序序列可得 F 是樹根結(jié)點(diǎn) 結(jié)合中序序列 DBA 構(gòu)成 F 的左子樹 CE 構(gòu)成 F 的右子樹 D E 是第 2 層結(jié)點(diǎn) 進(jìn)一步有 C 是 E 的左孩子 E 無右孩子 這樣 A 是第 4 層結(jié)點(diǎn) 據(jù) DBA 序列有 B 是 D 的右孩子 A 是 B 的右孩子 易知后序序列為 ABDCEF 提示 本類題型建議畫出草圖求快速解 根據(jù)左 右子樹的遍歷順序不變 遞歸地根據(jù)根結(jié)點(diǎn)劃分 出左 右子樹 直到得到序列的整個(gè)樹形結(jié)構(gòu) 然后再根據(jù)圖形代入驗(yàn)證 5 分析 單科書 P109 本題考查二叉排序樹的性質(zhì) 二叉排序樹的定義及性質(zhì) 二叉排序樹的建立 二叉排序樹的刪除 二叉排序樹的查找效率分析等都是考查的重點(diǎn) 二叉排序樹是遞歸定義的 解答 二叉排序樹的中序序列才是從小到大有序的 I 錯(cuò)誤 左子樹上所有的值均小于根結(jié)點(diǎn)的值 右子樹上所有的值均大于根結(jié)點(diǎn)的值 而不僅僅是與左 右孩子的值進(jìn)行比較 II 錯(cuò)誤 新插入的關(guān)鍵字 總是作為葉結(jié)點(diǎn)來插入 但葉結(jié)點(diǎn)不一定總是處于最底層 III 錯(cuò)誤 當(dāng)刪除的是非葉結(jié)點(diǎn)時(shí) 根據(jù) III 的 解釋 顯然重新得到的二叉排序樹和原來的不同 只有當(dāng)刪除的是葉結(jié)點(diǎn)時(shí) 才能得到和原來一樣的二叉 排序樹 IV 錯(cuò)誤 6 分析 單科書 P113 本題考查平衡二叉樹的旋轉(zhuǎn) 平衡二叉樹的插入過程前半程和二叉排序樹相 同 但新插入結(jié)點(diǎn)可能會(huì)導(dǎo)致不平衡 因此需要進(jìn)行旋轉(zhuǎn)調(diào)整 單科書指對應(yīng)科目的王道考研系列單科復(fù)習(xí)指導(dǎo)書 8 解答 由于在結(jié)點(diǎn) A 的右孩子 R 的右子樹 R 上插入新結(jié)點(diǎn) F A 的平衡因子由 1 減至 2 導(dǎo) 致以 A 為根的子樹失去平衡 需要進(jìn)行 RR 旋轉(zhuǎn) 左單旋 C A B DE F C A B DE 2 1 10 D C A FEB 0 0 1 1 RR 旋轉(zhuǎn)的過程如上圖所示 將 A 的右孩子 C 向左上旋轉(zhuǎn)代替 A 成為根結(jié)點(diǎn) 將 A 結(jié)點(diǎn)向左下旋轉(zhuǎn) 成為 C 的左子樹的根結(jié)點(diǎn) 而 C 的原來的左右子樹 E 則作為 A 的右子樹 注意 平衡旋轉(zhuǎn)的操作都是在插入操作后 引起不平衡的最小不平衡子樹上進(jìn)行的 只要將這個(gè)最 小不平衡子樹調(diào)整平衡 則其上級結(jié)點(diǎn)也將恢復(fù)平衡 7 分析 單科書 P150 本題考查無向完全圖的性質(zhì) n 個(gè)結(jié)點(diǎn)的無向完全圖共有 n n 1 2 條邊 對 于 n 1 個(gè)結(jié)點(diǎn)和 n n 1 2 邊構(gòu)成的非連通圖 僅當(dāng) n 個(gè)頂點(diǎn)構(gòu)成完全圖 第 n 1 個(gè)頂點(diǎn)構(gòu)成一個(gè)孤立頂點(diǎn) 的圖 若再增加一條邊 則在任何情況下都是連通的 解答 n 個(gè)頂點(diǎn)構(gòu)成的無向圖中 邊數(shù) n n 1 2 將 e 36 代入 有 n 9 現(xiàn)已知無向圖是非連通的 則 n 至少為 10 8 分析 單科書 P171 本題考查拓?fù)渑判?拓?fù)渑判虻姆椒?1 從 AOV 網(wǎng)中選擇一個(gè)沒有前驅(qū)的 頂點(diǎn) 入度為 0 并輸出它 2 從 AOV 網(wǎng)中刪去該頂點(diǎn) 以及從該頂點(diǎn)發(fā)出的全部有向邊 3 重復(fù)上 述兩步 直到剩余的網(wǎng)中不再存在沒有前驅(qū)的頂點(diǎn)為止 解答 選項(xiàng) D 中 刪去 a b 及其對應(yīng)的出邊后 c 的入度不為 0 此有邊 故不是拓?fù)湫蛄?選項(xiàng) A B D 均為拓?fù)湫蛄?解答本類題時(shí) 建議讀者根據(jù)邊集合畫出草圖 9 分析 單科書 P197 本題考查折半查找的查找過程 此類題應(yīng)結(jié)合元素下標(biāo)求解 解答 有序表長 12 依據(jù)折半查找的思想 第一次查找第 1 12 2 6 個(gè)元素 即 65 第二次查 找第 6 1 12 2 9 個(gè)元素 即 81 第三次查找第 7 9 1 2 7 個(gè)元素 即 70 第四次查找第 7 1 8 2 8 個(gè)元素 即 75 比較的元素依次為 65 81 70 75 10 分析 單科書 P237 本題考查堆排序的排序過程 堆排序的過程首先是構(gòu)造初始堆 然后將堆頂 元素 最大值或最小值 與最后一個(gè)元素交換 此時(shí)堆的性質(zhì)會(huì)被破壞 需要從根結(jié)點(diǎn)開始進(jìn)行向下調(diào)整 操作 如此反復(fù) 直到堆只有一個(gè)元素為止 解答 經(jīng)過觀察發(fā)現(xiàn) 每趟排序都是從未排序序列中選擇一個(gè)最大元素放到其最終位置 符合大頂 堆的性質(zhì) 初始序列本身就是一個(gè)大頂堆 將每趟數(shù)據(jù)代入驗(yàn)證正確 冒泡排序雖然也可以形成全局有序 序列 但是題中的排序過程顯然不滿足冒泡排序的過程 注意 堆存儲(chǔ)在一個(gè)連續(xù)的數(shù)組單元中 它是一棵完全二叉樹 11 分析 2012 補(bǔ)充文件 本題考查多路平衡歸并 解答 m 路平衡歸并就是將 m 個(gè)有序表組合成一個(gè)新的有序表 每經(jīng)過一趟歸并后 剩下的記錄數(shù) 是原來的 1 m 則經(jīng)過 3 趟歸并后 29 m3 1 4 為最小滿足條件的數(shù) 注意 本題中 4 和 5 均能滿足 但 6 不滿足 若 m 6 則只需 2 趟歸并便可排好序 因此 還需要 滿足 m2 29 也即只有 4 和 5 才能滿足 另解 此類題 建議大家畫出 ABC 選項(xiàng)對應(yīng)的滿樹的草圖 然后計(jì)算結(jié)點(diǎn)數(shù)是否能達(dá)到或超過 29 個(gè) 如果 C 能到達(dá) 則 D 就不必畫了 否則就必然選 D 了 12 分析 單科書 P10 本題考查計(jì)算機(jī)的性能指標(biāo) 微處理器的位數(shù)是指該 CPU 一次能夠處理的數(shù) 據(jù)長度 稱為機(jī)器字長 通常機(jī)器字長等于通用寄存器的長度 解答 64 位操作系統(tǒng) 通常向下兼容 需要 64 位 CPU 的支持 64 位操作系統(tǒng)不僅是尋址范圍增 加到 264 同時(shí)要求機(jī)器字長 64 位 13 分析 單科書 P31 本題考查小數(shù)的補(bǔ)碼表示法 真值 0 的補(bǔ)碼表示是唯一的 補(bǔ)碼比原碼多表示 1 負(fù)數(shù) x 補(bǔ)和 x 原的轉(zhuǎn)換規(guī)則 符號位不變 數(shù)值部分取反 末位加 1 解答 1 2 補(bǔ)為 1 1000 采用補(bǔ)碼表示時(shí) 如果符號位相同 則數(shù)值位越大 碼值越大 所以要使 9 x 1 2 成立 x1必須為 0 而 x2 x4任意 另解 因?yàn)?1 補(bǔ)為 1 0000 直接排除 A B C 只可能選 D 解答此類題時(shí) 應(yīng)有意識到聯(lián)想到 幾個(gè)特殊值的表示 以迅速得出答案 或檢驗(yàn)答案的正確性 14 分析 單科書 P33 本題考查無符號數(shù)的邏輯移位運(yùn)算 無符號數(shù)的移位方式為邏輯移位 不管是 左移還是右移 都是添 0 解答 A1B6H 作為無符號數(shù) 使用邏輯右移 1010 0001 10110 0110 右移一位得 0101 0000 1101 10011 即 50DBH 15 分析 單科書 P96 本題考查 Cache 與主存的映射原理 主存 Cache 地址映射表 標(biāo)記陣列 中 內(nèi)容 映射的 Cache 地址 直接映射不需要因?yàn)?Cache 地址唯一 組相聯(lián)只需要組號 主存標(biāo)記 命中 判斷 有效位 如下圖所示 解答 由于 Cache 被分為 64 個(gè)塊 那么 Cache 有 64 行 采用直接映射 一行相當(dāng)于一組 故而該 標(biāo)記陣列每行存儲(chǔ) 1 個(gè)標(biāo)記項(xiàng) 其中主存標(biāo)記項(xiàng)為 12bit 212 4096 是 Cache 容量的 4096 倍 那么就是 地址長度比 Cache 長 12 位 加上 1 位有效位 故而為 64 13bit 16 分析 單科書 P93 等 本題考查 Cache 和虛擬存儲(chǔ)器的特性 Cache 和虛擬存儲(chǔ)器和原理都是基于 程序訪問的局部性原理 但他們實(shí)現(xiàn)的方法和作用均不太相同 解答 Cache失效與虛擬存儲(chǔ)器失效的處理方法不同 Cache完全由硬件實(shí)現(xiàn) 不涉及到軟件端 虛 擬存儲(chǔ)器由硬件和OS共同完成 缺頁時(shí)才會(huì)發(fā)出缺頁中斷 故I錯(cuò)誤正確 II正確錯(cuò)誤 III錯(cuò)誤 在虛擬存 儲(chǔ)器中 主存的內(nèi)容只是輔存的一部分內(nèi)容 IV錯(cuò)誤 17 分析 單科書 P124 本題考查指令的地址碼字段 對于二地址指令 若兩個(gè)操作數(shù)都在寄存器中 稱為 RR 型指令 若一個(gè)操作數(shù)在寄存器中另一個(gè)操作數(shù)在存儲(chǔ)器中 稱為 RS 型指令 若兩個(gè)操作數(shù)都 在存儲(chǔ)器中 則稱為 SS 型指令 解答 緩沖存儲(chǔ)器 如 Cache 用來存放最近使用的數(shù)據(jù) 其內(nèi)容和調(diào)度是由硬件或操作系統(tǒng)完成 的 因此不能作為指令的地址碼 控制存儲(chǔ)器采用 ROM 結(jié)構(gòu) 存放的是微程序 它對軟件開發(fā)人員是透 明的 顯然不能作為指令的地址碼 CPU 不能直接訪問外存 如果所需的數(shù)據(jù)存放在外存 則需要先調(diào)入 主存 而指令中只能使用主存地址 18 分析 單科書 P153 本題考查指令的執(zhí)行特點(diǎn) 不論是中斷返回指令 還是無條件轉(zhuǎn)移指令等 指令總是根據(jù)程序計(jì)數(shù)器 PC 中的內(nèi)容來執(zhí)行下一條指令 解答 考生可能會(huì)想到無條件轉(zhuǎn)移指令 認(rèn)為不一定總是根據(jù) PC 讀出 實(shí)際上 當(dāng)前指令正在執(zhí) 行時(shí) 其實(shí) PC 已經(jīng)是下一條指令的地址了 若遇到無條件轉(zhuǎn)移指令 只需簡單地將跳轉(zhuǎn)地址覆蓋原 PC 的內(nèi)容即可 最終的結(jié)果還是指令需要根據(jù) PC 從主存讀出 19 分析 單科書 P178 本題考查流水線的數(shù)據(jù)相關(guān) 數(shù)據(jù)相關(guān)包括 RAW 寫后讀 WAW 寫后寫 WAR 讀后寫 設(shè)有 i 和 j 兩條指令 i 指令在前 j 指令在后 則三種相關(guān)的含義 RAW 寫后讀 指令 j 試圖在指令 i 寫入寄存器前舊讀出該寄存器的內(nèi)容 這樣指令 j 就會(huì)錯(cuò)誤地 讀出該寄存器舊的內(nèi)容 WAR 讀后寫 指令 j 試圖在指令 i 讀出該寄存器前就寫入該寄存器 這樣指令 i 就會(huì)錯(cuò)誤地讀出 該寄存器的新內(nèi)容 10 WAW 寫后寫 指令 j 試圖在指令 i 寫入寄存器前就寫入該寄存器 這樣兩次寫的先后次序被顛倒 就會(huì)錯(cuò)誤地使由指令 i 寫入的值稱為該寄存器的內(nèi)容 解答 在這兩條指令中 都對 R1 進(jìn)行操作 其中前面對 R1 寫操作 后面對 R1 讀操作 因此發(fā)生 寫后讀相關(guān) 20 分析 單科書 P153 本題考查間址周期的數(shù)據(jù)流 系統(tǒng)總線按傳送內(nèi)容的不同可分為 地址總線 數(shù)據(jù)總線和控制總線 地址總線由單向多根信號線組成 可用于 CPU 向主存 外設(shè)傳送地址信息 數(shù)據(jù) 總線由雙向的多根信號線組成 CPU 可以沿著這些線從主存或外設(shè)存讀入數(shù)據(jù) 也可發(fā)送數(shù)據(jù) 控制總線 上傳輸控制信息 包括控制命令和反饋信號等 解答 間址尋址第一次訪問內(nèi)存所得到的信息是操作數(shù)的有效地址 該地址通過數(shù)據(jù)線傳送至 CPU 而不是地址線 地址線是單向總線 只能由 CPU 向主存和外設(shè)傳送 21 分析 單科書 P219 本題考查圖像存儲(chǔ)空間的計(jì)算 首先計(jì)算出每幅圖的存儲(chǔ)空間 然后除以數(shù) 據(jù)傳輸率 就可以得出傳輸一幅圖的時(shí)間 圖片的容量不僅與分辨率有關(guān) 還與顏色數(shù)有關(guān) 分辨率越高 顏色數(shù)越多 圖像所占的容量就越大 解答 圖像的顏色數(shù)為 65 536 色 意味著顏色深度為 log265536 16 即用 16 位的二進(jìn)制數(shù)表示 65 536 種顏色 則一幅圖所占據(jù)的存儲(chǔ)空間為 640X480X16 4915200b 數(shù)據(jù)傳輸速度為 56kb s 則傳輸時(shí) 間 4915200b 56X103b s 87 77s 22 分析 單科書 P227 本題考查中斷請求 中斷請求是指中斷源向 CPU 發(fā)送中斷請求信號 分為外 中斷和內(nèi)中斷 外中斷指來自處理器和內(nèi)存外部的中斷 如 I O 設(shè)備發(fā)出的 外部事件等 內(nèi)中斷指在處 理器和內(nèi)存內(nèi)部產(chǎn)生的中斷 解答 外部事件如按鍵以退出運(yùn)行的程序等 屬于外中斷 I 正確 Cache 完全是由硬件實(shí)現(xiàn) 的 不會(huì)涉及到中斷層面 II 錯(cuò)誤 虛擬存儲(chǔ)器失效如缺頁等 會(huì)發(fā)出缺頁中斷 屬于內(nèi)中斷 III 正確 浮點(diǎn)運(yùn)算下溢 直接當(dāng)做機(jī)器零處理 而不會(huì)引發(fā)中斷 IV 錯(cuò)誤 浮點(diǎn)數(shù)上溢 表示超過了浮點(diǎn)數(shù)的表示 范圍 屬于內(nèi)中斷 V 正確 23 分析 補(bǔ)充文檔 本題考查微內(nèi)核結(jié)構(gòu)的特點(diǎn) 微內(nèi)核結(jié)構(gòu)將內(nèi)核中最基本的功能 如進(jìn)程管理 虛存管理等 保留在內(nèi)核 而將那些不需要在核心態(tài)執(zhí)行的部分移到用戶態(tài)執(zhí)行 解答 微內(nèi)核結(jié)構(gòu)需要頻繁地在管態(tài)和目態(tài)之間進(jìn)行切換 操作系統(tǒng)的執(zhí)行開銷相對偏大 而且在 微內(nèi)核結(jié)構(gòu)中 那些移出內(nèi)核的操作系統(tǒng)代碼根據(jù)分層的原則被劃分成若干服務(wù)程序 它們的執(zhí)行相互獨(dú) 立 交互則都借助于微內(nèi)核進(jìn)行通信 影響了系統(tǒng)的效率 因此 A 不是優(yōu)勢 由微內(nèi)核的定義和特點(diǎn) 不 難得出 B C 和 D 均是微內(nèi)核結(jié)構(gòu)的優(yōu)勢 24 分析 單科書 P35 本題考查進(jìn)程調(diào)度的時(shí)機(jī) 讀者應(yīng)掌握不能進(jìn)行進(jìn)程調(diào)度與切換的情況 處理 中斷的過程 訪問臨界區(qū) 原子操作 及應(yīng)該進(jìn)行進(jìn)程調(diào)度與切換的情況 解答 運(yùn)行著的進(jìn)程由于時(shí)間片用完 或者運(yùn)行結(jié)束 或者需要等待事件的發(fā)生 例如等待鍵盤響 應(yīng) 或者出錯(cuò) 或者自我阻塞等均可以激活調(diào)度程序進(jìn)行重新調(diào)度 選擇一個(gè)新的就緒進(jìn)程投入運(yùn)行 新進(jìn)程加入到就緒隊(duì)列不是引起調(diào)度的直接原因 當(dāng) CPU 正在運(yùn)行其它進(jìn)程時(shí) 該進(jìn)程仍需等待 即使 在采用高優(yōu)先級優(yōu)先調(diào)度算法的系統(tǒng)中 一個(gè)最高優(yōu)先級的進(jìn)程進(jìn)入就緒隊(duì)列 仍需要考慮是否允許搶占 當(dāng)不允許搶占時(shí)仍需等待 25 分析 單科書 P39 本題考查高響應(yīng)比優(yōu)先調(diào)度和平均周轉(zhuǎn)時(shí)間 高響應(yīng)比優(yōu)先調(diào)度算法綜合考慮 了進(jìn)程的等待時(shí)間和執(zhí)行時(shí)間 響應(yīng)比 等待時(shí)間 執(zhí)行時(shí)間 執(zhí)行時(shí)間 解答 J1 第一個(gè)提交 也第一個(gè)執(zhí)行 J1 在 10 00 執(zhí)行完畢 這時(shí) J2 J3 都已到達(dá) 此時(shí) J2 的響 應(yīng)比 1 5 1 1 2 5 J3 的響應(yīng)比 0 5 0 25 0 25 3 故第二個(gè)執(zhí)行 J3 第三個(gè)執(zhí)行 J2 平均周轉(zhuǎn)時(shí)間 J1 的周轉(zhuǎn)時(shí)間 J2 的周轉(zhuǎn)時(shí)間 J3 的周轉(zhuǎn)時(shí)間 3 2 1 75 1 0 5 0 25 3 5 5 3 1 83 26 分析 單科書 P22 本題考查程序的并發(fā)執(zhí)行 在并發(fā)環(huán)境下 程序的執(zhí)行是間斷的 由于失去了 封閉性 也將導(dǎo)致失去了結(jié)果的可再現(xiàn)性 解答 本題需要考慮賦值表達(dá)式左值和右值 或理解為分解成 2 條指令 如下 計(jì)算右值 1 counter 1 3 counter 2 左值賦值 2 counter 4 counter 11 初始時(shí) counter 為 6 考慮到進(jìn)程并發(fā)執(zhí)行的特點(diǎn) 當(dāng)執(zhí)行順序?yàn)?1 2 3 4 或 3 4 1 2 時(shí) counter 的結(jié)果 為 5 當(dāng)執(zhí)行順序?yàn)?1 3 2 4 或 3 1 2 4 時(shí) counter 的結(jié)果為 4 當(dāng)執(zhí)行順序?yàn)?1 3 4 2 或 3 1 4 2 時(shí) counter 的結(jié)果為 7 故而無法得到 6 27 分析 單科書 P75 本題考查死鎖的檢測 解答 A 不會(huì)發(fā)生死鎖 只有一個(gè)進(jìn)程怎么也不會(huì)發(fā)生死鎖 B 不會(huì)發(fā)生死鎖 兩個(gè)進(jìn)程各需要一 個(gè)資源 而系統(tǒng)中剛好有 2 個(gè)資源 C 不會(huì)發(fā)生死鎖 3 個(gè)進(jìn)程需要的最多資源數(shù)都是 2 系統(tǒng)總資源數(shù)是 4 所以總會(huì)有一個(gè)進(jìn)程得到 2 個(gè)資源 運(yùn)行完畢后釋放資源 D 可能會(huì)發(fā)生死鎖 當(dāng) 2 個(gè)進(jìn)程各自都占 有了 2 個(gè)資源后 系統(tǒng)再無可分配資源 由此可得出結(jié)論 當(dāng)滿足 m n w 1 1 時(shí) 不會(huì)產(chǎn)生死鎖 28 分析 單科書 P149 本題考查缺頁中斷的計(jì)算 對于整個(gè)程序 都會(huì)遇到每個(gè)頁面的第一個(gè)整數(shù) 不在內(nèi)存中 其他欲訪問的整數(shù)都在內(nèi)存的頁面中 解答 一個(gè)頁面可以容納 100 2 50 個(gè)整數(shù) 50 50 整型數(shù)組以行序?yàn)橹餍虼鎯?chǔ) 則每行 剛好 50 個(gè)整數(shù) 占用一個(gè)頁面 共需要 50 個(gè)頁面 在數(shù)組中剛好每行占用一個(gè)內(nèi)存頁面 代碼是按行訪問的 故每訪問一行的第一個(gè)整數(shù)時(shí)產(chǎn)生一次缺頁中斷 提示 本題若將語句 A i j 0 改為 A j i 0 則應(yīng)該如何計(jì)算 29 分析 單科書 P129 等 本題考查各存儲(chǔ)分配方法的特點(diǎn) 當(dāng)程序小于固定分區(qū)大小時(shí) 也占用了 一個(gè)完整的內(nèi)存分區(qū)空間 導(dǎo)致分區(qū)內(nèi)部有空間浪費(fèi) 這種現(xiàn)象稱內(nèi)部碎片 解答 固定分區(qū)存在內(nèi)部碎片 凡涉及到頁的存儲(chǔ)分配管理 每個(gè)頁的長度都一樣 對應(yīng)固定 所以會(huì)產(chǎn)生內(nèi)部碎片 雖然頁的碎片比較小 每個(gè)進(jìn)程平均產(chǎn)生半個(gè)塊大小的內(nèi)部碎片 段式管理中每個(gè) 段的長度都不一樣 對應(yīng)不固定 所以只會(huì)產(chǎn)生外部碎片 30 分析 單科書 P188 等 本題考查文件系統(tǒng)的多個(gè)知識點(diǎn) 解答 文件系統(tǒng)使用文件名進(jìn)行管理 也實(shí)現(xiàn)了文件名到物理地址的轉(zhuǎn)換 A 錯(cuò)誤 多級目錄結(jié)構(gòu) 中 對文件的訪問通過路徑名和文件名進(jìn)行 B 錯(cuò)誤 文件被劃分的物理塊的大小是固定的 通常和內(nèi)存 管理中的頁面大小一致 C 錯(cuò)誤 邏輯記錄是文件中按信息在邏輯上的獨(dú)立含義來劃分的信息單位 它是 對文件進(jìn)行存取操作的基本單位 D 正確 31 分析 單科書 P205 本題考查多級索引下文件的存放方式 本題是一個(gè)簡化的多級索引題 根據(jù) 題意 它采用的是三級索引 那么索引表就應(yīng)該具有三重 解答 依題意 每個(gè)盤塊為 1024B 每個(gè)索引號占 4 字節(jié) 因此每個(gè)索引塊可以存放 256 條索引號 三級索引共可以管理文件的大小為 256 256 256 1024B 16GTB 32 分析 單科書 P243 等 本題考查各種輸入 輸出技術(shù) 并行技術(shù)主要是為了提高整機(jī)的運(yùn)行效率 和吞吐率 通道技術(shù)是為了減少 CPU 對 I O 操作的控制 提高 CPU 的效率 緩沖技術(shù)是為了解決 CPU 和 外設(shè)的速度不匹配 虛存技術(shù)是為了解決存儲(chǔ)系統(tǒng)的容量問題 解答 緩沖技術(shù)的引入主要解決 CPU 速度和外設(shè)速度不匹配的問題 它同時(shí)減少了通道數(shù)量上的 占用 提高了 CPU I O 和通道的并發(fā)性 減少了中斷的次數(shù) 放寬了 CPU 對中斷響應(yīng)的時(shí)間要求 例如 打印 文件訪問 網(wǎng)絡(luò)收發(fā)等場合 均要用到緩沖技術(shù) 33 分析 單科書 P14 本題考查傳輸層的功能 在 OSI RM 中 數(shù)據(jù)鏈路層提供結(jié)點(diǎn)到結(jié)點(diǎn)的通信 網(wǎng)絡(luò)層提供主機(jī)到主機(jī)的通信 傳輸層提供端到端 進(jìn)程到進(jìn)程 的通信 解答 傳輸層的作用是提供源主機(jī)到目的主機(jī)進(jìn)程之間的邏輯通信 稱為 端到端 這里的 端 是 指用戶程序的端口 端口號標(biāo)識了不同的進(jìn)程 分用 34 分析 單科書 P42 本題考查物理層設(shè)備 電磁信號在網(wǎng)絡(luò)傳輸媒體中進(jìn)行傳遞時(shí)會(huì)衰減而使信號 變得越來越弱 還會(huì)由于電磁噪聲和干擾使信號發(fā)生畸變 因此需要在一定的傳輸媒體距離中使用中繼器 來對傳輸?shù)臄?shù)據(jù)信號整形放大后再傳遞 解答 放大器常用于遠(yuǎn)距離模擬信號的傳輸 它同時(shí)也會(huì)使噪聲放大 引起失真 網(wǎng)橋用來連接兩 個(gè)網(wǎng)段以擴(kuò)展物理網(wǎng)絡(luò)的覆蓋范圍 路由器是網(wǎng)絡(luò)層的互連設(shè)備 可以實(shí)現(xiàn)不同網(wǎng)絡(luò)的互連 中繼器的工 作原理是信號再生 不是簡單的放大 從而延長網(wǎng)絡(luò)的長度 35 分析 單科書 P62 本題考查后退 N 幀協(xié)議的原理 數(shù)據(jù)鏈路層的停止 等待協(xié)議 后退 N 幀協(xié)議 選擇重傳協(xié)議 以及 TCP 協(xié)議對發(fā)送窗口和接收窗口的要求 是理解協(xié)議工作原理精髓所在 12 解答 后退 N 幀協(xié)議的最大發(fā)送窗口為 2n 1 其中 n 為幀號的位數(shù) 題目中已經(jīng)說明發(fā)送窗口的 大小為 16 也就是說如果要使得協(xié)議不出錯(cuò) 必須滿足 16 2n 1 所以 n 至少要等于 5 36 分析 單科書 P69 本題考查 CSMA 協(xié)議的各種監(jiān)聽 CSMA 有三種類型 非堅(jiān)持 CSMA 一 個(gè)站點(diǎn)在發(fā)送數(shù)據(jù)幀之前 先對媒體進(jìn)行檢測 如果沒有其它站點(diǎn)在發(fā)送數(shù)據(jù) 則該站點(diǎn)開始發(fā)送數(shù)據(jù) 如果媒體被占用 則該站點(diǎn)不會(huì)持續(xù)監(jiān)聽媒體而等待一個(gè)隨機(jī)的延遲時(shí)間后再監(jiān)聽 1 堅(jiān)持 CSMA 當(dāng) 一個(gè)站點(diǎn)要發(fā)送數(shù)據(jù)幀時(shí) 它就監(jiān)聽媒體 判斷當(dāng)前時(shí)刻是否有其他站點(diǎn)正在傳輸數(shù)據(jù) 如果媒體忙的話 該站點(diǎn)等待直至媒體空閑 一旦該站點(diǎn)檢測到媒體空閑 就立即發(fā)送數(shù)據(jù)幀 故 IV 正確 如果產(chǎn)生沖突 則等待一個(gè)隨機(jī)時(shí)間再監(jiān)聽 之所以叫 1 堅(jiān)持 是因?yàn)楫?dāng)一個(gè)站點(diǎn)發(fā)現(xiàn)媒體空閑的時(shí)候 它傳輸數(shù)據(jù)幀 的概率是 1 P 堅(jiān)持 CSMA 當(dāng)一個(gè)站點(diǎn)要發(fā)送數(shù)據(jù)幀時(shí) 它先檢測媒體 若媒體空閑 則該站點(diǎn)以概 率 P 的可能性發(fā)送數(shù)據(jù) 而有 1 P 的概率會(huì)把發(fā)送數(shù)據(jù)幀的任務(wù)延遲到下一個(gè)時(shí)槽 P 堅(jiān)持 CSMA 是非堅(jiān) 持 CSMA 和 1 堅(jiān)持 CSMA 的折中 解答 采用隨機(jī)的監(jiān)聽延遲時(shí)間可以減少?zèng)_突的可能性但其缺點(diǎn)也是很明顯的 即使有多個(gè)站點(diǎn)有 數(shù)據(jù)要發(fā)送 因?yàn)榇藭r(shí)所有站點(diǎn)可能都在等待各自的隨機(jī)延遲時(shí)間 而媒體仍然可能處于空閑狀態(tài) 這樣 就使得媒體的利用率較為低下 故 I 錯(cuò)誤 1 堅(jiān)持 CSMA 的優(yōu)點(diǎn)是 只要媒體空閑 站點(diǎn)就立即發(fā)送 它 的缺點(diǎn)在于 假如有兩個(gè)或兩個(gè)以上的站點(diǎn)有數(shù)據(jù)要發(fā)送 沖突就不可避免 故 II 錯(cuò)誤 按照 P 堅(jiān)持 CSMA 的規(guī)則 若下一個(gè)時(shí)槽也是空閑的 則站點(diǎn)同樣按照概率 P 的可能性發(fā)送數(shù)據(jù) 所以說如果處理得當(dāng) P 堅(jiān) 持型監(jiān)聽算法還是可以減少網(wǎng)絡(luò)的空閑時(shí)間的 故 III 錯(cuò)誤 37 分析 單科書 P116 本題考查子網(wǎng)劃分與子網(wǎng)掩碼 不同子網(wǎng)之間需通過路由器相連 子網(wǎng)內(nèi)的 通信則無需經(jīng)過路由器轉(zhuǎn)發(fā) 因此比較各主機(jī)的子網(wǎng)號即可 解答 將子網(wǎng)掩碼 255 255 192 0 與主機(jī) 129 23 144 16 進(jìn)行 與 操作 得到該主機(jī)網(wǎng)絡(luò)地址為 129 23 128 0 再將該子網(wǎng)掩碼分別與四個(gè)候選答案的地址進(jìn)行 與 操作 只有 129 23 127 222 的網(wǎng)絡(luò)地址 不為 129 23 128 0 因此該主機(jī)與 129 23 144 16 不在一個(gè)子網(wǎng)中 需要通過路由器轉(zhuǎn)發(fā)信息 38 分析 單科書 P113 P120 本題考查 IP 報(bào)頭字段的功能和 ICMP 報(bào)文 ICMP 報(bào)文作為 IP 分組的 數(shù)據(jù)字段 用它來使得主機(jī)或路由器可以報(bào)告差錯(cuò)和異常情況 解答 路由器對 TTL 值為零的數(shù)據(jù)分組進(jìn)行丟棄處理 并向源主機(jī)返回時(shí)間超時(shí)的 ICMP 報(bào)文 39 分析 單科書 P171 本題考查 TCP 的擁塞控制 此類題往往綜合四種擁塞控制算法 解題時(shí)或畫 出擁塞窗口變化曲線圖 或列出擁塞窗口大小變化序列 尤其要注意在拐點(diǎn)處的變化情況 解答 在慢啟動(dòng)和擁塞避免算法中 擁塞窗口初始值為 1 窗口大小開始按指數(shù)增長 當(dāng)擁塞窗口 大于慢啟動(dòng)門限后 停止使用慢啟動(dòng)算法 改用擁塞避免算法 此時(shí) 慢啟動(dòng)的門限值初始為 8 當(dāng)擁塞 窗口增大到 8 時(shí)改用擁塞避免算法 窗口大小按線性增長 每次增長 1 個(gè)報(bào)文段 當(dāng)增加到 12 時(shí) 出現(xiàn) 超時(shí) 重新設(shè)置門限值為 6 12 的一半 擁塞窗口再重新設(shè)為 1 執(zhí)行慢啟動(dòng)算法 到門限值為 6 時(shí)執(zhí)行 擁塞避免算法 按照上面的算法 擁塞窗口的變化為 1 2 4 8 9 10 11 12 1 2 4 6 7 8 9 從該序列可以看出 第 12 次傳輸時(shí)擁塞窗口大小為 6 注意 很多考生誤選 D 選項(xiàng) 原因是直接在以上的序列中從 4 增加到 8 擁塞窗口的大小是和門限 值有關(guān)的 在慢開始算法中不能直接變化為大于門限值 所以 4 只能最多增加到 6 之后再執(zhí)行擁塞避免 算法 40 分析 單科書 P185 本題考查客戶 服務(wù)器模式的概念 客戶端是服務(wù)請求方 服務(wù)器是服務(wù)提供 方 二者的交互由客戶端發(fā)起 解答 客戶端是連接的請求方 在連接未建立之前 服務(wù)器在端口 80 上監(jiān)聽 這時(shí)客戶端必須要知 道服務(wù)器的地址才能發(fā)出請求 很明顯服務(wù)器事先不需要知道客戶端的地址 一旦連接建立后 服務(wù)器就 能主動(dòng)發(fā)送數(shù)據(jù)給客戶端 即瀏覽器顯示的內(nèi)容來自服務(wù)器 用于一些消息的通知 例如一些錯(cuò)誤的通 知 在客戶 服務(wù)器模型中 默認(rèn)端口號通常都是指服務(wù)器端 而客戶端的端口號通常都是動(dòng)態(tài)分配 二 綜合應(yīng)用題 第 41 47 小題 共 70 分 41 分析 本題考查順序查找和折半查找的判定樹 及對應(yīng)的平均查找長度 本題的難點(diǎn)在于各個(gè)數(shù)據(jù) 的查找概率 以及查找失敗的概率是不同的 在這種情況下折半查找的效率未必比順序查找的效率好 本 題應(yīng)特別注意如何計(jì)算折半查找失敗的比較次數(shù) 13 解答 1 采用順序查找的判定樹如下 do for if whi le while repeat while for if repe at if repeat do for do 題 41 圖 1 順序查找判定樹 采用折半查找的判定樹如下 for if whi le while repeat while for if repe at if repeat do for do do 題 41 圖 1 折半查找判定樹 2 根據(jù)各數(shù)據(jù)查找所需的比較次數(shù) 以及查找概率可得到平均查找長度為 ASL順序成功 1p1 2p2 3p3 4p4 5p5 0 97 ASL折半成功 1p3 2 p1 p4 3 p2 p5 1 04 ASL折半失敗 2q0 3q1 3q2 2q3 3q4 3q5 1 30 ASL順序失敗 1q0 2q1 3q2 4q3 5q4 5q5 1 07 3 由上題的計(jì)算結(jié)果可知 本題采用順序查找更好 42 分析 本題考查單鏈表的應(yīng)用 解答 1 從邏輯上可以把題中的單鏈表看成是一個(gè)循環(huán)單鏈表 因此在第一趟遍歷時(shí) 可以將單 鏈表改造成循環(huán)單鏈表 算法的基本設(shè)計(jì)思想如下 設(shè)置一個(gè)計(jì)數(shù)變量 i 初始時(shí)工作指針 p 指向第一個(gè)結(jié)點(diǎn) 故初始置 i 為 1 第一趟訪問時(shí) 令尾結(jié)點(diǎn)的指針 初始為 NULL 指向頭指針 L 注意 未改造前 單鏈表中僅有 尾結(jié)點(diǎn)的 next 域?yàn)?NULL 且改造后表中不存在 next 域?yàn)?NULL 的結(jié)點(diǎn) 如果 i 等于 m 則摘下 輸出并刪除這個(gè)計(jì)數(shù)值等于 m 的結(jié)點(diǎn) 工作指針 p 指向被刪除的下一 個(gè)結(jié)點(diǎn) 計(jì)數(shù)變量重新置為 1 如果 i 不等于 m 繼續(xù)訪問單鏈表的下一個(gè)結(jié)點(diǎn) 計(jì)數(shù)值加 1 重復(fù)過程 直到單鏈表中所有的結(jié)點(diǎn)均已刪除 即 L 指針等于 NULL 為止 2 算法的實(shí)現(xiàn)如下 typedef struct LNode 鏈表結(jié)點(diǎn)的結(jié)構(gòu)定義 ElemType data 結(jié)點(diǎn)數(shù)據(jù) struct LNode next 結(jié)點(diǎn)鏈接指針 LinkList void Loop Del LinkList 計(jì)數(shù) 初始 p 指向第 1 個(gè)元素 LNode pre p L pDel p 工作指針 pDel 指向待刪除結(jié)點(diǎn) while L L 不空則循環(huán) if p next NULL p next L 第一趟 將尾結(jié)點(diǎn)指向 L if i m 計(jì)數(shù)到第 m 個(gè)結(jié)點(diǎn) pDel p 摘下這個(gè)結(jié)點(diǎn) 14 pre next p next 斷鏈 p p next Output pDel data free pDel 輸出并銷毀 i 1 重新開始計(jì)數(shù) else 非第 m 個(gè)結(jié)點(diǎn) 則繼續(xù)計(jì)數(shù) pre p 逐鏈訪問 p p next i 計(jì)數(shù)值加 1 while L 3 在單鏈表中共有 n 個(gè)結(jié)點(diǎn) 每刪除一個(gè)結(jié)點(diǎn)需要遍歷 m 次 故總的時(shí)間復(fù)雜度為 O m n 若 m 為常量 則時(shí)間復(fù)雜度為 O n 算法的空間復(fù)雜度為 O 1 注意 解答中的單鏈表是不帶頭結(jié)點(diǎn)的 若采用帶頭結(jié)點(diǎn)的單鏈表 則算法要進(jìn)行一定的改造 留 給讀者思考 本題的思想若采用順序存儲(chǔ)結(jié)構(gòu) 則應(yīng)該如何設(shè)計(jì)算法 43 分析 本題考查浮點(diǎn)數(shù)的表示與運(yùn)算 解答 1 float 型變量在計(jì)算機(jī)中都被表示成 IEEE754 單精度格式 X 68 1000100 2 1 0001 26 符號位為 1 階碼為 127 6 128 5 1000 0101 2 尾數(shù)為 1 0001 所以小數(shù)部分為 000 1000 0000 0000 0000 0000 合起來整個(gè)浮點(diǎn)數(shù)表示為 1 1000 0101 000 1000 0000 0000 0000 0000 寫成十六進(jìn)制為 C2880000H Y 8 25 1000 01 2 1 00001 23 符號位為 1 階碼為 127 3 128 2 1000 0010 2 尾數(shù)為 1 00001 所以小數(shù)部分為 000 0100 0000 0000 0000 0000 合起來整個(gè)浮點(diǎn)數(shù)表示為 1 1000 0010 000 0100 0000 0000 0000 0000 寫成十六進(jìn)制為 C1040000H 因此 寄存器 A 和 B 的內(nèi)容分別為 C2880000H C1040000H 2 兩個(gè)浮點(diǎn)數(shù)相加的步驟如下 對階 Ex 10000101 Ey 10000010 則 Ex Ey 補(bǔ) Ex 補(bǔ) Ey 補(bǔ) 10000101 01111110 00000011 Ex大于 Ey 所以對 y 進(jìn)行對階 對階后 y 0 00100001 26 尾數(shù)相加 x 的尾數(shù)為 1 000 1000 0000 0000 0000 0000 y 的尾數(shù)為 0 001 0000 1000 0000 0000 0000 用原碼加法運(yùn)算實(shí)現(xiàn) 兩數(shù)符號相同 做加法 結(jié)果為 1 001 1000 1000 0000 0000 0000 即 x 加 y 的結(jié)果為 1 001 1000 1 26 所以符號位為 1 尾數(shù)為 001 1000 1000 0000 0000 0000 階碼 為 127 6 128 5 即 1000 0101 合起來為 1 1000 0101 001 1000 1000 0000 0000 0000 轉(zhuǎn)換為十六進(jìn)制 形式為 C2988000H 所以 C 寄存器中的內(nèi)容是 C2988000H 3 兩個(gè)浮點(diǎn)數(shù)相減的步驟同加法 對階的結(jié)果也一樣 只是尾數(shù)相減 尾數(shù)相減 x 的尾數(shù)為 1 000 1000 0000 0000 0000 0000 y 的尾數(shù)為 0 001 0000 1000 0000 0000 0000 用原碼減法運(yùn)算實(shí)現(xiàn) 兩數(shù)符號相同 做減法 符號位 取大數(shù)的符號 負(fù)數(shù) 所以為 1 數(shù)值部分 大數(shù)加小數(shù)負(fù)數(shù)的補(bǔ)碼 1 000 1000 0000 0000 00