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

1、20XX年東南大學(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.下列指令中，不是特權(quán)指令的是

2、A I/O 指令 B 讀取當(dāng)前時鐘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)于 Round Robin 調(diào)度算法，以下說法正確的是I.同樣的情況下，時間片越大，平均周轉(zhuǎn)時間越小II.FCFS算法是 Round Robin 算法的一種特殊情況III.只有實現(xiàn)了定時的機制，才能實現(xiàn) Round Robin 算法IV.R

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

4、更大的磁盤用于頁面置換 II.內(nèi)存分頁管理方式不會產(chǎn)生外部碎片 III.磁盤訪問時間主要是由旋轉(zhuǎn)時延和傳輸時延組成 IV.FCFS算法可用于實現(xiàn)磁盤調(diào)度 A 僅 I 和 II B 僅 III 和 IV C僅 II 和 IV D 僅 I 和 III 12.一個請求分頁存儲管理系統(tǒng)中，假設(shè)分配給某作業(yè)的頁框(Frame)數(shù)為 3，該作業(yè)的頁引用序列為 0,2,1,3,0,2,4,0,2,1,3,4 ，所有的頁框初始時都為空，分別采用最近最少次數(shù)使用(LRU)和最優(yōu) (OPT)頁面置換算法時，產(chǎn)生頁面失效 A 10 和 7 B9和 8 C 9和 7 D7 和 4 (Page Fault)的次數(shù)分別是

5、13.單處理器系統(tǒng)中有 n(n2)個進程，若進程調(diào)度程序當(dāng)前沒有執(zhí)行，則以下情形不可能發(fā)生的是A 有一個運行進程，沒有就緒進程，剩下的 B 有一個運行進程和一個就緒進程，剩下的 C沒有運行進程，有一個就緒進程，剩下的n-1 個進程處于等待狀態(tài) n-2 個進程處于等待狀態(tài) 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)中常用

6、的 CPU調(diào)度算法A 僅 I 和 III B 僅 II 和 IV C僅 I 和 IV D 僅 II 和 III 15.下列選項中，不是文件系統(tǒng)應(yīng)具備的功能的是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,

7、0,9 II.0,2,1,6,5,8,7,4,3,9 III.2,0,1,4,3,7,8,6,5,9 IV.6,5,7,8,4,3,1,2,9,0 A 僅 I B 僅 II C僅 I 和 III D 僅 II 和 IV 19.對任意一個給定的二叉樹進行前序、中序和后序遍歷可得到三個遍歷序列。下列有關(guān)這三個遍歷序列的敘述中，正確的是I.葉子結(jié)點在三個遍歷序列中先后次序是一樣的II.兄弟結(jié)點在三個遍歷序列中先后次序是一樣的III.父子結(jié)點在三個遍歷序列中先后次序是一樣的IV.祖先和子孫結(jié)點在三個遍歷序列中先后次序是一樣的A 僅 I 和 II B 僅 III 和 IV C僅 I 和 III D 僅

8、II 和 IV 20.下列選項中，不可能是任何二叉搜索樹的前序遍歷序列的是A4,2,3,5,6,7 B 4,3,2,7,6,5 C 6,5,4,2,3,7 D 6,5,3,4,2,7 21.用 n(n 大于等于 2)個權(quán)值均不相同的字符構(gòu)成哈夫曼樹，下列關(guān)于該樹的敘述中錯誤的是A 樹中一定沒有度為 1 的結(jié)點B 該樹一定是一棵完全二叉樹C樹中兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點D 樹中任一非葉子結(jié)點的權(quán)值一定不小于其任一子節(jié)點的權(quán)值22.無向圖 G 如下圖所示，下列選項中，不可能是 A 0,1,2,3,4,5 B 0,2,1,3,4,5 C 0,1,2,3,5,4 D 0,3,2,1,5,4 23

9、.下列關(guān)于圖的敘述中，正確的是 A 強連通有向圖的任何頂點到其他所有頂點都有弧 B 圖與樹的區(qū)別在于圖的邊樹大于等于頂點數(shù) C有向圖的遍歷不可采用廣度優(yōu)先遍歷方法G 的廣度優(yōu)先遍歷序列的是D 帶權(quán)無向圖G 中，若所有邊的權(quán)值均不相同，則G 的最小生成樹是唯一的24.若排序過程中出現(xiàn)這種情況，在最后一遍開始之前，所有元素都不能保證在其最終的位置上，則采用的排序算法是A 冒泡排序 B 堆排序C快速排序 D 直接插入排序25.若對 15 個元素進行快速排序，則元素的比較次數(shù)至少是 A 26 B 34 C 52 D 78 26.對序列 14,9,7,10,20,1,5 進行排序，若第一趟后的數(shù)據(jù)排列為

