沈陽師范大學(xué)教育技術(shù)學(xué)院計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)操作系統(tǒng)歷考研真題匯編附答案

1、沈陽師范大學(xué)教育技術(shù)學(xué)院862 計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)）歷年考研真題匯編附答案最新資料， WORD格式，可編輯修改！目 錄第一部分沈陽師范大學(xué)教育技術(shù)學(xué)院862 計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)）歷年考研真題匯編2014年沈陽師范大學(xué)教育技術(shù)學(xué)院867 計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)）考研真題.2013年沈陽師范大學(xué)教育技術(shù)學(xué)院867 計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)）考研真題.第二部分全國碩士研究生入學(xué)統(tǒng)一考試408 計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合歷年真題及詳解. 2012年全國碩士研究生入學(xué)統(tǒng)一考試408計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合真題 2012年全國

2、碩士研究生入學(xué)統(tǒng)一考試408計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合真題及詳解2011年全國碩士研究生入學(xué)統(tǒng)一考試408計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合真題 2011年全國碩士研究生入學(xué)統(tǒng)一考試408計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合真題及詳解2010年全國碩士研究生入學(xué)統(tǒng)一考試408計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合真題 2010年全國碩士研究生入學(xué)統(tǒng)一考試408計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合真題及詳解2009年全國碩士研究生入學(xué)統(tǒng)一考試408計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合真題 2009年全國碩士研究生入學(xué)統(tǒng)一考試408計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合真題及詳解說明：沈陽師范大學(xué)2012 年之前參加全國統(tǒng)考408 計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合， 2013 年開始自主命題，科

3、目改為 867 計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)），2015 年科目代碼改為862。為幫助考生全面復(fù)習(xí)，特提供2009 2012 年 408 計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合真題及詳解。第一部分沈陽師范大學(xué)教育技術(shù)學(xué)院2014 年沈陽師范大學(xué)教育技術(shù)學(xué)院862 計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)）歷年考研真題匯編867 計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)）考研真題科目代碼： 867科目名稱：計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)）適用專業(yè)名稱：計算機(jī)應(yīng)用技術(shù)考生注意：請將答案寫在答題紙上，寫在本題簽及草紙上無效?？荚嚭蟊绢}簽同答題紙一并交回。一、單項選擇題 （共 10 題，

4、每題 2 分，合計 20 分）1某算法的時間復(fù)雜度為O(n2)，表明該算法（）。A問題規(guī)模是n2B執(zhí)行時間等于n2棧的C執(zhí)行時間與n2 成正比22 設(shè)線性表有n 個元素，以下操作中，（）在順序表上實(shí)現(xiàn)比在鏈表上實(shí)現(xiàn)效率更高。A輸出第 i （ 1i n）個元素B交換第 1 個元素與第2 個元素的值C順序輸出這n 個元素的值D輸出與給定值x 相等的元素在線性表中的序號3給定一個空棧，若10、20、 23、13 依次進(jìn)棧，然后有兩個數(shù)出棧，又有3 個數(shù)進(jìn)棧，第一次進(jìn)23 現(xiàn)在在（）。A已出棧B從棧底算起第3 個C棧頂D從棧底算起第4 個4循環(huán)隊列 qu（其隊頭指針front指向隊列中隊頭元素的前一個

5、位置，隊尾指針?biāo)氐奈恢?，隊列中的單元個數(shù)為MaxSize）的隊滿足條件是（）。A（ qu.rear+1 ） %MaxSize=(qu.front+1)%MaxSizerear指向隊尾元B(qu.rear+1)%MaxSize=qu.front+1C(qu.rear+1)%MaxSize=qu.frontDqu.rear=qu.front5一棵二叉樹的中序序列為 ABDCEFG，后序序列為 BDCAFGE，則其左子樹中的節(jié)點(diǎn)個數(shù)為（）。A3B2C4D56根據(jù)使用頻率為5 個字符設(shè)計的哈夫曼編碼不可能是（）。A111,110,10,01,00B000,001,010,011,1C100,11,10

6、,1,0D001,000,01,11,107對所示的無向圖，從頂點(diǎn)1 開始進(jìn)行深度優(yōu)先遍歷，可得到的頂點(diǎn)訪問序列為（）。A1243576B1243567C1245637D12345768對于下圖，以下（）是其拓?fù)湫蛄小1,3,4,6,2,5,7B1,3,2,6,4,5,7C1,3,4,5,2,6,7D1,2,5,3,4,6,79對數(shù)據(jù)序列 15,9,7,8,20,-1,4進(jìn)行排序 , 一趟排序后的結(jié)果為9,15,7,8,20,-1,4,采用的是（）。A簡單選擇排序B起泡排序C直接插入排序D堆排序10對一組數(shù)據(jù) (2,12,16,88,5,10)進(jìn)行排序 , 若前三趟的結(jié)果如下:第一趟： 2,

7、12,16,5,10,88第二趟： 2,12,5,10,16,88第三趟： 2,5,10,12,16,88則采用的排序方法可能是() 。A起泡排序B希爾排序C歸并排序D基數(shù)排序二、應(yīng)用題 （共 4 題，每題 10 分，合計 40 分）11使用普里姆算法構(gòu)造如圖所示的圖G中從頂點(diǎn) 1 開始的一棵最小生成樹。12設(shè)有一組關(guān)鍵字19,1,23,14,55,20,84,27,68,11,10,77，其哈希函數(shù)如下：H(key)=key%13采用開放地址法的線性探測法解決沖突，試在018 的哈希表中對該關(guān)鍵字序列構(gòu)造哈希表。13已知有 6 個頂點(diǎn)（頂點(diǎn)編號為0-5 ）的有向帶權(quán)圖G，其鄰接矩陣A 為上三

8、角矩陣，按行為主序（行優(yōu)先）保存在如下的一維數(shù)組中。4654333要求：1）寫出圖 G的鄰接矩陣 A。2）畫出有向帶權(quán)圖 G。3）求圖 G的關(guān)鍵路徑，并計算該關(guān)鍵路徑的長度。14將整數(shù)序列 4,5,7,2,1,3,6中的數(shù)依次插入到一棵空的平衡二叉樹中，構(gòu)造相應(yīng)的平衡二叉樹。三、算法設(shè)計題 （共 3 題，每題 10 分，合計 30 分）15設(shè) C=a1,b 1, a 2,b 2 , ,a n,b n 為一線性表，采用帶頭節(jié)點(diǎn)的hc 單鏈表存放，設(shè)計一個就地算法，將其拆分為兩個線性表（它們都用單鏈表存放），使得：A= a ,a, ,an ，B=b , b, ,bn121216假設(shè)二叉樹采用二叉鏈

