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

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

0.一個(gè)棧的入棧序列是1，2，3，4，5，則棧的不可能的輸出序列是(     )。

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

1.設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a_1,1為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則a_8,5的地址是(     )。

A.13
B.33
C.18
D.40

2.在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹中，所有結(jié)點(diǎn)的空子樹個(gè)數(shù)等于(     )。

A.n
B.n-1
C.n+1
D.2n

3.在常用的描述二叉排序樹的存儲(chǔ)結(jié)構(gòu)中，關(guān)鍵字值最大的結(jié)點(diǎn)是(     )。

A.左指針一定為空
B.右指針一定為空
C.左右指針均為空
D.左右指針均不為空

4.由權(quán)值為9、2、5、7的四個(gè)葉子構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為(     )。

A.23
B.37
C.44
D.46

5.若一個(gè)具有n個(gè)結(jié)點(diǎn)、k條邊的非連通無向圖是一個(gè)森林(n>k)，則該森林中必有樹的數(shù)目是(     )。

A.k
B.n
C.n-k
D.n+k

6.采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類似于樹的(     )。

A.中根遍歷
B.先根遍歷
C.后根遍歷
D.按層次遍歷

7.在有向圖G的拓?fù)湫蛄兄校繇旤c(diǎn)V_i在頂點(diǎn)V_j之前，則下列情形不可能出現(xiàn)的是(     )。

A.G中有弧i，V_j>
B.G中有一條從V_i到V_j的路徑
C.G中沒有弧i，V_j>
D.G中有一條從V_j到V_i的路徑

8.假設(shè)有k個(gè)關(guān)鍵字互為同義詞，若用線性探查法把這k個(gè)關(guān)鍵字存入，至少要進(jìn)行的探查次數(shù)是(     )。

A.k-1
B.k
C.k+1
D.k(k+1)／2

9.下列序列中，滿足堆定義的是(     )。

A.(100，86，48，73，35，39，42，57，66，21)
B.(12，70，33，65，24，56，48，92，86，33)
C.(103，97，56，38，66，23，42，12，30，52，6，26)
D.(5，56，20，23，40，38，29，61，36，76，28，100)

10.對(duì)于一個(gè)長度為n的任意表進(jìn)行排序，至少需要進(jìn)行的比較次數(shù)是(     )。

A.O(n)
B.O(n²)
C.O(logn)
D.O(nlogn)

11.哈佛(Harvard)結(jié)構(gòu)的基本特點(diǎn)是(     )。

A.采用多指令流單數(shù)據(jù)流
B.程序和數(shù)據(jù)在不同的存儲(chǔ)空間
C.堆棧操作
D.存儲(chǔ)器按內(nèi)容選擇地址

12.若二進(jìn)制定點(diǎn)小數(shù)真值是一0．1101，機(jī)器中表示為1．0010，則該數(shù)采用的編碼方法是 (     )。

A.原碼
B.補(bǔ)碼
C.反碼
D.移碼

13.描述流水線CPU基本概念中，正確表述的句子是(     )。

A.流水線CPU是以空間并行性為原理構(gòu)造的處理
B.流水線CPU一定是RISC機(jī)器
C.流水線CPU一定是多媒體CPU
D.流水線CPU是一種非常經(jīng)濟(jì)而實(shí)用的時(shí)間并行技術(shù)

14.原碼乘法時(shí)，符號(hào)位單獨(dú)處理，乘積的符號(hào)是(     )。

A.兩個(gè)操作數(shù)符號(hào)相“與”
B.兩個(gè)操作數(shù)符號(hào)相“或”
C.兩個(gè)操作數(shù)符號(hào)相“異或”
D.兩個(gè)操作數(shù)中絕對(duì)值較大數(shù)的符號(hào)

15.頁式存儲(chǔ)系統(tǒng)的邏輯地址是由頁號(hào)和頁內(nèi)地址兩部分組成，地址變換過程如下圖所示。假定頁面的大小為8K，圖中所示的十進(jìn)制邏輯地址9612經(jīng)過地址變換后，形成的物理地址a(十進(jìn)制)是(     )。
  

