一、1.單項(xiàng)選擇題

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

0.抽象數(shù)據(jù)類型(ADT)不包括( )。

A.邏輯結(jié)構(gòu)
B.存儲(chǔ)結(jié)構(gòu)
C.數(shù)據(jù)關(guān)系
D.操作

1.利用棧對(duì)后綴表達(dá)式12+34+*求值，求值過(guò)程所需棧的最大深度是(  )。

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

2.序列EAs+Y+QUE* *+st+*+IO*n++*表示對(duì)一個(gè)雙端隊(duì)列的操作，大寫(xiě)字母表示向隊(duì)頭之前入列，小寫(xiě)字母表示在隊(duì)尾之后入列，加號(hào)+表示從隊(duì)頭出列，乘號(hào)*表示從隊(duì)尾出列。該操作序列得到的出隊(duì)結(jié)果是(  )。

A.E A s Y Q U E s t I O n
B.E s A Y U Q E s t I O n
C.A Y s E E U t O s O I n
D.A E y s E U t Q O I s n

3.一個(gè)具有1 025個(gè)結(jié)點(diǎn)的二叉樹(shù)的高h(yuǎn)為(  )。

A.11
B.10
C.11至1 025之間
D.10至1 025之間

4.

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

5.一棵折半查找樹(shù)(BST)有7個(gè)結(jié)點(diǎn)，存放的數(shù)據(jù)分別為A B C D E F G，(  )不是查找序列。

A.A B C D E F G
B.G F E D
C.D B C F
D.D G E F

6.在無(wú)序數(shù)組a[N]中作10次以上查找，為提高查找效率，先對(duì)a[N]排序，然后各次查找采用折半查找。問(wèn)N至少為(  )時(shí)，排序預(yù)處理才是合理的?

A.512
B.1 024
C.2 048
D.4 096

7.100個(gè)結(jié)點(diǎn)的平衡二叉樹(shù)(AVL樹(shù))最高為(  )層?(根是第1層)

A.10
B.11
C.12
D.13

8.對(duì)無(wú)序的撲克排序，要求先排花色，再排大小，兩次排序采用同種排序法，則應(yīng)選用 (  )。

A.快速排序
B.選擇排序
C.插入排序
D.堆排序

9.某種排序法對(duì)存放在內(nèi)存中的a[N]排序，時(shí)間為60秒，對(duì)存放在內(nèi)存中的a[2N]排序的時(shí)間超過(guò)240秒，則該排序法極可能是(  )。

A.歸并排序
B.快速排序
C.堆排序
D.基數(shù)排序

10.針對(duì)8位二進(jìn)制數(shù)，下列說(shuō)法中正確的是(  )。

A.-127的補(bǔ)碼為10000000
B.-127的反碼等于0的移碼
C.+1的移碼等于-127的反碼
D.0的補(bǔ)碼等于-1的反碼

11.下列說(shuō)法中正確的是(  )。

A.只有定點(diǎn)數(shù)運(yùn)算才有可能溢出，浮點(diǎn)數(shù)運(yùn)算不會(huì)產(chǎn)生溢出。
B.只有帶符號(hào)數(shù)的運(yùn)算才有可能產(chǎn)生溢出。
C.將兩個(gè)正數(shù)相加時(shí)有可能產(chǎn)生溢出。
D.采用變形補(bǔ)碼進(jìn)行加減法運(yùn)算可以避免溢出。

12.下列說(shuō)法中正確的是(  )。

A.虛擬存儲(chǔ)器技術(shù)提高了計(jì)算機(jī)的速度。
B.若主存由兩部分組成，容量分別為2n和2m，則主存地址共需要n+m位。
C.閃速存儲(chǔ)器是一種高密度、非易失性的讀／寫(xiě)半導(dǎo)體存儲(chǔ)器。
D.存取時(shí)間是指連續(xù)兩次讀操作所需間隔的最小時(shí)間。

13.在多級(jí)存儲(chǔ)體系中，“Cache-主存”結(jié)構(gòu)的作用是解決(  )的問(wèn)題。

A.主存容量不足
B.主存與輔存速度不匹配
C.輔存與CPU速度不匹配
D.主存與CPU速度不匹配

14.下列陳述中不正確的是(  )。

