考研計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合-44

1、考研計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合 -44（ 總分： 148.97 ，做題時(shí)間： 90 分鐘 ）一、 單項(xiàng)選擇題 （ 總題數(shù)： 40，分?jǐn)?shù)： 80.00）1. 在具有n個(gè)結(jié)點(diǎn)的順序表，算法的時(shí)間復(fù)雜度是 0（1）的操作是A. 訪問(wèn)某個(gè)結(jié)點(diǎn)B .插入一個(gè)新結(jié)點(diǎn)C.刪除一個(gè)已經(jīng)存在的結(jié)點(diǎn)D 將順序表從大到小排序（分?jǐn)?shù)： 2.00 ）A. VB.C.D.解析：解析順序表是隨機(jī)存取結(jié)構(gòu)，因此時(shí)間復(fù)雜度為 0（1）;選項(xiàng)B和C插入和刪除都需要移動(dòng)元素,時(shí)間復(fù)雜度為0（n）;選項(xiàng)D是排序問(wèn)題，時(shí)間復(fù)雜度是0（n）0（）。2. 若線性表最常用的運(yùn)算是查找第 i 個(gè)元素及其前驅(qū)的值，則下列存儲(chǔ)方式最節(jié)省時(shí)間的是 。A

2、. 單鏈表B 雙鏈表C 單循環(huán)鏈表D 順序表（分?jǐn)?shù)： 2.00 ）A.B.C.D. V解析： 解析 線性表中常用的操作是取第 i 個(gè)元素，所以應(yīng)選擇隨機(jī)存取結(jié)構(gòu)，即順序表，同時(shí)在順序表 中查找第 i 個(gè)元素的前驅(qū)也很方便。單鏈表和單循環(huán)鏈表既不能實(shí)現(xiàn)隨機(jī)存取，查找第i 個(gè)元素的前驅(qū)也不方便，雙鏈表雖然能快速查找第 i 個(gè)元素的前驅(qū)，但不能實(shí)現(xiàn)隨機(jī)存取。3. 已知循環(huán)隊(duì)列存儲(chǔ)在一維數(shù)組A0，n-1中，且隊(duì)列非空時(shí)front和rear。分別指向?qū)︻^和隊(duì)尾。若初始時(shí)隊(duì)列為空，且要求第一個(gè)進(jìn)入隊(duì)列的元素存儲(chǔ)在 A0 處，則初始時(shí) front ，和 rear 的值分別為A. 0，0 B . 0，n-1

3、C . n-1，0 D . n-1， n-1（分?jǐn)?shù)： 2.00 ）A.B. VC.D.解析： 解析 在隊(duì)列中插入元素時(shí)，只能在隊(duì)尾進(jìn)行操作。 rear 指針指向隊(duì)尾元素，因此插入時(shí)，要先 將 rear 指針向后移動(dòng)一個(gè)， 然后再將元素插入數(shù)組中。 如果要使得第一個(gè)進(jìn)入隊(duì)列的元素存儲(chǔ)在 A0 處， rear 指針初始值應(yīng)該為 n-1 。而插入第一個(gè)元素之后， front 指針不變， 隊(duì)尾指針要指向隊(duì)尾元素。 因此， rear 指針初始值應(yīng)該為 n-1 ， front 指針為 0。4. 某二叉樹的高度為 50，樹中只有度為 0和度為 2的結(jié)點(diǎn)，那么此二叉樹中所包含的結(jié)點(diǎn)數(shù)最少為 。A88 B90

4、C99 D100分?jǐn)?shù)： 2.00 ）A.B.D.解析：解析除根結(jié)點(diǎn)層只有1個(gè)結(jié)點(diǎn)外，其他各層均有兩個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)總數(shù)=2X（50 -1）+仁995. 在線索化二叉樹中，t所指結(jié)點(diǎn)沒(méi)有左子樹的充要條件是 。A. t- > left=NULL B . t- > ltag=1C. t- > ltag=1 且 t- > left=NULL D .以上都不對(duì)（分?jǐn)?shù)：2.00 ）A.B. VC.D.解析：解析線索二叉樹中某結(jié)點(diǎn)是否有左孩子，不能通過(guò)左指針域是否為空來(lái)判斷，而要判斷左標(biāo)志是 否為1。6. 在含有15個(gè)結(jié)點(diǎn)的平衡二叉樹上，查找關(guān)鍵字為28（存在該結(jié)點(diǎn)）的結(jié)點(diǎn)，則依次比較的

5、關(guān)鍵字有可能是。A. 30. 36 B. 38， 48， 28C. 48，18，38，28 D. 60，30，50，40，38，36（分?jǐn)?shù)：2.00 ）A.B.C. VD.解析：解析設(shè)m表示深度為h的平衡二叉樹中含有的最少結(jié)點(diǎn)數(shù)，有n°=0，m=1，m=2；計(jì)算的公式為：nh=nh+6-2+1 ；n3=n2+m+1=4；帀=隹+隹+1=7；壓=皿+壓+1=12；n6=n5+n4+1=20> 15。也就是說(shuō)，高度為6的平衡二叉樹的最少有 20個(gè)結(jié)點(diǎn)，因此15個(gè)結(jié)點(diǎn)的平衡二叉樹的高度為5,而最小葉子結(jié)點(diǎn)的層數(shù)為3，所以選項(xiàng)D錯(cuò)誤。如下圖所示：A在查找30后，指針應(yīng)該指向左孩子，而不

