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

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

0.在一個(gè)雙向鏈表中，在*p結(jié)點(diǎn)之后插入結(jié)點(diǎn)*q的操作是(     )。

A.q->prior=p；p->next=q；p->next一>prior=q；q->next=p->next；
B.q->next=p->next；p->next->prior=q；p->next=q；q->prior=p；
C.p->next=q；q->prior=p；q->next=p->next；p->next->prior=q；
D.p->next->prior=q；q->next=p->next；q->prior=p；p->next=q；

1.設(shè)線性表中有2n個(gè)元素，以下操作中，在單鏈表上實(shí)現(xiàn)要比在順序表上實(shí)現(xiàn)效率更高的是 (     )。

A.刪除指定元素
B.在最后一個(gè)元素的后面插入一個(gè)新元素
C.順序輸出前k個(gè)元素
D.交換第i個(gè)元素和2n—i一1個(gè)元素的值(i=0，1…．，n一1)

2.設(shè)數(shù)組S[n]作為兩個(gè)棧S₁和S₂的存儲(chǔ)空間，對(duì)任何一個(gè)棧只有當(dāng)S[n]全滿時(shí)才不能進(jìn)行進(jìn)棧操作。為這兩個(gè)棧分配空間的最佳方案是(     )。

A．S₁的棧底位置為O，S₂的棧底位置為n一1
B．S₁的棧底位置為O，S₂的棧底位置為n／2
C．S₁的棧底位置為O，S₂的棧底位置為n
D．S₁的棧底位置為0，S₂的棧底位置為1

3.若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和f．ront的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和Iront的值分別是(     )。

A.1和5
B.2和4
C.4和2
D.5和1

4.利用逐點(diǎn)插入建立序列(50，72，43，85，75，20，35，45，65，30)對(duì)應(yīng)的二叉排序樹(shù)以后，要查找元素30要進(jìn)行元素間的比較次數(shù)是(     )。

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

5.將有關(guān)二叉樹(shù)的概念推廣到三叉樹(shù)，則一棵有244個(gè)結(jié)點(diǎn)的完全三叉樹(shù)的高度是(     )。

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

6.在一個(gè)具有n(n>0)個(gè)頂點(diǎn)的連通無(wú)向圖中，至少需要的邊數(shù)是(     )。

A.n
B.n+1
C.n一1
D.n／2

7.已知一個(gè)線性表(38，25，74，63，52，48)，假定采用散列函數(shù)h(key)=key％7計(jì)算散列地址，并散列存儲(chǔ)在散列表A[0．．6]中，若采用線性探測(cè)方法解決沖突，則在該散列表上進(jìn)行等概率成功查找的平均查找長(zhǎng)度為(     )。

A.1．5
B.1．7
C.2
D.2.3

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

A.37／12
B.62／13
C.39／12
D.49／13

9.下列排序算法中不能保證每趟排序至少能將一個(gè)元素放到其最終的位置上的是(     )。

A.快速排序
B.希爾排序
C.堆排序
D.起泡排序

10.若要求盡可能快地對(duì)序列進(jìn)行穩(wěn)定的排序，則應(yīng)選的是(     )。

A.快速排序
B.歸并排序
C.起泡排序
D.堆排序

11.計(jì)算機(jī)系統(tǒng)的層次結(jié)構(gòu)，下列五個(gè)級(jí)別機(jī)器由下到上的順序是(     )。
  I．機(jī)器語(yǔ)言機(jī)器； Ⅱ．匯編語(yǔ)言機(jī)器；  Ⅲ．高級(jí)語(yǔ)言機(jī)器；
  Ⅳ．微程序控制機(jī)器 V．操作系統(tǒng)機(jī)器；

A.I→Ⅱ→Ⅲ→Ⅳ→V
B.Ⅳ→I→V→Ⅱ→Ⅲ
C.Ⅲ→Ⅱ→V→I→Ⅳ
D.V→Ⅳ→Ⅲ→Ⅱ→I

12.已知定點(diǎn)整數(shù)x的補(bǔ)碼為1 x₃x₂x₁x₀，且x>-8，則必是(     )。

A.x₃=1，x₂～x₀至少有一個(gè)1
B.x₃=0，x₂~x₀至少有一個(gè)1
C.x₃=1，x₂～x₀任意
D.x₃=0，x₂～x₀任意

13.在規(guī)格化浮點(diǎn)運(yùn)算中，若某浮點(diǎn)數(shù)為2⁵×1．10101，其中尾數(shù)為補(bǔ)碼表示，則該數(shù)是(     )。

A.不需規(guī)格化
B.需右移規(guī)格化
C.需將尾數(shù)左移一位規(guī)格化
D.需將尾數(shù)左移兩位規(guī)格化

