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

一、1.單項選擇題

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

0.如果對含有n(n＞1)個元素的線性表的運算只有4種：刪除第一個元素，刪除最后一個元素，在第一個元素前面插入新元素，在最后一個元素的后面插入新元素，則最好使用( )。

A.只有尾結(jié)點指針沒有頭結(jié)點指針的循環(huán)單鏈表
B.只有尾結(jié)點指針沒有頭結(jié)點指針的非循環(huán)單鏈表
C.只有頭結(jié)點指針沒有尾結(jié)點指針的循環(huán)單鏈表
D.既有頭結(jié)點指針也有尾結(jié)點指針的循環(huán)單鏈表

1.在一個順序循環(huán)隊列中刪除元素時，首先需要(  )。

A.前移隊首指針
B.后移隊首指針
C.取出隊首指針所指位置上的元素
D.取出隊尾指針所指位置上的元素

2.如果二叉樹T2是由有序樹T1轉(zhuǎn)換而來的二叉樹，那么T1中結(jié)點的后序就是T2中結(jié)點的(  )。

A.先序
B.中序
C.后序
D.層次序

3.前序遍歷和中序遍歷結(jié)果相同的二叉樹為(  )。

A.根結(jié)點無左孩子的二叉樹
B.根結(jié)點無右孩子的二叉樹
C.所有結(jié)點只有左子樹的二叉樹
D.所有結(jié)點只有右子樹的二叉樹

4.對包含n個關(guān)鍵碼的散列表進行檢索，平均檢索長度為(  )。

A.O(log n)
B.O(n)
C.O(nlog n)
D.不直接依賴于n

5.

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

6.

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

7.下面關(guān)于圖的存儲結(jié)構(gòu)的敘述中正確的是(  )。

A.用鄰接矩陣存儲圖占用空間大小只與圖中頂點有關(guān)，與邊數(shù)無關(guān)
B.用鄰接矩陣存儲圖占用空間大小只與圖中邊數(shù)有關(guān)，與頂點無關(guān)
C.用鄰接表存儲圖占用空間大小只與圖中頂點數(shù)有關(guān)，與邊數(shù)無關(guān)
D.用鄰接表存儲圖占用空間大小只與圖中邊數(shù)有關(guān)，與頂點數(shù)無關(guān)

8.下列排序算法中，(  )每一趟都能選出一個元素放在最終位置上，并且是不穩(wěn)定的。

A.冒泡排序
B.希爾排序
C.直接選擇排序
D.直接插入排序

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

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

10.條件轉(zhuǎn)移指令執(zhí)行時所依據(jù)的條件來自(  )。

A.指令寄存器IR
B.程序計數(shù)器PC
C.程序狀態(tài)字寄存器PSWR
D.主存地址寄存器MAR

11.某計算機字長8位，采用補碼表示小數(shù)。若某數(shù)真值為-0．1001，則它在該計算機中的機器數(shù)形式為( )。

A.10111
B.10110111
C.10111000
D.10110000

12.定點數(shù)采用模4補碼，即變形補碼進行加減運算時，判斷溢出的方法是(  )。

A.符號位進位與最高數(shù)值位進位相異時表明溢出
B.實際參與運算的兩數(shù)符號位相同，結(jié)果又與原操作數(shù)符號不同時表明溢出
C.雙符號位不同時表明溢出
D.以上都正確

13.浮點運算結(jié)果滿足下列哪個條件時，需做中斷處理(  )。

A.尾數(shù)雙符號位為“01”
B.尾數(shù)雙符號位為“10”
C.階碼雙符號位為“01”
D.階碼雙符號位為“10”

14.下列各選項是采用奇偶校驗碼編碼的ASCII碼，所有編碼都未發(fā)生錯誤，采用偶校驗的是(  )。

A.01001101
B.0011001
C.10101101
D.1101000

15.下列只讀存儲器中，可編程且可以實現(xiàn)字擦除的是(  )。

A.掩模ROM
B.PROM
C.EPROM
D.EEPROM

16.下列關(guān)于機器字長與指令字長的說法正確的是(  )。

A.指令字長等于機器字長
B.指令字長一定是機器字長的整數(shù)倍
C.兩者長度沒有必然關(guān)系
D.以上說法都不對

17.某機器指令字長12位，有零地址、一地址、二地址三種指令，地址碼長4位，采用擴展操作碼技術(shù)。若二地址指令和一地址指令條數(shù)都取最大值，則該機指令條數(shù)最多為(  )。

A.16
B.46
C.48
D.4 366

18.下列哪個選項不可能是微指令格式中的組成部分(  )。

A.操作碼字段
B.操作控制字段
C.外部條件字段
D.下地址字段

