東南大學(xué)計(jì)算機(jī)專(zhuān)業(yè)考研真題

1、2014年?yáng)|南大學(xué)計(jì)算機(jī)專(zhuān)業(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ì)一的線(xiàn)程模型中，一個(gè)多線(xiàn)程中的某個(gè)線(xiàn)程執(zhí)行一個(gè)需阻塞的系統(tǒng)調(diào)用時(shí)，下列選項(xiàng)中正確的是A整個(gè)進(jìn)程都將被阻塞B該進(jìn)程的其他線(xiàn)程仍可繼續(xù)執(zhí)行C該阻塞線(xiàn)程將被撤銷(xiāo)D該阻塞線(xiàn)程將阻塞直到進(jìn)程退出3.采用多道程序設(shè)計(jì)技術(shù)能提高整個(gè)計(jì)算機(jī)系統(tǒng)的效率，其基本條件是A硬盤(pán)容量大B處理器執(zhí)行指令速度快C外圍設(shè)備多D系統(tǒng)具有處理器與外設(shè)并行工作的能力4.下列指令中，不是特權(quán)指令的是A I/O指令B讀取當(dāng)前時(shí)鐘C設(shè)置基

2、址寄存器D關(guān)閉中斷5.在存儲(chǔ)管理中，外部碎片指的是A存儲(chǔ)分配完成所剩的空閑區(qū)B沒(méi)有被使用的存儲(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)于Round Robin調(diào)度算法，以下說(shuō)法正確的是I.同樣的情況下，時(shí)間片越大，平均周轉(zhuǎn)時(shí)間越小II.FCFS算法是Round Robin算法的一種特殊情況III.只有實(shí)現(xiàn)了定時(shí)的機(jī)制，才能實(shí)現(xiàn)Round Robin算法IV.Round Robin屬于非搶占調(diào)度算法A僅I和IIB僅II和IIIC僅III和

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

4、IB僅III和IVC僅II和IVD僅I和III12.一個(gè)請(qǐng)求分頁(yè)存儲(chǔ)管理系統(tǒng)中，假設(shè)分配給某作業(yè)的頁(yè)框(Frame)數(shù)為3，該作業(yè)的頁(yè)引用序列為0,2,1,3,0,2,4,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(n>2)個(gè)進(jìn)程，若進(jìn)程調(diào)度程序當(dāng)前沒(méi)有執(zhí)行，則以下情形不可能發(fā)生的是A有一個(gè)運(yùn)行進(jìn)程，沒(méi)有就緒進(jìn)程，剩下的n-1個(gè)進(jìn)程處于等待狀態(tài)B有一個(gè)運(yùn)行進(jìn)程和一個(gè)就緒進(jìn)程，剩下的n-2個(gè)進(jìn)程處于等待狀態(tài)C沒(méi)

5、有運(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)程，沒(méi)有進(jìn)程處于等待狀態(tài)14.關(guān)于短作業(yè)優(yōu)先(SJF)調(diào)度算法，下列說(shuō)法正確的是I.SJF算法能得到最優(yōu)的平均等待時(shí)間II.SJF算法能得到最優(yōu)的平均響應(yīng)時(shí)間III.SJF算法可能產(chǎn)生”饑餓”(Starvation)現(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ì)文件的各種操作C提高磁盤(pán)的I/O速度D訪(fǎng)問(wèn)數(shù)據(jù)時(shí)實(shí)現(xiàn)從邏輯結(jié)構(gòu)到物理結(jié)構(gòu)的轉(zhuǎn)換16.下列文件的物理結(jié)構(gòu)中，可能帶

6、來(lái)外部碎片問(wèn)題的是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,1,2,3,4,5,6,7,8,9，對(duì)于下列序列，S的可能出棧序列是I.5,6,8,7,2,1,4,3,0,9II.0,2,1,6,5,8,7,4,3,9III.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è)給定的二叉樹(shù)進(jìn)行前序、中序和后序遍歷可得到三個(gè)遍歷序列。下列有關(guān)這三個(gè)遍歷序列的敘述中，正確的是I.葉子結(jié)點(diǎn)在三個(gè)遍歷序列中先后

