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

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

0.若某線性表中最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)，則下面最合適的存儲(chǔ)方式是(     )。

A.單鏈表
B.循環(huán)雙鏈表
C.單循環(huán)鏈表
D.帶有尾指針的單循環(huán)鏈表

1.表長為n的順序存儲(chǔ)的線性表，當(dāng)在任何位置上刪除一個(gè)元素的概率相等時(shí)，刪除一個(gè)元素所需移動(dòng)元素的平均個(gè)數(shù)為(     )。

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

2.在下面的應(yīng)用中，通常使用棧的是(     )。
  I．遞歸調(diào)用  Ⅱ．括號(hào)匹配  Ⅲ．表達(dá)式求值

A. I、Ⅱ
B.Ⅱ、Ⅲ
C. I、Ⅲ
D. I、Ⅱ、Ⅲ

3.用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)，下面正確的是(     )。

A.僅修改頭指針
B.僅修改尾指針
C.頭、尾指針都要修改
D.頭、尾指針可能都要修改

4.用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)，下面正確的是(     )。

A.30，36
B.38，48，28
C.48，18，38，28
D.60，30，50，40，38，36 ‘

5.在含有1 5個(gè)結(jié)點(diǎn)的平衡二叉樹上，查找關(guān)鍵字為28(存在該結(jié)點(diǎn))的結(jié)點(diǎn)，則依次比較的關(guān)鍵字有可能是(     )。

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

6.設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1則T中的葉子數(shù)是 (     )。

A.B[18]
B.B[19]
C.B[20]
D.B[21]

7.以下關(guān)于圖的說法正確的是(     )。  ．
  I在一個(gè)有向圖的拓?fù)湫蛄兄?，若頂點(diǎn)a在頂點(diǎn)b之前，則圖中必有一條弧<a，b>
  Ⅱ若一個(gè)有向圖的鄰接矩陣中對角線一下元素均為O，則該圖的拓?fù)湫蛄斜囟ù嬖?br/>  Ⅲ在．AOE網(wǎng)中一定只有一條關(guān)鍵路徑

A.I、Ⅱ
B.Ⅱ、Ⅲ
C.I、Ⅲ
D.僅有Ⅱ

8.設(shè)無向圖G=(V，E)和G’=(V’，E’)，如果G’是G的生成樹，則下面說法中錯(cuò)誤的是 (     )。

A.G’是G的子圖
B.G’是G的連通分量
C.G’是G的極小連通子圖且V=V’
D.G’是G的一個(gè)無環(huán)子圖

9.設(shè)無向圖G=(V，E)和G’=(V’，E’)，如果G’是G的生成樹，則下面說法中錯(cuò)誤的是 (     )。

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

10.下列排序算法中，時(shí)間復(fù)雜度為O(nlogn)且占用額外空間最少的是(     )。

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

11.某計(jì)算機(jī)的時(shí)鐘頻率為400MHz，測試該計(jì)算機(jī)的程序使用4種類型的指令。每種指令的數(shù)量及所需指令時(shí)鐘數(shù)(CPI)如下表所示，則該計(jì)算機(jī)的運(yùn)算速度是(     )。
  

A.106．7
B.169．5
C.207.3
D.216.2

12.在補(bǔ)碼表示的機(jī)器中，若寄存器A中原存的數(shù)為9EH，現(xiàn)存的數(shù)為CFH，則表明執(zhí)行的一條指令是(     )。

A.算術(shù)左移
B.邏輯左移
C.算術(shù)右移
D.邏輯右移

13.計(jì)算機(jī)在進(jìn)行浮點(diǎn)數(shù)的相加(減)運(yùn)算之前先進(jìn)行對階操作，若x的階碼大于y的階碼，則應(yīng)將(     )。

A.x的階碼縮小至與y的階碼相同，且使x的尾數(shù)部分進(jìn)行算術(shù)左移
B.x的階碼縮小至與y的階碼相同，且使x的尾數(shù)部分進(jìn)行算術(shù)右移
C.y的階碼擴(kuò)大至與x的階碼相同，且使y的尾數(shù)部分進(jìn)行算術(shù)左移
D.y的階碼擴(kuò)大至與x的階碼相同，且使y的尾數(shù)部分進(jìn)行算術(shù)右移

14.在4位有效信息上增加3位校驗(yàn)位后得到碼長7位的海明校驗(yàn)碼，它的檢、糾錯(cuò)能力是 (     )。

A.糾一位錯(cuò)或檢兩位錯(cuò)
B.糾一位錯(cuò)且檢兩位錯(cuò)
C.只有檢錯(cuò)能力，沒有糾錯(cuò)能力
D.只有糾錯(cuò)能力，沒有檢錯(cuò)能力

