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

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

0.若一個(gè)棧的輸入序列為1，2，3…n，輸出序列的第一個(gè)元素是i，則第j個(gè)輸出元素是 (     )。

A.i—j一1
B.i—j
C.j—i+1
D.不確定

1.若循環(huán)隊(duì)列以數(shù)組Q[0．．m-1]作為其存儲(chǔ)結(jié)構(gòu)，變量rear表示循環(huán)隊(duì)列中的隊(duì)尾元素的實(shí)際位置，其移動(dòng)按rear=(rear+1)MOD m進(jìn)行，變量length表示當(dāng)前循環(huán)隊(duì)列中的元素個(gè)數(shù)，則循環(huán)隊(duì)列的隊(duì)首元素的實(shí)際位置是(     )。

A.rear-length
B.(rear-length+m)MOD m
C.(1+rear+m-length)MOD m
D.m-length

2.已知有一維數(shù)組A[0．．m*n-1]，若要對(duì)應(yīng)為m行、n列的矩陣，將元素A[k](0≤k<m*n)表示成矩陣的第i行、第j列的元素(0≤i<m，0≤j<n)，則下面的對(duì)應(yīng)關(guān)系是(     )。

A.i=k／n，j=k％m
B.i=k／m，j=k％m
C.i=k／n，j=k％n
D.i=k／m，j=k％n

3.由元素序列(27，1 6，75，38，51)構(gòu)造平衡二叉樹，則首次出現(xiàn)的最小不平衡子樹的根(即離插入結(jié)點(diǎn)最近且平衡因子的絕對(duì)值為2的結(jié)點(diǎn))是(     )。

A.27
B.38
C.5 1
D.75

4.設(shè)結(jié)點(diǎn)x和y是二叉樹中任意的兩個(gè)結(jié)點(diǎn)，在該二叉樹的先序遍歷序列中x在y之前，而在其后序遍歷序列中x在y之后，則x和y的關(guān)系是(     )。

A.x是y的左兄弟
B.x是y的右兄弟
C.x是y的祖先
D.x是y的后裔

5.在一棵完全二叉樹中，其根的序號(hào)為1，下列可判定序號(hào)為p和q的兩個(gè)結(jié)點(diǎn)是否在同一層的正確選項(xiàng)是(     )。
  

A.A
B.B
C.C
D.D

6.若G是一個(gè)具有36條邊的非連通無(wú)向圖(不含自回路和多重邊)，則圖G的結(jié)點(diǎn)數(shù)至少是 (     )。

A.11
B.10
C.9
D.8

7.有一個(gè)長(zhǎng)度為12的有序表，按折半查找法對(duì)該表進(jìn)行查找，在表內(nèi)各元素等概率情況下，查找成功所需的平均比較次數(shù)是(     )。

A.37／12
B.35／12
C.39／12
D.43／12

8.設(shè)有一個(gè)含200個(gè)表項(xiàng)的散列表，用線性探查法解決沖突，按關(guān)鍵碼查詢時(shí)找到一個(gè)表項(xiàng)的平均探查次數(shù)不超過(guò)1．5，則散列表項(xiàng)應(yīng)能夠至少容納的表項(xiàng)的數(shù)目是(     )。

A.400
B.526
C.624
D.676

9.對(duì)于序列(49，38，65，97，76，1 3，27，50)按由小到大進(jìn)行排序，初始步長(zhǎng)d=4的希爾排序法第一趟的結(jié)果的是(     )。

A.49，76，65，13，27，50，97，38
B.13，27，38，49，50，65，76，97
C.97，76，65，50，49，38，27，13
D.49，1 3，27，50，76，38，65，97

10.堆排序分為兩個(gè)階段，其中第一階段將給定的序列建成一個(gè)堆，第二階段逐次輸出堆頂元素。設(shè)給定序列(48，62，35，77，55，14，35，98)，若在堆排序的第一階段將該序列建成一個(gè)堆(大根堆)，那么交換元素的次數(shù)為(     )。

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

11.若存儲(chǔ)周期100內(nèi)秒，每次讀出一個(gè)字節(jié)，則該存儲(chǔ)器的數(shù)據(jù)傳輸率為(     )。

A.32×10⁶位／秒
B.8×10⁶位／秒
C.80Mb／秒
D.80×10⁶位／秒

