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

1、考研計(jì)算機(jī)學(xué)科專業(yè)根底綜合 -20( 總分： 150.00 ，做題時(shí)間： 90 分鐘 )一、 單項(xiàng)選擇題 ( 總題數(shù)： 40，分?jǐn)?shù)： 80.00)1.以下有關(guān)數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的表達(dá)中，正確的選項(xiàng)是()。A .順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)B .順序存儲(chǔ)方式的優(yōu)點(diǎn)是占用存儲(chǔ)空間小，插入、刪除等操作效率高C.鏈表的每個(gè)結(jié)點(diǎn)中都恰好含有一個(gè)指針D Hash 存儲(chǔ)的根本思想是由關(guān)鍵詞的值決定數(shù)據(jù)的存儲(chǔ)地址 分?jǐn)?shù)： 2.00 A.B.C.D. “解析：順序存儲(chǔ)方式除了用于存儲(chǔ)線性結(jié)構(gòu)外，還能存儲(chǔ)數(shù)組或完全一叉樹(shù)等非線性結(jié) 構(gòu)。插入、刪除操 作時(shí)，由于要移動(dòng)大量的數(shù)據(jù)，執(zhí)行效率低，鏈表的形式有單鏈表、雙鏈表

2、和 多重鏈表，除了單鏈表外， 其他鏈表中的結(jié)點(diǎn)需要兩個(gè)以上的指針。2. 以數(shù)組 Datam+1 作為循環(huán)隊(duì)列 SQ 的存儲(chǔ)空間， front 為頭指針， rear 為隊(duì)尾指針，那么執(zhí)行出 隊(duì)操作的 語(yǔ)句是 ( ) 。A front=front+1 B front=(front+1)%mC front=(front+1)%(m+1) D rear=(rear+1)%m( 分?jǐn)?shù)： 2.00 )A.B.C. VD.解析：3. 設(shè) n、 m 為一棵二叉樹(shù)上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n 在 m 前的條件是 ( )A . n在 m右方 B . n是 m祖先 C . n在m左方 D . n是m子孫( 分?jǐn)?shù)：

3、 2.00 )A.B.C. VD.解析：中序遍歷時(shí)，先訪問(wèn)左子樹(shù)，再訪問(wèn)根結(jié)點(diǎn)。n 在 m 前，那么 n 必須在 m 的左子樹(shù)中。因此此題答案為 C。4. 前序遍歷和后序遍歷結(jié)果相同的二叉樹(shù)為()。A .只有根結(jié)點(diǎn)的二叉樹(shù)B .根結(jié)點(diǎn)無(wú)左孩子的二叉樹(shù) C.根結(jié)點(diǎn)無(wú)右孩子的二叉樹(shù)D .所有結(jié)點(diǎn)只有左子樹(shù)的二叉樹(shù)B.C.D.解析：使用特值法，排除B 、 C、 D 選項(xiàng)。5. 一個(gè)線性表為 (38 ，25，74， 63， 52，48)，假定采用H(K)=Kmod7 計(jì)算散列地址進(jìn)行散列存儲(chǔ)，假設(shè)利 用線性探測(cè)的開(kāi)放定址法處理沖突， 那么在該散列表上進(jìn)行查找的平均查找長(zhǎng)度為 ( ) ； 假設(shè)利用鏈地址

4、法處理 沖突，那么在該散列上進(jìn)行查找的平均查找長(zhǎng)度為 ( ) 。A1.5，1 B1.7 ，3/2 C 2， 4/3 D 2.3 ， 7/6( 分?jǐn)?shù)： 2.00 )A.B.C. VD.解析：假設(shè)利用線性探測(cè)的開(kāi)放定址法處理沖突，發(fā)生 0 次沖突的關(guān)鍵字有 3個(gè)，1 次沖突的 1 個(gè)， 2 次沖突 的 1 個(gè)， 3 次沖突的 1 個(gè)，因而在該散列表上進(jìn)行查找的平均查找長(zhǎng)度為ASL=(3*1+1*2+1*3+1*4)/6=2 ；假設(shè) 利用鏈地址法處理沖突，同一鏈表上有 1 個(gè)元素的線性鏈表有 2 個(gè)，有 2 個(gè)元素的線性鏈表有 2 個(gè)，因此 ASL=(4*1+2*2)/6=4/3 。6. 關(guān)于AVL

