1、2018年全國碩士研究生入學統一考試計算機科學與技術學科聯考計算機學科專業基礎綜合試題一、單項選擇題；第140小題，每小題2分，共80分。下列每題給出的四個選項中， 只有一個選項最符合試題要求。1若棧S1中保存整數，棧S2中保存運算符，函數F()依次執行下述各步操作：從Si中依次彈出兩個操作數a和b；從S2中彈出一個運算符op；執行相應的運算b op a；將運算結果壓人S1中。 TOC o 1-5 h z 假定Si中的操作數依次是5, 8, 3, 2 (2在棧頂)，S2中的運算符依次是*，-, + (+在棧頂)。調 用3次F()后，S1棧頂保存的值是。-15B. 15C.-20D.20現有隊列

2、Q與棧S,初始時Q中的元素依次是1, 2, 3, 4, 5, 6 (1在隊頭)，S為空。若僅允許下列3種操作：出隊并輸出出隊元素；出隊并將出隊元素人棧；出棧并輸出出棧元素， 則不能得到的輸出序列是=1, 2, 5, 6, 4, 3B.2, 3, 4, 5, 6, 1C.3, 4, 5, 6, 1, 2D.6, 5, 4, 3, 2, 1設有一個12x12的對稱矩陣M,將其上三角部分的元素mi, j (1迄於12)按行優先存人C語言的一維數組N中，元素m6,6在N中的下標是。50B. 51C.55D. 66設一棵非空完全二叉樹T的所有葉結點均位于同一層，且每個非葉結點都有2個子結點。若T有k個葉

3、結點，則T的結點總數是o2k-1B. 2kC. k2D.2k-1已知字符集a, b, c, d, e, f,若各字符出現的次數分別為6, 3, 8, 2, 10, 4,則對應字符集中各字符的哈夫曼編碼可能是。00, 1011, 01, 1010, 11, 100B.00, 100, 110, 000, 0010, 01C.10, 1011, 11, 0011, 00, 010D.0011, 10, 11, 0010, 01, 000已知二叉排序樹如下圖所示，元素之間應滿足的大小關系是。&高度為5的3階B樹含有的關鍵字個數至少是。15B. 31C. 62D. 2427HTH（k） = k % 7

4、,用線性探測再散列法解決22, 43,15HT 后A. 1.5B. 1.6C. 2D. 3對初始數據序列（8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 61,3, 7, 5, 2, 6, 4, 9, 11, 10, 81, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9增量（間隔）依次是。A. 3, 1B. 3,2C. 5,2D. 5,36, 1, 5, 9, 8, 4, 7爲6,1,7,9,8,4,5 6,9,7,1,8,4,5 9,6異,1,8,4,5 9,8,7,1,6,4,56,9,5丄8,4,7 6,9,7,1,8,4,5 9,6,7,1,8,4,5

5、9,8,7,1,6,4,56,9,5,1,8,4,7 9,6,5,1,8,4,7 9,6,7丄8,4,5 9,8,7,1,6,4,56,1,7,9,8,4,5 7,1,6,9,8,4,5 7,9,6,1,8,4,5 9異,6,1,8,4,5 9,8,6,1,7,4,512.二IIJIII.A.B.C.僅 II、皿 D. I、II 和IIIintx yFFFF FFDFH 和 00000041Hx、yx-yx = -65, y = 41, x -y 於x = -33, y = 65, x-y 的機器數為 FFFF FF9DHx = -33, y = 65, x-y 的機器數為 FFFF FF9E

6、Hx = -65, y = 41, x-y 的機器數為 FFFF FF96H TOC o 1-5 h z IEEE 754單精度浮點格式表示的數中，最小的規格化正數是。A. 1.0 x2-i26B. 1.0 x2-i27C. 1.0 x2-i28D. 1.0 x2-”9某32位計算機按字節編址，采用小端(Little Endian)方式。若語令int i = 0;對應指令的機器代碼為“C7 45 FC 00 00 00 00”，則語句“int i = - 64;”對應指令的機器代碼是。A. C7 45 FC C0 FF FF FFB. C7 45 FC 0C FF FF FFC. C7 45

7、FC FF FF FF C0D. C7 45 FC FF FF FF 0C整數x的機器數為1101 1000，分別對x進行邏輯右移1位和算術右移1位操作，得到的機器數各是=A.1110 1100、 1110 1100B. 0110 1100、 1110 1100C.1110 1100、 0110 1100D. 0110 1100、 0110 1100假定DRAM芯片中存儲陣列的行數為r、列數為c,對于一個2Kx 1位的DRAM芯片，為保證其地址引腳數最少，并盡量減少刷新開銷，則r、c的取值分別是。A. 2048、1B. 64、32C. 32、64D. 1、2048按字節編址的計算機中，某dou

