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

一、1.單項選擇題

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

0.設(shè)n是描述問題規(guī)模的非負(fù)整數(shù)，下面程序片段的時間復(fù)雜度是(     )。
 int i=1：
 while(i<=n)
  i=i*2：

A.O(log₂n)
B.O(n)
C.O(nlog₂n)
D.O(n²)

1.下列關(guān)于棧和隊列說法中，正確的是(     )。

A.消除遞歸不一定需要使用棧
B.對同一輸入序列進(jìn)行兩組不同的合法入棧和出棧組合操作，所得的輸出序列也一定相同
C.通常使用隊列來處理函數(shù)或過程處理
D.隊列和棧是運(yùn)算受限的線性表，只允許在表的兩端進(jìn)行運(yùn)算

2.在解決計算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則從該緩沖區(qū)中取出數(shù)據(jù)打印。該緩沖區(qū)的結(jié)構(gòu)是(     )。

A.棧
B.隊列
C.數(shù)組
D.線性表

3.下列關(guān)于二叉樹的說法中，正確的是(     )。

A.度為2的有序樹就是二叉樹
B.含有n個結(jié)點(diǎn)的二叉樹，其高度為「10g₂n」+1
C.完全二叉樹中，若一個結(jié)點(diǎn)沒有左孩子，則它必是葉子結(jié)點(diǎn)
D.在任意一棵非空二叉排序樹中，刪除某結(jié)點(diǎn)后又將其插入，則所得的二叉排序樹與刪除前原二叉排序樹相同

4.含有n個結(jié)點(diǎn)的三叉樹的最小高度是(     )。
  

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

5.某二叉樹的先序遍歷序列為IJKLMNO，中序遍歷序列為JLKINMO，則后序遍歷序列是 (     )。

A.JLKMNOI
B.LKNJOMI
C.LKJNOMI
D.LKNOJMI

6.設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點(diǎn)個數(shù)分別為N1，N2和N3。與森林F對應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個數(shù)是(     )。

A.N1
B.N1+N2
C.N3
D.N2+N3

7.以下關(guān)于圖的說法正確的是(     )。
 I圖G的生成樹是該圖的一個極小連通子圖
 Ⅱ生成樹中最長路徑的起點(diǎn)和終點(diǎn)的度均為1
 Ⅲ對任意一個圖，從某個頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先遍歷，可訪問圖的所有頂點(diǎn)

A.I、Ⅱ
B.Ⅱ、Ⅲ
C.I、Ⅱ
D.僅有Ⅱ

8.已知有向圖G=(V，A)，其中V={a，b，c，d，e)，A={<a，b>，<a，c>，<d，c>，<d，e>，<b，e>，<c，e>}，對該圖進(jìn)行拓?fù)渑判?，下面序列中不是拓?fù)渑判虻氖?     )。

A.a，d，c，b，e
B.d，a，b，c，e
C. a，b，d，c，e
D.a，b，c，d，e

9.序列(8，9，10，4，5，6，20，1，2)，只能是(     )排序方法兩趟排序后的結(jié)果。

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

10.對關(guān)鍵碼序列(23，1 7，72，60，25，8，68，71，52)進(jìn)行堆排序，輸出兩個最小關(guān)鍵碼后的剩余堆是(     )。

A.(23，72，60，25，68，71，52)
B.(23，25，52，60，71，72，68)
C.(71，25，23，52，60，72，68)
D.(23，25，68，52，60，72，71)

11.MIPS(每秒百萬次指令數(shù))和MFL()PS(每秒百萬次浮點(diǎn)運(yùn)算數(shù))是衡量CPU性能的兩個指標(biāo)，其中(     )。

A.MIPS適合衡量向量處理機(jī)的性能，MFLOPS適合衡量標(biāo)量處理機(jī)的性能
B.MIPS適合衡量標(biāo)量處理機(jī)的性能，MFLOPS適合衡量向量處理機(jī)的性能
C.MIPS反映計算機(jī)系統(tǒng)的峰值性能，MFLOPS反映計算機(jī)系統(tǒng)的持續(xù)性能
D.MIPS反映計算機(jī)系統(tǒng)的持續(xù)性能，MFLOPS反映計算機(jī)系統(tǒng)的峰值性能

12.計算機(jī)中常采用下列幾種編碼表示數(shù)據(jù)，其中，±0編碼相同的是(     )。
  I原碼；  Ⅱ反碼；  Ⅲ補(bǔ)碼；  Ⅳ移碼

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