10、 排序算法是A 選擇排序B 歸并排序C希爾排序D 冒泡排序5,9,1,10,20,7,14 ，則采用的27.對一個長度為 16 的有序表， 若采用折半查找法查找一個表中不存在的元素，則比較次數(shù)最多的是A 7 B 6 C 5 D 4 28.在一棵初始為空的AVL樹 T 中依次插入關(guān)鍵碼1,2,3,4,5,6,7 的結(jié)點后， T 的根結(jié)點的關(guān)鍵碼是A 3 B 4 C 5 D 6 29.馮諾依曼模型計算機中存放指令地址的寄存器是A PC B IR C MAR D MDR 30.某計算機中各種指令的 CPI平均為 8，CPU采用 5 級流水方式執(zhí)行指令，流水線每拍為 2個時鐘周期。執(zhí)行程序 A 時，共

11、執(zhí)行 2000 條指令，此時流水線的加速比約為A 4.0 B 5.0 C 8.0 D 10.0 31.下列奇偶校驗碼中，若有一個存在錯誤，則它是A 10001001 B 01001101 C 11010110 D 10000101 32.某 16 位計算機中，存儲器按字節(jié)編址，整數(shù)用補碼表示。數(shù)據(jù)在存儲器中采用小端次序存放，若 X,Y,Z 為整數(shù)，且X=-41，Y=+75，Z=X-Y，Z 存放在地址為A 和 A+1 存儲單元中，則存儲單元 A 的內(nèi)容是A 00H B 74H C 8CH D FFH CF，零標(biāo)志為ZF，符號標(biāo)志為SF(0表示正 )，溢出標(biāo)志為33.某 CPU中，若進位 / 借位

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

13、構(gòu)類似于Cache 36.下列選項中，與 CPU主時鐘周期相同的是A CPU周期 B 機器周期 C節(jié)拍周期 D 節(jié)拍脈沖37.某同步總線的總線寬度為 16 位，每次數(shù)據(jù)傳輸需 2 個總線時鐘周期，若希望總線帶寬達到 1064MB/s ，則總線時鐘的頻率至少是A 133MHz B 266MHz C 532MHz D 1064MHz 38.下列總線仲裁方法中，仲裁過程不需要主設(shè)備參與的是A 鏈?zhǔn)讲樵?B 獨立請求 C分布式仲裁 D 計數(shù)器定時查詢39.某磁盤有 1800 個磁道， 每個磁道有 120 個扇區(qū)， 每個扇區(qū)可以記錄 2KB 的信息， 若磁盤機的轉(zhuǎn)速為 5400 轉(zhuǎn)/ 分鐘，則該磁盤的最

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

15、中，用于表示外層頁表(outer page table)、頁號和頁內(nèi)偏移量的位數(shù)分別是多少？2) 簡要描述該頁式內(nèi)存管理系統(tǒng)的邏輯地址到物理地址的轉(zhuǎn)換過程3) 訪問一個邏輯地址需要多長時間42(9 分)一個系統(tǒng)中共存在 A、B、C、D 四類資源，有 P0 到 P3 四個進程，系統(tǒng)在某一時刻的資源分配情況如下表所示：P0 A B Max C D A Allocation D A Available D B C B C 6 0 1 2 4 0 0 1 P1 1 7 5 0 1 1 0 0 3 2 1 1 P2 2 3 5 6 1 0 5 4 P3 1 6 5 3 0 6 3 3 請回答下列問題：1

16、) 死鎖產(chǎn)生的四個條件分別是什么？2) 需求 (Need)矩陣的內(nèi)容是怎樣的？3) 系統(tǒng)是否處于安全狀態(tài)？為什么？43(10 分)假設(shè)緩沖區(qū) buf 最多可存放 n 個數(shù)據(jù)， 進程 P1 往 buf 中寫數(shù)據(jù)， 當(dāng) 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) 請

17、畫出所構(gòu)造的散列表2) 分別計算等概率的情況下，查找成功和查找不成功的平均查找長度45(11 分)令 A 是具有 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 中是否存在主元素，若存在則給出其主元素。請簡要說明算法的設(shè)計思想，用 C或 C+語言給出算法，并請說明算法的時間、空間復(fù)雜度46(10 分)某計算機主存按字節(jié)編址、地址空間為 32 位；

