2023年研究生類研究生入學考試專業課計算機學科專業綜合基礎歷年真題薈萃帶答案難題附詳解（圖片大小可自由調整）第1卷一.歷年考點試題黑鉆版(共60題)1.在以下的文件物理存儲組織形式中，______常用于存放大型的系統文件。A.連續文件B.串聯文件C.索引文件D.多重索引文件2.證明：對有向圖的頂點適當地編號，可使其鄰接矩陣為下三角形且主對角線為全0的充要條件是該圖為無環圖。3.試分析，在第一級磁盤容錯技術和第二級磁盤容錯技術中，各采取了哪些容錯措施?什么是寫后讀校驗?4.死鎖預防是保證系統不進入死鎖狀態的靜態策略，其解決辦法是破壞產生死鎖的4個必要條件之一。下列方法中破壞了“循環等待”條件的是______。A.銀行家算法B.一次性分配策略C.剝奪資源法D.資源有序分配策略5.某公司網絡的地址是/17，下列選項中，______一定屬于這個網絡。A./17B./20C./16D./206.設有整數0～n-1存放在整型數組A[0，…，n-1]中，請設計一個時間復雜度為O(n)，且只用常量空間復雜度O(1)的算法來實現對A的排序(要求按從小到大排序)。7.下圖是一個簡化的CPU與主存連接結構示意圖(圖中省略了所有多路選擇器)。其中有一個累加寄存器AC、一個狀態寄存器和其他四個寄存器(主存地址寄存器MAR、主存數據寄存器MDR、程序計數器PC和指令寄存器IR)，各部件及其之間的連線表示數據通路，箭頭表示信息傳送方向。

要求：

(1)寫出圖中a、b、c、d四個寄存器的名稱。

(2)簡述圖中指令從主存取到控制器的過程。

(3)說明數據從主存取出、運算、寫回主存所經過的數據通路(假定數據地址已在MAR中)。8.如果到達的分組的片偏移值為100，分組首部中的首部長度字段值為5，總長度字段值為100。請問：數據部分第一個字節的編號是多少?能夠確定數據部分最后一個字節的編號嗎?9.CPU響應中斷的時間是

。A.中斷源提出請求B.取指周期結束C.執行周期結束D.間址周期結束10.下列排序方法中，若將順序存儲更換為鏈式存儲，則算法的時間效率會降低的是______

Ⅰ．插入排序

Ⅱ．選擇排序

Ⅲ．起泡排序

Ⅳ．希爾排序

Ⅴ．堆排序A.僅Ⅰ、ⅡB.僅Ⅱ、ⅢC.僅Ⅲ、ⅣD.僅Ⅳ、Ⅴ11.在微程序控制器設計中，假設微命令采用最短編碼法，需產生N種微操作。則微命令控制字段要設置的位數是______。

12.證明：具有n個頂點和多于n-1條邊的無向連通圖G一定不是樹。13.對給定關鍵字的序號j(0≤j＜n)，要求在無序記錄A[0，…，n-1]中找按關鍵字從小到大排在第i位上的記錄，利用快速排序的劃分思想設計上述算法。14.下列功能中，屬于表示層提供的功能是______。A.擁塞控制B.透明傳輸C.死鎖處理D.文本壓縮15.對n(n大于等于2)個權值均不相同的字符構成哈夫曼樹，關于該樹的敘述中，錯誤的是

A.該樹一定是一棵完全二叉樹B.樹中一定沒有度為1的結點C.樹中兩個權值最小的結點一定是兄弟結點D.樹中任一非葉結點的權值一定不小于下一任一結點的權值16.通常為用戶提供4種使用接口，它們是終端命令、圖標菜單、系統調用和______。A.計算機高級指令B.宏命令C.類似DOS的批命令文件或UNIX的shell文件D.匯編語言17.執行一次磁盤輸入輸出操作所花費的時間包括______。A.尋道時間、延遲時間、傳送時間和等待時間B.尋道時間、等待時間、傳送時間C.等待時間、尋道時間、延遲時間、讀寫時間D.尋道時間、延遲時間、傳送時間18.設磁盤的I/O請求隊列中的柱面號為19、376、205、134、18、56、193、396、29、3、19、40，磁頭的起始位置為100，若采用SCAN(電梯調度)算法(磁頭的當前是往柱面號小的方向移動)，則磁頭移動共需移動的磁道數為______(該調度算法的磁頭移動到最內/外磁道后，就改變方向)。A.205B.480C.490D.51219.由于進程具有異步性，這就可能使進程按下述兩種順序向前推進：______和______。20.若系統中有五個并發進程涉及某個相同的變量A，則變量A的相關臨界區是由

臨界區構成。A.2個B.3個C.4個D.5個21.為進程分配連續內存的是______。A.分頁存儲管理B.分段存儲管理C.可變分區管理D.段頁式存儲管理22.單級中斷系統中，中斷服務程序內的執行順序是______。

Ⅰ．保護現場

Ⅱ．開中斷

Ⅲ．關中斷

Ⅳ．保存斷點

Ⅴ．中斷事件處理

Ⅵ．恢復現場

Ⅶ．中斷返回A.Ⅰ→Ⅴ→Ⅵ→Ⅱ→ⅦB.Ⅲ→Ⅰ→Ⅴ→ⅦC.Ⅲ→Ⅳ→Ⅴ→Ⅵ→ⅦD.ⅣⅠ→Ⅴ→Ⅵ→Ⅶ23.若循環隊列以數組Q[0..m-1]作為其存儲結構，變量rear表示循環隊列中的隊尾元素的實際位置，其移動按rear=(rear+1)MODm進行，變量length表示當前循環隊列中的元素個數，則循環隊列的隊首元素的實際位置是______。A.rear-lengthB.(rear-length+m)MODmC.(1+rear+m-length)MODmD.m-length24.下列死鎖的論述中，正確的論述是

