日本91-日本91视频-日本96在线精品视频免费观看-日本a∨网站-亚洲国产精久久久久久久-亚洲国产精品67194成人

一、單項(xiàng)選擇題：1~40 小題，每小題2 分，共80 分。下列每題給出的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)符合試題要求。

1. 已知兩個(gè)長(zhǎng)度分別為m 和n 的升序鏈表，若將它們合并為一個(gè)長(zhǎng)度為m+n 的降序鏈表，則最壞情況下的時(shí)間復(fù)雜度是

A. O(n) B. O(m.n) C. O(min(m,n)) D. O(max(m,n))

2. 一個(gè)棧的入棧序列為1, 2,3, ,n ，其出棧序列是1 2 3 , , , , n p p p p 。若2 p . 3，則3 p 可能取值的個(gè)數(shù)是

A. n .3 B. n . 2 C. n .1 D. 無法確定

3. 若將關(guān)鍵字1，2，3，4，5，6，7 依次插入到初始為空的平衡二叉樹T 中，則T 中平衡因子為0 的分支結(jié)點(diǎn)的個(gè)數(shù)是

A. 0 B. 1 C. 2 D. 3

4. 已知三叉樹T 中6 個(gè)葉結(jié)點(diǎn)的權(quán)分別是2，3，4，5，6，7，T 的帶權(quán)(外部)路徑長(zhǎng)度最小是

A. 27 B. 46 C. 54 D. 56

5. 若X 是后序線索二叉樹中的葉結(jié)點(diǎn)，且X 存在左兄弟結(jié)點(diǎn)Y，則X 的右線索指向的是

A. X 的父結(jié)點(diǎn) B. 以Y 為根的子樹的最左下結(jié)點(diǎn)

C. X 的左兄弟結(jié)點(diǎn)Y D. 以Y 為根的子樹的最右下結(jié)點(diǎn)

6. 在任意一棵非空二叉排序樹T1 中，刪除某結(jié)點(diǎn)v 之后形成二叉排序樹T2，再將v 插入T2 形成二叉排序樹T3。下列關(guān)于T1 與T3 的敘述中，正確的是

I. 若v 是T1 的葉結(jié)點(diǎn)，則T1 與T3 不同

II. 若v 是T1 的葉結(jié)點(diǎn)，則T1 與T3 相同

III. 若v 不是T1 的葉結(jié)點(diǎn)，則T1 與T3 不同

IV. 若v 不是T1 的葉結(jié)點(diǎn)，則T1 與T3 相同

A. 僅I、III B. 僅I、IV C. 僅II、III D. 僅II、IV

7. 設(shè)圖的鄰接矩陣A 如下所示。各頂點(diǎn)的度依次是

A. 1，2，1，2 B. 2，2，1，1 C. 3，4，2，3 D. 4，4，2，2

8. 若對(duì)如下無向圖進(jìn)行遍歷，則下列選項(xiàng)中，不是廣度優(yōu)先遍歷序列的是

A. h，c，a，b，d，e，g，f B. e，a，f，g，b，h，c，d

C. d，b，c，a，h，e，f，g D. a，b，c，d，h，e，f，g

9. 下列 AOE 網(wǎng)表示一項(xiàng)包含 8個(gè)活動(dòng)的工程。經(jīng)過同時(shí)加快若干進(jìn)度可以縮短整個(gè)工程的工期。下列選項(xiàng)中，加快其進(jìn)度就可以縮短工程工期的是

A.c 和 e B. d 和 e C. f和 d D. f 和 h

10. 在一株高度為2的5階B樹中，所含關(guān)鍵字的個(gè)數(shù)最少是

A.5 B.7 C.8 D.14

11.對(duì)給定的關(guān)鍵字序列 110，119 ，007 ，911，114 ，120 ，122進(jìn)行基數(shù)排序，則第2趟分配收集后得到的關(guān)鍵字序列是

A. 007，110，119，114，911，120 ，122 B. 007，110，119，114，911，122，120

C. 007，110，911，114，119，120，122 D. 110，120，911，122，114，007，119

12. 某計(jì)算機(jī)主頻為 1.2 GHz 1.2 GHz 1.2 GHz，其指令分為 4類，它們?cè)诨鶞?zhǔn)程序中所占比例及 CPICPICPI如下表所示。

