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

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

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

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

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

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

6、,1,0D001,000,01,11,107對(duì)所示的無(wú)向圖，從頂點(diǎn)1 開始進(jìn)行深度優(yōu)先遍歷，可得到的頂點(diǎn)訪問(wèn)序列為（）。A1243576B1243567C1245637D12345768對(duì)于下圖，以下（）是其拓?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對(duì)數(shù)據(jù)序列 15,9,7,8,20,-1,4進(jìn)行排序 , 一趟排序后的結(jié)果為9,15,7,8,20,-1,4,采用的是（）。A簡(jiǎn)單選擇排序B起泡排序C直接插入排序D堆排序10對(duì)一組數(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 分，合計(jì) 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采用開放地址法的線性探測(cè)法解決沖突，試在018 的哈希表中對(duì)該關(guān)鍵字序列構(gòu)造哈希表。13已知有 6 個(gè)頂點(diǎn)（頂點(diǎn)編號(hào)為0-5 ）的有向帶權(quán)圖G，其鄰接矩陣A 為上三

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

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

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

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

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

14、，7，9， 13 為權(quán)值構(gòu)造一棵哈夫曼樹，則其帶權(quán)路徑長(zhǎng)為（）。A78B80C81D7911. 一個(gè)有向圖的鄰接表存儲(chǔ)如圖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任意一個(gè)無(wú)向連通圖（）最小生成樹。A只有一棵B一定有多棵C有一棵或多棵4D可能不存在13若一個(gè)有向圖中的頂點(diǎn)不能排成一個(gè)拓?fù)湫蛄?，則可斷定該有向圖（）。A是個(gè)有根有向圖B是個(gè)強(qiáng)連通

15、圖C含有多個(gè)入度為0 的頂點(diǎn)D含有頂點(diǎn)數(shù)目大于1 的強(qiáng)連通分量14順序查找法適合于存儲(chǔ)結(jié)構(gòu)為（）的線性表。A哈希存儲(chǔ)B索引存儲(chǔ)C壓縮存儲(chǔ)D順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)15在含有 27 個(gè)結(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 的元素，所比較過(guò)元素的次數(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都不對(duì)20下面說(shuō)法不正確的是（）。A關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間B任何一個(gè)關(guān)鍵活動(dòng)提前完成，將使整個(gè)工程提前完成C所有關(guān)鍵活動(dòng)都提前完成，則整個(gè)工程提前完成D某些關(guān)鍵活動(dòng)若提前完成，將使整個(gè)工程提

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

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

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

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

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

22、統(tǒng)一考試408 計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合真題一、單項(xiàng)選擇題：l 40 小題。每小題2 分，共 80 分。下列每題給出的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)是最符合題目要求的。1求整數(shù) n（n0）階乘的算法如下，其時(shí)間復(fù)雜度是（）。AO（ log 2n）B0（ n）CO（ nlog 2n）DO（ n2）2已知操作符包括 +、 - 、 * 、（和）。將中綴表達(dá)式 a+b-a* （ c+d） e-f ）+g 轉(zhuǎn)換為等價(jià)的后綴表達(dá)式 ab+acd+ef-*-g+ 時(shí)，用棧來(lái)存放暫時(shí)還不能確定運(yùn)算次序的操作符。若棧初始時(shí)為空，則轉(zhuǎn)換過(guò)程中同時(shí)保存在棧中的操作符的最大個(gè)數(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無(wú)法確定4若平衡二叉樹的高度為6，且所有非葉結(jié)點(diǎn)的平衡因子均為1，則該平衡二叉樹的結(jié)點(diǎn)總數(shù)為（）。A12B20C32D335對(duì)有 2 個(gè)頂點(diǎn)A0（ n）B0（ e）e 條邊且使用鄰接表存儲(chǔ)的有向圖進(jìn)行廣度優(yōu)先遍歷，其算法時(shí)間復(fù)雜度是 （）。CO（ n+e）DO（ne）6若用鄰接矩陣存儲(chǔ)有向圖，矩陣中主對(duì)角線以下的元素均為零，則關(guān)于該圖拓?fù)湫蛄械慕Y(jié)論是（）。A存在，且唯一B存在，且不唯一不唯一C存在，可能不唯一D無(wú)法確定是否存在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)于最小生成樹的敘述中，正確的是（）。最小生成樹的代價(jià)唯一所有權(quán)值最小的邊一定會(huì)出現(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排序過(guò)程中，對(duì)尚未確定最終位置的所有元素進(jìn)行一遍處理稱為一趟排序。下列排序方法中，每一趟排序結(jié)束時(shí)都至少能夠確定一個(gè)元素最終位置的方法是（）。簡(jiǎn)單選擇排序 希爾排序 快速排序 堆排 V二路歸并排序A僅、B僅、C僅、D僅、11對(duì)同一待排序列分別進(jìn)行折半插入排序和直接插入排序，兩者之間可能的不同之處是（）。A排序的總趟數(shù)B元素的移動(dòng)次數(shù)C使用輔助空間的數(shù)量D元素之間的比較次數(shù)12假定基準(zhǔn)程序A 在某計(jì)算機(jī)上的運(yùn)行時(shí)間為若 CPU速度提高 50， I/O 速度不變，則運(yùn)行基準(zhǔn)程序A55 秒B60

26、 秒C65 秒D70 秒l00 秒，其中 90 秒為 CPU時(shí)間，其余為I/O 時(shí)間。A 所耗費(fèi)的時(shí)間是（）。13假定編譯器規(guī)定 int 和 short 類型長(zhǎng)度分別為32 位和 16 位，執(zhí)行下列 C語(yǔ)言語(yǔ)句：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ì)算機(jī)存儲(chǔ)器按字節(jié)編

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

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

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

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

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

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

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

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