。A.由于產生死鎖的基本原因是系統資源不足，因而預防死鎖最常用方法，是根據系統規模，配置足夠的系統資源B.由于產生死鎖的另一個基本原因是進程推進順序不當，因而預防死鎖的常用方法，是使進程的推進順序合法C.因為只要系統不進入不安全狀態，便不會產生死鎖，故預防死鎖的常用方法，是防止系統進入不安全狀態D.可以通過破壞產生死鎖的四個必要條件之一或其中幾個方法，來預防發生死鎖25.一組N個站點共享一個56kb/s的純ALOHA信道，每個站點平均每100s輸出一個1000bit的幀，即使前一個幀沒有發送完也依舊進行。問N可取的最大值是多少?26.隨著3D游戲軟件的大量出現，許多機器的顯卡中配置了具有3D功能的GPU，下列有關這類顯卡的顯示存儲器的敘述中，錯誤的是______。A.顯存大多數由DRAM芯片組成B.CPU和GPU都可以訪問顯存C.顯存和主存之間可采用DMA方式傳送數據D.顯存容量大致等于最高分辨率與像素深度的乘積27.對于長度為18的順序存儲的有序表，若采用折半查找，則查找第15個元素的比較次數為______。A.3B.4C.5D.628.下列有關曼徹斯特編碼的敘述正確的是______。A.每個信號起始邊界作為時鐘信號有利于同步B.將時鐘與數據取值都包含在信號中C.這種模擬信號的編碼機制特別適合于傳輸聲音D.每位的中間不跳變表示信號的取值為029.進程狀態由就緒狀態轉化到運行狀態是由

引起的。A.中斷事件B.進程狀態轉換C.進程調度D.程序被創建為進程30.通道管理沒有涉及的數據結構有______。

Ⅰ．設備控制表

Ⅱ．控制器控制表

Ⅲ．通道控制表

Ⅳ．系統設備表

Ⅴ．內存分配表A.僅ⅤB.Ⅳ和ⅤC.Ⅰ和ⅡD.Ⅰ、Ⅱ和Ⅲ31.設有n個進程共用一個相同的程序段，假設每次最多允許m個進程(m≤n)同時進入臨界區，則信號量S的初值為______。A.mB.nC.m-nD.-m32.采用順序結構存儲串，編寫一個實現串通配符匹配的函數pattern_index()，其中的通配符只有'?'，它可以和任一字符匹配成功，例如，pattern_index("?re"，"thereare")返回的結果是3。33.為了加快文件目錄的查找，許多操作系統為用戶強加了兩個文件操作系統調用：OPEN系統調用和CLOSE系統調用。但是在某些操作系統中，不需要打開和關閉文件操作用戶也可以進行文件讀/寫。請問在兩類系統中，讀和寫文件的系統調用分別應該包含哪些參數?34.下列關于PROM與掩模ROM的說法中，錯誤的是______。A.掩模ROM制成后不可改寫B.PROM制成后可編寫一次，編程之后不可再改寫C.PROM制成后可多次改寫D.以上說法都不對35.14.IEEE802.3MAC幀的最小幀長是

。A.64ByteB.128ByteC.512ByteD.1024Byte36.下列關于磁盤的說法中，錯誤的是______。A.本質上，U盤(閃存)是一種只讀存儲器B.RAID技術可以提高磁盤的磁記錄密度和磁盤利用率C.未格式化的硬盤容量要大于格式化后的實際容量D.計算磁盤的存取時間時，“尋道時間”和“旋轉等待時間”常取其平均值37.802.3標準定義的以太網中，實現“給幀加序號”功能的層次是______。A.物理層B.介質訪問控制子層(MAC)C.邏輯鏈路控制子層(LLC)D.網絡層38.計算機系統的層次結構，下列五個級別機器由下到上的順序是______。

Ⅰ．機器語言機器

Ⅱ．匯編語言機器

Ⅲ．高級語言機器

Ⅳ．微程序控制機器

Ⅴ．操作系統機器A.Ⅰ→Ⅱ→Ⅲ→Ⅳ→ⅤB.Ⅳ→Ⅰ→Ⅴ→Ⅱ→ⅢC.Ⅲ→Ⅱ→Ⅴ→Ⅰ→ⅣD.Ⅴ→Ⅳ→Ⅲ→Ⅱ→Ⅰ39.有一矩陣varA:array[1..100，1..100]ofinteger以行為先進行存儲。有一個虛存系統，物理內存共有三頁，其中一頁用來存放程序，其余兩頁用于存放數據。假設程序已在內存中占一頁，其余兩頁空閑。

程序A：

fori:=1to100do

forj:=1to100do

A[i,j]:=0;

程序B：

forj:=1to100do

fori:=1to100do

A[i,j]:=0;

若每頁可存放200個整數，程序A和程序B的執行過程各會發生多少次缺頁?若每頁只能存放100個整數呢?以上說明了什么問題?40.設排序二叉樹中結點的結構由三個域構成：數據域data，指向左兒子結點的指針域left，指向右兒子結點的指針域right。