該機(jī)的 MIPSMIPSMIPSMIPS數(shù)是

A. 100 B. 200 C. 400 D. 600

13. 某數(shù)采用 IEEE 754IEEE 754IEEE 754 單精度浮點(diǎn)數(shù)格式表示為 C640 C640 0000 H，則該數(shù)的值是

A. -1.5 ×213 B. B. -1.5 ×212 C. C. -0.5x ×213 D. -0.5 ×212

14. 某字長(zhǎng)為 8位的計(jì)算機(jī)中，已知整型變量 x、y的機(jī)器數(shù)分別為[x]補(bǔ)=1 1110100，[y]補(bǔ)=1 0110000。若整型變量 z=2x+y/2，則 z的機(jī)器數(shù)為

A. 1 1000000 B. 0 0100100 C. 1 0101010 D. 溢出

15 . 用海明碼對(duì)長(zhǎng)度為 8位的數(shù)據(jù)進(jìn)行檢 /糾錯(cuò)時(shí)，若能糾正一位錯(cuò)，則校驗(yàn)位數(shù)至少為

A. 2 B. 3 C. 4 D. 5

16. 某計(jì)算機(jī)主存地址空間大小為256 MB，按字節(jié)編址。虛擬地空間大小為4 GB，采用頁式存儲(chǔ)管理，頁面大小為4KB，TLB(快表)采用全相聯(lián)映射，有4個(gè)頁表項(xiàng)，內(nèi)容如下表所示。

則對(duì)虛擬地址03FF F180H進(jìn)行虛實(shí)地址變換的結(jié)果是

A. 015 3180H B. 003 5180H C. TLB缺失 D. 缺頁

17. 假設(shè)變址寄存器R的內(nèi)容為1000 H，指令中的形式地址為2000H地址1000H中的內(nèi)容為2000H，地址2000H中的內(nèi)容為3000H，地址3000H中的內(nèi)容為4000H ，則變址尋方式下訪問到的操作數(shù)是

A. 1000H B. 2000H C. 3000H D. 4000H

18. 某CPU主頻為1.03 GHz，采用4級(jí)指令流水線，每個(gè)段的執(zhí)行需要1個(gè)時(shí)鐘周期。假定CPU執(zhí)行了100條指令，在其執(zhí)行過程中沒有發(fā)生任何流水線阻塞，此時(shí)流水線的吞吐率為

A. 0.25×10 9條指令/秒 B. 0.97 ×10 9條指令 /秒

C. 1.0 ×10 9條指令/秒 D. 1.03 ×10 9條指令 /秒

19. 下列選項(xiàng)中，用于設(shè)備和控制器 (I/O接口 )之間互連的接口標(biāo)準(zhǔn)是

A. PCI B. USB C. AGP D. PCI-Express

20. 下列選項(xiàng)中，用于提高RAID可靠性的措施有

I. 磁盤鏡像 II.條帶化 III. 奇偶校驗(yàn) IV. 增加 Cache機(jī)制

A. 僅 I、II B. 僅 I、III C. 僅I、III和IV D. 僅II、III和IV

21. 某磁盤的轉(zhuǎn)速為10,000轉(zhuǎn)/分，平均尋道時(shí)間是6ms，磁盤傳輸速率是20MB/s，磁盤控制器延遲為0.2ms，讀取一個(gè)4KB的扇區(qū)所需平均時(shí)間約為

A. 9ms B. 9.4ms C. 12ms D. 12.4ms

22. 下列關(guān)于中斷 I/ O方式和 DMA 方式比較的敘述中，錯(cuò)誤的是

A. 中斷 I/ O方式請(qǐng)求的是方式請(qǐng)求的是 CPUCPUCPU處理時(shí)間，DMA 方式請(qǐng)求的是總線使用權(quán)

B. 中斷響應(yīng)發(fā)生在一條指令執(zhí)行結(jié)束后，中斷響應(yīng)發(fā)生在一條指令執(zhí)行結(jié)束后，DMA響應(yīng)發(fā)生在一個(gè)總線事務(wù)完成后