13.已知小寫英文字母“a”的ASCⅡ碼值為61H，現(xiàn)字母“g”被存放在某個存儲單元中，若采用偶校驗(假設(shè)最高位作為校驗位)，則該存儲單元中存放的十六進(jìn)制數(shù)是(     )。

A.66 H
B.E6 H
C.67 H
D.E7 H

14.按照IEEEE754標(biāo)準(zhǔn)規(guī)定的32位浮點(diǎn)數(shù)(41A4C000)₁₆。對應(yīng)的十進(jìn)制數(shù)是(     )。

A.4．59375
B.-20．59375
C.-4．59375
D.20.59375

15.下面關(guān)于作為PC機(jī)內(nèi)存使用的ROM和RAM的敘述中，錯誤的是(     )。

A.ROM和RAM都是半導(dǎo)體存儲器
B.PC機(jī)關(guān)機(jī)后，存儲在PC機(jī)CMOS RAM中的內(nèi)容一般不會丟失
C.RAM芯片掉電后，存放在芯片中的內(nèi)容會丟失
D.F1ash ROM芯片中的內(nèi)容經(jīng)一次寫入后再也無法更改

16.下列有關(guān)I／O編址方式的描述中，正確的是(     )。

A.統(tǒng)一編址是將I／O地址看作是存儲器地址的一部分，可用專門的I／O指令對設(shè)備進(jìn)行訪問
B.獨(dú)立編址是指I／O地址和存儲器地址是分開的，所以對I／O訪問必須有專門的I／O指令
C.統(tǒng)一編址是指I／O地址和存儲器地址是分開的，所以可用訪存指令實現(xiàn)CPU對設(shè)備的訪問
D.獨(dú)立編址是將I／O地址看作是存儲器地址的一部分，所以對I／0訪問必須有專門的I／O指令

17.某指令流水線由5段組成，第1、3、5段所需時間為△t，第2、4段所需時間分別為3△t、2△t，如下圖所示，那么連續(xù)輸入n條指令時的吞吐率(單位時間內(nèi)執(zhí)行的指令個數(shù))TP是 (     )。
  

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

18.以下說法中，錯誤的是(     )。

A.指令執(zhí)行過程中的第一步就是取指令操作
B.為了進(jìn)行取指令操作，控制器需要得到相應(yīng)的指令
C.取指令操作是控制器自動進(jìn)行的
D.在指令長度相同的情況下，所有取指令的操作都是相同的

19.串行接口是指(     )。

A.接口與系統(tǒng)總線之間串行傳送，接口與I／O設(shè)備之間串行傳送
B.接口與系統(tǒng)總線之間串行傳送，接口與I／O設(shè)備之間并行傳送
C.接口與系統(tǒng)總線之間并行傳送，接口與I／O設(shè)備之間串行傳送
D.接口與系統(tǒng)總線之間并行傳送，接口與I／O設(shè)備之間并行傳送

20.硬盤查找時間的含義是(     )。

A.使磁頭移動到要找的柱面上所需的時間
B.在柱面上找到要找的磁道所需的時間
C.在磁道上找到要找的扇區(qū)所需的時間
D.在扇區(qū)中找到要找的數(shù)據(jù)所需的時間

21.計算機(jī)系統(tǒng)總線包括①地址總線、②數(shù)據(jù)總線和③控制總線。若采用DMA方式傳送數(shù)據(jù)，需要DMA控制器控制的是(     )。

A.①②
B.②③
C.①③
D.①②③

22.進(jìn)程P1、P2和I P3單獨(dú)執(zhí)行時間分別為10分、15分和20分，其中處理機(jī)占用時間分別為2分、3分和12分。如果采用多道程序設(shè)計技術(shù)使其并發(fā)，并假設(shè)處理機(jī)的利用率可以達(dá)到60％，加上系統(tǒng)開銷5分，那么并發(fā)使得計算機(jī)系統(tǒng)的效率提高了(     )。

A.63％
B.38％
C.74%
D.26%

23.進(jìn)程創(chuàng)建的時候，不需要做的是(     )。

A.填寫一個該進(jìn)程的進(jìn)程表項
B.分配該進(jìn)程適當(dāng)?shù)膬?nèi)存
C.將該進(jìn)程插入就緒隊列
D.為該進(jìn)程分配CPU