15.某32位計(jì)算機(jī)的Cache容量為16KB，Cache塊的大小為16B，若主存與Cache地址映像采用直接映像方式，則主存地址為0x1234E8F8的單元裝入Cache的地址是(     )。

A.00010001001 101
B.0100010001 1010
C.1.0100011111e+013
D.1.1010011101e+013

16.設(shè)指令中的地址碼為A，變址寄存器為X，程序計(jì)數(shù)器為PC，則變址間址尋址方式的操作數(shù)有效地址EA是(     )。

A.((PC)+A)
B.((X)+A)
C.(X)+(A)
D.(X)+A

17.下列關(guān)于主存儲(chǔ)器的描述中，正確的是(     )。
  I．CPU訪存時(shí)間由存儲(chǔ)器容量決定
  Ⅱ．ROM和RAM在存儲(chǔ)器中是統(tǒng)一編址的
  Ⅲ．ROM中任意一個(gè)單元可以隨機(jī)訪問
  Ⅳ．DRAM是破壞性讀出，因此需要讀后重寫

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

18.下列關(guān)于主存儲(chǔ)器的描述中，正確的是(     )。
  I．CPU訪存時(shí)間由存儲(chǔ)器容量決定
  Ⅱ．ROM和RAM在存儲(chǔ)器中是統(tǒng)一編址的
  Ⅲ．ROM中任意一個(gè)單元可以隨機(jī)訪問
  Ⅳ．DRAM是破壞性讀出，因此需要讀后重寫

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

19.下面是關(guān)于PCI總線的敘述，其中錯(cuò)誤的是(     )。

A.PCI總線支持64位總線
B.PCI總線的地址總線和數(shù)據(jù)總線是分時(shí)復(fù)用的
C.PCI總線是一種獨(dú)立設(shè)計(jì)的總線，它的性能不受CPU類型的影響
D.PC機(jī)不能同時(shí)使用PCI總線和ISA總線

20.若視頻圖像每幀的數(shù)據(jù)量為6．4MB，幀速率為30幀／秒，則顯示10秒的視頻信息，其原始數(shù)據(jù)量是(     )。

A.64MB
B.192MB
C.640MB
D.1920MB

21.一131的1字節(jié)、2字節(jié)補(bǔ)碼分別是(     )。

A.83H，0083H
B.7DH，F(xiàn)F83H
C.溢出，F(xiàn)F83H
D.溢出，F(xiàn)F7DH

22.在操作系統(tǒng)中引入并發(fā)可以提高系統(tǒng)效率。若有三個(gè)進(jìn)程P1、P2和P3，按照P1、P2到P3的優(yōu)先次序運(yùn)行，采用可搶先式調(diào)度，其運(yùn)行過程如下：
  P1：計(jì)算6ms；I／O 8ms；計(jì)算2ms；
  P2：計(jì)算12ms；I／O 6ms；計(jì)算2ms；
  P3：計(jì)算4ms；I／O 8ms；計(jì)算4ms；
  不計(jì)系統(tǒng)開銷，相比單通道順序運(yùn)行，多道并發(fā)可以節(jié)省的時(shí)間和CPU利用率分別是(     )。

A.14ms；79％
B.1 6ms；83％
C.12ms；75％
D.22ms；100％

23.假設(shè)當(dāng)前計(jì)算機(jī)并發(fā)系統(tǒng)中有一個(gè)用戶進(jìn)程，它的工作流程如下圖所示，再假設(shè)系統(tǒng)只有三個(gè)基本狀態(tài)，用戶進(jìn)程具有最高優(yōu)先級，采用不可搶先時(shí)間片輪轉(zhuǎn)調(diào)度算法，時(shí)間片為20ms，其它進(jìn)程不用磁盤及其它10設(shè)備。則該進(jìn)程運(yùn)行完成所需時(shí)間是(  )。
  

A.85ms
B.140ms
C.105ms
D.110ms

24.支持多道程序設(shè)計(jì)的操作系統(tǒng)在運(yùn)行過程中，不斷會(huì)選擇新進(jìn)程來運(yùn)行，共享CPU資源，但是，下面哪個(gè)不是操作系統(tǒng)選擇新進(jìn)程的直接原因(     )。

A.運(yùn)行進(jìn)程的時(shí)間片用完
B.運(yùn)行進(jìn)程出錯(cuò)
C.運(yùn)行進(jìn)程要等待某一個(gè)事件的發(fā)生
D.有新的進(jìn)程被創(chuàng)建進(jìn)入就緒隊(duì)列

25.下列哪些存儲(chǔ)分配方案可能使系統(tǒng)抖動(dòng)(     )。
  I．動(dòng)態(tài)分區(qū)分配 Ⅱ．簡單頁式 Ⅲ．虛擬頁式 Ⅳ．簡單段頁式 V．簡單段式
  Ⅵ．虛擬段式