9、存儲結(jié)構(gòu)存儲，試設(shè)計一個算法，計算一棵給定二叉樹的所有分支節(jié)點(diǎn)個數(shù)。17設(shè)計一個算法，判斷一個數(shù)據(jù)序列是否構(gòu)成一個小根堆。四、簡答題 （共 6 題，每題 5 分，合計 30 分）18什么是操作系統(tǒng)的基本功能？19描述系統(tǒng)調(diào)用的含義。20說明什么是進(jìn)程間的直接制約與間接制約。21說明什么是虛擬存儲器。22請說明分區(qū)存儲管理方式的主要優(yōu)缺點(diǎn)。23說明什么是中斷。五、綜合題 （共 2 題，每題 15分，合計30 分）24若有以下四個作業(yè)以 1、2、 3、 4 的順序，在0 時刻幾乎同時到達(dá)系統(tǒng)并立即進(jìn)入調(diào)度：作業(yè)名所需 CPU時間作業(yè) 19小時作業(yè) 22小時作業(yè) 310小時作業(yè) 45小時假設(shè)系統(tǒng)中沒

10、有其他作業(yè)，試給出對它們實(shí)施 FCFS調(diào)度算法的計算結(jié)果，并計算其平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。25幾個并行進(jìn)程共享一個數(shù)據(jù)集（如文件或表格）時，有些進(jìn)程可能只是要求讀這數(shù)據(jù)集的內(nèi)容，而另一些進(jìn)程則可能要求修改這數(shù)據(jù)集的內(nèi)容。這種情況在操作系統(tǒng)中是很普遍的。通常我們稱讀數(shù)據(jù)的進(jìn)程為讀者，而把要求修改數(shù)據(jù)的進(jìn)程稱為寫者。用P、 V 操作來描述讀者寫者問題。2013 年沈陽師范大學(xué)教育技術(shù)學(xué)院867 計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)）考研真題代碼： 868科目名稱：計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合適用專業(yè)名稱：計算機(jī)應(yīng)用技術(shù)考生注意：請將答案寫在答題紙上，寫在本題簽及草紙上無效。考試后本題簽同答

11、題紙一并交回。一、單項選擇題 （共 30 題，每題 2 分，合計 60 分）1某算法的時間復(fù)雜度為 O(n2) ，表明該算法的（）。A問題規(guī)模是 n2B執(zhí)行時間等于 n2C執(zhí)行時間與 n2 成正比D問題規(guī)模與 n2 成正比2設(shè)線性表中有 2n 個元素，以下操作中，（）在單鏈表上實(shí)現(xiàn)要比在順序表上實(shí)現(xiàn)效率更高。A刪除指定的元素B在最后一個元素的后面插入一個新元素C順序輸出前 k 個元素D交換第 i 個元素和第 2n-i-1 個元素的值 (i=0,1,n -1)3在一個單鏈表 L 中，指針 p 指向 L 的某個結(jié)點(diǎn)，在 p 之前插入一個指針 s 所指結(jié)點(diǎn)時的操作為 （）。As-next= p-ne

12、xt ； p-next=s ； t=p-data；p-data= s-data； s-data= t；Bp-next=s ；s-next= p-next ； t=p-data；p-data= s-data； s-data= t；Cs-next= p-next ； p-next=s ； p-data= s-data ；t=p-data ； s-data= t；Dp-next=s ；s-next= p-next ； t= s-data；s-data p-data； p-data= t；12n1i的值（）。4已知一個棧的進(jìn)棧序列是 1，2，3，n，其輸出序列是 p ,p, ,p ，若 p =n，則

13、pAiBn-iCn-i+1D不確定5對稀疏矩陣進(jìn)行壓縮存儲，常用的兩種方法是（）。A二元組和散列表B三元組和十字鏈表C三角矩陣和對角矩陣D對角矩陣和十字鏈表6廣義表（ a）， a）的表頭和表尾分別是（）。A（ a）和（ a）Ba 和（ a）C（ a）和 aD（ a）和（ a）7已知二叉樹的先序序列為ABDEGCF，中序序列為DBGEACF，則后序序列為（）。AGEDBFCABDGEBFCACDGEBAFCDEBFDGCA8一棵完全二叉樹上有1000 個結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個數(shù)是（）。A250B500C505D5019線索二叉樹是一種（）結(jié)構(gòu)。A邏輯B邏輯和存儲C物理D線性10以數(shù)據(jù)集2 ， 5

14、，7，9， 13 為權(quán)值構(gòu)造一棵哈夫曼樹，則其帶權(quán)路徑長為（）。A78B80C81D7911. 一個有向圖的鄰接表存儲如圖1 所示，現(xiàn)按深度優(yōu)先搜索遍歷，從頂點(diǎn)v1 出發(fā)，所得到的頂點(diǎn)序列是（ ）。v12 圖1 圖的3鄰接表4 Av1，v2， v3， v4， v5 v235 Bv，v ， v ， v ， v312354vCv1，v2， v4， v5， v3 v4 5 Dv，v ， v ， v ， vv51253412任意一個無向連通圖（）最小生成樹。A只有一棵B一定有多棵C有一棵或多棵4D可能不存在13若一個有向圖中的頂點(diǎn)不能排成一個拓?fù)湫蛄?，則可斷定該有向圖（）。A是個有根有向圖B是個強(qiáng)連通

15、圖C含有多個入度為0 的頂點(diǎn)D含有頂點(diǎn)數(shù)目大于1 的強(qiáng)連通分量14順序查找法適合于存儲結(jié)構(gòu)為（）的線性表。A哈希存儲B索引存儲C壓縮存儲D順序存儲或鏈?zhǔn)酱鎯?5在含有 27 個結(jié)點(diǎn)的二叉樹排序樹上，查找關(guān)鍵字為35 的結(jié)點(diǎn)，則依次比較的關(guān)鍵字有可能是（）。A28，36，18，46，35B18，36，28，46，35C46，28，18，36，35D46，36，18，28，3516在有序表 a 1.20 中，采用二分查找算法查找元素值等于a12 的元素，所比較過元素的次數(shù)為（）。A4B5C3D617數(shù)據(jù)序列 8， 9， 10，4，5，6， 20， 1， 2 只能是下列排序算法中的（ ）的兩趟排序后

16、的結(jié)果。A選擇排序B冒泡排序C插入排序D堆排序18就平均性能而言，目前最好的內(nèi)部排序方法是（）排序法。A冒泡排序B希爾排序C插入排序D快速排序19有一組數(shù)據(jù) 15， 9，7，8， 20， -1 ， 7， 4，用堆排序的篩選方法建立的初始堆為（ ）。A-1 ，4，5，9， 20，7，15，7B-1 ，7，15，7，4，8，20，9C-1 ，4，7，8， 20，15，7，9DA， B， C都不對20下面說法不正確的是（）。A關(guān)鍵活動不按期完成就會影響整個工程的完成時間B任何一個關(guān)鍵活動提前完成，將使整個工程提前完成C所有關(guān)鍵活動都提前完成，則整個工程提前完成D某些關(guān)鍵活動若提前完成，將使整個工程提

