2014年東南大學(xué)計算機專業(yè)考研真題

1、2014年東南大學(xué)計算機專業(yè)考 研真題2014年東南大學(xué)計算機專業(yè)考研真題一、選擇題（共80分）1 .下面關(guān)于進程的描述中，不正確的是A進程是動態(tài)的概念B進程就是一個獨立的程序C進程可以并發(fā)執(zhí)行D進程可由程序、數(shù)據(jù)和進程控制塊描述2 .在多對一的線程模型中，一個多線程中的某個 線程執(zhí)行一個需阻塞的系統(tǒng)調(diào)用時，下列選項中 正確的是A整個進程都將被阻塞B該進程的其他線程仍可繼續(xù)執(zhí)行C該阻塞線程將被撤銷D該阻塞線程將阻塞直到進程退出3 .采用多道程序設(shè)計技術(shù)能提高整個計算機系 統(tǒng)的效率，其基本條件是A硬盤容量大B處理器執(zhí)行指令速度快C外圍設(shè)備多D系統(tǒng)具有處理器與外設(shè)并行工作的能力4 .下列指令中，不

2、是特權(quán)指令的是A I/O指令B讀取當前時鐘C設(shè)置基址寄存器D關(guān)閉中斷5 .在存儲管理中，外部碎片指的是A存儲分配完成所剩的空閑區(qū) B沒有被使用 的存儲區(qū)C不能被使用的存儲區(qū)D未被使用，又暫時不能使用的存儲區(qū)6 .進程所請求的一次打印輸出結(jié)束后，進程狀態(tài) 會發(fā)生的變化是A從運行態(tài)變成就緒態(tài)B從運行態(tài)變成等待態(tài)C從等待態(tài)變成就緒態(tài)D從就緒態(tài)變成運行態(tài)7 .關(guān)于RoundRobin調(diào)度算法，以下說法正確的 是I.同樣的情況下，時間片越大，平均周轉(zhuǎn)時間越小II.FCFS算法是Round Robin算法的一種特殊情Round況III .只有實現(xiàn)了定時的機制，才能實現(xiàn)Robin算法IV .Round Ro

3、bin屬于非搶占調(diào)度算法A僅I和IIC僅III和IVB僅II和IIID僅I和IV8 .物理內(nèi)存和虛擬存儲空間相比，其大小關(guān)系是A前者比后者大C兩者一樣大B前者比后者小D不一定B一個共享變量D 一種同步機9 .臨界區(qū)指的是A一段內(nèi)存共享區(qū)域C訪問臨界資源的一段程序制10 .為使虛擬存儲系統(tǒng)有效發(fā)揮其預(yù)期作用，所 運行的程序應(yīng)具有的特性是A程序應(yīng)比較大B程序應(yīng)該具有良好的局部性D程序應(yīng)含有C程序應(yīng)含有多個I/O操作 較多的動態(tài)分配內(nèi)存工作11 .下列說法正確的是I .當發(fā)現(xiàn)系統(tǒng)中存在抖動（Thrashing）時，應(yīng)更 換一塊更大的磁盤用于頁面置換II .內(nèi)存分頁管理方式不會產(chǎn)生外部碎片III .磁

4、盤訪問時間主要是由旋轉(zhuǎn)時延和傳輸時 延組成IV .FCFS算法可用于實現(xiàn)磁盤調(diào)度A僅I和IIB僅III和IVC僅II和IVD僅I和III12.一個請求分頁存儲管理系統(tǒng)中，假設(shè)分配給 某作業(yè)的頁框（Frame）數(shù)為3,該作業(yè)的頁引用 序列為021,3,0,2,4,0,2,1,3,4,所有的頁框初始時都為空，分別采用最近最少次數(shù)使用（LRU） 和最優(yōu)（OPT）頁面置換算法時，產(chǎn)生頁面失效（Page Fault）的次數(shù)分別是A 10 和 7B 9 和 8C 9和7D 7和413.單處理器系統(tǒng)中有n(n>2)個進程，若進程調(diào) 度程序當前沒有執(zhí)行，則以下情形不可能發(fā)生的 是A有一個運行進程，沒有就