6、是右孩子；B與A存在同樣的問(wèn)題，因而 A B錯(cuò)誤。而C選項(xiàng)的查找路徑，如下圖所示：7. 以下關(guān)于圖的說(shuō)法正確的是 。I. 一個(gè)有向圖的鄰接表和逆鄰接表中的結(jié)點(diǎn)個(gè)數(shù)一定相等H.用鄰接矩陣存儲(chǔ)圖，所占用的存儲(chǔ)空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無(wú)關(guān) 山無(wú)向圖的鄰接矩陣一定是對(duì)稱的，有向圖的鄰接矩陣一定是不對(duì)稱的a.i，h B. n，m C.i，m D .僅有 u（分?jǐn)?shù):2.00 ）A. VB.C.D.解析：解析說(shuō)法I是正確的，鄰接表和逆鄰接表的區(qū)別僅在于岀邊和入邊，邊表的結(jié)點(diǎn)個(gè)數(shù)都等于有向 圖中的邊的個(gè)數(shù)。說(shuō)法H是正確的，鄰接矩陣的空間復(fù)雜度為0（），與邊的個(gè)數(shù)無(wú)關(guān)。說(shuō)法山是錯(cuò)誤的，有向圖的

7、鄰接矩陣不一定是不對(duì)稱的，例如，有向完全圖的鄰接矩陣就是對(duì)稱的。8. 存在一個(gè)由8個(gè)結(jié)點(diǎn)組成的圖，結(jié)點(diǎn)從 07編號(hào)，圖中有13條有向邊，分別是：0-7 0-1 1-4 1-6 2-33-4 4-2 5-2 6-0 6-3 6-5 7-1 7-3，下面選項(xiàng)中哪個(gè)是該圖的強(qiáng)連通分量 。A. 0-1-4 B . 3-5-6 C . 0-1-6-7 D . 1-4-3（分?jǐn)?shù)：2.00 ）A.B.C. VD.解析：解析先畫出圖，即可得出答案。9. 有一個(gè)長(zhǎng)度為12的有序表，按二分查找法對(duì)該表進(jìn)行查找，在表內(nèi)各元素等概率情況下，查找失敗時(shí)所需的平均比較次數(shù)是 。A. 37/12 B . 62/13 C .

8、 39/12 D . 49/13（分?jǐn)?shù)：2.00 ）A.B. VC.D.13個(gè)外結(jié)點(diǎn)，如下圖所示:解析：解析長(zhǎng)度為12的折半查找判定樹中有對(duì)于長(zhǎng)度為12的有序表，折半查找失敗時(shí)的平均查找長(zhǎng)度為：ASL=（4X 3+5X 10）/13=62/1310. 通過(guò)一趟排序，將待排序記錄分割成獨(dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，再分別對(duì)這兩部分記錄進(jìn)行下一趟排序，以達(dá)到整個(gè)序列有序，這種排序算法稱作。A. 直接插入排序B 基數(shù)排序C 快速排序D 歸并排序（分?jǐn)?shù)：2.00 ）A.B.C. VD.解析：解析題干中描述的是快速排序的過(guò)程。11. 數(shù)據(jù)序列F=2，1，4, 9，8，1

9、0, 6，20只能是下列排序算法中 的兩趟排序后的結(jié)果。A. 快速排序B 胃泡排序C 選擇排序D 插入排序（分?jǐn)?shù)： 2.00 ）A. VB.C.D.解析： 解析 對(duì)于后三種排序方法，兩趟排序后，序列的首部或尾部的兩個(gè)元素應(yīng)是有序的兩個(gè)極值，而 給定的序列不滿足。12. 在計(jì)算機(jī)的不同發(fā)展階段，操作系統(tǒng)最先出現(xiàn)在 。A. 第一代計(jì)算機(jī)B 第二代計(jì)算機(jī)C 第三代計(jì)算機(jī)D 第四代計(jì)算機(jī)（分?jǐn)?shù)： 2.00 ）A.B.C. VD.解析： 解析 根據(jù)計(jì)算機(jī)發(fā)展的歷史劃分，在硬件方面，第三代計(jì)算機(jī)的邏輯元件與存儲(chǔ)器均由集成電路 實(shí)現(xiàn)；在軟件方面，操作系統(tǒng)日益成熟。故選擇選項(xiàng)C。13. 浮點(diǎn)加減運(yùn)算結(jié)果滿足

10、時(shí)，應(yīng)作“機(jī)器零”處理。A. 尾數(shù)為“全0” B 階碼上溢 C 階碼下溢D . A或者C（分?jǐn)?shù)： 2.00 ）A.B.C.D. V解析： 解析 當(dāng)尾數(shù)為“全 0”時(shí)，不論階碼為何值，該浮點(diǎn)數(shù)真值都為0，應(yīng)作“機(jī)器零”處理；當(dāng)階碼下溢時(shí)，說(shuō)明浮點(diǎn)數(shù)的真值小于該機(jī)可以表示的最小值，也應(yīng)作“機(jī)器零”處理，故選D。14. 補(bǔ)碼定點(diǎn)小數(shù)除法中，被除數(shù)和除數(shù)應(yīng)滿足 。A. 0<|被除數(shù)| <|除數(shù)| B 0< |被除數(shù)| <|除數(shù)|C. 0< |除數(shù)I <|被除數(shù)I D 0< |被除數(shù)I <|除數(shù)I（分?jǐn)?shù)： 2.00 ）A.B. VC.D.解析：解析n位補(bǔ)碼

