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

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

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

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

4、復(fù)雜度為 O（n2）,表明該算法（）oA問題規(guī)模是n2B.執(zhí)行時(shí)間等于n2C.執(zhí)行時(shí)間與n2成正比D.問題規(guī)模與n2成正比2設(shè)線性表有n個(gè)元素，以下操作中，（）在順序表上實(shí)現(xiàn)比在鏈表上實(shí)現(xiàn)效率更 局。A輸出第i （1i 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.

5、 p-next=s ; s-next= p-next；t= s-data; s-data p-data;p-data= t;4 .已知一個(gè)棧的進(jìn)棧序列是1, 2, 3, ,n,其輸出序列是p1,p2,，p%若p1=n,則pi的值（）。A iB. n-iC. n-i+1D.不確定5.對稀疏矩陣進(jìn)行壓縮存儲(chǔ)，常用的兩種方法是（）。A二元組和散列表B.三元組和十字鏈表C.三角矩陣和對角矩陣D.對角矩陣和十字鏈表6 .廣義表（a） , a）的表頭和表尾分別是（）。A. （ a）和（a）B. a和（a）C. （a）和 aD. （ （ a）和（a）7 .已知二叉樹的先序序列為 ABDEGCF中序序列為DB

6、GEACF則后序序列為（）,A. GEDBFCAB. DGEBFCAC. DGEBAFCD. EBFDGCA8 . 一棵完全二叉樹上有1000個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（）。A 250B. 500C. 505D. 5019 .線索二叉樹是一種（）結(jié)構(gòu)。A.邏輯10 邏輯和存儲(chǔ)C.物理D.線性11 .以數(shù)據(jù)集2 , 5, 7, 9, 13為權(quán)值構(gòu)造一棵哈夫曼樹，則其帶權(quán)路徑長為（）A 78B. 80C. 81D. 7911.一個(gè)有向圖的鄰接表存儲(chǔ)如圖1所示，現(xiàn)按深度優(yōu)先搜索遍歷，從頂點(diǎn) 必出發(fā),所得到的頂點(diǎn)序列是（）?？赡懿淮嬖贒.13 .若一個(gè)有向圖中的頂點(diǎn)不能排成一個(gè)拓?fù)湫蛄?，則可斷定該有

7、向圖（）。A是個(gè)有根有向圖B.是個(gè)強(qiáng)連通圖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)鍵字有可能是（）A. 28, 36, 18, 46, 35B. 18, 36, 28, 46, 35C. 46, 28, 18, 36, 35D. 46, 36, 18, 28, 3516.在有序表a 1.20中，采用二分查找算法查找元素值等于 a12的元素，所 比較過元素的次數(shù)為（）。A. 4B. 5C. 3D.

8、 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,用堆排序的篩選方法建立的初 始堆為（）。A. -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都不對20 .下面說法不正確的是（）。A.關(guān)鍵活動(dòng)不按

9、期完成就會(huì)影響整個(gè)工程的完成時(shí)間B.任何一個(gè)關(guān)鍵活動(dòng)提前完成，將使整個(gè)工程提前完成C.所有關(guān)鍵活動(dòng)都提前完成，則整個(gè)工程提前完成D.某些關(guān)鍵活動(dòng)若提前完成，將使整個(gè)工程提前完成21 .下列選項(xiàng)中，（）不是操作系統(tǒng)關(guān)心的主要問題。A.管理計(jì)算機(jī)裸機(jī)B.設(shè)計(jì)、提供用戶程序與計(jì)算機(jī)硬件系統(tǒng)的界面C.管理計(jì)算機(jī)系統(tǒng)資源D.高級程序設(shè)計(jì)語言的編譯器22 .系統(tǒng)功能調(diào)用是（）。A.用戶編寫的一個(gè)子程序B.高級語言中的庫程序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í)間

10、片用完24 .高級調(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)順序非法D.以上3個(gè)因素全是27 .在下述存儲(chǔ)管理方案中，（）管理方式要求作業(yè)占用連續(xù)的存儲(chǔ)空間。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ù)存儲(chǔ)系統(tǒng)29 .下列文件中屬于邏輯結(jié)構(gòu)的文件是（）。A連續(xù)文件B.系統(tǒng)文件C.散列文件D.流式文件30 .在磁盤文件系統(tǒng)中，對于下列文件

