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

一、1.單項(xiàng)選擇題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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算法的時(shí)間復(fù)雜度正確的是(  )。

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

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

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

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

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

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

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

11.IEEE754標(biāo)準(zhǔn)浮點(diǎn)數(shù)的尾數(shù)采用(  )機(jī)器數(shù)形式。

A.原碼
B.補(bǔ)碼
C.移碼
D.反碼

12.字長(zhǎng)16位的補(bǔ)碼定點(diǎn)小數(shù)的表示范圍是(  )。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

30.驅(qū)動(dòng)調(diào)度算法中，(  )算法可能會(huì)隨時(shí)改變移動(dòng)臂的運(yùn)動(dòng)方向。

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

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

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

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

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

33.測(cè)得一個(gè)以太網(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ā)送了編號(hào)為0～7的幀。當(dāng)計(jì)時(shí)器超時(shí)時(shí)，若發(fā)送方只收到0、2、3號(hào)幀的確認(rèn)，則發(fā)送方需要重發(fā)的幀數(shù)是(  )。

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

35.一個(gè)C類地址，采用了255．255．255．240作為子網(wǎng)掩碼，那么這個(gè)C類地址可以劃分為(  )個(gè)子網(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é)議中，(  )的運(yùn)輸層協(xié)議是使用TCP的。

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

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

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

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

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

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

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

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

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