18、 Cache 數(shù)據(jù)區(qū)容量為 1MB，采用 4路組相聯(lián)映射方式、LRU替換算法、寫回法寫策略，塊大小為 32B。請回答下列問題：1) Cache共有多少個組？Cache行 (塊)包含目錄表項及塊數(shù)據(jù)區(qū)兩部分，Cache行的大小至少為多少位？2) 若 CPU訪存地址為 00463050H，命中時 Cache 的組號是多少？命中時 Cache 行的標(biāo)記字段的值是多少？(用二進制表示 ) 3) 某 C 語言程序段為“int i , A512; for (i = 0; i 512; i+=2); Ai+=Ai+1; ” ，若編譯時sizeof(int)=4 ，i 分配在寄存器中，A 分配在基址為 000

19、00060H 的連續(xù)主存空間中。執(zhí)行該程序段時，訪問數(shù)組 A 共多少次？若僅考慮數(shù)組 A 的訪存情況， Cache 的命中率是多少？寫出計算過程。47(11 分)某 8 位計算機的存儲器按字節(jié)編址，地址空間為 8 位。下圖所示的是該機指令系統(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表示存儲單元x 的內(nèi)容， OP1=000、001、010 分別表示加法、算術(shù)左移、算術(shù)右移操作， 移位位數(shù)放在Rs中。格式 2 指令為雙字長

20、指令， OP2=1000、1001、1010 分別表示賦值、取數(shù)、存數(shù)操作，Rs/Rd 表示源或目的寄存器，Imme/Address表示立即數(shù)或存儲單元結(jié)構(gòu)。CPU結(jié)構(gòu)中，數(shù)據(jù)通路為單總線結(jié)構(gòu)，R0R3為通用寄存器 (編號為 03)，寄存器間的數(shù)據(jù)傳送操作和ALU運算操作均需一個時鐘周期，訪存操作采用同步控制方式、需2 個時鐘周期，請回答下列問題：1)若(IR)=A8H，寫出該指令的操作、源操作數(shù)尋址方式23H，寫出實現(xiàn)該語句功能的指2)某 C 語言語句為“y=y*8 ” ，若變量 y 的存儲單元地址為令串。 (通用寄存器可任意使用 ) 3) CPU取指并譯碼后，若 IR 中指令為： R3(R

21、3)+(R2)，則該指令執(zhí)行階段至少需要幾個時鐘周期？ (可以用文字或微操作步序列描述 ) 答案：（若是發(fā)現(xiàn)答案中有錯的或者不確定的最好跟其他同學(xué)多討論討論 ）1-10 B A D B D C B D C B 11-20 C A C A C A D B A D 21-30 B C D D B C C B A A 31-40 B C D C A C D B D B 41. 42. （1）互斥、循環(huán)等待、占有并等待（請求和保持）（2）Need=Max-Allocation 、非搶占（不剝奪）P0 A B Max C D A Allocation D A Need D B C B C 6 0 1 2

22、 4 0 0 1 2 0 1 1 P1 1 7 5 0 1 1 0 0 0 6 5 0 P2 2 3 5 6 1 0 5 4 1 3 0 2 P3 1 6 5 3 0 6 3 3 1 0 2 0 （3）不是安全狀態(tài)，因為找不到安全序列，也就是找不到某種進程推進順序，使得每個進程都可順序地完成。43. Semaphore empty = n, full = -m, mutex = 1; 44. 裝填因子 0.6，關(guān)鍵字個數(shù)6 個，則散列表長度為6/0.6=10，地址為 09 8%7=1，19%7=5，12%7=5，17%7=3，13%7=6，20%7=6 散列表為：0 1 2 3 4 5 6 7

23、 8 9 8 17 19 12 13 20 ASLsucc=(1+1+2+1+2+3)/6=10/6=5/3 ASLunsucc=(1+2+1+2+1+5+4)/7=16/7 45. 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+; else count-; if (count = 0) mainElement = amainSub+; count+; count = 0; for ( int i=0;i n/2) return mainElement; else return 0 ; 46. （1）Cache 地址為：組號13 位、組內(nèi)塊號2 位、塊內(nèi)地址5 位。則 Cache 有 2 的 13 次方個組 =8192 個組。主存地址為：區(qū)號 14 位、區(qū)內(nèi)塊號 13 位、塊內(nèi)地址 5 位。 Cache行由目錄表項和數(shù)據(jù)區(qū)兩部分，目錄表項位數(shù)為：14+2（LRU位） +1（標(biāo)記位） +1（寫回法臟位）=18 位。數(shù)據(jù)區(qū)為 3