11、物理結(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單鏈表存放， 設(shè)計(jì)一個(gè)就地算法，將其拆分為兩個(gè)線性表，使得： A= a1,a2,，an,B= b1, b2, bn32 .冒泡排序的算法是把大的元素向上移動(dòng)（氣泡的上升）也可以把最小的元素向 下移動(dòng)（氣泡的下沉）。請給出上浮和下沉過程交替的冒泡排序算法。三、綜合應(yīng)用題（共6題，合計(jì)70分）33 .寫出用Prim算法構(gòu)造圖2最小生成樹的過程。（10分） 圖2無向網(wǎng)34

12、 .關(guān)鍵字序列 A=（36,27,68,33,97,40,81,24,23,90,32,14） 共 12 個(gè)數(shù)據(jù)，哈希表 長為13,采用的哈希函數(shù)為：h（key尸key %13如果采用開放定址的線性探測再散列方 法解決沖突，請構(gòu)造哈希表并求其查找成功時(shí)的平均查找長度。（10分）35 .在如圖3所示的AOEW,求：（10分）（1）完成此工程最少需要的多少天（設(shè)邊上權(quán)值為天數(shù)）。（2）是否存在某項(xiàng)活動(dòng)，當(dāng)其提高速度后能使整個(gè)工程縮短工期。a12=4a1=a8=1圖3 AOE網(wǎng)79需9=4 SJ584136.若有以下四個(gè)作業(yè)同2寸到達(dá)鈾并怔作業(yè)名作業(yè)作業(yè)作業(yè)作業(yè)1234cpuH間（分鐘）a6=312

13、=683_假設(shè)系統(tǒng)中沒有其他作業(yè)，現(xiàn)a宛fl(15給出作業(yè)調(diào)度順序并求出平均作業(yè)周轉(zhuǎn)時(shí)間T,平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間W分）37 .在一個(gè)請求式頁式管理系統(tǒng)中，某程序在內(nèi)存中分配三個(gè)頁面，初始為空 .頁 面走向?yàn)椋? ,3,2, 1,4,3,5,4,3,2,1,5。用學(xué)過的頁面值換算法FIFO算出缺頁次數(shù)。給出執(zhí)行過程中內(nèi)存頁面的變化情況。（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接到棒后跑完全程。試用信號量機(jī)制進(jìn)行描述。 試寫出這四個(gè)并發(fā)進(jìn)程能正確執(zhí)行的程序。（10分）關(guān)系圖第二部分全國碩士研究生入學(xué)統(tǒng)一考試408

14、計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合歷年真題及詳解2012年全國碩士研究生入學(xué)統(tǒng)一考試408計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合真題一、單項(xiàng)選擇題：l40小題。每小題2分，共80分。下列每題給出的四個(gè)選項(xiàng)中， 只有一個(gè)選項(xiàng)是最符合題目要求的。1 .求整數(shù)n (n0)階乘的算法如下，其時(shí)間復(fù)雜度是()。A. O (log2n)B. 0 (n)C. O (nlog2n) 一， 2、D. O ( n )2 .已知操作符包括+、 -、 *、 /、(和)。將中綴表達(dá) 式a+b-a* ( (c+d) /e-f ) +g轉(zhuǎn)換為等價(jià)的后綴表達(dá)式 ab+acd+e/f-*-g+時(shí)，用棧來 存放暫時(shí)還不能確定運(yùn)算次序的操作符。若棧初始時(shí)為空

15、，則轉(zhuǎn)換過程中同時(shí)保存在棧 中的操作符的最大個(gè)數(shù)是()。A. 5B. 7C. 8D. 113.若一棵二叉樹的前序遍歷序列為a, e, b, d, c,后序遍歷序列為b, c, d, e,a,則根結(jié)點(diǎn)的孩子結(jié)點(diǎn)()。A只有eB.有 e、bC.有 e、cD.無法確定4 .若平衡二叉樹的高度為 6,且所有非葉結(jié)點(diǎn)的平衡因子均為1,則該平衡二叉樹的結(jié)點(diǎn)總數(shù)為()。A. 12B. 20C. 32D. 335 .對有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ǔ)有向圖，矩陣中主