12.馮.諾依曼機(jī)工作方式的基本特點(diǎn)是(     )。

A.存儲(chǔ)器內(nèi)容選擇地址
B.采用多指令流單數(shù)據(jù)流
C.堆棧操作
D.按地址訪問(wèn)并按順序執(zhí)行指令

13.字長(zhǎng)相同的兩種浮點(diǎn)數(shù)，第一種階碼位數(shù)多，尾數(shù)位數(shù)少，第二種階碼位數(shù)少，尾數(shù)位數(shù)多，階的底數(shù)都是2，則有(     )。

A.它們表示的數(shù)的范圍與精度相同
B.第一種數(shù)的范圍大，但精度低
C.第二種數(shù)的范圍大，精度高
D.第一種數(shù)的范圍大，精度高

14.以下關(guān)于校驗(yàn)碼的敘述中，正確的是(     )。
  I．校驗(yàn)碼的碼距必須大于2
  Ⅱ．校驗(yàn)碼的碼距越大檢錯(cuò)糾錯(cuò)能力越強(qiáng)
  Ⅲ．增加奇偶校驗(yàn)位的位數(shù)可以提高奇偶校驗(yàn)的正確性
  Ⅳ．采用奇偶校驗(yàn)可檢測(cè)出一位數(shù)據(jù)錯(cuò)誤的位置并加以糾正
  V．采用海明校驗(yàn)可檢測(cè)出一位數(shù)據(jù)錯(cuò)誤的位置并加以糾正
  Ⅵ．循環(huán)冗余校驗(yàn)碼是通過(guò)除法運(yùn)算來(lái)建立數(shù)據(jù)和校驗(yàn)位之間的約定關(guān)系的

A.I、Ⅲ、V
B.Ⅱ、Ⅳ、Ⅵ
C.I、V、Ⅵ
D.Ⅱ、V、Ⅵ

15.若內(nèi)存地址區(qū)間為4000H～43FFH，每個(gè)存貯單元可存儲(chǔ)16位二進(jìn)制數(shù)，該內(nèi)存區(qū)域用4片存儲(chǔ)器芯片構(gòu)成，則構(gòu)成該內(nèi)存所用的存儲(chǔ)器芯片的容量是(     )。

A.512×1 6bit
B.256×8bit
C.256×16bit
D.1024×8bit

16.數(shù)據(jù)尋址和指令尋址的不同點(diǎn)在于(     )。

A.前者決定操作數(shù)地址，后者決定程序轉(zhuǎn)移地址
B.前者決定程序轉(zhuǎn)移地址，后者決定操作數(shù)地址
C.前者是短指令，后者是長(zhǎng)指令
D.前者是長(zhǎng)指令，后者是短指令

17.流水計(jì)算機(jī)中，下列語(yǔ)句發(fā)生的數(shù)據(jù)相關(guān)類型是(     )。
  ADD R1，R2，R3；(R2)+(R3)→R1
  ADD R4，R1，R5；(R1)+(R5)→R4

A.寫后讀
B.讀后寫
C.寫后寫
D.讀后讀

18.下列有關(guān)控制器的說(shuō)法正確的是(     )。

A.無(wú)論是組合邏輯控制器和時(shí)序邏輯控制器，都需要有程序計(jì)數(shù)器
B.微程序控制器不需要程序計(jì)數(shù)器，只要有微程序計(jì)數(shù)器
C.都可以不需要程序計(jì)數(shù)器
D.以上都不對(duì)

19.下面是關(guān)于目前流行的PC機(jī)主板的敘述：
  I．主板上通常包含微處理器插座(或插槽)和芯片組
  Ⅱ．主板上通常包含ROM BIOS和存儲(chǔ)器(內(nèi)存條)插座
  Ⅲ．主板上通常包含PCI和AGP總線插槽
  Ⅳ．主板上通常包含IDE連接器
  其中正確的是(     )。

A.僅I
B.僅I和Ⅱ
C.僅I、Ⅱ和Ⅲ
D.I、Ⅱ、Ⅲ和Ⅳ

20.當(dāng)圖像分辨率為800×600，屏幕分辨率為640×480時(shí)，正確的是(     )。

A.屏幕上顯示一幅圖像的64％左右
B.圖像正好占滿屏幕
C.屏幕上顯示一幅完整的圖像
D.圖像只占屏幕的一部分

