2016年全國(guó)碩士研究生招生考試計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題

1、2016年全國(guó)碩士研究生招生考試計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題140小題，每小題2分，共80分。下列每題給出的四個(gè)選項(xiàng)中。只有一 個(gè)選項(xiàng)符合試題要求。1c的單鏈表在內(nèi)存中的存儲(chǔ)狀態(tài)如下表所示。地址1000H1004H1008H100CH1010H1014Ha1010Hb100CHC1000HdNULLe1004H鏈接地址元素啲“鏈接地現(xiàn)將晞放于1014H處并插入到單鏈表中，若誑邏輯上位于a和e之間，則a, e,址”依次是A 1010H1014H,1004HB.1010H 1004H1014HC. 1014H,1010H,1004HD.1014H, 1004H,1010H2已

2、知一個(gè)帶有表頭結(jié)點(diǎn)的雙$循環(huán)鏈表L,結(jié)點(diǎn)結(jié)甲為prev data next,其中，prev和next分別是指向其直接前驅(qū)和直接后繼結(jié)點(diǎn)的指針?，F(xiàn)要?jiǎng)h除指針p所指的結(jié)點(diǎn)，正確的語(yǔ)句序列是p-next-prev=p-prev; p-prev-next=p-prev; free (p);p-next-prev=p-next; p-prey- next=p-next; free (p);p-next-prev=p-next; p-prev-next=p-prev; free (p);p- next- prey=p-prey; p-prev-next=p-next; free (p);3n右，列車可駛?cè)?/p>

3、任意一條軌道?，F(xiàn)有編號(hào)為19的9列列車，駛?cè)氲拇涡蛞来问?, 4, 2, 5, 3, 9 1, 6 71 9,則n987654321入口出口軌道A 2B 3 C 4 D. 54.有一個(gè)100階的三對(duì)角矩陣M,其元mi,j(li100, lj1000)個(gè)元素的升序數(shù)組A中查找關(guān)鍵字X。查找算法的偽代碼如下所示。 k=0;while(kn 且 Akx)k=k+3 ；if(kn 且 Ak=x)莖else if(k-1n 且 Ak-1=x)查找成功；else if(k-2n 且 Ak-2=x)查找成功；else查出本算法與折半查找算法相比，有可能具有更少比較次數(shù)的情形是AxB當(dāng)x接CxDx位 B+BI

4、BC.木D1110 TB的縷AB. CD12.匯編程序B.鏈接程序C.編譯程序D.解釋程序13有如下C語(yǔ)言程序段：short si=-32767；unsigned short usi=si；執(zhí)行上述兩條語(yǔ)句后，usi的值為A -32767 B 32767 C. 32768 D. 32769某計(jì)算機(jī)字長(zhǎng)為32位，按字節(jié)編址，采用小端(Little Endian)方式存放數(shù)據(jù)。假定有一 個(gè)double型變量，其機(jī)器數(shù)表示為1122 3344 5566 7788H，存放在0000 8040H開始的連續(xù)存儲(chǔ)單 元中，則存儲(chǔ)單元0000 8046H中存放的是22H B. 33H C. 66H D. 77

