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

一、1.單項選擇題

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

0.在順序表中刪除一個元素的時間復雜度為(  )。

A.O(1)
B.O(log n)
C.O(n)
D.O(n2)

1.設棧S和隊列Q的初始狀態(tài)均為空，元素abcdefg依次進入棧S。若每個元素出棧后立即進入隊列Q，且7個元素出隊的順序是bdcfeag，則棧S的容量至少是(  )。

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

2.設A是一個已有10個元素的棧，棧中依次是A1，A2，…，A10，棧頂是A10；B是一個已有10個元素的循環(huán)隊列，隊列中元素依次為B1，B2，…，B10，隊頭元素為B1。A、B均采用順序結構，現要將棧中元素全部移入隊列中，需(  )次基本操作才能使得隊列中元素與棧中元素交替排列，即B中排列后的元素為B1，A1，B2，．A2，…，B10，A10。(不必考慮存儲空間)

A.100
B.1 000
C.50
D.20

3.設高度為H的二叉樹上只有度為0和度為2的結點，則此類二叉樹中所包含的結點數至少為(  )。

A.2*H
B.2*H-1
C.2*H+1
D.H+1

4.設有13個值，用它們組成一棵哈夫曼樹，則該哈夫曼樹共有(  )個結點。

A.13
B.12
C.26
D.25

5.已知10個數據元素為(54，28，16，34，73，62，95，60，23，43)，按照依次插入結點的方法生成一棵二叉排序樹后，查找值為62的結點所需比較的次數為(  )。

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

6.當向一棵m階的B一樹做插入操作時，若一個結點中的關鍵字個數等于(  )，則必須分裂成兩個結點，當向一棵m階的B-樹做刪除操作時，若一個結點中的關鍵字個數等于(  )，則可能需要同它的左兄弟或右兄弟結點合并成一個結點。

A.m，m／2-2
B.m-1，m／2-1
C.m+1，m／2
D.m／2，m／2+1

7.下面關于Prim算法和Kruskal算法的時間復雜度正確的是(  )。

A.Prim算法的時間復雜度與網中的邊數有關，適合于稀疏圖
B.Prim算法的時間復雜度與網中的邊數無關，適合于稠密圖
C.Kruskal算法的時間復雜度與網中的邊數有關，適合于稠密圖
D.Kruskal算法的時間復雜度與網中的邊數無關，適合于稀疏圖

8.數據序列F={2，1，4，9，8，10，6，20)只能是下列排序算法中的(  )的兩趟排序后的結果。

A.快速排序
B.冒泡排序
C.選擇排序
D.插入排序

9.在含有n個關鍵字的大頂堆中，關鍵字最小的記錄有可能存儲在(  )位置上。

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

10.馮.諾依曼機中指令和數據均以二進制形式存放在存儲器中，CPU區(qū)分它們的依據是(  )。

A.指令操作碼的譯碼結果
B.指令和數據的尋址方式
C.指令周期的不同階段
D.指令和數據所在的存儲單元

11.IEEE754標準浮點數的尾數采用(  )機器數形式。

A.原碼
B.補碼
C.移碼
D.反碼

12.字長16位的補碼定點小數的表示范圍是(  )。

A.0～1-2^-15
B.-(1-2^-15)～1-2^-15
C.-1～1-2^-15
D.-1～1

13.補碼定點小數除法中，被除數和除數應滿足(  )。

A.0≤｜被除數｜≤｜除數｜
B.0＜｜被除數｜≤｜除數｜
C.0＜｜除數｜≤｜被除數｜
D.0＜｜被除數｜＜｜除數｜

14.某機器采用四體低位交叉存儲器，現分別執(zhí)行下述操作：(1)讀取6個連續(xù)地址單元中存放的存儲字，重復80次；(2)讀取8個連續(xù)地址單元中存放的存儲字，重復60次。則(1)、(2)所花時間之比為( )。

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

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

A.虛擬存儲器的引入主要是為了解決主存容量的問題
B.虛擬存儲器通過頁表來實現虛實地址的映射
C.虛擬存儲器是一個容量很大的邏輯模型，不是任何實際的存儲器
D.虛擬存儲器完全由硬件實現

16.在指令格式中，采用擴展操作碼設計方案的目的是(  )。

