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

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

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

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

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

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

6、各種操作C提高磁盤的I/O速度D訪問數(shù)據時實現(xiàn)從邏輯結構到物理結構的轉換16. 下列文件的物理結構中，可能帶來外部碎片問題的是A連續(xù)結構B鏈接結構C索引結構D Hash結構17. 下列選項中，不屬于算法的主要特征的是A有窮性B可行性C確定性D可讀性18. 若一個棧 S 的入棧序列為0,123,4,5,6,7,8,9，對于下列序列，S的可能出棧序列是1. 568,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僅IB僅IIC僅I和IIID僅II和IV19. 對任意一個給定的二叉

7、樹進行前序、中序和 后序遍歷可得到三個遍歷序列。下列有關這三個 遍歷序列的敘述中，正確的是I葉子結點在三個遍歷序列中先后次序是一樣的II. 兄弟結點在三個遍歷序列中先后次序是一樣的III. 父子結點在三個遍歷序列中先后次序是一 樣的IV. 祖先和子孫結點在三個遍歷序列中先后次序 是一樣的A僅I和IIB僅III和IVC僅I和IIID僅II和IV20. 下列選項中，不可能是任何二叉搜索樹的前序遍歷序列的是A 4,2,3,5,6,7B 4,3,2,7,6,5C 6,5,423,7D 6,5,3,42721. 用n（n大于等于2）個權值均不相同的字符構 成哈夫曼樹，下列關于該樹的敘述中錯誤的是A樹中一

8、定沒有度為1的結點B該樹一定是一棵完全二叉樹C樹中兩個權值最小的結點一定是兄弟結點D樹中任一非葉子結點的權值一定不小于其任一 子節(jié)點的權值22. 無向圖G如下圖所示，下列選項中，不可能 是G的廣度優(yōu)先遍歷序列的是A 0,123,4,5“B 021,3,4,5LC 0,1,2,3,5,4D 0,321,5,423. 下列關于圖的敘述中，正確的是A強連通有向圖的任何頂點到其他所有頂點都有 弧B圖與樹的區(qū)別在于圖的邊樹大于等于頂點數(shù)C有向圖的遍歷不可采用廣度優(yōu)先遍歷方法D帶權無向圖G中，若所有邊的權值均不相同，則G的最小生成樹是唯一的24. 若排序過程中出現(xiàn)這種情況，在最后一遍開 始之前，所有元素都

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

10、諾依曼模型計算機中存放指令地址的寄 存器是A PCB IRC MARDMDR30. 某計算機中各種指令的CPI平均為8, CPU采 用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ù)據在存儲器中采用小端次序存 放，若 X,Y,Z 為整數(shù)，且 X=-41，Y=+75 Z=X-Y，Z存放在地址為A和A+

11、1存儲單元中，則存儲單 元A的內容是A 00HB 74HC 8CHDFFH33. 某CPU中，若進位/借位標志為CF,零標志 為ZF，符號標志為SF（O表示正），溢出標志為 OF, uA和uB為無符號整數(shù)，則判定uA小于等 于uB的條件是A SF=1B SF+ZF=1 C CF=1DCF+ZF=134.目前，內存條通常由DDR2 SDRAMSSDRAMS片組成，該芯片為多體存儲器，能夠在的SDRAMS片，該類芯片提高性能采用的主要方 法是A增加數(shù)據引腳數(shù)量B減小存儲元和I/O電路延遲C交叉編址，并行或交叉存取D順序編址，并行或交叉存取35. 下列虛擬存儲器的敘述中，錯誤的是A虛擬存儲器有自己的

12、存儲陣列B虛擬存儲器需按程序邏輯地址訪問C虛擬存儲的慢表放在主存中D虛擬存儲的快表結構類似于Cache36. 下列選項中，與CPU主時鐘周期相同的是A CPU周期B機器周期C節(jié)拍周期D節(jié)拍脈沖37. 某同步總線的總線寬度為16 位,每次數(shù)據傳 輸需2個總線時鐘周期，若希望總線帶寬達到 1064MB/S,則總線時鐘的頻率至少是A 133MHz B 266MHz C 532MHz D 1064MHz38. 下列總線仲裁方法中，仲裁過程不需要主設 備參與的是A鏈式查詢B獨立請求C分布式仲裁D計數(shù)器定時查詢39. 某磁盤有1800個磁道，每個磁道有120個扇 區(qū)，每個扇區(qū)可以記錄2KB的信息，若磁盤機

13、的 轉速為5400轉/分鐘，則該磁盤的最大數(shù)據傳輸 率為A 2.73MB/SB 19.33MB/SC20.60MB/SD 22.12MB/S4O.lntel 8086 CPU 采用向量方式處理中斷和異 常，支持多個可屏蔽中斷向量，可以屏蔽中斷請 求及響應引腳為INTR及INTA，則CPU采用的可屏 蔽中斷源識別方法是A軟件查詢B串行判優(yōu)C并行判優(yōu)D無法確定二、綜合應用題（4147題，共70分）41（9分）頁式內存管理系統(tǒng)中，邏輯地址為24位，頁面大小為512B,采用兩極頁表結構，頁 表中的每一項占2B。該系統(tǒng)中訪問一次內存的時間為250ns,不考慮其他環(huán)節(jié)所用的時間。請 回答下列問題：1）邏輯