5、(平衡二叉樹(shù))，以下說(shuō)法錯(cuò)誤的選項(xiàng)是()。A .左子樹(shù)與右子樹(shù)高度差最多為1 B .插入操作的時(shí)間復(fù)雜度為 O(log n) C 平衡二叉樹(shù)是二叉排序樹(shù)中的一種D .使用平衡二叉樹(shù)的目的是為了節(jié)省空間 分?jǐn)?shù)： 2.00 A.B.C.D. V 解析：平衡二叉樹(shù)沒(méi)有節(jié)省空間，引入其目的是防止排序二叉樹(shù)左、右子樹(shù)高度失衡7. 下面關(guān)于對(duì)圖的操作的說(shuō)法不正確的選項(xiàng)是 ( ) 。A .尋找關(guān)鍵路徑是關(guān)于帶權(quán)有向圖的操作B .尋找關(guān)鍵路徑是關(guān)于帶權(quán)無(wú)向圖的操作C .連通圖的生成樹(shù)不一定是唯一的D .帶權(quán)無(wú)向圖的最小生成樹(shù)不一定是唯一的( 分?jǐn)?shù)： 2.00 )A.B. VC.D.解析：8. 在文件局部有序或

6、文件長(zhǎng)度較少的情況下，最正確的內(nèi)部排序方法是()A.直接插入排序B .冒泡排序C 簡(jiǎn)單項(xiàng)選擇擇排序 D 堆排序( 分?jǐn)?shù)： 2.00 )B.C.B. 解析：9. 以下 ( ) 是一個(gè)堆。 A19，75，34，26，97，56 B 97， 26， 34， 75， 19， 56 C19，56， 26，97，34，75 D 19， 34， 26， 97， 56， 75( 分?jǐn)?shù)： 2.00 )A.B.C.D. V解析：完全二叉樹(shù)中所有非終端結(jié)點(diǎn)的值均不大于(或不小于 ) 其左、右孩子結(jié)點(diǎn)的值， 那么此序列可稱為堆 據(jù)此，可畫(huà)出二叉樹(shù)來(lái)判斷答案為D。10. 以下有關(guān)二叉樹(shù)的描述中正確的選項(xiàng)是 ( ) 。(

7、1) 二叉樹(shù)按某種右岸序線索化后，任一結(jié)點(diǎn)均有指向其前驅(qū)和后繼的線索二叉樹(shù)的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面A .只有 B .只有 C(1) 和(2) D 以上全不對(duì)( 分?jǐn)?shù)： 2.00 )A.B. VC.D.解析：11. 某定點(diǎn)機(jī)字長(zhǎng) n 位，其中包含一位符號(hào)位。假設(shè)采用補(bǔ)碼一位乘 (Booth 算法 )實(shí)現(xiàn)乘法運(yùn)算， 那么最多需要 做 ( ) 次移位運(yùn)算。An-1 B nC n+1 D n+2 分?jǐn)?shù)： 2.00 A. VB.C.D.解析：12. 假設(shè)某浮點(diǎn)機(jī)基數(shù)為 4，尾數(shù)采用補(bǔ)碼表示，那么該浮點(diǎn)機(jī)的規(guī)格化尾數(shù)形式為( )A .最高兩位數(shù)值位與符號(hào)位相反B .最高兩位數(shù)值

8、位與符號(hào)位相同C .最高兩位數(shù)值位至少有一位與符號(hào)位相反D .最高兩位數(shù)值位至少有一位與符號(hào)位相同 分?jǐn)?shù)： 2.00 A.B.D.解析：13. 用 74181 和 74182 芯片構(gòu)成小組內(nèi)并行進(jìn)位， 小組間并行進(jìn)位， 大組間串行進(jìn)位的 32 位 ALU ， 需要 74182 芯片的片數(shù)為 ( ) 。A0 B1 C2 D3( 分?jǐn)?shù)： 2.00 )A.B.c. VD.解析： 74181 是內(nèi)部并行進(jìn)位的 4 位 ALU 芯片， 74182 是 4 位先行進(jìn)位芯片，故 4 片 74181 和 1 片 74182 可 構(gòu)成小組內(nèi)并行進(jìn)位。小組間并行進(jìn)位的 16 位 ALU ；又題目要求構(gòu)成小組內(nèi)并行