A.縮短指令字長
B.增加指令字長
C.保持指令字長不變的基礎上增加指令數量
D.保持指令字長不變的基礎上擴大指令尋址空間

17.磁盤的平均存取時間是指平均尋道時間和平均等待時間之和。若磁盤的轉速提高一倍，則(  )。

A.平均存取時間減半
B.平均尋道時間減半
C.平均等待時間減半
D.以上都正確

18.下列說法正確的是( )。

A.取指周期一定等于機器周期
B.指令字長等于機器字長的前提下，取指周期等于機器周期
C.指令字長等于存儲字長的前提下，取指周期等于機器周期
D.取指周期與機器周期沒有必然聯(lián)系

19.下列說法中正確的是(  )。

A.微處理器的程序稱為微程序
B.微指令控制器的執(zhí)行速度比硬布線控制器快
C.存放微程序的控制存儲器可用ROM或EPROM來實現
D.在微程序控制器中，微指令使用機器指令來解釋執(zhí)行

20.同步通信比異步通信數據傳輸率高的原因是(  )。

A.同步通信不需要應答信號
B.同步通信使用公共時鐘進行同步
C.同步通信中，通信雙方的速度相近
D.以上都包括

21.CPU在中斷周期要完成的任務不包括(  )。

A.保護斷點
B.關中斷
C.保護現場
D.向量地址送PC

22.實時系統(tǒng)中的進程調度，通常采用(  )算法。

A.先來先服務
B.時間片輪轉
C.搶占式的優(yōu)先數高者優(yōu)先
D.響應比高者優(yōu)先

23.進程由就緒態(tài)轉換為運行態(tài)是由(  )引起的。

A.中斷事件
B.進程狀態(tài)轉換
C.進程調度
D.為程序創(chuàng)建進程

24.以下(  )不是產生死鎖的原因。

A.資源共享
B.并發(fā)執(zhí)行的進程數太多
C.系統(tǒng)資源不足
D.進程推薦順序非法

25.把程序地址空間中使用的邏輯地址變成內存中物理地址稱為(  )。

A.加載
B.物理化
C.重定位
D.邏輯化

26.下面關于虛擬存儲器的論述中，正確的是(  )。

A.在段式系統(tǒng)中以段為單位管理用戶的邏輯空間，以頁為單位管理內存的物理空間；有了虛擬存儲器才允許用戶使用比內存更大的地址空間
B.為了提高請求分頁系統(tǒng)中內存的利用率，允許用戶使用不同大小的頁面
C.為了能讓更多的作業(yè)同時運行，通常只裝入10％～30％的作業(yè)即啟動運行
D.最佳適應算法是實現虛擬存儲器的常用算法

27.在下列文件的物理結構中，(  )不利于文件長度的動態(tài)增長。

A.連續(xù)結構
B.鏈接結構
C.索引結構
D.哈希結構

28.設文件F1的當前引用計數值為1，先建立F1的符號鏈接(軟鏈接)文件F2，再建 F1的硬鏈接文件F3，然后刪除F1。此時，F2和F3的引用計數值分別是(  )。

A.0、1
B.1、1
C.1、2
D.2、1

29.如果I／O設備與存儲設備間的數據交換不經過CPU來完成，則這種數據交換方式是(  )。

A.程序查詢方式
B.中斷方式
C.DMA方式
D.無條件存取方式

30.驅動調度算法中，(  )算法可能會隨時改變移動臂的運動方向。

A.電梯調度
B.最短尋找時間優(yōu)先
C.掃描
D.單向掃描

31.某虛存系統(tǒng)有3頁初始為空的頁框，若采用先進先出的頁面淘汰算法，則在下列的頁面需求提出時，會產生(  )次缺頁中斷?設頁面走向為：4 3 2 1 4 3 5 4 3 2 1 5~。

A.7
B.8
C.9
D.10

32.傳輸線上的位流信號同步，應該屬于下列OSI的(  )層處理。

A.物理層
B.數據鏈路層
C.網絡層
D.傳輸層

33.測得一個以太網數據的波特率是40 Mbps，那么其數據率是(  )。

A.10 Mbps
B.20 Mbps
C.40 Mbps
D.80 Mbps