16、對角線以下的元素均為零，則關(guān)于該圖拓 撲序列的結(jié)論是()。A.存在，且唯一8 .存在，且不唯一不唯一C.存在，可能不唯一D.無法確定是否存在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)于最小生成樹的敘述中，正確的是（）。I.最小生成樹的代價(jià)唯一n.所有權(quán)值最小的邊一定會(huì)出現(xiàn)在所有的最小生成樹中 m.使用普里姆（P

17、rim）算法從不同頂點(diǎn)開始得到的最小生成樹一定相同IV.使用普里姆算法和克魯斯卡爾（Kruskal ）算法得到的最小生成樹總不相同A僅IB.僅nC.僅 I、mD.僅 n、iv9 .設(shè)有一棵3階B樹，如題9圖所示。刪除關(guān)鍵字78得到一棵新B樹，其最右葉 結(jié)點(diǎn)所含的關(guān)鍵字是（）。題9圖3二叉樹圖A. 60B. 60, 62C. 62, 65D. 6510 .排序過程中，對尚未確定最終位置的所有元素進(jìn)行一遍處理稱為一趟排序。下 列排序方法中，每一趟排序結(jié)束時(shí)都至少能夠確定一個(gè)元素最終位置的方法是（）。I.簡單選擇排序 n .希爾排序田.快速排序iv.堆排V.二路歸并排序A.僅 I、m、IVB.僅 I

18、、n、mC.僅n、m、ivD.僅田、IV、V11 .對同一待排序列分別進(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ī)定語句：unsigned short XC語百）。A.B.C.D.00007FFAH 0000FFFAH FFFF7FFAH FFF

19、FFFFAH14. float類型（即IEEE754單精度浮點(diǎn)數(shù)格式）能表示的最大正整數(shù)是（A.B.C.D.2126-22127-22127-22128-2103104103104int和short類型長度分別為32位和16位，執(zhí)行下列= 65530; unsigned int y=X：得到 y 的機(jī)器數(shù)為（15 .某計(jì)算機(jī)存儲(chǔ)器按字節(jié)編址，采用小端方式存放數(shù)據(jù)。假定編譯器規(guī)定int和short型長度分別為32位和16位，并且數(shù)據(jù)按邊界對齊存儲(chǔ)。某C語言程序段如下：若record變量的首地址為 0xC008,則地址0xC008中內(nèi)容及record.c 的地址分別 為（）。A. 0x00、0xC

20、00DB. 0x00、0xCOOEC. 0x11、0xC00DD. 0x11、0xC00E16 .下列關(guān)于閃存（FlashMemory）的敘述中，錯(cuò)誤的是（）。A.信息可讀可寫，并且讀、寫速度一樣快17 存儲(chǔ)元由MOST組成，是一種半導(dǎo)體存儲(chǔ)器C.掉電后信息不丟失，是一種非易失性存儲(chǔ)器D.采用隨機(jī)訪問方式，可替代計(jì)算機(jī)外部存儲(chǔ)器17.假設(shè)某計(jì)算機(jī)按字編址，Cache有4個(gè)行，Cache和主存之間交換的塊大小為l個(gè)字。若Cache的內(nèi)容初始為空，采用 2路組相聯(lián)映射方式和 LRU替換算法，當(dāng)訪問的 主存地址依次為 0, 4, 8, 2, 0, 6, 8, 6, 4, 8時(shí)，命中Cache的次數(shù)是

21、（）。A. 1B. 2C. 3D. 418 .某計(jì)算機(jī)的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直 接編碼法，共有33個(gè)微命令，構(gòu)成5個(gè)互斥類，分別包含7、3、12、5和6個(gè)微命令, 則操作控制字段至少有（）。A. 5位B. 6位C. 15 位D. 33 位19 .某同步總線的時(shí)鐘頻率為100MHz,寬度為32位，地址/數(shù)據(jù)線復(fù)用，每傳輸 一個(gè)地址或數(shù)據(jù)占用一個(gè)時(shí)鐘周期。若該總線支持突發(fā)（猝發(fā)）傳輸方式，則一次“主 存寫”總線事務(wù)傳輸128位數(shù)據(jù)所需要的時(shí)間至少是（）。）。A. 20nsB. 40nsC. 50nsD. 80ns20 .下列關(guān)于USB總線特性的描述中，錯(cuò)誤的是（