A.42380
B.25996
C.9612
D.8192

16.在指令系統(tǒng)的各種尋址方式中，獲取操作數(shù)最快的方式是(     )。

A.直接尋址
B.立即尋址
C.寄存器尋址
D.間接尋址

17.在計(jì)算機(jī)體系結(jié)構(gòu)中，CPU內(nèi)部包括程序計(jì)數(shù)器PC、存儲(chǔ)器數(shù)據(jù)寄存器MDR、指令寄存器IR和存儲(chǔ)器地址寄存器MAR等。若CPU要執(zhí)行的指令為：MOV R0，#100(即將數(shù)值100傳送到寄存器R0中)，則CPU首先要完成的操作是(     )。

A.100→R0
B.100→MDR
C.PC→MAR
D.PC→IR

18.在微指令的編碼方式中，若微命令數(shù)相同，下列敘述中正確的是(     )。
  I．直接控制方式與編碼控制方式的微指令長度相等
  Ⅱ．最短編碼控制和直接控制方式不影響微指令字長
  Ⅲ．編碼控制方式的微指令比直接控制方式的微指令短
  Ⅳ．直接控制的微指令比字段編碼的微指令長
  V．字段直接編碼的微指令與字段間接編碼的微指令長度相等
  Ⅵ．字段間接編碼的微指令比字段直接編碼的微指令長

A.Ⅲ和PC
B.I和111
C.Ⅱ和Ⅲ
D.Ⅲ、Ⅳ和Ⅵ

19.下列計(jì)算機(jī)總線屬于串行總線的是(     )。

A.PCI
B.1394
C.EISA
D.ISA

20.某數(shù)碼相機(jī)內(nèi)置128MB的存儲(chǔ)空間，拍攝分辨率設(shè)定為1 600×1 200像素，顏色深度為24位，若不采用壓縮存儲(chǔ)技術(shù)，使用內(nèi)部存儲(chǔ)器最多可以存儲(chǔ)的照片數(shù)是(     )。

A.12
B.25
C.13
D.23

21.中斷向量表中保存的是(     )。

A.被中斷程序的返回地址
B.中斷服務(wù)程序入口地址
C.中斷優(yōu)先級(jí)
D.中斷源編碼

22.對(duì)于設(shè)計(jì)實(shí)時(shí)操作系統(tǒng)，不是其設(shè)計(jì)目標(biāo)的是(     )。

A.安全可靠
B.處理機(jī)效率
C.及時(shí)響應(yīng)輸入
D.快速處理請(qǐng)求

23.并發(fā)進(jìn)程在運(yùn)行時(shí)，其推進(jìn)的相對(duì)速度是(     )。

A.由進(jìn)程的程序結(jié)構(gòu)決定
B.由進(jìn)程自己的代碼控制
C.與進(jìn)程調(diào)度策略有關(guān)
D.在進(jìn)程創(chuàng)建時(shí)確定的

24.兩個(gè)旅行社甲和已為旅客到某航空公司訂飛機(jī)票，形成互斥資源的是(     )。

A.旅行社
B.航空公司
C.飛機(jī)票
D.旅行社與航空公司

25.在進(jìn)程通信中，消息的一般形式為四個(gè)部分組成。是(     )。

A.發(fā)送進(jìn)程名、接收進(jìn)程名、消息標(biāo)示符、消息正文
B.發(fā)送進(jìn)程名、消息標(biāo)示符、消息長度、消息正文
C.發(fā)送進(jìn)程名、接收進(jìn)程名、消息長度、消息當(dāng)前狀態(tài)
D.發(fā)送進(jìn)程名、接收進(jìn)程名、消息長度、消息正文

26.某計(jì)算機(jī)系統(tǒng)中內(nèi)存保護(hù)采用基址、限長寄存器的方法來實(shí)現(xiàn)，那么，判斷是否越界的判別式是(     )。

