?計算機(jī)專業(yè)（基礎(chǔ)綜合）模擬試卷22

一、1.單項選擇題

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

0.設(shè)n是描述問題規(guī)模的非負(fù)整數(shù)，下面程序片段的時間復(fù)雜度是(     )。
  void fun(int n){
  int i，k；
  for(i=1；i<=n；i十十)
  for(j=1；j<=n；j十十){
  k=1：
  while(k<=n)k=5*k：
  }
}

A.O(n²log₂n)
B.O(nlog₅n)
C.O(n²log₅n)
D.O(n³)

1.利用棧求表達(dá)式的值時，設(shè)立運算數(shù)棧OPND。假設(shè)OPND只有兩個存儲單元，在下列表達(dá)式中，不發(fā)生溢出的是(     )。

A.A—B*(C—D)
B.(A—B)*C—D
C.(A—B*C)—D
D.(A—B)*(C—D)

2.已知輸入序列為abcd，經(jīng)過輸出受限的雙端隊列后，能得到的輸出序列是(     )。

A.dacb
B.cadb
C.dbca
D.以上答案都不對

3.一個具有1025個結(jié)點的二叉樹的高h(yuǎn)為(     )。

A.11
B.10
C.11至1025之間
D.10至1024之間

4.以下關(guān)于二叉排序樹的說法正確的是(     )。  I在二叉排序樹中，每個結(jié)點的關(guān)鍵字都比左孩子關(guān)鍵字大，比右孩子關(guān)鍵字小。  Ⅱ每個結(jié)點的關(guān)鍵字都比左孩子關(guān)鍵字大，比右孩子關(guān)鍵字小，這樣的二叉樹都是二叉排序樹。  Ⅲ在二叉排序樹中，新插入的關(guān)鍵字總是處于最底層。  Ⅳ在二叉排序樹中，新結(jié)點總是作為葉子結(jié)點來插入的。  V二叉排序樹的查找效率和二叉排序樹的高度有關(guān)。

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

5.簡單無向圖的鄰接矩陣是對稱的，可以對其進(jìn)行壓縮存儲。若無向圖G有n個結(jié)點，其鄰接矩陣為A[1．．n，1．．n]，且壓縮存儲在B[1．．k]，則k的值至少為(     )。

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

6.下面關(guān)于圖的存儲的敘述中，正確的是(     )。

A.用鄰接矩陣法存儲圖，占用的存儲空間數(shù)只與圖中結(jié)點個數(shù)有關(guān)，而與邊數(shù)無關(guān)
B.用鄰接矩陣法存儲圖，占用的存儲空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點個數(shù)無關(guān)
C.用鄰接表法存儲圖，占用的存儲空間數(shù)只與圖中結(jié)點個數(shù)有關(guān)，而與邊數(shù)無關(guān)
D.用鄰接表法存儲圖，占用的存儲空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點個數(shù)無關(guān)

7.用遞歸算法實現(xiàn)n個不同元素的有序序列的折半查找，采用一個遞歸工作棧時，該棧的最小容量應(yīng)為(     )

A.n
B.「n/2」
C.「㏒2 n」
D.「㏒2 n」+1

8.在采用線性探測法處理沖突所構(gòu)成的散列表上進(jìn)行查找，可能要探測多個位置，在查找成功的情況下，所探測的這些位置的鍵值(     )。

A.一定都是同義詞
B.一定都不是同義詞
C.不一定都是同義詞
D.都相同

9.如果將中國人按照生日(不考慮年份，只考慮月、日)來排序，那么使用下列排序算法中最快的是(     )。

A.歸并排序
B.希爾排序
C.快速排序
D.基數(shù)排序

10.用某種排序方法對線性表(25，84，21，47，15，27，68，35，20)進(jìn)行排序時，元素序列的變化情況如下：
  (1)25，84，21，47，15，27，68，35，20
  (2)20，1 5，21，25，47，27，68，35，84
  (3)1 5，20，21，25，35，27，47，68，84
  (4)1 5，20，21，25，27，35，47，68，84
  則采用的排序方法是(     )。

A.選擇排序
B.希爾排序
C.二路歸并排序
D.快速排序

11.下圖中計算機(jī)硬件系統(tǒng)基本組成部件①、②、③、④和⑤的名稱是(     )。
  

A.①控制器、②運算器、③存儲器、④輸入設(shè)備、⑤輸出設(shè)備
B.①運算器、②控制器、③存儲器、④輸入設(shè)備、⑤輸出設(shè)備
C.①運算器、②存儲器、③控制器、④輸入設(shè)備、⑤輸出設(shè)備
D.①運算器、②控制器、③存儲器、④輸出設(shè)備、⑤輸入設(shè)備

