沈陽(yáng)農(nóng)業(yè)大學(xué)信息與電氣工程學(xué)院805計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)歷年考研真題匯編附答案

沈陽(yáng)師范大學(xué)教育技術(shù)學(xué)院862計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基

礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)）歷年考研真題匯編附答案最新資料，WORD式，可編輯修改!目錄說(shuō)明：沈陽(yáng)師范大學(xué)2012年之前參加全國(guó)統(tǒng)考408計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合，2013年開(kāi)始自主命題，科目改為867計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)），2015年科目代碼改為862o為幫助考生全面復(fù)習(xí)，特提供2009?2012年408計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合真題及詳解。第一部分 沈陽(yáng)師范大學(xué)教育技術(shù)學(xué)院862計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)）歷年考研真題匯編2014年沈陽(yáng)師范大學(xué)教育技術(shù)學(xué)院867計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)）考研真題科目代碼：867科目名稱(chēng)：計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)）適用專(zhuān)業(yè)名稱(chēng)：計(jì)算機(jī)應(yīng)用技術(shù)考生注意：請(qǐng)將答案寫(xiě)在答題紙上，寫(xiě)在本題簽及草紙上無(wú)效?？荚嚭蟊绢}簽同答題紙一并交回。一、單項(xiàng)選擇題（共10題，每題2分，合計(jì)20分）1．某算法的時(shí)間復(fù)雜度為 O（n2），表明該算法（）。A.問(wèn)題規(guī)模是n2B.執(zhí)行時(shí)間等于n2C.執(zhí)行時(shí)間與n2成正比D.問(wèn)題規(guī)模與n2成正比2設(shè)線(xiàn)性表有 n個(gè)元素，以下操作中，（）在順序表上實(shí)現(xiàn)比在鏈表上實(shí)現(xiàn)效率更高。A.輸出第i（1<i<n）個(gè)元素B.交換第1個(gè)元素與第2個(gè)元素的值C.順序舉^出這n個(gè)元素的值D.輸出與給定值x相等的元素在線(xiàn)性表中的序號(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è)位置，隊(duì)尾指針rear指向隊(duì)尾元素的位置，隊(duì)列中的單元個(gè)數(shù)為 MaxSize）的隊(duì)滿(mǎn)足條件是（）。A．（+1）%MaxSize==+1）%MaxSize+1）%MaxSize==+1C．+1）%MaxSize==D．==5.一棵二叉樹(shù)的中序序列為 ABDCEF,G后序序列為BDCAFGE則其左子樹(shù)中的節(jié)點(diǎn)個(gè)數(shù)為（）。A．32C．4D．56．根據(jù)使用頻率為 5個(gè)字符設(shè)計(jì)的哈夫曼編碼不可能是（）。A．111,110,10,01,00B．000,001,010,011,1C．100,11,10,1,0D．001,000,01,11,107．對(duì)所示的無(wú)向圖，從頂點(diǎn)1開(kāi)始進(jìn)行深度優(yōu)先遍歷，可得到的頂點(diǎn)訪(fǎng)問(wèn)序列為（）。A．1243576B．1243567C．1245637D．12345768．對(duì)于下圖，以下（）是其拓?fù)湫蛄小．1,3,4,6,2,5,7B．1,3,2,6,4,5,7C．1,3,4,5,2,6,7D．1,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,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開(kāi)始的一棵最小生成樹(shù)。12．設(shè)有一組關(guān)鍵字 {19,1,23,14,55,20,84,27,68,11,10,77}，其哈希函數(shù)如下：H（key）=key%13采用開(kāi)放地址法的線(xiàn)性探測(cè)法解決沖突，試在 0~18的哈希表中對(duì)該關(guān)鍵字序列構(gòu)造哈希表。13.已知有6個(gè)頂點(diǎn)（頂點(diǎn)編號(hào)為0-5）的有向帶權(quán)圖G,其鄰接矩陣A為上三角矩陣，按行為主序（行優(yōu)先）保存在如下的一維數(shù)組中。46OOOOOO5OOOOOO43OOOO33要求：（1）寫(xiě)出圖G的鄰接矩陣A。（2）畫(huà)出有向帶權(quán)圖Go（3）求圖G的關(guān)鍵路徑，并計(jì)算該關(guān)鍵路徑的長(zhǎng)度。.將整數(shù)序列{4,5,7,2,1,3,6} 中的數(shù)依次插入到一棵空的平衡二叉樹(shù)中，構(gòu)造相應(yīng)的平衡二叉樹(shù)。三、算法設(shè)計(jì)題（共3題，每題10分，合計(jì)30分）.設(shè)0=包1白1,a2,b2,…,an,bn}為一線(xiàn)性表，采用帶頭節(jié)點(diǎn)的hc單鏈表存放，設(shè)計(jì)一個(gè)就地算法，將其拆分為兩個(gè)線(xiàn)性表（它們都用單鏈表存放），使A={a1,,a2,…，an},B={b1，b2,…,bn}.假設(shè)二叉樹(shù)采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，試設(shè)計(jì)一個(gè)算法，計(jì)算一棵給定二叉樹(shù)的所有分支節(jié)點(diǎn)個(gè)數(shù)。.設(shè)計(jì)一個(gè)算法，判斷一個(gè)數(shù)據(jù)序列是否構(gòu)成一個(gè)小根堆。四、簡(jiǎn)答題（共6題，每題5分，合計(jì)30分）.什么是操作系統(tǒng)的基本功能？.描述系統(tǒng)調(diào)用的含義。.說(shuō)明什么是進(jìn)程間的直接制約與間接制約。.說(shuō)明什么是虛擬存儲(chǔ)器。.請(qǐng)說(shuō)明分區(qū)存儲(chǔ)管理方式的主要優(yōu)缺點(diǎn)。.說(shuō)明什么是中斷。五、綜合題（共2題，每題15分，合計(jì)30分）.若有以下四個(gè)作業(yè)以1、2、3、4的順序，在0時(shí)刻幾乎同時(shí)到達(dá)系統(tǒng)并立即進(jìn)入調(diào)度：作業(yè)名 所需CPUH間作業(yè)19小時(shí)作業(yè)22小時(shí)作業(yè)310小時(shí)作業(yè)45小時(shí)假設(shè)系統(tǒng)中沒(méi)有其他作業(yè)，試給出對(duì)它們實(shí)施FCFSM度算法的計(jì)算結(jié)果,并計(jì)算其平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。.幾個(gè)并行進(jìn)程共享一個(gè)數(shù)據(jù)集（如文件或表格）時(shí)，有些進(jìn)程可能只是要求讀這數(shù)據(jù)集的內(nèi)容，而另一些進(jìn)程則可能要求修改這數(shù)據(jù)集的內(nèi)容。這種情況在操作系統(tǒng)中是很普遍的。通常我們稱(chēng)讀數(shù)據(jù)的進(jìn)程為讀者，而把要求修改數(shù)據(jù)的進(jìn)程稱(chēng)為寫(xiě)者。用P、V操作來(lái)描述讀者一寫(xiě)者問(wèn)題。2013年沈陽(yáng)師范大學(xué)教育技術(shù)學(xué)院867計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)）考研真題代碼：868科目名稱(chēng)：計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合適用專(zhuān)業(yè)名稱(chēng)：計(jì)算機(jī)應(yīng)用技術(shù)考生注意：請(qǐng)將答案寫(xiě)在答題紙上，寫(xiě)在本題簽及草紙上無(wú)效?？荚嚭蟊绢}簽同答題紙一并交回。一、單項(xiàng)選擇題（共30題，每題2分，合計(jì)60分）某算法的時(shí)間復(fù)雜度為 O（n2），表明該算法的（ ）。A.問(wèn)題規(guī)模是n2B.執(zhí)行時(shí)間等于n2C.執(zhí)行時(shí)間與n2成正比D.問(wèn)題規(guī)模與n2成正比2．設(shè)線(xiàn)性表中有 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í)的操作為（）。A．s->next=p->next；p->next=s；t=p->data；p->data=s->data；s->data=t；B．p->next=s；s->next=p->next；t=p->data；p->data=s->data；s->data=t；C．s->next=p->next；p->next=s；p->data=s->data；t=p->data；s->data=t；D．p->next=s；s->next=p->next；t=s->data；s->datap->data；p->data=t；4.已知一個(gè)棧的進(jìn)棧序列是 1,2,3,……，n,其輸出序列是pi,p2,…，pn,若p產(chǎn)n,則pi的值（）。A．iB．n-iC．n-i+1D.不確定5．對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，常用的兩種方法是（）。A.二元組和散列表B.三元組和十字鏈表C.三角矩陣和對(duì)角矩陣D.對(duì)角矩陣和十字鏈表.廣義表（（a）,a）的表頭和表尾分別是（ ）。（a）和（a）a和（a）（a）和a（（a））和（a）.已知二叉樹(shù)的先序序列為ABDEGCF中序序列為DBGEACF則后序序列為（）。GEDBFCADGEBFCADGEBAFCEBFDGCA.一棵完全二叉樹(shù)上有1000個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（ ）。250500505501.線(xiàn)索二叉樹(shù)是一種（ ）結(jié)構(gòu)。A.邏輯邏輯和存儲(chǔ)C.物理D.線(xiàn)性.以數(shù)據(jù)集｛2,5,7,9,13｝為權(quán)值構(gòu)造一棵哈夫曼樹(shù)，則其帶權(quán)路徑長(zhǎng)為（）。78808179.一個(gè)有向圖的鄰接表存儲(chǔ)如圖 1所示，現(xiàn)按深度優(yōu)先搜索遍歷，從頂點(diǎn)V1出發(fā)，所得到的頂點(diǎn)序列是（ ）。D.可能不存在13.若一個(gè)有向圖中的頂點(diǎn)不能排成一個(gè)拓?fù)湫蛄?，則可斷定該有向圖（）。A.是個(gè)有根有向圖B.是個(gè)強(qiáng)連通圖C.含有多個(gè)入度為0的頂點(diǎn)D.含有頂點(diǎn)數(shù)目大于1的強(qiáng)連通分量14．順序查找法適合于存儲(chǔ)結(jié)構(gòu)為（）的線(xiàn)性表。A.哈希存儲(chǔ)B.索引存儲(chǔ)C.壓縮存儲(chǔ)D.順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)15．在含有27個(gè)結(jié)點(diǎn)的二叉樹(shù)排序樹(shù)上，查找關(guān)鍵字為35的結(jié)點(diǎn)，則依次比較的關(guān)鍵字有可能是（）。TOC\o"1-5"\h\zA． 28， 36， 18， 46， 35B． 18， 36， 28， 46， 35C． 46， 28， 18， 36， 35D． 46， 36， 18， 28， 3516．在有序表 a[1..20]中，采用二分查找算法查找元素值等于a[12]的元素，所比較過(guò)元素的次數(shù)為（）。A．4B．5C．3D．617.數(shù)據(jù)序列｛8,9,10,4,5,6,20,1,2｝只能是下列排序算法中的（）的兩趟排序后的結(jié)果。A.選擇排序B.冒泡排序C.插入排序D.堆排序18．就平均性能而言，目前最好的內(nèi)部排序方法是（）排序法。A.冒泡排序B.希爾排序C.插入排序D.快速排序19.有一組數(shù)據(jù)｛ 15, 9, 7,8,20,-1,7,4｝,用堆排序的篩選方法建立的初始堆為（）。TOC\o"1-5"\h\zA． -1 ， 4， 5，9， 20， 7， 15， 7B． -1 ， 7， 15，7，4， 8， 20， 9C． -1 ， 4， 7，8， 20， 15，7， 9D.A,B,C都不對(duì)．下面說(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è)工程提前完成．下列選項(xiàng)中，（）不是操作系統(tǒng)關(guān)心的主要問(wèn)題。A.管理計(jì)算機(jī)裸機(jī)B.設(shè)計(jì)、提供用戶(hù)程序與計(jì)算機(jī)硬件系統(tǒng)的界面C.管理計(jì)算機(jī)系統(tǒng)資源D.高級(jí)程序設(shè)計(jì)語(yǔ)言的編譯器．系統(tǒng)功能調(diào)用是（）。A.用戶(hù)編寫(xiě)的一個(gè)子程序B.高級(jí)語(yǔ)言中的庫(kù)程序C.操作系統(tǒng)中的一條命令D.操作系統(tǒng)向用戶(hù)程序提供的接口．在處理機(jī)管理中，當(dāng)（）時(shí)，進(jìn)程從阻塞狀態(tài)變?yōu)榫途w狀態(tài)。A.進(jìn)程被調(diào)度程序選中B.等待某一事件發(fā)生C.等待的事件發(fā)生D.時(shí)間片用完．高級(jí)調(diào)度是（）。A.進(jìn)程調(diào)度B.作業(yè)調(diào)度C.程序調(diào)度D.設(shè)備調(diào)度．臨界區(qū)是（）。一個(gè)緩沖區(qū)一段共享數(shù)據(jù)區(qū)一段程序一個(gè)互斥資源．產(chǎn)生死鎖的根本原因是（）。A.資源共享B.并發(fā)執(zhí)行的進(jìn)程太多C.進(jìn)程推進(jìn)順序非法D.以上3個(gè)因素全是．在下述存儲(chǔ)管理方案中，（）管理方式要求作業(yè)占用連續(xù)的存儲(chǔ)空間。A.分區(qū)B.分頁(yè)C.分段D.段頁(yè)式．操作系統(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).下列文件中屬于邏輯結(jié)構(gòu)的文件是（ ）。A.連續(xù)文件B.系統(tǒng)文件C.散列文件D.流式文件.在磁盤(pán)文件系統(tǒng)中，對(duì)于下列文件物理結(jié)構(gòu)，（ ）不具有直接讀寫(xiě)文件任意一個(gè)記錄的能力。A.順序結(jié)構(gòu)B.鏈接結(jié)構(gòu)C.索引結(jié)構(gòu)D.散列結(jié)構(gòu)二、算法設(shè)計(jì)題（共2題，每題10分，合計(jì)20分）.設(shè)C={a1,b1,a2,b2,…,an,bn}為一線(xiàn)性表，采用帶頭結(jié)點(diǎn)的 hc單鏈表存放，設(shè)計(jì)一個(gè)就地算法，將其拆分為兩個(gè)線(xiàn)性表，使得：A={a1,a2,…，an},B={b1,b2, …，bn}.冒泡排序的算法是把大的元素向上移動(dòng)（氣泡的上升）也可以把最小的元素向下移動(dòng)（氣泡的下沉）。請(qǐng)給出上浮和下沉過(guò)程交替的冒泡排序算法。三、綜合應(yīng)用題（共6題，合計(jì)70分）.寫(xiě)出用Prim算法構(gòu)造圖2最小生成樹(shù)的過(guò)程。（10分）圖2無(wú)向網(wǎng).關(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。如果采用開(kāi)放定址的線(xiàn)性探測(cè)再散列方法解決沖突，請(qǐng)構(gòu)造哈希表并求其查找成功時(shí)的平均查找長(zhǎng)度。（10分）.在如圖3所示的AOEW,求：（10分）（1）完成此工程最少需要的多少天（設(shè)邊上權(quán)值為天數(shù)）。（2）是否存在某項(xiàng)活動(dòng)，當(dāng)其提高速度后能使整個(gè)工程縮短工期。a3=36.若有以下四個(gè)作業(yè)同2憐作業(yè)名作業(yè)

作業(yè)

作業(yè)

作業(yè)12347ck=a8=150AOEa3=36.若有以下四個(gè)作業(yè)同2憐作業(yè)名作業(yè)

作業(yè)

作業(yè)

作業(yè)12347ck=a8=150AOE典并遇=4入調(diào)8SJEa13=29CPUH間（分鐘）a6=38a2=6假設(shè)系統(tǒng)中沒(méi)有其他作業(yè),3..現(xiàn)新3注球94給出作業(yè)調(diào)度順序并求出平均作業(yè)周轉(zhuǎn)時(shí)間 T,平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間W（15分）.在一個(gè)請(qǐng)求式頁(yè)式管理系統(tǒng)中，某程序在內(nèi)存中分配三個(gè)頁(yè)面，初始為空.頁(yè)面走向?yàn)椋?,3,2,1,4,3,5,4,3,2,1,5。用學(xué)過(guò)的頁(yè)面值換算法FIFO算出缺頁(yè)次數(shù)。給出執(zhí)行過(guò)程中內(nèi)存頁(yè)面的變化情況。（ 15分）.在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)行描述。試寫(xiě)出這四個(gè)并發(fā)進(jìn)程能正確執(zhí)行的程序。（ 10分）第二部分 全國(guó)碩士研究生入學(xué)統(tǒng)一考試 408計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合歷年真題及詳解2012年全國(guó)碩士研究生入學(xué)統(tǒng)一考試 408計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合真題一、單項(xiàng)選擇題：l?40小題。每小題2分，共80分。下列每題給出的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)是最符合題目要求的。.求整數(shù)n（n>0）階乘的算法如下，其時(shí)間復(fù)雜度是（ ）。A．O（log2n）0（n）C．O（nlog2n）D．O（n2）2．已知操作符包括‘ +’、‘ -’、‘ *’、‘／’、‘（’和‘）’。將中綴表達(dá)式a+b-a*（（c+d）/e-f）+g轉(zhuǎn)換為等價(jià)的后綴表達(dá)式 ab+acd+e/f-*-g+時(shí)，用棧來(lái)存放暫時(shí)還不能確定運(yùn)算次序的操作符。若棧初始時(shí)為空，則轉(zhuǎn)換過(guò)程中同時(shí)保存在棧中的操作符的最大個(gè)數(shù)是（）。A．57C．8D．113.若一棵二叉樹(shù)的前序遍歷序列為 a,e,b,d,c,后序遍歷序列為b,c,d,e,a,則根結(jié)點(diǎn)的孩子結(jié)點(diǎn)（ ）。A.只有eB.有e、bC.有e、cD.無(wú)法確定4．若平衡二叉樹(shù)的高度為 6，且所有非葉結(jié)點(diǎn)的平衡因子均為 1，則該平衡二叉樹(shù)的結(jié)點(diǎn)總數(shù)為（）。A．12B．20C．32D．335．對(duì)有 2個(gè)頂點(diǎn)e條邊且使用鄰接表存儲(chǔ)的有向圖進(jìn)行廣度優(yōu)先遍歷，其算法時(shí)間復(fù)雜度是（）。A．0（n）B．0（e）C．O（n+e）D.O（nxe）6．若用鄰接矩陣存儲(chǔ)有向圖，矩陣中主對(duì)角線(xiàn)以下的元素均為零，則關(guān)于該圖拓?fù)湫蛄械慕Y(jié)論是（）。A.存在，且唯一B.存在，且不唯一不唯一C.存在，可能不唯一D.無(wú)法確定是否存在7．有向帶權(quán)圖如題 7圖所示，若采用迪杰斯特拉（Dijkstra）算法求從源點(diǎn)a到其他各頂點(diǎn)的最短路徑，則得到的第一條最短路徑的目標(biāo)頂點(diǎn)是 b，第二條最短路徑的目標(biāo)頂點(diǎn)是 c，后續(xù)得到的其余各最短路徑的目標(biāo)頂點(diǎn)依次是（ ）。題7圖有向帶權(quán)圖A．d,e,fB．e，d，fC．f，d，eD．f，e，d8．下列關(guān)于最小生成樹(shù)的敘述中，正確的是（）。I.最小生成樹(shù)的代價(jià)唯一 n.所有權(quán)值最小的邊一定會(huì)出現(xiàn)在所有的最小生成樹(shù)中 田.使用普里姆（Prim）算法從不同頂點(diǎn)開(kāi)始得到的最小生成樹(shù)一定相同IV.使用普里姆算法和克魯斯卡爾（Kruskal）算法得到的最小生成樹(shù)總不相同A.僅IB.僅nC.僅I、mD.僅n、iv9.設(shè)有一棵3階B樹(shù)，如題9圖所示。刪除關(guān)鍵字 78得到一棵新B樹(shù)，其最右葉結(jié)點(diǎn)所含的關(guān)鍵字是（）。題9圖3二叉樹(shù)圖A．60B．60，62C．62，65D．6510．排序過(guò)程中，對(duì)尚未確定最終位置的所有元素進(jìn)行一遍處理稱(chēng)為一趟排序。下列排序方法中，每一趟排序結(jié)束時(shí)都至少能夠確定一個(gè)元素最終位置的方法是（）。I.簡(jiǎn)單選擇排序 n.希爾排序 田.快速排序 iv.堆排 V.二路歸并排序A.僅I、m、IVB.僅I、n、mC.僅n、m、ivD.僅田、IV、V11．對(duì)同一待排序列分別進(jìn)行折半插入排序和直接插入排序，兩者之間可能的不同之處是（）。A.排序的總趟數(shù)B.元素的移動(dòng)次數(shù)C.使用輔助空間的數(shù)量D.元素之間的比較次數(shù)

