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

一、1.單項選擇題

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

0.設n是描述問題規(guī)模的非負整數(shù)，下面程序片段的時間復雜度是(     )。
  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.利用棧求表達式的值時，設立運算數(shù)棧OPND。假設OPND只有兩個存儲單元，在下列表達式中，不發(fā)生溢出的是(     )。

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

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

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

3.一個具有1025個結點的二叉樹的高h為(     )。

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

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

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

5.簡單無向圖的鄰接矩陣是對稱的，可以對其進行壓縮存儲。若無向圖G有n個結點，其鄰接矩陣為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.下面關于圖的存儲的敘述中，正確的是(     )。

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

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

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

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

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

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

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

10.用某種排序方法對線性表(25，84，21，47，15，27，68，35，20)進行排序時，元素序列的變化情況如下：
  (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.下圖中計算機硬件系統(tǒng)基本組成部件①、②、③、④和⑤的名稱是(     )。
  

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

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

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

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

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

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

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

15.下面是有關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.設指令由取指、分析、執(zhí)行3個子部件完成，每個子部件的工作周期均為⊿t，采用常規(guī)標量流水線處理機。若連續(xù)執(zhí)行10條指令，則共需時間是(     )。

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

18.某計算機的指令系統(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.關于在I／O設備與主機間交換數(shù)據(jù)的敘述中，錯誤的是(     )。

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

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

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

23.有2個優(yōu)先級相同的并發(fā)進程P1和P2，它們的執(zhí)行過程如下圖所示，x、y和z是共享變量。假設，當前信號量s1=0，s2=0，進程運行結束后，x、y和z的值分別為(     )。
  進程P1  進程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ā)進程訪問共享變量段的(     )。

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

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

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

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

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

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

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

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

A.成正比
B.成反比
C.無關系
D.固定值

29.某一個磁盤共有16個盤面，每個盤面上從外到內共有30000個磁道(或稱30000個柱面)，每個磁道有250個扇區(qū)。假定存儲信息時以一個扇區(qū)作為一個存儲塊，盤面號(磁頭號)、磁道號和扇區(qū)號均從0開始編號，那么，盤塊號10025 78對應的盤面號、磁道號和扇區(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.重名翻譯機構
B.建立索引表
C.建立指針
D.建立樹形目錄結構

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

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

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

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

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

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

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

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

35.以太網交換機轉發(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.關于因特網中的主機和路由器，以下說法正確的是(     )。
  I．主機通常需要實現(xiàn)TCP協(xié)議  Ⅱ．路由器必須實現(xiàn)TCP協(xié)議
  Ⅲ．主機必須實現(xiàn)IP協(xié)議    Ⅳ．路由器必須實現(xiàn)IP協(xié)議

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

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

A.目標端口號
B.序號
C.源端口號
D.校驗號

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

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

二、2.綜合應用題

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

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

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

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

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

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

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

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