17、前完成21下列選項中，（）不是操作系統(tǒng)關(guān)心的主要問題。A管理計算機(jī)裸機(jī)B設(shè)計、提供用戶程序與計算機(jī)硬件系統(tǒng)的界面C管理計算機(jī)系統(tǒng)資源D高級程序設(shè)計語言的編譯器22系統(tǒng)功能調(diào)用是（）。A用戶編寫的一個子程序B高級語言中的庫程序C操作系統(tǒng)中的一條命令D操作系統(tǒng)向用戶程序提供的接口23在處理機(jī)管理中，當(dāng)（）時，進(jìn)程從阻塞狀態(tài)變?yōu)榫途w狀態(tài)。A進(jìn)程被調(diào)度程序選中B等待某一事件發(fā)生C等待的事件發(fā)生D時間片用完24高級調(diào)度是（）。A進(jìn)程調(diào)度B作業(yè)調(diào)度C程序調(diào)度D設(shè)備調(diào)度25臨界區(qū)是（）。A一個緩沖區(qū)B一段共享數(shù)據(jù)區(qū)C一段程序D一個互斥資源26產(chǎn)生死鎖的根本原因是（）。A資源共享B并發(fā)執(zhí)行的進(jìn)程太多C進(jìn)程推進(jìn)

18、順序非法D以上 3 個因素全是27在下述存儲管理方案中，（）管理方式要求作業(yè)占用連續(xù)的存儲空間。A分區(qū)B分頁C分段D段頁式28操作系統(tǒng)中對數(shù)據(jù)進(jìn)行管理的部分叫做（）。A數(shù)據(jù)庫系統(tǒng)B文件系統(tǒng)C檢索系統(tǒng)D數(shù)據(jù)存儲系統(tǒng)29下列文件中屬于邏輯結(jié)構(gòu)的文件是（）。A連續(xù)文件B系統(tǒng)文件C散列文件D流式文件30在磁盤文件系統(tǒng)中，對于下列文件物理結(jié)構(gòu)，（）不具有直接讀寫文件任意一個記錄的能力。A順序結(jié)構(gòu)B鏈接結(jié)構(gòu)C索引結(jié)構(gòu)D散列結(jié)構(gòu)二、算法設(shè)計題 （共 2 題，每題 10 分，合計 20 分）31設(shè) C=a1,b1,a2,b2,an,bn 為一線性表，采用帶頭結(jié)點(diǎn)的hc法，將其拆分為兩個線性表，使得：A= a1

19、,a2, , an,B= b1, b2, bn單鏈表存放，設(shè)計一個就地算32冒泡排序的算法是把大的元素向上移動（氣泡的上升）也可以把最小的元素向下移動（氣泡的下沉）。請給出上浮和下沉過程交替的冒泡排序算法。三、綜合應(yīng)用題（共6 題，合計 70 分）33寫出用 Prim 算法構(gòu)造圖2 最小生成樹的過程。（10 分）圖 2無向網(wǎng)34關(guān)鍵字序列 A=(36,27,68,33,97,40,81,24,23,90,32,14)共 12 個數(shù)據(jù)，哈希表長為13，采用的哈希函數(shù)為： h(key)=key %13 。如果采用開放定址的線性探測再散列方法解決沖突，請構(gòu)造哈希表并求其查找成功時的平均查找長度。（1

20、0 分）35在如圖 3 所示的 AOE網(wǎng)，求：（ 10 分）（ 1）完成此工程最少需要的多少天（設(shè)邊上權(quán)值為天數(shù)）。（ 2）是否存在某項活動，當(dāng)其提高速度后能使整個工程縮短工期。a3=3圖 3AOE 網(wǎng)a7=436若有以下四個作業(yè)同時到達(dá)系統(tǒng)并立即進(jìn)入調(diào)度：612 =4作業(yè)名24所需 CPU時間（分鐘）a作業(yè) 19 a1=5作業(yè) 24a4=6a=37a10=51016a8=1a2 =69a13=2355a9=48 a11=2a =3作業(yè)310作業(yè)48假設(shè)系統(tǒng)中沒有其他作業(yè)，現(xiàn)對它們實(shí)施SJF 調(diào)度算法。給出作業(yè)調(diào)度順序并求出平均作業(yè)周轉(zhuǎn)時間T ，平均帶權(quán)作業(yè)周轉(zhuǎn)時間W 。（ 15 分）37在一

21、個請求式頁式管理系統(tǒng)中，某程序在內(nèi)存中分配三個頁面，初始為空 . 頁面走向為 :4 ，3，2，1，4，3， 5， 4， 3，2， 1， 5。用學(xué)過的頁面值換算法FIFO 算出缺頁次數(shù)。給出執(zhí)行過程中內(nèi)存頁面的變化情況。（ 15 分）38在 4*100m 接力賽中， 4 個運(yùn)動員之間存在如下關(guān)系圖4，運(yùn)動員 1 跑到終點(diǎn)把接力棒交給運(yùn)動員 2，運(yùn)動員 4 接到棒后跑完全程。試用信號量機(jī)制進(jìn)行描述。試寫出這四個并發(fā)進(jìn)程能正確執(zhí)行的程序。（ 10 分）開始圖 4 進(jìn)程關(guān)系圖P1P2P3P4結(jié)束第二部分全國碩士研究生入學(xué)統(tǒng)一考試408 計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合歷年真題及詳解2012 年全國碩士研究生入學(xué)

22、統(tǒng)一考試408 計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合真題一、單項選擇題：l 40 小題。每小題2 分，共 80 分。下列每題給出的四個選項中，只有一個選項是最符合題目要求的。1求整數(shù) n（n0）階乘的算法如下，其時間復(fù)雜度是（）。AO（ log 2n）B0（ n）CO（ nlog 2n）DO（ n2）2已知操作符包括 +、 - 、 * 、（和）。將中綴表達(dá)式 a+b-a* （ c+d） e-f ）+g 轉(zhuǎn)換為等價的后綴表達(dá)式 ab+acd+ef-*-g+ 時，用棧來存放暫時還不能確定運(yùn)算次序的操作符。若棧初始時為空，則轉(zhuǎn)換過程中同時保存在棧中的操作符的最大個數(shù)是（）。A5B7C8D113若一棵二叉樹的前序遍

23、歷序列為a，e， b， d， c，后序遍歷序列為b， c， d， e，a，則根結(jié)點(diǎn)的孩子結(jié)點(diǎn)（）。A只有 eB有C有e、 be、 cD無法確定4若平衡二叉樹的高度為6，且所有非葉結(jié)點(diǎn)的平衡因子均為1，則該平衡二叉樹的結(jié)點(diǎn)總數(shù)為（）。A12B20C32D335對有 2 個頂點(diǎn)A0（ n）B0（ e）e 條邊且使用鄰接表存儲的有向圖進(jìn)行廣度優(yōu)先遍歷，其算法時間復(fù)雜度是 （）。CO（ n+e）DO（ne）6若用鄰接矩陣存儲有向圖，矩陣中主對角線以下的元素均為零，則關(guān)于該圖拓?fù)湫蛄械慕Y(jié)論是（）。A存在，且唯一B存在，且不唯一不唯一C存在，可能不唯一D無法確定是否存在7有向帶權(quán)圖如題7 圖所示，若采用迪