8、ble型數組A的首地址為2000H,使用變址尋址和循環結構訪問數組A,保存數組下標的變址寄存器初值為0,每次循環取一個數組元素，其偏移地址為 變址值乘以sizeof(double),取完后變址寄存器內容自動加1。若某次循環所取元素的地址為2100H, 則進入該次循環時變址寄存器的內容是。A. 25B. 32C. 64D. 100減法指令“subRl,R2,R3”的功能為“(R1) - (R2)的”，該指令執行后將生成進位/借位標志CF和溢出標志OF。若(R1) = FFFF FFFFH, (R2) = FFFF FFF0H,則該減法指令執行 后，CF與OF分別為。A. CF=0, OF=0B.

9、 CF=1, OF=0C. CF=0, 0F=1D. CF=1, OF=1若某計算機最復雜指令的執行需要完成5個子功能，分別由功能部件AE實現，各功能部件所需時間分別為80ps、50ps、50ps、70ps和50ps,采用流水線方式執行指令，流水段寄存器 延時為20ps,則CPU時鐘周期至少為。A. 60 psB. 70 psC. 80 psD. 100 ps下列選項中，可提高同步總線數據傳輸率的是。.增加總線寬度II .提高總線工作頻率III.支持突發傳輸IV.采用地址/數據線復用A.僅 I、IIB.僅 I、II、IIIc.僅m、ivd. I、ii、iii和iv下列關于外部I/O中斷的敘述中

10、，正確的是。中斷控制器按所接收中斷請求的先后次序進行中斷優先級排隊CPU響應中斷時，通過執行中斷隱指令完成通用寄存器的保護CPU只有在處于中斷允許狀態時，才能響應外部設備的中斷請求有中斷請求時，CPU立即暫停當前指令執行，轉去執行中斷服務程序下列關于多任務操作系統的敘述中，正確的是。具有并發和并行的特點需要實現對共享資源的保護III.需要運行在多CPU的硬件平臺上A.僅 IB.僅 IIC.僅 I、IID. I、II、HI24.某系統采用基于優先權的非搶占式進程調度策略，完成一次進程調度和進程切換的系統 時間開銷為Ips。在T時刻就緒隊列中有3個進程Pl、P2和P3,其在就緒隊列中的等待時間、需

11、 要的CPU時間和優先權如下表所示。進程等待時間需要的CPU時間優先權P130ps12ps10P215ps24ps30P318ps36ps20若優先權值大的進程優先獲得CPU,從T時刻起系統開始進程調度，則系統的平均周轉時間為OA. 54ps B. 73psC. 74psD. 75ps25.屬于同一進程的兩個線程thread 1和thread2并發執行，共享初值為0的全局變量xthreadl和thread2實現對全局變量x加1的機器級代碼描述如下。thread1thread2mov R1, x/ (x) R1inc R1/ (R1) +1 -R1mov x, R111 (R1) xmov R2

12、, x11 (x) R2inc R211 (R2) +1 -R2mov x, R211 (R2) x在所有可能的指令執行序列中，使x的值為2的序列個數是。A. 1B. 2C. 3D. 426.假設系統中有4個同類資源，進程P1、P2和P3需要的資源數分別為4、3和1, P1、P2和P3已申請到的資源數分別為2、1和0,則執行安全性檢測算法的結果是=不存在安全序列，系統處于不安全狀態存在多個安全序列，系統處于安全狀態存在唯一安全序列P3、P1、P2,系統處于安全狀態存在唯一安全序列P3、P2、P1，系統處于安全狀態下列選項中，可能導致當前進程P阻塞的事件是。.進程P申請臨界資源.進程P從磁盤讀數

13、據系統將CPU分配給高優先權的進程A.僅 IB.僅 IIC.僅 I、IID. I、II、HI若x是管程內的條件變量，則當進程執行x.wait()時所做的工作是。實現對變量x的互斥訪問喚醒一個在x上阻塞的進程根據x的值判斷該進程是否進人阻塞狀態阻塞該進程，并將之插入x的阻塞隊列中當定時器產生時鐘中斷后，由時鐘中斷服務程序更新的部分內容是.內核中時鐘變量的值當前進程占用CPU的時間當前進程在時間片內的剩余執行時間A.僅 I、II B.僅 II、III C.僅 I、HI D. I、II、III30. TOC o 1-5 h z 下列磁盤調度算法中，不會導致磁臂粘著的是。A.FCFSB.SSTF)C.