9、 進(jìn)位，大組內(nèi)串行進(jìn)位的32 位 ALU ，故只需將 2 個(gè)前述 16 位 ALU 串聯(lián)即可，共需 2 片 74182 芯片，選 C。14. 某機(jī)字長(zhǎng) 32 位，它的存儲(chǔ)容量為 256MB ，按字節(jié)編址，那么它的尋址范圍大小為 ( ) 。 A 256MB B (256-1)MBC 64MB D (64-1)MB( 分?jǐn)?shù)： 2.00 )A. VB.C.D.解析：該機(jī)存儲(chǔ)容量為256MB，又按字節(jié)編址，故其尋址范圍為0256 M-1 ,尋址空間大小為256MB 。15. 采用了虛擬存儲(chǔ)器的計(jì)算機(jī)系統(tǒng)中，邏輯地址與物理地址相比( ) 。A .兩者位數(shù)相等B .邏輯地址位數(shù)多C .物理地址位數(shù)多D .

10、無(wú)法判斷( 分?jǐn)?shù)： 2.00 )A.B. VC.C.解析：虛擬存儲(chǔ)器主要是為了解決存儲(chǔ)系統(tǒng)的容量問(wèn)題， 引入虛擬存儲(chǔ)器后， 程序員編程可使用的虛擬空 間要遠(yuǎn)大于物理內(nèi)存容量， 故邏輯地址位數(shù)要大于物理地址位數(shù)，選B。16. 以下關(guān)于 RISC 的表達(dá)中，錯(cuò)誤的選項(xiàng)是 ( ) 。A RISC 普遍采用微程序控制器B RISC 大多數(shù)指令在一個(gè)時(shí)鐘周期內(nèi)完成C RISC 的內(nèi)部通用存放器數(shù)量相對(duì) CISC 多( 分?jǐn)?shù)： 2.00 )A. VB.C.D.解析：與 CISC 相比， RISC 的特點(diǎn)是：指令數(shù)量和尋址方式少，指令格式簡(jiǎn)單，大多數(shù)指令在一 個(gè)時(shí)鐘周 期內(nèi)完成； CPU 內(nèi)部通用存放器數(shù)量

11、多； 控制器多采用硬布線邏輯， 且多采用流水 線技術(shù)， 執(zhí)行速度較快。 故 A 選項(xiàng)錯(cuò)誤。17. 以下尋址方式中，執(zhí)行速度最快的是 。A .立即數(shù)尋址 B .直接尋址C .間接尋址 D .存放器間接尋址 分?jǐn)?shù)： 2.00 A. VB.C.B. 解析：四個(gè)選項(xiàng)中，只有立即數(shù)尋址不需要訪存，故其執(zhí)行速度最快。18. CPU在響應(yīng)中斷的過(guò)程中，保護(hù)現(xiàn)場(chǎng)的工作由完成。A.中斷隱指令 B .中斷效勞程序CA 或 B 之一完成 DA 和 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

12、 內(nèi)部其他存放器的任務(wù)由中斷效勞程序來(lái)完成，故 D 為正確選項(xiàng)。19. CPU 的中斷周期前可能是 。A .取指周期B .間址周期C.執(zhí)行周期D .以上都有可能 分?jǐn)?shù)： 2.00 A.B.C. VD.解析： CPU 在一個(gè)指令周期結(jié)束，即一條指令的執(zhí)行周期結(jié)束后檢查是否有中斷請(qǐng)求，如果有那么 進(jìn)入中斷 周期，故中斷周期前只可能是執(zhí)行周期。20. 數(shù)據(jù)總線、地址總線、控制總線是根據(jù)總線 來(lái)劃分的。A .傳送內(nèi)容的不同 B .所處位置的不同C .連接部件的不同 D .所使用標(biāo)準(zhǔn)的不同 分?jǐn)?shù)： 2.00 A. VB.C.B. 解析：根據(jù)總線上傳輸內(nèi)容的不同，可將總線分為數(shù)據(jù)總線、地址總線和控制總線2