14、地址中，用于表示外層頁表（outer page table）、頁號和頁內偏移量的位數(shù)分別是多 少？2）簡要描述該頁式內存管理系統(tǒng)的邏輯地址到 物理地址的轉換過程3）訪問一個邏輯地址需要多長時間42（9分）一個系統(tǒng)中共存在A B、C、D四類資 源，有P0到P3四個進程，系統(tǒng)在某一時刻的資 源分配情況如下表所示：MaxAllocati onAvailableABCDABCDABCDP0601240013211P117501100P223561054P316530633請回答下列問題:1）死鎖產生的四個條件分別是什么？2）需求（Need）矩陣的內容是怎樣的?3）系統(tǒng)是否處于安全狀態(tài)？為什么？43（1

15、0分）假設緩沖區(qū)buf最多可存放n個數(shù)據， 進程P1往buf中寫數(shù)據，當buf中數(shù)據多于m 個時允許進程P2從中取數(shù)據，m小于n，均為正 數(shù)，試用信號量實現(xiàn)P1和P2之間的同步44（10分）設散列表HT的存儲空間是一個從0開 始的一位數(shù)組，裝填（載）因子為0.6，散列函數(shù) 為H（key）=key MOD 7?，F(xiàn)將關鍵字序列 （8,19,12,17,13,20） 散列存儲到HT中，處理沖 突采用線性探測法?；卮鹣铝袉栴}：1）請畫出所構造的散列表2）分別計算等概率的情況下，查找成功和查找不 成功的平均查找長度45（11分）令A是具有n個元素的一維數(shù)組，x是 A中的一個元素，若A中有一半以上的元素與

16、x 相同，則稱x是A的主元素。例如：若數(shù)組A為 a c a b a d a ，則 存在主元素a；若數(shù)組A為 a d b c b， d a ，則A中不存在主元素。試設 計算法，判斷A中是否存在主兀素，若存在則給出其主元素。請簡要說明算法的設計思想，用C或C+吾言給出算法，并請說明算法的時間、空 間復雜度46（10分）某計算機主存按字節(jié)編址、地址空間為32位；Cache數(shù)據區(qū)容量為1MB采用4路組相聯(lián)映射方式、LRU替換算法、寫回法寫策略， 塊大小為32氏請回答下列問題：1）Qche共有多少個組？ Cache行（塊）包含目錄 表項及塊數(shù)據區(qū)兩部分，Cache行的大小至少 為多少位？2）若CPU訪存

17、地址為00463050H 命中時Cache 的組號是多少？命中時Cache行的標記字段 的值是多少？（用二進制表示）3）某C語言程序段為“ int i , A512; for （i=0; i .貞號和頁內襯甬希抽如剔是多加 盍外嚴屯殳加坷捱血鼻鮒冉及愿島狛墾殳界時拒的噸址直2）簡耍描述該賀式內存槪理系統(tǒng)的逵輯地免到物理蚯址的羈換過程.gg r 止曲曲理3）訪阿-個彌甌需要多長時剛 WIRE事如嗎紗一昭氓的吐.42.（1） 持）、互斥、循環(huán)等待、占有并等待（請求和保 非搶占（不剝奪）MaxAllocati onNeedABCDABCDABCDP0601240012011P117501100065

18、0P2235610541302Need=Max-AllocationP3165306331020(3)不是安全狀態(tài)，因為找不到安全序列，也就是找不到某種進程推進順序，使得每個進程都可順序地完成。43.Semaphore empty = n, full = -m, mutex = 1;裝填因子0.6，關鍵字個數(shù)6個，則散列表長度為6/0.6=10，地址為098%7=1 19%7=5 12%7=5 17%7=3 13%7=6 20%7= 散列表為：012345678981719121320ASLsucc=(1+1+2+1+2+3)/6=10/6=5/3ASLu nsucc=(1+2+1+2+1+5

19、+4)/7=16/745.卑也進q】戍果* j譴巾丄汕親詢胃無朮寸戴瓦曲5如叫j uuAOf； i 5 T t A ft. 5?4i t. Mi*#rt 襯，誘本壬皿碩一 ；歲心gzt芒=0軌肅A 檢戟44城ZJ3的敘桜麥拓玨葩總菱押翅也小i電聲計區(qū)k牟也込玄卻|帛丑char function( char a, int n)int count = 0;int mainSub = 0;char main Eleme nt =a0;cou nt+;for ( int i=1;i n;i+)if ( ai = mainElement) count+;elsecou nt-;if (count = 0

20、)main Eleme nt = ama in Sub+;cou nt+;cou nt = 0;for ( int i=0;i n/2)return mai nEleme nt;elsereturn 0;46.(1) Cache地址為：組號13位、組內塊號2位、塊內地址5位。則Cache有 2的13次方個組=8192個組 主存地址為：區(qū)號14位、區(qū)內塊號13位、塊內 地址5位。Cache行由目錄表項和數(shù)據區(qū)兩部分， 目錄表項位數(shù)為：14+2( LRU位)+1 (標記位) +1 (寫回法臟位)=18位。數(shù)據區(qū)為32*8位=256位。貝V Cache行大小至少 有 18+256=274位。(2) 0000 0000 0100 0110 0011 0000 0101 0000, 則10