21.外部設(shè)備打印機(jī)適合于連接的通道是(     )。

A.數(shù)組多路通道
B.字節(jié)多路通道
C.選擇通道
D.任意一種通道

22.在不同類型的操作系統(tǒng)中，批處理操作系統(tǒng)的主要缺點(diǎn)是(     )。

A.CPU利用率低
B.不能并發(fā)執(zhí)行
C.缺少交互性
D.周轉(zhuǎn)時(shí)間太長(zhǎng)

23.下列所示不是信號(hào)量能實(shí)現(xiàn)的功能是(     )。

A.進(jìn)程同步
B.進(jìn)程互斥
C.執(zhí)行的前趨關(guān)系
D.進(jìn)程的并發(fā)執(zhí)行

24.下面是一個(gè)并發(fā)進(jìn)程的程序代碼，正確的說(shuō)法是(     )。
  semaphore x1=x2=y=1；
  int c1：c2=0：
  cobegin
  procedure P1      procedure P2
    P(x1)；         P(x2)；
    if(++cl=1)P(y)；    if(++c2=1)P(y)；
    V(x1)；         V(x2)；
    computer(A)；      computer(B)；
    P(x1)；         P(x2)；
    if(--c1=0)V(y)；    if(--c2=0)V(y)；
    V(x1)；         V(x2)；
   end         end
   coend

A.進(jìn)程不會(huì)死鎖，也不會(huì)饑餓
B.進(jìn)程不會(huì)死鎖，但是會(huì)饑餓
C.進(jìn)程會(huì)死鎖，但是不會(huì)饑餓
D.進(jìn)程會(huì)死鎖，也會(huì)饑餓

25.在操作系統(tǒng)中，要對(duì)并發(fā)進(jìn)程進(jìn)行同步的原因是(     )。

A.進(jìn)程的有限時(shí)間性
B.進(jìn)程具有動(dòng)態(tài)性
C.并發(fā)進(jìn)程推進(jìn)的不確定性
D.進(jìn)程具有結(jié)構(gòu)性

26.操作系統(tǒng)中為實(shí)現(xiàn)多道程序并發(fā)，對(duì)內(nèi)存管理可以有多種方式，其中代價(jià)最小的是(     )。

A.分區(qū)管理
B.分頁(yè)管理
C.分段管理
D.段頁(yè)式管理

27.在一個(gè)請(qǐng)求頁(yè)式的虛擬存儲(chǔ)系統(tǒng)中，每個(gè)頁(yè)面的大小分為4096字節(jié)。如下某個(gè)程序需要將數(shù)組賦值，假設(shè)，執(zhí)行代碼已經(jīng)駐留內(nèi)存，而數(shù)據(jù)頁(yè)面尚未分配，數(shù)組按先行后列存放。請(qǐng)計(jì)算，其缺頁(yè)中斷次數(shù)是(     )。
 int a[1024][1024]；
 int i，j；
 i=0：
 for(j=0；j<=1023；j++)
  a[i][j]=j；

A.2
B.1
C.1024
D.512

28.在頁(yè)式存儲(chǔ)管理系統(tǒng)中選擇頁(yè)面的大小，需要考慮的因素是(     )。
  I．頁(yè)面大的好處是頁(yè)表較小
  Ⅱ．頁(yè)面小的好處是可以減少由內(nèi)碎片引起的內(nèi)存浪費(fèi)
  Ⅲ．通常，影響磁盤訪問(wèn)時(shí)間的主要因素不在于頁(yè)面的大小，所以使用時(shí)可優(yōu)先考慮較大的頁(yè)面

A.I和Ill
B.Ⅱ和Ⅲ
C.I和II
D.I和Ⅱ和Ⅲ

29.磁臂驅(qū)動(dòng)調(diào)度算法中，能夠隨時(shí)改變磁頭運(yùn)動(dòng)方向的算法是(     )。

A.電梯調(diào)度算法
B.掃描算法
C.循環(huán)察看算法
D.最短尋道距離優(yōu)先算法

30.有一個(gè)文件含有10000個(gè)文件塊，若將其順序結(jié)構(gòu)存放，則對(duì)文件塊順序查找的平均時(shí)間為5000個(gè)單位。若按索引順序文件的結(jié)構(gòu)存放，每個(gè)索引為。100個(gè)文件塊，則順序查找次數(shù)是(     )。

