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

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

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

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

4、復雜度為 O（n2）,表明該算法（）oA問題規(guī)模是n2B.執(zhí)行時間等于n2C.執(zhí)行時間與n2成正比D.問題規(guī)模與n2成正比2設(shè)線性表有n個元素，以下操作中，（）在順序表上實現(xiàn)比在鏈表上實現(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 .已知一個棧的進棧序列是1, 2, 3, ,n,其輸出序列是p1,p2,，p%若p1=n,則pi的值（）。A iB. n-iC. n-i+1D.不確定5.對稀疏矩陣進行壓縮存儲，常用的兩種方法是（）。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個結(jié)點，其中葉子結(jié)點的個數(shù)是（）。A 250B. 500C. 505D. 5019 .線索二叉樹是一種（）結(jié)構(gòu)。A.邏輯10 邏輯和存儲C.物理D.線性11 .以數(shù)據(jù)集2 , 5, 7, 9, 13為權(quán)值構(gòu)造一棵哈夫曼樹，則其帶權(quán)路徑長為（）A 78B. 80C. 81D. 7911.一個有向圖的鄰接表存儲如圖1所示，現(xiàn)按深度優(yōu)先搜索遍歷，從頂點 必出發(fā),所得到的頂點序列是（）。可能不存在D.13 .若一個有向圖中的頂點不能排成一個拓撲序列，則可斷定該有

7、向圖（）。A是個有根有向圖B.是個強連通圖C.含有多個入度為0的頂點D.含有頂點數(shù)目大于1的強連通分量14 .順序查找法適合于存儲結(jié)構(gòu)為（）的線性表。A哈希存儲B.索引存儲C.壓縮存儲D.順序存儲或鏈式存儲15.在含有27個結(jié)點的二叉樹排序樹上，查找關(guān)鍵字為35的結(jié)點，則依次比較的關(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)鍵活動不按

9、期完成就會影響整個工程的完成時間B.任何一個關(guān)鍵活動提前完成，將使整個工程提前完成C.所有關(guān)鍵活動都提前完成，則整個工程提前完成D.某些關(guān)鍵活動若提前完成，將使整個工程提前完成21 .下列選項中，（）不是操作系統(tǒng)關(guān)心的主要問題。A.管理計算機裸機B.設(shè)計、提供用戶程序與計算機硬件系統(tǒng)的界面C.管理計算機系統(tǒng)資源D.高級程序設(shè)計語言的編譯器22 .系統(tǒng)功能調(diào)用是（）。A.用戶編寫的一個子程序B.高級語言中的庫程序C.操作系統(tǒng)中的一條命令D.操作系統(tǒng)向用戶程序提供的接口23 .在處理機管理中，當（）時，進程從阻塞狀態(tài)變?yōu)榫途w狀態(tài)。A.進程被調(diào)度程序選中B.等待某一事件發(fā)生C.等待的事件發(fā)生D.時間

10、片用完24 .高級調(diào)度是（）。A進程調(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í)行的進程太多C.進程推進順序非法D.以上3個因素全是27 .在下述存儲管理方案中，（）管理方式要求作業(yè)占用連續(xù)的存儲空間。A分區(qū)B.分頁C.分段D.段頁式28 .操作系統(tǒng)中對數(shù)據(jù)進行管理的部分叫做（）。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)中，對于下列文件