5、H有如下C語(yǔ)言程序段：for(k=0； kR513:add R4, R5, R3 ;(R5)+(R3)R4I4:add R5, R2, R6 ;(R2)+(R6)R5A. I1 和I2B. I2和I3C. I2和I4D. I3和I4單周期處理器中所有指令的指令周期為一個(gè)時(shí)鐘周期。下列關(guān)于單周期處理器的敘述 中，笹謖的是可以采用單總線結(jié)構(gòu)數(shù)據(jù)通路處理器時(shí)鐘頻率較低在指令執(zhí)行過(guò)程中控制信號(hào)不變D 每條指令的CPI為1下列關(guān)于總線設(shè)計(jì)的敘述中，錯(cuò)誤的是并行總線傳輸比串行總線傳輸速度快采用信號(hào)線復(fù)用技術(shù)可減少信號(hào)線數(shù)量采用突發(fā)傳輸方式可提高總線數(shù)據(jù)傳輸率采用分離事務(wù)通信方式可提高總線利用率異常是指令執(zhí)

6、行過(guò)程中在處理器內(nèi)部發(fā)生的特殊事件，中斷是來(lái)自處理器外部的請(qǐng)求 事件。下列關(guān)于中斷或異常情況的敘述中，舖課的是“訪存時(shí)缺頁(yè)”屬于中斷“整數(shù)除以0”屬于異?！癉MA傳送結(jié)束”屬于中斷“存儲(chǔ)保護(hù)錯(cuò)”屬于異常下列關(guān)于批處理系統(tǒng)的敘述中，正確的是-批處理系統(tǒng)允許多個(gè)用戶與計(jì)算機(jī)直接交互-批處理系統(tǒng)分為單道批處理系統(tǒng)和多道批處理系統(tǒng)III.中斷技術(shù)使得多道批處理系統(tǒng)的I/O設(shè)備可與CPU并行工作A.僅 II、III B.僅IIC.僅 I、II D.僅 I、III24某單CPU系統(tǒng)中有輸入和輸出設(shè)備各1臺(tái)，現(xiàn)有3個(gè)并發(fā)執(zhí)行的作業(yè)，每個(gè)作業(yè)的輸入、 計(jì)算和輸出時(shí)間均分別為2 ms、3 ms和4 ms,且都按

7、輸入、計(jì)算和輸出的順序執(zhí)行，則執(zhí)行完3 個(gè)作業(yè)需要的時(shí)間最少是A. 15 ms B 17 ms C 22 msD 27 ms25.系統(tǒng)中有3個(gè)不同的臨界資源R1、R2和R3,被4個(gè)進(jìn)程p1、p2、p3及p4共享。各進(jìn)程對(duì) 資源的需求為：p1申請(qǐng)R1和R2, p2申請(qǐng)R2和R3, p3申請(qǐng)R1和R3, p4申請(qǐng)R2。若系統(tǒng)出現(xiàn)死鎖, 則處于死鎖狀態(tài)的進(jìn)程數(shù)至少是A. 1 B 2 C. 3 D. 426某系統(tǒng)采用改進(jìn)型CLOCK置換算法，頁(yè)表項(xiàng)中字段A為訪問(wèn)位，M為修改位。A=0表 示頁(yè)最近沒(méi)有被訪問(wèn)，A=1表示頁(yè)最近被訪問(wèn)過(guò)。M=0表示頁(yè)沒(méi)有被修改過(guò)，M=1表示頁(yè)被修 改過(guò)。按(A, M)所有可

8、能的取值，將頁(yè)分為四類：(0, 0)、(1, 0)、(0, 1)和(1, 1),則該算法淘汰頁(yè)的次序?yàn)锳(0,0)，(0,1),(1,0), (11,1)B (0,0)，(1,0)，(0,1), (1I, 1)C. (0,0)，(0,1),(1,1), (10)D(0,0)，(1,1),(0,1), (11, 0)27.使用TSL(Test and Set Lock)指令實(shí)現(xiàn)進(jìn)程互斥的偽代碼如下所示。 do while(TSL( &lock)； critical section； lock=FALSE； while(TRUE)；下列與該實(shí)現(xiàn)機(jī)制相關(guān)的敘述中，正確的是ABCPU TOC o 1-

9、5 h z -while(TSL(&lock)語(yǔ)句應(yīng)在關(guān)中斷狀態(tài)下執(zhí)行某進(jìn)程的段表內(nèi)容如下所示。段長(zhǎng)內(nèi)存起始地址權(quán)限狀態(tài)1006000只讀在內(nèi)存200一讀寫不在內(nèi)存3004000讀寫在內(nèi)存段號(hào)012 TOC o 1-5 h z 2400AB.4400CD某進(jìn)程訪問(wèn)頁(yè)面的序列如下所示。,1,3, 4, 5, 6, 0,3, 2,3,2,丫 0,4, 0,3, 2,9,2,1,“ ” t時(shí)間若工作集的窗口大小為6,則在時(shí)刻的工作集為A. 6, 0,3,2B.2, 3,0,4c. 0, 4,32,9 D.4, 56,0,3 230P1和P2均/進(jìn)程P1/進(jìn)程P2int x=0：int x=0：Thr

10、ead1()Thread3( ) int a： int a；a=l；x+=1；a=x；x+=3；Thread2( )Thread4( ) int a：int b；a=2； x+=2；b=x； x+=4；下列選項(xiàng)中，需要互斥執(zhí)行的操作是A. a=l與a=2B. a=x與b=xc. x+=l與x+=2D. x+=l與x+=331SPOOLing 技 TOC o 1-5 h z 韋fTD/輸出井之間的數(shù)據(jù)傳送下列關(guān)于管程的敘述中，笹課的是ABCD題3341均依據(jù)題3341圖回答。 在OSIRl、Switch、Hub實(shí)現(xiàn)的最高功能層分別是A. 2、 2、 l B. 2、 2、 2 C. 3、 2、 l

11、 D. 3、 2、 234R2 和 R38 kHz30 dB為理論最大數(shù)據(jù)傳輸速率的50%,則該鏈路的實(shí)際數(shù)據(jù)傳輸速率約是/24A. 8 kbps B. 20 kbps題3341圖35若主機(jī)H2向主機(jī)H4發(fā)送1H4向主機(jī)H2立即發(fā)送一個(gè)確認(rèn)幀，則除H4外，從物理層上能夠收到該確認(rèn)幀的主機(jī)還有A.僅H2B.僅H3C.僅H1、H2 D.僅H2、H3Hub1.200 ms,不考慮以太H3與H4之A. 200 m B. 205 m C. 359 m D. 512 mR1、R2、R3 RIPR3/25R2R2 更A. 2 B. 3C. 16 D. 17R1、R2和R3201.1. 3. x/30H3We

12、b服務(wù)器S時(shí)，R2HTTPIPIP地址和目的IP地A. 192.168.3. 251, B. 192.168.3. 251, 201.1. 3.9C. 201.1. 3.8, D. 201.1. 3.10, 39.假設(shè)H1與H2的默認(rèn)網(wǎng)關(guān)和子網(wǎng)掩碼均分別配置為192.168.3. 1和28, H3 與H4192.168.3 254 28,則下列現(xiàn)象中可能發(fā)生的是A. H1不能與H2進(jìn)行正常IP通信H2與H4均不能訪問(wèn)InternetHl不能與H3進(jìn)行正常IP通信D H3不能與H4進(jìn)行正常IP通信40假設(shè)所有域名服務(wù)器均采用迭代查詢方式進(jìn)行域名解析。當(dāng)H4訪問(wèn)規(guī)范域名為 www. abc. xy

13、z. com的網(wǎng)站時(shí)，域名服務(wù)器20l.l. l.l在完成該域名解析過(guò)程中，可能發(fā)出DNS 查詢的最少和最多次數(shù)分別是A 0, 3 B. l, 3C. 0, 4D. l, 4二、綜合應(yīng)用題：4147小題，共70分。(9分)假設(shè)題3341圖中的H3訪問(wèn)Web服務(wù)器S時(shí)，S為新建的TCP連接分配了20 KB(K=l 024)的接收緩存，最大段長(zhǎng)MSS=1 KB,平均往返時(shí)間RTT=200 ms。H3建立連接時(shí)的初始序號(hào) 為100,且持續(xù)以MSS大小的段向S發(fā)送數(shù)據(jù)，擁塞窗口初始閾值為32 KB； S對(duì)收到的每個(gè)段進(jìn) 行確認(rèn)，并通告新的接收窗口。假定TCP連接建立完成后，S端的TCP接收緩存僅有數(shù)據(jù)

14、存入而 無(wú)數(shù)據(jù)取出。請(qǐng)回答下列問(wèn)題。在TCP連接建立過(guò)程中，H3收到的S發(fā)送過(guò)來(lái)的第二次握手TCP段的SYN和ACK標(biāo)志位 的值分別是多少?確認(rèn)序號(hào)是多少？H3收到的第8個(gè)確認(rèn)段所通告的接收窗口是多少?此時(shí)H3的擁塞窗口變?yōu)槎嗌?H3的發(fā) 送窗口變?yōu)槎嗌伲慨?dāng)H3的發(fā)送窗口等于0時(shí)，下一個(gè)待發(fā)送的數(shù)據(jù)段序號(hào)是多少? H3從發(fā)送第1個(gè)數(shù)據(jù)段到 發(fā)送窗口等于0時(shí)刻為止，平均數(shù)據(jù)傳輸速率是多少(忽略段的傳輸延時(shí))？若H3與S之間通信已經(jīng)結(jié)束，在t時(shí)刻H3請(qǐng)求斷開該連接，則從t時(shí)刻起，S釋放該連接的 最短時(shí)間是多少？(8分)如果一棵非空k(kN2)叉樹T中每個(gè)非葉結(jié)點(diǎn)都有k個(gè)孩子，則稱T為正則后k樹。請(qǐng)