11、定點(diǎn)小數(shù)的表示范圍是 -1 1-2 '（n'1），故被除數(shù)的絕對(duì)值應(yīng)小于等于除數(shù)的絕對(duì)值，否則結(jié)果會(huì)溢出；此外應(yīng)避免被除數(shù)為0，因?yàn)榇藭r(shí)結(jié)果一定為 0，這個(gè)除法沒(méi)有意義，浪費(fèi)了機(jī)器時(shí)間。15. 已知Cache命中率H=0.98，主存比Cache慢4倍，已知主存儲(chǔ)取周期為 200ns，平均訪問(wèn)時(shí)間是 A125ns B75ns C55ns D53ns分?jǐn)?shù)： 2.00 ）A.B.C.D. V解析：解析R=TTc=4; Tc=T/4=50ns ; Ta=Tc/E=X4 - 3X0.98=50 xi.06=53ns。16. 某 8位機(jī)的地址碼為 1 6位，主存按字節(jié)編址，該機(jī)所允許的最大

12、主存空間是 A16KB B24KB C48KB D64KB（分?jǐn)?shù)： 2.00 ）A.B.C.D. V解析：解析內(nèi)存空間為：216 X8=64KB17. 下面的尋址方式中，指令中包含操作數(shù)的地址的是 A.直接尋址B 立即尋址C 寄存器尋址D 間接尋址（分?jǐn)?shù)： 2.00 ）A. VB.C.D.解析： 解析 若指令中包含著操作數(shù)的有效地址，則指令的尋址方式就是直接尋址。直接尋址時(shí)指令中地址碼字段給出的地址 A就是操作數(shù)的有效地址，即形式地址等于有效地址：EA=A由于這樣給出的操作數(shù)地址是不能修改的，與程序本身所在的位置無(wú)關(guān)，所以又叫做絕對(duì)尋址方式。而間接尋址指令中給出的地 址 A 不是操作數(shù)的地址，

13、而是存放操作數(shù)地址的主存單元的地址，簡(jiǎn)稱操作數(shù)地址的地址，EA=（A）。18. 在基址尋址方式中，若基址寄存器BR的內(nèi)容為2D3CH形式地址A的內(nèi)容為53H,則有效地址EA為A. 53H B. 2D3CH C. 2D8FH D. 803CH（分?jǐn)?shù)： 2.00 ）A.B.C. VD.解析：解析基址尋址方式下，EA=（BR）+A結(jié)合題中條件，EA=（BR）+A=2D3C+5316=2D8F6,選Co19. 中央處理器中不包括 。A.指令寄存器B .指令譯碼器C .數(shù)據(jù)寄存器D .地址寄存器（分?jǐn)?shù)： 2.00 ）A.B.C.D. V解析：解析中央處理器主要由控制器和運(yùn)算器兩部分構(gòu)成?？刂破饔沙绦蛴?jì)數(shù)

14、器PC指令寄存器IR、指令譯碼器、時(shí)序產(chǎn)生器、操作控制器組成；運(yùn)算器由算術(shù)邏輯單元ALU累加寄存器 AC數(shù)據(jù)緩沖寄存器DR狀態(tài)條件寄存器PSV組成。，第2、4段所需時(shí)間分別為，如下A.B .D .20. 某指令流水線由5段組成，第1、3、5段所需時(shí)間為圖所示那么連續(xù)輸入n條指令時(shí)的吞吐率（單位時(shí)間內(nèi)執(zhí)行的指令個(gè)數(shù)）TP是。（分?jǐn)?shù)：2.00 ）A.B. VC.D.解析：解析流水線的實(shí)際吞吐率均小于最大吞吐率。本題中還存在著瓶頸段，吞吐率將受到瓶頸段的影 響。吞吐率TP指的是流水線機(jī)器在單位時(shí)間里能流岀的任務(wù)數(shù)或結(jié)果數(shù)。如果流水線各段的經(jīng)過(guò)時(shí)間相同，流水線的最大吞吐率 。如果流水線各段的經(jīng)過(guò)時(shí)間不

15、同時(shí)，流水線的最大吞吐率，此時(shí)受限于流水線最慢子過(guò)程經(jīng)過(guò)的時(shí)間。流水線中經(jīng)過(guò)時(shí)間最長(zhǎng)的子過(guò)程瓶頸子過(guò)程。存在瓶頸段的流水線的實(shí)際吞吐率為：21. 某機(jī)采用計(jì)數(shù)器定時(shí)查詢方式來(lái)進(jìn)行總線判優(yōu)控制，共有4個(gè)主設(shè)備競(jìng)爭(zhēng)總線使用權(quán)，當(dāng)計(jì)數(shù)器初值恒為102（二進(jìn)制）時(shí)，4個(gè)主設(shè)備的優(yōu)先級(jí)順序?yàn)?。A.設(shè)備0設(shè)備1設(shè)備2設(shè)備3 B .設(shè)備2設(shè)備1 設(shè)備0設(shè)備3C. 設(shè)備2設(shè)備3設(shè)備0設(shè)備1 D .設(shè)備2=設(shè)備3=設(shè)備0=設(shè)備1（分?jǐn)?shù)：2.00 ）A.B.C. VD.解析：解析計(jì)數(shù)器初值為102，故設(shè)備2的優(yōu)先級(jí)最高，計(jì)數(shù)器值會(huì)遞增，然后返回到0,故優(yōu)先級(jí)順序?yàn)樵O(shè)備2 設(shè)備3 設(shè)備0設(shè)備1。22. CPU在響