7、次序是一樣的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)中，不可能是任何二叉搜索樹(shù)的前序遍歷序列的是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)個(gè)權(quán)值均不相同的字符構(gòu)成哈夫曼樹(shù)，下列關(guān)于該樹(shù)的敘述中錯(cuò)誤的是A樹(shù)中一定沒(méi)有度為1的結(jié)點(diǎn)B該樹(shù)一定是一棵完全二叉樹(shù)C樹(shù)中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)D樹(shù)中任一非葉子結(jié)點(diǎn)的權(quán)值一定不小于其任一子節(jié)

8、點(diǎn)的權(quán)值22.無(wú)向圖G如下圖所示，下列選項(xiàng)中，不可能是G的廣度優(yōu)先遍歷序列的是A 0,1,2,3,4,5B 0,2,1,3,4,5C 0,1,2,3,5,4D 0,3,2,1,5,423.下列關(guān)于圖的敘述中，正確的是A強(qiáng)連通有向圖的任何頂點(diǎn)到其他所有頂點(diǎn)都有弧B圖與樹(shù)的區(qū)別在于圖的邊樹(shù)大于等于頂點(diǎn)數(shù)C有向圖的遍歷不可采用廣度優(yōu)先遍歷方法D帶權(quán)無(wú)向圖G中，若所有邊的權(quán)值均不相同，則G的最小生成樹(shù)是唯一的24.若排序過(guò)程中出現(xiàn)這種情況，在最后一遍開(kāi)始之前，所有元素都不能保證在其最終的位置上，則采用的排序算法是A冒泡排序B堆排序C快速排序D直接插入排序25.若對(duì)15個(gè)元素進(jìn)行快速排序，則元素的比較次

9、數(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ù)最多的是A 7B 6C 5 D 428.在一棵初始為空的AVL樹(shù)T中依次插入關(guān)鍵碼1,2,3,4,5,6,7的結(jié)點(diǎn)后，T的根結(jié)點(diǎn)的關(guān)鍵碼是A 3B 4 C 5 D 629.馮·諾依曼模型計(jì)算機(jī)中存放指令地址的寄存器是A PCB IRC MARD MDR30.某計(jì)算機(jī)中各種指令的CPI平均為8，CP

10、U采用5級(jí)流水方式執(zhí)行指令，流水線(xiàn)每拍為2個(gè)時(shí)鐘周期。執(zhí)行程序A時(shí)，共執(zhí)行2000條指令，此時(shí)流水線(xiàn)的加速比約為A 4.0B 5.0C 8.0D 10.031.下列奇偶校驗(yàn)碼中，若有一個(gè)存在錯(cuò)誤，則它是A 10001001B 01001101C 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+1存儲(chǔ)單元中，則存儲(chǔ)單元A的內(nèi)容是A 00HB 74HC 8CHD FFH33.某CPU中，若進(jìn)位/借位標(biāo)志為CF，零標(biāo)志為ZF，符號(hào)標(biāo)志為SF(0

11、表示正)，溢出標(biāo)志為OF，uA和uB為無(wú)符號(hào)整數(shù)，則判定uA小于等于uB的條件是A SF=1B SF+ZF=1C CF=1D CF+ZF=134.目前，內(nèi)存條通常由DDR2 SDRAM或DDR3 SDRAM芯片組成，該芯片為多體存儲(chǔ)器，能夠在總線(xiàn)時(shí)鐘上升沿、下降沿都傳送數(shù)據(jù)。相對(duì)基本的SDRAM芯片，該類(lèi)芯片提高性能采用的主要方法是A增加數(shù)據(jù)引腳數(shù)量B減小存儲(chǔ)元和I/O電路延遲C交叉編址，并行或交叉存取D順序編址，并行或交叉存取35.下列虛擬存儲(chǔ)器的敘述中，錯(cuò)誤的是A虛擬存儲(chǔ)器有自己的存儲(chǔ)陣列B虛擬存儲(chǔ)器需按程序邏輯地址訪(fǎng)問(wèn)C虛擬存儲(chǔ)的慢表放在主存中D虛擬存儲(chǔ)的快表結(jié)構(gòu)類(lèi)似于Cache36.下