5、緒進程，剩下的 n-1 個進程處于等待狀態(tài)B有一個運行進程和一個就緒進程，剩下的 n-2 個進程處于等待狀態(tài)C沒有運行進程，有一個就緒進程，剩下的 n-1 個進程處于等待狀態(tài)D有一個運行進程和n-1個就緒進程，沒有進程 處于等待狀態(tài)14.關(guān)于短作業(yè)優(yōu)先(SJF)調(diào)度算法，下列說法正 確的是I.SJF算法能得到最優(yōu)的平均等待時間II.SJF算法能得到最優(yōu)的平均響應(yīng)時間III.SJF算法可能產(chǎn)生"饑餓” (Starvation)現(xiàn) 象IV.SJF算法是一種實際系統(tǒng)中常用的CPU調(diào)度算法A僅I和IIIB僅II和IVC僅I和IVD僅II和III15 .下列選項中，不是文件系統(tǒng)應(yīng)具備的功能的

6、是A對文件按名存取B實現(xiàn)對文件的各種操作C提高磁盤的I/O速度 D訪問數(shù)據(jù)時實 現(xiàn)從邏輯結(jié)構(gòu)到物理結(jié)構(gòu)的轉(zhuǎn)換16 .下列文件的物理結(jié)構(gòu)中，可能帶來外部碎片 問題的是A連續(xù)結(jié)構(gòu)B鏈接結(jié)構(gòu)C索引結(jié)構(gòu)D Hash結(jié)構(gòu)17 .下列選項中，不屬于算法的主要特征的是A有窮性B可行性C確定性D可讀性18 .若一個棧 S 的入棧序列為0,1,2,3,4,5,6,7,8,9,對于下列序列，S的可能出棧序列是I.5,6,8,7,2,1,4,3,0,911.0,2,1,6,5,8,7,4,3,9111.2,0,1,4,3,7,8,6,5,9IV.6,5,7,8,4,3,1,2,9,0A僅IC僅I和IIIB僅IID僅

7、II和IV19.對任意一個給定的二叉樹進行前序、中序和 后序遍歷可得到三個遍歷序列。下列有關(guān)這三個 遍歷序列的敘述中，正確的是I.葉子結(jié)點在三個遍歷序列中先后次序是一樣的II .兄弟結(jié)點在三個遍歷序列中先后次序是一樣的III .父子結(jié)點在三個遍歷序列中先后次序是一 樣的IV .祖先和子孫結(jié)點在三個遍歷序列中先后次序是一樣的A僅I和IIB僅III和IVC僅I和IIID僅II和IV20 .下列選項中，不可能是任何二叉搜索樹的前序遍歷序列的是A 4,2,3,5,6,7B 4,3,2,7,6,5C 6,5,4,2,3,7D 6,5,3,4,2,721 .用n（n大于等于2）個權(quán)值均不相同的字符構(gòu) 成哈

8、夫曼樹，下列關(guān)于該樹的敘述中錯誤的是 A樹中一定沒有度為1的結(jié)點B該樹一定是一棵完全二叉樹C樹中兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點D樹中任一非葉子結(jié)點的權(quán)值一定不小于其任一 子節(jié)點的權(quán)值22 .無向圖G如下圖所示，下列選項中，不可能 是G的廣度優(yōu)先遍歷序列的是A 0,123,4,53B 0,2,1,3,4,51 I；C 0,1,2,3,5,4UD 0,3,2,1,5,423 .下列關(guān)于圖的敘述中，正確的是A強連通有向圖的任何頂點到其他所有頂點都有 弧B圖與樹的區(qū)別在于圖的邊樹大于等于頂點數(shù)C有向圖的遍歷不可采用廣度優(yōu)先遍歷方法D帶權(quán)無向圖G中，若所有邊的權(quán)值均不相同， 則G的最小生成樹是唯一的2