16、應(yīng)中斷的過(guò)程中，保護(hù)現(xiàn)場(chǎng)的工作由 完成。A.中斷隱指令B .中斷服務(wù)程序C. A或B D. A和B共同（分?jǐn)?shù)：2.00 ）A.B.C.D. V解析：解析保護(hù)現(xiàn)場(chǎng)包括保護(hù)程序斷點(diǎn)和保護(hù)CPU內(nèi)部各寄存器內(nèi)容，其中，保護(hù)程序斷點(diǎn)的任務(wù)由中斷隱指令完成；而保護(hù) CPU內(nèi)部其他寄存器的任務(wù)由中斷服務(wù)程序來(lái)完成，故D為正確選項(xiàng)。23. 操作系統(tǒng)提供給用戶的接口方式包括 。A.命令方式和函數(shù)方式 B 命令方式和系統(tǒng)調(diào)用方式C.命令方式和文件管理方式 D 設(shè)備管理方式和系統(tǒng)調(diào)用方式分?jǐn)?shù)： 2.00 ）A.B.C.D.解析：V 解析 用戶利用操作系統(tǒng)管理和使用計(jì)算機(jī)，操作系統(tǒng)的提供給用戶的接口有命令接口、系統(tǒng)

17、調(diào)用以及圖形化界面等。24. 下面選項(xiàng)中，不能實(shí)現(xiàn)進(jìn)程之間通信的是 A.數(shù)據(jù)庫(kù)B 共享內(nèi)存C 消息傳遞機(jī)制D 管道（分?jǐn)?shù)： 2.00 ）A.B.C.D.解析：V 解析 本題考查進(jìn)程間的通信，進(jìn)程間的通信主要有管道、命名管道、消息傳遞、共享內(nèi)存、文件映射和套接字等。數(shù)據(jù)庫(kù)不能用于進(jìn)程間的通信。25. 為了實(shí)現(xiàn)進(jìn)程之間的同步和互斥，我們使用PV操作，從本質(zhì)上講 PV操作是A.機(jī)器指令B 系統(tǒng)調(diào)用命令C.作業(yè)控制命令 D 低級(jí)進(jìn)程通信原語(yǔ)（分?jǐn)?shù)： 2.00 ）A.B.C.D. V解析：解析從本質(zhì)上講，PV操作是一種不能夠被中斷的低級(jí)進(jìn)程通信原語(yǔ)。26. 避免死鎖是指在資源的動(dòng)態(tài)分配過(guò)程中，防止系統(tǒng)進(jìn)

18、入 狀態(tài)。A.死鎖B 安全C 不安全D 循環(huán)（分?jǐn)?shù)： 2.00 ）A.B.C.D.解析：V 解析 避免死鎖是指在資源的動(dòng)態(tài)分配過(guò)程中，用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免發(fā)生死鎖。這種方法只需事先施加較弱的限制條件，便可獲得較高的資源利用率及系統(tǒng)吞吐率，但在實(shí)現(xiàn)上有一定的困難。27. 操作系統(tǒng)對(duì)內(nèi)存的管理方式中， 不會(huì)產(chǎn)生內(nèi)部碎片。A.分頁(yè)式存儲(chǔ)管理 B 分段式存儲(chǔ)管理C.固定分區(qū)式存儲(chǔ)管理 D 段頁(yè)式存儲(chǔ)管理（分?jǐn)?shù)： 2.00 ）A.B. VC.D.解析： 解析 在內(nèi)存的管理方式中， 分段式存儲(chǔ)管理方式中只能產(chǎn)生外零頭， 不會(huì)產(chǎn)生內(nèi)零頭即內(nèi)部碎片。28. 某個(gè)頁(yè)式存儲(chǔ)管理系統(tǒng)，接收了

19、一個(gè)大小一共 7 頁(yè)的程序，其依次訪問(wèn)的頁(yè)為： 1，2，3，4，2，1，5，6, 2, 1 , 2, 3, 7。若分配給該程序的內(nèi)存空間為4頁(yè)，并一次預(yù)裝入。用 LRU調(diào)度算法，首先淘汰的頁(yè)面是 。A1 B2 C3 D4（分?jǐn)?shù)： 2.00 ）A.B.B. VD.解析：解析本題根據(jù)LRU替換算法可知，應(yīng)淘汰的為 3號(hào)頁(yè)面。29. 位示圖可用于磁盤空間的管理。設(shè)某系統(tǒng)磁盤共有 500塊，塊號(hào)從 0到 499；第 0 字的第 0 位表示第 0 塊，第 0 字的第 1 位表示第 1 塊，依次類推。若用位示圖法管理這 500塊的磁盤空間，當(dāng)字長(zhǎng)為 32 位時(shí)， 第 i 個(gè)第 j 位對(duì)應(yīng)的塊號(hào)是 。A 3