12、列選項(xiàng)中，與CPU主時(shí)鐘周期相同的是A CPU周期B機(jī)器周期C節(jié)拍周期D節(jié)拍脈沖37.某同步總線(xiàn)的總線(xiàn)寬度為16位，每次數(shù)據(jù)傳輸需2個(gè)總線(xiàn)時(shí)鐘周期，若希望總線(xiàn)帶寬達(dá)到1064MB/s，則總線(xiàn)時(shí)鐘的頻率至少是A 133MHzB 266MHzC 532MHzD 1064MHz38.下列總線(xiàn)仲裁方法中，仲裁過(guò)程不需要主設(shè)備參與的是A鏈?zhǔn)讲樵?xún)B獨(dú)立請(qǐng)求C分布式仲裁D計(jì)數(shù)器定時(shí)查詢(xún)39.某磁盤(pán)有1800個(gè)磁道，每個(gè)磁道有120個(gè)扇區(qū)，每個(gè)扇區(qū)可以記錄2KB的信息，若磁盤(pán)機(jī)的轉(zhuǎn)速為5400轉(zhuǎn)/分鐘，則該磁盤(pán)的最大數(shù)據(jù)傳輸率為A 2.73MB/sB 19.33MB/sC 20.60MB/sD 22.12MB

13、/s40.Intel 8086 CPU采用向量方式處理中斷和異常，支持多個(gè)可屏蔽中斷向量，可以屏蔽中斷請(qǐng)求及響應(yīng)引腳為INTR及，則CPU采用的可屏蔽中斷源識(shí)別方法是A軟件查詢(xún)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)中訪(fǎng)問(wèn)一次內(nèi)存的時(shí)間為250ns，不考慮其他環(huán)節(jié)所用的時(shí)間。請(qǐng)回答下列問(wèn)題：1) 邏輯地址中，用于表示外層頁(yè)表(outer page table)、頁(yè)號(hào)和頁(yè)內(nèi)偏移量的位數(shù)分別是多少？2) 簡(jiǎn)要描述該頁(yè)式內(nèi)存管理系統(tǒng)的邏輯地址到物理地址的轉(zhuǎn)

14、換過(guò)程3) 訪(fǎng)問(wèn)一個(gè)邏輯地址需要多長(zhǎng)時(shí)間42(9分)一個(gè)系統(tǒng)中共存在A、B、C、D四類(lèi)資源，有P0到P3四個(gè)進(jìn)程，系統(tǒng)在某一時(shí)刻的資源分配情況如下表所示：MaxAllocationAvailableABCDABCDABCDP0601240013211P117501100P223561054P316530633請(qǐng)回答下列問(wèn)題：1) 死鎖產(chǎn)生的四個(gè)條件分別是什么？2) 需求(Need)矩陣的內(nèi)容是怎樣的？3) 系統(tǒng)是否處于安全狀態(tài)？為什么？43(10分)假設(shè)緩沖區(qū)buf最多可存放n個(gè)數(shù)據(jù)，進(jìn)程P1往buf中寫(xiě)數(shù)據(jù)，當(dāng)buf中數(shù)據(jù)多于m個(gè)時(shí)允許進(jìn)程P2從中取數(shù)據(jù)，m小于n，均為正數(shù)，試用信號(hào)量實(shí)現(xiàn)P

15、1和P2之間的同步44(10分)設(shè)散列表HT的存儲(chǔ)空間是一個(gè)從0開(kāi)始的一位數(shù)組，裝填(載)因子為0.6，散列函數(shù)為H(key)=key MOD 7。現(xiàn)將關(guān)鍵字序列(8,19,12,17,13,20)散列存儲(chǔ)到HT中，處理沖突采用線(xiàn)性探測(cè)法?；卮鹣铝袉?wèn)題：1) 請(qǐng)畫(huà)出所構(gòu)造的散列表2) 分別計(jì)算等概率的情況下，查找成功和查找不成功的平均查找長(zhǎng)度45(11分)令A(yù)是具有n個(gè)元素的一維數(shù)組，x是A中的一個(gè)元素，若A中有一半以上的元素與x相同，則稱(chēng)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中是