C. 中斷 I/ O方式下數(shù)據(jù)傳送經(jīng)過軟件完成，方式下數(shù)據(jù)傳送經(jīng)過軟件完成，DMA方式下數(shù)據(jù)傳送由硬件完成

D. 中斷 I/ O方式適用于所有外部設(shè)備，方式適用于所有外部設(shè)備，DMA方式僅適用于快速外部設(shè)備

23 . 用戶在刪除某文件的過程中，操作系統(tǒng)不可能執(zhí)行是

A. 刪除此文件所在的目錄 B. 刪除與此文件關(guān)聯(lián)的目錄項(xiàng)

C. 刪除與此文件對(duì)應(yīng)的控制塊 D. 釋放與此文件關(guān)聯(lián)的內(nèi)存級(jí)沖區(qū)

24. 為支持CD-ROM中視頻文件的快速隨機(jī)播放，播放性能最好的文件數(shù)據(jù)塊組織方式是

A. 連續(xù)結(jié)構(gòu) B. 鏈?zhǔn)浇Y(jié)構(gòu) C. 直接索引結(jié)構(gòu) D. 多級(jí)索引結(jié)鉤

25. 用戶程序發(fā)出磁盤I/O請(qǐng)求后，系統(tǒng)的處理系統(tǒng)的處理流程是：用戶程序&rarr系統(tǒng)調(diào)用處理程序&rarr設(shè)備駱動(dòng)程序&rarr中斷處理程序。其中，計(jì)算數(shù)據(jù)所在磁盤的柱面號(hào)、磁頭號(hào)、扇區(qū)號(hào)的程序是

A. 用戶程序 B. 系統(tǒng)調(diào)用處理程序

C. 設(shè)備驅(qū)動(dòng)程序 D. 中斷處理程序

26. 若某文件系統(tǒng)索引結(jié)點(diǎn)(inode)中有直接地址項(xiàng)和間接地址項(xiàng)，則下列選項(xiàng)中，與單個(gè)文件長(zhǎng)度無關(guān)的因素是

A. 索引結(jié)點(diǎn)的總數(shù) B. 間接地址索引的級(jí)數(shù)

C. 地址項(xiàng)的個(gè)數(shù) D. 文件塊大小

27 . 設(shè)系統(tǒng)緩沖區(qū)和用戶工作均采單，從外讀入1個(gè)數(shù)據(jù)塊到系統(tǒng)緩沖區(qū)的時(shí)間為100，從系統(tǒng)緩沖區(qū)讀入 1個(gè)數(shù)據(jù)塊到用戶工作區(qū)的時(shí)間為5，對(duì)用戶工作區(qū)中的1個(gè)數(shù)據(jù)塊進(jìn)行分析的時(shí)間為90(如下圖所示)。進(jìn)程從外設(shè)讀入并分析2個(gè)數(shù)據(jù)塊的最短時(shí)間是

A. 200 B. 295 C. 300 D .390

28. 下列選項(xiàng)中，會(huì)導(dǎo)致用戶進(jìn)程從態(tài)切換到內(nèi)核的操作是

I. 整數(shù)除以零 II. sin( )函數(shù)調(diào)用 III. read系統(tǒng)調(diào)用

A. 僅 I、II B. 僅 I、III C. 僅 II 、III D. I、II和III

29. 計(jì)算機(jī)開后，操作系統(tǒng)最終被加載到

A. BIOS B. ROM C. EPROM D. RAM

30. 若用戶進(jìn)程訪問內(nèi)存時(shí)產(chǎn)生缺頁，則下列選項(xiàng)中，操作系統(tǒng)可能執(zhí)行的是

I. 處理越界錯(cuò) II. 置換頁 III. 分配內(nèi)存

A. 僅 I、II B. 僅 II 、III C. 僅 I、III D. I、II 和 III

31. 某系統(tǒng)正在執(zhí)行三個(gè)進(jìn)程P1、P2和P3，各進(jìn)程的計(jì)算(CPUCPUCPU)時(shí)間和I/OI/O時(shí)間比例如下表所示。

34. 若下圖為10BaseT網(wǎng)卡接收到的信號(hào)波形，則該比特串是

A. 0011 0110 B. 1010 1101 C. 0101 0010 D. 1100 0101