A.0≤被訪問的邏輯地址<限長寄存器的內(nèi)容
B.0≤被訪問的邏輯地址≤限長寄存器的內(nèi)容
C.O≤被訪問的物理地址<限長寄存器的內(nèi)容
D.0≤被訪問的物理地址≤限長寄存器的內(nèi)容

27.在某個(gè)計(jì)算機(jī)系統(tǒng)中，內(nèi)存的分配采用按需調(diào)頁的方式，測(cè)得當(dāng)前CPU的利用率為8%，硬盤交換空間的利用率為55%，硬盤的繁忙率為97%，其它設(shè)備的利用率可以忽略不計(jì)，由此斷定系統(tǒng)發(fā)生異常，此異?？赡軙?huì)是(     )，解決辦法是(     )。
  I．Belady現(xiàn)象；Ⅱ．抖動(dòng)；Ⅲ．死鎖；Ⅳ．饑餓；V．加大交換空間容量；Ⅵ．增加內(nèi)存容量；Ⅶ．增加CPU數(shù)量；Ⅷ．增加并發(fā)進(jìn)程數(shù)；

A.I和V
B.Ⅱ和Ⅵ
C.Ⅲ和Ⅶ
D.Ⅳ和Ⅷ

28.若用100個(gè)雙字(字長32位)組成的位示圖管理內(nèi)存，假定用戶歸還一個(gè)塊號(hào)為240的內(nèi)存塊時(shí)，它對(duì)應(yīng)的位示圖的位置是(     )。

A.字號(hào)為6，位號(hào)為16
B.字號(hào)為7，位號(hào)為16
C.字號(hào)為6，位號(hào)為14
D.字號(hào)為7，位號(hào)為14

29.通常對(duì)文件系統(tǒng)來說，文件名和文件屬性可以找到的地方是(     )。

A.目錄
B.索引
C.字典
D.作業(yè)控制塊

30.為保證文件的安全，操作系統(tǒng)一般采用多種方式來保護(hù)文件。為防止未經(jīng)授權(quán)對(duì)文件的訪問而造成的篡改或破壞，所采取的方法是(     )。

A.訪問控制列表
B.轉(zhuǎn)儲(chǔ)備份
C.加密數(shù)據(jù)
D.口令保護(hù)

31.CPU輸出數(shù)據(jù)的速度遠(yuǎn)遠(yuǎn)高于打印機(jī)的打印速度，為解決這一矛盾，可采用的技術(shù)是 (     )。

A.并行技術(shù)
B.通道技術(shù)
C.緩沖技術(shù)
D.虛存技術(shù)

32.在不同網(wǎng)絡(luò)節(jié)點(diǎn)的對(duì)等層之間通信需要的是(     )。

A.模塊接El
B.對(duì)等層協(xié)議
C.電信號(hào)
D.傳輸介質(zhì)

33.關(guān)于數(shù)據(jù)交換，下列敘述不正確的是(     )。

A.線路交換面向連接
B.分組交換比報(bào)文交換具有更好的網(wǎng)絡(luò)響應(yīng)速度
C.報(bào)文交換無存儲(chǔ)轉(zhuǎn)發(fā)過程
D.分組交換有存儲(chǔ)轉(zhuǎn)發(fā)過程

34.當(dāng)DHCP客戶計(jì)算機(jī)第一次啟動(dòng)或初始化IP時(shí)，廣播發(fā)送給本地子網(wǎng)的消息是(     )。

A.DHCP DISCOVER
B.DHCP REQUEST
C.DHCP OFFER
D.DHCP ACK

35.網(wǎng)絡(luò)由6個(gè)路由器互連而成，路由器之間的鏈路費(fèi)用如下圖所示，從PC機(jī)到服務(wù)器的最短路徑和通路費(fèi)用是(     )。
  

A.1→3→6，7
B.1→4→5→6，4
C.1→4→3一→6，6
D.1→2→4→5→6，7

36.一個(gè)B類網(wǎng)絡(luò)的子網(wǎng)掩碼為255．255．252．0，則該B類網(wǎng)絡(luò)的主機(jī)數(shù)目是(     )。