14.漢字“啊”的十進(jìn)制區(qū)位碼為“16-01”，它的十六進(jìn)制機(jī)內(nèi)碼是(     )。

A.1601H
B.9081H
C.BOA1H
D.B081H

15.在一個(gè)按字節(jié)編址的計(jì)算機(jī)中，若數(shù)據(jù)在存儲(chǔ)器中以小端方案存放。假定int型變量i的地址為08000000H，i的機(jī)器數(shù)為01234567 H，地址：08000000H單元的內(nèi)容是(     )。

A.01 H
B.23 H
C.45 H
D.67 H

16.在CPU的狀態(tài)寄存器中，若符號(hào)標(biāo)志為“1”，表示運(yùn)算結(jié)果是(     )。

A.正
B.負(fù)
C.零
D.不一定

17.在微程序控制器設(shè)計(jì)中，假設(shè)微命令采用最短編碼法，需產(chǎn)生N種微操作。則微命令控制字段要設(shè)置的位數(shù)是(     )。
  

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

18.下列是有關(guān)馮.諾依曼結(jié)構(gòu)計(jì)算機(jī)中指令和數(shù)據(jù)存放位置的敘述，其中正確的是(     )。

A.指令存放在內(nèi)存中，數(shù)據(jù)存放在外存中
B.指令和數(shù)據(jù)任何時(shí)候都存放在內(nèi)存中
C.指令和數(shù)據(jù)任何時(shí)候都存放在外存中
D.程序被啟動(dòng)前指令和數(shù)據(jù)都存放在外存中，而啟動(dòng)后指令和數(shù)據(jù)被裝入內(nèi)存

19.在讀寫(xiě)硬盤(pán)的一個(gè)物理記錄塊時(shí)，不需要的參數(shù)是(     )。

A.柱面(磁道)號(hào)
B.盤(pán)片(磁頭)
C.簇號(hào)
D.扇區(qū)號(hào)

20.有效容量為128KB的Cache，每塊1 6字節(jié)，8路組相聯(lián)。字節(jié)地址為1 2345 67 H的單元調(diào)入該Cache，其Tag應(yīng)是(     )。

A.1234H
B.2468H
C.048DH
D.12345 H：

21.中斷的概念是(     )。

A.暫停正在運(yùn)行的程序
B.暫停對(duì)內(nèi)存的訪問(wèn)
C.暫停CPU運(yùn)行
D.I／O設(shè)備的輸入或輸出

22.在操作系統(tǒng)的以下功能中，不需要硬件支持的是(     )。

A.中斷系統(tǒng)
B.時(shí)鐘管
C.地址映射
D.頁(yè)面調(diào)度

23.在單處理機(jī)的多進(jìn)程系統(tǒng)中，進(jìn)程什么時(shí)候占用處理機(jī)以及決定占用時(shí)間的長(zhǎng)短是 (     )。

A.進(jìn)程相應(yīng)的代碼長(zhǎng)度
B.進(jìn)程總共需要運(yùn)行的時(shí)間
C.進(jìn)程特點(diǎn)和進(jìn)程調(diào)度策略
D.進(jìn)程完成什么功能

24.系統(tǒng)產(chǎn)生死鎖的可能原因是(     )。

A.共享資源分配不當(dāng)
B.系統(tǒng)資源不足
C.進(jìn)程運(yùn)行太快
D.CPU內(nèi)核太多

25.下列選項(xiàng)中，降低進(jìn)程優(yōu)先級(jí)的合理時(shí)機(jī)是(     )。

A.進(jìn)程時(shí)間片用完
B.進(jìn)程剛完成I／O，進(jìn)入就緒隊(duì)列
C.進(jìn)程長(zhǎng)期處于就緒隊(duì)列
D.進(jìn)程從就緒狀態(tài)轉(zhuǎn)換為運(yùn)行狀態(tài)

26.在某計(jì)算機(jī)中采用了多級(jí)存儲(chǔ)體系，設(shè)計(jì)有cache，主存和磁盤(pán)，假設(shè)訪問(wèn)cache一個(gè)字需要花費(fèi)10ns，若該字不在cache p但是存在在主存中，那么需要100ns載2k cache，然后重新開(kāi)始定位。若該字既不在cache中，也不在主存中，那么需要10ms的時(shí)間裝入主存，再化100ns復(fù)制到cache，再開(kāi)始定位。設(shè)cache的命中率為0．90，主存的命中率為0．75，那么，該系統(tǒng)訪問(wèn)一個(gè)字的平均時(shí)間是(     )。

A.25000ns
B.250023ns
C.250017ns
D.250020ns