11、物理結(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é)點的 hc單鏈表存放， 設(shè)計一個就地算法，將其拆分為兩個線性表，使得： A= a1,a2,，an,B= b1, b2, bn32 .冒泡排序的算法是把大的元素向上移動（氣泡的上升）也可以把最小的元素向 下移動（氣泡的下沉）。請給出上浮和下沉過程交替的冒泡排序算法。三、綜合應(yīng)用題（共6題，合計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 個數(shù)據(jù)，哈希表 長為13,采用的哈希函數(shù)為：h（key尸key %13如果采用開放定址的線性探測再散列方 法解決沖突，請構(gòu)造哈希表并求其查找成功時的平均查找長度。（10分）35 .在如圖3所示的AOEW,求：（10分）（1）完成此工程最少需要的多少天（設(shè)邊上權(quán)值為天數(shù)）。（2）是否存在某項活動，當其提高速度后能使整個工程縮短工期。a12=4a1=a8=1圖3 AOE網(wǎng)79需9=4 SJ584136.若有以下四個作業(yè)同2寸到達鈾并怔作業(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)時間T,平均帶權(quán)作業(yè)周轉(zhuǎn)時間W分）37 .在一個請求式頁式管理系統(tǒng)中，某程序在內(nèi)存中分配三個頁面，初始為空 .頁 面走向為：4 ,3,2, 1,4,3,5,4,3,2,1,5。用學過的頁面值換算法FIFO算出缺頁次數(shù)。給出執(zhí)行過程中內(nèi)存頁面的變化情況。（15分）38 .在4*100m接力賽中，4個運動員之間存在如下關(guān)系圖 4,運動員1跑到終點把 接力棒交給運動員2,，運動員4接到棒后跑完全程。試用信號量機制進行描述。 試寫出這四個并發(fā)進程能正確執(zhí)行的程序。（10分）關(guān)系圖第二部分全國碩士研究生入學統(tǒng)一考試408

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

15、，則轉(zhuǎn)換過程中同時保存在棧 中的操作符的最大個數(shù)是()。A. 5B. 7C. 8D. 113.若一棵二叉樹的前序遍歷序列為a, e, b, d, c,后序遍歷序列為b, c, d, e,a,則根結(jié)點的孩子結(jié)點()。A只有eB.有 e、bC.有 e、cD.無法確定4 .若平衡二叉樹的高度為 6,且所有非葉結(jié)點的平衡因子均為1,則該平衡二叉樹的結(jié)點總數(shù)為()。A. 12B. 20C. 32D. 335 .對有2個頂點e條邊且使用鄰接表存儲的有向圖進行廣度優(yōu)先遍歷，其算法時 間復雜度是()。A. 0 (n)B. 0 (e)C. O (n+e)D. O (nXe)6 .若用鄰接矩陣存儲有向圖，矩陣中主

16、對角線以下的元素均為零，則關(guān)于該圖拓 撲序列的結(jié)論是()。A.存在，且唯一8 .存在，且不唯一不唯一C.存在，可能不唯一D.無法確定是否存在7 .有向帶權(quán)圖如題7圖所示，若采用迪杰斯特拉（Dijkstra ）算法求從源點a到 其他各頂點的最短路徑，則得到的第一條最短路徑的目標頂點是b,第二條最短路徑的目標頂點是c,后續(xù)得到的其余各最短路徑的目標頂點依次是（）。題7圖有向帶權(quán)圖A. d, e, fB. e, d, fC. f, d, eD. f, e, d8 .下列關(guān)于最小生成樹的敘述中，正確的是（）。I.最小生成樹的代價唯一n.所有權(quán)值最小的邊一定會出現(xiàn)在所有的最小生成樹中 m.使用普里姆（P

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

18、、n、mC.僅n、m、ivD.僅田、IV、V11 .對同一待排序列分別進行折半插入排序和直接插入排序，兩者之間可能的不同 之處是（）。A.排序的總趟數(shù)B.元素的移動次數(shù)C.使用輔助空間的數(shù)量D.元素之間的比較次數(shù)12 .假定基準程序A在某計算機上的運行時間為l00秒，其中90秒為CPU時間， 其余為I/O時間。若CPU1度提高50%, I/O速度不變，則運行基準程序 A所耗費的時 同是（）。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單精度浮點數(shù)格式）能表示的最大正整數(shù)是（A.B.C.D.2126-22127-22127-22128-2103104103104int和short類型長度分別為32位和16位，執(zhí)行下列= 65530; unsigned int y=X：得到 y 的機器數(shù)為（15 .某計算機存儲器按字節(jié)編址，采用小端方式存放數(shù)據(jù)。假定編譯器規(guī)定int和short型長度分別為32位和16位，并且數(shù)據(jù)按邊界對齊存儲。某C語言程序段如下：若record變量的首地址為 0xC008,則地址0xC008中內(nèi)容及record.c 的地址分別 為（）。A. 0x00、0xC

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

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

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

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

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