24、杰斯特拉（Dijkstra）算法求從源點(diǎn)路徑，則得到的第一條最短路徑的目標(biāo)頂點(diǎn)是b，第二條最短路徑的目標(biāo)頂點(diǎn)是短路徑的目標(biāo)頂點(diǎn)依次是（）。a 到其他各頂點(diǎn)的最短c，后續(xù)得到的其余各最題 7 圖有向帶權(quán)圖Ad, e, fBe， d， fCf ， d， eDf ， e， d8下列關(guān)于最小生成樹的敘述中，正確的是（）。最小生成樹的代價唯一所有權(quán)值最小的邊一定會出現(xiàn)在所有的最小生成樹中使用普里姆（ Prim ）算法從不同頂點(diǎn)開始得到的最小生成樹一定相同使用普里姆算法和克魯斯卡爾（ Kruskal ）算法得到的最小生成樹總不相同A僅B僅C僅、D僅、9設(shè)有一棵3 階 B樹，如題9 圖所示。刪除關(guān)鍵字78

25、得到一棵新B 樹，其最右葉結(jié)點(diǎn)所含的關(guān)鍵字是（）。題9圖3二叉樹圖A60B60，62C62，65D6510排序過程中，對尚未確定最終位置的所有元素進(jìn)行一遍處理稱為一趟排序。下列排序方法中，每一趟排序結(jié)束時都至少能夠確定一個元素最終位置的方法是（）。簡單選擇排序 希爾排序 快速排序 堆排 V二路歸并排序A僅、B僅、C僅、D僅、11對同一待排序列分別進(jìn)行折半插入排序和直接插入排序，兩者之間可能的不同之處是（）。A排序的總趟數(shù)B元素的移動次數(shù)C使用輔助空間的數(shù)量D元素之間的比較次數(shù)12假定基準(zhǔn)程序A 在某計算機(jī)上的運(yùn)行時間為若 CPU速度提高 50， I/O 速度不變，則運(yùn)行基準(zhǔn)程序A55 秒B60

26、 秒C65 秒D70 秒l00 秒，其中 90 秒為 CPU時間，其余為I/O 時間。A 所耗費(fèi)的時間是（）。13假定編譯器規(guī)定 int 和 short 類型長度分別為32 位和 16 位，執(zhí)行下列 C語言語句：unsigned shortX65530； unsigned int yX：得到 y 的機(jī)器數(shù)為（）。A00007FFAHB0000FFFAHCFFFF7FFAHDFFFFFFFAH14 float 類型（即 IEEE754 單精度浮點(diǎn)數(shù)格式）能表示的最大正整數(shù)是（）。A2126-2 103B2127-2 104C2127-2 103D2128-2 104別為15某計算機(jī)存儲器按字節(jié)編

27、址，采用小端方式存放數(shù)據(jù)。假定編譯器規(guī)定32 位和 16 位，并且數(shù)據(jù)按邊界對齊存儲。某C語言程序段如下：若 record 變量的首地址為0 xC008，則地址 0 xC008 中內(nèi)容及 record.cA0 x00、 0 xC00DB0 x00、 0 xCOOEC0 x11、 0 xC00DD0 x11、 0 xC00E16下列關(guān)于閃存（FlashMemory）的敘述中，錯誤的是（）。int和 short的地址分別為（型長度分）。A信息可讀可寫，并且讀、寫速度一樣快B存儲元由 MOS管組成，是一種半導(dǎo)體存儲器C掉電后信息不丟失，是一種非易失性存儲器D采用隨機(jī)訪問方式，可替代計算機(jī)外部存儲器1

28、7假設(shè)某計算機(jī)按字編址，Cache 有 4 個行， Cache 和主存之間交換的塊大小為的內(nèi)容初始為空，采用2 路組相聯(lián)映射方式和LRU替換算法，當(dāng)訪問的主存地址依次為6，8，6， 4， 8 時，命中 Cache 的次數(shù)是（）。A1l 個字。若 Cache 0，4，8，2，0，B2C3D418某計算機(jī)的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接編碼法，共有33 個微命令，構(gòu)成5 個互斥類，分別包含7、3、12、 5 和 6 個微命令，則操作控制字段至少有（）。A5 位B6 位C15 位D33 位19某同步總線的時鐘頻率為l00MHz，寬度為 32 位，地址數(shù)據(jù)線復(fù)用，每傳輸一

29、個地址或數(shù)據(jù)占用一個時鐘周期。若該總線支持突發(fā)（猝發(fā)）傳輸方式，則一次“主存寫”總線事務(wù)傳輸l28 位數(shù)據(jù)所需要的時間至少是（）。）。A20nsB40nsC50nsD80ns20下列關(guān)于USB總線特性的描述中，錯誤的是（）。A可實(shí)現(xiàn)外設(shè)的即插即用和熱插拔B可通過級聯(lián)方式連接多臺外設(shè)C是一種通信總線，可連接不同外設(shè)D同時可傳輸2 位數(shù)據(jù)，數(shù)據(jù)傳輸率高21下列選項中，在I O總線的數(shù)據(jù)線上傳輸?shù)男畔ǎǎ?I O接口中的命令字 I 0 接口中的狀態(tài)字中斷類型號A僅、B僅、C僅、D、22響應(yīng)外部中斷的過程中，中斷隱指令完成的操作，除保護(hù)斷點(diǎn)外，還包括（）。開關(guān)中斷 保存通用寄存器的內(nèi)容 形成中斷

30、服務(wù)程序入口地址并送 PC A僅、B僅、C僅、D、23下列選項中，不可能在用戶態(tài)發(fā)生的事件是（）。A系統(tǒng)調(diào)用B外部中斷C進(jìn)程切換D缺頁24中斷處理和子程序調(diào)用都需要壓棧以保護(hù)現(xiàn)場，中斷處理一定會保存而子程序調(diào)用不需要保存其內(nèi)容的是（）。A程序計數(shù)器B程序狀態(tài)字寄存器C通用數(shù)據(jù)寄存器D通用地址寄存器25下列關(guān)于虛擬存儲的敘述中，正確的是（ ）。A虛擬存儲只能基于連續(xù)分配技術(shù)B虛擬存儲只能基于非連續(xù)分配技術(shù)C虛擬存儲容量只受外存容量的限制D虛擬存儲容量只受內(nèi)存容量的限制26操作系統(tǒng)的I O子系統(tǒng)通常由四個層次組成，每一層明確定義了與鄰近層次的接口。其合理的層次組織排列順序是（）。A用戶級 I O軟

31、件、設(shè)備無關(guān)軟件、設(shè)備驅(qū)動程序、中斷處理程序B用戶級 I O軟件、設(shè)備無關(guān)軟件、中斷處理程序、設(shè)備驅(qū)動程序C用戶級 I O軟件、設(shè)備驅(qū)動程序、設(shè)備無關(guān)軟件、中斷處理程序D用戶級 I O軟件、中斷處理程序、設(shè)備無關(guān)軟件、設(shè)備驅(qū)動程序27假設(shè) 5 個進(jìn)程 P0、Pl 、P2、P3、P4 共享三類資源 Rl 、R2、R3，這些資源總數(shù)分別為l8 、6、22。T0 時刻的資源分配情況如題27 表所示，此時存在的一個安全序列是（）。題 27 表資源分配情況表已分配資源資源最大需求進(jìn)程R1R2R3R1R2R3PO3235510P14O3536P24O54O11P32O4425P4314424AP0，P2，