A.I和I
B.Ⅲ和Ⅳ
C.V和Ⅵ
D.Ⅲ和Ⅵ

26.某個(gè)計(jì)算機(jī)采用動(dòng)態(tài)分區(qū)來分配內(nèi)存，經(jīng)過一段時(shí)間的運(yùn)行，現(xiàn)在在內(nèi)存中依地址從小到大存在100KB、450KB、250KB、200KB和600KB的空閑分區(qū)。分配指針現(xiàn)指地址起始點(diǎn)，繼續(xù)運(yùn)行還會(huì)有21 2KB、41 7KB、112KB和426KB的進(jìn)程申請使用內(nèi)存，那么，對內(nèi)存充分利用的分配算法是(     )。

A.最先適應(yīng)算法
B.下次適應(yīng)算法
C.最佳適應(yīng)算法
D.最壞適應(yīng)算法

27.在一個(gè)虛擬存儲(chǔ)系統(tǒng)中，假設(shè)主存的容量是128MB，輔存的容量為2GB，處理機(jī)地址寄存器以及地址線位寬32位，在這樣的系統(tǒng)中，虛存的空間最大為(     )。

A.2GB
B.128M
C.128M+2GB
D.4GB

28.下列關(guān)于索引表的敘述中，正確的是(     )。

A.建立索引表的目的之一是為了減少存儲(chǔ)空間
B.索引表中含有索引文件的數(shù)據(jù)及其物理地址
C.對索引文件存取時(shí)，必須先查找索引表
D.索引表中每個(gè)記錄的索引項(xiàng)可以有多個(gè)

29.在下列敘述中，正確的是(     )。

A.在磁帶上的順序文件中插入新紀(jì)錄時(shí)，必須復(fù)制整個(gè)文件
B.由于磁帶的價(jià)格比磁盤便宜，用磁帶實(shí)現(xiàn)索引文件更經(jīng)濟(jì)
C.在磁帶上的順序文件末尾插入新紀(jì)錄時(shí)，不必復(fù)制整個(gè)文件
D.由于磁帶不利于隨機(jī)存儲(chǔ)，故用磁帶來作為備份的介質(zhì)是不合適的

30.操作系統(tǒng)為了管理文件，設(shè)計(jì)了文件控制塊(FCB)，文件控制塊的建立是(     )。

A.在調(diào)用create()時(shí)
B.在調(diào)用open()時(shí)
C.在調(diào)用read()時(shí)
D.在調(diào)用write()時(shí)

31.UNIX系統(tǒng)中，輸入／輸出設(shè)備看作是(     )。

A.普通文件
B.目錄文件
C.索引文件
D.特殊文件

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

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

33.某信道的信號(hào)傳輸速率為2000波特，若想令其數(shù)據(jù)傳輸速率達(dá)到8kbps，則一個(gè)信號(hào)碼元所取的有效離散值個(gè)數(shù)至少是(     )。

A.2
B.4
C.8
D.16

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

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

35.在Internet上有許多協(xié)議，下面的選項(xiàng)中能夠正確表示協(xié)議層次關(guān)系的是(     )。
  

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

36.如果子網(wǎng)1 72．6．32．0／20再劃分為1 72．6．32．0／26，則下面的結(jié)論中正確的是(     )。

A.劃分為1024個(gè)子網(wǎng)
B.每個(gè)子網(wǎng)有64臺(tái)主機(jī)
C.每個(gè)子網(wǎng)有62臺(tái)主機(jī)
D.劃分為2044個(gè)子網(wǎng)

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

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

38.下列關(guān)于TCP和UDP的說法正確的是(     )。

A.兩者都是面向無連接的
B.兩者都是面向連接的
C.TCP是面向連接而UDP是面向無連接的
D.TCP無連接而UDP是面向連接的

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

A.比特，數(shù)據(jù)幀，數(shù)據(jù)包，數(shù)據(jù)段，數(shù)據(jù)
B.數(shù)據(jù)，數(shù)據(jù)段，數(shù)據(jù)包，數(shù)據(jù)幀，比特
C.數(shù)據(jù)包，數(shù)據(jù)段，數(shù)據(jù)，比特，數(shù)據(jù)幀
D.數(shù)據(jù)段，數(shù)據(jù)包，數(shù)據(jù)幀，比特，數(shù)據(jù)

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

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

0. 已知AOE網(wǎng)中頂點(diǎn)v₁，v₂，v₃，……v₇分別表示7個(gè)時(shí)間，有向線段a₁，a₂，a₃，……a₁₀分別表示10個(gè)活動(dòng)，線段旁的數(shù)值表示每個(gè)活動(dòng)花費(fèi)的天數(shù)，如下圖所示。請?zhí)顚懴旅鎯蓚€(gè)表格，并用頂點(diǎn)序列表示出關(guān)鍵路徑，給出關(guān)鍵活動(dòng)。
  