16、否存在主元素，若存在則給出其主元素。請(qǐng)簡(jiǎn)要說(shuō)明算法的設(shè)計(jì)思想，用C或C+語(yǔ)言給出算法，并請(qǐng)說(shuō)明算法的時(shí)間、空間復(fù)雜度46(10分)某計(jì)算機(jī)主存按字節(jié)編址、地址空間為32位；Cache數(shù)據(jù)區(qū)容量為1MB，采用4路組相聯(lián)映射方式、LRU替換算法、寫(xiě)回法寫(xiě)策略，塊大小為32B。請(qǐng)回答下列問(wèn)題：1) Cache共有多少個(gè)組？Cache行(塊)包含目錄表項(xiàng)及塊數(shù)據(jù)區(qū)兩部分，Cache行的大小至少為多少位？2) 若CPU訪(fǎng)存地址為00463050H，命中時(shí)Cache的組號(hào)是多少？命中時(shí)Cache行的標(biāo)記字段的值是多少？(用二進(jìn)制表示)3) 某C語(yǔ)言程序段為“int i , A512; for (i = 0

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

18、、010分別表示加法、算術(shù)左移、算術(shù)右移操作，移位位數(shù)放在Rs中。格式2指令為雙字長(zhǎng)指令，OP2=1000、1001、1010分別表示賦值、取數(shù)、存數(shù)操作，Rs/Rd表示源或目的寄存器，Imme/Address表示立即數(shù)或存儲(chǔ)單元結(jié)構(gòu)。CPU結(jié)構(gòu)中，數(shù)據(jù)通路為單總線(xiàn)結(jié)構(gòu)，R0R3為通用寄存器(編號(hào)為03)，寄存器間的數(shù)據(jù)傳送操作和ALU運(yùn)算操作均需一個(gè)時(shí)鐘周期，訪(fǎng)存操作采用同步控制方式、需2個(gè)時(shí)鐘周期，請(qǐng)回答下列問(wèn)題：1) 若(IR)=A8H，寫(xiě)出該指令的操作、源操作數(shù)尋址方式2) 某C語(yǔ)言語(yǔ)句為“y=y*8”，若變量y的存儲(chǔ)單元地址為23H，寫(xiě)出實(shí)現(xiàn)該語(yǔ)句功能的指令串。(通用寄存器可任意使用

19、)3) CPU取指并譯碼后，若IR中指令為：R3(R3)+(R2)，則該指令執(zhí)行階段至少需要幾個(gè)時(shí)鐘周期？(可以用文字或微操作步序列描述)答案：（若是發(fā)現(xiàn)答案中有錯(cuò)的或者不確定的最好跟其他同學(xué)多討論討論）1-10 B A D B D C B D C B11-20 C A C A C A D B A D21-30 B C D D B C C B A A31-40 B C D C A C D B D B41.42.（1）互斥、循環(huán)等待、占有并等待（請(qǐng)求和保持）、非搶占（不剝奪）（2）Need=Max-AllocationMaxAllocationNeedABCDABCDABCDP060124001

20、2011P1175011000650P2235610541302P3165306331020（3）不是安全狀態(tài)，因?yàn)檎也坏桨踩蛄?，也就是找不到某種進(jìn)程推進(jìn)順序，使得每個(gè)進(jìn)程都可順序地完成。43.Semaphore empty = n, full = -m, mutex = 1;44.裝填因子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=6散列表為：012345678981719121320ASLsucc=(1+1+2+1+2+3)/6=10/6=5/3ASLunsucc=(1+2+1+2+1+5

21、+4)/7=16/745.char function(char a,int n)int count = 0;int mainSub = 0;char mainElement = a0;count+;for (int i=1;i<n;i+)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;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（寫(xiě)回法臟位）=18位。數(shù)據(jù)區(qū)為32*8位=256位。則Ca