13、1. 采用DMA方式傳送數(shù)據(jù)時(shí)，每傳送一個(gè)數(shù)據(jù)要占用。A .一個(gè)指令周期B .一個(gè)機(jī)器周期C .一個(gè)存取周期D .一個(gè)時(shí)鐘周期( 分?jǐn)?shù)： 2.00 )A.B.C. VD.解析：采用 DMA 方式傳送數(shù)據(jù)時(shí)，每傳送一個(gè)數(shù)據(jù)需要占用 CPU 一個(gè)存取周期， 即在該存取周期內(nèi)，不能訪存。22. 中斷系統(tǒng)中，中斷屏蔽字的作用是 ( ) 。A .暫停對(duì)所有中斷源的響應(yīng)B .暫停對(duì)所有可屏蔽中斷源的響應(yīng)C .暫停對(duì)某些可屏蔽中斷源的響應(yīng)D .暫停對(duì)主存的訪問(wèn)( 分?jǐn)?shù)： 2.00 )A.B.C. VD.解析： CPU 通過(guò)設(shè)置中斷屏蔽字來(lái)中斷對(duì)某些可屏蔽中斷源的響應(yīng)。23. 分頁(yè)式虛擬存儲(chǔ)管理系統(tǒng)中，一般來(lái)

14、說(shuō)頁(yè)面的大小與可能產(chǎn)生缺頁(yè)中斷的次數(shù)( ) 。 A比 B 成反比C 無(wú)關(guān) D 成固定比值( 分?jǐn)?shù)： 2.00 )A.B. VC.C. 解析：頁(yè)面越小發(fā)生缺頁(yè)中斷次數(shù)的可能性越大。24. 請(qǐng)求分頁(yè)存儲(chǔ)管理方案中，如果所需的頁(yè)面不在內(nèi)存中，那么產(chǎn)生缺頁(yè)中斷，它屬于( )A .硬件故障 B .1/0 C .外D .程序中斷CPU成正中斷分?jǐn)?shù)： 2.00 )A.B.C.D. V解析：此題考查中斷的概念。25.頁(yè)式虛擬存儲(chǔ)管理的主要特點(diǎn)是()。A .不要求將作業(yè)裝入到主存的連續(xù)區(qū)域B將作業(yè)同時(shí)全部裝入到主存的連續(xù)區(qū)域C.不要求進(jìn)行缺頁(yè)中斷處理D 不要求進(jìn)行頁(yè)面置換不要求(分?jǐn)?shù)： 2.00 )A.B. V

15、C.C. 解析：此題考查頁(yè)式存儲(chǔ)的概念。26.分區(qū)分配內(nèi)存管理方式的主要保護(hù)措施是()。A .界地址保護(hù) B .程序代碼保護(hù)據(jù)保護(hù)D .棧保護(hù)C.數(shù)分?jǐn)?shù)： 2.00 )A. VB.C.B. 解析：界地址存放器來(lái)保護(hù)內(nèi)存管理方式的主要措施。27. 在存儲(chǔ)系統(tǒng)管理中，采用覆蓋與交換技術(shù)的目的是( )A .節(jié)省主存空間 B.物理上擴(kuò)充主存容量C .提高CPU效率D .實(shí)現(xiàn)主存共存分?jǐn)?shù)： 2.00 )A. VB.C.B. 解析：覆蓋和交換是虛擬上擴(kuò)充內(nèi)存的技術(shù)。28. 既考慮作業(yè)等待時(shí)間又考慮作業(yè)執(zhí)行時(shí)間的調(diào)度算法是( )A .響應(yīng)比高者優(yōu)先 B .短作業(yè)優(yōu)先 C.優(yōu)先級(jí)調(diào)度 D .先來(lái)先效勞(分?jǐn)?shù)：