34.數據鏈路層采用了后退N幀(GBN)協(xié)議，發(fā)送方已經發(fā)送了編號為0～7的幀。當計時器超時時，若發(fā)送方只收到0、2、3號幀的確認，則發(fā)送方需要重發(fā)的幀數是(  )。

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

35.一個C類地址，采用了255．255．255．240作為子網掩碼，那么這個C類地址可以劃分為(  )個子網。

A.16
B.32
C.64
D.128

36.下列地址中，不屬于多播地址的是(  )。

A.225．189．123．43
B.239．14．68．89
C.240．32．22．12
D.224．0．0．255

37.下列的網絡協(xié)議中，(  )的運輸層協(xié)議是使用TCP的。

A.TFTP
B.DNS
C.RIP
D.TELNEI、

38.一個FTP的用戶，發(fā)送了LIS27、命令來獲取服務器的文件列表，這時候服務器應該通過( )端口來傳輸該列表。

A.21
B.20
C.22
D.19

39.UDP的報文頭部不包括( )。

A.目的地址
B.報文長度
C.目的UDP端H
D.源UDP端口

二、2.綜合應用題

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

0.

1. 給定集合S={0，1，2，3，4)，以及優(yōu)先關系R={0＜1，1＜4，1＜2，2＜3，
  2＜4，4＜0)。
  (1)R是偏序關系嗎?
  (2)證明你的結論。

2. 下圖所示為雙總線結構機器的數據通路，IR為指令寄存器，PC為程序計數器(具有自增功能)，M為主存(受R／W信號控制)，AR為地址寄存器，DR為數據緩沖寄存器，ALU由加、減控制信號決定完成何種操作，控制信號G控制的是一個門電路。另外，線上標注有小圈表示有控制信號，例中yi表示y寄存器的輸入控制信號，R1 o為寄存器R1的輸出控制信號，未標字符的線為直通線，不受控制。
  (1)“ADD R2，R0”指令完成(R0)+(R2)→R0的功能操作，畫出其指令周期流程圖，假設該指令的地址已放入PC中。并列出相應的微操作控制信號序列。
  (2)若將“取指周期”縮短為一個CPU周期，請先畫出修改數據通路，后畫出指令周期流程圖。
  (3)在(2)的基礎上，將“執(zhí)行周期”也縮短為一個CPU周期，先修改運算器數據通路，后畫出指令周期流程圖。此時加法指令速度比(1)提高幾倍?

3. 有兩部計算機M1和M2，指令系統(tǒng)相同。它們的操作頻率頻率分別是400 MHz和200 MHz。指令分成A、B和C三類，在M1上執(zhí)行分別需4、6和8個周期；在M2上執(zhí)行分別需2、4和3個周期?，F有一程序在兩機器上執(zhí)行，其中A、B和C三類指令依次占30％、50％和20％。請問哪一部機器較快完成，快幾倍?

4. 某會議有n個參與者，等大家到齊后會議才能開始，利用P、V原語操作實現會議參與者進程。

5. 完成以下各小題。
 (1)什么是Belady現象?為什么會產生這種現象?
 (2)頁面置換算法FIFO為什么會出現Belady現象?簡述理由。
 (3)頁面置換算法LRU為什么不會出現Belady現象?簡述理由。

6. 假定A和B是試圖在一個以太網上發(fā)送的兩個站。每個站都有一個穩(wěn)定的幀的隊列準備發(fā)送，A的幀編號是A1，A2和A3等，B的幀編號是B1，B2和B3等。再假定指數后退的基本單元時間是T=51．2微秒。
  現在A和B同時嘗試發(fā)送1號幀，碰撞，并且剛好分別選擇了0×T和1×T的退避時間，也就是說，A贏得了這一次競爭，發(fā)送A1，B需要等待。在這次傳送結束時，B嘗試再發(fā)送B1，而A則嘗試發(fā)送A2。這一輪的首次嘗試產生碰撞，此時，A的退避時間從0×T和1×T中選擇，而B則從0×T，…，3×T中選擇。
  (1)給出A贏得第2次退避競爭的概率。
  (2)假定A已贏得了第2次退避競爭。A在成功發(fā)送A2后，接著嘗試發(fā)送A3。當B再次嘗試發(fā)送B1時，A和B再次碰撞。給出A贏得這第3次退避競爭的概率。
  (3)給出A贏得所有其余后退競爭的概率的合理下限值。