設data域為正整數，該二叉樹樹根結點地址為T?，F給出一個正整數x。請編寫非遞歸程序，實現將data域的值小于等于x的結點全部刪除。41.下列四個序列中，______是堆。A.75，65，30，15，25，45，20，10B.75，65，45，10，30，25，20，15C.75，45，65，30，15．25，20，10D.75，45，65，10，25，30，20，1542.如果一個用戶需要實現漫游，那么它需要完成______工作。

Ⅰ．創建一個本地代理

Ⅱ．創建一個外部代理

Ⅲ．外部代理與該用戶本地代理進行聯系A.全部B.Ⅰ、ⅡC.Ⅰ、ⅢD.Ⅱ、Ⅲ43.試計算一個包括5段鏈路的傳輸連接的單程端到端時延。5段鏈路中有2段是衛星鏈路，每條衛星鏈路又由上行鏈路和下行鏈路兩部分組成，可以取這兩部分的傳播時延之和為250ms。每一個廣域網的范圍為1500km，其傳播時延可按150000km/s來計算。各數據鏈路速率為48kb/s，幀長為960b。44.下圖是一個3階B樹。分別畫出在插入65、15、40、30后B樹的變化。

45.數據總線的寬度由總線的______來定義。A.物理特性B.功能特性C.電氣特性D.時間特性46.二維數組Amn按行序為主序存放在內存，每個數組元素占1個存儲單元，則元素aij的地址計算公式是(

)。A.loc(aij)-loc(all)+[(i-1)*m+(j-1)]B.loc(aij)-loc(all)+[(j-1)*m+(i-1)]C.loc(aij)-loc(all)+[(i-1)*n+(j-1)]D.loc(aij)-loc(all)+[(j-1)*n+(i-1)]47.在可變式分區分配方案中，將空白區在空白區表中按地址遞增次序排列的是(

)。A.最佳適應算法B.最差適應算法C.最先適應算法D.最遲適應算法48.采用SPOOLing技術后，使得系統資源利用率

。A.提高了B.降低了C.有時提高有時降低D.出錯的機會增加了49.

不是常用三級時序系統中的一級。A.指令周期B.工作周期C.時鐘周期D.定時脈沖50.計算機系統中，創建的進程數量受到制約的主要因素是

。A.內存大小B.終端數目C.打開文件數D.處理機數量51.下列說法中正確的是______。A.如果有向圖的鄰接矩陣是對稱矩陣，則該有向圖一定是有向完全圖B.如果某個圖的鄰接矩陣不是對稱矩陣，則該圖一定是有向圖C.如果某個圖的鄰接矩陣是對稱矩陣，則該圖一定是無向圖D.鄰接矩陣表示法只存儲了邊的信息，沒有存儲頂點的信息52.用戶要求計算機系統所做的工作的集合稱為______。53.端口(port)和套接字(socket)的區別是什么?54.存SPOOLing技術中，用戶進程實際分配到的是______。A.用戶所需的外設B.一塊內存區，即虛擬設備C.共享設備的一部分存儲區D.虛擬設備的一部分空間55.TCP采用滑動窗口協議解決了______。A.端到端的流量控制B.整個網絡的擁塞控制C.端到端的流量控制和網絡的擁塞控制D.整個網絡的差錯控制56.下列______是動態半導體存儲器的特點。

Ⅰ．在工作中存儲器內容會產生變化

Ⅱ．每隔一定時間，需要根據原存內容重新寫入一遍

Ⅲ．一次完整的刷新過程需要占用兩個存儲周期

Ⅳ．一次完整的刷新過程只需要占用一個存儲周期A.Ⅰ、ⅢB.Ⅱ、ⅢC.Ⅱ、ⅣD.只有Ⅲ57.下列關于棧和隊列說法中，正確的是

。A.消除遞歸不一定需要使用棧B.對同一輸入序列進行兩組不同的合法入棧和出棧組合操作，所得的輸出序列也一定相同C.通常使用隊列來處理函數或過程調用D.隊列和棧是運算受限的線性表，只允許在表的兩端進行運算58.現在有三個同時到達的作業J1、J2和J3，它們的執行時間分別是T1、T2、T3，且T1＜T2＜T3。系統按單道方式運行且采用短作業優先調度算法，則平均周轉時間是

。A.T1+T2+T3B.(3×T1+2×T2+T3)/3C.(T1+T2+T3)/3D.(T1+2×T2+3×T3)/359.以下關于網絡操作系統的功能的敘述不正確的是

。A.網絡通信的任務是在源主機和目標主機之間，實現無差錯的數據傳輸B.在局域網中典型的共享資源有硬盤、打印機、文件和數據C.網絡操作系統最基本的功能是網絡管理D.網絡管理最基本的任務是安全管理60.已知小寫英文字母“a”的ASCII碼值為61H，現字母“g”被存放在某個存儲單元中，若采用偶校驗(假設最高位作為校驗位)，則該存儲單元中存放的十六進制數是______。A.66HB.E6HC.67HD.E7H第1卷參考答案一.歷年考點試題黑鉆版1.參考答案：A[解析]連續文件常用于存放大型的系統文件。2.參考答案：此題考查的知識點是無環圖的定義。根據題意，該有向圖頂點編號的規律是讓弧尾頂點的編號大于弧頭頂點的編號。由于不允許從某頂點發出并回到自身頂點的弧，所以鄰接矩陣主對角線元素均為0。先證明該命題的充分條件。由于弧尾頂點的編號均大于弧頭頂點的編號，在鄰接矩陣中，非零元素(A[i][j]=1)自然是落到下三角矩陣中；命題的必要條件是要使上三角為0，則不允許出現弧頭頂點編號大于弧尾頂點編號的弧，否則，就必然存在環路。(對該類有向無環圖頂點編號，應按頂點出度順序編號。)3.參考答案：在第一級磁盤容錯技術中，包括以下容錯措施：