27.在一個(gè)采用請(qǐng)求式調(diào)頁(yè)的虛擬存儲(chǔ)系統(tǒng)中，存放在外存上的程序代碼調(diào)入內(nèi)存的時(shí)機(jī)是(     )。

A.在進(jìn)程創(chuàng)建填寫(xiě)進(jìn)程表時(shí)
B.在進(jìn)程創(chuàng)建分配內(nèi)存時(shí)
C.在進(jìn)程被調(diào)度占用處理機(jī)執(zhí)行時(shí)
D.在每次產(chǎn)生缺頁(yè)中斷時(shí)

28.為了防止各種意外可能破壞文件，文件系統(tǒng)保護(hù)文件的方法可以是(     )。

A.為文件加密
B.對(duì)每個(gè)文件規(guī)定使用權(quán)限
C.建立副本和定時(shí)轉(zhuǎn)儲(chǔ)
D.為文件設(shè)置口令

29.已知某磁盤(pán)的平均轉(zhuǎn)速為r秒／轉(zhuǎn)，平均尋道時(shí)間為T(mén)秒，每個(gè)磁道可以存儲(chǔ)的字節(jié)數(shù)為N，現(xiàn)向該磁盤(pán)讀寫(xiě)b字節(jié)的數(shù)據(jù)，采用隨機(jī)尋道的方法，每道的所有扇區(qū)組成一個(gè)簇，請(qǐng)問(wèn)：平均訪問(wèn)時(shí)間是(     )。

A.b／N*(r+T)
B.b／N*T
C.(b／Nq+T)*r
D.b*T／N+r

30.文件系統(tǒng)中，當(dāng)調(diào)用open()去打開(kāi)一個(gè)文件時(shí)，其主要目的是(     )。

A.把文件內(nèi)容從外存調(diào)入內(nèi)存
B.把文件的控制信息從外存調(diào)入內(nèi)存
C.把文件系統(tǒng)的文件分配表調(diào)入內(nèi)存
D.把文件系統(tǒng)的目錄調(diào)入內(nèi)存

31.在下列事件中，哪個(gè)不是設(shè)備分配中應(yīng)該考慮的問(wèn)題(     )。

A.及時(shí)性
B.設(shè)備的固有屬性
C.設(shè)備的無(wú)關(guān)性
D.安全性

32.OSI模型中完成路徑選擇功能的層次是(     )。

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

33.現(xiàn)采用調(diào)相與調(diào)幅相結(jié)合的調(diào)制方式，載波有四種相位變化和兩種振幅變化，調(diào)制速率是600波特，那么數(shù)據(jù)速率是(     )。

A.1 200bps
B.1 800bps
C.2400bps
D.3 600bps

34.在CSMA／CD協(xié)議中，下列指標(biāo)與沖突時(shí)間沒(méi)有關(guān)系的是(     )。

A.檢測(cè)一次沖突所需的最長(zhǎng)時(shí)間
B.最小幀長(zhǎng)度
C.最大幀長(zhǎng)度
D.最大幀碎片長(zhǎng)度

35.CSMA／CD以太網(wǎng)中，發(fā)生沖突后，重發(fā)前的退避時(shí)間最大是(     )。

A.65536個(gè)時(shí)間片
B.65535個(gè)時(shí)間片
C.1024個(gè)時(shí)間片
D.1023個(gè)時(shí)間片

36.IEEE 802．11采用了CSMA／CA協(xié)議，下面關(guān)于這個(gè)協(xié)議的描述中錯(cuò)誤的是(     )。

A.各個(gè)發(fā)送站在兩次幀間隔(IFS)之間進(jìn)行競(jìng)爭(zhēng)發(fā)送
B.每一個(gè)發(fā)送站維持一個(gè)后退計(jì)數(shù)器并監(jiān)聽(tīng)網(wǎng)絡(luò)上的通信
C.各個(gè)發(fā)送站按業(yè)務(wù)的優(yōu)先級(jí)獲得不同的發(fā)送機(jī)會(huì)
D.CSMA／CA協(xié)議適用于突發(fā)性業(yè)務(wù)

37.局域網(wǎng)交換機(jī)首先完整地接收數(shù)據(jù)幀，并進(jìn)行差錯(cuò)檢測(cè)。如果正確，則根據(jù)幀目的，則根據(jù)目的地址確定輸出端口號(hào)再轉(zhuǎn)發(fā)出去。這種交換方式是(     )。

A.直接交換
B.改進(jìn)直接交換
C.存儲(chǔ)轉(zhuǎn)發(fā)交換
D.查詢交換

38.在TCP協(xié)議中，建立連接時(shí)被置為1的標(biāo)志位和所處的字段是(     )。

A.保留，ACK
B.保留，SYN
C.偏移，ACK
D.控制，SYN