12．假定基準(zhǔn)程序 A在某計(jì)算機(jī)上的運(yùn)行時(shí)間為 l00秒，其中90秒為CPU時(shí)間，其余為I/O時(shí)間。若CPU1度提高50%,I/O速度不變，則運(yùn)行基準(zhǔn)程序A所耗費(fèi)的時(shí)間是（）。A．55秒B．60秒C．65秒D．70秒13．假定編譯器規(guī)定int和short類(lèi)型長(zhǎng)度分別為32位和16位，執(zhí)行下列C語(yǔ)言語(yǔ)句：unsignedshortX=65530;unsignedinty =X：得至Uy的機(jī)器數(shù)為（）。A．00007FFAHB．0000FFFAHC．FFFF7FFAHD．FFFFFFFAH.float類(lèi)型（即IEEE754單精度浮點(diǎn)數(shù)格式）能表示的最大正整數(shù)是）。A．B．C）。A．B．C．D．02126-22127-22127-22128-2103104103104．某計(jì)算機(jī)存儲(chǔ)器按字節(jié)編址，采用小端方式存放數(shù)據(jù)。假定編譯器規(guī)定int和short型長(zhǎng)度分別為32位和16位，并且數(shù)據(jù)按邊界對(duì)齊存儲(chǔ)。某 C語(yǔ)言程序段如下：若record變量的首地址為0xC008,則地址0xC008中內(nèi)容及的地址分別為（ ）。A．0x00、0xC00D0x00、0xCOOEC．0x11、0xC00DD．0x11、0xC00E.下列關(guān)于閃存（FlashMemory）的敘述中，錯(cuò)誤的是（ ）。A.信息可讀可寫(xiě)，并且讀、寫(xiě)速度一樣快B.存儲(chǔ)元由MOST組成，是一種半導(dǎo)體存儲(chǔ)器C.掉電后信息不丟失，是一種非易失性存儲(chǔ)器D.采用隨機(jī)訪(fǎng)問(wèn)方式，可替代計(jì)算機(jī)外部存儲(chǔ)器.假設(shè)某計(jì)算機(jī)按字編址，Cache有4個(gè)行，Cache和主存之間交換的塊大小為l個(gè)字。若Cache的內(nèi)容初始為空，采用2路組相聯(lián)映射方式和LRU瞽換算法，當(dāng)訪(fǎng)問(wèn)的主存地址依次為0，4，8，2，0，6，8，6，4，8時(shí)，命中Cache的次數(shù)是（）。A．1B．2C．3D．4．某計(jì)算機(jī)的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接編碼法，共有 33個(gè)微命令，構(gòu)成5個(gè)互斥類(lèi)，分別包含 7、3、12、5和6個(gè)微命令，則操作控制字段至少有（）。A．5位B．6位C．15位D．33位.某同步總線(xiàn)的時(shí)鐘頻率為100MHz,寬度為32位，地址/數(shù)據(jù)線(xiàn)復(fù)用，每傳輸一個(gè)地址或數(shù)據(jù)占用一個(gè)時(shí)鐘周期。若該總線(xiàn)支持突發(fā)（猝發(fā)）傳輸方式，則一次“主存寫(xiě)”總線(xiàn)事務(wù)傳輸 128位數(shù)據(jù)所需要的時(shí)間至少是 （ ）。）A．20nsB．40nsC．50nsD．80ns.下列關(guān)于USB總線(xiàn)特性的描述中，錯(cuò)誤的是（ ）。A.可實(shí)現(xiàn)外設(shè)的即插即用和熱插拔B.可通過(guò)級(jí)聯(lián)方式連接多臺(tái)外設(shè)C.是一種通信總線(xiàn)，可連接不同外設(shè)D.同時(shí)可傳輸2位數(shù)據(jù)，數(shù)據(jù)傳輸率高.下列選項(xiàng)中，在I/O總線(xiàn)的數(shù)據(jù)線(xiàn)上傳輸?shù)男畔ǎ?）。I.I/O接口中的命令字 n.I/O接口中的狀態(tài)字 m.中斷類(lèi)型號(hào)A.僅I、nB.僅I、mC.僅n、田d.I、n、田22．響應(yīng)外部中斷的過(guò)程中，中斷隱指令完成的操作，除保護(hù)斷點(diǎn)外，還包括（）。I.開(kāi)關(guān)中斷 n.保存通用寄存器的內(nèi)容 田.形成中斷服務(wù)程序入口地址并送 PCA.僅I、nB.僅I、mC.僅n、田d.I、n、田23．下列選項(xiàng)中，不可能在用戶(hù)態(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.用戶(hù)級(jí)I/O軟件、設(shè)備無(wú)關(guān)軟件、設(shè)備驅(qū)動(dòng)程序、中斷處理程序B.用戶(hù)級(jí)I/O軟件、設(shè)備無(wú)關(guān)軟件、中斷處理程序、設(shè)備驅(qū)動(dòng)程序C.用戶(hù)級(jí)I/O軟件、設(shè)備驅(qū)動(dòng)程序、設(shè)備無(wú)關(guān)軟件、中斷處理程序D.用戶(hù)級(jí)I/O軟件、中斷處理程序、設(shè)備無(wú)關(guān)軟件、設(shè)備驅(qū)動(dòng)程序27.假設(shè)5個(gè)進(jìn)程P0、Pl、P2、P3、P4共享三類(lèi)資源Rl、R2、R3,這些資源總數(shù)分別為18、6、22oTo時(shí)刻的資源分配情況如題27表所示，此時(shí)存在的一個(gè)安全序列是（ ）。題27表資源分配情況表已分配資源資源最大需求進(jìn)程R1R2R3R1R2R3PO3235510P14O3536P24O54O11P32O4425P4314424P0,P2,P4,Pl,P3Pl,P0,P3,P4,P2P2,Pl,P0,P3,P4P3,P4,P2,Pl,P0P028.若一個(gè)用戶(hù)進(jìn)程通過(guò)read系統(tǒng)調(diào)用讀取一個(gè)磁盤(pán)文件中的數(shù)據(jù)，則下列關(guān)于此過(guò)程的敘述中，正確的是（ ）。I.若該文件的數(shù)據(jù)不在內(nèi)存， 則該進(jìn)程進(jìn)入睡眠等待狀態(tài)； n.請(qǐng)求read系統(tǒng)調(diào)用會(huì)導(dǎo)致CPU從用戶(hù)態(tài)切換到核心態(tài)；m.read系統(tǒng)調(diào)用的參數(shù)應(yīng)包含文件的名稱(chēng)A.僅I、nB.僅I、mC.僅n、田d.I、n和田29.一個(gè)多道批處理系統(tǒng)中僅有 Pl和P2兩個(gè)作業(yè)，P2比Pl晚5ms到達(dá)它們的計(jì)算和I/0操作順序如下：P1:計(jì)算60msI/O80ms,計(jì)算20msP2:計(jì)算120ms,I/O40ms,計(jì)算40ms若不考慮調(diào)度和切換時(shí)間，則完成兩個(gè)作業(yè)需要的時(shí)間最少是（）。A．240msB．260msC．340msD．360ms30．若某單處理器多進(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)用完成并返回用戶(hù)態(tài)時(shí)能進(jìn)行處理機(jī)調(diào)度．下列關(guān)于進(jìn)程和線(xiàn)程的敘述中，正確的是（）。A.不管系統(tǒng)是否支持線(xiàn)程，進(jìn)程都是資源分配的基本單位B.線(xiàn)程是資源分配的基本單位，進(jìn)程是調(diào)度的基本單位C.系統(tǒng)級(jí)線(xiàn)程和用戶(hù)級(jí)線(xiàn)程的切換都需要內(nèi)核的支持D.同一進(jìn)程中的各個(gè)線(xiàn)程擁有各自不同的地址空間.下列選項(xiàng)中，不能改善磁盤(pán)設(shè)備 I/O性能的是（ ）。A.重排I/0請(qǐng)求次序B.在一個(gè)磁盤(pán)上設(shè)置多個(gè)分區(qū)C.預(yù)讀和滯后寫(xiě)D.優(yōu)化文件物理塊的分布33.在TCP/IP體系結(jié)構(gòu)中，直接為ICMP提供服務(wù)的協(xié)議是（ ）。A．PPPB．IPC．UDPD．TCP34．在物理層接口特性中，用于描述完成每種功能的事件發(fā)生順序的是（ ）。A.機(jī)械特性B.功能特性C.過(guò)程特性D.電氣特性35.以太網(wǎng)的MAO議提供的是（ ）。A.無(wú)連接不可靠服務(wù)B.無(wú)連接可靠服務(wù)C.有連接不可靠服務(wù)D.有連接可靠服務(wù)36.兩臺(tái)主機(jī)之間的數(shù)據(jù)鏈路層采用后退 N幀協(xié)議（GBN傳輸數(shù)據(jù)，數(shù)據(jù)傳輸速率為16kbps,單向傳播時(shí)延為270ms數(shù)據(jù)幀長(zhǎng)度范圍是128?512字節(jié),接收方總是以與數(shù)據(jù)幀等長(zhǎng)的幀進(jìn)行確認(rèn)。為使信道利用率達(dá)到最高，幀序號(hào)的比特?cái)?shù)至少為（）。A．5B．4C．3D．23737．下列關(guān)于 IP路由器功能的描述中，正確的是（）。I.運(yùn)行路由協(xié)議，設(shè)置路由表；n.監(jiān)測(cè)到擁塞時(shí)，合理丟棄 ip分組；出.對(duì)收到的ip分組頭進(jìn)行差錯(cuò)校驗(yàn)，確保傳輸?shù)腎P分組不丟失；IV.根據(jù)收到的Ip分組的目的Ip地址，將其轉(zhuǎn)發(fā)到合適的輸出線(xiàn)路上。A.僅田、IVB.僅I、n、mC.僅i、n、ivd.i、n、m、iv.ARPB議的功能是（ ）。A.根據(jù)IP地址查詢(xún)MACft址B.根據(jù)MACM址查詢(xún)IP地址C.根據(jù)域名查詢(xún)IP地址D.根據(jù)IP地址查詢(xún)域名．某主機(jī)的 IP地址為，子網(wǎng)掩碼為。若該主機(jī)向其所在子網(wǎng)發(fā)送廣播分組，則目的地址可以是（）。A.若用戶(hù)l與用戶(hù)2之間發(fā)送和接收電子郵件的過(guò)程如題 40圖所示，則圖中①、②、③階段分別使用的應(yīng)用層協(xié)議可以是（ ）。題40圖電子郵件發(fā)送接收示意圖A．SMTP、SMTP、SMTPPOP3、SMTP、POP3C．POP3、SMTP、SMTPD．SMTP、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è)升序表，并在最壞情況下比較的總次數(shù)達(dá)到最小。請(qǐng)回答下列問(wèn)題。（1）給出完整的合并過(guò)程，并求出最壞情況下比較的總次數(shù)。（2）根據(jù)你的合并過(guò)程，描述n（n>2）個(gè)不等長(zhǎng)升序表的合并策略，并說(shuō)明理由。42．（13分）假定采用帶頭結(jié)點(diǎn)的單鏈表保存單詞，當(dāng)兩個(gè)單詞有相同的后綴時(shí)，則可共享相同的后綴存儲(chǔ)空間。例如，“l(fā)oading”和“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）給出算法的基本設(shè)計(jì)思想。（2）根據(jù)設(shè)計(jì)思想，采用C或C+域JAVA語(yǔ)言描述算法，關(guān)鍵之處給出注釋。（3）說(shuō)明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度。43.（11分）假定某計(jì)算機(jī)的CPU主頻為80MHzCPI為4,并且平均每條指令訪(fǎng)存次，主存與Cache之間交換的塊大小為168,Cache的命中率為99%,存儲(chǔ)器總線(xiàn)寬度為32位。請(qǐng)回答下列問(wèn)題。（1）該計(jì)算機(jī)的MIPS數(shù)是多少？平均每秒Cache缺失的次數(shù)是多少？在不考慮DMA專(zhuān)送的情況下，主存帶寬至少達(dá)到多少才能滿(mǎn)足 CPU的訪(fǎng)存要求？（2）假定在Cache缺失的情況下訪(fǎng)問(wèn)主存時(shí)，存在％的缺頁(yè)率，則 CPU￥均每秒產(chǎn)生多少次缺頁(yè)異常？若頁(yè)面大小為4KB,每次缺頁(yè)都需要訪(fǎng)問(wèn)磁盤(pán)，訪(fǎng)問(wèn)磁盤(pán)時(shí)DMA專(zhuān)送采用周期挪用方式，磁盤(pán) I/O接口的數(shù)據(jù)緩沖寄存器為32位，則磁盤(pán)I/O接口平均每秒發(fā)出的DMA青求次數(shù)至少是多少？CPUffiDMA空制器同時(shí)要求使用存儲(chǔ)器總線(xiàn)時(shí)， 哪個(gè)優(yōu)先級(jí)更高？為什么？（4）為了提高性能，主存采用4體交叉存儲(chǔ)模式，工作時(shí)每l/4個(gè)存儲(chǔ)周期啟動(dòng)一個(gè)體。若每個(gè)體的存儲(chǔ)周期為 50ns,則該主存能提供的最大帶寬是多少？（12分）某16位計(jì)算機(jī)中，帶符號(hào)整數(shù)用補(bǔ)碼表示，數(shù)據(jù)Cache和指令Cache分離。題44表給出了指令系統(tǒng)中部分指令格式，其中Rs和Rd表示寄存器，me譙示存儲(chǔ)單元地址，（X）表示寄存器X或存儲(chǔ)單元X的內(nèi)容。表指令系統(tǒng)中部分指令格式名稱(chēng)指令的匯編格式指令功能加法指令A(yù)DDRsRd(Rs)+(Rd)fRd算術(shù)/邏輯左移SHLRd2*(Rd)fRd算術(shù)右移SHRRd(Rd)/2fRd取數(shù)指令LOADRDmem(mermfRd存數(shù)指令STORERsmem(Rs)—mem該計(jì)算機(jī)采用5段流水方式執(zhí)行指令，各流水段分別是取指（IF）、譯碼/讀寄存器（ID）、執(zhí)行/計(jì)算有效地址（EX）、訪(fǎng)問(wèn)存儲(chǔ)器（M）和結(jié)果寫(xiě)回寄存器（WB,流水線(xiàn)采用“按序發(fā)射，按序完成”方式，沒(méi)有采用轉(zhuǎn)發(fā)技術(shù)處理數(shù)據(jù)相關(guān)，并且同一個(gè)寄存器的讀和寫(xiě)操作不能在同一個(gè)時(shí)鐘周期內(nèi)進(jìn)行。請(qǐng)回答下列問(wèn)題。（1）若int型變量x的值為-513,存放在寄存器Rl中，則執(zhí)行指令“SHRRl”后，Rl的內(nèi)容是多少？（用十六進(jìn)制表示）(2)若某個(gè)時(shí)間段中，有連續(xù)的 4條指令進(jìn)入流水線(xiàn)，在其執(zhí)行過(guò)程中沒(méi)有發(fā)生任何阻塞，則執(zhí)行這4條指令所需的時(shí)鐘周期數(shù)為多少 ？(3)若高級(jí)語(yǔ)言程序中某賦值語(yǔ)句為 x=a+b,x、a和b均為int型變量,它們的存儲(chǔ)單元地址分別表示為［x］、［司和［b］。該語(yǔ)句對(duì)應(yīng)的指令序列及其在指令流水線(xiàn)中的執(zhí)行過(guò)程如題 44圖所示。則這4條指令執(zhí)行過(guò)程中，I3的ID段和14的IF段被阻塞的原因各是什么？(4)若高級(jí)語(yǔ)言程序中某賦值語(yǔ)句為 x=2*x+a,x和a均為unsignedint類(lèi)型變量，它們的存儲(chǔ)單元地址分別表示為 ［x］、回，則執(zhí)行這條語(yǔ)句至少需要多少個(gè)時(shí)鐘周期？要求模仿題44圖畫(huà)出這條語(yǔ)句對(duì)應(yīng)的指令序列及其在流水線(xiàn)中的執(zhí)行過(guò)程示意圖。(7分)某請(qǐng)求分頁(yè)系統(tǒng)的局部頁(yè)面置換策略如下：系統(tǒng)從 0時(shí)刻開(kāi)始掃描，每隔5個(gè)時(shí)間單位掃描一輪駐留集(掃描時(shí)間忽略不計(jì))，本輪沒(méi)有被訪(fǎng)問(wèn)過(guò)的頁(yè)框?qū)⒈幌到y(tǒng)回收，并放入到空閑頁(yè)框鏈尾，其中內(nèi)容在下一次被分配之前不被清空。當(dāng)發(fā)生缺頁(yè)時(shí)，如果該頁(yè)曾被使用過(guò)且還在空閑頁(yè)框鏈表中，則重新放回進(jìn)程的駐留集中；否則，從空閑頁(yè)框鏈表頭部取出一個(gè)頁(yè)框。假設(shè)不考慮其他進(jìn)程的影響和系統(tǒng)開(kāi)銷(xiāo)，初始時(shí)進(jìn)程駐留集為空。目前系統(tǒng)空閑頁(yè)框鏈表中頁(yè)框號(hào)依次為32、15、21、41o進(jìn)程P依次訪(fǎng)問(wèn)的＜虛擬頁(yè)號(hào)，訪(fǎng)問(wèn)時(shí)刻＞是：＜1,1＞、＜3,2＞、＜0,4＞、＜0,6＞、＜1,11＞、＜0,13＞、＜2,14＞。請(qǐng)回答下列問(wèn)題。(1)訪(fǎng)問(wèn)＜0,4＞時(shí)，對(duì)應(yīng)的頁(yè)框號(hào)是什么？(2)訪(fǎng)問(wèn)＜1,11＞時(shí)，對(duì)應(yīng)的頁(yè)框號(hào)是什么？說(shuō)明理由。(3)訪(fǎng)問(wèn)＜2,14＞時(shí)，對(duì)應(yīng)的頁(yè)框號(hào)是什么？說(shuō)明理由。(4)該策略是否適合于時(shí)間局部性好的程序 ？說(shuō)明理由。(8分)某文件系統(tǒng)空間的最大容量為 4TB(1T=24°),以磁盤(pán)塊為基本分配單位，磁盤(pán)塊大小為IKB。文件控制塊(FCB包含一個(gè)512B的索引表區(qū)。請(qǐng)回答下列問(wèn)題。(1)假設(shè)索引表區(qū)僅采用直接索引結(jié)構(gòu)，索引表區(qū)存放文件占用的磁盤(pán)塊號(hào)。索引表項(xiàng)中塊號(hào)最少占多少字節(jié)？可支持的單個(gè)文件最大長(zhǎng)度是多少字節(jié) ？(2)假設(shè)索引表區(qū)采用如下結(jié)構(gòu)：第0?7字節(jié)采用＜起始?jí)K號(hào)，塊數(shù)＞格式表示文件創(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ō)明理由。(9分)主機(jī)H通過(guò)快速以太網(wǎng)連接Internet,IP地址為，服務(wù)器S的IP地址為。H與S使用TCP通信時(shí)，在H上捕獲的其中5個(gè)IP分組如題47-a表所不。題47-a表IP分組的前40字節(jié)內(nèi)容(十六進(jìn)制)019b40008006lde8coa80008d34447500bd91388846b41c500000000 5db00000