(1)雙份目錄和雙份文件分配表。在磁盤上存放的文件目錄和文件分配表FAT均為文件管理所用的重要數據結構，所以為之建立備份。

(2)在系統每次加電啟動時都要對兩份目錄和兩份FAT進行檢查，以驗證它們的一致性。

在第二級磁盤容錯技術中，包括以下容錯措施：

(1)磁盤鏡像。在同一磁盤控制器下增設一個完全相同的磁盤驅動器，在每次向文件服務器的主磁盤寫入數據后，都要采用寫后讀校驗方式將數據再同樣地寫到備份磁盤上，使兩者具有完全相同的位像圖。

(2)磁盤雙工。將兩臺磁盤驅動器分別接到兩個磁盤控制器上，同樣使這兩臺磁盤機鏡像成對，從而在磁盤控制器發生故障時起到數據保護的作用。在磁盤雙工時，由于每一個磁盤都有自己的獨立通道，故可以同時(并行)地將數據寫入磁盤。在讀入數據時，可采用分離搜索技術，從響應快的通道上取得數據，因而加快了對數據的讀取速度。

(3)熱修復重定向和寫后讀校驗。兩者均用于防止將數據寫入有缺陷的盤塊中。就熱修復重定向而言，系統將一定的磁盤容量作為熱修復重定向區，用于存放當發現盤塊有缺陷時的待寫數據，并對寫入該區的所有數據進行登記，方便將來對數據進行訪問。而寫后讀校驗則是為了保證所有寫入磁盤的數據都能寫入到完好的盤塊中，故在每次從內存緩沖區向磁盤中寫入一個數據塊后，應立即從磁盤上讀出該數據塊并送至另一緩沖區中，再將該緩沖區中內容與原內存緩)中區中在寫后仍保留的數據進行比較。若兩者一致，便認為此次寫入成功，可繼續寫入下一個盤塊；否則，則重寫。若重寫后兩者仍不一致，則認為該盤塊有缺陷，此時便將應寫入該盤塊的數據寫入熱修復重定向區中，并將該損壞盤塊的地址記錄在壞盤塊表中。4.參考答案：D資源有序分配策略將資源編號并有序分配，如果前置資源沒有得到，則不能申請后續資源，因此系統中不會出現得到后續資源而請求前置資源的情況，破壞了循環等待條件，因此答案選擇D選項。

一次性分配策略破壞了請求與保持條件，有資源就全部分配，沒有就一點也不分配；剝奪資源法破壞了不剝奪條件；銀行家算法是對情況進行預測，如果存在安全序列則分配，如果不存在則拒絕分配，因此銀行家算法并沒有破壞4個必要條件之一，不屬于死鎖預防。5.參考答案：B[解析]/17轉換為二進制是11001010.01101110.1XXXXXXX.XXXXXXXX。

A：/17轉換為二進制是11001010.01101110.0XXXXXXX.XXXXXXXX，第17位和/17的第17位不同，所以A不屬于這個網絡。

B：/20轉換為二進制是11001010.01101110.1010XXXX.XXXXXXXX，前17位和/17的前17位完全相同，所以B屬于此網絡。

C：/16這個是具有欺騙性的表達方法，實際上這個網絡是/16，網絡號為16位的網絡不可能屬于一個網絡號為17位的網絡。

D：/20轉換為二進制是11001010.01101110.0001XXXX.XXXXXXXX。第17位和/17的第17位不同，所以D不屬于這個網絡。6.參考答案：本題關鍵字本身即指示了其在序列中的位置，由此可以寫出如下代碼：

voidorder(intA[],intn)

{

inti;

for(i=0;i＜n;++1)

A(A[i]]=A[i];

}[說明]本題用直接給A[]從i=0到n-1進行賦值的做法是不對的，雖然結果一樣。因為實際應用中，關鍵字一般都與數據域相關，有可能需要將相關數據放在正確位置上，而不僅僅是將關鍵字放在正確位置上。7.參考答案：(1)b單向連接微控制器，由微控制器的作用不難得知b是指令寄存器(IR)；a和c直接連接主存，只可能是MDR和MAR，c到主存是單向連接，a和主存雙向連接，根據指令執行的特點，MAR只單向給主存傳送地址，而MDR既存放從主存中取出的數據又要存放將要寫入主存的數據，因此c為主存地址寄存器(MAR)，a為主存數據寄存器(MDR)。d具有自動加1的功能，且單向連接MAR，不難得出為程序計數器(PC)。

因此，a為MDR，b為IR，c為MAR，d為PC。

(2)先從程序計數器(PC)中取出指令地址，將指令地址送入主存地址寄存器(MAR)，在相關的控制下從主存中取出指令送至主存數據寄存器(MDR)，然后將MDR中的指令送至指令寄存器(IR)，最后流向微控制器，供微控制器分析并執行指令。

因此，取指令的數據通路為：PC→MAR，M(MAR)→MDR→IR→控制器

(3)與(2)的分析類似，根據MAR中的地址去主存取數據，將取出的數據送至主存數據寄存器(MDR)，然后將MDR中的數據送至ALU進行運算，運算的結果送至累加器(AC)，運算結束后將AC中的結果送至MDR，最后將MDR中的數據寫入主存。