16、 2.00 )A. VB.C.D.解析：響應(yīng)比 =( 等待時(shí)間 +執(zhí)行時(shí)間 ) / 執(zhí)行時(shí)間29. 以下死鎖的論述中，正確的論述是 ( ) 。A .由于產(chǎn)生死鎖的根本原因是系統(tǒng)資源缺乏，因而預(yù)防死鎖最常用方法，是根據(jù)系統(tǒng)規(guī)模，配置 足夠的系統(tǒng)資源B .由于產(chǎn)生死鎖的另一個(gè)根本原因是進(jìn)程推進(jìn)順序不當(dāng)，因而預(yù)防死鎖的常用方法， 程的推進(jìn)順序合法是使進(jìn)C .因?yàn)橹灰到y(tǒng)不進(jìn)入不平安狀態(tài)，便不會(huì)產(chǎn)生死鎖，故預(yù)防死鎖的常用方法， 是防止系統(tǒng)進(jìn)入不平安狀態(tài)D .可以通過(guò)破壞產(chǎn)生死鎖的四個(gè)必要條件之一或其中幾個(gè)方法，來(lái)預(yù)防發(fā)生死鎖( 分?jǐn)?shù)： 2.00 )A.B.C.D. V解析：A :不可能根據(jù)系統(tǒng)的規(guī)模，

17、配置足夠的系統(tǒng)資源，因?yàn)橄到y(tǒng)的資源是有限的。B :這種方法不能保證死鎖不發(fā)生，而且進(jìn)程推進(jìn)過(guò)程很復(fù)雜，實(shí)現(xiàn)合理的順序不太可能。C :系統(tǒng)進(jìn)入不平安狀態(tài)不一定會(huì)產(chǎn)生死鎖，防止系統(tǒng)進(jìn)入不平安狀態(tài)不太可能，故不是常用的方法。30.設(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=1C m=4， n=3， w=2 D m=4， n=2 ， w=3 分?jǐn)?shù): 2.00 A.B.C.D. V解析:當(dāng) 2個(gè)進(jìn)程已經(jīng)擁有 2個(gè)資源，都申請(qǐng)第 3 個(gè)資源時(shí)，導(dǎo)致死鎖 31

18、. MS-DOS 中的文件物理結(jié)構(gòu)采用 ( ) 。A .連續(xù)結(jié)構(gòu)B .鏈接結(jié)構(gòu) C .索引結(jié)構(gòu) D .哈希表 分?jǐn)?shù): 2.00 A.B. VC.D.解析:此題考查文件物理結(jié)構(gòu)的知識(shí)。32. 通過(guò)硬件和軟件的功能擴(kuò)充， 把原來(lái)獨(dú)占的設(shè)備改造成假設(shè)干用戶共享的設(shè)備， 這種設(shè)備稱為 ( ) A .系統(tǒng)設(shè)備 B .存儲(chǔ)設(shè)備 C.用戶設(shè)備 D .虛擬設(shè)備 分?jǐn)?shù): 2.00 A.B.C.D. V解析：此題考查虛擬設(shè)備的概念。33.ICMP 在 TCP/IP 協(xié)議集中屬于 ( ) 。A .數(shù)據(jù)鏈路層 B .傳輸層C.網(wǎng)絡(luò)層D .應(yīng)用層( 分?jǐn)?shù)： 2.00 )A.B.C. VD.解析： ICMP 在 TCP/

19、IP 協(xié)議集中是屬于 IP 層的，即屬于網(wǎng)絡(luò)層。34. 采用 8 種相位，每種相位各有兩種幅度的 QAM 調(diào)制方法，在 4800 波特率的信號(hào)傳輸速率下 能到達(dá)的數(shù) 據(jù)傳輸速率為 ( ) 。A 4800bps B 9600bpsC 19200bps D 38400bps 分?jǐn)?shù)： 2.00 A.B.C. VD.混合調(diào)制方法。解析： QAM 調(diào)制是一種多元制的振幅相位 QAM題目中有 8 種相位， 每種相位各有兩種幅度的調(diào)制方法，共有 16 種狀態(tài)，所以每個(gè) Baud 為 4位。由于是 4800 波特率的信號(hào)傳輸速率，因此 數(shù)據(jù)傳輸速 率是 19200bps 。35. 兩個(gè)網(wǎng)段在物理層進(jìn)行互聯(lián)時(shí)要