20000400031066e833d3444750cOa8000813880bd9e0599fef846b41c66701216d037e100003019c40008006ldefcOa80008d3444750bd91388846b41c6e0599ff0501043802b3200004019d400080061ddecOa80008d34447500bd91388846b4lc6e0599ff0 c655000053106067ad3444750cOa8000813880bd9e0599ff0846b41d6501016d057d20000請(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分組到達(dá)H時(shí)經(jīng)過(guò)了多少個(gè)路由器？題47-b表注:4006eCadd3444750ca7601061388a108e0599ff0846b41d6501016dOb7d60000版本注:4006eCadd3444750ca7601061388a108e0599ff0846b41d6501016dOb7d60000版本頭部長(zhǎng)度服務(wù)類(lèi)型(8-15)總長(zhǎng)度(16-31)標(biāo)識(shí)標(biāo)志片偏移生存時(shí)(TTL)協(xié)議頭部校驗(yàn)和源IP地址目的IP地址來(lái)自S發(fā)出的3組IP分組頭和TCP段頭結(jié)構(gòu)分別如題47-a圖、題47-b圖所示:題47-a圖IP分組頭結(jié)構(gòu)源端口(0-15)目的端口(16-31)序號(hào)(seq)確認(rèn)號(hào)(ack)數(shù)據(jù)偏移保留URGACKPSHRSTSYNFIN窗口校驗(yàn)和緊急?#選項(xiàng)(長(zhǎng)度可艾) 填充題47-b圖TCP段頭結(jié)構(gòu)2012年全國(guó)碩士研究生入學(xué)統(tǒng)一考試 408計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合真題及詳解一、單項(xiàng)選擇題：l?40小題。每小題2分，共80分。下列每題給出的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)是最符合題目要求的。.求整數(shù)n(n>0)階乘的算法如下，其時(shí)間復(fù)雜度是( )。O(log2n)0(n)O(nlog2n)O(n2)【答案】Bo【解析】設(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)n&l時(shí)，T(n)-0(1);當(dāng)n>1時(shí)，T(n)=T(n-1)+O(1)。則，T(n)=O(1)+T(n-1)=2XO(1)+T(n-2)=(n-1)xO(1)+T(1)=nxO(1)=0(n)即fact(n)的時(shí)間復(fù)雜度為O(n)。.已知操作符包括‘+‘、'-'、'*'、'/'、'('和。將中綴表達(dá)式a+b-a*((c+d)/e-f)+g轉(zhuǎn)換為等價(jià)的后綴表達(dá)式ab+acd+e/f-*-g+時(shí)，用棧來(lái)存放暫時(shí)還不能確定運(yùn)算次序的操作符。若棧初始時(shí)為空，則轉(zhuǎn)換過(guò)程中同時(shí)保存在棧中的操作符的最大個(gè)數(shù)是( )。57811【答案】Ao【解析】基本思想是：采用運(yùn)算符棧是為了比較運(yùn)算符的優(yōu)先級(jí)，所有運(yùn)算符必須進(jìn)棧。只將大于棧頂元素優(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-*((+1ab+acd)-*(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+e/f)-*ab+acd+e/f-與其配對(duì)的左括號(hào)及其前所有運(yùn)算符出棧+-ab+acd+e/f-*“+”的優(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ù)是5。.若一棵二叉樹(shù)的前序遍歷序列為a,e,b,d,c,后序遍歷序列為b,c,d,e,a,則根結(jié)點(diǎn)的孩子結(jié)點(diǎn)( )。A.只有e.有e、bC.有e、cD.無(wú)法確定【答案】Ao【解析】由題目可知，若一棵二叉樹(shù)的前序遍歷序列為 a,e,b,d,c,后序遍歷序列為b,c,d,e,a,其中a為這棵二叉樹(shù)的根結(jié)點(diǎn)，接下來(lái)，在前序遍歷的第二個(gè)結(jié)點(diǎn)為e,而后序遍歷的倒數(shù)第二個(gè)結(jié)點(diǎn)為e,說(shuō)明a的孩子結(jié)點(diǎn)只有e。.若平衡二叉樹(shù)的高度為6,且所有非葉結(jié)點(diǎn)的平衡因子均為1,則該平衡二叉樹(shù)的結(jié)點(diǎn)總數(shù)為( )。12203233【答案】Bo【解析】本題題目的實(shí)際問(wèn)題是，具有6層結(jié)點(diǎn)的平衡二叉樹(shù)含有最少的結(jié)點(diǎn)數(shù)是多少。Nh表示深度為h的平衡二叉樹(shù)中含有的最少結(jié)點(diǎn)數(shù)，有 NL=0,N=1,Nb=2Nn=N-i+N-2+1由此可得20。對(duì)應(yīng)的平衡二叉樹(shù)如下圖所示。.對(duì)有2個(gè)頂點(diǎn)e條邊且使用鄰接表存儲(chǔ)的有向圖進(jìn)行廣度優(yōu)先遍歷，其算法時(shí)間復(fù)雜度是( )。0(n)0(e)O(n+e)O(nxe)【答案】Co【解析】遍歷圖的過(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é)構(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)。即可得出正確答案。.若用鄰接矩陣存儲(chǔ)有向圖，矩陣中主對(duì)角線(xiàn)以下的元素均為零，則關(guān)于該圖拓?fù)湫蛄械慕Y(jié)論是( )。A.存在，且唯一.存在，且不唯一不唯一C.存在，可能不唯一D.無(wú)法確定是否存在【答案】Co【解析】圖的基本應(yīng)用一一拓?fù)渑判?，用鄰接矩陣存?chǔ)有向圖，矩陣中主對(duì)角線(xiàn)以下的元素均為零，說(shuō)明該圖為有向無(wú)環(huán)圖，所以其拓?fù)湫蛄写嬖?，但r?\I]不一定唯一，如圖的鄰接矩陣為 ，則存在兩個(gè)拓?fù)湫蛄小?I)停7.有向帶權(quán)圖如題7圖所示，若采用迪杰斯特拉(Dijkstra)算法求從源點(diǎn)a到其他各頂點(diǎn)的最短路徑，則得到的第一條最短路徑的目標(biāo)頂點(diǎn)是b,第二條最短路徑的目標(biāo)頂點(diǎn)是c,后續(xù)得到的其余各最短路徑的目標(biāo)頂點(diǎn)依次是()。題7圖有向帶權(quán)圖d,e,fe,d,ff,d,ef,e,d【答案】Co【解析】本題主要考查Dijkstra算法的思想和解題步驟。題目執(zhí)行算法過(guò)程中各步的狀態(tài)如下表所示。執(zhí)行Dijkstra 算法過(guò)程中各步的狀態(tài)表，故后續(xù)目標(biāo)頂點(diǎn)依次為 f,d,e\頂點(diǎn)\^刖數(shù)、bcdef集合Sk=12(a,b)5(a,c)(a,b)k=2(a,b,c)(a,b,d){a,b,c}k=3(a,b,d)4(a,b,c,f)(a,b,c,e){a,b,c,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,e)8.下列關(guān)于最小生成樹(shù)的敘述中，正確的是（ ）I.最小生成樹(shù)的代價(jià)唯一 n.所有權(quán)值最小的邊一定會(huì)出現(xiàn)在所有的最小生成樹(shù)中 田.使用普里姆（Prim）算法從不同頂點(diǎn)開(kāi)始得到的最小生成樹(shù)一定相同IV.使用普里姆算法和克魯斯卡爾（Kruskal）算法得到的最小生成樹(shù)總不相同A.僅IB.僅nC.僅I、mD.僅n、iv【答案】Ao【解析】當(dāng)圖中存在相同權(quán)值的邊時(shí)，其最小生成樹(shù)可能是不唯一的，但最小生成樹(shù)的代價(jià)一定是相同的，所以說(shuō)法I正確。從 n個(gè)頂點(diǎn)的連通圖中選取n-1條權(quán)值最小的邊可能構(gòu)成回路，所以說(shuō)法n錯(cuò)誤。當(dāng)某個(gè)頂點(diǎn)有權(quán)值相同的邊，使用普里姆（Prim）算法從不同頂點(diǎn)開(kāi)始得到的最小生成樹(shù)并不一定相同，所以說(shuō)法出錯(cuò)誤。當(dāng)最小生成樹(shù)不唯一時(shí)，使用普里姆算法和克魯斯卡爾（Kruskal）算法得到的最小生成樹(shù)可能相同， 也可能不同，所以說(shuō)法IV錯(cuò)誤。由此可得出正確答案。.設(shè)有一棵3階B樹(shù)，如題9圖所示。刪除關(guān)鍵字78得到一棵新B樹(shù)，其最右葉結(jié)點(diǎn)所含的關(guān)鍵字是（ ）。題9圖3二叉樹(shù)圖A．60B．60，62C．62，65D．65【答案】 D。【解析】 本題主要考查 B樹(shù)刪除操作。即被刪關(guān)鍵字所在的結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)等于[ m/2]-1，而與該結(jié)點(diǎn)相鄰的右兄弟（或左兄弟）結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目大于[ m/2] -1，則需將其兄弟結(jié)點(diǎn)中最?。ɑ蜃畲螅┑年P(guān)鍵字上移至雙親結(jié)點(diǎn)中，而將雙親結(jié)點(diǎn)中小于（或大于）且緊靠該上移關(guān)鍵字的關(guān)鍵字下移至被刪關(guān)鍵字所在結(jié)點(diǎn)中。題目中刪除關(guān)鍵字 78得到一棵新 B樹(shù)如下，其最右葉結(jié)點(diǎn)所含的關(guān)鍵字是 65。．排序過(guò)程中，對(duì)尚未確定最終位置的所有元素進(jìn)行一遍處理稱(chēng)為一趟排序。下列排序方法中，每一趟排序結(jié)束時(shí)都至少能夠確定一個(gè)元素最終位置的方法是（）。i.簡(jiǎn)單選擇排序 n.希爾排序田.快速排序 iv.堆排V.二路歸并排序A.僅I、m、IVB.僅I、n、mC.僅n、m、ivD.僅田、IV、v【答案】 A。【解析】 其中簡(jiǎn)單選擇排序、堆排序?qū)儆谶x擇類(lèi)排序，每一趟排序結(jié)束時(shí)將確定最大（或最小）關(guān)鍵字所在的位置?？焖倥判蛎恳惶伺判蚪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）,所以?xún)烧咧g的不同只可能是元素之間的比較次數(shù)。12．假定基準(zhǔn)程序 A在某計(jì)算機(jī)上的運(yùn)行時(shí)間為l00秒，其中90秒為CPU時(shí)間，其余為I/O時(shí)間。若CPU1度提高50%,I/O速度不變，則運(yùn)行基準(zhǔn)程序A所耗費(fèi)的時(shí)間是（）。A．55秒

B．60秒C．65秒D．70秒【答案】D?！窘馕觥緾PU1度提高50%,即CPU生能提高比為，改進(jìn)之后的CPUS行時(shí)間=90+=60秒。I/O速度不變，仍維持10秒，所以運(yùn)行基準(zhǔn)程序A所耗費(fèi)的時(shí)間為70秒。13．假定編譯器規(guī)定 int和short類(lèi)型長(zhǎng)度分別為32位和16位，執(zhí)行下列C語(yǔ)言語(yǔ)句：unsignedshortX=65530;unsignedinty =X：得至Uy的機(jī)器數(shù)為（）。A．00007FFAH0000FFFAHC．FFFF7FFAHD．FFFFFFFAH【答案】B?！窘馕觥縓和y均為無(wú)符號(hào)數(shù)，其中X為16位，y為32位，將16位無(wú)符號(hào)數(shù)轉(zhuǎn)化成32位無(wú)符號(hào)數(shù)，前面要補(bǔ)零。因?yàn)?X=65530=FFFAh|所以y=0000FFFAH。.float類(lèi)型（即IEEE754單精度浮點(diǎn)數(shù)格式）能表示的最大正整數(shù)是A．021262103B．A．021262103B．2127-2104C．D．2127-21032128-2104【答案】 D。【解析】 IEEE754單精度浮點(diǎn)數(shù)尾數(shù)采用隱藏位策略的原碼表示， 且階碼用移碼表示的浮點(diǎn)數(shù)。規(guī)格化的短浮點(diǎn)數(shù)的真值為：（ -1）SxX2（E-127）,S為符號(hào)位，E的取值為1?254,f為23位；故float類(lèi)型能表示的最大整數(shù)是7X2（254-127）=2127X（2-2-23）=2128-2104。．某計(jì)算機(jī)存儲(chǔ)器按字節(jié)編址，采用小端方式存放數(shù)據(jù)。假定編譯器規(guī)定int和short型長(zhǎng)度分別為32位和16位，并且數(shù)據(jù)按邊界對(duì)齊存儲(chǔ)。某 C語(yǔ)言程序段如下：若record變量的首地址為0xC008,則地址0xC008中內(nèi)容及的地址分別為（ ）。A．0x00、0xC00D0x00、0xCOOEC．0x11、0xC00DD．0x11、0xC00E【答案】 D?！窘馕觥?2位整數(shù)a需要占4個(gè)字節(jié)，l6位整數(shù)c需要占2個(gè)字節(jié)，而字符數(shù)據(jù)b占一個(gè)字節(jié)。a=273，轉(zhuǎn)換成十六進(jìn)制是111H,采用小端方式存放數(shù)據(jù)，地址0xC008中的內(nèi)容為11H。由于數(shù)據(jù)按邊界^^齊存儲(chǔ)，地址0xC008?OxCOOB中存放a,地址0xC00C中存放b,地址0xC00D中空閑，地址0xC00&0xC00F中存放 c。.下列關(guān)于閃存（FlashMemory）的敘述中，錯(cuò)誤的是（ ）。A.信息可讀可寫(xiě)，并且讀、寫(xiě)速度一樣快B.存儲(chǔ)元由MOST組成，是一種半導(dǎo)體存儲(chǔ)器C.掉電后信息不丟失，是一種非易失性存儲(chǔ)器D.采用隨機(jī)訪(fǎng)問(wèn)方式，可替代計(jì)算機(jī)外部存儲(chǔ)器【答案】 A?！窘馕觥靠疾殚W存的特性，閃存是EEPROMJ進(jìn)一步發(fā)展，可讀可寫(xiě)，用MOS管的浮柵上有無(wú)電荷來(lái)存儲(chǔ)信息，它依然是 ROM勺一種，故寫(xiě)速度比讀速度要慢不少。閃存是一種非易失性存儲(chǔ)器，它采用隨機(jī)訪(fǎng)問(wèn)方式，現(xiàn)在常見(jiàn)的SSD固態(tài)硬盤(pán)就是由flash芯片組成的，故答案為 A。.假設(shè)某計(jì)算機(jī)按字編址，Cache有4個(gè)行，Cache和主存之間交換的塊大小為l個(gè)字。若Cache的內(nèi)容初始為空，采用2路組相聯(lián)映射方式和LRU瞽換算法，當(dāng)訪(fǎng)問(wèn)的主存地址依次為0，4，8，2，0，6，8，6，4，8時(shí)，命中Cache的次數(shù)是（）。A．1B．2C．3D．4【答案】 C?！窘馕觥緾ache有4個(gè)行，2路組相聯(lián)，即Cache被分成2組，每組2行。主存地址為0?1、4?5、8?9可映射到第0組Cache中，主存地址為2?3、6?7可映射到第1組Cache中。Cache初始為空，采用LRU替換算法，當(dāng)訪(fǎng)問(wèn)主存的10個(gè)地址依次為0,4,8,2,0,6,8,6,4,8時(shí)，命中Cache的次數(shù)共有3次，分別發(fā)生在第 7、8和10步時(shí)。．某計(jì)算機(jī)的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接編碼法，共有 33個(gè)微命令，構(gòu)成5個(gè)互斥類(lèi)，分別包含 7、3、12、5和6個(gè)微命令，則操作控制字段至少有（）。A．5位B．6位C．15位D．33位【答案】 C。【解析】 33個(gè)微命令分成 5個(gè)互斥類(lèi)（即5個(gè)字段），根據(jù)每個(gè)類(lèi)中微命令的多少可以分別確定字段的長(zhǎng)度為 3、2、4、3、3位，又因?yàn)椴捎弥苯泳幋a方式，所以它們之和3+2+4+3+3=15也就是操作控制字段的位數(shù)。.某同步總線(xiàn)的時(shí)鐘頻率為l00MHz,寬度為32位，地址/數(shù)據(jù)線(xiàn)復(fù)用，每傳輸一個(gè)地址或數(shù)據(jù)占用一個(gè)時(shí)鐘周期。若該總線(xiàn)支持突發(fā)（猝發(fā)）傳輸方式，則一次“主存寫(xiě)”總線(xiàn)事務(wù)傳輸 l28位數(shù)據(jù)所需要的時(shí)間至少是 （ ）。）。A．20nsB．40nsC．50nsD．80ns【答案】 C?！窘馕觥靠偩€(xiàn)的時(shí)鐘頻率為100MHz,則時(shí)鐘周期為10ns。數(shù)據(jù)是128位，總線(xiàn)寬度是 32位，所以需要4個(gè)時(shí)鐘周期，而傳輸?shù)刂愤€需要一個(gè)周期，所以傳輸一個(gè)128位的數(shù)據(jù)至少需要5個(gè)時(shí)鐘周期，所以至少需要10ns*5=50ns。.下列關(guān)于USB總線(xiàn)特性的描述中，錯(cuò)誤的是（ ）。A.可實(shí)現(xiàn)外設(shè)的即插即用和熱插拔B.可通過(guò)級(jí)聯(lián)方式連接多臺(tái)外設(shè)C.是一種通信總線(xiàn)，可連接不同外設(shè)D.同時(shí)可傳輸2位數(shù)據(jù)，數(shù)據(jù)傳輸率高TOC\o"1-5"\h\z【答案】 D?！窘馕觥縐SB總線(xiàn)即通用串行總線(xiàn)，它的特點(diǎn)有：（1）即插即用；（2）熱插拔；（ 3）有很強(qiáng)的鏈接能力能將所有外設(shè)鏈接起來(lái)，且不損失帶寬；（ 4）有很好的可擴(kuò)展性；（5）高速傳輸，速度可達(dá)480Mbp4所有A,B,C都符合USB總線(xiàn)的特點(diǎn)。對(duì)于選項(xiàng)D,USB是串行總線(xiàn)，不能同時(shí)傳輸兩位數(shù)據(jù)，所以答案為D。.下列選項(xiàng)中，在I/O總線(xiàn)的數(shù)據(jù)線(xiàn)上傳輸?shù)男畔ǎ?）。I.I/O接口中的命令字 n.I/0接口中的狀態(tài)字 m.中斷類(lèi)型號(hào)A.僅I、nB.僅I、mC.僅n、田d.I、n、田TOC\o"1-5"\h\z【答案】 D?！窘馕觥吭贗/O總線(xiàn)的數(shù)據(jù)線(xiàn)上傳輸?shù)男畔?I/O接口中的命令字、狀態(tài)字以及真正的數(shù)據(jù)，而中斷類(lèi)型號(hào)也是通過(guò)數(shù)據(jù)線(xiàn)傳輸?shù)摹?2．響應(yīng)外部中斷的過(guò)程中，中斷隱指令完成的操作，除保護(hù)斷點(diǎn)外，還包括（ ）。.開(kāi)關(guān)中斷 n.保存通用寄存器的內(nèi)容 田.形成中斷服務(wù)程序入口地址并送 PCA.僅I、nB.僅I、mC.僅n、田d.I、n、田【答案】 B?！窘馕觥恐袛嚯[指令完成的操作有3個(gè)：①保存斷點(diǎn)；②關(guān)中斷；③引出中斷服務(wù)程序（形成中斷服務(wù)程序入口地址并送 PQo而保存通用寄存器內(nèi)容的操作是由軟件來(lái)實(shí)現(xiàn)，不是由中斷隱指令實(shí)現(xiàn)的。23．下列選項(xiàng)中，不可能在用戶(hù)態(tài)發(fā)生的事件是（A.系統(tǒng)調(diào)用B.外部中斷C.進(jìn)程切換D.缺頁(yè)【答案】 C?！窘馕觥?我們?cè)趯W(xué)習(xí)操作系統(tǒng)中知道，任何一個(gè)進(jìn)程在現(xiàn)代操作系統(tǒng)中為了共享和保護(hù)，設(shè)定了用戶(hù)態(tài)和內(nèi)核態(tài)（可以通過(guò)設(shè)置軟、硬件標(biāo)志位來(lái)實(shí)現(xiàn)），在用戶(hù)態(tài)運(yùn)行用戶(hù)的程序，在內(nèi)核運(yùn)行系統(tǒng)的程序。所以，從選項(xiàng)來(lái)看，系統(tǒng)調(diào)用可以在任何態(tài)發(fā)生，用戶(hù)可以發(fā)起系統(tǒng)調(diào)用，系統(tǒng)也可以；外部中斷是不可控的，也會(huì)在任何時(shí)刻發(fā)生，缺頁(yè)的發(fā)生也是不可控的，可以發(fā)生在用戶(hù)代碼之間；而進(jìn)程切換卻不會(huì)在用戶(hù)態(tài)發(fā)生。我們可以考慮一下情形，進(jìn)程切換是在什么時(shí)候發(fā)生的，進(jìn)程切換前必定運(yùn)行的是進(jìn)程調(diào)度，只有進(jìn)程調(diào)度選擇了下一次被調(diào)度的進(jìn)程，進(jìn)程切換才可以進(jìn)行。進(jìn)程調(diào)度是 scheduler，進(jìn)程切換是dispather，這體現(xiàn)了現(xiàn)代操作系統(tǒng)策略與機(jī)制分離的設(shè)計(jì)思想。所以，進(jìn)程切換必定不會(huì)在用戶(hù)態(tài)發(fā)生（所謂發(fā)生指其起始的源頭時(shí)刻），必定是在內(nèi)核態(tài)（進(jìn)程調(diào)度）發(fā)生的。24．中斷處理和子程序調(diào)用都需要壓棧以保護(hù)現(xiàn)場(chǎng)，中斷處理一定會(huì)保存而子程序調(diào)用不需要保存其內(nèi)容的是（）。A.程序計(jì)數(shù)器B.程序狀態(tài)字寄存器C.通用數(shù)據(jù)寄存器D.通用地址寄存器【答案】 B。【解析】 中斷處理與子程序調(diào)用最大的區(qū)別是中斷處理程序與正在運(yùn)行的進(jìn)程可能無(wú)關(guān)，而子程序調(diào)用與正在運(yùn)行的進(jìn)程有關(guān)。中斷是要打斷處理器的正常工作次序，并要求其去處理某一事件的一種常用手段。因此，除了要保護(hù)當(dāng)前程序的地址，計(jì)數(shù)器（指針）和數(shù)據(jù)寄存器以外，還需要保存程序狀態(tài)字。子程序調(diào)用是與當(dāng)前進(jìn)程有關(guān)，是正在運(yùn)行的程序有意安排執(zhí)行的，這一類(lèi)調(diào)用發(fā)生的時(shí)間以及位置具有確定性，處于同一個(gè)進(jìn)程內(nèi)，因此不需要保存程序狀態(tài)字。所以中斷處理和子程序調(diào)用不同的區(qū)別是中斷處理程序必定會(huì)保存程序狀態(tài)字寄存器。25．下列關(guān)于虛擬存儲(chǔ)的敘述中，正確的是（）。A.虛擬存儲(chǔ)只能基于連續(xù)分配技術(shù)B.虛擬存儲(chǔ)只能基于非連續(xù)分配技術(shù)C.虛擬存儲(chǔ)容量只受外存容量的限制D.虛擬存儲(chǔ)容量只受內(nèi)存容量的限制【答案】 D?！窘馕觥?所謂虛擬存儲(chǔ)，是指運(yùn)行的進(jìn)程不必全部裝入內(nèi)存，只需要部分裝入便可以開(kāi)始運(yùn)行的一種技術(shù)，在運(yùn)行過(guò)程中，當(dāng)所需要的代碼部分不在內(nèi)存時(shí)，通過(guò)一種技術(shù)（例如缺頁(yè)中斷技術(shù)），將所需要的頁(yè)面調(diào)入內(nèi)存，從而繼續(xù)運(yùn)行。虛擬存儲(chǔ)可以在較少的內(nèi)存中運(yùn)行較大的程序。但是需要有較大的外存以及相應(yīng)的軟、硬件機(jī)制配合才能實(shí)現(xiàn)。虛擬存儲(chǔ)器可以連續(xù)分配也可以非連續(xù)分配，虛擬存儲(chǔ)器和外存大小沒(méi)有關(guān)系，所以選項(xiàng)中的 A,B,C都是錯(cuò)誤的，所以答案是D項(xiàng)。26.操作系統(tǒng)的I/O子系統(tǒng)通常由四個(gè)層次組成，每一層明確定義了與鄰近層次的接口。其合理的層次組織排列順序是（ ）。A.用戶(hù)級(jí)I/O軟件、設(shè)備無(wú)關(guān)軟件、設(shè)備驅(qū)動(dòng)程序、中斷處理程序B.用戶(hù)級(jí)I/O軟件、設(shè)備無(wú)關(guān)軟件、中斷處理程序、設(shè)備驅(qū)動(dòng)程序C.用戶(hù)級(jí)I/O軟件、設(shè)備驅(qū)動(dòng)程序、設(shè)備無(wú)關(guān)軟件、中斷處理程序D.用戶(hù)級(jí)I/O軟件、中斷處理程序、設(shè)備無(wú)關(guān)軟件、設(shè)備驅(qū)動(dòng)程序【答案】Ao【解析】對(duì)于一次設(shè)備的調(diào)用，操作系統(tǒng)為用戶(hù)準(zhǔn)備了系統(tǒng)調(diào)用的接口，當(dāng)用戶(hù)使用設(shè)備時(shí)，首先在用戶(hù)程序中發(fā)起一次系統(tǒng)調(diào)用，操作系統(tǒng)的設(shè)備無(wú)關(guān)層軟件接到該調(diào)用請(qǐng)求后調(diào)用處理程序進(jìn)行處理，根據(jù)調(diào)用格式和形參，再轉(zhuǎn)到相應(yīng)的設(shè)備驅(qū)動(dòng)程序去處理；大部分設(shè)備在運(yùn)行時(shí)是需要時(shí)間的，所以設(shè)備驅(qū)動(dòng)程序會(huì)以中斷方式驅(qū)動(dòng)設(shè)備，即設(shè)置好控制寄存器參數(shù)和中斷向量等參數(shù)后阻塞自己；當(dāng)設(shè)備準(zhǔn)備好或所需數(shù)據(jù)到達(dá)后設(shè)備硬件發(fā)出中斷，設(shè)備驅(qū)動(dòng)程序喚醒，將數(shù)據(jù)按上述調(diào)用順序逆向回傳到用戶(hù)程序中，或繼續(xù)驅(qū)動(dòng)設(shè)備執(zhí)行下一條指令。因此，I/O軟件從上到下分為四個(gè)層次：用戶(hù)層、與設(shè)備無(wú)關(guān)的軟件層、設(shè)備驅(qū)動(dòng)程序以及中斷處理程序。27.假設(shè)5個(gè)進(jìn)程P0、Pl、P2、P3、P4共享三類(lèi)資源Rl、R2R3,這些資源總數(shù)分別為18、6、22oTo時(shí)刻的資源分配情況如題27表所示，此時(shí)存在的一個(gè)安全序列是（ ）。題27表資源分配情況表已分配資源資源最大需求進(jìn)程R1R2R3R1R2R3PO3235510P14O3536P24O54O11P32O4425P4314424P0,P2,P4,Pl,P3Pl,P0,P3,P4,P2P2,Pl,P0,P3,P4P3,P4,P2,Pl,P0P0【答案】Do【解析】典型的死鎖避免算法、銀行家算法的應(yīng)用。本題的題型與 2011年的27題相似。銀行家算法是操作系統(tǒng)中的一個(gè)重點(diǎn)知識(shí)單元，考生對(duì)此應(yīng)該非常熟悉，本題并無(wú)難點(diǎn)。分析一下下表，可以看到， P3,P4,P2,Pl,P0運(yùn)行是可以的。已分配資源尚需資源可用資源進(jìn)程R1R2R3R1R2R3R1R2R3P32O4221233P4314llO437P24O5O067411P1403113311416PO32323715419本題也可以排除法，To時(shí)刻可用資源是R1,R2,R3分另U為2,3,3,此時(shí)刻，P0需要R1,R2,R3分另U為2,3,7,故排除A,P1需要R1,R2,R3分另U為1,3,3,P2還需要資源R1,R2,R3分別為0,0,6,故C排除，P3需要R1,R2,R3分別為2,2,1。所以正確答案在B,D之間?？碆選項(xiàng)，P1之后的可用資源R1,R2,R3分別變?yōu)?,3,6,而P0尚需資源2,3,7,故B方案行不通。因而最終答案只有D項(xiàng)。28.若一個(gè)用戶(hù)進(jìn)程通過(guò)read系統(tǒng)調(diào)用讀取一個(gè)磁盤(pán)文件中的數(shù)據(jù)，則下列關(guān)于此過(guò)程的敘述中，正確的是（ ）。I.若該文件的數(shù)據(jù)不在內(nèi)存，則該進(jìn)程進(jìn)入睡眠等待狀態(tài)； n.請(qǐng)求read系統(tǒng)調(diào)用會(huì)導(dǎo)致CPU從用戶(hù)態(tài)切換到核心態(tài)；m.read系統(tǒng)調(diào)用的參數(shù)應(yīng)包含文件的名稱(chēng)A.僅I、nB.僅I、mC.僅n、田d.I、n和田【答案】A【解析】對(duì)于I,當(dāng)所讀文件的數(shù)據(jù)不再內(nèi)存時(shí)，產(chǎn)生中斷（缺頁(yè)中斷、缺段中斷），原進(jìn)程進(jìn)入睡眠等待狀態(tài)（阻塞狀態(tài)），直到所需數(shù)據(jù)從外村調(diào)入內(nèi)存后，將該進(jìn)程喚醒，使其變?yōu)榫途w狀態(tài)。對(duì)于n,read系統(tǒng)調(diào)用CPUW從用戶(hù)態(tài)切換到核心態(tài)，從而獲取操作系統(tǒng)提供的服務(wù)。對(duì)于田，在操作系統(tǒng)中，要讀一個(gè)文件首先要open系統(tǒng)調(diào)用將該文件打開(kāi)。Open系統(tǒng)調(diào)用的參數(shù)需要包含文件的路徑名與文件名，而 read系統(tǒng)調(diào)用只需使用open返回的文件描述符，并不使用文件名作為參數(shù)。 Read系統(tǒng)調(diào)用要求用戶(hù)提供三個(gè)輸入?yún)?shù)：①文件描述符；②buf緩沖區(qū)首址；③傳送的字節(jié)數(shù)noread系統(tǒng)調(diào)用的功能是試圖從fd所指示的文件中讀入n個(gè)字節(jié)的數(shù)據(jù)，并將它們送至由指針 buf所指示的緩沖區(qū)中。一個(gè)多道批處理系統(tǒng)中僅有Pl和P2兩個(gè)作業(yè)，P2比Pl晚5ms到達(dá)。它們的計(jì)算和I/0操作順序如下：P1:計(jì)算60msI/O80ms,計(jì)算20msP2:計(jì)算120ms,I/O 40ms,計(jì)算40ms若不考慮調(diào)度和切換時(shí)間，則完成兩個(gè)作業(yè)需要的時(shí)間最少是（ ）。240ms260ms340ms360ms【答案】B?！窘馕觥靠疾樘幚硐到y(tǒng)的性能計(jì)算，由于P2比P1晚5ms到達(dá)，P1先占用CPU根據(jù)P1和P2的執(zhí)行過(guò)程，作業(yè)運(yùn)行的甘特圖如下所示，故答案為 Bo30．若某單處理器多進(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)用完成并返回用戶(hù)態(tài)時(shí)能進(jìn)行處理機(jī)調(diào)度【答案】 C。【解析】對(duì)于A(yíng)、B、D顯然是可以進(jìn)行處理機(jī)調(diào)度的，對(duì)于C,當(dāng)進(jìn)程處于臨界區(qū)時(shí)，只要不破壞臨界資源的使用規(guī)則，是不會(huì)影響處理機(jī)調(diào)度的，比如，通常訪(fǎng)問(wèn)臨界資源可能是慢速的外設(shè)（如打印機(jī)），如果在進(jìn)程訪(fǎng)問(wèn)打印機(jī)時(shí)，不能處理機(jī)調(diào)度，那么系統(tǒng)的性能將是非常低的。幾種不進(jìn)行處理機(jī)調(diào)度的情況如下：①在處理機(jī)中斷的過(guò)程中；②進(jìn)程在操作系統(tǒng)內(nèi)核程序臨界區(qū)中；③其他需要完全屏蔽中斷的原子操作過(guò)程中。．下列關(guān)于進(jìn)程和線(xiàn)程的敘述中，正確的是（）。A.不管系統(tǒng)是否支持線(xiàn)程，進(jìn)程都是資源分配的基本單位B.線(xiàn)程是資源分配的基本單位，進(jìn)程是調(diào)度的基本單位C.系統(tǒng)級(jí)線(xiàn)程和用戶(hù)級(jí)線(xiàn)程的切換都需要內(nèi)核的支持D.同一進(jìn)程中的各個(gè)線(xiàn)程擁有各自不同的地址空間【答案】 A。【解析】 利用排除法來(lái)確定正確答案：“線(xiàn)程是資源分配的基本單位，進(jìn)程是調(diào)度的基本單位”這句話(huà)說(shuō)反了，明顯錯(cuò)誤?！跋到y(tǒng)級(jí)線(xiàn)程和用戶(hù)級(jí)線(xiàn)程的切換都需要內(nèi)核的支持”也不正確，因?yàn)橛脩?hù)級(jí)線(xiàn)程的切換由用戶(hù)編寫(xiě)的RuntimeSystem執(zhí)行的，內(nèi)核并不感知。“同一進(jìn)程中的各個(gè)線(xiàn)程擁有各自不同的地址空間”明顯錯(cuò)誤，引入線(xiàn)程的目的就是為了同一進(jìn)程的所有線(xiàn)程能共享進(jìn)程的地址空間，故“不管系統(tǒng)是否支持線(xiàn)程，進(jìn)程都是資源分配的基本單位”是正確的。.下列選項(xiàng)中，不能改善磁盤(pán)設(shè)備 I/O性能的是（ ）。A.重排I/0請(qǐng)求次序B.在一個(gè)磁盤(pán)上設(shè)置多個(gè)分區(qū)C.預(yù)讀和滯后寫(xiě)D.優(yōu)化文件物理塊的分布【答案】B?！窘馕觥看疟P(pán)I/O性能主要是指其讀寫(xiě)速度。相對(duì)而言，磁盤(pán)的I/O性能是計(jì)算機(jī)性能提高的一個(gè)瓶頸?！爸嘏?I/O請(qǐng)求次序”可以?xún)?yōu)化磁臂調(diào)度的算法，減少讀寫(xiě)時(shí)間，故正確；“預(yù)讀和滯后寫(xiě)”是利用內(nèi)存作為磁盤(pán)的緩存，使得對(duì)磁盤(pán)的訪(fǎng)問(wèn)變?yōu)閷?duì)內(nèi)存的訪(fǎng)問(wèn)，也可以在總體上提高其性能；“優(yōu)化文件物理塊的分布”減少磁臂調(diào)度和旋轉(zhuǎn)調(diào)度的等待時(shí)間，也可以提高磁盤(pán) I／O性能，而磁盤(pán)分區(qū)僅在磁盤(pán)空間的組織上進(jìn)行劃分，對(duì)磁盤(pán)I/O性能的提升沒(méi)有什么幫助，是不能改善磁盤(pán)設(shè)備 I/O性能的，故答案為Bo33.在TCP/IP體系結(jié)構(gòu)中，直接為ICMP提供服務(wù)的協(xié)議是（ ）。A．PPPB．IPC．UDPD．TCP【答案】B?！窘馕觥渴紫让鞔_ICMP是網(wǎng)絡(luò)層的協(xié)議，由于服務(wù)必須是下一層向上一層提供服務(wù)的，因此選項(xiàng)C項(xiàng)中的UD濟(jì)口選項(xiàng)D項(xiàng)中的TCP屬于傳輸層，在網(wǎng)絡(luò)層上面，所以顯然錯(cuò)誤，而PPPW議是廣域網(wǎng)數(shù)據(jù)鏈路層協(xié)議，直接為網(wǎng)絡(luò)層，也就是IP層提供服務(wù)，ICMP協(xié)議是封裝在網(wǎng)絡(luò)層，因此PPP不能直接為ICMP提供服務(wù)，ICMP報(bào)文直接封裝在IP分組中，故答案是Bo34．在物理層接口特性中，用于描述完成每種功能的事件發(fā)生順序的是（ ）。A.機(jī)械特性B.功能特性C.過(guò)程特性D.電氣特性【答案】 C。【解析】 物理層的主要任務(wù)描述為確定與傳輸媒體接口的一些特性；機(jī)械特性：主要定義物理連接的邊界點(diǎn)，即接插裝置；電氣特性：規(guī)定傳輸二進(jìn)制位時(shí)，線(xiàn)路上信號(hào)的電壓高低、阻抗匹配、傳輸速率和距離限制；功能特性：主要定義各條物理線(xiàn)路的功能；規(guī)程特性：主要定義各條物理線(xiàn)路的工作規(guī)程和時(shí)序關(guān)系。而從題干可以分析描述事件先后順序的就是規(guī)程，也就是過(guò)程特性，答案是 C。35.以太網(wǎng)的MAO議提供的是（ ）。A.無(wú)連接不可靠服務(wù)B.無(wú)連接可靠服務(wù)C.有連接不可靠服務(wù)D.有連接可靠服務(wù)【答案】A。【解析】考查以太網(wǎng)MA的議，考慮到局域網(wǎng)信道質(zhì)量好，以太網(wǎng)采取了兩項(xiàng)重要的措施以使通信更簡(jiǎn)潔：①采用無(wú)連接的工作方式；②不對(duì)發(fā)送的數(shù)據(jù)幀進(jìn)行編號(hào)，也不要求對(duì)方發(fā)回確認(rèn)。因此，以太網(wǎng)提供的服務(wù)是不可靠的服務(wù)，即盡最大努力交付，差錯(cuò)的糾正由高層完成。36.兩臺(tái)主機(jī)之間的數(shù)據(jù)鏈路層采用后退N幀協(xié)議（GBN傳輸數(shù)據(jù)，數(shù)據(jù)傳輸速率為16kbps,單向傳播時(shí)延為270ms數(shù)據(jù)幀長(zhǎng)度范圍是128?512字節(jié),接收方總是以與數(shù)據(jù)幀等長(zhǎng)的幀進(jìn)行確認(rèn)。為使信道利用率達(dá)到最高，幀序號(hào)的比特?cái)?shù)至少為（）。A．5B．4C．3D．237TOC\o"1-5"\h\z【答案】 B?！窘馕觥縂BN勺工作原理如下圖所示，本題求解的是發(fā)送一個(gè)幀到接收到這個(gè)幀的確認(rèn)期間最多可以發(fā)送多少數(shù)據(jù)幀，要盡可能多發(fā)送幀，應(yīng)以短的數(shù)據(jù)幀計(jì)算，注意幀的單位是字節(jié)，因此首先計(jì)算出發(fā)送一幀的時(shí)間 t1=128X8/16kbps=64ms,故發(fā)送一幀到收到確認(rèn)為止的總時(shí)間為 ；64+270*2+64=668ms.這段時(shí)間總共可以發(fā)送668/64=（幀），為了保證發(fā)送幀序號(hào)和確認(rèn)幀序號(hào)在此期間不重復(fù)，因此幀序號(hào)的比特?cái)?shù)至少為 4，答案為 B37．下列關(guān)于 IP路由器功能的描述中，正確的是（）。I.運(yùn)行路由協(xié)議，設(shè)置路由表；n.監(jiān)測(cè)到擁塞時(shí)，合理丟棄 ip分組；出.對(duì)收到的ip分組頭進(jìn)行差錯(cuò)校驗(yàn)，確保傳輸?shù)?IP分組不丟失；IV.根據(jù)收到的Ip分組的目的Ip地址，將其轉(zhuǎn)發(fā)到合適的輸出線(xiàn)路上。A.僅田、IVB.僅I、n、mC.僅i、n、ivd.i、n、m、ivTOC\o"1-5"\h\z【答案】 C。【解析】路由器的主要功能是路由和轉(zhuǎn)發(fā)，因此I和IV是正確的，而針對(duì)