12.一7的八位二進(jìn)制反碼表示為(     )。

A.00000111
B.10000111
C.11111000
D.11111001

13.設(shè)數(shù)據(jù)碼字為1001001 1，采用海明碼進(jìn)行校驗，若僅考慮糾正一位錯，則必須加入的(冗余)位數(shù)是(     )。

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

14.如果X為負(fù)數(shù)，則已知[X]_補(bǔ)求[一X]_補(bǔ)的方法是(     )。

A.[X]_補(bǔ)各值保持不變
B.[X]_補(bǔ)符號位變反，其他各位不變
C.[X]_補(bǔ)除符號位外，各位變反，末位加1
D.[X]_補(bǔ)連同符號位一起各位變反，末位加1

15.下面是有關(guān)DRAM和SRAM存儲器芯片的敘述：
  I DRAM芯片的集成度比SRAM高
  Ⅱ DRAM芯片的成本比SRAM高
  Ⅲ DRAM芯片的速度比SRAM快
  Ⅳ DRAM芯片工作時需要刷新，SRAM芯片工作時不需要刷新
  通常情況下，錯誤的是(     )。

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

16.若想對某個寄存器中的某幾位清零，可以使用的一條指令是(     )。

A.AND
B.OR
C.NOT
D.XOR

17.設(shè)指令由取指、分析、執(zhí)行3個子部件完成，每個子部件的工作周期均為⊿t，采用常規(guī)標(biāo)量流水線處理機(jī)。若連續(xù)執(zhí)行10條指令，則共需時間是(     )。

A.8⊿t
B.10⊿t
C.12⊿t
D.14 ⊿t

18.某計算機(jī)的指令系統(tǒng)中共有1 01條不同的指令，采用微程序控制方式時，控制存儲器中具有的微程序數(shù)目至少是(     )。

A.101
B.102
C.103
D.104

19.某總線有104根信號線，其中數(shù)據(jù)總線(DB)32根，若總線工作頻率為33 MHz，則其理論最大傳輸率是(     )。

A.33 MB／s
B.64 MB／s
C.132 MB／s
D.164 MB／s

20.RGB8：8：8表示一幀彩色圖像的顏色數(shù)是(     )。

A.2³
B.2⁸
C.2²⁴
D.2⁵¹²

21.關(guān)于在I／O設(shè)備與主機(jī)間交換數(shù)據(jù)的敘述中，錯誤的是(     )。

A.中斷方式下，CPU需要執(zhí)行程序來實現(xiàn)數(shù)據(jù)傳送任務(wù)
B.中斷方式和DMA方式下，CPU與I／O設(shè)備都可并行工作
C.中斷方式和DMA方式中，快速I／O設(shè)備更適合采用中斷方式傳遞數(shù)據(jù)
D.若同時接到DMA請求和中斷請求，CPU優(yōu)先響應(yīng)DMA請求

22.交互式操作系統(tǒng)中為了能使多個用戶同時與系統(tǒng)進(jìn)行交互，最關(guān)鍵的問題是(     )。

A.計算機(jī)要有足夠快的運行速度
B.能快速進(jìn)行內(nèi)外存之間的信息交換
C.系統(tǒng)能夠及時接收多個用戶的輸入
D.一段時間內(nèi)所有用戶的程序都能運行

23.有2個優(yōu)先級相同的并發(fā)進(jìn)程P1和P2，它們的執(zhí)行過程如下圖所示，x、y和z是共享變量。假設(shè)，當(dāng)前信號量s1=0，s2=0，進(jìn)程運行結(jié)束后，x、y和z的值分別為(     )。
  進(jìn)程P1  進(jìn)程P2
  ……   ……
  y：=20；  x：=10；
  y：=y+1；  x：=x+1；
  y：=y+1；  x：=x+1；
  z：=y+1；  P(s1)；
  V(s1)；   x：=x+y；
  P(s2)；   z：=x+z；
  y：=z+y；  V(s2)；

A.33，42，22
B.11，42，33
C.33，76，55
D.33，76，33

24.臨界區(qū)是指并發(fā)進(jìn)程訪問共享變量段的(     )。

A.管理信息
B.信息存儲
C.數(shù)據(jù)
D.代碼程序

25.一個正在訪問臨界資源的進(jìn)程由于申請等待10操作而被中斷時，它是(     )。

A.可以允許其它進(jìn)程進(jìn)入與該進(jìn)程相關(guān)的臨界區(qū)
B.不允許其它進(jìn)程進(jìn)入任何臨界區(qū)
C.可以允許其它進(jìn)程搶占處理機(jī)，但不得進(jìn)入該進(jìn)程的臨界區(qū)
D.不允許任何進(jìn)程搶占處理機(jī)