20、2i+j B 32i+j- 1 C 32i+j-32 D 32i+j-32-1分?jǐn)?shù)： 2.00 )A. VB.C.D.32 位，可以表示 32 個(gè)塊的狀態(tài)。那么，我們可以歸納解析： 解析 根據(jù)題目中的條件可知，一個(gè)字長(zhǎng)為 得出：第0塊對(duì)應(yīng)的是第0字的第0位，即32X0+0；第1塊對(duì)應(yīng)的是第0字的第1位，即32X0+1； 第 31 塊對(duì)應(yīng)的是第 0字的第 31 位，即 32X0+31；第 32 塊對(duì)應(yīng)的是第 1 字的第 0位，即 32X1+0；第 33 塊對(duì)應(yīng)的是第1 字的第 2 位，即 32X1+1；第 63 塊對(duì)應(yīng)的是第 0字的第 31 位，即 32X1+31；那么第 i 字第 j 位對(duì)應(yīng)的

21、塊號(hào)是 32Xi+j 。30. 某操作系統(tǒng)的文件管理采用直接索引和多級(jí)索引混合方式，文件索引表共有10 項(xiàng)，其中前 8項(xiàng)是直接索引項(xiàng)，第9項(xiàng)是一次間接索引項(xiàng)，第 10項(xiàng)是二次間接索引項(xiàng)。假定物理塊的大小是1K，每個(gè)索引項(xiàng)占用 4 個(gè)字節(jié)，則該文件系統(tǒng)中最大的文件可以達(dá)到 。A65536K B32768K C65793K D34000K分?jǐn)?shù)： 2.00 ）A.B.B. VD.解析：解析 多級(jí)索引的邏輯并不復(fù)雜， 二級(jí)間接索引表最多有 256 張，但是并沒(méi)有用滿。 只用了 255 張， 而且第 255 張中電沒(méi)有全部用足 256 條表項(xiàng)。計(jì)算時(shí)一定要認(rèn)真仔細(xì)，一般不會(huì)有太多變化，但是對(duì)多級(jí) 索引的

22、方法一定要掌握。 直接索引為8X1K=8K 級(jí)間接索引為（1K/4B） X1K=256K 二級(jí)間接索引為（1K/4B） X（1K/4B） X1K=64M64M的文件需要64M/1K=64K=65536個(gè)磁盤塊，所以其占用直接索引 8塊，一級(jí)間接索引256塊，二級(jí) 間接索引 65272塊，還要加上一級(jí)間接索引表 1 塊，二級(jí)間接索引表 1 塊+255塊，所以一共占有磁盤空間 65793 塊。31. 設(shè)備管理中，設(shè)備映射表（DMT）的作用是。A.管理物理設(shè)備 B 管理邏輯設(shè)備C. 實(shí)現(xiàn)輸入/輸出D .建立邏輯設(shè)備與物理設(shè)備的對(duì)應(yīng)關(guān)系（分?jǐn)?shù)： 2.00 ）A.B.C.D. V解析： 解析 本題考查設(shè)

23、備管理中，重要的數(shù)據(jù)結(jié)構(gòu)的作用。既然是映射關(guān)系，必定有源和目標(biāo)，能說(shuō)明 存在這關(guān)系的只有D選項(xiàng)。32. 在一個(gè)磁盤上，有1000個(gè)柱面，編號(hào)從0999,假設(shè)最后服務(wù)的請(qǐng)求是在磁道 345上，并且讀寫頭正 在朝磁道 0 移動(dòng)。按 FIFO 順序排列的隊(duì)列中包含了如下磁道上的請(qǐng)求： 123、874、692、475、105、376 利用SCAN調(diào)度算法滿足系統(tǒng)請(qǐng)求，那么磁盤臂必須移過(guò)的磁道的數(shù)目為 。A. 1298 B . 2013 C . 1219 D . 1967（分?jǐn)?shù)： 2.00 ）A.B.C. VD.解析：解析SCAN :移動(dòng)磁道的順序?yàn)?345、123、105、0、376、475、692、

24、874。磁盤臂必須移過(guò)的磁道的數(shù)目為 222+18+105+376+99+217+182=1 219。33. 是一個(gè)事實(shí)的網(wǎng)絡(luò)工業(yè)標(biāo)準(zhǔn)。A. TCP/IP B . OSI/ISO C . IEEE802.11 D .以上均不正確（分?jǐn)?shù)： 2.00 ）A. VB.C.D.解析： 解析 目前，眾多的網(wǎng)絡(luò)產(chǎn)品廠家都支持 TCP/IP 協(xié)議，并被廣泛用于因特網(wǎng) （Internet） 連接的所有計(jì)算機(jī)上，所以 TCP/IP 已成為一個(gè)事實(shí)上的網(wǎng)絡(luò)工業(yè)標(biāo)準(zhǔn)。34. RS232-C 接口規(guī)范所處的層次是 。A.物理層B 數(shù)據(jù)鏈路層C 網(wǎng)絡(luò)層D 傳輸層（分?jǐn)?shù)： 2.00 ）A. VB.C.D.解析：解析本題考