15、 回答下列問(wèn)題并給出推導(dǎo)過(guò)程。若T有m個(gè)非葉結(jié)點(diǎn)，貝!JT中的葉結(jié)點(diǎn)有多少個(gè)？若T的高度為h(單結(jié)點(diǎn)的樹h=1),則T的結(jié)點(diǎn)數(shù)最多為多少個(gè)?最少為多少個(gè)？(15分)已知由n(nN2)個(gè)正整數(shù)構(gòu)成的集合A=ak OVkn,將其劃分為兩個(gè)不相交的子 集A1和A2,元素個(gè)數(shù)分別是珥和n2, A】和A2中元素之和分別為S1和S?。設(shè)計(jì)一個(gè)盡可能高效的 劃分算法，滿足|珥-血|最小且IS1-S21最大。要求：給出算法的基本設(shè)計(jì)思想。根據(jù)設(shè)計(jì)思想，采用C或C+語(yǔ)言描述算法，關(guān)鍵之處給出注釋。說(shuō)明你所設(shè)計(jì)算法的平均時(shí)間復(fù)雜度和空間復(fù)雜度。(9分)假定CPU主頻為50 MHz, CPI為4。設(shè)備D采用異步串行

16、通信方式向主機(jī)傳送7位 ASCII字符，通信規(guī)程中有1位奇校驗(yàn)位和1位停止位，從D接收啟動(dòng)命令到字符送入I/O端口需 要0.5 ms。請(qǐng)回答下列問(wèn)題，要求說(shuō)明理由。每傳送一個(gè)字符，在異步串行通信線上共需傳輸多少位?在設(shè)備D持續(xù)工作過(guò)程中，每秒 鐘最多可向I/0端口送入多少個(gè)字符？設(shè)備D采用中斷方式進(jìn)行輸入/輸出，示意圖如下：外設(shè)DCPU工作 完工作 完工作 完 TOC o 1-5 h z 1:成；:成:成-!Ij動(dòng) TU動(dòng) Tti啟請(qǐng)響返請(qǐng)響返請(qǐng)響動(dòng)求應(yīng)回求應(yīng)回求應(yīng)I/O1020條15DCPU D 1000?CPU?在CPU?(14 )32位248 KB； TLBCache64 KB,按2路組