20、求 ()o A .數(shù)據(jù)傳輸率和數(shù)據(jù)鏈路層協(xié)議都不相同B .數(shù)據(jù)傳輸率和數(shù)據(jù)鏈路層協(xié)議都相同C.數(shù)據(jù)傳輸率相同，數(shù)據(jù)鏈路層協(xié)議可不同D .數(shù)據(jù)傳輸率可不同，數(shù)據(jù)鏈路層協(xié)議相同( 分?jǐn)?shù)： 2.00 )A.B.C. VD. 解析：數(shù)據(jù)傳輸率是物理層的重要參數(shù)，兩個(gè)網(wǎng)段在物理層進(jìn)行互聯(lián)，數(shù)據(jù)傳輸率必須相同。如果在數(shù)據(jù) 鏈路層互聯(lián)，那么要求數(shù)據(jù)鏈路層協(xié)議也相同。36. 條線路帶寬為1Mbps，往返時(shí)延為45ms，假設(shè)數(shù)據(jù)幀的大小為1000字節(jié)。假設(shè)采用停一等協(xié)議， 的數(shù)據(jù)率是 ( ) oA 15Kbps B 1.5KbpsC 151Kbps D 1510Kbps 分?jǐn)?shù)： 2.00 A.B.C. VD.解

21、析：往返時(shí)延為45ms，發(fā)送一幀的時(shí)間是8 X iooo - 1000000s。實(shí)際的數(shù)據(jù)率是8X 1000 + (8 X 1000 + 1000000+45 X 0.003)=150943(bps)151(Kbps)。37.假設(shè)數(shù)據(jù)鏈路層采用回退N滑動(dòng)窗口字而已，發(fā)送幀的序列號(hào)用7bit表示，發(fā)送窗口的最大值為 ( ) 。A7 B64 C127 D128( 分?jǐn)?shù)： 2.00 )A.B.C. VD.解析： 7 位的發(fā)送序列號(hào)，最大可以有 128 個(gè)序列，采用回退 N 幀的協(xié)議，發(fā)送窗口的最大值應(yīng) 該是最大 序列號(hào)減 1，即 127 。38. 以下地址中的 ( ) 和 匹配。A 86.33.22

22、4.123 B C 4 D ( 分?jǐn)?shù)： 2.00 )A. VB.C.D.解析：觀察地址的第二個(gè)字節(jié) 0X32=00100000 ，前綴 12位，說(shuō)明第二個(gè)字節(jié)的前 4 位在前綴中。 給出的4個(gè)地址的第二字節(jié)的前 4位分別是：0010 , 0100 , 0011和010。，故只有A是匹配的。 39. 在 TCP 連接中，如果已經(jīng)接收了 1000 字節(jié)的數(shù)據(jù)， 那么在發(fā)送回的數(shù)據(jù)包頭中， 確認(rèn)號(hào)為 ( ) A 1000 B 1001 C999 D998 分?jǐn)?shù)： 2.00 A.B. VC.D.解析：確認(rèn)號(hào)表示接下來(lái)希望接收數(shù)據(jù)的序列號(hào)，成功接收1000 字節(jié)之后， TCP 連接

23、希望接收1001 號(hào)字節(jié)，所以答案是 1001 。40. FTP客戶和效勞器間傳遞 FTP命令時(shí)，使用的連接是()。A .建立在TCP之上的控制連接B .建 立在TCP之上的數(shù)據(jù)連接 C .建立在UDP之上的控制連接D .建立在UDP之上的數(shù)據(jù)連接 分?jǐn)?shù)： 2.00 A. VB.C.D.解析：TCP 的控制連接用來(lái)傳輸控制命令，數(shù)據(jù)連接用來(lái)傳輸文件。綜合應(yīng)用題 ( 總題數(shù)： 7，分?jǐn)?shù)：70.00)但是41. 沒(méi)有m個(gè)連續(xù)單元供一個(gè)棧與隊(duì)列使用， 要求在任何時(shí) 刻它們占用的單元數(shù)量不超過(guò)且棧與隊(duì)列的實(shí)際占用單元數(shù)事先不知道， m，試寫(xiě)出上述棧與隊(duì)列的插入算法。分?jǐn)?shù)：10.00 正確答案：算法如下