19.某機中，設(shè)備號小的主設(shè)備在總線判優(yōu)時具有較高的優(yōu)先級，其總線判優(yōu)方式可能是(  )。

A.鏈式查詢方式
B.計數(shù)器定時查詢方式
C.獨立請求方式
D.以上都有可能

20.中斷向量表中保存的是(  )。

A.被中斷程序的返回地
B.中斷服務(wù)程序入口地址
C.中斷服務(wù)程序入口地址的地址
D.中斷優(yōu)先級

21.下列說法中錯誤的是(  )。

A.程序查詢方式下，CPU與I／O設(shè)備串行工作
B.程序中斷方式下，CPU與I／O設(shè)備并行工作
C.DMA方式下，主程序可與I／O數(shù)據(jù)傳送并行工作
D.實現(xiàn)了DMA方式的系統(tǒng)中，程序中斷方式?jīng)]有存在的必要

22.為了保證操作系統(tǒng)本身的安全，(  )是必須加以保護的。

A.從內(nèi)核模式轉(zhuǎn)換到用戶模式
B.從存儲操作系統(tǒng)內(nèi)核的空間讀取數(shù)據(jù)
C.從存儲操作系統(tǒng)內(nèi)核的空間讀取指令
D.打開定時器

23.以下關(guān)于UNIX操作系統(tǒng)的敘述中，(  )是錯誤的。

A.UNIX 對實時系統(tǒng)是不合適的，因為進程在核心態(tài)不可搶占
B.UNIX終究會在市場上消失的
C.UNIX是目前最流行的操作系統(tǒng)之一
D.UNIX 比較適用于高檔計算機系統(tǒng)和網(wǎng)絡(luò)環(huán)境，它不能用于普通的微機

24.關(guān)于臨界區(qū)問題(critical section problem)是一個算法(假設(shè)只有進程P0和P1可能進入該臨界區(qū))，算法如下(i為0或1)，該算法(  )。
 repeat
  retry：if(turn≠-1)turn：=i；
  if(turn≠i)go to retry；
  turn：=-1；
  critical Section(臨界區(qū))
  turn=0；
  remainder Section(其他區(qū)域)
until false；

A.不能保證進程互斥進入臨界區(qū)，且會出現(xiàn)“饑餓”(Starvation)
B.不能保證進程互斥進入臨界區(qū)，但不會出現(xiàn)“饑餓”
C.保證進程能互斥進入臨界區(qū)，但會出現(xiàn)“饑餓”
D.保證進程互斥進入臨界區(qū)，不會出現(xiàn)“饑餓”

25.系統(tǒng)功能調(diào)用是( )。

A.用戶編寫的一個子程序
B.高級語言中的庫程序
C.操作系統(tǒng)中的一條命令
D.操作系統(tǒng)向用戶提供的接口

26.在(  )的情況下，系統(tǒng)出現(xiàn)死鎖。

A.計算機系統(tǒng)發(fā)生重大故障
B.有多個封鎖的進程同時存在
C.若干進程因競爭資源而無休止地相互等待對方釋放已占有的資源
D.資源數(shù)大大小于進程數(shù)或進程同時申請的資源數(shù)大大超過資源總數(shù)

27.通常對文件系統(tǒng)來說，文件名及其屬性可以集中在(  )。

A.目錄
B.索引
C.字典
D.作業(yè)控制塊

28.一個分段存儲管理系統(tǒng)中，地址長度為32位，其中段號占8位，則最大段長是(  )。

A.2⁸字節(jié)
B.2¹⁶字節(jié)
C.2²⁴字節(jié)
D.2³²字節(jié)

29.如果I／O設(shè)備和存儲設(shè)備之間的數(shù)據(jù)交換不經(jīng)過CPU來完成，則這種交換方式是 (  )。

A.程序查詢方式
B.中斷方式
C.DMA方式
D.外部總線方式

30.假設(shè)系統(tǒng)的所有資源是同類型的，系統(tǒng)中的進程每次申請資源數(shù)最多1個，那么，下面列出的4種情況中，(  )可能發(fā)生死鎖。情況序號系統(tǒng)中進程數(shù)資源總量

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

31.

A.進程A
B.進程B
C.進程A和進程B同時
D.不一定

32.下列交換方式中，(  )一次連接沿著一條路由路徑發(fā)送所有的數(shù)據(jù)。

A.分組交換
B.報文交換
C.電路交換
D.以上都不是

33.某通訊線路每20 ms采樣一次，每一個信號共有64種不同的狀態(tài)，那么這個線路的傳輸速率是(  )。

A.100 bps
B.200 bps
C.300 bps
D.400 bps

34.RS-232-C的電氣特性規(guī)定邏輯“1”的電平范圍為(  )。

A.+5～+15 V
B.-5～-15 V
C.0～+5 V
D.0～-5 V