17、相聯(lián)方64 Bo 彳-B存在位頁(yè)框號(hào)HI E 丨 F | G |標(biāo)記數(shù)據(jù) 標(biāo)記數(shù)據(jù)請(qǐng)回答下列問(wèn)題。AG?TLBB?4099CacheCache?對(duì)應(yīng)的 H 字段內(nèi)? Cache?Cache(Write Through)(WriteBack) ?(6 )(priority卅運(yùn)行，進(jìn)程創(chuàng)建時(shí)由用戶指定一個(gè)nice作為靜態(tài)優(yōu)先數(shù)。為了動(dòng)態(tài)調(diào)整優(yōu)先數(shù)，引入運(yùn)行時(shí)間 cpuTime和等待時(shí)間waitTime，初值均為0。進(jìn)程處于執(zhí)行態(tài)時(shí)，cpuTime定時(shí)加1,且waitTime 0cpuTime 置 0 waitTime 1nicepriority=nice,?使用nice cpuTime和waitT

18、ime設(shè)種動(dòng)態(tài)優(yōu)先數(shù)計(jì)算方法，以避免產(chǎn)生饑餓現(xiàn)象，并 說(shuō)明waitTime的47 (9分)4 KB。目錄文件的每個(gè)目錄項(xiàng)包括文件名和文件的第一個(gè)簇號(hào)，其他簇號(hào)存放在文件分配表FAT中。(1)dir、dir1 是目錄，file1、file2是ele2 mfil文件名簇號(hào)dir1dir148file1100、 106、 108file2200、 201、 202若FAT的每個(gè)表項(xiàng)僅存放簇號(hào)，占2個(gè)字節(jié)，則FAT的最大長(zhǎng)度為多少字節(jié)?該文件系統(tǒng) 支持的文件長(zhǎng)度最大是多少？FAT實(shí)現(xiàn)對(duì)文件的按名存取，說(shuō)明file 1的106、108兩個(gè)簇號(hào)分別存 放在FAT的IFAT和dir目錄文件已讀入內(nèi)存，若需將

19、文件dir/dirl/file 1的第5000個(gè)字節(jié)讀入內(nèi) 存，則要訪問(wèn)哪幾個(gè)簇？計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題參考答案(2016年)單項(xiàng)選擇題1. D2. D3. C4. B5. C6. D7. B8. B9. B10.A11. D12. C13. D14. A15. C16. C17. C18. B19. B20. A21. A22. A23. A24. B25. C26. A27. B28. D29. A30. C31. D32. A33. C34. C35. D36. B37. B38. D39. C40. C二綜合應(yīng)用題41.TCP SYN=1, (1 )ACK=1； (1 分)101。

20、(1 )H3812 KB； (1 分)此時(shí)H39 KB；(1 分)H39 KB。(1 ) 當(dāng)H3的發(fā)送窗口等于020 K+101=20 x1024+101=20581； (1分)H31020 KB/(5x200 ms)=20KB/s=20.48 kbps。(1 分)從tS1.5x200 ms=300 ms。(1 分)42.k(n0)k(4nk)Tn=n+nk=n0+me=n-1mk 的e=mxk。整理得：n0+m=mxk+1,故n0=(k-1)xm+1。(3分)h k Th1到第h-1層的結(jié)點(diǎn)都是 度為k的分支結(jié)點(diǎn)，而第h層均為葉結(jié)點(diǎn)，即樹是“滿”樹。此時(shí)第j(iqvh)層結(jié)點(diǎn)數(shù)為k-1,結(jié)點(diǎn)

21、總 數(shù)Ml為：h k h 1 TOC o 1-5 h z M、= -_-(3 分)冃-1含最少結(jié)點(diǎn)的正則k叉樹的樹形為：第1層只有根結(jié)點(diǎn)，第2到第h-1層僅含1個(gè)分支結(jié)點(diǎn)和k-1 個(gè)葉結(jié)點(diǎn)，第h層有k個(gè)葉結(jié)點(diǎn)。即除根外第2到第h層中每層的結(jié)點(diǎn)數(shù)均為k,故T中所含結(jié)點(diǎn)總 數(shù)M2為：M2=1+(h-1”k(2 分)【評(píng)分說(shuō)明】參考答案僅給出一種推導(dǎo)過(guò)程，若考生采用其他推導(dǎo)方法且正確，同樣給分。若考生僅給出結(jié)果，但沒(méi)有推導(dǎo)過(guò)程，則(1)、(2)的最高得分分別是2分和3分。若推導(dǎo)過(guò) 程或答案不完全正確，酌情給分?！敬鸢敢c(diǎn)】算法的基本設(shè)計(jì)思想(4分)由題意知，將最小的/2個(gè)元素放在A1中，其余的元素放

22、在A2中，分組結(jié)果即可滿足題 目要求。仿照快速排序的思想，基于樞軸將n個(gè)整數(shù)劃分為兩個(gè)子集。根據(jù)劃分后樞軸所處的位 置i分別處理：若i=L/2，則分組完成，算法結(jié)束；若iL/2，則樞軸及之后的所有元素均屬于A?，繼續(xù)對(duì)i之前的元素進(jìn)行劃分；基于該設(shè)計(jì)思想實(shí)現(xiàn)的算法，毋須對(duì)全部元素進(jìn)行全排序，其平均時(shí)間復(fù)雜度是0(n),空 間復(fù)雜度是0(1)。算法實(shí)現(xiàn)(9分)int setPartition(int a int n)int pivotkey, low=0, low0=0, high=n-l, highO=n-1, flag=1, k=n/2, i；int s1=0, s2=0；while(flag) pivotkey=alow；選擇樞軸while(lowhigh)基于樞軸對(duì)數(shù)據(jù)進(jìn)行劃分 while(low=pivotkey)-high;if(low!=high)alow=ahigh； while