24.某系統(tǒng)中共有7臺打印機(jī)，3個進(jìn)程共享此打印機(jī)設(shè)備，每個進(jìn)程最多請求使用n臺，則，系統(tǒng)不會死鎖的n值是(     )。

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

25.下面的敘述中，正確的是(     )。

A.進(jìn)程獲得處理機(jī)運(yùn)行是通過調(diào)度得到的
B.優(yōu)先級是進(jìn)程調(diào)度的重要依據(jù)，一旦確定不能改動
C.在單處理機(jī)的系統(tǒng)中，任何時刻都只有一個進(jìn)程處于運(yùn)行狀態(tài)
D.進(jìn)程申請?zhí)幚頇C(jī)而得不到滿足時，其狀態(tài)變?yōu)樽枞?/p>

26.一個64位的計算機(jī)系統(tǒng)中，地址線寬為64位，實際使用的虛擬地址空間的大小是2⁴⁸，若采用虛擬頁式存儲管理，每頁的大小為2¹³，即8KB，頁表表項長為8字節(jié)，采用多級頁表進(jìn)行管理，那么，多級頁表的級次最小是(     )。

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

27.在請求頁式虛擬存儲系統(tǒng)中，假設(shè)系統(tǒng)為某個進(jìn)程分配了4個物理頁框，頁面的引用串號為0，1，2，4，5，2，3，4，3，0，1，4，5，3，采用固定分配局部置換，當(dāng)采用OPT算法時會產(chǎn)生的缺頁中斷次數(shù)是(     )。

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

28.文件的安全管理中，主要通過控制用戶對文件的訪問的設(shè)置的是(     )。

A.文件訪問權(quán)限
B.管理員或文件主對文件屬性的設(shè)置
C.文件讀寫權(quán)限
D.用戶級別

29.一個磁盤有N個磁道，尋道時每移過一個磁道耗時T秒，文件相鄰的數(shù)據(jù)塊在磁盤上存放的位置平均相隔1 3個磁道，磁盤旋轉(zhuǎn)延時平均R秒，每個存儲塊的傳輸時間為P秒，在這種情況下，傳輸100個數(shù)據(jù)塊需要的時間是(     )。

A.13T+100(R+P)
B.100(13T+R+P)
C.13(T+100R+P)
D.100(13T+P)+R

30.在磁盤上，最容易導(dǎo)致存儲碎片發(fā)生的物理文件結(jié)構(gòu)是(     )。

A.隱式鏈接
B.順序存放
C.索引存放
D.顯式鏈接

31.磁盤是一種可共享的設(shè)備，因此某一時刻讀寫它的用戶進(jìn)程可以是(     )。

A.任意多個
B.能限定多個
C.至少能有一個
D.至多能有一個

32.正確描述網(wǎng)絡(luò)體系結(jié)構(gòu)中的分層概念的是(     )。

A.保持網(wǎng)絡(luò)靈活且易于修改
B.所有的網(wǎng)絡(luò)體系結(jié)構(gòu)都使用相同的層次名稱和功能
C.把相關(guān)的網(wǎng)絡(luò)功能組合在一層中
D.A和C

33.在相隔400KM的兩地間通過電纜以4800b／s的速率傳送3000 L匕特長的數(shù)據(jù)包，從開始發(fā)送到接收完數(shù)據(jù)需要的時間是(     )。

A.480ms
B.607ms
C.612ms
D.627 ms

34.設(shè)有兩個子網(wǎng)202．118．133．0／24和202．118．130．0／24，如果進(jìn)行路由匯聚，得到的網(wǎng)絡(luò)地址是(     )。

A.202．118．128．0／21
B.202．1 18．128．0／22
C.202．118．130．0／22
D.202．118．132．0／20

35.在因特網(wǎng)中，IP數(shù)據(jù)報的傳輸需要經(jīng)由源主機(jī)和中途路由器到達(dá)目的主機(jī)，下面說法正確的是(     )。

A.源主機(jī)和中途路由器都知道IP數(shù)據(jù)報到達(dá)目的主機(jī)需要經(jīng)過的完整路徑
B.源主機(jī)知道IP數(shù)據(jù)報到達(dá)目的主機(jī)需要經(jīng)過的完整路徑，而中途路由器不知道
C.源主機(jī)不知道IP報到達(dá)目的主機(jī)需要經(jīng)過的完整路徑，而中途路由器知道
D.源主機(jī)和中途路由器都不知道IP數(shù)據(jù)報到達(dá)目的主機(jī)需要經(jīng)過的完整路徑