25、查物理層接口特性。RS232是物理層通信接口，其規(guī)范也處于物理層，答案是 Ao35. 若數(shù)據(jù)鏈路的發(fā)送窗口尺寸WT=4在發(fā)送3號(hào)幀、并接到2號(hào)幀的確認(rèn)幀后，發(fā)送方還可連續(xù)發(fā)送的幀數(shù)是 oA. 2幀B . 3幀C . 4幀D . 1幀（分?jǐn)?shù)： 2.00 ）A.B. VC.D.解析：解析本題考查滑動(dòng)窗口的機(jī)制。這里收到2號(hào)幀的確認(rèn)后，即，1 , 2號(hào)幀已經(jīng)正確接收，因此窗口向右移動(dòng) 3個(gè)幀，目前已經(jīng)發(fā)送了 3 號(hào)幀，因此可連續(xù)發(fā)送的幀數(shù)是窗口大小一已經(jīng)發(fā)送的幀數(shù)，即 4-1=3 ，因此答案是 Bo36. 一個(gè)大型跨國(guó)公司的管理者從網(wǎng)絡(luò)管理中心獲得一個(gè)A類IP地址，需要?jiǎng)澐?000個(gè)子網(wǎng),選擇子網(wǎng)號(hào)

26、的位長(zhǎng)為 oA11 B10 C12 D13（分?jǐn)?shù)： 2.00 ）A.B. VC.D.解析： 解析 該公司需要有 1000個(gè)物理網(wǎng)絡(luò)，加上主機(jī)號(hào)全 0和全 1 的兩種特殊地址，子網(wǎng)數(shù)量至少為 1002;選擇子網(wǎng)號(hào)的位長(zhǎng)為 10,可以剛來(lái)分配的子網(wǎng)最多為1024，滿足用戶要求。37. 一臺(tái)主機(jī)的IP地址為，子網(wǎng)掩碼為?，F(xiàn)在用戶需要配置該主機(jī)的默認(rèn)路由。經(jīng) 過(guò)觀察發(fā)現(xiàn)，與該主機(jī)直接相連的路由器具有如下4個(gè)IP地址和子網(wǎng)掩碼：iIP 地址：，子網(wǎng)掩碼：nIP 地址：，子網(wǎng)掩碼：山.IP 地址：，子網(wǎng)掩碼：255.0.0

27、.0wIP 地址：，子網(wǎng)掩碼：那么 IP 地址和子網(wǎng)屏蔽碼可能是該主機(jī)的默認(rèn)路由的是 a.i和u b.i和n C.i，m和w D.m和w（分?jǐn)?shù)： 2.00 ）A. VB.C.D.解析：解析本題考查默認(rèn)路由的配置，主機(jī)地址是一個(gè)標(biāo)準(zhǔn)的A類地址，其網(wǎng)絡(luò)地址為 。選項(xiàng)I的網(wǎng)絡(luò)地址為，選項(xiàng)U的網(wǎng)絡(luò)地址為 ，選項(xiàng)山的網(wǎng)絡(luò)地址為 ，選項(xiàng)W的 網(wǎng)絡(luò)地址為，因此和主機(jī)在同一個(gè)網(wǎng)絡(luò)是選項(xiàng)I和因此答案為Ao38. TCP是采用來(lái)控制流量的。A.設(shè)定擁塞窗口B . TCP首部中的接收窗口C.設(shè)定擁塞閥值 D .通過(guò)標(biāo)志位來(lái)通知（分?jǐn)?shù)：2.00 ）A.B. VC.D.解析：解析TCP

28、首部中的接收窗口是用來(lái)標(biāo)識(shí)接收方的緩沖能力的，避免快速的發(fā)送方淹沒(méi)慢速的接收 方。39. 在TCP/IP模型中，主機(jī)采用 標(biāo)識(shí)，運(yùn)行在主機(jī)上的應(yīng)用程序采用 標(biāo)識(shí)。A.端口號(hào)，主機(jī)地址 B .主機(jī)地址，IP地址C. IP地址，主機(jī)地址 D . IP地址，端口號(hào)（分?jǐn)?shù)：2.00 ）A.B.C.D. V解析：解析在TCP/IP模型中，IP地址用來(lái)標(biāo)識(shí)主機(jī)，使用IP地址來(lái)完成數(shù)據(jù)包的路由。而端口號(hào)則存在于傳輸層的頭部中，用來(lái)標(biāo)識(shí)主機(jī)上的不同進(jìn)程。40. 一個(gè)門P的用戶，發(fā)送了 LIST命令來(lái)獲取服務(wù)器的文件列表，這時(shí)候服務(wù)器應(yīng)該通過(guò) 端口來(lái)傳輸該列表。A. 21 B. 20 C . 22 D. 19（