因此，從主存取出、運算和寫回主存所經過的數據通路為：MAR→M，M(MAR)→MDR→ALU，ALU→AC，AC→MDR→M(MAR)。8.參考答案：分片的片偏移值表示其數據部分首字節在原始分組的數據部分中的相對位置，單位為8字節。首部長度字段以4字節為單位，總長度字段以字節為單位。題目中，分組的片偏移值為100，那么其數據部分第一個字節的編號是800。因為分組的總長度100B，首部長度為4×5=20B，所以數據部分長度為80B。那么該分組的數據部分的最后一個字節的編號是879。9.參考答案：C因為CPU是在指令周期的最后一個機器周期——執行周期的結束時刻統一向所有中斷源發出中斷查詢信號，所以答案為C。10.參考答案：D11.參考答案：C[解析]由于微命令控制字段必須是一個整數，所以在最短編碼法中為位。

最短編碼法將所有的微命令統一編碼，每條微指令只定義一個微命令。若微命令的總數為N，操作控制字段的長度為L，則最短編碼法應滿足下列關系式：

L≥log2N12.參考答案：此題考查的知識點是圖的定義。具有n個頂點n-1條邊的無向連通圖是自由樹，即沒有確定根結點的樹，每個結點均可當根。若邊數多于n-1條，因一條邊要連接兩個結點，則必因加上這一條邊而使兩個結點多了一條通路，即形成回路。形成回路的連通圖不再是樹(在圖論中樹定義為無回路的連通圖)。13.參考答案：本算法不需要將整個記錄排序，只進行查找第j個記錄(從小到大排序)。

程序代碼如下：

voidsplit(intA[],intlow,inthigh,int&i)

{

intj;

elemtypex;

i=low;j=high;x=A[i];

//初始化

while(i＜j)

{

while(A[j]＞=x&&i＜j)

//從右向左遍歷

--j;

if(i＜j)

{

A[i]=A[j];++i;

//相當于交換A[i]與A[j]

}

while(A[i]＜=x&&i＜j)

//從左向右遍歷

++i;

if(i＜j)

{

A[j]=A[i];--j;

//相當于交換A[i]與A[j]

}

}

A[i]=x;

//x定位在位置i處

}

sort(intA[],intj,intn)

{

ints=0,t=n-1,k;

split(A,s,t,k);

while(k!=j)

if(k＜j)

split(A,k+1,t,k);

//元素在右邊，對右邊進行劃分

else

split(A,s,k-1,k);

//元素在左邊，對左邊進行劃分

returnA[j];

}14.參考答案：D[解析]表示層涉及在應用層進程之間傳送的數據表示，這可以包括加密、正文壓縮或者兩個端點系統，使用的語法或數據格式之間的轉換(例如EBCDIC和ASCII碼之間的轉換)，也可以包括為了建立適當的語法與遠方對等表示層進行的協商過程。15.參考答案：A[解析]考查哈弗曼樹的特性。

哈夫曼樹為帶權路徑長度最小的二叉樹，不一定是完全二叉樹。

哈夫曼樹中沒有度為1的結點，B正確；

構造哈夫曼樹時，最先選取兩個權值最小的結點作為左右子樹構造一棵新的二叉樹，C正確；

哈夫曼樹中任一非葉結點P的權值為其左右子樹根結點權值之和，其權值不小于其左右子樹根結點的權值，在與結點P的左右子樹根結點處于同一層的結點中，若存在權值大于結點．P權值的結點Q，那么結點Q的兄弟結點中權值較小的一個應該與結點P作為左右子樹構造新的二叉樹。

綜上可知，哈夫曼樹中任一非葉結點的權值一定不小于下一層任一結點的權值。16.參考答案：C操作系統作為用戶與計算機硬件系統之間的接口，用戶可通過3種方式使用計算機：①命令方式；②系統調用方式；③圖形、窗口方式。題于中所說的終端命令屬于①，圖標菜單屬于③，系統調用屬于②。而C選項中的批處理命令就是把一批終端命令放在一個文本里，然后批量執行。UNIX的shell文件也是類似的，因此C選項屬于命令方式。因此本題選C。

宏命令一般是指用戶與應用程序之間的接口。17.參考答案：B[解析]本題考查磁盤操作時間的概念。18.參考答案：C本題其實是有爭議的。問題其實就是SCAN算法和LOOK算法的區別。SCAN算法是要掃到頭的，而LOOK算法是移動到最內/外磁道后，就改變方向。但很多時候教材只提到SCAN算法，而算法描述其實是LOOK算法?？忌绻龅竭@樣的問題，建議這樣處理：如果沒有給出最內、最外磁道號，題目就默認是考查LOOK算法；給出最內、最外磁道號的，而又無特殊說明的，就默認考查SCAN算法。2012年的大綱解析中，對SCAN算法的解釋是要掃到底才改變方向。解答如下：

尋道順序為100、56、40、29、19、18、3、134、193、205、376、396，移動磁道數分別為44、16、11、10、1、15、131、59、12、171、20，總數為490。

注意：

1)對于SCAN算法，磁臂從磁盤的一端向另一端移動，同時當磁頭移過每個柱面時，處理位于該柱面上的服務請求。當到達另一端時，磁頭改變移動方向，處理繼續。

2)C-SCAN調度是SCAN調度的變種，主要提供一個更為均勻的等待時間。與SCAN一樣，C-SCAN將磁頭從磁盤一端移到磁盤的另一端，隨著移動不斷地處理請求。不過，當磁頭移到另一端時，它會馬上返回到磁盤開始處，返回時并不處理請求。C-SCAN調度算法基本上將柱面當做一個環鏈，以將最后柱面和第一柱面相連。