26.在連續(xù)內(nèi)存分配管理中，分區(qū)分配是最簡單的實現(xiàn)并發(fā)的內(nèi)存管理方法。對于該方法，進(jìn)行內(nèi)存保護(hù)的措施是(     )。

A.存取控制列表
B.用戶權(quán)限保護(hù)
C.程序狀態(tài)保護(hù)
D.界地址保護(hù)

27.段頁式存儲管理中，某個進(jìn)程的段表和頁表如下圖所示，頁的大小為4096B，現(xiàn)有邏輯地址(1，8228)，其對應(yīng)的物理地址是(     )。
  

A.483364
B.409636
C.475172
D.516132

28.分頁式虛擬存儲管理系統(tǒng)中，頁面的大小與可能產(chǎn)生的缺頁中斷次數(shù)是(     )。

A.成正比
B.成反比
C.無關(guān)系
D.固定值

29.某一個磁盤共有16個盤面，每個盤面上從外到內(nèi)共有30000個磁道(或稱30000個柱面)，每個磁道有250個扇區(qū)。假定存儲信息時以一個扇區(qū)作為一個存儲塊，盤面號(磁頭號)、磁道號和扇區(qū)號均從0開始編號，那么，盤塊號10025 78對應(yīng)的盤面號、磁道號和扇區(qū)號是(     )。

A.1，2500，78
B.10，250，78
C.2，250，1 61
D.0，4010，78

30.現(xiàn)代操作系統(tǒng)中，文件系統(tǒng)都有效地解決了重名問題，允許不同的文件可以有相同的文件名。那么，實現(xiàn)該功能的主要方法是(     )。

A.重名翻譯機(jī)構(gòu)
B.建立索引表
C.建立指針
D.建立樹形目錄結(jié)構(gòu)

31.設(shè)備管理中，設(shè)備映射表(DMT)的作用是(     )。

A.管理物理設(shè)備
B.管理邏輯設(shè)備
C.實現(xiàn)輸入／輸出
D.建立邏輯設(shè)備與物理設(shè)備的對應(yīng)關(guān)系

32.在OSI參考模型中，實現(xiàn)系統(tǒng)間二進(jìn)制信息塊的正確傳輸，為上一層提供可靠、無錯誤的數(shù)據(jù)信息的協(xié)議層是(     )。

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

33.光纖分為單模光纖和多模光纖，這兩種光纖的區(qū)別是(     )。

A.單模光纖的數(shù)據(jù)速率比多模光纖低
B.多模光纖比單模光纖傳輸距離更遠(yuǎn)
C.單模光纖比多模光纖的價格更便宜
D.多模光纖比單模光纖的纖芯直徑粗

34.使用HDLC時，位串011111110111110進(jìn)行位填充后的位模式是(     )。

A.011101110101110110
B.0111101110111110
C.1.1111110111e+014
D.1.1111011011e+015

35.以太網(wǎng)交換機(jī)轉(zhuǎn)發(fā)數(shù)據(jù)包時所依據(jù)的是(     )。

A.IP地址
B.MAC地址
C.LLC地址
D.PORT、地址

36.CRC校驗是目前常用的檢錯方式。如果采用的多項式為G(X)=X⁴+X+1，那么對于要傳的信息串1101011011的CRC校驗碼是(     )。

A.1011
B.1101
C.：1110
D.1100

37.關(guān)于因特網(wǎng)中的主機(jī)和路由器，以下說法正確的是(     )。
  I．主機(jī)通常需要實現(xiàn)TCP協(xié)議  Ⅱ．路由器必須實現(xiàn)TCP協(xié)議
  Ⅲ．主機(jī)必須實現(xiàn)IP協(xié)議    Ⅳ．路由器必須實現(xiàn)IP協(xié)議

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

38.下面包含在TCP頭中而不包含在UDP頭中的信息是(     )。

A.目標(biāo)端口號
B.序號
C.源端口號
D.校驗號

39.DNS服務(wù)器在名稱解析過程中正確的查詢順序是(     )。

A.本地緩存記錄→區(qū)域記錄→轉(zhuǎn)發(fā)域名服務(wù)器→根域名服務(wù)器
B.區(qū)域記錄→本地緩存記錄→轉(zhuǎn)發(fā)域名服務(wù)器→根域名服務(wù)器
C.本地緩存記錄→區(qū)域記錄→根域名服務(wù)器→轉(zhuǎn)發(fā)域名服務(wù)器
D.區(qū)域記錄→本地緩存記錄→根域名服務(wù)器→轉(zhuǎn)發(fā)域名服務(wù)器

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

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

