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

一、1.單項選擇題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A.Prim算法的時間復(fù)雜度與網(wǎng)中的邊數(shù)有關(guān)，適合于稀疏圖
B.Prim算法的時間復(fù)雜度與網(wǎng)中的邊數(shù)無關(guān)，適合于稠密圖
C.Kruskal算法的時間復(fù)雜度與網(wǎng)中的邊數(shù)有關(guān)，適合于稠密圖
D.Kruskal算法的時間復(fù)雜度與網(wǎng)中的邊數(shù)無關(guān)，適合于稀疏圖

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

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

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

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

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

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

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

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

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

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

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

A.0≤｜被除數(shù)｜≤｜除數(shù)｜
B.0＜｜被除數(shù)｜≤｜除數(shù)｜
C.0＜｜除數(shù)｜≤｜被除數(shù)｜
D.0＜｜被除數(shù)｜＜｜除數(shù)｜

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A.保護斷點
B.關(guān)中斷
C.保護現(xiàn)場
D.向量地址送PC

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

A.先來先服務(wù)
B.時間片輪轉(zhuǎn)
C.搶占式的優(yōu)先數(shù)高者優(yōu)先
D.響應(yīng)比高者優(yōu)先

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

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

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

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

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

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

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

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

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

A.連續(xù)結(jié)構(gòu)
B.鏈接結(jié)構(gòu)
C.索引結(jié)構(gòu)
D.哈希結(jié)構(gòu)

28.設(shè)文件F1的當(dāng)前引用計數(shù)值為1，先建立F1的符號鏈接(軟鏈接)文件F2，再建 F1的硬鏈接文件F3，然后刪除F1。此時，F(xiàn)2和F3的引用計數(shù)值分別是(  )。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.下列的網(wǎng)絡(luò)協(xié)議中，(  )的運輸層協(xié)議是使用TCP的。

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

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

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

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

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

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

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

0.

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

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

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

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

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

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