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

一、1.單項選擇題

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

0.下面說法錯誤的是( )。
 (1)算法原地工作的含義是指不需要任何額外的輔助空間
 (2)在相同的規(guī)模n下，復(fù)雜度O(n)的算法在時間上總是優(yōu)于復(fù)雜度O(2n)的算法
 (3)所謂時間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界
 (4)同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率就越低

A.-1
B.(1)，(2)
C.(1)，(4)
D. -3

1.若線性表最常用的運算是查找第i個元素及其前驅(qū)的值，則采用(  )存儲方式節(jié)省時間。

A.單鏈表
B.雙鏈表
C.單循環(huán)鏈表
D.順序表

2.設(shè)計一個判別表達(dá)式中左右括號是否配對出現(xiàn)的算法，采用(  )數(shù)據(jù)結(jié)構(gòu)最佳。

A.順序表
B.隊列
C.鏈表
D.棧

3.設(shè)n階方陣是一個上三角矩陣，則需存儲的元素個數(shù)為(  )。

A.n
B.n×n
C.n×n／2
D.n(n+1)／2

4.在二叉樹的順序存儲中，每個結(jié)點的存儲位置與其父結(jié)點、左右子樹結(jié)點的位置都存在一個簡單的映射關(guān)系，因此可與三叉鏈表對應(yīng)。若某二叉樹共有n個結(jié)點，采用三叉鏈表存儲時，每個結(jié)點的數(shù)據(jù)域需要d個字節(jié)，每個指針域占用4個字節(jié)，若采用順序存儲，最后一個結(jié)點下標(biāo)為k(起始下標(biāo)為1)，那么(  )時采用順序存儲更節(jié)省空間。

A.d＜12n／(k-n)
B.d＞12n／(k-n)
C.d＜12n／(k+n)
D.d＞12n／(k+n)

5.中綴表達(dá)式A-(B+C／D)*E的后綴形式是(  )。

A.AB-C+D／E*
B.ABC+D／-E*
C.ABCD／E*+-
D.ABCD／+E*-

6.有m個葉子結(jié)點的哈夫曼樹所具有的結(jié)點數(shù)為(  )。

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

7.簡單無向圖的鄰接矩陣是對稱的，可以對其進(jìn)行壓縮存儲。若無向圖G有n個結(jié)點，其鄰接矩陣為A[1…n，1…n]，且壓縮存儲在B[1…k]，則k的值至少為(  )。

A.n(n+1)／2
B.n²／2
C.(n-1)(n+1)／2
D.n(n-1)／2

8.設(shè)順序存儲的某線性表共有123個元素，按分塊查找的要求等分為3塊。若對索引表采用順序查找方法來確定子塊，且在確定的子塊中也采用順序查找方法，則在等概率的情況下，分塊查找成功的平均查找長度為(  )。

A.21
B.23
C.41
D.62

9.快速排序最易發(fā)揮其長處的情況是(  )。

A.被排序的數(shù)據(jù)中含有多個相同排序碼
B.被排序的數(shù)據(jù)已基本有序
C.被排序的數(shù)據(jù)完全無序
D.被排序的數(shù)據(jù)中的最大值和最小值相差懸殊

10.在機(jī)器數(shù)中，正數(shù)的符號位用“1”表示的是(  )。

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

11.IEEE 754標(biāo)準(zhǔn)規(guī)定的64位浮點數(shù)格式中，符號位為1位，階碼為11位，尾數(shù)為52位。則它所能表示的最小規(guī)格化負(fù)數(shù)為(  )。

A.-(2-2⁵²)×2^-1023
B.-(2-2^-52)×2⁺¹⁰²³
C.-1×2-^-1024
D.-(1-2⁵²)×2⁺²⁰⁴⁷

12.按其數(shù)據(jù)流的傳遞過程和控制節(jié)拍來看，陣列乘法器可認(rèn)為是(  )。

A.全串行運算的乘法器
B.全并行運算的乘法器
C.串一并行運算的乘法器
D.并啊一串行運算的乘法器

13.字長相同的兩種浮點數(shù)，第一種階碼位數(shù)較多，尾數(shù)位數(shù)少，第二種階碼位數(shù)少，尾數(shù)位數(shù)多，階的底數(shù)都是2，則(  )。

A.表示的數(shù)的范圍與精度相同
B.第一種數(shù)的范圍大，但精度低
C.第二種數(shù)的范圍大，精度高
D.第一種數(shù)的范圍大，精度高

14.4片74181ALU和1片74182CLA器件相配合，具有(  )進(jìn)位傳遞功能。

A.串行進(jìn)位
B.組內(nèi)并行進(jìn)位，組間并行進(jìn)位
C.組內(nèi)并行進(jìn)位，組間串行進(jìn)位
D.組內(nèi)串行進(jìn)位，組間并行進(jìn)位