35、12 字節(jié)，接收方總是以與數(shù)據(jù)幀等長(zhǎng)的幀進(jìn)行確認(rèn)。為使信道利用率達(dá)到最高，幀序號(hào)的比特?cái)?shù)至少為（）。A5B4C3D23737下列關(guān)于IP路由器功能的描述中，正確的是（）。運(yùn)行路由協(xié)議，設(shè)置路由表；監(jiān)測(cè)到擁塞時(shí)，合理丟棄進(jìn)行差錯(cuò)校驗(yàn)，確保傳輸?shù)腎P 分組不丟失；根據(jù)收到的IP輸出線路上。A僅、IP 分組；對(duì)收到的 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ā)送和接收電子郵件的過(guò)程如題40 圖所示，則圖中、階段分別使用的應(yīng)用層協(xié)議可以是（）。題 40 圖電子郵件發(fā)送接收示意圖ASMTP、 SMTP、SMTPBPOP3、 SMTP、POP3CPOP3、 SMTP、SMTPDSMTP、 SMTP、POP3二、綜合應(yīng)用題：41-47小題。共 70 分。41（ 10 分）設(shè)有 6 個(gè)有序表 A、B、 C、 D、E、F，分別含有10、 35、40、 50、 60 和 200 個(gè)數(shù)據(jù)元素，各表中元素按升序排列。要求通過(guò) 5 次兩兩合并，將 6 個(gè)表最終合并成 1 個(gè)升序表，并在最壞情況下比較的總

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

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

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

40、部分指令格式，其中Rs 和 Rd表示寄存器， mem表示存儲(chǔ)單元地址，（X）表示寄存器X 或存儲(chǔ)單元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ì)算機(jī)采用5 段流水方式執(zhí)行指令，各流水段分別是取指（IF ）、譯碼讀寄存器（ID ）、執(zhí)行計(jì)算有效地址 （EX）、訪問(wèn)存儲(chǔ)器 （ M）和結(jié)果寫回寄存器 （ WB），流水線采用“按序發(fā)射，按序完成”方式

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

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

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

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

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

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

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