3)LOOK調度，正如上所述，SCAN和C-SCAN位磁頭在整個磁盤寬度內進行移動。事實上，這兩個算法都不是這樣實現的。通常，磁頭只移動到一個方向上最遠的請求為止，接著馬上回頭，而不是繼續到磁盤的盡頭。這種形式的SCAN和C-SCAN稱為LOOK調度和C-LOOK調度，這是因為它們在朝一個方向移動時會看是否有請求。19.參考答案：進程推進順序合法；進程推進順序非法20.參考答案：D臨界資源是諸進程之間應采取互斥方式訪問的，也就是一次只允許一個進程訪問的資源，可以為硬件，軟件，變量，數據，表格，隊列等，并不單指硬件資源。臨界區就是每個進程中訪問臨界資源的那段代碼。五個并發進程都涉及了變量A，每一個進程中都有訪問變量A的代碼，所以每個進程中都有相關臨界區，因此是五個臨界區構成。21.參考答案：C22.參考答案：A[解析]在單級(或單重)中斷系統中，不允許中斷嵌套。中斷處理過程為：①關中斷；②保存斷點；③識別中斷源；④保存現場；⑤中斷事件處理；⑥恢復現場；⑦開中斷；⑧中斷返回。其中，①～③由硬件完成，④～⑧由中斷服務程序完成，故選A。23.參考答案：C[解析]按照循環隊列的定義，因為元素移動按照rear=(rear+1)MODm進行，則當數組Q[m-1]存放了元素之后，下一個入隊的元素將存放到Q[0]中，因此隊列的首元素的實際位置是(rear-length+1+m)MODm。24.參考答案：DA：不可能根據系統的規模，配置足夠的系統資源，因為系統的資源是有限的。B：這種方法不能保證死鎖不發生，而且進程推進過程很復雜，實現合理的順序不太可能。C：系統進入不安全狀態不一定會產生死鎖，防止系統進入不安全狀態不太可能，故不是常用的方法。25.參考答案：對于純ALOHA協議，其信道利用率為0.184，故可用帶寬是0.184*56kb/s。每個站需要的帶寬是1000/100=10b/s。因此，N可取的最大值是10304/10≈1030。26.參考答案：D[解析]從早期的EDORAM、MDRAM、SDRAM、SGRAM、VRAM、WRAM等到今天廣泛采用的DDRSDRAM，顯存經歷了很多代的進步。目前市場中所采用的顯存類型主要有SDRAM，DDRSDRAM和DDRSGRAM三種，故A選項正確。

GPU是顯示卡的“心臟”，也就相當于CPU在計算機中的作用，CPU和GPU都可以訪問顯存，故B選項正確。

DMA方式高效的I/O控制方式，當然可以應用于顯存和主存之間的數據傳輸，故C選項正確。

D選項錯誤比較明顯，舉例如下：顯示分辨率基本都是1024×768，顏色位數為32bit，那么需要的顯存容量=1024×768×32bit/8bit=3145728B，可是這針對是2D顯卡(普通平面)，如果是3D加速卡，那么需要的顯存容量為1024×768×32bit×3/8bit=9437184B=9.216MB，這是最低需求，而且還必須增加一定的容量作為紋理顯示內存，否則當顯示資源被完全占用時，計算機只有占用主內存作為紋理內存，這樣的二次調用會導致顯示性能下降，因此作為真正的3D加速卡顯存容量一定大于9.216MB。27.參考答案：B折半查找要求查找表用順序存儲結構存放且各數據元素按關鍵字有序(升序或降序)排列，也就是說折半查找只適用于對有序順序表進行查找。有序順序表也稱為有序表。

折半查找的基本思想是：首先以整個查找表作為查找范圍，用查找條件中給定值k與中間位置結點的關鍵字比較，若相等，則查找成功；否則，根據比較結果縮小查找范圍，如果k的值小于關鍵字的值，根據查找表的有序性可知查找的數據元素只有可能在表的前半部分，即在左半部分子表中，所以繼續對左子表進行折半查找；若k的值大于中間結點的關鍵字值，則可以判定查找的數據元素只有可能在表的后半部分，即在右半部分子表中，所以應該繼續對右子表進行折半查找。每進行一次折半查找，要么查找成功，結束查找，要么將查找范圍縮小一半，如此重復，直到查找成功或查找范圍縮小為空即查找失敗為止。28.參考答案：B[解析]曼徹斯特編碼將每一個碼元分成兩個相等的間隔。前面一個間隔為高電平而后一個間隔為低電平表示碼元1，碼元0正好相反；也可以采用相反的規定，因此D錯。位中間的跳變作為時鐘信號，每個碼元的電平作為數據信號，因此B正確。曼徹斯特編碼是將時鐘和數據包含在數據流中，在傳輸代碼信息的同時，也將時鐘同步信號一起傳輸到對方，因此A錯。聲音是模擬數據，而曼徹斯特編碼最適合傳輸二進制數字信號，因此C錯。29.參考答案：C[解析]本題目考查進程的基本狀態轉換。處于就緒態的進程經過進程調度則會獲得CPU執行，從而轉化為執行態。因此應該選C。30.參考答案：A[解析]本題考查通道管理。為了實現對I/O設備的管理和控制、需要對每臺設備、通道及控制器的情況進行登記。設備分配依據的主要數據結構有，系統設備表：記錄系統中全部設備的情況。設備控制表：系統為每個設備配置一張設備控制表，用戶記錄本設備的情況。控制器控制表：系統為每個控制器設置一張用于記錄本控制器情況的控制器控制表，它反映控制器的使用狀態及于通道的鏈接情況等。通道控制表：用來記錄通道的特性、狀態、及其他的管理信息。31.參考答案：A[解析]本題考查互斥信號量的設置?；コ庑盘柫康某踔祽獮榭捎觅Y源數，在本題中為可同時進入臨界區的資源數。每當一個進程進入臨界區，S減1，減到-(n-m)為止，此時共有|S|個進程在等待進入。32.參考答案：本題增加了'?'的處理功能。實現代碼如下：