n和田，可以從icmp協(xié)議的差錯(cuò)控制出發(fā)，注意檢測(cè)到擁塞時(shí)，合理丟棄 ip分組，并回傳ICMP源抑制報(bào)文，n是正確的，而田對(duì)收到的IP分組頭進(jìn)行差錯(cuò)校驗(yàn)，確保傳輸?shù)膇p分組不丟失，差錯(cuò)校驗(yàn)是正確的，但網(wǎng)絡(luò)層不保證 ip分組不丟失，也就是不可靠的，因此田的說(shuō)法錯(cuò)誤，正確的說(shuō)法僅I、n、iv,因此答案是 C。.ARPB議的功能是（ ）。A.根據(jù)IP地址查詢(xún)MACM址B.根據(jù)MACM址查詢(xún)IP地址C.根據(jù)域名查詢(xún)IP地址D.根據(jù)IP地址查詢(xún)域名TOC\o"1-5"\h\z【答案】 A?！窘馕觥緼RPW議是網(wǎng)絡(luò)層協(xié)議，因此只能和傳輸層和數(shù)據(jù)鏈路層有關(guān)系，從這一點(diǎn)出發(fā)，域名是應(yīng)用層的范疇，選項(xiàng) C和D是不正確的，根據(jù)MAO址查詢(xún)IP地址是RAR的議的功能，因此進(jìn)而得出正確答案是 Ao．某主機(jī)的 IP地址為，子網(wǎng)掩碼為。若該主機(jī)向其所在子網(wǎng)發(fā)送廣播分組，則目的地址可以是（）。A．【答案】D。【解析】.，也就是，因此答案是 D。40．若用戶(hù) l與用戶(hù)2之間發(fā)送和接收電子郵件的過(guò)程如題40圖所示，則圖中①、②、③階段分別使用的應(yīng)用層協(xié)議可以是（ ）。題40圖電子郵件發(fā)送接收示意圖A．SMTP、SMTP、SMTPPOP3、SMTP、POP3C．POP3、SMTP、SMTPD．SMTP、SMTP、POP3【答案】 D?！窘馕觥?題中電子郵件的工作過(guò)程如下：①用戶(hù)l調(diào)用用戶(hù)代理來(lái)編輯要發(fā)送的郵件，用戶(hù)代理用 SMTP等郵件傳送給用戶(hù)1的發(fā)送端郵件服務(wù)器。②發(fā)送端郵件服務(wù)器也就是用戶(hù)1的郵件服務(wù)器將郵件放入郵件緩存隊(duì)列中，等待發(fā)送。③運(yùn)行在發(fā)送端郵件服務(wù)器的SMT喀戶(hù)進(jìn)程，發(fā)現(xiàn)在郵件緩存中有待發(fā)送的郵件，就向運(yùn)行在接收端郵件