A.2046
B.1022
C.5 10
D.1 28

37.在TCP報(bào)文段的報(bào)頭中，窗口字段的作用是(     )。

A.報(bào)頭中32bit字節(jié)的數(shù)量
B.說明對(duì)方端口的數(shù)量
C.控制對(duì)方的發(fā)送流量
D.說明網(wǎng)絡(luò)的負(fù)荷能力

38.關(guān)于以太網(wǎng)交換機(jī)，下面的論述中不正確的是(     )。

A.交換機(jī)工作在數(shù)據(jù)鏈路層
B.交換機(jī)的每個(gè)端口形成一個(gè)沖突域
C.交換機(jī)支持多端口同時(shí)收發(fā)數(shù)據(jù)
D.交換機(jī)是一種多端口中繼器

39.一臺(tái)主機(jī)要解析www．a(chǎn)bc．edu．cn的IP地址，如果這臺(tái)主機(jī)配置的域名服務(wù)器為202．120．66．68，因特網(wǎng)頂級(jí)域名服務(wù)器為11．2．8．6，而存儲(chǔ)www．a(chǎn)bc．edu．cn 其IP地址對(duì)應(yīng)關(guān)系的域名服務(wù)器為202．113．16．10，那么這臺(tái)主機(jī)解析該域名通常首先查詢的服務(wù)器是(     )。

A.202．120．66．68域名服務(wù)器
B.11．2．8．6域名服務(wù)器
C.202．113．16．10域名服務(wù)器
D.不能確定，可從這三個(gè)域名服務(wù)器中任選一個(gè)

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

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

0. 已知一組關(guān)鍵字為(26，36，41，38，44，1 5，68，12，6，51，25)，用鏈地址法解決沖突。
假設(shè)裝填因子a=0．75，散列函數(shù)的形式為H(K)=K MOD P，回答下列問題：
  (1)構(gòu)造散列函數(shù)；
  (2)畫出散列表；
  (3)計(jì)算出等概率情況下查找成功的平均查找長度；
  (4)計(jì)算出等概率情況下查找不成功的平均查找長度。

1. 已知L為沒有頭結(jié)點(diǎn)的單鏈表中第一個(gè)結(jié)點(diǎn)的指針，每個(gè)結(jié)點(diǎn)數(shù)據(jù)域存放一個(gè)字符，該字符可能是英文字母字符或數(shù)字字符或其它字符，編寫算法構(gòu)造三個(gè)以帶頭結(jié)點(diǎn)的單循環(huán)鏈表表示的線性表，使每個(gè)表中只含同一類字符。(要求用最少的時(shí)間和最少的空間)。

2. 下圖所示的CPU邏輯框圖中，有兩條獨(dú)立的總線和兩個(gè)獨(dú)立的存儲(chǔ)器。已知指令存儲(chǔ)器IM最大容量為16384字(字長18位)，數(shù)據(jù)存儲(chǔ)器DM最大容量是65536字(字長1 6位)。各寄存器均有“打入”(R_in)“送出”(R_out/)控制命令，但圖中未標(biāo)出。
  
  (1)指出下列寄存器的位數(shù)：
  程序計(jì)數(shù)器PC，指令寄存器IR，累加器AC₀、AC₁，通用寄存器R₀～R₃，指令存儲(chǔ)器地址寄存器IAR，指令存儲(chǔ)器數(shù)據(jù)存儲(chǔ)器IDR，數(shù)據(jù)存儲(chǔ)器地址寄存器DAR，數(shù)據(jù)存儲(chǔ)器數(shù)據(jù)寄存器DDR。
  (2)設(shè)機(jī)器指令格式為
  
  加法指令可寫為“ADD X(R_i)”，其功能是(AC₀)+((R_i)+X)→AC₁，其中((R_i)+X)部分通過尋址方式指向數(shù)據(jù)存儲(chǔ)器DM?，F(xiàn)取R_i為R₁。畫出ADD指令的指令周期流程圖，寫明“數(shù)據(jù)通路”和相應(yīng)的微操作控制信號(hào)。

