沈陽農(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)）考研真題第二部分全國(guó)碩士研究生入學(xué)統(tǒng)一考試408計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合歷年真題及詳解2012年全國(guó)碩士研究生入學(xué)統(tǒng)一考試408計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合真2012年全國(guó)碩士研究生入學(xué)統(tǒng)一考試408

2、計(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ǔ)綜合真題及詳解說明：沈陽師范大學(xué)2012年之前參加全國(guó)統(tǒng)考408計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合，2013年開始自主命題，科目改為867計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合（數(shù)據(jù)結(jié)

3、構(gòu)、操作系統(tǒng)），2015年科目代碼改為862o為幫助考生全面復(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ù)考生注意：請(qǐng)將答案寫在答題紙上，寫在本題簽及草紙上無效?？荚嚭蟊绢}簽同答題紙一并交回。一、單項(xiàng)選擇題（共10題，每題2分，合計(jì)20分）1.某算法的時(shí)間復(fù)雜度為O（n2）,表明該算法（

4、）oA.問題規(guī)模是n2B.執(zhí)行時(shí)間等于n2C.執(zhí)行時(shí)間與n2成正比D.問題規(guī)模與n2成正比2設(shè)線性表有n個(gè)元素，以下操作中，（）在順序表上實(shí)現(xiàn)比在鏈表上實(shí)現(xiàn)效率更高。A.輸出第i（1<i<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)在在（）oA.已出棧B.從棧底算起第3個(gè)C.棧頂D.從棧底算起第4個(gè)4.循環(huán)隊(duì)列qu（其隊(duì)頭指針front指向隊(duì)列中隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針rear指向隊(duì)尾元素的位置，隊(duì)列中的

5、單元個(gè)數(shù)為MaxSize）的隊(duì)滿足條件是（）oA. （qu.rear+1）%MaxSize=（qu.front+1）%MaxSizeB. （qu.rear+1）%MaxSize=qu.front+1C. （qu.rear+1）%MaxSize=qu.frontD. qu.rear=qu.frontS. 一棵二叉樹的中序序列為ABDCEFG后序序列為BDCAFGE則其左子樹中的節(jié)點(diǎn)個(gè)數(shù)為（）oA. 3B. 2C. 4D. 56 .根據(jù)使用頻率為5個(gè)字符設(shè)計(jì)的哈夫曼編碼不可能是（）oA.111,110,10,01,00B.000,001,010,011,1C.100,11,10,1,0D.001,

6、000,01,11,107 .對(duì)所示的無向圖，從頂點(diǎn)1開始進(jìn)行深度優(yōu)先遍歷，可得到的頂點(diǎn)訪問序列為（）0A. 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,采用的是（）oA.簡(jiǎn)單選擇排序B.起泡排序C.直接插入排序D.堆排序10 .對(duì)一組數(shù)據(jù)（2,12,16,88,5,10）進(jìn)行排序，若前三趟的結(jié)果如下

7、：第一趟：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開始的一棵最小生成樹。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ù)組中46OOOOOO5OOOOOO43OOOO33要求：（1）寫出圖G的鄰接矩陣Ao（2）畫出有向帶權(quán)圖Go（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,b1,a2,b2,an,bn為一線性表，采用帶頭節(jié)點(diǎn)的hc單鏈表存放，設(shè)計(jì)一個(gè)就地算法，將其拆分為兩個(gè)線性表（它們都用單鏈表存放），使得：A=a1,a2,an,B=b1，b2,bn16 .假設(shè)二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，試設(shè)計(jì)

9、一個(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 .說明什么是進(jìn)程間的直接制約與間接制約。21 .說明什么是虛擬存儲(chǔ)器。22 .請(qǐng)說明分區(qū)存儲(chǔ)管理方式的主要優(yōu)缺點(diǎn)。23 .說明什么是中斷。五、綜合題（共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)中沒有其他作業(yè)，試給出對(duì)它們實(shí)施FC

10、FSM度算法的計(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操作來描述讀者一寫者問題。2013年沈陽師范大學(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)將答案寫在答題紙上，寫在本題簽及草紙上無效?？荚嚭蟊绢}簽同答題紙一并交回。一、單項(xiàng)選擇題（共30題

11、，每題2分，合計(jì)60分）1.某算法的時(shí)間復(fù)雜度為O（n2）,表明該算法的（）。A.問題規(guī)模是n2B.執(zhí)行時(shí)間等于n2C.執(zhí)行時(shí)間與n2成正比D.問題規(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í)的操作為（）。A. s->next=p->next;p->next=s;t=p->data;p->

12、;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)棧序列