35. 主機(jī)甲經(jīng)過1個(gè)路由器個(gè)路由器(存儲(chǔ)轉(zhuǎn)發(fā)方式)與主機(jī)乙互聯(lián)，兩段鏈路的數(shù)據(jù)傳輸速率均為10Mbps,主機(jī)甲分別采用報(bào)文交換和組大小為10kb的分組交換向主機(jī)乙發(fā)送1個(gè)大小為8Mb(1M=10 6)的報(bào)文。若忽略鏈路傳播延遲、分組頭開銷和拆裝時(shí)間，則兩種交換方式完成該報(bào)文傳輸所需的總時(shí)間分別為

A. 800ms 、1600ms B. 801ms、1600ms

C. 1600ms、800ms D. 1600ms 、801ms

36. 下列介質(zhì)訪問控制方法中，可能發(fā)生沖突的是

A. CDMA B. CSMA C. TDMAC D. FDMA

37. HDLC 37. HDLC37. HDLC協(xié)議對(duì)01111100 01111110組幀后對(duì)應(yīng)的比特串為

A. 01111100 00111110 10 B. 01111100 01111101 01111110

C. 01111100 01111101 0 D. 01111100 01111110 01111101

38. 對(duì)于100Mbps的以太網(wǎng)交換機(jī)，當(dāng)輸出端口無排隊(duì)直通(cut-through switching)方式轉(zhuǎn)發(fā)一個(gè)以太網(wǎng)幀(不包括前導(dǎo)碼)時(shí)，引入的轉(zhuǎn)發(fā)延遲至少是

A. 0 &mus B. 0.48 &mus C. 5.12 &mus D. 121.44 &mus

39. 主機(jī)甲與乙之間已建立一個(gè)TCP連接，雙方持續(xù)有數(shù)據(jù)傳輸,且無差錯(cuò)與丟失。若甲收到1個(gè)來自乙的TCP段，該段的序號(hào)為1913、確認(rèn)序號(hào)為2046、有效載荷為100字節(jié)，則甲立即發(fā)送給乙的 TCP 段的序號(hào)和確認(rèn)分別是

A. 2046 、2012 B. 2046、2013 C. 2047 、2012 D. 2047 2012

40. 下列關(guān)于SMTP 協(xié)議的敘述中，正確的是

I. 只支持傳輸7比特ASCII碼內(nèi)容

II. 支持在郵件服務(wù)器之間發(fā)送郵件

III. 支持從用戶代理向郵件服務(wù)器發(fā)送郵件

IV. 支持從郵件服務(wù)器向用戶代理發(fā)送郵件

A. 僅I、II 和III B. 僅I、II 和IV

C. 僅I、III 和IV D. 僅II、III 和IV

二、綜合應(yīng)用題：41~47 小題，共70 分。

41.

(0， 5，5，3，5，7，5，5)，側(cè)5 為主元素又如A=(0，5，5，3，5，1，5，7)，則A中沒有主元素。假設(shè)A中的n個(gè)元素保存在一個(gè)一維數(shù)組中，請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，找出A的主元素。若存在主元素，則輸出該元素否則輸出-1。要求：

(1)給出算法的基本設(shè)計(jì)思想。

(2)根據(jù)設(shè)計(jì)思想，采用C 或C++或Java 語言描述算法，關(guān)鍵之處給出注釋。

(3)說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。

42. (10 分)設(shè)包含4 個(gè)數(shù)據(jù)元素的集合S= "do"，"for"，" repeat"，" while"，各元素的查找概率依次為：p1=0.35，p2 = 0.15，p3=0. 15，p4=0.35。將S 保存在一個(gè)長(zhǎng)度為4的順序表中，采用折半查找法，查找成功時(shí)的平均查找長(zhǎng)度為2.2。請(qǐng)回答：

(1)若采用順序存儲(chǔ)結(jié)構(gòu)保存S，且要求平均查找長(zhǎng)度更短，則元素應(yīng)如何排列?應(yīng)使用何種查找方法?查找成功時(shí)的平均查找長(zhǎng)度是多少?

(2)若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)保存S，且要求平均查找長(zhǎng)度更短，則元素應(yīng)如何排列?應(yīng)使用何種查找方法?查找成功時(shí)的平均查找長(zhǎng)度是多少?