3. 設(shè)某計(jì)算機(jī)有四級(jí)中斷A、B、C、D，其硬件排隊(duì)優(yōu)先級(jí)次序?yàn)锳>B>C>D。下表列出了執(zhí)行每級(jí)中斷服務(wù)程序所需的時(shí)間。
  
  如果以執(zhí)行中斷服務(wù)程序的時(shí)間作為確定中斷優(yōu)先級(jí)的尺度：時(shí)間越短優(yōu)先級(jí)越高。
  (1)請(qǐng)指出如何為各級(jí)中斷服務(wù)程序設(shè)置屏蔽碼?
  (2)如果A、B、C、D分別在6μs、8μs、10μs、0μs時(shí)刻發(fā)出中斷請(qǐng)求，請(qǐng)畫出CPU執(zhí)行中斷服務(wù)程序的序列。
  (3)基于上題，請(qǐng)計(jì)算上述四個(gè)中斷服務(wù)程序的平均執(zhí)行時(shí)間。

4. 某大學(xué)的閱覽室共有300個(gè)座位，同學(xué)進(jìn)入時(shí)必須先在管理處用學(xué)生證換取座位牌，若座位滿了，同學(xué)就要在閱覽室外等候。當(dāng)有同學(xué)離開時(shí)，要到管理處用座位牌換回學(xué)生證。請(qǐng)畫出流程圖，試用一種類語言，利用信號(hào)量和P、V操作，描述同學(xué)進(jìn)入和離開閱覽室的過程。

5. 某虛擬存儲(chǔ)系統(tǒng)中有一個(gè)進(jìn)程共有6頁(0～5)，其中代碼占3頁(0～2)，數(shù)據(jù)占1頁(3)，數(shù)據(jù)堆占1頁(4)，用戶棧占1頁(5)。它們依次存放在外存的22，23，25，26存儲(chǔ)塊。當(dāng)前，代碼頁已經(jīng)分配在物理內(nèi)存的66，67，87頁，數(shù)據(jù)頁為31，并已經(jīng)進(jìn)行了修改。數(shù)據(jù)堆頁還沒有分配內(nèi)存，用戶棧分配在01頁。請(qǐng)問：
  (1)頁表中應(yīng)該包含哪些項(xiàng)目?請(qǐng)?zhí)顚懘隧摫?見下表)。
  (2)若內(nèi)存堆申請(qǐng)內(nèi)存，因無分配物理內(nèi)存而產(chǎn)生缺頁中斷，此時(shí)內(nèi)存無空閑頁面，則采用LRU頁面淘汰算法選中內(nèi)存的那個(gè)頁面?操作系統(tǒng)作何處理?頁表又如何變化?設(shè)當(dāng)前時(shí)刻為虛擬時(shí)間1256。 。
  

6. 主機(jī)A向主機(jī)B連續(xù)發(fā)送了兩個(gè)TCP報(bào)文段，其序號(hào)分別為70和100。試問：
  (1)第一個(gè)報(bào)文段攜帶了多少個(gè)字節(jié)的數(shù)據(jù)?
  (2)主機(jī)B收到第一個(gè)報(bào)文段后發(fā)回的確認(rèn)中的確認(rèn)號(hào)應(yīng)當(dāng)是多少?
  (3)如果主機(jī)B收到第二個(gè)報(bào)文段后發(fā)回的確認(rèn)中的確認(rèn)號(hào)是180，試問A發(fā)送的第二個(gè)報(bào)文段中的數(shù)據(jù)有多少字節(jié)?
  (4)如果A發(fā)送的第一個(gè)報(bào)文段丟失了，但第二個(gè)報(bào)文段到達(dá)了B。B在第二個(gè)報(bào)文段到達(dá)后向A發(fā)送確認(rèn)。試問這個(gè)確認(rèn)號(hào)應(yīng)為多少?