?計算機專業(yè)（基礎綜合）模擬試卷25

一、1.單項選擇題

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

0.若已知一個棧的入棧序列是1，2，3……．n，其輸出序列為p1，p2，p3……．pn，若p1=n，則pi是(     )。

A.i
B.n-i
C.n-i+1
D.不確定

1.將一個A[1……100，1……100]的三對角矩陣，按行優(yōu)先存入一維數(shù)組B[1．．298]中，A中元素A_66,65(即該元素下標i=66，j=65)，在B數(shù)組中的位置k為(     )。

A.1 98
B.1 95
C.197
D.1 96

2.查找效率最高的二叉排序樹是(     )。

A.所有結(jié)點的左子樹都為空的二叉排序樹
B.所有結(jié)點的右子樹都為空的二叉排序樹
C.平衡二叉樹
D.沒有左子樹的二叉排序樹

3.一棵深度為k的平衡二叉樹，其每個非葉子結(jié)點的平衡因子均為0，則該樹的結(jié)點數(shù)是(     )。

A.2^k-1-1
B.2^k-1
C.2^k-1+1
D.2^k一1

4.以下敘述正確的是(     )。
  I．對有向圖G，如果以任一頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先搜索能訪問到每個頂點，則該圖一定是完全圖
  Ⅱ．連通圖的廣度優(yōu)先搜索中一般要采用隊列來暫存訪問過的頂點
  Ⅲ．圖的深度優(yōu)先搜索中一般要采用棧來暫存訪問過的頂點

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

5.一個含有n個頂點和e條邊的簡單無向圖，在其鄰接矩陣存儲結(jié)構(gòu)中零元素的個數(shù)是(     )。

A.e
B.2e
C.n²-e
D.n²-2e

6.從二叉樹的任一結(jié)點出發(fā)到根的路徑上，所經(jīng)過的結(jié)點序列必按其關鍵字降序排列的是 (     )。

A. 二叉排序樹
B.大頂堆
C.小頂堆
D.平衡二叉樹

7.順序存儲的某線性表共有123個元素，按分塊查找的要求等分為3塊。若對索引表采用順序查找方法來確定子塊，且在確定的子塊中也采用順序查找方法，則在等概率的情況下，分塊查找成功的平均查找長度為(     )。

A.21
B.23
C.41
D.62

8.在下列存儲結(jié)構(gòu)中，數(shù)據(jù)結(jié)構(gòu)中元素的存儲地址與其關鍵字之間存在某種映射關系的是 (     )。

A.樹形存儲結(jié)構(gòu)
B.鏈式存儲結(jié)構(gòu)
C.索引存儲結(jié)構(gòu)
D.散列存儲結(jié)構(gòu)

9.若對27個元素只進行三趟多路歸并排序，則選取的歸并路數(shù)是(     )。

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

10.下列序列中，執(zhí)行第一趟快速排序的結(jié)果是(     )。

A.[da，ax，eb，de，bb]ff[ha，gc]
B.[cd，eb，ax，da]ff[ha，gc，bb]
C.[gc，ax，eb，cd，bb]ff[da，ha]
D.[ax，bb，cd，da]ff[eb，gc，ha]

11.某工作站采用時鐘頻率f為15MHz，處理速率為10MIPS的處理機來執(zhí)行一個已知混合程序。假定每次存儲器存取為1周期延遲，試問此計算機的有效CPI是(     )。

A.2．5
B.2
C.1.5
D.1

12.5位二進制定點小數(shù)，用補碼表示時，最小負數(shù)是(     )。

A.0．11 11
B.1．0001
C.1．11 11
D.1

13.浮點加減中的對階是(     )。

A.將較小的一個階碼調(diào)整到與較大的一個階碼相同
B.將較大的一個階碼調(diào)整到與較小的一個階碼相同
C.將被加數(shù)的階碼調(diào)整到與加數(shù)的階碼相同
D.將加數(shù)的階碼調(diào)整到與被加數(shù)的階碼相同

14.若內(nèi)存按字節(jié)編址，用存儲容量為32K×8比特的存儲器芯片構(gòu)成地址編號A0000H至DFFFFH的內(nèi)存空間，則至少需要的片數(shù)是(     )。