24、：/定義結(jié)點(diǎn)的結(jié)構(gòu)為struct Node ElemType data; struct Node* next; / 定義棧的結(jié)構(gòu)struct Stack Node* base;Node* top ；/ 定義隊(duì)列的結(jié)構(gòu) struct Queue Node* frontNode* tail;/設(shè)m個(gè)連續(xù)單元的數(shù)組為bm，定義全局?jǐn)?shù)組static int am用以標(biāo)識(shí)m個(gè)單元中各個(gè)單元是否被占用/ai=1 表示已占用， ai=0 void In sertStackstruct stack for(i nt i=0;i< m;i+)if(ai=0)break; if(i=m)prin tf(&q

25、uot;NO SPACE/n"); return;ai=1 ；表示未被占用& S,ElemType elem)Node* P= & bi:P-> data=elem:P-> next二NULL: if(S.base=NULL)S.base=P;S.top=P:else p- > next=P; S.top=P: voidIn sertQueue(struct Queuefor(int i=0; i < m ; i+)if(ai=0)break ;if(i=m)prin tf("NO SPACE/n");return"

26、;ai=1;Node* P= & bi;P-> data=elem;P-> next=NULL:if(Q.fro nt=NULL)& Q ,elem)ElemTypeQ.fr on t=p;Q.tail二p;elseQ.tail- > next=P;Q.tail=p;解析：42. 序列的“中值記錄指的是：如果將此序列排序后，它是第n/2個(gè)記錄。試寫(xiě)出一個(gè)求中值記錄的算法。分?jǐn)?shù)：15.00 正確答案：解析算法如下:typedef structint gt ；/大于該記錄的個(gè)數(shù)int lt;/小于該記錄的個(gè)數(shù)place;int Get_Mid(int aint n

27、)place bMAXSIZE;/*對(duì)第i個(gè)元素統(tǒng)計(jì)比它大和比它小的元數(shù)的個(gè)數(shù)，分別為gt 和 It*/ for(int i=0;i < n;i+)for(i nt j=0;j< n;j+)if(aj >aEi)bi.gt+;if(aj <ai)bi.It+;int mid=0;/*找出gt值與it值最接近的元素，即為中值記錄 */int min_dif=abs(b0.gt-b0.It); for(int i=0;i<n;i+) ifabs bi.gt_bi.lt mid二i: <min_dif;return mid;解析：43. 某浮點(diǎn)機(jī)字長(zhǎng)16位，其浮點(diǎn)

28、數(shù)格式為：階碼5位含1位階符，采用補(bǔ)碼表示，尾數(shù)11位含1位數(shù)符，采用補(bǔ)碼表示，且尾數(shù)為規(guī)格化形式。X=0.1011000011 X2°,°101 , Y =0.0001100000 X2°,1000，試求X+Y，要求寫(xiě)出詳細(xì)的計(jì)算過(guò)程。假設(shè)浮點(diǎn)加減過(guò)程中階碼和尾數(shù)采用雙符號(hào)位，并使用“0舍1入法進(jìn)行舍入。分?jǐn)?shù)：13.00 正確答案：寫(xiě)出 X、Y的機(jī)器數(shù)形式，根據(jù)題意，尾數(shù)為規(guī)格化形式，故Y二0.0001100000乞0,1000 =0.1100000000 ><20,0101。運(yùn)算過(guò)程中階碼、尾數(shù)采用雙符號(hào)位，X、Y的機(jī)器數(shù)形式為X=00,0101;

29、 00.1011000011, Y=00,0101 ；00.1100000000,X+Y的計(jì)算過(guò)程如下： 對(duì)階，X、Y階碼相同，階差為 0，故不需對(duì)階。 尾數(shù)求和，即得 X+Y =00,0101 ；01.0111000011。 規(guī)格化，尾數(shù)雙符號(hào)位為01，說(shuō)明尾數(shù)溢出，需要右規(guī)，尾數(shù)右移1位，階碼加1，得X+Y=00,0110 ; 00.1011100001尾數(shù)為規(guī)格化數(shù)，規(guī)格化結(jié)束。 舍入，采用“ 0舍1入法進(jìn)行舍入，由于中規(guī)格化時(shí)丟掉的數(shù)位中最高位為1，故需將結(jié)果的最低數(shù)值位加1，得X+Y=00,0110 ; 00.1011100010 溢出判斷，X+Y階碼雙符號(hào)位為00，說(shuō)明未發(fā)生溢出。