22、）。A.可實(shí)現(xiàn)外設(shè)的即插即用和熱插拔B.可通過級聯(lián)方式連接多臺(tái)外設(shè)C.是一種通信總線，可連接不同外設(shè)D.同時(shí)可傳輸2位數(shù)據(jù)，數(shù)據(jù)傳輸率高21 .下列選項(xiàng)中，在I/O總線的數(shù)據(jù)線上傳輸?shù)男畔ǎǎ?。I. I/O接口中的命令字n. I/O接口中的狀態(tài)字 m.中斷類型號A.僅 I、nB.僅 I、mC.僅n、田d. I 、 n 、田22.響應(yīng)外部中斷的過程中，中斷隱指令完成的操作，除保護(hù)斷點(diǎn)外，還包括（）I.開關(guān)中斷 n.保存通用寄存器的內(nèi)容田.形成中斷服務(wù)程序入口地址并送PCA.僅 I、nB.僅 i、mC.僅n、田d. i 、 n 、田23.下列選項(xiàng)中，不可能在用戶態(tài)發(fā)生的事件是（）。A系統(tǒng)調(diào)用B

23、.外部中斷C.進(jìn)程切換D.缺頁24.中斷處理和子程序調(diào)用都需要壓棧以保護(hù)現(xiàn)場，中斷處理一定會(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.用戶級I /O軟件、設(shè)備無關(guān)軟件、設(shè)備驅(qū)動(dòng)程序、中斷處理程序B.用戶級I /O軟件、設(shè)備無關(guān)軟

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

25、2, Pl , P0, P3, P4D. P3, P4, P2, Pl , P0P028.若一個(gè)用戶進(jìn)程通過read系統(tǒng)調(diào)用讀取一個(gè)磁盤文件中的數(shù)據(jù)，則下列關(guān)于 此過程的敘述中，正確的是（）。I .若該文件的數(shù)據(jù)不在內(nèi)存，則該進(jìn)程進(jìn)入睡眠等待狀態(tài)；n .請求 read系統(tǒng) 調(diào)用會(huì)導(dǎo)致CPU從用戶態(tài)切換到核心態(tài)；m. read系統(tǒng)調(diào)用的參數(shù)應(yī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ì)算60ms, I/O 80ms,計(jì)算20ms； P2:計(jì)算120m

26、s, I/O 40ms ，計(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)用完成并返回用戶態(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)級線程和用戶級線程的切換都需

27、要內(nèi)核的支持D.同一進(jìn)程中的各個(gè)線程擁有各自不同的地址空間32 .下列選項(xiàng)中，不能改善磁盤設(shè)備I/O性能的是（）。A.重排I/0請求次序B.在一個(gè)磁盤上設(shè)置多個(gè)分區(qū)C.預(yù)讀和滯后寫D.優(yōu)化文件物理塊的分布33 .在TC% IP體系結(jié)構(gòu)中，直接為ICMP提供服務(wù)的協(xié)議是（）。A. PPP B. IP C. UDP D. TCP34 .在物理層接口特性中，用于描述完成每種功能的事件發(fā)生順序的是（）。A.機(jī)械特性 B.功能特性 C.過程特性 D.電氣特性 35.以太網(wǎng)的MAO議提供的是（）。A無連接不可靠服務(wù)B.無連接可靠服務(wù)C.有連接不可靠服務(wù)D.有連接可靠服務(wù)36.兩臺(tái)主機(jī)之間的數(shù)據(jù)鏈路層采用后

28、退N幀協(xié)議（GBN傳輸數(shù)據(jù)，數(shù)據(jù)傳輸速率為16kbps ,單向傳播時(shí)延為270ms數(shù)據(jù)幀長度范圍是128512字節(jié)，接收方總是 以與數(shù)據(jù)幀等長的幀進(jìn)行確認(rèn)。為使信道利用率達(dá)到最高，幀序號的比特?cái)?shù)至少為 （ ）。A. 5B. 4C. 3 D. 237 37.下列關(guān)于IP路由器功能的描述中，正確的是（）。I.運(yùn)行路由協(xié)議，設(shè)置路由表；n.監(jiān)測到擁塞時(shí)，合理丟棄IP分組；田.對收到的IP分組頭進(jìn)行差錯(cuò)校驗(yàn)，確保傳輸?shù)?IP分組不丟失；IV.根據(jù)收到的IP分組 的目的IP地址，將其轉(zhuǎn)發(fā)到合適的輸出線路上。A.僅田、IVB.僅 I、n、mC.僅 i、n、iv d. i、n、m、iv 38. ARP協(xié)議的