A.總線結(jié)構(gòu)傳送方式可以提高數(shù)據(jù)的傳輸速度。
B.與獨(dú)立請(qǐng)求方式相比，鏈?zhǔn)讲樵兎绞綄?duì)電路的故障更敏感。
C.PCI總線采用同步時(shí)序協(xié)議和集中式仲裁策略。
D.總線的帶寬即總線本身所能達(dá)到的最高傳輸速率。

15.已知定點(diǎn)整數(shù)x的原碼為1x_n-1x_n-2x_n-3…x₀，且x＞-2^n-1，則必有(  )。

A.x_n-1=0
B.x_n-1=1
C.x_n-1=0，且x₀～x_n-2不全為0
D.x_n-1=1，且x₀~x_n-2不全為0

16.下列說(shuō)法中不正確的是(  )。

A.機(jī)器語(yǔ)言和匯編語(yǔ)言都是面向機(jī)器的，它們和具體機(jī)器的指令系統(tǒng)密切相關(guān)。
B.指令的地址字段指出的不是地址，而是操作數(shù)本身，這種尋址方式稱為直接尋址。
C.串聯(lián)堆棧一般不需要堆棧指示器，但串聯(lián)堆棧的讀出是破壞性的。
D.存儲(chǔ)器堆棧是主存的一部分，因而也可以按照地址隨機(jī)進(jìn)行讀寫(xiě)操作。

17.下列描述中，屬于馮.諾依曼體系結(jié)構(gòu)的特點(diǎn)是(  )。
①采用流水線技術(shù)；②指令和數(shù)據(jù)均以二進(jìn)制表示；③存儲(chǔ)程序并且存儲(chǔ)時(shí)不區(qū)別數(shù)據(jù)和指令。

A.①和②
B.①和③
C.②和③
D.①，②和③

18.下述有關(guān)存儲(chǔ)器的描述中，正確的是(  )。

A.雙端口存儲(chǔ)器具有分離的讀端口和寫(xiě)端口，因而CPU可以同時(shí)對(duì)其進(jìn)行讀、寫(xiě)操作。
B.存儲(chǔ)保護(hù)的目的是：在多用戶環(huán)境中，既要防止一個(gè)用戶程序出錯(cuò)而破壞系統(tǒng)軟件或其他用戶程序，又要防止一個(gè)用戶訪問(wèn)不是分配給他的主存區(qū)，以達(dá)到數(shù)據(jù)安全與保密的要求。
C.在虛擬存儲(chǔ)器中，外存和主存以相同的方式工作，因此允許程序員用比主存空間大得多的外存空間編程。
D.CPU中通常都設(shè)置有若干個(gè)寄存器，這些寄存器與Cache統(tǒng)一編址，但訪問(wèn)速度更高。

19.在計(jì)算機(jī)系統(tǒng)中，表征系統(tǒng)運(yùn)行狀態(tài)的部件是(  )。

A.程序計(jì)數(shù)器
B.累加寄存器
C.中斷寄存器
D.程序狀態(tài)字

20.下列陳述中正確的是(  )。

A.由于微程序控制器具有設(shè)計(jì)規(guī)整、靈活性強(qiáng)等優(yōu)點(diǎn)，已經(jīng)全部取代硬布線控制器
B.由于堆棧按照先入先出的固定順序訪問(wèn)，故不需直接給出訪問(wèn)地址
C.集中式總線控制中，計(jì)數(shù)器定時(shí)查詢方式下，各設(shè)備的優(yōu)先級(jí)是固定不變的
D.CPU在每個(gè)指令周期后響應(yīng)中斷請(qǐng)求

21.某虛擬存儲(chǔ)器采用頁(yè)式內(nèi)存管理，使用LRU頁(yè)面替換算法，考慮下面的頁(yè)面訪問(wèn)地址流(每次訪問(wèn)在一個(gè)時(shí)間單位中完成)，1，8，1，7，8，2，7，2，1，8，3，8，2，1，3，1，7，1，3，7。假定內(nèi)存容量為4個(gè)頁(yè)面，開(kāi)始時(shí)是空的，則頁(yè)面失效次數(shù)是(  )。

A.4
B.5
C.6
D.7

22.支持多道程序的操作系統(tǒng)，區(qū)別于其他操作系統(tǒng)的主要特征為(  )。

A.多用戶、進(jìn)程的獨(dú)立性、進(jìn)程之間的同步與通信
B.進(jìn)程的獨(dú)立性、進(jìn)程之間的同步與通信、動(dòng)態(tài)存儲(chǔ)分配
C.進(jìn)程的獨(dú)立性、動(dòng)態(tài)存儲(chǔ)分配、虛存
D.多內(nèi)核結(jié)構(gòu)、進(jìn)程的獨(dú)立性、動(dòng)態(tài)存儲(chǔ)分配