13、是1,2,3,，n,其輸出序列是p,p2,，pn,若p1二n,則pi的值（）。A. iB. n-iC. n-i+1D.不確定5 .對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，常用的兩種方法是（）。A.二元組和散列表B.三元組和十字鏈表C.三角矩陣和對(duì)角矩陣D.對(duì)角矩陣和十字鏈表6 .廣義表（a）,a）的表頭和表尾分別是（）。A. （a）和（a）B. a和（a）C. （a）和aD. （a）和（a）7 .已知二叉樹的先序序列為ABDEGCF中序序列為DBGEACF則后序序列為（）。A. GEDBFCAB. DGEBFCAC. DGEBAFCD. EBFDGCA8 .一棵完全二叉樹上有1000個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)

14、是（），A. 250B. 500C. 505D. 5019 .線索二叉樹是一種（）結(jié)構(gòu)。A.邏輯10 邏輯和存儲(chǔ)C.物理D.線性10 .以數(shù)據(jù)集2,5,7,9,13為權(quán)值構(gòu)造一棵哈夫曼樹，則其帶權(quán)路徑長(zhǎng)為（）。A. 78B. 80C. 81D. 7911 .一個(gè)有向圖的鄰接表存儲(chǔ)如圖1所示，現(xiàn)按深度優(yōu)先搜索遍歷，從頂點(diǎn)V1出發(fā)，所得到的頂點(diǎn)序列是（）。A. v1，V2, V3, v B. V1, V2, V3, v5 C. V1, V2, V4, V5 D. v1，V2, V5, v3 12.任意一個(gè)無向1'通3*）最小生成樹。4A.只有一棵8. 一定有多棵C.有一棵或多棵D.可能不存

15、在13 .若一個(gè)有向圖中的頂點(diǎn)不能排成一個(gè)拓?fù)湫蛄校瑒t可斷定該有向圖（）。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 .在有序表a1.20中，采用二分查找算法查找元素值等于a12的元素，所比較過元素的次數(shù)

16、為（）。A. 4B. 5C. 3D. 617 .數(shù)據(jù)序列8,9,10,4,5,6,20,1,2只能是下列排序算法中的（）的兩趟排序后的結(jié)果。A.選擇排序18 冒泡排序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都不對(duì)20 .下面說法不正確的是（）。A.關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)

17、工程的完成時(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.高級(jí)程序設(shè)計(jì)語言的編譯器22 .系統(tǒng)功能調(diào)用是（）。A.用戶編寫的一個(gè)子程序B.高級(jí)語言中的庫程序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í)

18、調(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)中對(duì)數(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)中，對(duì)于下列文件物理結(jié)

19、構(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)（氣泡的下沉）。請(qǐng)給出上浮和下沉過程交替的冒泡排序算法。三、綜合應(yīng)用題（共6題，合計(jì)70分）33 .寫出用Prim算法構(gòu)造圖2最小生成樹的過程。（10分）圖2無向網(wǎng)34 .關(guān)鍵字序列A=（36,

20、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)度。（10分）35 .在如圖3所示的AOEW,求：（10分）（1）完成此工程最少需要的多少天（設(shè)邊上權(quán)值為天數(shù)）。（2）是否存在某項(xiàng)活動(dòng)，當(dāng)其提高速度后能使整個(gè)工程縮短工期。ai2=4a8=183僦=4 SJ579836.若有以下四個(gè)作業(yè)同2寸到迷痛并立即進(jìn)入調(diào)作業(yè)名作業(yè)作業(yè)作業(yè)作業(yè)1234CPU時(shí)間（分鐘）a6=3aio=5假設(shè)系統(tǒng)中沒有其他作業(yè),給出作業(yè)調(diào)度順序并求出

21、平均作業(yè)周轉(zhuǎn)時(shí)間T,平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間W。（15分）37 .在一個(gè)請(qǐng)求式頁式管理系統(tǒng)中，某程序在內(nèi)存中分配三個(gè)頁面，初始為空.頁面走向?yàn)椋?,3,2,1,4,3,5,4,3,2,1,5。用學(xué)過的頁面值換算法FIFO算出缺頁次數(shù)。給出執(zhí)行過程中內(nèi)存頁面的變化情況。（1538 .在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)P12P2P3P4第二部分全國(guó)碩士研究生入學(xué)統(tǒng)一考試408計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合歷年真題及詳解2012年全國(guó)碩士研究生入學(xué)統(tǒng)

