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

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

2、址寄存器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.關于Round Robin調度算法，以下說法正確的是I.同樣的情況下，時間片越大，平均周轉時間越小II.FCFS算法是Round Robin算法的一種特殊情況III.只有實現了定時的機制，才能實現Round Robin算法IV.Round Robin屬于非搶占調度算法A僅I和IIB僅II和IIIC僅III和

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

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

5、有運行進程，有一個就緒進程，剩下的n-1個進程處于等待狀態(tài)D有一個運行進程和n-1個就緒進程，沒有進程處于等待狀態(tài)14.關于短作業(yè)優(yōu)先(SJF)調度算法，下列說法正確的是I.SJF算法能得到最優(yōu)的平均等待時間II.SJF算法能得到最優(yōu)的平均響應時間III.SJF算法可能產生”饑餓”(Starvation)現象IV.SJF算法是一種實際系統(tǒng)中常用的CPU調度算法A僅I和IIIB僅II和IVC僅I和IVD僅II和III15.下列選項中，不是文件系統(tǒng)應具備的功能的是A對文件按名存取B實現對文件的各種操作C提高磁盤的I/O速度D訪問數據時實現從邏輯結構到物理結構的轉換16.下列文件的物理結構中，可能帶

6、來外部碎片問題的是A連續(xù)結構B鏈接結構C索引結構D Hash結構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,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.對任意一個給定的二叉樹進行前序、中序和后序遍歷可得到三個遍歷序列。下列有關這三個遍歷序列的敘述中，正確的是I.葉子結點在三個遍歷序列中先后

7、次序是一樣的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,4,2,3,7D 6,5,3,4,2,721.用n(n大于等于2)個權值均不相同的字符構成哈夫曼樹，下列關于該樹的敘述中錯誤的是A樹中一定沒有度為1的結點B該樹一定是一棵完全二叉樹C樹中兩個權值最小的結點一定是兄弟結點D樹中任一非葉子結點的權值一定不小于其任一子節(jié)

8、點的權值22.無向圖G如下圖所示，下列選項中，不可能是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.下列關于圖的敘述中，正確的是A強連通有向圖的任何頂點到其他所有頂點都有弧B圖與樹的區(qū)別在于圖的邊樹大于等于頂點數C有向圖的遍歷不可采用廣度優(yōu)先遍歷方法D帶權無向圖G中，若所有邊的權值均不相同，則G的最小生成樹是唯一的24.若排序過程中出現這種情況，在最后一遍開始之前，所有元素都不能保證在其最終的位置上，則采用的排序算法是A冒泡排序B堆排序C快速排序D直接插入排序25.若對15個元素進行快速排序，則元素的比較次

9、數至少是A 26B 34C 52D 7826.對序列14,9,7,10,20,1,5進行排序，若第一趟后的數據排列為5,9,1,10,20,7,14，則采用的排序算法是A選擇排序B歸并排序C希爾排序D冒泡排序27.對一個長度為16的有序表，若采用折半查找法查找一個表中不存在的元素，則比較次數最多的是A 7B 6C 5 D 428.在一棵初始為空的AVL樹T中依次插入關鍵碼1,2,3,4,5,6,7的結點后，T的根結點的關鍵碼是A 3B 4 C 5 D 629.馮·諾依曼模型計算機中存放指令地址的寄存器是A PCB IRC MARD MDR30.某計算機中各種指令的CPI平均為8，CP

10、U采用5級流水方式執(zhí)行指令，流水線每拍為2個時鐘周期。執(zhí)行程序A時，共執(zhí)行2000條指令，此時流水線的加速比約為A 4.0B 5.0C 8.0D 10.031.下列奇偶校驗碼中，若有一個存在錯誤，則它是A 10001001B 01001101C 11010110D 1000010132.某16位計算機中，存儲器按字節(jié)編址，整數用補碼表示。數據在存儲器中采用小端次序存放，若X,Y,Z為整數，且X=-41，Y=+75，Z=X-Y，Z存放在地址為A和A+1存儲單元中，則存儲單元A的內容是A 00HB 74HC 8CHD FFH33.某CPU中，若進位/借位標志為CF，零標志為ZF，符號標志為SF(0

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

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

13、/s40.Intel 8086 CPU采用向量方式處理中斷和異常，支持多個可屏蔽中斷向量，可以屏蔽中斷請求及響應引腳為INTR及，則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) 邏輯地址中，用于表示外層頁表(outer page table)、頁號和頁內偏移量的位數分別是多少？2) 簡要描述該頁式內存管理系統(tǒng)的邏輯地址到物理地址的轉

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

15、1和P2之間的同步44(10分)設散列表HT的存儲空間是一個從0開始的一位數組，裝填(載)因子為0.6，散列函數為H(key)=key MOD 7。現將關鍵字序列(8,19,12,17,13,20)散列存儲到HT中，處理沖突采用線性探測法?；卮鹣铝袉栴}：1) 請畫出所構造的散列表2) 分別計算等概率的情況下，查找成功和查找不成功的平均查找長度45(11分)令A是具有n個元素的一維數組，x是A中的一個元素，若A中有一半以上的元素與x相同，則稱x是A的主元素。例如：若數組A為a，c，a，b，a，d，a，則存在主元素a；若數組A為a，d，b，c，b，d，a，則A中不存在主元素。試設計算法，判斷A中是

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

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

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

19、)3) CPU取指并譯碼后，若IR中指令為：R3(R3)+(R2)，則該指令執(zhí)行階段至少需要幾個時鐘周期？(可以用文字或微操作步序列描述)答案：（若是發(fā)現答案中有錯的或者不確定的最好跟其他同學多討論討論）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)等待、占有并等待（請求和保持）、非搶占（不剝奪）（2）Need=Max-AllocationMaxAllocationNeedABCDABCDABCDP060124001

20、2011P1175011000650P2235610541302P3165306331020（3）不是安全狀態(tài)，因為找不到安全序列，也就是找不到某種進程推進順序，使得每個進程都可順序地完成。43.Semaphore empty = n, full = -m, mutex = 1;44.裝填因子0.6，關鍵字個數6個，則散列表長度為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地址為：組號13位、組內塊號2位、塊內地址5位。則Cache有2的13次方個組=8192個組。主存地址為：區(qū)號14位、區(qū)內塊號13位、塊內地址5位。Cache行由目錄表項和數據區(qū)兩部分，目錄表項位數為：14+2（LRU位）+1（標記位）+1（寫回法臟位）=18位。數據區(qū)為32*8位=256位。則Ca