29、功能是（）。A.根據(jù)IP地址查詢MAC4址B.根據(jù)MAO址查詢IP地址C.根據(jù)域名查詢IP地址D.根據(jù)IP地址查詢域名39 .某主機(jī)的IP地址為180.80.77.55 ,子網(wǎng)掩碼為 255.255.252.0。若該主機(jī)向 其所在子網(wǎng)發(fā)送廣播分組，則目的地址可以是（）。A. 180.80.76.0B. 180.80.76.255C. 180.80.77.255D. 180.80.79.25540 .若用戶l與用戶2之間發(fā)送和接收電子郵件的過程如題40圖所示，則圖中、階段分別使用的應(yīng)用層協(xié)議可以是()。題40圖電子郵件發(fā)送接收示意圖A. SMTP SMTP SMTPB. POP3 SMTP PO

30、P3C. POP3 SMTP SMTPD. SMTP SMTP POP3二、綜合應(yīng)用題：41-47 小題。共70分。41 . (10分)設(shè)有6個(gè)有序表 A B、C、R E、F,分別含有10、35、40、50、60 和200個(gè)數(shù)據(jù)元素，各表中元素按升序排列。要求通過 5次兩兩合并，將6個(gè)表最終合 并成1個(gè)升序表，并在最壞情況下比較的總次數(shù)達(dá)到最小。請回答下列問題。(1)給出完整的合并過程，并求出最壞情況下比較的總次數(shù)。(2)根據(jù)你的合并過程，描述n (n2)個(gè)不等長升序表的合并策略，并說明理由。42 . (13分)假定采用帶頭結(jié)點(diǎn)的單鏈表保存單詞，當(dāng)兩個(gè)單詞有相同的后綴時(shí)， 則可共享相同的后綴存

31、儲(chǔ)空間。例如，“ loading ”和“ being ”的存儲(chǔ)映像如題42圖所示。題42圖存儲(chǔ)映像示意圖設(shè)strl和str2分別指向兩個(gè)單詞所在單鏈表的頭結(jié)點(diǎn)，鏈表結(jié)點(diǎn)結(jié)構(gòu)為data ,next,請?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語言描述算法，關(guān)鍵之處給出注釋。(3)說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度。43. (11分)假定某計(jì)算機(jī)的 CPUfe頻為80MHz CPI為4,并且平均每條指令訪 存1.5次，主存與Cache之間交

32、換的塊大小為 168, Cache的命中率為99%,存儲(chǔ)器總 線寬度為32位。請回答下列問題。(1)該計(jì)算機(jī)的 MIPS數(shù)是多少？平均每秒Cache缺失的次數(shù)是多少？在不考慮DMA 傳送的情況下，主存帶寬至少達(dá)到多少才能滿足CPU勺訪存要求？(2)假定在Cache缺失的情況下訪問主存時(shí)，存在 0.0005 %的缺頁率，則CPUff 均每秒產(chǎn)生多少次缺頁異常？若頁面大小為4KB,每次缺頁都需要訪問磁盤，訪問磁盤時(shí) DMA專送采用周期挪用方式， 磁盤I/O接口的數(shù)據(jù)緩沖寄存器為 32位，則磁盤I/O接 口平均每秒發(fā)出的DMA 青求次數(shù)至少是多少？(3) CPUffl DMA空制器同時(shí)要求使用存儲(chǔ)器