32、 P4，Pl ，P3BPl ，P0， P3，P4，P2CP2，Pl ， P0，P3，P4DP3，P4， P2，Pl ，P0P028若一個用戶進(jìn)程通過read 系統(tǒng)調(diào)用讀取一個磁盤文件中的數(shù)據(jù)，則下列關(guān)于此過程的敘述中，正確的是（）。若該文件的數(shù)據(jù)不在內(nèi)存，則該進(jìn)程進(jìn)入睡眠等待狀態(tài)；請求用戶態(tài)切換到核心態(tài)； read 系統(tǒng)調(diào)用的參數(shù)應(yīng)包含文件的名稱read系統(tǒng)調(diào)用會導(dǎo)致CPU從A僅、B僅、C僅、D、和29一個多道批處理系統(tǒng)中僅有Pl 和 P2 兩個作業(yè)， P2 比Pl 晚 5ms到達(dá)。它們的計算和I0操作順序如下： P1：計算 60ms，I O 80ms，計算 20ms； P2：計算考慮調(diào)度和切

33、換時間，則完成兩個作業(yè)需要的時間最少是（120ms，I O40ms，計算）。40ms若不A240msB260msC340msD360ms30若某單處理器多進(jìn)程系統(tǒng)中有多個就緒態(tài)進(jìn)程，則下列關(guān)于處理機(jī)調(diào)度的敘述中，錯誤的是（）。A在進(jìn)程結(jié)束時能進(jìn)行處理機(jī)調(diào)度B創(chuàng)建新進(jìn)程后能進(jìn)行處理機(jī)調(diào)度C在進(jìn)程處于臨界區(qū)時不能進(jìn)行處理機(jī)調(diào)度D在系統(tǒng)調(diào)用完成并返回用戶態(tài)時能進(jìn)行處理機(jī)調(diào)度31下列關(guān)于進(jìn)程和線程的敘述中，正確的是（ ）。A不管系統(tǒng)是否支持線程，進(jìn)程都是資源分配的基本單位B線程是資源分配的基本單位，進(jìn)程是調(diào)度的基本單位C系統(tǒng)級線程和用戶級線程的切換都需要內(nèi)核的支持D同一進(jìn)程中的各個線程擁有各自不同的地

34、址空間32下列選項中，不能改善磁盤設(shè)備I O性能的是（A重排 I 0 請求次序）。B在一個磁盤上設(shè)置多個分區(qū)C預(yù)讀和滯后寫D優(yōu)化文件物理塊的分布33在 TCPIP 體系結(jié)構(gòu)中，直接為ICMP提供服務(wù)的協(xié)議是（）。APPPBIPCUDPDTCP34在物理層接口特性中，用于描述完成每種功能的事件發(fā)生順序的是（）。A機(jī)械特性B功能特性C過程特性D電氣特性35以太網(wǎng)的MAC協(xié)議提供的是（）。A無連接不可靠服務(wù)B無連接可靠服務(wù)C有連接不可靠服務(wù)D有連接可靠服務(wù)36兩臺主機(jī)之間的數(shù)據(jù)鏈路層采用后退N 幀協(xié)議（ GBN）傳輸數(shù)據(jù)，數(shù)據(jù)傳輸速率為l6kbps，單向傳播時延為270ms，數(shù)據(jù)幀長度范圍是1285

35、12 字節(jié)，接收方總是以與數(shù)據(jù)幀等長的幀進(jìn)行確認(rèn)。為使信道利用率達(dá)到最高，幀序號的比特數(shù)至少為（）。A5B4C3D23737下列關(guān)于IP路由器功能的描述中，正確的是（）。運(yùn)行路由協(xié)議，設(shè)置路由表；監(jiān)測到擁塞時，合理丟棄進(jìn)行差錯校驗，確保傳輸?shù)腎P 分組不丟失；根據(jù)收到的IP輸出線路上。A僅、IP 分組；對收到的 IP 分組頭分組的目的 IP 地址，將其轉(zhuǎn)發(fā)到合適的B僅、C僅、D、38 ARP協(xié)議的功能是（）。A根據(jù) IP 地址查詢 MAC地址B根據(jù) MAC地址查詢 IP 地址C根據(jù)域名查詢IP 地址D根據(jù) IP 地址查詢域名39某主機(jī)的IP 地址為，子網(wǎng)掩碼為。若該主機(jī)向其所在子網(wǎng)發(fā)送廣播分組

36、，則目的地址可以是（A）。BCD40若用戶 l 與用戶 2 之間發(fā)送和接收電子郵件的過程如題40 圖所示，則圖中、階段分別使用的應(yīng)用層協(xié)議可以是（）。題 40 圖電子郵件發(fā)送接收示意圖ASMTP、 SMTP、SMTPBPOP3、 SMTP、POP3CPOP3、 SMTP、SMTPDSMTP、 SMTP、POP3二、綜合應(yīng)用題：41-47小題。共 70 分。41（ 10 分）設(shè)有 6 個有序表 A、B、 C、 D、E、F，分別含有10、 35、40、 50、 60 和 200 個數(shù)據(jù)元素，各表中元素按升序排列。要求通過 5 次兩兩合并，將 6 個表最終合并成 1 個升序表，并在最壞情況下比較的總

37、次數(shù)達(dá)到最小。請回答下列問題。1）給出完整的合并過程，并求出最壞情況下比較的總次數(shù)。2）根據(jù)你的合并過程，描述 n（n2）個不等長升序表的合并策略，并說明理由。42（ 13 分）假定采用帶頭結(jié)點(diǎn)的單鏈表保存單詞，當(dāng)兩個單詞有相同的后綴時，則可共享相同的后綴存儲空間。例如，“ loading ”和“ being ”的存儲映像如題42 圖所示。題 42 圖存儲映像示意圖設(shè) strl和 str2分別指向兩個單詞所在單鏈表的頭結(jié)點(diǎn)，鏈表結(jié)點(diǎn)結(jié)構(gòu)為data ，next ，請設(shè)計一個時間上盡可能高效的算法，找出由strl和 str2所指的兩個鏈表共同后綴的起始位置（如圖中字符i所在結(jié)點(diǎn)的位置p）。要求：1

38、）給出算法的基本設(shè)計思想。2）根據(jù)設(shè)計思想，采用 C或 C+或 JAVA語言描述算法，關(guān)鍵之處給出注釋。3）說明你所設(shè)計算法的時間復(fù)雜度。43（ 11 分）假定某計算機(jī)的 CPU主頻為 80MHz，CPI 為 4，并且平均每條指令訪存 1.5 次，主存與 Cache 之間交換的塊大小為 168， Cache 的命中率為 99，存儲器總線寬度為 32 位。請回答下列問題。1）該計算機(jī)的 MIPS 數(shù)是多少 ?平均每秒 Cache 缺失的次數(shù)是多少 ?在不考慮 DMA傳送的情況下，主存帶寬至少達(dá)到多少才能滿足 CPU的訪存要求 ?（ 2）假定在 Cache 缺失的情況下訪問主存時，存在 0.000

