2014年?yáng)|南大學(xué)計(jì)算機(jī)專業(yè)考研真題

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

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

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

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

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

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

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

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

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

10、諾依曼模型計(jì)算機(jī)中存放指令地址的寄 存器是A PCB IRC MARDMDR30. 某計(jì)算機(jī)中各種指令的CPI平均為8, CPU采 用5級(jí)流水方式執(zhí)行指令，流水線每拍為2個(gè)時(shí) 鐘周期。執(zhí)行程序A時(shí)，共執(zhí)行2000條指令， 此時(shí)流水線的加速比約為A 4.0B 5.0C 8.0D10.031. 下列奇偶校驗(yàn)碼中，若有一個(gè)存在錯(cuò)誤，則 它是A 10001001 B 01001101 C 11010110D 1000010132. 某16位計(jì)算機(jī)中，存儲(chǔ)器按字節(jié)編址，整數(shù)用補(bǔ)碼表示。數(shù)據(jù)在存儲(chǔ)器中采用小端次序存 放，若 X,Y,Z 為整數(shù)，且 X=-41，Y=+75 Z=X-Y，Z存放在地址為A和A+

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

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

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

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

15、0分）假設(shè)緩沖區(qū)buf最多可存放n個(gè)數(shù)據(jù)， 進(jìn)程P1往buf中寫數(shù)據(jù)，當(dāng)buf中數(shù)據(jù)多于m 個(gè)時(shí)允許進(jìn)程P2從中取數(shù)據(jù)，m小于n，均為正 數(shù)，試用信號(hào)量實(shí)現(xiàn)P1和P2之間的同步44（10分）設(shè)散列表HT的存儲(chǔ)空間是一個(gè)從0開 始的一位數(shù)組，裝填（載）因子為0.6，散列函數(shù) 為H（key）=key MOD 7?，F(xiàn)將關(guān)鍵字序列 （8,19,12,17,13,20） 散列存儲(chǔ)到HT中，處理沖 突采用線性探測(cè)法?；卮鹣铝袉栴}：1）請(qǐng)畫出所構(gòu)造的散列表2）分別計(jì)算等概率的情況下，查找成功和查找不 成功的平均查找長(zhǎng)度45（11分）令A(yù)是具有n個(gè)元素的一維數(shù)組，x是 A中的一個(gè)元素，若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中不存在主元素。試設(shè) 計(jì)算法，判斷A中是否存在主兀素，若存在則給出其主元素。請(qǐng)簡(jiǎn)要說明算法的設(shè)計(jì)思想，用C或C+吾言給出算法，并請(qǐng)說明算法的時(shí)間、空 間復(fù)雜度46（10分）某計(jì)算機(jī)主存按字節(jié)編址、地址空間為32位；Cache數(shù)據(jù)區(qū)容量為1MB采用4路組相聯(lián)映射方式、LRU替換算法、寫回法寫策略， 塊大小為32氏請(qǐng)回答下列問題：1）Qche共有多少個(gè)組？ Cache行（塊）包含目錄 表項(xiàng)及塊數(shù)據(jù)區(qū)兩部分，Cache行的大小至少 為多少位？2）若CPU訪存

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

18、0P2235610541302Need=Max-AllocationP3165306331020(3)不是安全狀態(tài)，因?yàn)檎也坏桨踩蛄?，也就是找不到某種進(jìn)程推進(jìn)順序，使得每個(gè)進(jìn)程都可順序地完成。43.Semaphore empty = n, full = -m, mutex = 1;裝填因子0.6，關(guān)鍵字個(gè)數(shù)6個(gè)，則散列表長(zhǎng)度為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.卑也進(jìn)q】戍果* j譴巾丄汕親詢胃無(wú)朮寸戴瓦曲5如叫j uuAOf； i 5 T t A ft. 5?4i t. Mi*#rt 襯，誘本壬皿碩一 ；歲心gzt芒=0軌肅A 檢戟44城ZJ3的敘桜麥拓玨葩總菱押翅也小i電聲計(jì)區(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地址為：組號(hào)13位、組內(nèi)塊號(hào)2位、塊內(nèi)地址5位。則Cache有 2的13次方個(gè)組=8192個(gè)組 主存地址為：區(qū)號(hào)14位、區(qū)內(nèi)塊號(hào)13位、塊內(nèi) 地址5位。Cache行由目錄表項(xiàng)和數(shù)據(jù)區(qū)兩部分， 目錄表項(xiàng)位數(shù)為：14+2( LRU位)+1 (標(biāo)記位) +1 (寫回法臟位)=18位。數(shù)據(jù)區(qū)為32*8位=256位。貝V Cache行大小至少 有 18+256=274位。(2) 0000 0000 0100 0110 0011 0000 0101 0000, 則10