9、4 .若排序過程中出現(xiàn)這種情況，在最后一遍開 始之前，所有元素都不能保證在其最終的位置 上，則采用的排序算法是A冒泡排序B堆排序C快速排序D直接插入排序25 .若對15個元素進行快速排序，則元素的比較 次數(shù)至少是A 26B 34C 52D 7826 .對序列14,9,7,10,20,1,5 進行排序，若第一 趟后的數(shù)據(jù)排列為 5,9,1,10,20,7,14,則采用的排序算法是A選擇排序B歸并排序C希爾排序D冒泡排序27 .對一個長度為16的有序表，若采用折半查找 法查找一個表中不存在的元素，則比較次數(shù)最多 的是28 .在一棵初始為空的AVL樹T中依次插入關(guān)鍵 碼1,2,3,4,5,6,7 的

10、結(jié)點后，T的根結(jié)點的關(guān)鍵 碼是A 3B 4C 5D 629 .馮諾依曼模型計算機中存放指令地址的寄 存器是A PCB IRC MAR DMDR30 .某計算機中各種指令的CPI平均為8, CPUI 用5級流水方式執(zhí)行指令，流水線每拍為2個時 鐘周期。執(zhí)行程序A時，共執(zhí)行2000條指令， 此時流水線的加速比約為A 4.0B 5.0C 8.0D10.031 .下列奇偶校驗碼中，若有一個存在錯誤，則 它是A 10001001 B 01001101 C 11010110D 1000010132 .某16位計算機中，存儲器按字節(jié)編址，整數(shù) 用補碼表示。數(shù)據(jù)在存儲器中采用小端次序存放，若 X,Y,Z 為整

11、數(shù)，且 X=-41, Y=+7§ Z=X-Y, Z存放在地址為A和A+1存儲單元中，則存儲單 元A的內(nèi)容是A 00HFFHB 74HC 8CH33 .某CPU中，若進位/借位標志為CF,零標志 為ZF,符號標志為SF（0表示正），溢出標志為 OF, uA和uB為無符號整數(shù)，則判定uA小于等于uB的條件是A SF=1 B SF+ZF=1 C CF=1CF+ZF=134 .目前，內(nèi)存條通常由DDR2 SDRA瞰 DDR3SDRA這片組成，該芯片為多體存儲器，能夠在總線時鐘上升沿、下降沿都傳送數(shù)據(jù)。相對基本 的SDRA這片，該類芯片提高性能采用的主要方 法是A增加數(shù)據(jù)引腳數(shù)量B減小存儲元和

12、I/O電路延遲C交叉編址，并行或交叉存取D順序編址，并行或交叉存取35 .下列虛擬存儲器的敘述中，錯誤的是A虛擬存儲器有自己的存儲陣列B虛擬存儲器需按程序邏輯地址訪問C虛擬存儲的慢表放在主存中D虛擬存儲的快表結(jié)構(gòu)類似于Cache36 .下列選項中，與CPU時鐘周期相同的是A CPU周期B機器周期C節(jié)拍周期D節(jié)拍脈沖37 .某同步總線的總線寬度為16位，每次數(shù)據(jù)傳 輸需2個總線時鐘周期，若希望總線帶寬達到 1064MB/S,則總線時鐘的頻率至少是A 133MHz B 266MHz C 532MHz D1064MHz38 .下列總線仲裁方法中，仲裁過程不需要主設(shè) 備參與的是A鏈式查詢B獨立請求C分

13、布式仲裁D計數(shù)器定時查詢39 .某磁盤有1800個磁道，每個磁道有120個扇 區(qū)，每個扇區(qū)可以記錄2KB的信息，若磁盤機的 轉(zhuǎn)速為5400轉(zhuǎn)/分鐘，則該磁盤的最大數(shù)據(jù)傳輸 率為A 2.73MB/SB 19.33MB/sC20.60MB/SD 22.12MB/S40.Intel 8086 CPU 采用向量方式處理中斷和異 常，支持多個可屏蔽中斷向量，可以屏蔽中斷請 求及響應(yīng)引腳為INTR及而a,則CPURI用的可屏 蔽中斷源識別方法是A軟件查詢B串行判優(yōu)C并行判優(yōu)D無法確定二、綜合應(yīng)用題（4147題，共70分）41（9分）頁式內(nèi)存管理系統(tǒng)中，邏輯地址為24位，頁面大小為512B,采用兩極頁表結(jié)構(gòu)