30、綜上，X+Y=0,0110 ； 0.1011100010 ，即 X+Y=0.1011100010 20,0110。注答案中機(jī)器數(shù)形式中的逗號(hào)、分號(hào)只是為了方便區(qū)分符號(hào)位和數(shù)值位、階碼和尾數(shù)，并非機(jī) 器數(shù)中實(shí)際存在。解析：某計(jì)算機(jī)的CPU主頻為500MHz , CPI為5 即執(zhí)行每條指令平均需5個(gè)時(shí)鐘周期。假定某外設(shè)的數(shù)據(jù)傳輸率為0.5MB/S ,采用中斷方式與主機(jī)進(jìn)行數(shù)據(jù)傳送，以32位為傳輸單位，對(duì)應(yīng)的中斷效勞程序包含18條指令，中斷效勞的其他開(kāi)銷相當(dāng)于2條指令的執(zhí)行時(shí)間。請(qǐng)答復(fù)以下問(wèn)題，要求給出計(jì)算過(guò)程。分?jǐn)?shù)：8.00 1.在中斷方式下，CPU用于該外設(shè)I/O的時(shí)間占整個(gè)CPU時(shí)間的百分比是

31、多少 ？分?jǐn)?shù)：4.00 正確答案：該外設(shè)數(shù)據(jù)傳輸率為0.5MB/S ,以32位為傳輸單位，故 1s內(nèi)因外設(shè)傳輸數(shù)據(jù)而引起的中斷次 數(shù)為0.5MB/4B=1.25 X 10 5 次對(duì)應(yīng)的中斷效勞程序及其他開(kāi)銷共需18+2=20條指令，CPI為5,故1s內(nèi)用于該外沒(méi)I/O的時(shí)鐘周期數(shù)為 1.25 X 10 5 X 20 X 5=1.25 X 10 7 個(gè)CPU主頻為500MHz，即1s內(nèi)共有500M個(gè)時(shí)鐘周期，故用于該外設(shè)I/O的時(shí)間占整個(gè) CPU時(shí)間的百分比是1.25 X 10 7 / 500 X 10 6 X 100%=2.5% 解析：.當(dāng)該外設(shè)的數(shù)據(jù)傳輸率到達(dá)5MB/S時(shí)，改用DMA方式傳送

32、數(shù)據(jù)。假設(shè)每次DMA傳送大小為5000B，且DMA預(yù)處理和后處理的總開(kāi)銷為500個(gè)時(shí)鐘周期，那么 CPU用于該外設(shè)I/O的時(shí)間占整個(gè)CPU時(shí)間的百分比 是多少?(假設(shè)DMA與CPU之間沒(méi)有訪存沖突)(分?jǐn)?shù)：4.00 )正確答 案：(該外設(shè)的數(shù)據(jù)傳輸率為5MB/S，每次DMA傳送大小為5000B，故1s內(nèi)的DMA傳輸次數(shù)為5MB/5000B=(5 X 10 6B)/(5 X 10 3B)=1000( 次 )DMA預(yù)處理及后處理的總開(kāi)銷為500個(gè)時(shí)鐘周期，故1s內(nèi)用于該外設(shè)傳輸數(shù)據(jù)的時(shí)鐘周期數(shù)為1000 X 500=5 X 10 5(個(gè))CPU主頻為500MHz，故用于該外設(shè)I/O的時(shí)間占整個(gè) CPU時(shí)間的百分比是(5 X 10 5)/(500 X 10 6) X 100%=0.1%)解析：44. 分時(shí)系統(tǒng)里，在條件相同的情況下，通常KLT(內(nèi)核級(jí)線程)比ULT(用戶級(jí)線程)得到更多的 CPU時(shí)間，請(qǐng)簡(jiǎn)要解釋之。分?jǐn)?shù)：7.00 )正確答案：(KLT(內(nèi)核級(jí)線程)直接參與CPU的調(diào)度，得到 CPU的時(shí)間和進(jìn)程相當(dāng)， ULT(用戶 級(jí)線程)由運(yùn)行thread Libray的進(jìn)程控制和管理，是該進(jìn)程得到的CPU時(shí)間總數(shù)里再次分配，往往比參加內(nèi)核調(diào)度的其他進(jìn)程少。)解析：45. 舉例說(shuō)明P、V操作為什么要