39.下列協(xié)議中，用于解決電子郵件中傳輸多語(yǔ)言文字和附件問(wèn)題的協(xié)議是(     )。

A.MIME
B.SMTP
C.SNMP
D.POP3

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

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

0. 對(duì)于下圖G，按下列條件試分別寫(xiě)出從頂點(diǎn)0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列和按廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列。
  (1)假定它們均采用鄰接矩陣表示；
  (2)假定它們均采用鄰接表表示，并且假定每個(gè)頂點(diǎn)鄰接表中的結(jié)點(diǎn)是按頂點(diǎn)序號(hào)從大到小的次序鏈接的。
  

1. 一棵二叉樹(shù)的繁茂度定義為R層結(jié)點(diǎn)數(shù)的最大值與樹(shù)的高度的乘積。編寫(xiě)一個(gè)算法求二叉樹(shù)的繁茂度。

2. (11分)某圖形顯示器的分辨率為640×480，刷新頻率為50Hz，且假定水平回掃期和垂直回掃期各占水平掃描周期和垂直掃描周期的20％，試計(jì)算圖形顯示器的行頻、水平掃描周期、每個(gè)像素的讀出時(shí)間和視頻帶寬。若分辨率提高到1024×768，刷新頻率提高到60Hz，再次計(jì)算圖形顯示器的行頻、水平掃描周期、每個(gè)像素的讀出時(shí)間和視頻帶寬。

3. 一臺(tái)模型機(jī)共有7條指令，主頻25MHz，各指令的使用頻率與CPI如下表所示，該機(jī)有8位和16位兩種指令字長(zhǎng)，采用2—4擴(kuò)展操作碼。8位字長(zhǎng)指令為寄存器一寄存器(R—R)二地址類型，1 6位字長(zhǎng)指令為寄存器～存儲(chǔ)器(R—M)二地址變址類型(地址碼范圍在一128～127之間)。
  (1)計(jì)算該機(jī)的MIPS速率。
  (2)計(jì)算操作碼的平均碼長(zhǎng)。
  (3)設(shè)計(jì)該機(jī)的兩種指令格式，標(biāo)出各字段位數(shù)并給出操作碼編碼。
  (4)該機(jī)允許使用多少個(gè)可編址的通用寄存器，多少個(gè)變址寄存器?
  (5)如何計(jì)算存儲(chǔ)器有效地址?
  

4. 假設(shè)有8個(gè)記錄A、B，C、D、E、F、G、H存放在磁盤(pán)里，每個(gè)磁道有8個(gè)扇區(qū)，正好可以存放8個(gè)記錄。假設(shè)磁盤(pán)旋轉(zhuǎn)速度為20ms／r，處理程序每讀出一個(gè)記錄后，用2ms的 時(shí)間進(jìn)行處理，請(qǐng)問(wèn)：
  (1)當(dāng)記錄A、B、C、D、E、F、G、H按順序放在磁道上時(shí)，順序處理這5個(gè)記錄花費(fèi)的總時(shí)間是多少?假設(shè)啟動(dòng)時(shí)的位置正好在A扇區(qū)的起點(diǎn)。
  (2)如何采取優(yōu)化方法，使處理這些記錄所花費(fèi)的總時(shí)間最短?求出該最短時(shí)間。

5. 在某個(gè)操作系統(tǒng)中，通過(guò)大量的實(shí)驗(yàn)，人們觀察到在兩次缺頁(yè)中斷之間執(zhí)行的指令數(shù)與分配給程序的頁(yè)框數(shù)成正比，即可用內(nèi)存加倍，缺頁(yè)中斷的平均間隔也加倍。整體缺頁(yè)次數(shù)減少約一半。假設(shè)一條普通指令需要100ns，但若發(fā)生了缺頁(yè)中斷就需要1ms。一個(gè)程序運(yùn)行了60s，期間發(fā)生了1 500次缺頁(yè)中斷，如果該程序的可用內(nèi)存增加到原來(lái)的2倍，那么，請(qǐng)計(jì)算，此時(shí)這個(gè)程序運(yùn)行需要多少時(shí)間?

6. 下面是給出的一段IP數(shù)據(jù)包頭所包含的數(shù)據(jù)，00 00 30 52 52 40 00 80 06 2C 23 C0 A8 01 01 D8 03 E2 15，請(qǐng)根據(jù)IPv4頭部格式回答如下問(wèn)題：
  (1)該IP包的發(fā)送主機(jī)和接收主機(jī)的地址分別是什么?
  (2)該IP包的總長(zhǎng)度是多少?頭部長(zhǎng)度是多少?
  (3)該IP分組有分片嗎?如果有分片它的分片偏移量是多少?
  (4)該IP包是由什么傳輸層協(xié)議發(fā)出的?