23.進(jìn)程與線程的主要差別體現(xiàn)在(  )。

A.不同進(jìn)程不能共享代碼，而不同線程可以共享代碼
B.不同進(jìn)程不能共享內(nèi)存，而不同線程可以共享內(nèi)存
C.不同進(jìn)程有不同的地址空間，而不同線程可以有相同的地址空間
D.不同進(jìn)程不能并行，而不同線程可并行

24.以下給出UNIX Shell的兩條命令行：  I．1s＞output．txt&wc output．txt&　  II．Ls ｜ WC 命令行I與命令行II的主要差別在于(  )。

A.I的ls與wc串行執(zhí)行，而II的ls與WC并發(fā)執(zhí)行
B.I的ls與WC并發(fā)執(zhí)行，而II的ls與wc串行執(zhí)行
C.I正確，而II不正確
D.I不正確，而II正確

25.UNIX對(duì)已有文件建立物理鏈接與建立符號(hào)鏈接，以下敘述正確的是(  )。

A.物理鏈接創(chuàng)建新的目錄項(xiàng)，而符號(hào)鏈接不創(chuàng)建新的目錄項(xiàng)
B.物理鏈接創(chuàng)建新的inode，而符號(hào)鏈接不創(chuàng)建新的inode
C.物理鏈接不創(chuàng)建新的目錄項(xiàng)，而符號(hào)鏈接創(chuàng)建新的目錄項(xiàng)
D.物理鏈接不創(chuàng)建新的inode，而符號(hào)鏈接創(chuàng)建新的inode

26.某系統(tǒng)進(jìn)程P1在時(shí)刻t開(kāi)始執(zhí)行，所需執(zhí)行時(shí)間是5秒。進(jìn)程P2在時(shí)刻t+2秒開(kāi)始執(zhí)行，所需執(zhí)行時(shí)間是2秒。隨后無(wú)其他進(jìn)程進(jìn)入系統(tǒng)。如果進(jìn)程調(diào)度算法為時(shí)間片輪轉(zhuǎn)(RR)，時(shí)間片大小為1秒且調(diào)度開(kāi)銷忽略不計(jì)，那么(  )。

A.P1的結(jié)束時(shí)間是t+5秒，P2的結(jié)束時(shí)間是t+7秒
B.P1的結(jié)束時(shí)間是t+4秒，P2的結(jié)束時(shí)間是t+7秒
C.P1的結(jié)束時(shí)間是t+7秒，P2的結(jié)束時(shí)間是t+5秒
D.P1的結(jié)束時(shí)間是t+6秒，P2的結(jié)束時(shí)間是t+7秒

27.進(jìn)程P需要資源1、2、3、4，進(jìn)程Q需要資源2、3、4、5，系統(tǒng)中有資源1、2、3、4、5各一個(gè)，以下序列(  )將導(dǎo)致死鎖。(+表示請(qǐng)求資源)

A.P+1，P+2，Q+5，P+4，P+3，Q+3，Q+2，Q+4
B.Q+5，Q+4，P+1，P+2，P+3，P+4，Q+3，Q+2
C.Q+2，Q+3，Q+4，P+1，P+2，P+3，Q+5，P+4
D.P+1，Q+4，Q+3，Q+2，Q+5，P+2，P+3，P+4

28.頁(yè)面淘汰策略之一的先進(jìn)先出算法可能導(dǎo)致Belady現(xiàn)象，其根本原因是(  )。

A.局部性原理
B.工作集太大
C.地址格式設(shè)置不當(dāng)
D.程序錯(cuò)誤

29.復(fù)制文件操作完成之后(無(wú)錯(cuò)誤)，存放文件的磁盤其空閑塊將(  )。

A.增加
B.減少
C.不變
D.A、B、C都有可能

30.某激光打印機(jī)每分鐘打印20頁(yè)，每頁(yè)4 000字符，相應(yīng)的設(shè)備驅(qū)動(dòng)程序一次輸出一個(gè)字符，采用中斷方式，CPU處理每次中斷需50微秒，則CPU用于打印的開(kāi)銷是(  )。

A.1／10
B.1／15
C.1／20
D.1／4 000

