【正文】 （ 2）分別計(jì)算等概率情況下，查找成功和查找不成功的平均查找長度。（ turn==0）） 臨界區(qū)： Flag[0]=FALSE。 ture=1 While （ flag[1]amp。局域網(wǎng) 1 和 局域網(wǎng) 2 的地址可以聚合為 ，而 R2 去往局域網(wǎng) 1 和局域網(wǎng) 2 都是同一條路徑。默認(rèn)路由在某些時(shí)候非常有效，當(dāng)存在末梢網(wǎng)絡(luò)時(shí)，默認(rèn)路由會(huì)大大簡化路由器的配置，減輕管理員的工作負(fù)擔(dān)，提高網(wǎng)絡(luò)性能。 填寫互聯(lián)網(wǎng)路由。接口填寫 E2。由于局域網(wǎng) 1 是直接連接到路由器 R1 的 E1 口上的，因此，下一跳地址填寫直接路由（ Direct）。 所以劃分的兩個(gè)網(wǎng)段是： 。 該網(wǎng)絡(luò)要?jiǎng)澐譃閮蓚€(gè)子網(wǎng)，每個(gè)子網(wǎng)要 120 臺(tái)主機(jī)， 因此主機(jī)位數(shù) X 應(yīng)該滿足下面三個(gè)條件： X8，因?yàn)槭窃谥鳈C(jī)號(hào)位長為 8 位的網(wǎng)絡(luò)進(jìn)行劃分，所以 X 一定要小于 8 位。本題中網(wǎng)絡(luò)地址位數(shù)是 24，由于 IP 地址是 32 位，因此其主機(jī)號(hào)部分就是 8 位。 25A5H： P=2，訪問快表，因第一次訪問已將該頁號(hào)放入快表，因此花費(fèi) 10ns 便可合成物理地址，訪問主存 100ns，共計(jì) 10ns+100ns=110ns。 end. Parend. 46. （ 1）根據(jù)頁式管理的工作原理，應(yīng)先考慮頁面大小，以便將頁 號(hào)和頁內(nèi)位移分解出來。 Geteven()。 Countodd():=countodd()+1。 V(mutex)。 P(mutex)。因?yàn)橹袛喾?wù)程序包含 18 條指令，中斷服務(wù)的 其他開銷相當(dāng)于 2 條指令的執(zhí)行時(shí)間，且執(zhí)行每條指令平均需 5 個(gè)時(shí)鐘周期，所以， 1 秒內(nèi)用于中斷 的時(shí) 鐘周期數(shù)為 （ 18+2） 5 104= 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%=% 時(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 S1 控制 P1 與 P2 之間的同步； S2 控制 P1 與 P3 之間的同步； empty 控制生產(chǎn)者與消費(fèi)者 之間的同步； mutex 控制進(jìn)程間互斥使用緩沖區(qū)。 //如果 ik,則 p 也往后移 } if(p==list)return 0。 i=1。用整型變量 i 表示當(dāng)前遍 歷了多少節(jié)點(diǎn)，當(dāng) ik 時(shí)，指針 p 隨著每次遍歷，也向前移動(dòng)一個(gè)節(jié) 點(diǎn)。例如，對于下圖所示的帶權(quán)圖，如果按照題中的原則， 從 A 到 C 的最短路徑為 A→ B→ C，事實(shí)上其最短路徑為 A→ D→ C。 一個(gè) TCP 連接總是以 1KB 的最大段發(fā)送 TCP 段，發(fā)送方有足夠多的數(shù)據(jù)要發(fā)送。 ：在剛建立連接時(shí)，將擁塞窗口的大小初始化為該連接所需的最大連接數(shù)據(jù)段的長度值，并發(fā)送一個(gè)最大長度的數(shù)據(jù)段（當(dāng)然必須是接收窗口允許的）。 例如，序列號(hào)等于前一個(gè)報(bào)文段的序列號(hào)與前一個(gè)報(bào)文段中數(shù)據(jù)字節(jié)的數(shù)量之和。 在一個(gè)采用 CSMA/CD 協(xié)議的網(wǎng)絡(luò) 中，傳輸介質(zhì)是一根完整的電纜，傳輸速率為 1Gbps,電纜中的信號(hào)傳播速度是 200 000km/s。每個(gè)站在發(fā)送數(shù)據(jù)幀之前，首先要進(jìn)行載波監(jiān)聽，只有介質(zhì)空閑時(shí)，才允許發(fā)送幀。但這個(gè)目標(biāo) MAC 地址是如何獲得的呢？它就是通過地址解析協(xié)議獲得的。 PDU 地址是 (目的物理地址 )。若帶寬 B=3000Hz，則 Rmax≈30kbps。 奈奎斯特定理描述了有限帶寬、無噪聲信道的最大數(shù)據(jù)傳輸速率與信道帶寬的關(guān)系。 自下而上 方法的一般從檢查 物理層 開始。 設(shè)文件 F1 的當(dāng)前引用計(jì)數(shù)值為 1，先建立 F1 的符號(hào)鏈接（軟鏈接）文件 F2，再建立 F1的硬鏈接文件 F3，然后刪除 F1?，F(xiàn)在一個(gè)磁道訪問請求序列為 35， 45， 12， 68， 110， 180， 170， 195，采用 SCAN 調(diào)度（電梯調(diào)度）算法得到的磁道訪問序列是： 110,170,180,195,68,45,35,12。 調(diào)度 (電 梯調(diào)度 )算法 : 電梯調(diào)度算法基于日常生活中的電梯工作模式：電梯保持按一個(gè)方向移動(dòng)，直到在那個(gè)方向上沒有請求為止，然后改變方向。表中每一欄目指出文件信息所在的邏輯塊號(hào)和與之對應(yīng)的物理塊號(hào)。 優(yōu)點(diǎn)：簡單 。 時(shí)間片輪轉(zhuǎn)調(diào)度法 :以先來后到的次序 +時(shí)間片輪轉(zhuǎn) 。 微程序控制器，硬布線控制器的特點(diǎn) 是 指令執(zhí)行速度快，指令功能的修改和擴(kuò)展難 。這就是說一條指令取出階段（通常為取指）需要一個(gè) CPU 周期時(shí)間。若某轉(zhuǎn)移指令所在主存地址為 2022H， 相對位移量字段的內(nèi)容為 06H，則該轉(zhuǎn)移指令成功轉(zhuǎn)移后的目標(biāo)地址是 (2022H) 相對尋址 :以當(dāng)前程序計(jì)數(shù)器 pc 的內(nèi)容為基址，加上指令給出的一字節(jié)補(bǔ)碼數(shù)（偏移量）形成新的 pc 值的尋址方式稱為相對尋址。每個(gè)主存塊大小為 32 字節(jié)，按字節(jié)編址。 (2)讀寫存儲(chǔ)器 (RAM):既能讀出又能寫入的存儲(chǔ)器。 特點(diǎn)是容量大，可存放大量的程序和數(shù)據(jù)，但速度慢。由 靜態(tài) MOS 存儲(chǔ)器構(gòu)成。 :(1)隨機(jī)存取存儲(chǔ)器 RAM； (2)順序存儲(chǔ)器 SAM； (3)直接存取存儲(chǔ)器 DAM。 雙符號(hào)位判溢 ：加，減后。若有兩個(gè)數(shù) X=2^7*29/32， Y=2^5*5/8,則用浮點(diǎn)加法計(jì)算 X+Y 的最終結(jié)果是發(fā)生溢出 浮點(diǎn)數(shù) 表示：小數(shù)點(diǎn)的位置可以在一定范圍內(nèi)浮動(dòng)。 D ：十進(jìn)制數(shù)。諾依曼計(jì)算機(jī)中 指令和數(shù)據(jù) 均以二進(jìn)制形式存放在存儲(chǔ)器中， CPU 區(qū)分它們的依據(jù)是 指令周期的不同階段 。 快速排序基本思想 ： 取 R[1..n]中任一記錄作為 “樞軸 ”，一趟排序之后樞軸的值均小于 “樞軸 ”左邊的值，樞軸右邊的值均大于 “樞軸 ”的值。 簡單選擇排序基本思想 ： 第一趟在 R[1..n]中選最小的，與 R[1]交換 第二趟在 R[2..n]中選最小的，與 R[2]交換， 依次類推，進(jìn)行 n1 次選擇后，整個(gè)文件有序。 當(dāng)向一個(gè)小根堆插入一個(gè)具有最小值的元素時(shí) ,該元素需要逐層 向上 調(diào)整 ,直到被調(diào)整到 堆頂 位置為止。 由堆的定義可知，若一棵完全二叉樹是堆，則該樹中以 每個(gè)結(jié)點(diǎn)為根的子樹也都是一個(gè)堆。 頂點(diǎn)的度 定義：與定點(diǎn) v 相關(guān)聯(lián)的邊數(shù) (每個(gè)環(huán)計(jì)算兩次 )。 完全二叉樹 ：若對滿二叉樹的結(jié)點(diǎn)從上到下從左到右進(jìn)行編號(hào)，則深度為 k 且有 n 個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為 k 的滿二叉樹的編號(hào)從 1 到 n 一一對應(yīng)時(shí)，稱為完全二叉樹。因此，平衡樹中每個(gè)結(jié)點(diǎn)的平衡因子只能是 0 或 1。 S 和隊(duì)列 Q 的初始狀態(tài)均為空 ,元素 abcdefg 依次進(jìn)入棧 S。 隊(duì)列 的定義：隊(duì)列是允許在一端進(jìn)行插入而在另一端進(jìn)行刪除的線性表。 請給出 R1 的路由表，使其明確包括到局域網(wǎng) 1 的路由、局域網(wǎng) 2 的路由、域名服務(wù)器的主機(jī)路由和 互聯(lián)網(wǎng)的路由。 47．（ 9 分）某公司網(wǎng)絡(luò)拓?fù)鋱D如下圖所示，路由器 R1 通過接口 E E2 分別連接局域網(wǎng) 局域網(wǎng) 2， 通過接口 L0 連接路由器 R2，并通過路由器 R2 連接域名服務(wù)器與互聯(lián)網(wǎng)。 頁面大小為 4KB，一次內(nèi)存的訪問時(shí)間是 100ns，一次快表（ TLB）的訪問時(shí)間是10ns，處理一次缺頁的平均時(shí)間為 108ns（已含更新 TLB 和頁表的時(shí)間），進(jìn)程的駐留集大小固定為 2，采用最近最少使用置換算法（ LRU）和局部淘汰策略。P1 每次用 produce（）生成一個(gè)正整數(shù)并用 put（）送入緩沖區(qū)某一空單元中；P2 每次用 getodd（）從該緩沖區(qū)中取出一個(gè)奇數(shù)并用 countodd（）統(tǒng)計(jì)奇數(shù)個(gè)數(shù)； P3 每次用 geteven（）從該緩沖區(qū)中取出一個(gè)偶數(shù)并用 counteven（）統(tǒng)計(jì)偶數(shù)個(gè)數(shù)。假設(shè) MAR的輸出一直處于使能狀態(tài)。 （ 1）在中斷方式下， CPU 用于該外設(shè) I/O 的時(shí)間占整個(gè) CPU 時(shí)間的百分比是多少？ （ 2）當(dāng)該外設(shè)的數(shù)據(jù)傳輸率達(dá)到 5MB/s 時(shí)，改用 DMA 方式傳送數(shù)據(jù)。要求： （ 1） 描述算法的基本設(shè)計(jì)思想 （ 2） 描述算法的詳細(xì)實(shí)現(xiàn)步驟 （ 3） 根據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟，采用程序設(shè)計(jì)語言描述算法（使用 C 或 C++或 JAVA 語言實(shí)現(xiàn)），關(guān)鍵之處請給出簡要注釋。 請問上述方法能否求得最短路徑？若該方法可行，請證明之；否則，請舉例說明。當(dāng)擁塞窗口為 16KB 時(shí)發(fā)生了超時(shí)，如果接下來的 4 個(gè) RTT（往返時(shí)間）時(shí)間 內(nèi)的 TCP 段的傳輸都是成功的，那么當(dāng)?shù)?4 個(gè) RTT 時(shí)間內(nèi)發(fā)送的所有 TCP 段都得到肯定應(yīng)答時(shí)，擁塞窗口大小是 A． 7KB B. 8KB C. 9KB D. 16KB 客戶和服務(wù)器間傳遞 FTP 命令時(shí)，使用的連接是 A．建立在 TCP 之上的控制連接 B. 建立在 TCP 之上的數(shù)據(jù)連接 C. 建立在 UDP 之上的控制連接 D. 建立在 UDP 之上的數(shù)據(jù)連接 二． 綜合應(yīng)用題?，F(xiàn)有一個(gè)磁道訪問請求序列為 35， 45， 12， 68， 110， 180， 170， 195，采用 SCAN 調(diào)度（電梯調(diào)度）算法得到的磁道訪問序列是 A． 110， 170， 180， 195， 68， 45， 35， 12 ， 68， 45， 35， 12， 170， 180， 195 ， 170， 180， 195， 12， 35， 45， 68 ， 35， 45， 68， 110， 170， 180， 195 ，文件訪問控制信息存儲(chǔ)的合理位置是 A．文件控制塊 31．設(shè)文件 F1 的當(dāng)前引用計(jì)數(shù)值為 1，先建立 F1 的符號(hào)鏈接（軟鏈接）文件 F2，再建立 F1 的硬鏈接文件 F3，然后刪除 F1。注意問的如果是“不會(huì)發(fā)生死鎖的最大值”就選 B。 現(xiàn)要用 2K 8 位的 ROM 芯片和 4K 4 位的 RAM 芯片來設(shè)計(jì)該存儲(chǔ)器，則需要上述規(guī)格的ROM 芯片數(shù)和 RAM 芯片數(shù)分別是 A． 15 B． 15 C． 30 D． 30 16 位，主存按字節(jié)編址，轉(zhuǎn)移指令采用相對尋址，由兩個(gè)字節(jié)組成，第一字節(jié)為操作碼字段，第二字節(jié)為相對位移量字段。設(shè)浮點(diǎn)數(shù)的階碼和尾數(shù)均采用補(bǔ)碼表示，且位數(shù)分別為 5 位和 7 位（均含 2 位符號(hào)位）。若遍歷后的結(jié)點(diǎn)序列為 3， 1， 7， 5， 6， 2， 4，則其遍歷方式是 A． LRN ，滿足平衡二叉樹定義的是 6 層（設(shè)根為第 1 層）有 8 個(gè)葉結(jié)點(diǎn)，則完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多是 A． 39 ，若在二叉樹中，結(jié)點(diǎn) u 是結(jié)點(diǎn) v 的父結(jié)點(diǎn)的父結(jié)點(diǎn)，則在原來的森林中， u 和 v 可能具有的關(guān)系是 I．父子關(guān)系 關(guān)系 III. u 的父結(jié)點(diǎn)與 v 的父結(jié)點(diǎn)是兄弟關(guān)系 II 和 II 和 III 、 II 和 III ，正確的是 I．所有頂點(diǎn)的度之和為偶數(shù) 1 1 I B. 只有 II 和 II 和 III ，不符合 m 階 B 樹定義要求的是 A．根節(jié)點(diǎn)最多有 m 棵子樹 C．各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列 5， 8， 12， 19， 28， 20， 15， 22 是小根堆（最小堆），插入關(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， 12， 5， 20， 15， 22， 28， 19 D. 3， 12， 5， 8， 28， 20， 15， 22， 19 11， 12， 13， 7， 8， 9， 23， 4， 5 是采用下列 排序方法之一得到的第二趟排序后的結(jié)果，則該排序算法只能是 A．起泡排序