35.一個16端口的二層以太網(wǎng)交換機，沖突域和廣播域的個數(shù)分別是(  )。

A.1，1
B.16，16
C.1，16
D.16，1

36.假定一臺主機的IP地址是222．205．74．56，子網(wǎng)掩碼為255．255．240．0，該子網(wǎng)地址為 (  )。

A.222．205．0．0
B.222．205．64．0
C.222．205．72．0
D.222．205．74．0

37.以下(  )協(xié)議完成了從網(wǎng)卡到IP地址的映射。

A.ARP協(xié)議
B.RARP協(xié)議
C.IGMP協(xié)議
D.ICMP協(xié)議

38.一個TCP連接總是以1 KB的最大段發(fā)送TCP段，發(fā)送方有足夠多的數(shù)據(jù)要發(fā)送。當(dāng)擁塞窗口為16 KB時發(fā)生了超時，如果接下來的4個RTT(往返時間)時間內(nèi)的TCP段的傳輸都是成功的，那么當(dāng)?shù)?個RTT時間內(nèi)發(fā)送的所有TCP段都得到肯定應(yīng)答時，擁塞窗口大小是(  )。

A.7 KB
B.8 KB
C.9 KB
D.16 KB

39.在HTTP協(xié)議中，一個以2開頭的響應(yīng)報文表示(  )。

A.暫時性失敗
B.永久性失敗
C.重定向
D.成功

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

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

0. 在平衡二叉樹中的每個結(jié)點上增設(shè)一個Lsize域，其值為它的左子樹中的結(jié)點個數(shù)加1，試寫一個時間復(fù)雜度為O(log n)的算法，確定樹中第k個結(jié)點的位置。

1.

2. 某32位機(機器字長32位)的一臺外設(shè)通過32位總線與系統(tǒng)內(nèi)存相連。CPU每秒執(zhí)行100條指令，平均每條指令需要5個機器周期，其中3個周期必須訪問內(nèi)存，內(nèi)存讀寫需一個機器周期，假定CPU在95％的時間內(nèi)持續(xù)執(zhí)行“背景程序”，且這段時間內(nèi)不執(zhí)行I／O指令?，F(xiàn)該外設(shè)需要把一個非常大的數(shù)據(jù)塊傳送到內(nèi)存。
  (1)如果采用程序I／O方式，每傳送一32位字寬的數(shù)據(jù)需要CPU執(zhí)行2條指令。請計算最大數(shù)據(jù)傳輸率(單位：字／秒)。
  (2)如果采用DMA方式，在DMA與CPU出現(xiàn)總線訪問沖突時，CPU優(yōu)先。請計算最大數(shù)據(jù)傳輸率(單位：字／秒)。

3. 下圖是某模型機CPU的組成框圖。設(shè)該CPU采用同步控制邏輯，分取指周期、取第一操作數(shù)周期，取第二操作數(shù)周期、執(zhí)行周期四個機器周期，每個機器周期有T₀、T₁、T₂三個節(jié)拍。試寫出如下雙操作數(shù)運算指令的微操作命令及節(jié)拍安排。ADD R0，(R1)  完成功能(R0)+((R1))→R0

4. 設(shè)有一緩沖池P，P中含有10個可用緩沖區(qū)，一個輸入進程將外部數(shù)據(jù)讀入P，另有一個輸出進程將P中數(shù)據(jù)取出并輸出(如下圖所示)。若進程每次操作均以一個緩沖區(qū)為單位，試用記錄型信號量寫出兩個進程的同步算法，要求寫出信號量的設(shè)置。
  輸入進程  輸出進程
  L：讀入數(shù)據(jù)  L：從一滿緩沖區(qū)中取出數(shù)據(jù)
  將數(shù)據(jù)寫入一空緩沖區(qū)  將數(shù)據(jù)輸出
  GnTOL  GOTOL

5.
處理一次缺頁的平均時間為108 ns(已含更新TLB和頁表的時間)，進程的駐留集大小固定為2，采用最近最少使用置換算法(LRU)和局部淘汰策略。假設(shè)：①TLB初始為空；②地址轉(zhuǎn)換時先訪問TLB，若TLB未命中，再訪問頁表(忽略訪問頁表之后的TLB更新時間)；③有效位為0表示頁面不在內(nèi)存，產(chǎn)生缺頁中斷，缺頁中斷處理后，返回到產(chǎn)生缺頁中斷的指令處重新執(zhí)行。設(shè)有虛地址訪問序列2362H、1565H、25A5H，請問：
  (1)依次訪問上述三個虛地址，各需多少時間?給出計算過程。
  (2)基于上述訪問序列，虛地址1565H的物理地址是多少?請說明理由。

6.