29、分?jǐn)?shù)：2.00 ）A.B. VC.D.解析：解析FTP中數(shù)據(jù)傳輸端口是20，而文件的列表是通過(guò)數(shù)據(jù)連接來(lái)傳輸?shù)?。二、綜合應(yīng)用題（總題數(shù)：7分?jǐn)?shù)：69.00）設(shè)一段正文由字符集 A，B, C，D, E，F(xiàn)中的字母組成，這6個(gè)字母在正文中出現(xiàn)的次數(shù)分別為12，18,26， 6， 4， 34o（分?jǐn)?shù)：9.99 ）（1）.為這6個(gè)編碼設(shè)計(jì)哈夫曼編碼；（分?jǐn)?shù)：3.33 ） 正確答案：（構(gòu)造哈夫曼樹的過(guò)程，如下圖所示：根據(jù)題目中給岀的序列，依此選取其中最小的兩個(gè)組成一棵二叉樹。最后的結(jié)果為:)解析：(2) .設(shè)每個(gè)字節(jié)由8位二進(jìn)制位組成，試計(jì)算按哈夫曼編碼壓縮存儲(chǔ)這段正文共需多少個(gè)字節(jié)；(分?jǐn)?shù):3.33)

30、正確答案：(各個(gè)字母對(duì)應(yīng)的編碼為：A 011B 00C 10D 0101E 0100F 11要進(jìn)行壓縮存儲(chǔ)，B，F(xiàn)，C只需要2位，出現(xiàn)的次數(shù)分別為18，26，34； A只需要3位，出現(xiàn)的次數(shù)分別為12 ； D，E只需要4位，出現(xiàn)的次數(shù)分別為 4，6。壓縮后，共需字節(jié)數(shù)為：(2 X (18+26+34)+3 X 12+4X (4+6)/8=232/8=29)解析：(3) .若這段正文開始部分的二進(jìn)制編碼序列為：，請(qǐng)按(1)的哈夫曼編碼將其譯為正文。(分?jǐn)?shù)：3.33 ) 正確答案：(給出的序列是：，將其拆分成字母對(duì)應(yīng)的編碼。011 ： A; 00： B; 0100： E; 10： E; 11 ：

31、F; 0101 : D; 00： B。譯文序列為：ABECFDB)解析：已知一個(gè)線性表，其中的數(shù)據(jù)元素類型均為整型?，F(xiàn)有兩個(gè)單鏈表La和Lb，其中La只能存儲(chǔ)偶數(shù)而Lb只能存儲(chǔ)奇數(shù)?，F(xiàn)想利用 La和Lb來(lái)存儲(chǔ)此線性表。請(qǐng)完成以下問(wèn)題：(分?jǐn)?shù)：9.99 )(1) .給出算法的主要思想；(分?jǐn)?shù)：3.33 )正確答案：(依次遍歷線性表，如果線性表中的數(shù)據(jù)是偶數(shù)則插入La中，如果是奇數(shù)，那么就插入Lb中。)解析：(2) .寫出算法的實(shí)現(xiàn)函數(shù)；(分?jǐn)?shù)：3.33 ) 正確答案：(算法的函數(shù)如下：void decompose(LinkList &L, LinkList &La, LinkLi

32、st &Lb)/含頭結(jié)點(diǎn)LNode *p, *q;p=L- > next;La=L;La- > next=La;Lb- >next=Lb; /空的循環(huán)鏈表while(p!=NULL)q=p- > next;if(p- > data%2=0)/ 偶數(shù)則插入 La 中p- > next=La- > next;La- > next=p;else /奇數(shù)則插入Lb中p- > next=Lb- > next;Lb- > next=p;p=q;)解析：(3) .總結(jié)所用算法的時(shí)間和空間復(fù)雜度。(分?jǐn)?shù)：3.33 )正確答案：(遍歷鏈表

33、的時(shí)間復(fù)雜度為0(n)，算法實(shí)現(xiàn)過(guò)程中使用的輔助空間為常量，空間復(fù)雜度為0(1) o)解析：已知4位有效信息為1010，試根據(jù)下列要求進(jìn)行編碼。(分?jǐn)?shù)：10.00 )(1) .按配偶原則將其編碼為擴(kuò)展的海明碼，要求能發(fā)現(xiàn)兩位錯(cuò)并糾正一位錯(cuò)。(分?jǐn)?shù)：5.00 )正確答案：(題目要求能夠發(fā)現(xiàn)兩位錯(cuò)并糾正一位錯(cuò)，故需要在海明碼的基礎(chǔ)上增加 1位全局的奇偶校驗(yàn)位，此時(shí)的編碼方式稱為“擴(kuò)展的海明碼”。普通海明碼編碼計(jì)算如下：首先計(jì)算所需校驗(yàn)位的位數(shù)k，根據(jù)2k>4+k+1，可知應(yīng)取3位校驗(yàn)位，數(shù)據(jù)位與校驗(yàn)位的位置安排如下：7 6 5 4 3 2 1D3 D2D G D)C2 Ci1 0 1 0各校