0. 已知加權(quán)有向圖G如下，回答下列問題：
  
  (1)畫出該有向圖G的鄰接矩陣；
  (2)試?yán)肈ijkstra算法求G中從頂點a到其他各頂點間的最短路徑，并給出求解過程。

1. 已知數(shù)組A[1……n]的元素類型為整型int，設(shè)計一個時間和空間上盡可能高效的算法，將其調(diào)整為左右兩部分，左邊所有元素為負(fù)整數(shù)，右邊所有元素為正整數(shù)。不要求對這些元素排序。
  (1)給出算法的基本設(shè)計思想；
  (2)根據(jù)設(shè)計思想，采用C或C++或JAVA語言表述算法，關(guān)鍵之處給出注釋；
  (3)說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度。

2. 設(shè)某計算機(jī)有變址尋址、間接尋址和相對尋址等尋址方式，設(shè)當(dāng)前指令的地址碼部分為001AH，正在執(zhí)行的指令所在地址為1F05H，變址寄存器中的內(nèi)容為23A0H。
  (1)當(dāng)執(zhí)行取數(shù)指令時，如為變址尋址方式，則取出的數(shù)為多少?
  (2)如為間接尋址，取出的數(shù)為多少?
  (3)當(dāng)執(zhí)行轉(zhuǎn)移指令時，轉(zhuǎn)移地址為多少?
  已知存儲器的部分地址及相應(yīng)內(nèi)容，見下表。
  

3. 四位運算器框圖如下圖所示，ALU為算術(shù)邏輯單元，A和B為三選一多路開關(guān)，預(yù)先已通過多路開關(guān)A的SW門向寄存器R₁，R₂送入數(shù)據(jù)如下：R₁=0101，R₂=1010。寄存器BR輸出端接四個發(fā)光二極管進(jìn)行顯示。其運算過程依次如下：
  
  (1)R₁(A)+R₂(B)→BR(顯示結(jié)果1010)；
  (2)R₂(A)+R₁(B)→BR(顯示結(jié)果1111)；
  (3)R₁(A)+R₁(B)→BR(顯示結(jié)果1010)；
  (4)R₂(A)+R₂(B)→BR(顯示結(jié)果1111)；
  (5)R₂(A)+BR(B)→BR(顯示結(jié)果1111)；
  (6)R₁(A)+BR(B)→BR(顯示結(jié)果1010)；
  試分析運算器的故障位置與故障性質(zhì)(“1”故障還是“0”故障)，說明理由。

4. 在某一個單處理機(jī)的系統(tǒng)中，外接了一臺打印機(jī)，一臺輸入設(shè)備。當(dāng)前在系統(tǒng)中有二個進(jìn)程P0、P1已經(jīng)就緒，進(jìn)程P0首先獲得處理機(jī)運行，調(diào)度算法為先來先服務(wù)，進(jìn)程P0、P1的運行要求是這樣的：P0：計算100ms，打印信息200ms，繼續(xù)計算1 00ms，打印信息200ms，結(jié)束。P1：計算100ms，輸入數(shù)據(jù)150ms，繼續(xù)計算200ms，結(jié)束。
  請用甘特圖畫出它們的運行軌跡，并說明：
  進(jìn)程P0、P1在運行時有無等待?若有，請指出時間區(qū)間。
  計算處理機(jī)的利用率。

5. 某一個計算機(jī)系統(tǒng)采用虛擬頁式存儲管理方式，當(dāng)前在處理機(jī)上執(zhí)行的某一個進(jìn)程的頁表如下所示，所有的數(shù)字均為十進(jìn)制，每一項的起始編號是0，并且所有的地址均按字節(jié)計址，每頁的大小為1024字節(jié)。
  
  (1)計算下列邏輯地址轉(zhuǎn)換為物理地址，并說明為什么?
  0793，1197，2099，3320，41 88，5332
  (2)假設(shè)程序要訪問第2頁，頁面置換算法為改進(jìn)的Clock算法，請問該淘汰哪頁?頁表如何修改?上述地址的轉(zhuǎn)換結(jié)果是否改變?變成多少?

6. 如果下表是路由器R1的路由表，仔細(xì)分析各個表項的特點，并回答如下問題。
  
  (1)給出m0和m1所在的網(wǎng)絡(luò)號，以及可連接的最大主機(jī)數(shù)目。
  (2)給出接口m0，m1和m2的合理的IP地址。
  (3)試給出網(wǎng)絡(luò)的拓?fù)洹?/p>