2009年計算機統(tǒng)考考研試題及參考答案.doc

2009年全國碩士研究生入學統(tǒng)一考試計算機科學與技術(shù)學科聯(lián)考計算機學科專業(yè)基礎綜合試題一 單項選擇題，每小題2分，共80分。1.為解決計算機與打印機之間速度不匹配的問題，通常設置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應該是 A.棧 B.隊列 C.樹 D.圖 此題考察各數(shù)據(jù)結(jié)構(gòu)的特點。棧的特點是先進后出。隊列的特點是先進先出。樹的特點是節(jié)點的前驅(qū)只能有一個的數(shù)據(jù)結(jié)構(gòu)。圖是最復雜的數(shù)據(jù)結(jié)構(gòu)，它是前驅(qū)和后繼都可以有多個的網(wǎng)狀結(jié)構(gòu)。2.設棧S和隊列Q的初始狀態(tài)均為空，元素abcdefg依次進入棧S。若每個元素出棧后立即進入隊列Q，且7個元素出隊的順序是bdcfeag，則棧S的容量至少是 A1 B.2 C.3 D.4 元素abcdefg依次進入棧，bdcfeag依次出隊，那么他們在棧中操作順序依次為：a入棧、b入棧、b出棧、c入棧、d入棧、d出棧、c出棧、e入棧、f入棧、f出棧、e出棧、a出棧、g入棧、g出棧。這其間棧中數(shù)據(jù)最多有3個。3.給定二叉樹圖所示。設N代表二叉樹的根，L代表根結(jié)點的左子樹，R代表根結(jié)點的右子樹。若遍歷后的結(jié)點序列為3，1，7，5，6，2，4，則其遍歷方式是 ALRN B.NRL C.RLN D.RNL 一看第一個遍歷出來的元素是3，所以后序遍歷4.下列二叉排序樹中，滿足平衡二叉樹定義的是 AB. C. D. 平衡二叉樹，又稱AVL樹。它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的高度之差之差的絕對值不超過1。5.已知一棵完全二叉樹的第6層（設根為第1層）有8個葉結(jié)點，則完全二叉樹的結(jié)點個數(shù)最多是 A39 B.52 C.111 D.119 第6層有8個葉節(jié)點，說明這個完全二叉樹最多共7層，所以樹的節(jié)點數(shù)為：1+2+4+8+16+32+48=111。6.將森林轉(zhuǎn)換為對應的二叉樹，若在二叉樹中，結(jié)點u是結(jié)點v的父結(jié)點的父結(jié)點，則在原來的森林中，u和v可能具有的關(guān)系是 I父子關(guān)系 II.兄弟關(guān)系 III. u的父結(jié)點與v的父結(jié)點是兄弟關(guān)系 A.只有II B.I和II C.I和III D.I、II和III 7.下列關(guān)于無向連通圖特性的敘述中，正確的是 I所有頂點的度之和為偶數(shù) II.邊數(shù)大于頂點個數(shù)減1 III.至少有一個頂點的度為1 A.只有I B. 只有II C.I和II D.I和III 8.下列敘述中，不符合m階B樹定義要求的是 A根節(jié)點最多有m棵子樹 B.所有葉結(jié)點都在同一層上 C各結(jié)點內(nèi)關(guān)鍵字均升序或降序排列 D.葉結(jié)點之間通過指針鏈接 B樹是一種多叉平衡查找樹。一棵m階的B樹，或為空樹，或為滿足下列特性的m叉樹：樹中每個結(jié)點至多有m棵子樹；若根結(jié)點不是葉子結(jié)點，則它至少有兩棵子樹；除根之外的所有非葉子結(jié)點至少有m/2棵子樹；所有的非葉子結(jié)點中包含卞列數(shù)據(jù)信息(n，A0，K1，A1，K2，A2，Kn，An)其中：Ki(i=1，2，n)為關(guān)鍵字，且Ki0）個單元的緩沖區(qū)。P1每次用produce()生成一個正整數(shù)并用put()送入緩沖區(qū)某一空單元中；P2每次用getodd()從該緩沖區(qū)中取出一個奇數(shù)并用countodd()統(tǒng)計奇數(shù)個數(shù)；P3每次用geteven()從該緩沖區(qū)中取出一個偶數(shù)并用counteven()統(tǒng)計偶數(shù)個數(shù)。請用信號量機制實現(xiàn)這三個進程的同步與互斥活動，并說明所定義的信號量的含義。要求用偽代碼描述。 答案：（1）緩沖區(qū)是一互斥資源，因此設互斥信號量mutex。（2）同步問題：P1、P2因為奇數(shù)的放置與取用而同步，設同步信號量odd；P1、P3因為偶數(shù)的放置與取用而同步，設同步信號量even；P1、P2、P3因為共享緩沖區(qū)，設同步信號量empty。Semaphore mutex=1;Semaphore odd=0; even=0;Semaphore empty=N;main()cobeginProcess P1while(True) number=produce();P(empty);P(mutex);put();V(mutex);if number % 2=0 V(even);else V(odd);Process P2while(true) P(odd); P(mutex);getodd();V(mutex);V(empty);countodd();Process P3while(true)P(even);P(mutex);geteven();V(mutex);V(empty);counteven();coend【評分說明】能正確給出互斥信號量定義與含義的，給1分；能正確給出3個同步信號量定義與含義的，各給1分，共3分；能正確描述P1、P2和P3進程活動的，各給1分，共3分；wait()、signal()等同于P、V。歸納總結(jié)：點評：鏈接：某車站售票廳，任何時間最多可容納100名購票者進入，當售票廳中少于100名購票者時，則廳外的購票者可立即進入，否則需在外面等待。若把一個購票者看作一個進程，請回答以下問題：（1）用PV操作管理這些并發(fā)進程時，應怎樣定義信號量？寫出信號量的初值以及信號量各種取值的含義。（2）根據(jù)所定義的信號量，把應執(zhí)行的PV操作填入下列方框中，以保證進程能夠正確地并發(fā)執(zhí)行。cobegin process pi(i=1,2,n)begin進入售票廳；購票；退出；endcoend（3）若欲購票者最多為n個人，寫出信號量可能的變化范圍（最大值和最小者）。解析：（1）應定義一個信號量S，S的初值為100，當0S=100時，允許廳外的購票者進入；當S=0時，廳內(nèi)已有100人，欲購票者暫不能進入；當S0時，|S|表示等待進入者的人數(shù)。（2）用PV操作管理時保證進程正確執(zhí)行的程序如下：cobegin process i(i=1,2,3,n)begin p(s);進入售票廳；購票；退出；v(s);end;coend;（3）若購票者最多為n人，則信號量S的變化范圍：5M-Nk時，指針p隨著每次遍歷，也向前移動一個節(jié)點。當遍歷完成時，p或者指向表頭就節(jié)點，或者指向鏈表中倒數(shù)第K個位置上的節(jié)點。（3）算法描述： Int LocateElement(linklist list,int k) P1=list-link; P=list; i=1;while(P1) P1=P1-link; i+; if(ik) p=p-next; /如果ik,則p也往后移 if(p=list)return 0; /說明鏈表沒有k個結(jié)點 else printf(“%dn“,p-data); return 1; 43. （1）在中斷方式下，每32位（4B）被中斷一次，故每秒中斷 0.5MB/4B=0.5106/4=12.5104次 要注意的是，這里是數(shù)據(jù)傳輸率，所以1MB=106B。因為中斷服務程序包含18條指令，中斷服務的其他開銷相當于2條指令的執(zhí)行時間，且執(zhí)行每條指令平均需5個時鐘周期，所以，1秒內(nèi)用于中斷的時鐘周期數(shù)為 （18+2）512.5104=12.5106 （2）在DMA方式下，每秒進行DMA操作 5MB/5000B=5106/5000=1103 次因為DMA預處理和后處理的總開銷為500個時鐘周期，所以1秒鐘之內(nèi)用于DMA操作的時鐘周期數(shù)為 5001103=5105 故在DMA方式下，占整個CPU時間的百分比是 （5105）/（500106）100%=0.1% 44.指令執(zhí)行階段每個節(jié)拍的功能和有效控制信號如下所示 時鐘 功能 有效控制信號 C5 MAR(R1) PCout,MARin C6 MDRM(MAR) MemR,MDRinE C7 A(R0) R0out,Ain C8 AC(MDR)+(A) MDRout,Addr,ACin C9 MDR(AC) ACout,MDRin C10 M(MAR) MDR MDRoutE,MemW 45.定義信號量S1控制P1與P2之間的同步；S2控制P1與P3之間的同步；empty控制生產(chǎn)者與消費者之間的同步；mutex控制進程間互斥使用緩沖區(qū)。程序如下： Var s1=0,s2=0,empty=N,mutex=1; Parbegin P1:begin X=produce(); /*生成一個數(shù)*/ P(empty); /*判斷緩沖區(qū)是否有空單元*/ P(mutex); /*緩沖區(qū)是否被占用*/ Put(); If x%2=0 V(s2); /*如果是偶數(shù)，向P3發(fā)出信號*/ else V(s1); /*如果是奇數(shù)，向P2發(fā)出信號*/ V(mutex); /*使用完緩沖區(qū)，釋放*/ end. P2:begin P(s1); /*收到P1發(fā)來的信號，已產(chǎn)生一個奇數(shù)*/ P(mutex); /*緩沖區(qū)是否被占用*/ Getodd(); Countodd():=countodd()+1; V(mutex); /*釋放緩沖區(qū)*/ V(empty); /*向P1發(fā)信號，多出一個空單元*/ end. P3:begin P(s2) /*收到P1發(fā)來的信號，已產(chǎn)生一個偶數(shù)*/ P(mutex); /*緩沖區(qū)是否被占用*/ Geteven(); Counteven():=counteven()+1; V(mutex); /*釋放緩沖區(qū)*/ V(empty); /*向P1發(fā)信號，多出一個空單元*/ end. Parend. 46. （1）根據(jù)頁式管理的工作原理，應先考慮頁面大小，以便將頁號和頁內(nèi)位移分解出來。頁面大小為4KB，即212，則得到頁內(nèi)位移占虛地址的低12位，頁號占剩余高位?？傻萌齻€虛地址的頁號P如下（十六進制的一位數(shù)字轉(zhuǎn)換成4位二進制，因此，十六進制的低三位正好為頁內(nèi)位移，最高位為頁號）： 2362H：P=2，訪問快表10ns，因初始為空，訪問頁表100ns得到頁框號，合成物理地址后訪問主存100ns，共計10ns+100ns+100ns=210ns。 1565H：P=1，訪問快表10ns，落空，訪問頁表100ns落空，進行缺頁中斷處理108ns，合成物理地址后訪問主存100ns，共計10ns+100ns+108ns+100ns108ns。 25A5H：P=2，訪問快表，因第一次訪問已將該頁號放入快表，因此花費10ns便可合成物理地址，訪問主存100ns，共計10ns+100ns=110ns。 （2）當訪問虛地址1565H時，產(chǎn)生缺頁中斷，合法駐留集為2，必須從頁表中淘汰一個頁面，根據(jù)題目的置換算法，應淘汰0號頁面，因此1565H的對應頁框號為101H。由此可得1565H的物理地址為101565H。 47. （1）無類IP地址的核心是采用不定長的網(wǎng)絡號和主機號，并通過相應的子網(wǎng)掩碼來表示（即網(wǎng)絡號部分為1，主機號部分為0）。本題中網(wǎng)絡地址位數(shù)是24，由于IP地址是32位，因此其主機號部分就是8位。因此，子網(wǎng)掩碼就是11111111 11111111 11111111 00000000，即255.255.255.0。 根據(jù)無類IP地址的規(guī)則，每個網(wǎng)段中有兩個地址是不分配的：主機號全0表示網(wǎng)絡地址，主機號全1表示廣播地址。因此8位主機號所能表示的主機數(shù)就是2的8次方2，即254臺。 該網(wǎng)絡要劃分為兩個子網(wǎng)，每個子網(wǎng)要120臺主機，因此主機位數(shù)X應該滿足下面三個條件： X120,因為根據(jù)題意需要容納120臺主機。 X是整數(shù)。 解上述方程，得到X=7.子網(wǎng)掩碼就是11111111 11111111 11111111 10000000，即255.255.255.128。 所以劃分的兩個網(wǎng)段是：202.118.1.0/25與202.118.1.128/25。 （2）填寫R1的路由表 填寫到局域網(wǎng)1的路由。局域網(wǎng)1的網(wǎng)絡地址和掩碼在問題（1）已經(jīng)求出來了，為202.118.1.0/25。則R1路由表應填入的網(wǎng)絡地址為202.118.1.0，掩碼為255.255.255.128。由于局域網(wǎng)1是直接連接到路由器R1的E1口上的，因此，下一跳地址填寫直接路由（Direct）。接口填寫E1. 填寫到局域網(wǎng)2的路由表1。局域網(wǎng)2的網(wǎng)絡地址和掩碼在問題（1）中已經(jīng)求出來了，為202.118.1.128/25。則R1路由表應該填入的網(wǎng)絡地址為202.118.1.128，掩碼為255.255.255.128.由于局域網(wǎng)2是直接連接到路由器R1的E2口上的，因此，下一跳地址填寫直接路由。接口填寫E2。 填寫到域名服務器的路由。由于域名服務器的IP地址為202.118.3.2，而該地址為主機地址，因此掩碼為255.255.255.255。同時，路由器R1要到DNS服務器，就需要通過路由器R2的接口L0才能到達，因此下一跳地址填寫L0的IP地址（202.118.2.2）。 填寫互聯(lián)網(wǎng)路由。本題實質(zhì)是編寫默認路由。默認路由是一種特殊的靜態(tài)路由，指的是當路由表中與包的目的地址之間沒有匹配的表項時路由器能夠做出的選擇。如果沒有默認路由器，那么目的地址在路由表中沒有匹配表項的包將被丟棄。默認路由在某些時候非常有效，當存在末梢網(wǎng)絡時，默認路由會大大簡化路由器的配置，減輕管理員的工作負擔，提高網(wǎng)絡性能。默認路由叫做“0/0”路由，因為路由的IP地址0.0.0.0，而子網(wǎng)掩碼也是0.0.0.0。同時路由器R1連接的網(wǎng)絡需要通過路由器R2的L0口才能到達互聯(lián)網(wǎng)絡，因此下一跳地址填寫L0的IP為202.118.2.2。 綜上，填寫的路由表如下： R1路由表 目的網(wǎng)絡IP地址 子網(wǎng)掩碼 下一跳IP地址 接口 202.118.1.0 255.255.255.128 Direct E1 202.118.1.128 255.255.25