39、5 的缺頁率， 則 CPU平均每秒產(chǎn)生多少次缺頁異常 ?若頁面大小為4KB，每次缺頁都需要訪問磁盤，訪問磁盤時DMA傳送采用周期挪用方式，磁盤I O接口的數(shù)據(jù)緩沖寄存器為32 位，則磁盤I O接口平均每秒發(fā)出的DMA請求次數(shù)至少是多少?（ 3） CPU和 DMA控制器同時要求使用存儲器總線時，哪個優(yōu)先級更高?為什么 ?（ 4）為了提高性能，主存采用4 體交叉存儲模式，工作時每l/4個存儲周期啟動一個體。若每個體的存儲周期為50ns，則該主存能提供的最大帶寬是多少?44（ 12 分）某 16 位計算機(jī)中，帶符號整數(shù)用補(bǔ)碼表示，數(shù)據(jù)Cache 和指令 Cache 分離。題 44 表給出了指令系統(tǒng)中

40、部分指令格式，其中Rs 和 Rd表示寄存器， mem表示存儲單元地址，（X）表示寄存器X 或存儲單元X 的內(nèi)容。表指令系統(tǒng)中部分指令格式名稱指令的匯編格式指令功能加法指令A(yù)DD Rs，Rd（ Rs） +（Rd） Rd算術(shù)邏輯左移SHLR d2* （ Rd） Rd算術(shù)右移SHRR d（Rd） 2 Rd取數(shù)指令LOAD RD，mem（mem） Rd存數(shù)指令STORE Rs， mem（Rs） mem該計算機(jī)采用5 段流水方式執(zhí)行指令，各流水段分別是取指（IF ）、譯碼讀寄存器（ID ）、執(zhí)行計算有效地址 （EX）、訪問存儲器 （ M）和結(jié)果寫回寄存器 （ WB），流水線采用“按序發(fā)射，按序完成”方式

41、，沒有采用轉(zhuǎn)發(fā)技術(shù)處理數(shù)據(jù)相關(guān)，并且同一個寄存器的讀和寫操作不能在同一個時鐘周期內(nèi)進(jìn)行。請回答下列問題。1）若 int 型變量 x 的值為 -513 ，存放在寄存器 Rl 中，則執(zhí)行指令“ SHR Rl ”后， Rl 的內(nèi)容是多少 ?（用十六進(jìn)制表示）2）若某個時間段中，有連續(xù)的 4 條指令進(jìn)入流水線，在其執(zhí)行過程中沒有發(fā)生任何阻塞，則執(zhí)行這 4 條指令所需的時鐘周期數(shù)為多少 ?3）若高級語言程序中某賦值語句為x a+b，x、 a 和 b 均為 int 型變量，它們的存儲單元地址分別表示為 x 、a 和 b 。該語句對應(yīng)的指令序列及其在指令流水線中的執(zhí)行過程如題44 圖所示。則這 4條指令執(zhí)行

42、過程中，I 3 的 ID 段和 I 4 的 IF 段被阻塞的原因各是什么?（ 4）若高級語言程序中某賦值語句為x 2*x+a ， x 和 a 均為 unsigned int類型變量，它們的存儲單元地址分別表示為x 、a ，則執(zhí)行這條語句至少需要多少個時鐘周期?要求模仿題44 圖畫出這條語句對應(yīng)的指令序列及其在流水線中的執(zhí)行過程示意圖。45（7 分）某請求分頁系統(tǒng)的局部頁面置換策略如下：系統(tǒng)從0 時刻開始掃描，每隔5 個時間單位掃描一輪駐留集（掃描時間忽略不計），本輪沒有被訪問過的頁框?qū)⒈幌到y(tǒng)回收，并放入到空閑頁框鏈尾，其中內(nèi)容在下一次被分配之前不被清空。當(dāng)發(fā)生缺頁時，如果該頁曾被使用過且還在空

43、閑頁框鏈表中，則重新放回進(jìn)程的駐留集中；否則，從空閑頁框鏈表頭部取出一個頁框。假設(shè)不考慮其他進(jìn)程的影響和系統(tǒng)開銷，初始時進(jìn)程駐留集為空。目前系統(tǒng)空閑頁框鏈表中頁框號依次為 32、15、21、41。進(jìn)程 P 依次訪問的 是： 、。請回答下列問題。1）訪問 時，對應(yīng)的頁框號是什么 ?2）訪問 時，對應(yīng)的頁框號是什么 ?說明理由。3）訪問 時，對應(yīng)的頁框號是什么 ?說明理由。4）該策略是否適合于時間局部性好的程序?說明理由。46（ 8 分）某文件系統(tǒng)空間的最大容量為4TB（ 1T 240），以磁盤塊為基本分配單位，磁盤塊大小為 lKB 。文件控制塊（ FCB）包含一個 512B 的索引表區(qū)。請回答下

44、列問題。1）假設(shè)索引表區(qū)僅采用直接索引結(jié)構(gòu)，索引表區(qū)存放文件占用的磁盤塊號。索引表項中塊號最少占多少字節(jié) ?可支持的單個文件最大長度是多少字節(jié) ?（ 2）假設(shè)索引表區(qū)采用如下結(jié)構(gòu)：第0 7 字節(jié)采用 格式表示文件創(chuàng)建時預(yù)分配的連續(xù)存儲空間，其中起始塊號占6B，塊數(shù)占2B；剩余 504 字節(jié)采用直接索引結(jié)構(gòu)，一個索引項占6B，則可支持的單個文件最大長度是多少字節(jié)?為了使單個文件的長度達(dá)到最大， 請指出起始塊號和塊數(shù)分別所占字節(jié)數(shù)的合理值并說明理由。47（ 9 分）主機(jī) H通過快速以太網(wǎng)連接Internet， IP 地址為 ，服務(wù)器 S 的 IP 地址為0 。H與 S 使用 TCP通信時，在 H

45、上捕獲的其中5 個 IP 分組如題 47-a 表所示。題 47-a 表編號IP 分組的前40 字節(jié)內(nèi)容（十六進(jìn)制）1019b40008006lde8coa80008d34447500bd91388846b41c5000000005db0000020000400031066e833d3444750cOa8000813880bd9 e0599fef 846b41c6 6701216d0 37e10000019c40008006ldefcOa80008d3444750 bd913888346b41c6e0599ff0501043802b320000019d400080061ddecOa80008d3

46、444750 0bd913884846b4lc6e0599ff0c655000053106067ad3444750cOa80008e0599ff0846b41d6501016d057d2000013880bd9請回答下列問題。（ 1）題 47-a 表中的 IP 分組中，哪幾個是由H發(fā)送的 ?哪幾個完成了 TCP連接建立過程 ?哪幾個在通過快速以太網(wǎng)傳輸時進(jìn)行了填充?（ 2）根據(jù)題 47-a 表中的 IP 分組，分析S 已經(jīng)收到的應(yīng)用層數(shù)據(jù)字節(jié)數(shù)是多少?（ 3）若題 47-a 表中的某個IP 分組在 S 發(fā)出時的前40 字節(jié)如題 47-b 表所列，則該IP時經(jīng)過了多少個路由器?分組到達(dá) H題 4