A.4
B.6
C.8
D.10

15.某計算機的存儲系統(tǒng)由Cache一主存系統(tǒng)構(gòu)成，Cache的存取周期為10ns，主存的存取周期為50ns。在CPU執(zhí)行一段程序時，Cache完成存取的次數(shù)為4800次，主存完成的存取次數(shù)為200次，該Cache一主存系統(tǒng)的效率是(     )。

A.0．856
B.0．862
C.0.958
D.0.96

16.對于RISC機和CISC機，以下說法錯誤的是(     )。

A.RISC機的指令條數(shù)比CISC機少
B.RISC機指令的平均字長比CISC機指令的平均字長短
C.對大多數(shù)計算任務來說，RISC機程序所用的指令條數(shù)比CISC機少
D.RISC機和CISC機都在發(fā)展

17.微程序在計算機中存放的位置是(     )。

A.主存儲器
B.控制存儲器
C.通用寄存器
D.指令寄存器

18.下列各敘述中正確的命題是(     )。
  I．在取指周期中也可能從內(nèi)存取到操作數(shù)
  Ⅱ．CPU的訪存時間是由存儲器的容量決定的，存儲容量越大，訪存時間就越長
  Ⅲ．在主存與Cache之間的直接映射方式下，不采用替換策略也可以實現(xiàn)正確的塊替換
  Ⅳ．動態(tài)存儲器的讀操作也具有刷新的功能

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

19.在菊花鏈方式中，靠近控制器的設備與遠處設備的(     )。

A.優(yōu)先級高
B.優(yōu)先級相等
C.優(yōu)先級低
D.不一定

20.RAID利用冗余技術實現(xiàn)高可靠性，其中RAIDl的磁盤利用率是(     )。

A.25％
B.50％
C.75%
D.100%

21.設存儲器容量為32字，字長64位，模塊數(shù)m=4，存儲周期T=200ns，數(shù)據(jù)總線寬度為64位，總線傳送周期τ=50ns。用交叉方式進行組織，交叉存儲器的帶寬是(     )。

A.32×10⁷位／秒
B.8×10⁷位／秒
C.73×10⁷位／秒
D.18×10⁷位／秒

22.操作系統(tǒng)為用戶提供了多種接口，它們是(     )。
  I．計算機高級指令；Ⅱ．終端命令；Ⅲ．圖標菜單；Ⅳ．匯編語言；V．C語言；Ⅵ．系統(tǒng)調(diào)用；

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

23.若一個信號量的初值為3，經(jīng)過多次PV操作以后當前值為一1，此表示等待進入臨界區(qū)的進程數(shù)是(     )。

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

24.利用銀行家算法進行安全序列檢查時，不需要的參數(shù)是(     )。

A.系統(tǒng)資源總數(shù)
B.滿足系統(tǒng)安全的最少資源數(shù)
C.用戶最大需求數(shù)
D.用戶已占有的資源數(shù)

25.若有一進程擁有100個線程，這些線程都屬于用戶級線程，則在系統(tǒng)調(diào)度執(zhí)行時間上占用的時間片是(     )。

A.1
B.100
C.1／100
D.0

26.某計算機采用頁式存儲管理，內(nèi)存中現(xiàn)有1000個頁表項，CPU的cache中可以存放N個頁表項，該系統(tǒng)中，CPU內(nèi)存訪問的時間為lOOns，對cache訪問的時間是5ns，如果希望頁表映射的平均時間降到20ns以下，那么cache中的N必須高于(     )。

A.850
B.858
C.923
D.842

27.分頁系統(tǒng)中的頁面是(     )。

A.用戶所能感知的
B.操作系統(tǒng)所能感知的
C.編譯程序所能感知的
D.鏈接裝配程序所能感知的

28.某操作系統(tǒng)的文件管理采用直接索引和多級索引混合方式，文件索引表共有10項，其中前8項是直接索引項，第9項是一次間接索引項，第10項是二次間接索引項，假定物理塊的大小是1K，每個索引項占用4個字節(jié)，則該文件系統(tǒng)中最大的文件可以達到(     )。