48、結(jié)構(gòu)緊急指針填充2012 年全國(guó)碩士研究生入學(xué)統(tǒng)一考試408 計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合真題及詳解一、單項(xiàng)選擇題：l 40 小題。每小題2 分，共 80 分。下列每題給出的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)是最符合題目要求的。1求整數(shù) n（n0）階乘的算法如下，其時(shí)間復(fù)雜度是（）。AO（ log 2n）B0（ n）CO（ nlog 2n）DO（ n2）【答案】 B?！窘馕觥?設(shè) fact （ n）的運(yùn)行時(shí)間函數(shù)是T（n）。該函數(shù)中語(yǔ)句的運(yùn)行時(shí)間是 0（ 1），語(yǔ)句的運(yùn)行時(shí)間是 T（ n-1 ） +O（ 1），其中 O（ 1）為乘法運(yùn)算的時(shí)間。因此，當(dāng) n1時(shí)， T（n） -0 （ 1）；當(dāng) n1 時(shí)， 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）的時(shí)間復(fù)雜度為O（ n）。2已知操作符包括 +、 - 、 * 、（和）。將中綴表達(dá)式 a+b-a* （ c+d） e-f ）+g 轉(zhuǎn)換為等價(jià)的后綴表達(dá)式 ab+acd+ef-*-g+ 時(shí)，用棧來(lái)存放暫時(shí)還不能確定運(yùn)算次序的操作符。若棧初始時(shí)為空，則轉(zhuǎn)換過(guò)程中同時(shí)保存在棧中的操作符的最大個(gè)數(shù)是（）。A5B7C8D11【答案】 A?！窘馕觥?基本思想是：采用運(yùn)算符棧是為了比較運(yùn)算符的優(yōu)先級(jí)，所有運(yùn)算符必須進(jìn)棧。

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