33、總線時(shí)，哪個(gè)優(yōu)先級更高？為什么？(4)為了提高性能，主存采用 4體交叉存儲(chǔ)模式，工作時(shí)每l/4個(gè)存儲(chǔ)周期啟動(dòng) 一個(gè)體。若每個(gè)體的存儲(chǔ)周期為50ns,則該主存能提供的最大帶寬是多少 ？44. (12分)某16位計(jì)算機(jī)中，帶符號整數(shù)用補(bǔ)碼表示， 數(shù)據(jù)Cache和指令Cache 分離。題44表給出了指令系統(tǒng)中部分指令格式，其中 Rs和Rd表示寄存器，memi示存 儲(chǔ)單元地址，(X)表示寄存器X或存儲(chǔ)單元X的內(nèi)容。表指令系統(tǒng)中部分指令格式名稱指令的匯編格式指令功能 1加法指令A(yù)DD R Rd(Rs) + (Rd) f Rd算術(shù)/邏輯左移SHLR d2* (Rd) f Rd 算術(shù)右移SHRR d(Rd)

34、 /2f Rd取數(shù)指令LOAD RD mem(merm f Rd存數(shù)指令STORE Rs mem(Rs) f mem該計(jì)算機(jī)采用5段流水方式執(zhí)行指令，各流水段分別是取指(IF)、譯碼/讀寄存 器(ID)、執(zhí)行/計(jì)算有效地址(EX)、訪問存儲(chǔ)器(M)和結(jié)果寫回寄存器(WB , 流水線采用“按序發(fā)射，按序完成”方式，沒有采用轉(zhuǎn)發(fā)技術(shù)處理數(shù)據(jù)相關(guān)，并且同一 個(gè)寄存器的讀和寫操作不能在同一個(gè)時(shí)鐘周期內(nèi)進(jìn)行。請回答下列問題。(1)若int型變量x的值為-513,存放在寄存器Rl中，則執(zhí)行指令 SHRRl”后, Rl的內(nèi)容是多少？(用十六進(jìn)制表示)(2)若某個(gè)時(shí)間段中，有連續(xù)的 4條指令進(jìn)入流水線，在其執(zhí)

35、行過程中沒有發(fā)生任何阻塞，則執(zhí)行這4條指令所需的時(shí)鐘周期數(shù)為多少 ？(3)若高級語言程序中某賦值語句為x = a+b, x、a和b均為int型變量，它們的存儲(chǔ)單元地址分別表示為x、聞和回。該語句對應(yīng)的指令序列及其在指令流水線中 的執(zhí)行過程如題44圖所示。則這4條指令執(zhí)行過程中，I 3的ID段和14的IF段被阻塞 的原因各是什么？(4)若高級語言程序中某賦值語句為x = 2*x+a, x和a均為unsigned int 類型變量，它們的存儲(chǔ)單元地址分別表示為x、聞，則執(zhí)行這條語句至少需要多少個(gè)時(shí)鐘周期？要求模仿題44圖畫出這條語句對應(yīng)的指令序列及其在流水線中的執(zhí)行過程示意圖。45. (7分)某請

36、求分頁系統(tǒng)的局部頁面置換策略如下：系統(tǒng)從0時(shí)刻開始掃描，每隔5個(gè)時(shí)間單位掃描一輪駐留集(掃描時(shí)間忽略不計(jì))，本輪沒有被訪問過的頁框?qū)?被系統(tǒng)回收，并放入到空閑頁框鏈尾，其中內(nèi)容在下一次被分配之前不被清空。當(dāng)發(fā)生 缺頁時(shí)，如果該頁曾被使用過且還在空閑頁框鏈表中，則重新放回進(jìn)程的駐留集中；否 則，從空閑頁框鏈表頭部取出一個(gè)頁框。假設(shè)不考慮其他進(jìn)程的影響和系統(tǒng)開銷，初始 時(shí)進(jìn)程駐留集為空。目前系統(tǒng)空閑頁框鏈表中頁框號依次為32、15、21、41。進(jìn)程P依次訪問的 虛擬頁號，訪問時(shí)刻 是：1, 1、3, 2、0, 4、0, 6、1, 11、0, 13、2, 14。請回答下列問題。(1)訪問0, 4時(shí)，

37、對應(yīng)的頁框號是什么？(2)訪問1, 11時(shí)，對應(yīng)的頁框號是什么？說明理由。(3)訪問2, 14時(shí)，對應(yīng)的頁框號是什么？說明理由。(4)該策略是否適合于時(shí)間局部性好的程序 ？說明理由。46. (8分)某文件系統(tǒng)空間的最大容量為 4TB (1T= 24),以磁盤塊為基本分配單位，磁盤塊大小為lKBo文件控制塊(FCB包含一個(gè)512B的索引表區(qū)。請回答下列 問題。(1)假設(shè)索引表區(qū)僅采用直接索引結(jié)構(gòu)，索引表區(qū)存放文件占用的磁盤塊號。索引表項(xiàng)中塊號最少占多少字節(jié) ？可支持的單個(gè)文件最大長度是多少字節(jié) ？(2)假設(shè)索引表區(qū)采用如下結(jié)構(gòu)：第 07字節(jié)采用 起始塊號，塊數(shù) 格式表示文 件創(chuàng)建時(shí)預(yù)分配的連續(xù)存

38、儲(chǔ)空間，其中起始塊號占 6B,塊數(shù)占2B;剩余504字節(jié)采用 直接索引結(jié)構(gòu)，一個(gè)索引項(xiàng)占 6B,則可支持的單個(gè)文件最大長度是多少字節(jié) ？為了使單 個(gè)文件的長度達(dá)到最大，請指出起始塊號和塊數(shù)分別所占字節(jié)數(shù)的合理值并說明理由。47. （9分）主機(jī)H通過快速以太網(wǎng)連接Internet , IP地址為192.168.0.8 ,服務(wù) 器S的IP地址為211.68.71.80 。H與S使用TCP信時(shí)，在 H上捕獲的其中5個(gè)IP分 組如題47-a表所示。題47-a表Sfflj七IP分組的前40字節(jié)內(nèi)容（十六進(jìn)制）1019b4000 8006lde8 coa80008 d3444750 0bd91388 84

39、6b41c5 000000005db00000200004000 31066e83 3d3444750 cOa8000813880bd9 e0599fef 846b41c6 6701216d037e100003019c4000 8006ldef cOa80008 d3444750 bd913888 46b41c6e 0599ff05 01043802 b3200004019d4000 80061dde cOa80008 d34447500bd91388 846b4lc6 e0599ff0c655000053106067a d3444750 cOa8000813880bd9 e0599ff0 8

40、46b41d6 501016d057d20000請回答下列問題。（1）題47-a表中的IP分組中，哪幾個(gè)是由H發(fā)送的？哪幾個(gè)完成了 TCP連接建立 過程？哪幾個(gè)在通過快速以太網(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)過了多少個(gè)路由器？題47-b表來自S發(fā)出的上組4006eCad d3444750 ca760106 1388a108 e0599ff0 846b41d6 501016dO b7d60000注：IP分組頭和TCP段頭結(jié)構(gòu)分別如題4

41、7-a圖、題47-b圖所示:版本頭部長 度服務(wù)類型 （8-15）總長度(16-31 )標(biāo)識(shí)標(biāo)志片偏移生存時(shí)（TTL）協(xié)議頭部校驗(yàn)和源IP地址目的IP地址題47-a圖IP分組頭結(jié)構(gòu)源端口（ 0-15）目的端口 （ 16-31 ）序號（seq)確認(rèn)號（ack）UAPRSF數(shù)據(jù)偏移保留RCSSYI窗口GKHTNN校驗(yàn)和1緊急指針選項(xiàng)（長度可艾）填充題47-b圖TCP段頭結(jié)構(gòu)2012年全國碩士研究生入學(xué)統(tǒng)一考試408計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合真題及詳解一、單項(xiàng)選擇題：l40小題。每小題2分，共80分。下列每題給出的四個(gè)選項(xiàng)中， 只有一個(gè)選項(xiàng)是最符合題目要求的。1 .求整數(shù)n (n0)階乘的算法如下，其時(shí)間

42、復(fù)雜度是()。A. O (log2n)B. 0 (n)C. O (nlog2n)一， 2、D. O ( n )【答案】Bo【解析】設(shè)fact (n)的運(yùn)行時(shí)間函數(shù)是 T (n)。該函數(shù)中語句的運(yùn)行時(shí)間是 0 (1),語句的運(yùn)行時(shí)間是 T (n-1) +O (1),其 中O (1)為乘法運(yùn)算的時(shí)間。因此，當(dāng) n1 時(shí)，T (n) =T (n-1 ) +O (1)。則，T (n) = O (1) +T (n-1 )= 2XO (1) +T (n-2) = (n-1) x O (1) +T (1) =nx O (1)=O (n)即fact (n)的時(shí)間復(fù)雜度為 O (n)。2 .已知操作符包括+、

43、-、 *、 /、(和)。將中綴表達(dá) 式a+b-a* ( (c+d) /e-f ) +g轉(zhuǎn)換為等價(jià)的后綴表達(dá)式 ab+acd+e/f-*-g+時(shí)，用棧來 存放暫時(shí)還不能確定運(yùn)算次序的操作符。若棧初始時(shí)為空，則轉(zhuǎn)換過程中同時(shí)保存在棧 中的操作符的最大個(gè)數(shù)是()。A. 5B. 7C. 8D. 11【答案】Ao【解析】基本思想是：采用運(yùn)算符棧是為了比較運(yùn)算符的優(yōu)先級，所有運(yùn)算符必須 進(jìn)棧。只將大于棧頂元素優(yōu)先級的運(yùn)算符直接進(jìn)棧，否則需要退棧棧頂運(yùn)算符(先出棧 的運(yùn)算符先計(jì)算，同優(yōu)先級的運(yùn)算符在棧中的先計(jì)算)。表達(dá)式a+b-a* ( (c+d) /e-f )+g產(chǎn)生后綴表達(dá)式的過程如下表所列：當(dāng)前字符運(yùn)

44、算符棧內(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)-* (ab+acd+與其配對的左括號及其前所有運(yùn) 算符出棧/-* (/ab+acd+進(jìn)棧e-* (/ab+acd+e-* (-ab+acd+e/“-”的優(yōu)先級小于棧頂兀素“/”，則出棧，“-”進(jìn) 棧f-* (

45、-ab+acd+e/f)-*ab+acd+e/f-與其配對的左括號及其前所有運(yùn) 算符出棧+-ab+acd+e/ f-*“+”的優(yōu)先級小于棧頂兀素“*”， 則“出棧+ab+acd+e/ f-*-“ +”與棧頂兀素“-”的優(yōu)先級 相同，則“-”出棧，“ +”進(jìn)棧g+ab+acd+e/ f-*-gab+acd+e/ f-*-g+全部出棧通過上表可以看出，顯然轉(zhuǎn)換過程中同時(shí)保存在棧中的操作符的最大個(gè)數(shù)是5。3 .若一棵二叉樹的前序遍歷序列為 a, e, b, d, c,后序遍歷序列為b, c, d, e, a,則根結(jié)點(diǎn)的孩子結(jié)點(diǎn)（）。A.只有e8 .有 e、bC.有 e、cD.無法確定【答案】Ao【解析】由題目可知，若一棵二叉樹的前序遍歷序列為a, e, b, d, c,后序遍歷序列為b, c, d, e, a,其中a為這棵二叉樹的根結(jié)點(diǎn)，接下來，在前序遍歷的第二個(gè) 結(jié)點(diǎn)為e,而后序遍歷的倒數(shù)第二個(gè)結(jié)點(diǎn)為 e,說明a的孩子結(jié)點(diǎn)只有e。4 .若平衡二叉樹的高度為 6,且所有非葉結(jié)點(diǎn)的平衡因子均為 1,則該平衡二叉樹 的結(jié)點(diǎn)總數(shù)為（）。A. 12B. 20C. 32D. 33【答案】Bo【解析】本題題目的實(shí)際問題是，具有 6層結(jié)點(diǎn)的平衡二叉樹含有最少的結(jié)點(diǎn)數(shù)是 多少。Nh表示深度為h的平衡二叉樹中含有的最少結(jié)點(diǎn)數(shù)，有 N=0, N = 1, Nb = 2 N=N-i+N-2+1由此可