43.(9 分)某32 位計(jì)算機(jī)，CPU 主頻為800MHz，Cache 時(shí)的CPI 為4，Cache 塊大小為32 字節(jié)主存采用8 體交叉存儲(chǔ)方式，每個(gè)體的存儲(chǔ)字長(zhǎng)為32 位、存儲(chǔ)周期為40 ns存儲(chǔ)器總線寬度為32 位，總線時(shí)鐘頻率為200 MHz，支持突發(fā)傳送總線事務(wù)。每次讀突發(fā)傳送總線事務(wù)的過程包括：送首地址和命令、存儲(chǔ)器準(zhǔn)備數(shù)據(jù)、傳送數(shù)據(jù)。每次突發(fā)傳送32 字節(jié)，傳送地址或32 位數(shù)據(jù)均需要一個(gè)總線時(shí)鐘周期。請(qǐng)回答下列問題，要求給出理由或計(jì)算過程。

(1)CPU 和總線的時(shí)鐘周期各為多少?總線的帶寬(即最大數(shù)據(jù)傳輸率)為多少?

(2)Cache 缺失時(shí)，需要用幾個(gè)讀突發(fā)傳送總線事務(wù)來完成一個(gè)主存塊的讀取?

(3)存儲(chǔ)器總線完成一次讀突發(fā)傳送總線事務(wù)所需的時(shí)間是多少?

(4)若程序BP 執(zhí)行過程中，共執(zhí)行了100 條指令，平均每條指令需進(jìn)行1.2 次訪存，Cache 缺失率為5%，不考慮替換等開銷，則BP 的CPU 執(zhí)行時(shí)間是多少?

44.(14 分)某計(jì)算機(jī)采用16 位定長(zhǎng)指令字格式，其CPU 中有一個(gè)標(biāo)志寄存器，其中包含進(jìn)位/借位標(biāo)志CF、零標(biāo)志ZF 和符號(hào)標(biāo)志NF。假定為該機(jī)設(shè)計(jì)了條件轉(zhuǎn)移指令，其格式如下：

其中，00000為操作碼OPC、Z和 N分別為CF、ZF和NF的對(duì)應(yīng)檢測(cè)位，某測(cè)位為1時(shí)表示需檢測(cè)對(duì)應(yīng)標(biāo)志，需檢測(cè)的標(biāo)志位中只要有一個(gè)為1就轉(zhuǎn)移，否則就不轉(zhuǎn)移，例如，若C=1，Z=0，N=1，則需檢測(cè)CF和NF的值，當(dāng) CF=1或NF=1時(shí)發(fā)生轉(zhuǎn)移OFFSET是相對(duì)偏移量，用補(bǔ)碼表示。轉(zhuǎn)移執(zhí)行時(shí)，轉(zhuǎn)移目標(biāo)地址為(PC)+2+2×OFFSET順序執(zhí)行時(shí)，下條指令地址為(PC)+2。請(qǐng)回答下列問題。

(1)該計(jì)算機(jī)存儲(chǔ)器按字節(jié)編址，還是按字編址?該條件轉(zhuǎn)移指令向后(反向)最多可跳轉(zhuǎn)最多少條指令?

(2)某條件轉(zhuǎn)移指令的地址為200CH，指令內(nèi)容如下圖所示，若該執(zhí)行時(shí)CF=0，ZF=0，NF=1，則該指令執(zhí)行后PC的值是多少?若該指令執(zhí)行時(shí)CF=1，ZF=0 Z，NF=0，則該指令執(zhí)行后PC的值又是多少?請(qǐng)給出計(jì)算過程。

(3)實(shí)現(xiàn)“無符號(hào)數(shù)比較小于等時(shí)轉(zhuǎn)移”功能的指令中， C、Z和 N應(yīng)各是什么?

(4)以下是該指令對(duì)應(yīng)的數(shù)據(jù)通路示意圖，要求給出中部件①~③的名稱或功能說明。

為提高系統(tǒng)資源利用率，合理的進(jìn)程優(yōu)先級(jí)設(shè)置應(yīng)

A. P1 >P2 >P3 B. P3>P2 >P1 C. P2>P1 =P3 D. P1>P2=P3

32 . 下列關(guān)于銀行家算法的敘述中，正確的是