intpattern_index(Str*subs,Str*s)

{

inti,j,k;

for(i=0;s-＞ch[i];++i)

for(j=i,k=0;(s-＞ch[j]==subs-＞ch[k])||(subs-＞ch[k]=='?');++j,++k)

if(subs-＞ch[k+1]=='\0')

returni+1;

return-1;

}33.參考答案：支持文件打開和關閉的文件系統參照《計算機考研考點精講及復習指導》一書的對應章節的“考點精講”。

在不支持文件打開和關閉的文件系統中，讀/寫文件的系統調用參數包括：①文件名；②文件讀/寫緩沖地址；③文件讀/寫長度；④文件讀/寫指針位置。[解析]在文件系統實現上存在許多選擇，OPEN和CLOSE并不是唯一的實現選擇。OPEN和CLOSE存在的唯一理由是整數比較的開銷小于字串匹配，但是有許多沒有實現OPEN/CLOSE接口的操作系統，其性能并沒有顯著的下降(這個性能問題可以進一步討論，讀者可以繼續考慮這樣的實現方法)。

是否支持OPEN/CLOSE接口的問題本質上是有狀態和無狀態服務器問題。支持OPEN/CLOSE接口的操作系統實現了一個有狀態的服務器——文件系統，文件系統維持文件的操作狀態，因此調用者無需提供狀態參數。而不支持OPEN/CLOSE接口的操作系統則實現了一個無狀態服務器，因此需調用者自行維護文件狀態，在調用時必須提供類似于“讀/寫指針位置”的狀態信息。34.參考答案：C[解析]PROM(ProgrammableRead-OnlyMemory)——可編程只讀存儲器，也叫One-TimeProgrammable(OTP)ROM(一次可編程只讀存儲器)，是一種可以用程序操作的只讀內存。其最主要特征是只允許數據寫入一次，如果數據燒入錯誤只能報廢。

注：可擦除的ROM的名字中都帶E，如EPROM、EEPROM等，還有一個是FlashMemory。35.參考答案：A36.參考答案：B[解析]閃存是在E2PROM的基礎上發展起來的，本質上是只讀存儲器。RAID將多個物理盤組成像單個邏輯盤，不會影響磁記錄密度，也不可能提高磁盤利用率。37.參考答案：C[解析]以太網沒有網絡層。物理層的主要功能是：信號的編碼和譯碼、比特的接收和傳輸；MAC子層的主要功能是：組幀和拆幀、比特差錯檢測、尋址、競爭處理；LLC子層的主要功能是：建立和釋放數據鏈路層的邏輯連接、提供與高層的接口、差錯控制、給幀加序號。38.參考答案：B[解析]現代計算機系統是一個硬件與軟件組成的綜合體，可以把它看成按功能劃分的多級層次結構。計算機系統的多層次結構，如下圖所示。層次結構由高到低的次序分別是：應用語言機器級、高級語言機器級、匯編語言機器級、操作系統機器級、傳統機器級、微程序機器級。對每一個機器級的用戶來說，都可以將此機器看成是一臺獨立的使用自己特有的“機器語言”的機器。

39.參考答案：有兩個內存塊可以用來存放數組信息，每個主存塊可存放200個數組元素，數組中的元素按行編址。對于程序A來說，其訪問順序也是按行進行，由于每行有100個元素，每訪問兩行遇到一次缺頁中斷。如果采用FIFO或LRU頁面調度算法，一共產生50次缺頁中斷。

對于程序B來說，其訪問順序按列進行，與數組的按行存儲順序不一致，每訪問兩個數組元素將發生一次缺頁中斷。如果采FIFO或LRU頁面調度算法，一共產生5000次缺頁中斷。

若每頁只能存放100個整數，對于程序A，數組的存儲順序與訪問順序一致，每訪問一行數組遇到一次缺頁中斷。如果采用FIFO或LRU頁面調度算法，會產生100次缺頁中斷。對于程序B，數組的存儲順序與訪問順序不一致，每訪問一個數組元素遇到一次缺頁中斷。如果采用FIFO或LRU頁面調度算法，一共產生10000次缺頁中斷。

以上結果說明：頁面越大，缺頁中斷次數越少；頁面越小，缺頁中斷次數越多。40.參考答案：利用二叉排序樹的性質，從根結點開始查找，若根結點的值小于等于x，則根結點及其左子樹均應刪除，然后以右子樹的根結點為樹根，重新開始查找。若根結點的值大于x，則順左子樹向下查找，直到某結點的值小于等于x，則該結點及其左子樹均應刪除。下面設計一查找算法，確定被刪除子樹的根結點，再設計一刪除算法，刪除以被刪結點為根的子樹。

typedefstructnode{

intdata;

structnode*left,*right;

}BiTNode,*BSTree;