A.500
B.100
C.50
D.1 0

31.計(jì)算機(jī)系統(tǒng)中，不屬于DMA控制器的是(     )。

A.命令／狀態(tài)寄存器
B.內(nèi)存地址寄存器
C.數(shù)據(jù)寄存器
D.堆棧指針寄存器

32.在協(xié)議數(shù)據(jù)單元中，控制信息所不包括的內(nèi)容是(     )。

A.地劃L
B.查錯(cuò)碼
C.數(shù)據(jù)
D.協(xié)議控制

33.通過(guò)改變載波信號(hào)的相位值來(lái)表示數(shù)字信號(hào)1、0的方法是(     )。

A.ASK
B.FSK
C.PSK
D.PPP

34.假設(shè)一個(gè)NAT服務(wù)器其公網(wǎng)地址為205．56．79．35，并且有如下的表項(xiàng)，那么當(dāng)一個(gè)IP地址為192．1 68．32．56端口為21分組進(jìn)入公網(wǎng)的時(shí)候，轉(zhuǎn)換后的端口號(hào)和源IP地址是(     )。
  

A.205．56．79．35：2056
B.1 92．168．32．56：2056
C.205．56．79．35：1892
D.205．56．79．35：2256

35.ICMP協(xié)議不具備的功能是(     )。

A.向源主機(jī)發(fā)送網(wǎng)絡(luò)不可達(dá)報(bào)文
B.向路由器發(fā)送回送請(qǐng)求報(bào)文
C.進(jìn)行時(shí)間戳請(qǐng)求
D.獲取主機(jī)IP地址

36.現(xiàn)有一個(gè)長(zhǎng)度為3000B的IP數(shù)據(jù)報(bào)，其IP頭部的長(zhǎng)度為20B，該IP數(shù)據(jù)報(bào)如在最大幀長(zhǎng)度為1518B的以太網(wǎng)中進(jìn)行傳輸，那么為了正確傳輸，需要將其拆分的數(shù)據(jù)報(bào)個(gè)數(shù)是(     )。

A.2
B.3
C.4
D.不必拆分

37.傳輸層用于標(biāo)識(shí)不同的應(yīng)用的是(     )。

A.物理地址
B.端口號(hào)
C.IP地址
D.邏輯地址

38.有關(guān)路由器的描述正確的是(     )。

A.單獨(dú)的廣播域，分開的沖突域
B.分開的廣播域，單獨(dú)的沖突域
C.分開的廣播域，分開的沖突域
D.單獨(dú)的廣播域，單獨(dú)的沖突域

39.DNS作為一種分布式系統(tǒng)，所基于的模式是(     )。

A.C／S模式
B.B／S模式
C.P2P模式
D.以上均不正確

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

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

0. 采用散列函數(shù)H(k)=3×k MOD 13并用線性探測(cè)開放地址法處理沖突，在數(shù)列地址空間[0．．12]中對(duì)關(guān)鍵字序列22，41，5 3，46，30，13，1，67，51；
  (1)構(gòu)造散列表(畫示意圖)；
  (2)裝填因子；
  (3)等概率情況下查找成功的平均查找長(zhǎng)度；
  (4)等概率情況下查找失敗的平均查找長(zhǎng)度。

1. 假設(shè)二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，試設(shè)計(jì)一個(gè)算法，求出該二叉樹中第一條最長(zhǎng)的路徑長(zhǎng)度以及此路徑上各結(jié)點(diǎn)的值。

2. 某微機(jī)的尋址范圍為64KB，其存儲(chǔ)器選擇器信號(hào)為M，接有8片8KB的存儲(chǔ)器，試完成下列問(wèn)題。
  (1)畫出選片譯碼邏輯圖。
  (2)寫出每片RAM的尋址范圍。
  (3)如果運(yùn)行時(shí)發(fā)現(xiàn)不論往哪片存儲(chǔ)器存放8KB數(shù)據(jù)，以4000H起始地址的存儲(chǔ)芯片都有與之相同的數(shù)據(jù)，分析故障原因。
  (4)如果運(yùn)行時(shí)發(fā)現(xiàn)以0000H為起始地址的一片存儲(chǔ)芯片不能讀寫，分析故障原因。
  (5)若發(fā)現(xiàn)譯碼器中的地址線A₁₃與CPU斷線，并搭接到低電平的故障，問(wèn)后果如何?
  (6)如果發(fā)現(xiàn)只能對(duì)第1～4片RAM進(jìn)行讀寫，試分析故障原因。

