2018年全國碩士研究生入學統(tǒng)一考試計算機科學與技術(shù)學科聯(lián)考計算機學科專業(yè)基礎(chǔ)綜合試題

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

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設(shè)有一個12x12的對稱矩陣M,將其上三角部分的元素mi, j (1迄於12)按行優(yōu)先存人C語言的一維數(shù)組N中，元素m6,6在N中的下標是。50B. 51C.55D. 66設(shè)一棵非空完全二叉樹T的所有葉結(jié)點均位于同一層，且每個非葉結(jié)點都有2個子結(jié)點。若T有k個葉

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

4、,用線性探測再散列法解決22, 43,15HT 后A. 1.5B. 1.6C. 2D. 3對初始數(shù)據(jù)序列（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 的機器數(shù)為 FFFF FF9DHx = -33, y = 65, x-y 的機器數(shù)為 FFFF FF9E

6、Hx = -65, y = 41, x-y 的機器數(shù)為 FFFF FF96H TOC o 1-5 h z IEEE 754單精度浮點格式表示的數(shù)中，最小的規(guī)格化正數(shù)是。A. 1.0 x2-i26B. 1.0 x2-i27C. 1.0 x2-i28D. 1.0 x2-”9某32位計算機按字節(jié)編址，采用小端(Little Endian)方式。若語令int i = 0;對應(yīng)指令的機器代碼為“C7 45 FC 00 00 00 00”，則語句“int i = - 64;”對應(yīng)指令的機器代碼是。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整數(shù)x的機器數(shù)為1101 1000，分別對x進行邏輯右移1位和算術(shù)右移1位操作，得到的機器數(shù)各是=A.1110 1100、 1110 1100B. 0110 1100、 1110 1100C.1110 1100、 0110 1100D. 0110 1100、 0110 1100假定DRAM芯片中存儲陣列的行數(shù)為r、列數(shù)為c,對于一個2Kx 1位的DRAM芯片，為保證其地址引腳數(shù)最少，并盡量減少刷新開銷，則r、c的取值分別是。A. 2048、1B. 64、32C. 32、64D. 1、2048按字節(jié)編址的計算機中，某dou

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

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

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

11、 要的CPU時間和優(yōu)先權(quán)如下表所示。進程等待時間需要的CPU時間優(yōu)先權(quán)P130ps12ps10P215ps24ps30P318ps36ps20若優(yōu)先權(quán)值大的進程優(yōu)先獲得CPU,從T時刻起系統(tǒng)開始進程調(diào)度，則系統(tǒng)的平均周轉(zhuǎn)時間為OA. 54ps B. 73psC. 74psD. 75ps25.屬于同一進程的兩個線程thread 1和thread2并發(fā)執(zhí)行，共享初值為0的全局變量xthreadl和thread2實現(xiàn)對全局變量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在所有可能的指令執(zhí)行序列中，使x的值為2的序列個數(shù)是。A. 1B. 2C. 3D. 426.假設(shè)系統(tǒng)中有4個同類資源，進程P1、P2和P3需要的資源數(shù)分別為4、3和1, P1、P2和P3已申請到的資源數(shù)分別為2、1和0,則執(zhí)行安全性檢測算法的結(jié)果是=不存在安全序列，系統(tǒng)處于不安全狀態(tài)存在多個安全序列，系統(tǒng)處于安全狀態(tài)存在唯一安全序列P3、P1、P2,系統(tǒng)處于安全狀態(tài)存在唯一安全序列P3、P2、P1，系統(tǒng)處于安全狀態(tài)下列選項中，可能導(dǎo)致當前進程P阻塞的事件是。.進程P申請臨界資源.進程P從磁盤讀數(shù)

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

14、SCAND.CSCAN)31.I .III.A.B.C.D.32.A. Peterson 方法B. swap指令C.信號量方法D. TestAndSet指令TCP/IP 應(yīng)A. FTPB. DNSC. SMTPD. HTTP34.A.B.C.D.IEEE 802.11MAC 協(xié)議 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條路由聚合后的目的網(wǎng)絡(luò)地址為。A. /19B. /20C. /19D. /20UDP(demultiplexing)時A.B.C.D.SMTP 協(xié)A. JPEG圖像 B. MPEG 視頻C.EXED

16、. ASCII文本二、綜合應(yīng)用題：第4147小題，共70分。(13 庫組中未出現(xiàn)的最小正整數(shù)。例如，數(shù)組-5, 3, 2, 3中未出現(xiàn)的最小正整數(shù)是1；數(shù)組1, 2, 3中未出4。1)(2C C+(3)（12分）擬建設(shè)一個光通信骨干網(wǎng)絡(luò)連通BJ、CS、XA、QD、JN NJ、TL和WH等8個城市，題42圖中無向邊上的權(quán)值表示兩個城市間備選光纜的鋪設(shè)費用。請回答下列問題。（1）僅從鋪設(shè)費用角度出發(fā)，給出所有可能的最經(jīng)濟的光纜鋪設(shè)方案（用帶權(quán)圖表示），并計算相應(yīng)方案的總費用。 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 最多間隔多長時間查詢一次才能不丟失數(shù)據(jù)？ CPU用于設(shè)備A輸入/輸出的時間占CPU總時間的百分 比至少是多少？I/O400，則設(shè)備BI/O(3)若設(shè)備B采用DMA方式，每次DMA傳送的數(shù)據(jù)塊大小1000B, CPU用于DMA預(yù)處 理和后處理的總時鐘周期數(shù)為500,則CPU用于設(shè)備B輸人/輸出的時間占CPU總時間的百分比 最多是多少？(15)某計算機采用頁式虛擬存儲管理方式，按字節(jié)編址。CPU進行存儲訪問的過程如題44 00324H1F800H0008CH10040H8C040H10160H043

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

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

20、礎(chǔ)綜合試題參考答案一、單項選擇題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二、綜合應(yīng)用題41.1)組 BnA1nB01, Bn-1n,B0 An1n+1 A n 個1nn+1A0n1n 中 返回結(jié)果必然在1n中，因此對于A中出現(xiàn)了小于等于0或者大于n的值可以不采取任何操作。經(jīng)過以上分析可以得出算法流程：從A0開始遍歷A,若0Ai=n，則令B

21、Ai-1=1；否ABBi=0i,i+1A1nBi0i+1 (跳出循環(huán)時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）存儲題中的圖可以采用鄰接矩陣（或鄰接表）。構(gòu)造最小生成樹采用Prim算法（或kruskal 算法）。3） TTL=5,即 IP5,方案 1 中 TL BJ 由TTL=5IPH1H2 H2IP2 中 TL BJ 令H2IP 分431時訪問端口

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

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

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

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