31.磁盤D1每道32扇區(qū)，每扇區(qū)：1K，磁盤D2每道8扇區(qū)，每扇區(qū)4K。文件F1和F2內(nèi)容相同，大小為100K。F1均勻分布在D1，F(xiàn)2均勻分布在D2。磁盤D1、D2的平均尋道時(shí)間均為10毫秒，旋轉(zhuǎn)延遲5毫秒，傳輸時(shí)間忽略不計(jì)。順序讀完F1、F2的時(shí)間分別為 (  )。

A.1．5秒和6秒
B.0．375秒和1．5秒
C.1．5秒和0．375秒
D.6秒和1．5秒

32.網(wǎng)絡(luò)協(xié)議的三要素是(  )。

A.數(shù)據(jù)格式、編碼、信號(hào)電平
B.數(shù)據(jù)格式、控制信息、速度匹配
C.語(yǔ)法、語(yǔ)義、時(shí)序
D.編碼、控制信息、同步

33.RS232-C接口規(guī)范所處的層次是(  )。

A.物理層
B.數(shù)據(jù)鏈路層
C.網(wǎng)絡(luò)層
D.傳輸層

34.一個(gè)廣域網(wǎng)信道的比特率是4 Kbps，傳播延遲為20毫秒，若確保停一等協(xié)議至少50％的效率，那么幀的大小至少是(  )。

A.大于160 bit
B.大于150 bit
C.大于140 bit
D.大于130 bit

35.下列哪項(xiàng)是SNMP的正確描述(  )。

A.SNMP很少在新安裝設(shè)備上使用
B.SNMP是一個(gè)TCP／IP標(biāo)準(zhǔn)
C.SNMP是一個(gè)如MB一樣的概念
D.SNMP是大流量網(wǎng)絡(luò)的最佳選擇

36.IP數(shù)據(jù)報(bào)的報(bào)文格式如下圖所示。在沒(méi)有選項(xiàng)和填充的情況下，報(bào)頭長(zhǎng)度域的值為(  )。

A.3
B.5
C.10
D.20

37.對(duì)地址轉(zhuǎn)換協(xié)議(ARP)描述正確的是( )。

A.ARP封裝在IP數(shù)據(jù)報(bào)的數(shù)據(jù)部分
B.ARP是采用廣播方式發(fā)送的
C.ARP是用于IP地址到域名的轉(zhuǎn)換
D.發(fā)送ARP包需要知道對(duì)方的MAC電址

38.下列哪一項(xiàng)控制端到端傳送的信息量并保證TCP的可靠性(  )。

A.廣播
B.窗口
C.錯(cuò)誤恢復(fù)
D.流量控制

39.當(dāng)一臺(tái)計(jì)算機(jī)從FTP服務(wù)器下載文件時(shí)，在該FTP服務(wù)器上對(duì)數(shù)據(jù)進(jìn)行封裝的五個(gè)轉(zhuǎn)換步驟是(  )。

A.比特，數(shù)據(jù)幀，數(shù)據(jù)報(bào)，數(shù)據(jù)段，數(shù)據(jù)
B.數(shù)據(jù)，數(shù)據(jù)段，數(shù)據(jù)報(bào)，數(shù)據(jù)幀，比特
C.數(shù)據(jù)報(bào)，數(shù)據(jù)段，數(shù)據(jù)，比特，數(shù)據(jù)幀
D.數(shù)據(jù)段，數(shù)據(jù)報(bào)，數(shù)據(jù)幀，比特，數(shù)據(jù)

二、2.綜合應(yīng)用題

綜合應(yīng)用題
41-47小題，共70分。

0. 試編寫(xiě)一個(gè)建立帶表頭結(jié)點(diǎn)的雙向循環(huán)鏈表的算法。

1. 編寫(xiě)判定給定的二叉樹(shù)是否是二叉排序樹(shù)的函數(shù)。

2. 設(shè)磁盤的扇區(qū)大小為4 KB，磁盤轉(zhuǎn)速為15 000 r／min，磁盤平均尋道時(shí)間為4 ms，最大數(shù)據(jù)傳輸速率為40 MB／s，磁盤控制器開(kāi)銷時(shí)問(wèn)為1 ms，計(jì)算讀寫(xiě)一個(gè)扇區(qū)所需平均時(shí)間(不考慮I／O請(qǐng)求隊(duì)列中的等待時(shí)間)。

3.

4.

5.

6.