3. 某模型機(jī)的通路結(jié)構(gòu)如下圖所示，用寄存器傳送語(yǔ)句(如PC→MAR)，擬出下列指令從讀取到執(zhí)行的完整流程。
  (1)數(shù)據(jù)傳送指令MOV X(R₀)，Y(R₁)，源和目的操作數(shù)地址均采用變址尋址，第1個(gè)參數(shù)X為源操作數(shù)的形式地址，第2個(gè)參數(shù)為目的操作數(shù)的形式地址，分別位于指令的第2個(gè)和第3個(gè)存儲(chǔ)字。
  (2)數(shù)據(jù)求反指令COM一(R₀)，采用自減型寄存器間接尋址，結(jié)果送回自減后的地由E單元。
  

4. 某工廠有一個(gè)倉(cāng)庫(kù)可以存放甲、乙兩種零部件，甲零件可以存放m件，乙零件可以存放n件，車間A專門生產(chǎn)甲零件，每次1件，每生產(chǎn)1件存放進(jìn)倉(cāng)庫(kù)1件；車間B專門生產(chǎn)零件乙，每次1件，每生產(chǎn)1件存放進(jìn)倉(cāng)庫(kù)1件?？傃b車間每次從倉(cāng)庫(kù)取出2件甲零件、1件乙零件組裝成成品，車間A、B和總裝車間必須互斥進(jìn)入倉(cāng)庫(kù)。當(dāng)倉(cāng)庫(kù)內(nèi)甲、乙零件分別達(dá)到m、n件時(shí)，車間A、B分別停止生產(chǎn)。而倉(cāng)庫(kù)內(nèi)任何一種零件為0時(shí)，總裝車間停產(chǎn)。根據(jù)上述規(guī)則，請(qǐng)利用信號(hào)量機(jī)制，設(shè)計(jì)一個(gè)可以讓車問(wèn)A、B和總裝車間協(xié)調(diào)運(yùn)轉(zhuǎn)的程序，并說(shuō)明各個(gè)信號(hào)量的意義，用類C語(yǔ)言寫出整個(gè)過(guò)程。

5. 某個(gè)頁(yè)式存儲(chǔ)管理系統(tǒng)，接收了一個(gè)大小一共7頁(yè)的程序，其依次訪問(wèn)的頁(yè)為：1、2、3、4、2、1、5、6、2、1、2、3、7。若分配給該程序的內(nèi)存空間為4頁(yè)，并一次預(yù)裝入，請(qǐng)用先進(jìn)先出(FIFO)調(diào)度算法和最近最少用(lRU)調(diào)度算法計(jì)算，程序執(zhí)行時(shí)會(huì)產(chǎn)生多少次缺頁(yè)中斷?依次寫出被淘汰的頁(yè)號(hào)并計(jì)算缺頁(yè)率。

6. 如圖所示一臺(tái)路由器連接3個(gè)以太網(wǎng)。
  
  請(qǐng)根據(jù)圖中給出的參數(shù)回答如下問(wèn)題：
  (1)該TCP／IP網(wǎng)絡(luò)使用的是哪一類IP地址。
  (2)寫出該網(wǎng)絡(luò)劃分子網(wǎng)后所采用的子網(wǎng)掩碼。
  (3)系統(tǒng)管理員將計(jì)算機(jī)D和E按照?qǐng)D中所示結(jié)構(gòu)連入網(wǎng)絡(luò)并使用所分配的地址對(duì)TCP／IP軟件進(jìn)行常規(guī)配置后，發(fā)現(xiàn)這兩臺(tái)機(jī)器上的網(wǎng)絡(luò)應(yīng)用程序不能夠正常通信。這是為什么?
  (4)如果你在主機(jī)C上要發(fā)送一個(gè)IP分組，使得主機(jī)D和主機(jī)E都會(huì)接收它，而子網(wǎng)3和子網(wǎng)4上的主機(jī)都不會(huì)接收它，那么該IP分組應(yīng)該填寫什么樣的目標(biāo)IP地址?