A.65800K
B.65792K
C.65536K
D.34000K

29.設磁盤的IO請求隊列中所要訪問的磁道號為：96，184，25，120，1 2，126，73，75，當前磁頭在96，前一次在90。當采用最短尋道時間優(yōu)先算法(SSTF)和電梯算法所要移動的距離是(     )。

A.618，418
B.306，260
C.306,418
D.618,260

30.UNIX操作系統(tǒng)中，文件的索引結(jié)構(gòu)存放在(     )。

A.超級塊
B.索引節(jié)點
C.目錄項
D.空閑塊

31.在設備管理中，用來實現(xiàn)設備分配的四個數(shù)據(jù)結(jié)構(gòu)中，每個設備一張，描述設備的特性和狀態(tài)，反映設備的特性、設備和控制器的連接情況的數(shù)據(jù)結(jié)構(gòu)是(     )。

A.設備控制表(DCT)
B.系統(tǒng)設備表(SDT)
C.控制器控制表(COCT)
D.通道控制表(CHCT)

32.在OSI參考模型中，第N層和其上的第N+1層的關系是(     )。

A.第N層為第N+1層提供服務
B.第N+1層將從第N層接收的信息增加了一個頭
C.第N層利用第N+1層提供的服務
D.第N層對N+1層沒有任何作用

33.設待傳送數(shù)據(jù)總長度為L位，分組長度為P位，其中頭部開銷長度為H位，源節(jié)點到目的節(jié)點之間．的鏈路數(shù)為h，每個鏈路上的延遲時間為D秒，數(shù)據(jù)傳輸率為B bps，電路交換建立連接的時間為S秒，則傳送所有數(shù)據(jù)，電路交換需時間是(     )。

A.hD+L／B秒
B.S+hD+L／P秒
C.S+hD+L／B秒
D.S+L／B秒

34.若數(shù)據(jù)鏈路的發(fā)送窗口尺寸WT=4，在發(fā)送3號幀、并接到2號幀的確認幀后，發(fā)送方還可連續(xù)發(fā)送的幀數(shù)是(     )。

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

35.TCP／IP網(wǎng)絡中，某主機的IP地址為130．25．3．1 35，子網(wǎng)掩碼為255．255．25 5．1 92，那么該主機所在的子網(wǎng)的網(wǎng)絡地址是(     )。

A.130．25．0．0
B.130．25．3．0
C.130．25．3．128
D.130．25．3．255

36.為了限制路由信息傳播的范圍，OSPF、協(xié)議把網(wǎng)絡劃分成4種區(qū)域(Area)，其中連接各個區(qū)域的傳輸網(wǎng)絡是(     )。

A.不完全存根區(qū)域
B.標準區(qū)域
C.主干區(qū)域
D.存根區(qū)域

37.一臺主機的IP地址為11．1．1．100，子網(wǎng)掩碼為255．0．0．0。現(xiàn)在用戶需要配置該主機的默認路由。經(jīng)過觀察發(fā)現(xiàn)，與該主機直接相連的路由器具有如下4個IP地址和子網(wǎng)掩碼：
  I．IP地址：1 1．1．1．1，子網(wǎng)掩碼：255．0．0．0
  Ⅱ．IP地址：11．1．2．1，子網(wǎng)掩碼：255．0．0．0
  Ⅲ．IP地址：1 2．1．1．1，子網(wǎng)掩碼：255．0．0．0
  Ⅳ．IP地址：13．1．2．1，子網(wǎng)掩碼：255．0．0．0
  請問IP地址和子網(wǎng)屏蔽碼可能是該主機的默認路由的是(     )。

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

38.以太網(wǎng)交換機中的端口／MAC地址映射表是(     )。

A.是由交換機的生產(chǎn)廠商建立的
B.是交換機在數(shù)據(jù)轉(zhuǎn)發(fā)過程中通過學習動態(tài)建立的
C.是由網(wǎng)絡管理員建立的
D.是由網(wǎng)絡用戶利用特殊的命令建立的

39.下面關于電子郵件的說法中，不正確的是(     )。

A.電子郵件只能發(fā)送文本文件
B.電子郵件可以發(fā)送圖形文件
C.電子郵件可以發(fā)送二進制文件
D.電子郵件可以發(fā)送主頁形式的文件