22、一考試408計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合真題一、單項(xiàng)選擇題：l40小題。每小題2分，共80分。下列每題給出的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)是最符合題目要求的。1 .求整數(shù)n(n>0)階乘的算法如下，其時(shí)間復(fù)雜度是()。A. O(log2n)B. 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í)，用棧來存放暫時(shí)還不能確定運(yùn)算次序的操作符。若棧初始時(shí)為空，則轉(zhuǎn)換過程中同時(shí)保存在棧中的

23、操作符的最大個(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 .對(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ì)角線以下的元素均為零，則關(guān)于該圖拓?fù)湫蛄械慕Y(jié)論是(A.存

24、在，且唯一B.存在，且不唯一不唯一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)在所有的最小生成樹中田.使用普里姆（Prim）算法從不同頂點(diǎn)開始得到的最小生成樹一定相同IV.使用普里姆算法和克魯斯卡爾（Kru

25、skal）算法得到的最小生成樹總不相同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 .排序過程中，對(duì)尚未確定最終位置的所有元素進(jìn)行一遍處理稱為一趟排序。下列排序方法中，每一趟排序結(jié)束時(shí)都至少能夠確定一個(gè)元素最終位置的方法是（）。I.簡(jiǎn)單選擇排序n.希爾排序田.快速排序iv.堆排V.二路歸并排序A.僅I、m、IVB.僅I、n、mC.僅n、m、ivD.僅田、IV、V11.對(duì)同一待排序列分別進(jìn)行折半插入排序和直接插入排序，兩者之間可

26、能的不同之處是（）。A.排序的總趟數(shù)B.元素的移動(dòng)次數(shù)C.使用輔助空間的數(shù)量D.元素之間的比較次數(shù)12 .假定基準(zhǔn)程序A在某計(jì)算機(jī)上的運(yùn)行時(shí)間為100秒，其中90秒為CPUS寸間，其余為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類型長(zhǎng)度分別為32位和16位，執(zhí)行下列C語言語句：unsignedshortX=65530;unsignedinty=X:得到y(tǒng)的機(jī)器數(shù)為（）。A. 00007FFAH B. 0000FFFAH C. FFFF7FFAH D. FFFFF

27、FFAH 14. float類型（即IEEE754單精度浮點(diǎn)數(shù)格式）能表示的最大正整數(shù) 是（A. B. C. D.）。2126 2 1032偌7 2 1042127-212810310415 .某計(jì)算機(jī)存儲(chǔ)器按字節(jié)編址，采用小端方式存放數(shù)據(jù)。假定編譯器規(guī)定int和short型長(zhǎng)度分別為32位和16位，并且數(shù)據(jù)按邊界對(duì)齊存儲(chǔ)。某C語言程序段如下：若record變量的首地址為0xC008,則地址0xC008中內(nèi)容及record.c的地址分別為（）。A. 0x00、0xC00DB. 0x00、0xCOOEC. 0x11、0xC00DD. 0x11、0xC00E16.下列關(guān)于閃存（FlashMemor

28、y）的敘述中，錯(cuò)誤的是（）。A.信息可讀可寫，并且讀、寫速度一樣快B.存儲(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ù)是（）。A. 1B. 2C. 3D. 418 .某計(jì)算機(jī)的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接編碼法，共有33個(gè)微命令，構(gòu)成5個(gè)互斥類，分

29、別包含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ù)傳輸l28位數(shù)據(jù)所需要的時(shí)間至少是（）。）。A. 20nsB. 40nsC. 50nsD. 80ns20.下列關(guān)于USB總線特性的描述中，錯(cuò)誤的是（）。A.可實(shí)現(xiàn)外設(shè)的即插即用和熱插拔B.可通過級(jí)聯(lián)方式連接多臺(tái)外設(shè)C.是一種通信總線，可連接不同外設(shè)D.同時(shí)可傳輸2位數(shù)據(jù)，數(shù)據(jù)傳輸率高21.下列選項(xiàng)中，在I/O總線的數(shù)據(jù)線

30、上傳輸?shù)男畔ǎǎ.I/O接口中的命令字n.I/0接口中的狀態(tài)字m.中斷類型號(hào)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.外部中斷C.進(jìn)程切換D.缺頁24.中斷處理和子程序調(diào)用都需要壓棧以保護(hù)現(xiàn)場(chǎng)，中斷處理一定會(huì)保存而子程序調(diào)用不需要保存其內(nèi)容的是（）。A.程序計(jì)數(shù)器B.程序狀態(tài)字寄存器C.通用數(shù)據(jù)寄存器D.通用地址寄存器