25、2, Pl , P0, P3, P4D. P3, P4, P2, Pl , P0P028.若一個用戶進程通過read系統(tǒng)調(diào)用讀取一個磁盤文件中的數(shù)據(jù)，則下列關(guān)于 此過程的敘述中，正確的是（）。I .若該文件的數(shù)據(jù)不在內(nèi)存，則該進程進入睡眠等待狀態(tài)；n .請求 read系統(tǒng) 調(dià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. 一個多道批處理系統(tǒng)中僅有 Pl和P2兩個作業(yè)，P2比Pl晚5ms到達。它們的 計算和I/0操作順序如下：P1:計算60ms, I/O 80ms,計算20ms； P2:計算120m

26、s, I/O 40ms ，計算40ms若不考慮調(diào)度和切換時間，則完成兩個作業(yè)需要的時間最 少是（）。A. 240msB. 260msC. 340msD. 360ms30 .若某單處理器多進程系統(tǒng)中有多個就緒態(tài)進程，則下列關(guān)于處理機調(diào)度的敘述 中，錯誤的是（）。A.在進程結(jié)束時能進行處理機調(diào)度B.創(chuàng)建新進程后能進行處理機調(diào)度C.在進程處于臨界區(qū)時不能進行處理機調(diào)度D.在系統(tǒng)調(diào)用完成并返回用戶態(tài)時能進行處理機調(diào)度31 .下列關(guān)于進程和線程的敘述中，正確的是（）。A.不管系統(tǒng)是否支持線程，進程都是資源分配的基本單位B.線程是資源分配的基本單位，進程是調(diào)度的基本單位C.系統(tǒng)級線程和用戶級線程的切換都需

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

28、退N幀協(xié)議（GBN傳輸數(shù)據(jù)，數(shù)據(jù)傳輸速率為16kbps ,單向傳播時延為270ms數(shù)據(jù)幀長度范圍是128512字節(jié)，接收方總是 以與數(shù)據(jù)幀等長的幀進行確認。為使信道利用率達到最高，幀序號的比特數(shù)至少為 （ ）。A. 5B. 4C. 3 D. 237 37.下列關(guān)于IP路由器功能的描述中，正確的是（）。I.運行路由協(xié)議，設(shè)置路由表；n.監(jiān)測到擁塞時，合理丟棄IP分組；田.對收到的IP分組頭進行差錯校驗，確保傳輸?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 .某主機的IP地址為180.80.77.55 ,子網(wǎng)掩碼為 255.255.252.0。若該主機向 其所在子網(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個有序表 A B、C、R E、F,分別含有10、35、40、50、60 和200個數(shù)據(jù)元素，各表中元素按升序排列。要求通過 5次兩兩合并，將6個表最終合 并成1個升序表，并在最壞情況下比較的總次數(shù)達到最小。請回答下列問題。(1)給出完整的合并過程，并求出最壞情況下比較的總次數(shù)。(2)根據(jù)你的合并過程，描述n (n2)個不等長升序表的合并策略，并說明理由。42 . (13分)假定采用帶頭結(jié)點的單鏈表保存單詞，當兩個單詞有相同的后綴時， 則可共享相同的后綴存

31、儲空間。例如，“ loading ”和“ being ”的存儲映像如題42圖所示。題42圖存儲映像示意圖設(shè)strl和str2分別指向兩個單詞所在單鏈表的頭結(jié)點，鏈表結(jié)點結(jié)構(gòu)為data ,next,請設(shè)計一個時間上盡可能高效的算法，找出由 strl和str2所指的兩個鏈表共 同后綴的起始位置(如圖中字符 i所在結(jié)點的位置p)。要求：(1)給出算法的基本設(shè)計思想。(2)根據(jù)設(shè)計思想，采用 C或C+堿JAVA語言描述算法，關(guān)鍵之處給出注釋。(3)說明你所設(shè)計算法的時間復雜度。43. (11分)假定某計算機的 CPUfe頻為80MHz CPI為4,并且平均每條指令訪 存1.5次，主存與Cache之間交

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

33、總線時，哪個優(yōu)先級更高？為什么？(4)為了提高性能，主存采用 4體交叉存儲模式，工作時每l/4個存儲周期啟動 一個體。若每個體的存儲周期為50ns,則該主存能提供的最大帶寬是多少 ？44. (12分)某16位計算機中，帶符號整數(shù)用補碼表示， 數(shù)據(jù)Cache和指令Cache 分離。題44表給出了指令系統(tǒng)中部分指令格式，其中 Rs和Rd表示寄存器，memi示存 儲單元地址，(X)表示寄存器X或存儲單元X的內(nèi)容。表指令系統(tǒng)中部分指令格式名稱指令的匯編格式指令功能 1加法指令ADD 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該計算機采用5段流水方式執(zhí)行指令，各流水段分別是取指(IF)、譯碼/讀寄存 器(ID)、執(zhí)行/計算有效地址(EX)、訪問存儲器(M)和結(jié)果寫回寄存器(WB , 流水線采用“按序發(fā)射，按序完成”方式，沒有采用轉(zhuǎn)發(fā)技術(shù)處理數(shù)據(jù)相關(guān)，并且同一 個寄存器的讀和寫操作不能在同一個時鐘周期內(nèi)進行。請回答下列問題。(1)若int型變量x的值為-513,存放在寄存器Rl中，則執(zhí)行指令 SHRRl”后, Rl的內(nèi)容是多少？(用十六進制表示)(2)若某個時間段中，有連續(xù)的 4條指令進入流水線，在其執(zhí)

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

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

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

38、儲空間，其中起始塊號占 6B,塊數(shù)占2B;剩余504字節(jié)采用 直接索引結(jié)構(gòu)，一個索引項占 6B,則可支持的單個文件最大長度是多少字節(jié) ？為了使單 個文件的長度達到最大，請指出起始塊號和塊數(shù)分別所占字節(jié)數(shù)的合理值并說明理由。47. （9分）主機H通過快速以太網(wǎng)連接Internet , IP地址為192.168.0.8 ,服務(wù) 器S的IP地址為211.68.71.80 。H與S使用TCP信時，在 H上捕獲的其中5個IP分 組如題47-a表所示。題47-a表Sfflj七IP分組的前40字節(jié)內(nèi)容（十六進制）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分組中，哪幾個是由H發(fā)送的？哪幾個完成了 TCP連接建立 過程？哪幾個在通過快速以太網(wǎng)傳輸時進行了填充？（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分組到達H時經(jīng)過了多少個路由器？題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 )標識標志片偏移生存時（TTL）協(xié)議頭部校驗和源IP地址目的IP地址題47-a圖IP分組頭結(jié)構(gòu)源端口（ 0-15）目的端口 （ 16-31 ）序號（seq)確認號（ack）UAPRSF數(shù)據(jù)偏移保留RCSSYI窗口GKHTNN校驗和1緊急指針選項（長度可艾）填充題47-b圖TCP段頭結(jié)構(gòu)2012年全國碩士研究生入學統(tǒng)一考試408計算機學科專業(yè)基礎(chǔ)綜合真題及詳解一、單項選擇題：l40小題。每小題2分，共80分。下列每題給出的四個選項中， 只有一個選項是最符合題目要求的。1 .求整數(shù)n (n0)階乘的算法如下，其時間

42、復雜度是()。A. O (log2n)B. 0 (n)C. O (nlog2n)一， 2、D. O ( n )【答案】Bo【解析】設(shè)fact (n)的運行時間函數(shù)是 T (n)。該函數(shù)中語句的運行時間是 0 (1),語句的運行時間是 T (n-1) +O (1),其 中O (1)為乘法運算的時間。因此，當 n1 時，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)的時間復雜度為 O (n)。2 .已知操作符包括+、

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

44、算符棧內(nèi) 容后綴表達式說明a+“+”進棧b+ab-ab+“-”與棧頂兀素“ +”的優(yōu)先級 相同，則“ +”出棧，“-”進棧a-ab+a*-*ab+a“* ”的優(yōu)先級大于棧頂兀素“-”， 則“進棧(-* (ab+a“(”對它之前后的運算符起隔 離作用(-* (ab+a“（”對它之前后的運算符起隔 離作用-* (ab+ac+-* ( ( +ab+ac“+”進棧d-* ( ( +ab+acd)-* (ab+acd+與其配對的左括號及其前所有運 算符出棧/-* (/ab+acd+進棧e-* (/ab+acd+e-* (-ab+acd+e/“-”的優(yōu)先級小于棧頂兀素“/”，則出棧，“-”進 棧f-* (

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