二、2.綜合應用題

綜合應用題
41-47小題，共70分。

0. 已知二叉樹采用二叉鏈表方式存放，要求返回二叉樹T的后序序列中的第一個結(jié)點的指針，是否可不用遞歸且不用棧來完成?請簡述原因。

1. 設有一個帶頭結(jié)點的循環(huán)單鏈表，其結(jié)點值均為正整數(shù)。試設計一個算法，反復找出單鏈表中結(jié)點值最小的結(jié)點，并輸出之，然后將該結(jié)點從中刪除，直到單鏈表空為止，最后再刪除表頭結(jié)點。

2. 什么是單重分組和雙重分組跳躍進位鏈?一個按3，5，3，5分組的雙重分組跳躍進位鏈(最低位為第O位)，試問大組中產(chǎn)生的是哪幾位進位?與4，4，4，4分組的雙重分組跳躍進位鏈相比，試問產(chǎn)生全部進位的時間是否一致?為什么?

3. 某機的主要部件如下圖所示。
  
  (1)請補充各部件間的主要連接線，并注明數(shù)據(jù)流動方向。
  (2)擬出指令SUB(R₁)，一(R₂)的執(zhí)行流程(含取指過程與確定后繼指令地址)。該指令的含義是進行減法操作，源操作數(shù)地址和目的操作數(shù)地址分別在寄存器R₁和R₂中，目的操作數(shù)尋址方式為自減型寄存器間接尋址。
  其中：LA—A輸入選擇器，LB—B輸入選擇器，C、D一暫存器。

4. 實現(xiàn)一個經(jīng)典的“讀者一寫者”算法時，若當前臨界區(qū)中有讀者訪問，寫者再來時必須在臨界區(qū)外面等候，如果其后讀者源源不斷地到達，按策略他們均可以進入臨界區(qū)，始終保持臨界區(qū)中有讀者訪問，那么寫者可能長時間不能進入臨界區(qū)而形成饑餓。為解決此類問題，我們修改訪問策略，要求當寫者到達時，寫者具有優(yōu)先權。具體說，寫者到達后，已經(jīng)在臨界區(qū)內(nèi)的讀者繼續(xù)讀取直到結(jié)束，而后來的讀者就不能進入臨界區(qū)。等所有的讀者離開臨界區(qū)以后讓寫者先進去訪問，然后等寫者離開后再允許讀者進入臨界區(qū)。這所謂“寫者優(yōu)先讀者一寫者’’問題。請用信號量和PV操作來描述這一組進程的工作過程。

5. 某32位計算機系統(tǒng)采用段頁式虛擬存儲管理，現(xiàn)有一個進程被分成5段，其段號和段長見下表，段內(nèi)分頁，頁表見下，存放在內(nèi)存中，每頁的長度為4096B。進程運行到某一個指令，其地址為(2，3，010)，當前CPU的寄存器和地址加法器的狀態(tài)如圖所示，當上述指令執(zhí)行時，操作系統(tǒng)如何工作?CPU中各個寄存器和快表的值為多少?(均為十六進制)。
  
  當前CPU的寄存器和地址加法器的狀態(tài)：
  
  請?zhí)顚懼噶顖?zhí)行時的狀況：
  

6. 設需在兩臺計算機間經(jīng)兩個中間節(jié)點傳送100M字節(jié)的文件，假定：
  (1)計算機與中間節(jié)點間的通信線路以及中間節(jié)點間通信線路的通信速率皆為8Kbps；
  (2)數(shù)據(jù)傳輸?shù)牟铄e可以忽略不計；
  (3)中間節(jié)點存儲轉(zhuǎn)發(fā)時間可忽略不計；
  (4)每一段線路的傳播時延均為10ms
  試計算采用甲、乙兩種方案傳送此文件所需時間。其中：
  (1)方案甲：將整個文件逐級存儲轉(zhuǎn)發(fā)。
  (2)方案乙：將文件分為1000字節(jié)長的幀在進行逐級存儲轉(zhuǎn)發(fā)，假定幀頭和幀尾的開銷為10字節(jié)。