voidDelTree(BSTreer){

//非遞歸刪除以r為根的二叉排序樹

BSTreeS[];

//棧，容量足夠大，棧中元素是二叉排序樹結點的指針

BSTreep;

inttop=0;

while(r!=null||top＞0){

while(r!=null){S[++top]=r;r=r-＞left;}

//沿左分支向下

if(top＞0)

//退棧，沿棧頂結點的右子樹向下刪除，釋放被刪除結點空間

{p=S[top--];r=p-＞fight;free(p);}

}

}//DelTree

voidDeleteAllx(BSTreeT,intx){

//在二叉排序樹T中，刪除所有小于等于x的結點

BSTreep=T,q;

while(T&&T-＞data＜=x){

//根結點的值小于等于x

p=T;T=T-＞fight;p-＞fight=null;

DelTree(p);}

//刪除二叉樹P，刪除持續到“根”結點值大于x或T為空樹為止

if(T){

q=T;p=T-＞left;

while(p&&p-＞data＞x){

//沿根結點左分支向下，查小于等于x的結點

while(p&&p-＞data＞x){q=p;p=p-＞left;}

//q記p的雙親

if(p)

//p結點的值小于等于x

{q-＞left=p-＞fight;p-＞fight=null;DelTree(p);}

p=q-＞left;

//再查原p的右子樹中小于等于x的結點

}

}41.參考答案：C堆排序是另一種基于選擇的排序方法。n個元素的序列{k1，k2，k3，．．．kn}，當且僅當滿足以下關系時，稱之為堆：

或者：

其中i=1，2，…，n/2。

若將同以上序列對應的一維數組看成是一棵完全二叉樹，則堆的含義表明：該完全二叉樹的所有非終端結點均不大于(或不小于)其左、右孩子結點的值。由此，若{k1，k2，．．．kn)是堆，則堆頂元素(或完全二叉樹的根結點)必定是該序列n個元素中的最小值(或者最大值)。

若將堆看成是一棵以k1為根的完全二叉樹，則這棵完全二叉樹中的每個非終端結點的值均不大于(或不小于)其左、右孩子結點的值。由此可以看出，若一棵完全二叉樹是堆，則根結點一定是這n個結點中的最小者(或最大者)。下面圖給出的兩個堆的示例。

從堆的定義可以看出，若將堆用一棵完全二叉樹表示，則根結點是當前堆中所有結點的最小者(或最大者)。堆排序的基本思想是：首先將待排序的記錄序列構造一個堆，此時，選出了堆中所有記錄的最小者或最大者，然后將它從堆中移走，并將剩余的記錄再調整成堆，這樣又找出了次小(或次大)的記錄，以此類推，直到堆中只有一個記錄為止，每個記錄出堆的順序就是一個有序序列。42.參考答案：A[解析]如果一個站點的用戶希望實現漫游，那么它必先創建一個本地代理，如果一個站點允許其他的訪問者進到它的網絡中，那么它必須創建一個外部代理。當移動主機在一個外地站點中啟動時，它與當地的外部代理聯系，并且進行注冊。然后，外部代理與該用戶的本地代理進行聯系，并且交給它一個移交地址。43.參考答案：5段鏈路的傳播時延=250×2+(1500/150000)×3×1000=530ms。

5段鏈路的發送時延=960/(48×1000)×5×1000=100ms。

所以5段鏈路單程端到端時延=530+100=630ms。44.參考答案：插入過程：

插入65后，如下圖所示：

插入65后的3階B樹

插入15后，如下圖所示：

插入15后的3階B樹

插入40后，如下圖所示：

插入40后的3階B樹

插入30后，如下圖所示：

插入30后的3階B樹45.參考答案：B總線的物理特性描述了總線的根數、插頭、形狀及引腳排列等物理連接方式。功能特性描述總線的每一根線的功能，如數據總線的寬度指明了訪問一次存儲器或外設時能夠交換數據的位數。電氣特性定義每根線上信號的傳遞方向及有效電平范圍。時間特性定義了每根線在什么時間有效。46.參考答案：A二維數組就是平常所說的矩陣，也可以看成是數據元素是一維數組的一位數組。由于計算機內部存儲器的地址是一維線性排列的，故在存儲數據時，必須將二維數組轉換為計算機的內部存儲形式才可以。一般有兩種存儲方式：以行為主的存儲方式(row—major)和以列為主的存儲方式(column—major)。

設二維數組A[1:U1，1:U2]，該數組有(U1-1)+1=U1行，有(U1-1)+1=U1列。設每個元素占d個空間，數組的起始地址為L1。

①以行為主(row—major)：也稱行優先存儲。其特點為：以每一行為單位，一行一行地放入內存，如C語言、PASCAL語言等都是如此處理二維數組的。

②以列為主(column—major)：也稱列優先存儲。其特點為：以每一列為單位，一列一列地放入內存，如Fortran語言就是如此處理二維數組的。二維數組A可以看成由U2個一維數組組成，每個一維數組有U1個元素。同1)類似，有：

*第j列數據元素的起始地址為：(j-1)×U1×d+L1

*數組元素A[i，j]的地址為：Loc(A[i，j])=L1+(j-1)×U1×d-6(i-1)×d

重要說明：二維數組Am*n的含義是：該數組有m行(0～m-1第一維)，有n列(0～n-1，第二維)，占用m*n個存儲空間。假設每個數據元素占用L個存儲單元(可理解為字節)，則二維數組A中任意一個元素aij的存儲位置為：

行優先：LOC(