15.需要刷新的存儲器是( )。

A.SRAM
B.DRAM
C.ROM
D.上述三種

16.雙端口存儲器在(  )情況下會發(fā)生讀／寫沖突。

A.左端口與右端口的地址碼不同
B.左端口與右端口的地址碼相同
C.左端口與右端口的數(shù)據(jù)碼相同
D.左端口與右端口的數(shù)據(jù)碼不同

17.操作數(shù)地址存放在寄存器的尋址方式叫(  )。

A.相對尋址方式
B.變址寄存器尋址方式
C.寄存器尋址方式
D.寄存器間接尋址方式

18.在微程序控制中，機(jī)器指令和微指令的關(guān)系是(  )。

A.每一條機(jī)器指令由一條微指令解釋執(zhí)行
B.每一條機(jī)器指令由一段微程序解釋執(zhí)行
C.每一條微指令由一條機(jī)器指令解釋執(zhí)行
D.每一段微程序由若干條機(jī)器指令解釋執(zhí)行

19.直接映射Cache的主要優(yōu)點是實現(xiàn)簡單。這種方式的主要缺點是(  )。

A.它比其他幾利Cache組織類型更貴
B.如果使用中的2個或多個block映射到Cache的同一行，命中率將下降
C.它的存取時間大于其他類型
D.Cache 中的Block數(shù)隨著主存的容量線性增加

20.由于CPU內(nèi)部的操作速度較快，而CPU訪問一次主存所花的時間較長，因此機(jī)器周期通常用( )來規(guī)定。

A.主存中讀取一個指令字的最短時間
B.主存中讀取一個數(shù)據(jù)字的最長時間
C.主存中寫入一個數(shù)據(jù)字的平均時間
D.主存中取一個數(shù)據(jù)字的平均時間

21.DMA方式是在(  )之間建立直接的數(shù)據(jù)通路。

A.CPU與外部設(shè)備
B.外部設(shè)備與外部設(shè)備
C.主存與外部設(shè)備
D.主存與外部設(shè)備

22.在設(shè)計實時操作系統(tǒng)中，首先要考慮的是(  )。

A.靈活性和可靠性
B.實時性和可靠性
C.交互性和實時性
D.資源利用率

23.(  )進(jìn)程調(diào)度算法綜合考慮到了CPU密集型進(jìn)程和I／O密集型進(jìn)程。

A.時間片輪轉(zhuǎn)
B.優(yōu)先級
C.多重隊列
D.彩票

24.信號量S的初值定義為5，在S上調(diào)用了10次wait操作和8次signal操作后，S的值應(yīng)為(  )。

A.2
B.3
C.7
D.13

25.臨界區(qū)是指并發(fā)進(jìn)程中訪問共享變量的(  )段。

A.管理信息
B.信息存儲
C.數(shù)據(jù)
D.程序

26.死鎖的預(yù)防是通過破壞產(chǎn)生死鎖的四個必要條件來實現(xiàn)的。下列方法中，破壞了“循環(huán)等待”條件的是( )。

A.資源按序分配策略
B.銀行家算法
C.一次性分配資源策略
D.資源分配圖化簡法

27.系統(tǒng)“抖動”現(xiàn)象的發(fā)生是由(  )引起的。

A.置換算法選擇不當(dāng)
B.交換的信息量過大
C.內(nèi)存容量不足
D.請求頁式管理方案

28.兩個進(jìn)程P、Q都需要三個資源1，2，3，系統(tǒng)中有資源1、2、3各一個，如果P請求資源的順序是1、2、3，Q請求資源的順序任意，共有3!=6種排列，其中共有(  )個排列可能導(dǎo)致死鎖。

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

29.對于三級文件目錄，若主目錄、用戶目錄及子目錄各級分別最多有3、4、5個目錄項，則為找到一指定文件的目錄項(絕對路徑名方式)，最多只需檢索的目錄項數(shù)是(  )。

A.12個
B.17個
C.23個
D.60個

30.在文件系統(tǒng)中，文件的不同物理結(jié)構(gòu)有不同的優(yōu)缺點。在下列文件的物理結(jié)構(gòu)中，(  )具有直接讀寫文件任意一個記錄的能力，又提高了文件存儲空間的利用率。

A.順序結(jié)構(gòu)
B.鏈接結(jié)構(gòu)
C.Hash結(jié)構(gòu)
D.索引結(jié)構(gòu)

31.啟動磁盤執(zhí)行一次輸入／輸出操作時，(  )是硬件設(shè)計時就固定的。

A.尋找時間
B.傳送時間
C.延遲時間
D.一次I／O操作的總時間

32.在網(wǎng)絡(luò)中計算機(jī)接收的信號是(  )。

A.數(shù)字信號
B.模擬信號
C.廣播信號
D.脈沖信號