36.在IP數(shù)據(jù)報的傳遞過程中，IP數(shù)據(jù)報報頭中保持不變的域是(     )。

A.標(biāo)識和片偏移
B.標(biāo)志和頭部校驗和
C.標(biāo)識和目的地址
D.標(biāo)志和生存周期

37.一個快速以太網(wǎng)交換機(jī)的端口速率為100Mbps，若該端口可以支持全雙工傳輸數(shù)據(jù)，那么該端口實際的傳輸帶寬是(     )。

A.100Mbps
B.150Mbps
C.200Mbps
D.1000Mbps

38.假設(shè)某應(yīng)用程序每秒產(chǎn)生一個60字節(jié)的數(shù)據(jù)塊，每個數(shù)據(jù)塊被封裝在一個TCP報文中，然后在封裝到一個IP數(shù)據(jù)報中。那么最后每個數(shù)據(jù)報所含有的應(yīng)用數(shù)據(jù)所占的百分比是(     )。(注：TCP報文和IP數(shù)據(jù)報的頭部沒有附加字段)

A.20％
B.40％
C.60%
D.80%

39.TCP協(xié)議規(guī)定HTTP端口號為80的進(jìn)程是(     )。

A.客戶
B.分布
C.服務(wù)器
D.主機(jī)

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

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

0. 下圖中的頂點(diǎn)表示村莊，有向邊代表交通路線，若要建立一家醫(yī)院，試問建在哪一個村莊能使各村莊總體交通代價最小?
  

1. 快速排序算法中，如何選取一個界值(又稱為軸元素)，影響著快速排序的效率，而且界值也并不一定是被排序序列中的一個元素。例如，我們可以用被排序序列中所有元素的平均值作為界值。編寫算法實現(xiàn)以平均值為界值的快速排序方法。

2. 在虛擬地址和物理地址均為32位、頁大小為4KB的某種體系結(jié)構(gòu)中，假定存在下表所示的地址映像關(guān)系，問：對應(yīng)于下列虛擬地址的物理地址分別是什么?
  (1)22433007H
  (2)13385ABCH
  (3)ABC89011H
  

3. 設(shè)某計算機(jī)有四個中斷源，優(yōu)先順序按1→2→3→4降序排列，若1、2、3、4中斷源的服務(wù)程序中對應(yīng)的屏蔽字分別為1110、0100、0110、11 11，試寫出這四個中斷源的中斷處理次序(按降序排列)。若四個中斷源同時有中斷請求，畫出CPU執(zhí)行程序的軌跡。

4. 某銀行的營業(yè)廳有多個柜員窗口，可以同時辦理業(yè)務(wù)。銀行的營業(yè)廳中安排有n張座椅供儲戶休息等候。每個儲戶在進(jìn)入營業(yè)廳時會在排隊機(jī)上取得一個號碼，若此前沒有客戶，則排隊機(jī)就會喚醒一個柜員為儲戶服務(wù)，當(dāng)沒有儲戶時柜員便可以休息。若儲戶較多，則所有柜員均會參與服務(wù)，當(dāng)排隊儲戶數(shù)超過柜員數(shù)時，沒有被服務(wù)的儲戶便會在座椅上休息，并等候叫號。當(dāng)座位滿時，再進(jìn)入營業(yè)廳的儲戶不再從排隊機(jī)上獲取號碼，會離開去找另外的營業(yè)廳。若將銀行的柜員和儲戶的行為看成是不同類型的進(jìn)程，請設(shè)計一個程序，利用信號量來完成上述操作，用類C語言寫出程序。

5. 在Windows操作系統(tǒng)中支持FAT32文件系統(tǒng)，一個文件的物理結(jié)構(gòu)是用文件分配表FAT來表示的，在FAT32中，文件分配表每個表項占32位。如果某分區(qū)為FAT32磁盤文件系統(tǒng)，每簇8扇區(qū)，扇區(qū)的大小為512字節(jié)，則該分區(qū)最大可為多少字節(jié)?每個FAT表占用的存儲空間是多少字節(jié)?

6. 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如下圖所示，與C相連接的節(jié)點(diǎn)B，E，D的權(quán)值分別是6，5，3。
  
  如果C收到的三張矢量表分別為：
  
  試根據(jù)距離矢量路由算法給出C所構(gòu)造的路由表，并給出計算過程，路由表結(jié)構(gòu)如下表所示。