31、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軟件、設(shè)備無關(guān)軟件、設(shè)備驅(qū)動(dòng)程序、中斷處理程序B.用戶級(jí)I/O軟件、設(shè)備無關(guān)軟件、中斷處理程序、設(shè)備驅(qū)動(dòng)程序C.用戶級(jí)I/O軟件、設(shè)備驅(qū)動(dòng)程序、設(shè)備無關(guān)軟件、中斷處理程序D.用戶級(jí)I/O軟件、中斷處理程序、設(shè)備無關(guān)軟件、設(shè)備驅(qū)動(dòng)程序27.假設(shè)5個(gè)進(jìn)程P0、Pl、P2、P3、P4共享三類資源

32、Rl、R2、R3,這些資源總數(shù)分別為18、6、22。飛時(shí)刻的資源分配情況如題27表所示，此時(shí)存在的一個(gè)安全序列是（）。題27表資源分配情況表已分配資源資源最大需求進(jìn)程R1R2R3R1R2R3PO323155101P14O3536P24O54O11P32O4425P4314424A. P0,P2,P4,Pl,P3B. Pl,P0,P3,P4,P2C. P2,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.請(qǐng)求read系統(tǒng)調(diào)

33、用會(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/O80ms,計(jì)算20ms;P2:計(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)程后

34、能進(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è)線程擁有各自不同的地址空間32 .下列選項(xiàng)中，不能改善磁盤設(shè)備I/O性能的是（）。A.重排I/0請(qǐng)求次序B.在一個(gè)磁盤上設(shè)置多個(gè)分區(qū)C.預(yù)讀和滯后寫D.優(yōu)化文件物理塊的分布33.在TC%IP體系結(jié)構(gòu)中，直接為ICMP提供服務(wù)的協(xié)議是（）。A. PPPB. IPC. UDPD.

35、 TCPE. .在物理層接口特性中，用于描述完成每種功能的事件發(fā)生順序的是（）。A.機(jī)械特性B.功能特性C.過程特性D.電氣特性F. .以太網(wǎng)的MAO議提供的是（）。A.無連接不可靠服務(wù)B.無連接可靠服務(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)度范圍是128512字節(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è)置路由

36、表；n.監(jiān)測(cè)到擁塞時(shí)，合理丟棄ip分組；田.對(duì)收到的ip分組頭進(jìn)行差錯(cuò)校驗(yàn)，確保傳輸?shù)腎P分組不丟失；IV.根據(jù)收到的ip分組的目的ip地址，將其轉(zhuǎn)發(fā)到合適的輸出線路上。A.僅田、IVB.僅I、n、mC.僅i、n、ivd.i、n、m、iv38.ARPB議的功能是（）。A.根據(jù)IP地址查詢MAC4址B.根據(jù)MAC4址查詢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.

37、77.255D. 180.80.79.25540.若用戶l與用戶2之間發(fā)送和接收電子郵件的過程如題40圖所示,則圖中、階段分別使用的應(yīng)用層協(xié)議可以是()。題40圖電子郵件發(fā)送接收示意圖A. SMTPSMTPSMTPB. POP3SMTPPOP3C. POP3SMTPSMTPD. SMTPSMTPPOP3二、綜合應(yīng)用題：41"-47小題。共70分。41. (10分)設(shè)有6個(gè)有序表AB、CRE、F,分別含有10、35、40、50、60和200個(gè)數(shù)據(jù)元素，各表中元素按升序排列。要求通過5次兩兩合并，將6個(gè)表最終合并成1個(gè)升序表，并在最壞情況下比較的總次數(shù)達(dá)到最小。請(qǐng)回答下列問題。(1)給出

38、完整的合并過程，并求出最壞情況下比較的總次數(shù)。(2)根據(jù)你的合并過程，描述n(n>2)個(gè)不等長(zhǎng)升序表的合并策略，并說明理由。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)o要求：(1)給出算法的基本設(shè)計(jì)思想。(2)根據(jù)設(shè)計(jì)思想，采用C

39、或C+堿JAVA語言描述算法，關(guān)鍵之處給出注釋。(3)說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度。43. (11分)假定某計(jì)算機(jī)的CPUfe頻為80MHzCPI為4,并且平均每條指令訪存1.5次，主存與Cache之間交換的塊大小為168,Cache的命中率為99%,存儲(chǔ)器總線寬度為32位。請(qǐng)回答下列問題。（1）該計(jì)算機(jī)的MIPS數(shù)是多少？平均每秒Cache缺失的次數(shù)是多少？在不考慮DMA專送的情況下，主存帶寬至少達(dá)到多少才能滿足CPU勺訪存要求？（2）假定在Cache缺失的情況下訪問主存時(shí)，存在0.0005%的缺頁率，則CPUF均每秒產(chǎn)生多少次缺頁異常？若頁面大小為4KB,每次缺頁都需要訪問磁盤，訪問磁盤時(shí)