47、7-b 表注： IP來自 S 發(fā)出的分4006eCad d3444750 ca760106組1388a108 e0599ff0 846b41d6 501016dO b7d60000分組頭和 TCP段頭結(jié)構(gòu)分別如題47-a 圖、題 47-b 圖所示：版本頭部長度 服務(wù)類型（8-15 ）總長度（ 16-31 ）標(biāo)識標(biāo)志片偏移生存時（ TTL）協(xié)議頭部校驗和源IP地址目的 IP 地址題 47-a 圖 IP 分組頭結(jié)構(gòu)源端口（ 0-15 ）目的端口（ 16-31 ）序號（ seq）確認(rèn)號（ ack ）數(shù)據(jù)偏移保留UAPRSFRCSSYIGKHTNN窗口校驗和選項（長度可變）題 47-b 圖 TCP段頭

48、結(jié)構(gòu)緊急指針填充2012 年全國碩士研究生入學(xué)統(tǒng)一考試408 計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合真題及詳解一、單項選擇題：l 40 小題。每小題2 分，共 80 分。下列每題給出的四個選項中，只有一個選項是最符合題目要求的。1求整數(shù) n（n0）階乘的算法如下，其時間復(fù)雜度是（）。AO（ log 2n）B0（ n）CO（ nlog 2n）DO（ n2）【答案】 B?！窘馕觥?設(shè) fact （ n）的運(yùn)行時間函數(shù)是T（n）。該函數(shù)中語句的運(yùn)行時間是 0（ 1），語句的運(yùn)行時間是 T（ n-1 ） +O（ 1），其中 O（ 1）為乘法運(yùn)算的時間。因此，當(dāng) n1時， T（n） -0 （ 1）；當(dāng) n1 時， T（

49、n） T（n-1 ）+O（1）。則， T（ n） O（1）+Tn-1 ）2 O（ 1） +T（n-2 ）（ n-1 ） O（1） +T（ 1） n O（ 1）O（ n）即 fact （ n）的時間復(fù)雜度為O（ n）。2已知操作符包括 +、 - 、 * 、（和）。將中綴表達(dá)式 a+b-a* （ c+d） e-f ）+g 轉(zhuǎn)換為等價的后綴表達(dá)式 ab+acd+ef-*-g+ 時，用棧來存放暫時還不能確定運(yùn)算次序的操作符。若棧初始時為空，則轉(zhuǎn)換過程中同時保存在棧中的操作符的最大個數(shù)是（）。A5B7C8D11【答案】 A。【解析】 基本思想是：采用運(yùn)算符棧是為了比較運(yùn)算符的優(yōu)先級，所有運(yùn)算符必須進(jìn)棧。

50、只將大于棧頂元素優(yōu)先級的運(yùn)算符直接進(jìn)棧，否則需要退棧棧頂運(yùn)算符（先出棧的運(yùn)算符先計算，同優(yōu)先級的運(yùn)算符在棧中的先計算）。表達(dá)式a+b-a* （ c+d） e-f ）+g 產(chǎn)生后綴表達(dá)式的過程如下表所列：當(dāng)前字符運(yùn)算符棧內(nèi)容后綴表達(dá)式說明a+“+”進(jìn)棧b+ab-ab+“ - ”與棧頂元素“ +”的優(yōu)先級相同，則“ +”出棧，“ - ”進(jìn)棧a-ab+a*-*ab+a“ * ”的優(yōu)先級大于棧頂元素“ - ”，則“* ”進(jìn)棧（-* （ab+a“（”對它之前后的運(yùn)算符起隔離作用（-* （ab+a“（”對它之前后的運(yùn)算符起隔離作用-* （ab+ac+-*（+ab+ac“+”進(jìn)棧d-*（+ab+acd）-*

51、 （ab+acd+與其配對的左括號及其前所有運(yùn)算符出棧-* （ab+acd+“”進(jìn)棧e-* （ab+acd+e-* （-ab+acd+e“- ”的優(yōu)先級小于棧頂元素“”，則“”出棧，“ - ”進(jìn)棧f-* （-ab+acd+ef）-*ab+acd+ef-與其配對的左括號及其前所有運(yùn)算符出棧+-ab+acd+ef-*“ +”的優(yōu)先級小于棧頂元素“ * ”，則“*”出棧+ab+acd+e f-*-“ +”與棧頂元素“ - ”的優(yōu)先級相同，則“ - ”出棧，“ +”進(jìn)棧g+ab+acd+e f-*-gab+acd+e全部出棧f-*-g+通過上表可以看出，顯然轉(zhuǎn)換過程中同時保存在棧中的操作符的最大個數(shù)是

52、5。3若一棵二叉樹的前序遍歷序列為a，e， b， d， c，后序遍歷序列為b， c， d， e，a，則根結(jié)點(diǎn)的孩子結(jié)點(diǎn)（）。A只有 eB有 e、 bC有 e、 cD無法確定【答案】 A?！窘馕觥?由題目可知，若一棵二叉樹的前序遍歷序列為a，e，b， d， c，后序遍歷序列為b， c， d，e，a，其中 a 為這棵二叉樹的根結(jié)點(diǎn)，接下來，在前序遍歷的第二個結(jié)點(diǎn)為e，而后序遍歷的倒數(shù)第二個結(jié)點(diǎn)為 e，說明 a 的孩子結(jié)點(diǎn)只有 e。4若平衡二叉樹的高度為 6，且所有非葉結(jié)點(diǎn)的平衡因子均為1，則該平衡二叉樹的結(jié)點(diǎn)總數(shù)為（）。A12B20C32D33【答案】 B?！窘馕觥?本題題目的實(shí)際問題是，具有6

53、層結(jié)點(diǎn)的平衡二叉樹含有最少的結(jié)點(diǎn)數(shù)是多少。N h 表示深度為 h 的平衡二叉樹中含有的最少結(jié)點(diǎn)數(shù)，有N00，N11， N2 2 Nh Nh-1+Nh-2 +1由此可得 N 20。對應(yīng)的平衡二叉樹如下圖所示。55對有 2 個頂點(diǎn) e 條邊且使用鄰接表存儲的有向圖進(jìn)行廣度優(yōu)先遍歷，其算法時間復(fù)雜度是 （）。A0（ n）B0（ e）CO（ n+e）DO（ne）【答案】 C?！窘馕觥?遍歷圖的過程實(shí)質(zhì)上是對每個頂點(diǎn)查找其鄰接點(diǎn)的過程。其耗費(fèi)的時間則取決于所采用的存儲結(jié)構(gòu)。當(dāng)用二維數(shù)組表示鄰接矩陣圖的存儲結(jié)構(gòu)時，查找每個頂點(diǎn)的鄰接點(diǎn)所需時間為O（ n2），其中 n 為圖中頂點(diǎn)數(shù)。而當(dāng)以鄰接表作圖的存儲結(jié)