1. 已知在二叉樹中，T為根結(jié)點(diǎn)，*p和*q為二叉樹中兩個(gè)結(jié)點(diǎn)，試編寫求距離它們最近的共同祖先的算法。

2. 試用7418l和門電路實(shí)現(xiàn)一位余3碼加法器。

3. 一個(gè)字節(jié)多路通道連接D₁、D₂、D₃、D₄、D₅共5臺(tái)設(shè)備，這些設(shè)備分別每10μs、30μs、30μs、50μs和75μs向通道發(fā)出一次數(shù)據(jù)傳送的服務(wù)請求，請回答下列問題：
  (1)計(jì)算這個(gè)字節(jié)多路通道的實(shí)際流量和工作周期。
  (2)如果設(shè)計(jì)字節(jié)多路通道的最大流量正好等于通道實(shí)際流量，并假設(shè)對數(shù)據(jù)傳輸率高的設(shè)備，通道響應(yīng)它的數(shù)據(jù)傳送請求的優(yōu)先級也高。5臺(tái)設(shè)備在0時(shí)刻同時(shí)向通道
  發(fā)出第一次傳送數(shù)據(jù)的請求，并在以后的時(shí)間里按照各自的數(shù)據(jù)傳輸率連續(xù)工作。畫出通道分時(shí)為每臺(tái)設(shè)備服務(wù)的時(shí)間關(guān)系圖，并計(jì)算這個(gè)字節(jié)多路通道處理完各臺(tái)設(shè)備的第一次數(shù)據(jù)傳送請求的時(shí)刻。
  (3)從時(shí)間關(guān)系圖上可以發(fā)現(xiàn)什么問題?如何解決這個(gè)問題?

4. 設(shè)某多道程序系統(tǒng)中有用戶使用內(nèi)存1000M，打印機(jī)1臺(tái)。系統(tǒng)采用可變分區(qū)動(dòng)態(tài)分配算法管理內(nèi)存，而對打印機(jī)采用靜態(tài)分配。假設(shè)輸入輸出操作時(shí)間忽略不計(jì)，采用最短剩余時(shí)間優(yōu)先的進(jìn)程調(diào)度算法，進(jìn)程最短剩余時(shí)間相同時(shí)采用先來先服務(wù)的算法，進(jìn)程調(diào)度時(shí)機(jī)選擇在進(jìn)程執(zhí)行結(jié)束或新進(jìn)程創(chuàng)建時(shí)，現(xiàn)有進(jìn)程如下：
  
  假設(shè)系統(tǒng)優(yōu)先分配內(nèi)存低地址區(qū)域，且不允許移動(dòng)，那么，求：
  (1)給出進(jìn)程調(diào)度算法選中進(jìn)程的次序，并說明理由。
  (2)全部進(jìn)程執(zhí)行結(jié)束所用的時(shí)間是多少?

5. 假定某采用頁式虛擬存儲(chǔ)管理的計(jì)算機(jī)系統(tǒng)中，主存儲(chǔ)器容量為1GB，被分為262144塊物理塊，物理塊號(hào)為0，1，2，……，262143。某進(jìn)程的地址空間占4頁，邏輯頁號(hào)為0，1，2，3，被分配到主存儲(chǔ)器的第20，45，101，58號(hào)物理塊中?；卮穑?BR>  (1)內(nèi)存物理地址至少應(yīng)該用多少位字長來表示?
  (2)進(jìn)程每一頁的長度為多少字節(jié)?邏輯地址中的頁內(nèi)地址應(yīng)占用多少位字長?
  (3)把進(jìn)程中每一頁在分到的主存物理塊中的起始地址和結(jié)束地址填入下表：
  

6. 某路由器的IP地址是125．45．23．12，它在以太網(wǎng)上的物理地址為
  2345AB4F67CD，它收到了一個(gè)分組，分組中的目的IP地址是125．11．78．10。
  (1)試給出這個(gè)路由器發(fā)出的ARP請求分組中的各項(xiàng)目。假定不劃分子網(wǎng)。
  (2)假定目的主機(jī)在以太網(wǎng)上的物理地址為AABBA24F67CD，試給出目的主機(jī)發(fā)送的ARP響應(yīng)分組中的各項(xiàng)目。
  (3)將問題1的結(jié)果封裝成數(shù)據(jù)鏈路層的幀，試填充所有的字段。
  (4)將問題2的結(jié)果封裝成數(shù)據(jù)鏈路層的幀，試填充所有的字段。