40、DM砥送采用周期挪用方式，磁盤I/O接口的數(shù)據(jù)緩沖寄存器為32位，則磁盤I/O接口平均每秒發(fā)出的DMA青求次數(shù)至少是多少？（3）CP次口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)中部分指令格式，其中Rs和Rd表示寄存器，memi示存儲(chǔ)單元地址，（X）表示寄存器X或存儲(chǔ)單元X的內(nèi)容。表指令系統(tǒng)中部分指令格式名稱指令的匯編

41、格式指令功能加法指令A(yù)DDRsRd(Rs)+(Rd)fRd算術(shù)/邏輯左移SHLRd2*(Rd)fRd算術(shù)右移SHRRd(Rd)/2fRd取數(shù)指令LOADRDmem(mermfRd存數(shù)指令STORERsmem(Rs)fmem該計(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)行。請(qǐng)回答下列問題。（1）若屁型變量x的值為-513,存放在寄存器Rl中，則執(zhí)行指令“SHRRl”后，R

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

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

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

45、創(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ù)的合理值并說明理由。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)制)1019b40008006lde8coa80008d34447500bd913

46、88846b41c5000000005db0000020000400031066e833d3444750cOa8000813880bd9e0599fef846b41c66701216d037e100003019c40008006ldefcOa80008d3444750bd91388846b41c6e0599ff0501043802b3200004019d400080061ddecOa80008d34447500bd91388846b4lc6e0599ff0c655000053106067ad3444750cOa8000813880bd9e0599ff0846b41d6501016d057d20

47、000請(qǐng)回答下列問題。(1)題47-a表中的IP分組中，哪幾個(gè)是由H發(fā)送的？哪幾個(gè)完成了TC唯接建立過程？哪幾個(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ā)出的分組4006eCadd3444750ca7601061388a108e0599ff0846b41d6501016dOb7d60000注：IP分組頭和TCP段頭結(jié)構(gòu)分別如題47-a圖、題47-b圖所示:版本頭部長(zhǎng)度服務(wù)類型(8-15)總長(zhǎng)

48、度(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ù)偏移保留URGACKPSHRSTSYNFIN窗口校驗(yàn)和緊急®#選項(xiàng)(長(zhǎng)度可艾)填充題47-b圖TCP段頭結(jié)構(gòu)2012年全國(guó)碩士研究生入學(xué)統(tǒng)一考試408計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合真題及詳解一、單項(xiàng)選擇題：l40小題。每小題2分，共80分。下列每題給出的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)是最符合題目要求的。1 .求整數(shù)n(n>0)階乘的算法如下，其時(shí)間復(fù)雜度是()。A. O(log2n)B. 0(n)C. O(nlo

49、g2n)一，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)+0(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)+0(1)。則，T(n)=O(1)+T(n-1)=2XO(1)+T(n-2)=(n-1)xO(1)+T(1)=nxO(1)=O(n)即fact(n)的時(shí)間復(fù)雜度為O(n)。2 .已知操作符包括+、'-'、'*'、'/'、'('和。將中綴表達(dá)式a+b-a*

50、(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)先級(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á)式的過程如下表所列：卜前字符運(yùn)算符棧內(nèi)容后綴表達(dá)式說明a+“+”進(jìn)棧b+ab-ab+“-”與棧頂兀素“+”的優(yōu)先

51、級(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)-*(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í)小

52、于棧頂兀素“*”，則“*”出棧+ab+acd+e/f-*-“+”與棧頂兀素“-”的優(yōu)先級(jí)相同，則“-”出棧，“+”進(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.只有eB.有e、bC.有e、cD.無法確定【答案】A。【解析】由題目可知，若一棵二叉樹的前序遍歷序列為a,e,b,d,c,后序遍歷序列為b,c,d,e,a,其中a為這棵二叉樹的根結(jié)點(diǎn)，接下來，在前序遍歷的第二個(gè)結(jié)點(diǎn)為e,而后序

53、遍歷的倒數(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=2NL=N.-i+N,-2+I由此可得N=20。對(duì)應(yīng)的平衡二叉樹如下圖所示。5 .對(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)【答案】Co【解析】遍歷

54、圖的過程實(shí)質(zhì)上是對(duì)每個(gè)頂點(diǎn)查找其鄰接點(diǎn)的過程。其耗費(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為無向圖中邊的數(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.存在，且唯一8 .存在，且不唯一不唯一C.存在，可能不唯一D.無法確定是否存在【答案】Co【解析】圖的基本應(yīng)用一一拓?fù)渑判?，用鄰接矩陣存?chǔ)有向圖