A. 銀行家算法可以預(yù)防死鎖

B. 當(dāng)系統(tǒng)處于安全狀態(tài)時(shí)，系統(tǒng)中一定無死鎖進(jìn)程

C. 當(dāng)系統(tǒng)處于不安全狀態(tài)時(shí)，系統(tǒng)中一定會(huì)出現(xiàn)死鎖進(jìn)程

D. 銀行家算法破壞了死鎖必要條件中的“請(qǐng)求和保持”條件

33. 在 OSI 參考摸型中，下列功能需由應(yīng)用層的相鄰層實(shí)現(xiàn)的是

A. 對(duì)話管理 B. 數(shù)據(jù)格式轉(zhuǎn)換 C. 路由選擇 D. 可靠數(shù)據(jù)傳輸

45. (7分)某博物館最多可容納500人同時(shí)參觀，有一個(gè)出入口，該出入口一次僅允許個(gè)經(jīng)過。參觀者的活動(dòng)描述如下：

cobegin

參觀者進(jìn)程i：

…

進(jìn)門

…

參觀

…

出門

…

coend

請(qǐng)?zhí)砑颖匾男盘?hào)量和P、V(或wait()、signal( ))操作，以實(shí)現(xiàn)上述操作過程中的互斥與同步。

要求寫出完整的過程，說明信號(hào)量含義并賦初值。

46. (8分)某計(jì)算機(jī)主存按字節(jié)編址，邏輯地址和物理地址都是32位，頁表項(xiàng)大小為4字節(jié)。請(qǐng)回答下列問題。

(1)若使用一級(jí)頁表的分存儲(chǔ)管理方式，邏輯地址結(jié)構(gòu)為：

則頁的大小是多少字節(jié)?頁表最大占用多少字節(jié)?

(2)若使用二級(jí)頁表的分存儲(chǔ)管理方式，邏輯地址結(jié)構(gòu)為：

設(shè)邏輯地址為 LA ，請(qǐng)分別給出其對(duì)應(yīng)的頁目錄號(hào)和表索引達(dá)式。

(3)采用(1)中的分頁存儲(chǔ)管理方式，一個(gè)代碼段起始邏輯地址為0000 8000H，其長(zhǎng)度為8KB，被裝載到從物理地址0090 0000H開始的連續(xù)主存空間中。頁表從主存0020 0000H 0020 0000H開始的物理地址處連續(xù)存放，如下圖所示(地址大小自下向上遞增)。請(qǐng)計(jì)算出該代碼段對(duì)應(yīng)的兩個(gè)頁表項(xiàng)物理地址、這中框號(hào)以及計(jì)算出該代碼段對(duì)應(yīng)的兩個(gè)頁表項(xiàng)物理地址、這中框號(hào)以及計(jì)算出該代碼段對(duì)應(yīng)的兩個(gè)頁表項(xiàng)物理地址、這兩個(gè)頁表項(xiàng)中的框號(hào)以及代碼頁面2的起始物理地址。

47. (9分)假設(shè)Internet的兩個(gè)自治系統(tǒng)構(gòu)成網(wǎng)絡(luò)如題 47 圖所示，自治系統(tǒng)ASI由路由器R1連接兩個(gè)子網(wǎng)構(gòu)成自治系統(tǒng)AS2由路由器R2、R3互聯(lián)并連接3個(gè)子網(wǎng)構(gòu)成。各子網(wǎng)地址、R2的接口名、R1與R3的部分接口IP地址如題47圖所示。

題47圖網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

請(qǐng)回答下列問題。

(1)假設(shè)路由表結(jié)構(gòu)如下所示。請(qǐng)利用路由聚合技術(shù)，給出R2的路由表，要求包括到達(dá)題47圖中所有子網(wǎng)的路由，且路由表中的路由項(xiàng)盡可能少。

(2)若R2收到一個(gè)目的IP地址為194.17.20.200的IP分組，R2會(huì)經(jīng)過哪個(gè)接口轉(zhuǎn)發(fā)該IP分組?

(3)R1與R2之間利用哪個(gè)路由協(xié)議交換信息?該路由協(xié)議的報(bào)文被封裝到哪個(gè)議的分組中進(jìn)行傳輸?