14、，頁 表中的每一項占2B。該系統(tǒng)中訪問一次內(nèi)存的時間為250ns,不考慮其他環(huán)節(jié)所用的時間。請回答下列問題：1）邏輯地址中，用于表示外層頁表（outer page table）、頁號和頁內(nèi)偏移量的位數(shù)分別是多 少？2）簡要描述該頁式內(nèi)存管理系統(tǒng)的邏輯地址到 物理地址的轉(zhuǎn)換過程3）訪問一個邏輯地址需要多長時間42（9分）一個系統(tǒng)中共存在 A、B、G D四類資 源，有P0到P3四個進程，系統(tǒng)在某一時刻的資 源分配情況如下表所示：MaxAllocationAvailableABCDABCDABCDP0601240013211P117501100P223561054P316530633請回答下列問題：

15、1）死鎖產(chǎn)生的四個條件分別是什么？2）需求（Need）矩陣的內(nèi)容是怎樣的?3）系統(tǒng)是否處于安全狀態(tài)？為什么？43（10分）假設(shè)緩沖區(qū)buf最多可存放n個數(shù)據(jù)， 進程P1往buf中寫數(shù)據(jù)，當buf中數(shù)據(jù)多于m 個時允許進程P2從中取數(shù)據(jù)，m小于n,均為正 數(shù)，試用信號量實現(xiàn)P1和P2之間的同步44（10分）設(shè)散列表HT的存儲空間是一個從0開 始的一位數(shù)組，裝填（載）因子為0.6,散列函數(shù) 為H（key尸key MOD 7。現(xiàn)將關(guān)鍵字序列（8,19,12,17,13,20） 散列存儲到HT中，處理沖 突采用線性探測法。回答下列問題：1）請畫出所構(gòu)造的散列表2）分別計算等概率的情況下，查找成功和查找

16、不 成功的平均查找長度45（11分）令A(yù)是具有n個元素的一維數(shù)組，x是 A中的一個元素，若A中有一半以上的元素與x 相同，則稱x是A的主元素。例如：若數(shù)組A為 'a', 'c', 'a', 'b', 'a', d, 'a' ,則 存在主元素a;若數(shù)組A為 'a', 'd', 'b', 'c', 'b', 'd', 'a' ,則A中不存在主元素。試設(shè)計算法，判斷A中是否存在主元素，若存在則給

17、出其主元素。請簡要說明算法的設(shè)計思想，用 C 或C+吾言給出算法，并請說明算法的時間、空 間復(fù)雜度46（10分）某計算機主存按字節(jié)編址、地址空間 為32位；Cache數(shù)據(jù)區(qū)容量為1MB采用4路組 相聯(lián)映射方式、LRUT換算法、寫回法寫策略， 塊大小為32BL請回答下列問題：1） 6che共有多少個組？ Cache行（塊）包含目錄 表項及塊數(shù)據(jù)區(qū)兩部分，Cache行的大小至少 為多少位？2）若CPU存地址為00463050H 命中時Cache 的組號是多少？命中時Cache行的標記字段 的值是多少？（用二進制表示）3）某C語言程序段為“ int i, A512; for （i=0; i <

18、 512; i+=2）; Ai+=Ai+1;"，若編譯時sizeof（int）=4 , i分配在寄存器中，A 分配在基址為00000060H的連續(xù)主存空間中。 執(zhí)行該程序段時，訪問數(shù)組A共多少次？若僅 考慮數(shù)組A的訪存情況，Cache的命中率是多 少？寫出計算過程。47(11分)某8位計算機的存儲器按字節(jié)編址，地址空間為8位。下圖所示的是該機指令系統(tǒng)的 指令格式，以及CPlft部與數(shù)據(jù)通路相關(guān)的結(jié)構(gòu)。指令格式中，格式1指令功能為：R (Rd) OP1(Rs)或 Rd (Rd) OP1 (Rs) , Rs、Rd表示寄 存器，(Ry)表示寄存器Ry的內(nèi)容，岡 表示存儲 單元x的內(nèi)容，OP