33.通常通信信道的帶寬越大，在數(shù)據(jù)傳輸中失真將會(  )。

A.嚴(yán)重
B.不變
C.越大
D.越小

34.在共享介質(zhì)的以太網(wǎng)中，采用的介質(zhì)訪問控制方法是(  )。

A.并發(fā)連接
B.CSMA／CD
C.時間片
D.令牌

35.IP層的功能不包括( )。

A.差錯處理
B.數(shù)據(jù)報路由選擇
C.無連接的數(shù)據(jù)報傳輸
D.提供可靠連接

36.路由器在ISO／OSI開放系統(tǒng)參考模型中對應(yīng)于(  )。

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

37.TCP使用( )機(jī)制來進(jìn)行流量控制。

A.三次握手
B.二次握手
C.Windows窗口
D.滑動窗口

38.下列應(yīng)用層協(xié)議中，(  )協(xié)議是基于UDP傳輸?shù)摹?/p>

A.DNS
B.SMTP
C.HTTP
D.FTP

39.在OSI參考模型中，同一結(jié)點內(nèi)相鄰層之間通過(  )來進(jìn)行通信。

A.協(xié)議
B.接口
C.進(jìn)程
D.應(yīng)用程序

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

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

0. 給定單鏈表的結(jié)點結(jié)構(gòu)
  typedef struct node *link；
  struct node{int item，link next；)；
 將兩個升序單鏈表歸并為一個升序單鏈表。

1. 某中央處理器的數(shù)據(jù)通路如圖所示。MDR為內(nèi)存數(shù)據(jù)寄存器，PC為程序計數(shù)器，IR為指令寄存器。所有的單線箭頭為控制微命令。
  (1)請說明圖中部件X的名稱和功能、寄存器Y的名稱和功能。
  (2)請解釋：為什么要設(shè)置T暫存器?
  (3)假定指令格式為RS型指令，其中“SUB R，A”指令的操作為：R←R-[A]，[A]為內(nèi)存地址A所存儲的內(nèi)容。請畫出SUB指令的指令周期流程圖，并給出每個微操作對應(yīng)的微命令。

2. 設(shè)某系統(tǒng)有兩種磁盤配置：一種單磁盤結(jié)構(gòu)，一種4磁盤組陣列結(jié)構(gòu)。每個磁盤每磁道64個扇區(qū)，每扇區(qū)1 024．字節(jié)，轉(zhuǎn)速為10 000 rpm。找道時間為6 ms。兩種結(jié)構(gòu)的磁盤控制器每次訪問的延遲時間均為1 ms。設(shè)I／O系統(tǒng)的性能只與磁盤和控制器有關(guān)，單磁盤中連續(xù)訪問的扇區(qū)在磁盤組中將盡量分布在不同磁盤中。設(shè)扇區(qū)可以按照任意順序讀寫。問：@A@若從單盤結(jié)構(gòu)的順序排列的扇區(qū)中讀取4 KB，每次I／O操作用時多少?@B@若從陣列結(jié)構(gòu)的順序排列的扇區(qū)中讀取4 KB，每次I／O操作用時多少?@C@設(shè)讀請求是隨機(jī)的，其中一半的請求從順序排列的扇區(qū)中讀取4KB，另一半的請求從順序排列的扇區(qū)中讀取16 KB。請比較兩種組織結(jié)構(gòu)的I／O性能。

3. 某閱覽室晚間開放，第一個進(jìn)入的讀者開燈，最后一個離開的讀者關(guān)燈。利用P、V原語操作實現(xiàn)讀者進(jìn)程。

4. 給定頁面請求序列RS=cadbebabcd，頁框為4，起始為空，寫出LRU頁面置換過程。

5. 如圖所示一臺路由器連接3個以太網(wǎng)。請根據(jù)圖中給出的參數(shù)回答如下問題：
 (1)該TCP／IP網(wǎng)絡(luò)使用的是哪一類IP地址?
 (2)寫出該網(wǎng)絡(luò)劃分子網(wǎng)后所采用的子網(wǎng)掩碼。
 (3)系統(tǒng)管理員將計算機(jī)D和E按照圖中所示結(jié)構(gòu)連入網(wǎng)絡(luò)并使用所分配的地址對TCP／IP軟件進(jìn)行常規(guī)配置后，發(fā)現(xiàn)這兩臺機(jī)器上的網(wǎng)絡(luò)應(yīng)用程序不能夠正常通信。這是為什么?
 (4)如果你在主機(jī)C上要發(fā)送一個IP分組，使得主機(jī)D和主機(jī)E都會接收它，而子網(wǎng)3和子網(wǎng)4上的主機(jī)都不會接收它，那么該IP分組應(yīng)該填寫什么樣的目標(biāo)IP地址?