51、 （ab+acd+與其配對(duì)的左括號(hào)及其前所有運(yùn)算符出棧-* （ab+acd+“”進(jìn)棧e-* （ab+acd+e-* （-ab+acd+e“- ”的優(yōu)先級(jí)小于棧頂元素“”，則“”出棧，“ - ”進(jìn)棧f-* （-ab+acd+ef）-*ab+acd+ef-與其配對(duì)的左括號(hào)及其前所有運(yùn)算符出棧+-ab+acd+ef-*“ +”的優(yōu)先級(jí)小于棧頂元素“ * ”，則“*”出棧+ab+acd+e f-*-“ +”與棧頂元素“ - ”的優(yōu)先級(jí)相同，則“ - ”出棧，“ +”進(jìn)棧g+ab+acd+e f-*-gab+acd+e全部出棧f-*-g+通過(guò)上表可以看出，顯然轉(zhuǎn)換過(guò)程中同時(shí)保存在棧中的操作符的最大個(gè)數(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無(wú)法確定【答案】 A?！窘馕觥?由題目可知，若一棵二叉樹的前序遍歷序列為a，e，b， d， c，后序遍歷序列為b， c， d，e，a，其中 a 為這棵二叉樹的根結(jié)點(diǎn)，接下來(lái)，在前序遍歷的第二個(gè)結(jié)點(diǎn)為e，而后序遍歷的倒數(shù)第二個(gè)結(jié)點(diǎn)為 e，說(shuō)明 a 的孩子結(jié)點(diǎn)只有 e。4若平衡二叉樹的高度為 6，且所有非葉結(jié)點(diǎn)的平衡因子均為1，則該平衡二叉樹的結(jié)點(diǎn)總數(shù)為（）。A12B20C32D33【答案】 B?！窘馕觥?本題題目的實(shí)際問(wèn)題是，具有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。對(duì)應(yīng)的平衡二叉樹如下圖所示。55對(duì)有 2 個(gè)頂點(diǎn) e 條邊且使用鄰接表存儲(chǔ)的有向圖進(jìn)行廣度優(yōu)先遍歷，其算法時(shí)間復(fù)雜度是 （）。A0（ n）B0（ e）CO（ n+e）DO（ne）【答案】 C?！窘馕觥?遍歷圖的過(guò)程實(shí)質(zhì)上是對(duì)每個(gè)頂點(diǎn)查找其鄰接點(diǎn)的過(guò)程。其耗費(fèi)的時(shí)間則取決于所采用的存儲(chǔ)結(jié)構(gòu)。當(dāng)用二維數(shù)組表示鄰接矩陣圖的存儲(chǔ)結(jié)構(gòu)時(shí)，查找每個(gè)頂點(diǎn)的鄰接點(diǎn)所需時(shí)間為O（ n2），其中 n 為圖中頂點(diǎn)數(shù)。而當(dāng)以鄰接表作圖的存儲(chǔ)結(jié)

54、構(gòu)時(shí)，找鄰接點(diǎn)所需時(shí)間為0（e），其中 e 為無(wú)向圖中邊的數(shù)或有向圖中弧的數(shù)。由此，當(dāng)以鄰接表作存儲(chǔ)結(jié)構(gòu)時(shí)， 深度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度為O（n+e）。即可得出正確答案。6若用鄰接矩陣存儲(chǔ)有向圖，矩陣中主對(duì)角線以下的元素均為零，則關(guān)于該圖拓?fù)湫蛄械慕Y(jié)論是（）。A存在，且唯一B存在，且不唯一不唯一C存在，可能不唯一D無(wú)法確定是否存在【答案】 C?！窘馕觥?圖的基本應(yīng)用拓?fù)渑判?，用鄰接矩陣存?chǔ)有向圖，矩陣中主對(duì)角線以下的元素均為零，說(shuō)明該圖為有向無(wú)環(huán)圖，所以其拓?fù)湫蛄写嬖?，但不一定唯一，如圖的鄰接矩陣為，則存在兩個(gè)拓?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í)行算法過(guò)程中各步的狀態(tài)如下表所示。執(zhí)行 Dijkstra算法過(guò)程中各步的狀態(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)于最小生成樹的敘述中，正確的是（）。最小生成樹的代價(jià)唯一所有權(quán)值最小的邊一定會(huì)出現(xiàn)在所有的最小生成樹中使用普里姆（ Prim ）算法從不同頂點(diǎn)開始得到的最小生成樹一定相同使用普里姆算法和克魯斯卡爾（ Kruskal ）算法得到的最小生成樹總不相同A僅B僅C僅、D僅、【答案】 A?！窘馕觥?當(dāng)圖中存在相同權(quán)值的邊時(shí)，其最小生成樹可能是不唯一的，但最小生成樹的代價(jià)一定是相同的，所以說(shuō)法正確。從n 個(gè)頂點(diǎn)的連

57、通圖中選取n-1 條權(quán)值最小的邊可能構(gòu)成回路，所以說(shuō)法錯(cuò)誤。當(dāng)某個(gè)頂點(diǎn)有權(quán)值相同的邊，使用普里姆（Prim ）算法從不同頂點(diǎn)開始得到的最小生成樹并不一定相同，所以說(shuō)法錯(cuò)誤。當(dāng)最小生成樹不唯一時(shí)，使用普里姆算法和克魯斯卡爾（Kruskal ）算法得到的最小生成樹可能相同，也可能不同，所以說(shuō)法錯(cuò)誤。由此可得出正確答案。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)鍵字個(gè)數(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排序過(guò)程中，對(duì)尚未確定最終位置的所有元素進(jìn)行一遍處理稱為一趟排序。下列排序方法中，每一趟排序結(jié)束時(shí)都至少能夠確定一個(gè)元素最終位置的方法是（）。簡(jiǎn)單選擇排序希爾排序快速排序堆排V二路歸并排序A僅、B僅、C僅、D僅、【答案】 A?！窘馕觥?其中簡(jiǎn)單選擇排序、堆排序?qū)儆谶x擇類排序，每一趟排序結(jié)束時(shí)將確定最大（或最小）關(guān)鍵字

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

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