14、SCAND.CSCAN)31.I .III.A.B.C.D.32.A. Peterson 方法B. swap指令C.信號量方法D. TestAndSet指令TCP/IP 應A. FTPB. DNSC. SMTPD. HTTP34.A.B.C.D.IEEE 802.11MAC 協議 CSMA/CA 進；A.B.C.使用多個MAC地址D.交換RTS與CTS幀-3 kbps,單向傳播延時是200ms40%A. 240比特B. 400比特C. 480比特D. 800比特RS1 S2RH1 H2 IP IMACH1 H2 1 IP P H1PMAC H2PMAC 地192.16&4.200-aI-b2-

15、c3-d4-6200-al-b2-c3-d4-6200-a1-b2-c3-d4-62、00-1a-2b-3c-4d-5200-a1-b2-c3-d4-62、00-a1-b2-c3-d4-6100-1a-2b-3c-4d-51、 00-1a-2b-3c-4d-5200-la-2b-3c-4d-51、00-al-b2-c3-d4-614/21、 TOC o 1-5 h z /21、/21和/21,將該4條路由聚合后的目的網絡地址為。A. /19B. /20C. /19D. /20UDP(demultiplexing)時A.B.C.D.SMTP 協A. JPEG圖像 B. MPEG 視頻C.EXED

16、. ASCII文本二、綜合應用題：第4147小題，共70分。(13 庫組中未出現的最小正整數。例如，數組-5, 3, 2, 3中未出現的最小正整數是1；數組1, 2, 3中未出4。1)(2C C+(3)（12分）擬建設一個光通信骨干網絡連通BJ、CS、XA、QD、JN NJ、TL和WH等8個城市，題42圖中無向邊上的權值表示兩個城市間備選光纜的鋪設費用。請回答下列問題。（1）僅從鋪設費用角度出發，給出所有可能的最經濟的光纜鋪設方案（用帶權圖表示），并計算相應方案的總費用。 TOC o 1-5 h z (2421)31H1 1TLH2BJH1 H2TTL=5 的 IP 分則 H2IP(8)500

17、MHz, CPI 4A B, J2MB/s 40MB/s I/O32 屈計算過程。AI/O/10A 最多間隔多長時間查詢一次才能不丟失數據？ CPU用于設備A輸入/輸出的時間占CPU總時間的百分 比至少是多少？I/O400，則設備BI/O(3)若設備B采用DMA方式，每次DMA傳送的數據塊大小1000B, CPU用于DMA預處 理和后處理的總時鐘周期數為500,則CPU用于設備B輸人/輸出的時間占CPU總時間的百分比 最多是多少？(15)某計算機采用頁式虛擬存儲管理方式，按字節編址。CPU進行存儲訪問的過程如題44 00324H1F800H0008CH10040H8C040H10160H043

18、20H00E80HTag有效伐實頁弓比較傘1F8000H1008C0H000400H有效位Tag44主存物理地址占多少位？TLB采用什么映射方式？ TLB用SRAM還是DRAM實現？ CacheCache 采用 LRUWrite Back)策略，則Cache每行中除數據(Data)、Tag和有效位外,還應有哪些附加位？ Cache總容量是多少？ Cache 中有效位的作用是什么？若CPU給出的虛擬地址為0008 C040H,則對應的物理地址是多少？是否在Cache中命 CPU0007 C260HCache 組號是多少？(8)44(16,在相應的頁表中對應的頁號為6,頁內偏移量為8,該虛擬地址的

19、十六進制表示是什么？PDBR用PDBRPDBR 的會變化？說明理由。CLOCK*(7)4KB。464B118個，一級、二級和三級間接地址項各1個，每4B1)1M (1M=220512M5600BF16KBF240KBF1 和 F2 最后一個簇的簇號需要的時間是否相同？為什么？(7分)某公司網絡如題47圖所示。IP地址空間/24被均分給銷售部和技術部兩 個子網，并已分別為部分主機和路由器接口分配了 IP地址，銷售部子網的MTU=1500B,技術部 子網的MTU=800B。1個IP地08 發送一個總長度為 1500B 的 IP 分組，IP 分20BF1IPIP移量是多少？2018年計算機學科專業基

20、礎綜合試題參考答案一、單項選擇題1.B2.C3.A4.A5.A6.C7.D8.B9C10.D11.A12.D13.C14.A15.A16.B17.C18.B19.A20.D21.B22.C23.C24.D25.B26.A27.C28.D29.D30.A31.D32.C33.B34.C35.D36.D37.D38.C39.B40.D二、綜合應用題41.1)組 BnA1nB01, Bn-1n,B0 An1n+1 A n 個1nn+1A0n1n 中 返回結果必然在1n中，因此對于A中出現了小于等于0或者大于n的值可以不采取任何操作。經過以上分析可以得出算法流程：從A0開始遍歷A,若0Ai=n，則令B

