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

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

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

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

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

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

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

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

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

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

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

11、定點小數(shù)的表示范圍是 -1 1-2 '（n'1），故被除數(shù)的絕對值應小于等于除數(shù)的絕對值，否則結(jié)果會溢出；此外應避免被除數(shù)為0，因為此時結(jié)果一定為 0，這個除法沒有意義，浪費了機器時間。15. 已知Cache命中率H=0.98，主存比Cache慢4倍，已知主存儲取周期為 200ns，平均訪問時間是 A125ns B75ns C55ns D53ns分數(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位機的地址碼為 1 6位，主存按字節(jié)編址，該機所允許的最大

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

30、正確答案：(各個字母對應的編碼為：A 011B 00C 10D 0101E 0100F 11要進行壓縮存儲，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) .若這段正文開始部分的二進制編碼序列為：，請按(1)的哈夫曼編碼將其譯為正文。(分數(shù)：3.33 ) 正確答案：(給出的序列是：，將其拆分成字母對應的編碼。011 ： A; 00： B; 0100： E; 10： E; 11 ：

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

32、st &Lb)/含頭結(jié)點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ù)：3.33 )正確答案：(遍歷鏈表

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

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

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

36、。已知Cache的存取速度為10ns,主存的存取速度為 60ns，磁盤的存取速度為12ms 該計算機的時鐘周期為 10ns。如果指令和數(shù)據(jù)的提取均命中Cache，指令的執(zhí)行需要1個時鐘周期。Cache采用的是直接映射并使用寫回策略。在Cache中平均50%勺塊是修改過的。對于主存，同樣采用寫回策略，主存中平均 30%的頁面已經(jīng)被修改。我們假定指令在Cache和主存中的命中率均為 95%而數(shù)據(jù)在Cache和主存中的命中率為 90%我們還知道 一般情況下35%的指令存取數(shù)據(jù)，求這種情況下的最大 CPI。該題必須寫出計算過程，并對每一步作必要的 說明，否則不給分。分數(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ù)所耗費的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)于分頁系統(tǒng)，回答下列問題：(分數(shù)： 9.99 )(1) . 在頁表中，哪些

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