34、驗(yàn)位的數(shù)值計(jì)算如下：C校驗(yàn)的比特位包含1，3, 5，7位，按配偶原則C=0?1?1=0C2校驗(yàn)的比特位包含2，3, 6，7位，按配偶原則C2=0?0?1=1G校驗(yàn)的比特位包含4，5, 6，7位，按配偶原則G=1?0?1=0綜上所述，將1010編碼擴(kuò)展為海明碼為1010010,為了能夠發(fā)現(xiàn)兩位錯(cuò)并糾正一位錯(cuò)，在最左端增加1位全局偶校驗(yàn)位C8OG=1?0?1?0?0?1?0=1故，將有效信息1010編碼擴(kuò)展的海明碼為 11010010。)解析：(2) .將其編碼為循環(huán)冗余校驗(yàn)碼，生成多項(xiàng)式G(x)=1011 o (分?jǐn)?shù)：5.00 ) 正確答案：(將待編碼的有效信息1010表示為多項(xiàng)式M(x):M(

35、x)=x 3+x=1010由于生成多項(xiàng)式 G(x)為4位，故將M(x)左移3位，得M(x) Xx 3，目的是空出3位，以便拼裝余數(shù)(校驗(yàn)位):M(x) Xx 3=x6+x4=1010000用M(x) Xx 3模2除生成多項(xiàng)式G(x):將左移后的待編碼有效信息與余數(shù)R(x)作模2加，即形成循環(huán)冗余校驗(yàn)碼：M(x) Xx 3+R(x)=1010000+011=1010011即用生成多項(xiàng)式 G(x)=1011將有效信息1010編碼，得循環(huán)冗余校驗(yàn)碼1010011o ) 解析：41. 一臺(tái)計(jì)算機(jī)有分離的數(shù)據(jù)和指令Cache。同時(shí)該計(jì)算機(jī)還采用了頁(yè)式虛擬存儲(chǔ)器技術(shù)。這里假定頁(yè)面和Cache塊具有大小相同

36、。已知Cache的存取速度為10ns,主存的存取速度為 60ns，磁盤的存取速度為12ms 該計(jì)算機(jī)的時(shí)鐘周期為 10ns。如果指令和數(shù)據(jù)的提取均命中Cache，指令的執(zhí)行需要1個(gè)時(shí)鐘周期。Cache采用的是直接映射并使用寫回策略。在Cache中平均50%勺塊是修改過(guò)的。對(duì)于主存，同樣采用寫回策略，主存中平均 30%的頁(yè)面已經(jīng)被修改。我們假定指令在Cache和主存中的命中率均為 95%而數(shù)據(jù)在Cache和主存中的命中率為 90%我們還知道 一般情況下35%的指令存取數(shù)據(jù)，求這種情況下的最大 CPI。該題必須寫出計(jì)算過(guò)程，并對(duì)每一步作必要的 說(shuō)明，否則不給分。分?jǐn)?shù)： 10.00 ) 正確答案：

37、( 分成兩種指令算：一種是需要存取數(shù)據(jù)的指令；另一種是不需要存取數(shù)據(jù)的指令。不需要存取 數(shù)據(jù)的指令：不需要考慮數(shù)據(jù)的命中和寫回。65%< (95%x 50%< 1+95%< 50%< 60ns/10ns+5%x 95%< 70%< 60ns/10ns+5%x 95%< 30%< 12ms/60ns+5%< 5% x 12ms/10ns)=6。需要存取數(shù)據(jù)的指令：需要存取數(shù)據(jù)的指令本身的 CPI 為：A=(95%< 50%< 1+95%< 50%< 60ns/10ns+5%< 95%< 70%< 60

38、ns/10ns+5%< 95%< 30%< 12ms/60ns+5%< 5%<1 2ms/10ns) 。指令需要存取的數(shù)據(jù)所耗費(fèi)的CPI：B=(90%< 50%< 1+90%< 50%< 60ns/10ns+10%< 90%< 70%< 60ns/10ns+10%< 90%< 30%< 12ms/60ns+10%< 10 %< 12ms/10ns)。最后結(jié)果為： A< 35%+B< 35%=11。 )解析：關(guān)于分頁(yè)系統(tǒng)，回答下列問(wèn)題：(分?jǐn)?shù)： 9.99 )(1) . 在頁(yè)表中，哪些

39、數(shù)據(jù)項(xiàng)是為實(shí)現(xiàn)換頁(yè)而設(shè)置的?(分?jǐn)?shù)： 3.33)正確答案： ( 在頁(yè)表中，訪問(wèn)位和修改位是為請(qǐng)求頁(yè)面調(diào)度設(shè)置的。訪問(wèn)位來(lái)跟蹤頁(yè)的使用，修改位來(lái)跟蹤 頁(yè)的寫入。 )解析：(2) . 設(shè)某系統(tǒng)為每個(gè)作業(yè)進(jìn)程分配 3 個(gè)內(nèi)存塊，某作業(yè)進(jìn)程在運(yùn)行訪問(wèn)中的軌跡為 1， 4， 3， 1， 6， 8， 1， 且每一頁(yè)都是按請(qǐng)求裝入的。 問(wèn)：先進(jìn)先出頁(yè)面置換算法(FIFO)和最近未使用頁(yè)面置換算法(LRU)下，產(chǎn)生 缺頁(yè)的次數(shù)各是多少 ?(畫出必要的數(shù)據(jù)圖 )(分?jǐn)?shù)： 3.33)正確答案： (FIFO 算法：缺頁(yè)次數(shù)是 6，具體如下表所示：頁(yè)面 14 3 1 6 811 14 3 3 6 812 1 4 4 3 683 1 1 4 36中斷 YYY YYYLRU 算法：缺頁(yè)中斷次數(shù)為 5，具體如下表所示：頁(yè)面 14 3 1 6 81114 3 1 6 812 1 4