19、1=000 001、010分別表示加法、算術(shù)左移、算術(shù)右移操作，移位位數(shù)放在 Rs中。格式2指令為雙字長指令，OP2=1000 1001、1010分別表示賦值、取數(shù)、存數(shù)操作， Rs/Rd表示源或目的寄存器)Imme/Address表示 立即數(shù)或存儲單元結(jié)構(gòu)。CPU吉構(gòu)中，數(shù)據(jù)通路為單總線結(jié)構(gòu)，R0R3 為通用寄存器(編號為03),寄存器間的數(shù)據(jù)傳 送操作和AL啟算操作均需一個時鐘周期，訪存 操作采用同步控制方式、需2個時鐘周期，請回 答下列問題：1）若（IR尸A8H ,寫出該指令的操作、源操作數(shù)尋 址方式2）某C語言語句為“y=y*8"，若變量y的存儲單 元地址為23H,寫出實現(xiàn)該

20、語句功能的指令串。 （通用寄存器可任意使用）3） CPU取指并譯碼后，若IR中指令為：RA （R3）+（R2）,則該指令執(zhí)行階段至少需要幾 個時鐘周期？（可以用文字或微操作步序列描 述）答案：（若是發(fā)現(xiàn)答案中有錯的或者不確定的最好跟其他同學(xué)多討論討論 ）1-10B A D B D C B D C B11-20 21-30 31-4041.41. a分）頁式內(nèi)存管理第統(tǒng)中1U輯地址為M位，如M大小為51ap【字節(jié)）.采用兩繳 貫表結(jié)構(gòu).貫表中的組二季占陽。該系統(tǒng)中訪百？內(nèi)存的時也型如，小號忠只他。邛 所用的時間；畫卷豆問號1 Haq I1）邏輯地/石瓦T赤弛層頁表（Outerpe （able）,

21、頁號和立內(nèi)閘將金油鑰十熱磊翻鷹里呼嬋麟鱷然卷展:黑3）訪問一個港輯地址需要著長時間?42.(1)互斥、循環(huán)等待、占有并等待（請求和保持）、非搶占（不剝奪）(2)Need=Max-AllocationP3165306331020(3)不是安全狀態(tài)，因為找不到安全序列，也就是找不到某種進程推進順序，使得每個進程都可順序地完成o43.Semaphore empty = n, full = -m, mutex = 1;Fl；-P2： *while Ctru喇- Lwhi.lt? (true) * kwait; wait (full);.wait (Diitpx);wait(mutex);*put a

22、data into buffer;get a data into buffer;signal (nybex.):.signal riiitc5);-signal(full):一signal (einptv)；.1 * 44.裝填因子0.6,關(guān)鍵字個數(shù)6個，則散列表長度為6/0.6=10 ,地址為098%7=1 19%7=5 12%7=5 17%7=3 13%7=6 20%7=散歹U表為：012345678981719121320ASLsucc=(1+1+2+1+2+3)/6=10/6=5/3ASLunsucc=(1+2+1+2+1+5+4)/7=16/7 45.，域定十0A 4+謖內(nèi)i小AM王

23、力集葉翻名由uunc,。7&tawf：發(fā)弟-于九£.芳宗生無第 "小十3蕓米芝卬卬46. Cache地址為：組號13位、組內(nèi)塊號2位、 塊內(nèi)地址5位。則Cache有2的13次方個組=8192 個組。亡：-;y"unt占=04制W" j 博取WQJ為幺而東夕珞外教.根愛心標拿與常次卻卷卷丹寸寂3葉秋乂什率（上，51克全告可本走.char function（ char a口，int n）int count = 0;int mainSub = 0;char mainElement = a0;count+;for ( int i=1;i< n;i+

24、)if ( ai = mainElement) count+;elsecount-;if (count = 0)mainElement = amainSub+; count+;count = 0;for ( int i=0;i< n;i+)if ( ai = mainElement)count+;if (count > n/2)return mainElement;else return '0' ;主存地址為：區(qū)號14位、區(qū)內(nèi)塊號13位、塊內(nèi) 地址5位。Cache行由目錄表項和數(shù)據(jù)區(qū)兩部分， 目錄表項位數(shù)為：14+2 (LRU位)+1 (標記位) +1 (寫回法臟位)=18位。數(shù)據(jù)區(qū)