21、Ai-1=1；否ABBi=0i,i+1A1nBi0i+1 (跳出循環時i=n,int findMissMin(int A,int n)int i,*B;B=(int *)malloc(sizeof(int)*n memset(B,0,sizeof(int)*n); for(i=0;i0&Ai=n)BAi-1=1; for(i=0;iT-方案1方案216。2）存儲題中的圖可以采用鄰接矩陣（或鄰接表）。構造最小生成樹采用Prim算法（或kruskal 算法）。3） TTL=5,即 IP5,方案 1 中 TL BJ 由TTL=5IPH1H2 H2IP2 中 TL BJ 令H2IP 分431時訪問端口

22、，以防止部分數據沒有被及時讀取而丟失。設備A準備32位數據所用時間為 4B/2MB=2us,所以最多每隔2us必須查詢一次，每秒的查詢次數至少是1s/2us=5x105,每秒CPU 用于設備 A /5x105x10 x4=2x107CPU 時I少是 2x107/500M=4%。2）中斷響應和中斷處理的時間為400 x （1/500M） =0.8us，這時只需判斷設備B準備32位數 據要多久，如果準備數據的時間小于中斷響應和中斷處理的時間，那么數據就會被刷新、造成丟B 324B/40MB=0.1usBI/O 方：DMA方式中，只有預處理和后處理需要CPUDMA控制。設備B每秒的DMA次數最多為4

23、0MB/1000B=40000, CPU用于設備B輸入/輸出的時間最多為 40000 x500=2x107個時鐘周期，占CPU總時間的百分比最多為2x107/500M=4%。44.解析：116+12=2820+3+5=28。2） TLBTLBTLB 較器，沒有映射規則，只要空閑就行。TLB采用靜態存儲器SRAM,讀寫速度快，但成本高，多 用于容量較小的高速緩沖存儲器。Cache2 鹿LRU1 位 LRU回寫策略，所以每行有1位修改位（臟位），根據臟位判斷數據是否被更新，如果臟位為1則需 要寫回內存。28Tag2035 位，故 Cache 共有 23=8 組，每組 2 行，每行有 25=32B；

24、故 Cache 總容量為 8x2x （20+1+1+1+32x8） =4464 位=558 字節。CacheCache 年4利用虛擬地址的虛頁號部分去查找TLB表（缺失時從頁表調入），將實頁號取出后和虛擬地址的 頁內地址拼接，就形成了物理地址。虛頁號008CH恰好在TLB表中對應實頁號0040H （有效位13040H0040040H。物理地址為0040040H，其中高20位00400H為標志字段，低5位00000B為塊內偏移量， 中間 3010B200400H與 Cache2Cache00400H0Cache行的標志字段與00400H不相等，故訪問Cache不命中。因為物理地址的低12位與虛擬

25、地址低12位相同，即為0010 0110 0000B。根據物理地址的 結構，物理地址的后八位01100000B的前三位011B是組號，因此該地址所在的主存映射到Cache 3。45.132位，高2012位為頁內地址。且虛頁號高10位為頁目錄號，低10位為頁號。展開成二進制則表示為：0000 0001 1000 0000 01100000 0000 1000 BI,MM,頁目錄號 頁號頁內地址故十六進制表示為0180 6008H2） PDBR為頁目錄基址地址寄存器（Directory Base Register）,其存儲頁目錄表物理內 存基地址。進程切換時，PDBR的內容會變化；同一進程的線程切換時，PDBR的內容不會變化。 每個進程的地址空間、頁目錄和PDBR的內容存在一一對應的關系。進程切換時，地址空間發生 了變化，對應的頁目錄及其起始地址也相應變化，因此需要用進程切換后當前進程的頁目錄起始 PDBR。P線程使用的頁目錄不變，因此PDBR的內容也不變。CLOCK置修改字段（臟位）。解析：4K