54、構(gòu)時，找鄰接點(diǎn)所需時間為0（e），其中 e 為無向圖中邊的數(shù)或有向圖中弧的數(shù)。由此，當(dāng)以鄰接表作存儲結(jié)構(gòu)時， 深度優(yōu)先搜索遍歷圖的時間復(fù)雜度為O（n+e）。即可得出正確答案。6若用鄰接矩陣存儲有向圖，矩陣中主對角線以下的元素均為零，則關(guān)于該圖拓?fù)湫蛄械慕Y(jié)論是（）。A存在，且唯一B存在，且不唯一不唯一C存在，可能不唯一D無法確定是否存在【答案】 C。【解析】 圖的基本應(yīng)用拓?fù)渑判?，用鄰接矩陣存儲有向圖，矩陣中主對角線以下的元素均為零，說明該圖為有向無環(huán)圖，所以其拓?fù)湫蛄写嬖?，但不一定唯一，如圖的鄰接矩陣為，則存在兩個拓?fù)湫蛄小?有向帶權(quán)圖如題7 圖所示，若采用迪杰斯特拉（Dijkstra）算法求

55、從源點(diǎn)路徑，則得到的第一條最短路徑的目標(biāo)頂點(diǎn)是b，第二條最短路徑的目標(biāo)頂點(diǎn)是短路徑的目標(biāo)頂點(diǎn)依次是（）。a 到其他各頂點(diǎn)的最短c，后續(xù)得到的其余各最題 7 圖有向帶權(quán)圖Ad, e, fBe， d， fCf ， d， eDf ， e， d【答案】 C?！窘馕觥?本題主要考查Dijkstra算法的思想和解題步驟。題目執(zhí)行算法過程中各步的狀態(tài)如下表所示。執(zhí)行 Dijkstra算法過程中各步的狀態(tài)表，故后續(xù)目標(biāo)頂點(diǎn)依次為f,d,e。頂點(diǎn)bcdef集合 S趟數(shù)k 125（ a，b）（ a，b） （a，c）k 2（a， b， c）（ a，b，d）a ，b， c4（ a，b，c，k 3（ a，b，d） （

56、a， b，c， e） a ， b， c，f f ）k 4（ a，b，d）（ a， b，c， e）a ，b，c， f ， d）k 5（ a， b，d， e）a, b ，c， f ， d，e8下列關(guān)于最小生成樹的敘述中，正確的是（）。最小生成樹的代價唯一所有權(quán)值最小的邊一定會出現(xiàn)在所有的最小生成樹中使用普里姆（ Prim ）算法從不同頂點(diǎn)開始得到的最小生成樹一定相同使用普里姆算法和克魯斯卡爾（ Kruskal ）算法得到的最小生成樹總不相同A僅B僅C僅、D僅、【答案】 A。【解析】 當(dāng)圖中存在相同權(quán)值的邊時，其最小生成樹可能是不唯一的，但最小生成樹的代價一定是相同的，所以說法正確。從n 個頂點(diǎn)的連

57、通圖中選取n-1 條權(quán)值最小的邊可能構(gòu)成回路，所以說法錯誤。當(dāng)某個頂點(diǎn)有權(quán)值相同的邊，使用普里姆（Prim ）算法從不同頂點(diǎn)開始得到的最小生成樹并不一定相同，所以說法錯誤。當(dāng)最小生成樹不唯一時，使用普里姆算法和克魯斯卡爾（Kruskal ）算法得到的最小生成樹可能相同，也可能不同，所以說法錯誤。由此可得出正確答案。9設(shè)有一棵 3 階 B 樹，如題 9 圖所示。刪除關(guān)鍵字78 得到一棵新 B 樹，其最右葉結(jié)點(diǎn)所含的關(guān)鍵字是（）。題9圖3二叉樹圖A60B60，62C62，65D65【答案】 D?！窘馕觥?本題主要考查B 樹刪除操作。即被刪關(guān)鍵字所在的結(jié)點(diǎn)中的關(guān)鍵字個數(shù)等于m/2 -1 ，而與該結(jié)點(diǎn)

58、相鄰的右兄弟（或左兄弟）結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目大于m/2-1 ，則需將其兄弟結(jié)點(diǎn)中最小（或最大）的關(guān)鍵字上移至雙親結(jié)點(diǎn)中，而將雙親結(jié)點(diǎn)中小于（或大于）且緊靠該上移關(guān)鍵字的關(guān)鍵字下移至被刪關(guān)鍵字所在結(jié)點(diǎn)中。題目中刪除關(guān)鍵字78 得到一棵新 B 樹如下，其最右葉結(jié)點(diǎn)所含的關(guān)鍵字是65。10排序過程中，對尚未確定最終位置的所有元素進(jìn)行一遍處理稱為一趟排序。下列排序方法中，每一趟排序結(jié)束時都至少能夠確定一個元素最終位置的方法是（）。簡單選擇排序希爾排序快速排序堆排V二路歸并排序A僅、B僅、C僅、D僅、【答案】 A?！窘馕觥?其中簡單選擇排序、堆排序?qū)儆谶x擇類排序，每一趟排序結(jié)束時將確定最大（或最?。╆P(guān)鍵字

59、所在的位置?？焖倥判蛎恳惶伺判蚪Y(jié)束時將確定基準(zhǔn)關(guān)鍵字所在的位置。希爾排序、二路歸并排序每一趟排序結(jié)束時不一定能確定一個元素的最終位置。11對同一待排序列分別進(jìn)行折半插入排序和直接插入排序，兩者之間可能的不同之處是（ ）。A排序的總趟數(shù)B元素的移動次數(shù)C使用輔助空間的數(shù)量D元素之間的比較次數(shù)【答案】 D?！窘馕觥?折半插入排序所需附加存儲空間和直接插入排序相同，從時間上比較，折半插入排序僅減少了關(guān)鍵字間的比較次數(shù)，而記錄的移動次數(shù)不變。折半插入排序的時間復(fù)雜度仍為O（ n2） , 所以兩者之間的不同只可能是元素之間的比較次數(shù)。12假定基準(zhǔn)程序A 在某計算機(jī)上的運(yùn)行時間為l00 秒，其中 90 秒

60、為 CPU時間，其余為I/O 時間。若 CPU速度提高 50， I/O 速度不變，則運(yùn)行基準(zhǔn)程序A 所耗費(fèi)的時間是（）。A55 秒B60 秒C65 秒D70 秒【答案】 D?！窘馕觥?CPU速度提高 50，即 CPU性能提高比為l.5 ，改進(jìn)之后的CPU運(yùn)行時間 901.5 60 秒。I/O 速度不變，仍維持l0 秒，所以運(yùn)行基準(zhǔn)程序A 所耗費(fèi)的時間為70 秒。13假定編譯器規(guī)定X65530； unsigned int yint和 short 類型長度分別為X：得到 y 的機(jī)器數(shù)為（32 位和 16 位，執(zhí)行下列）。C語言語句：unsigned shortA00007FFAHB0000FFFA