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

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

2、知一個帶有表頭結(jié)點的雙$循環(huán)鏈表L,結(jié)點結(jié)甲為prev data next,其中，prev和next分別是指向其直接前驅(qū)和直接后繼結(jié)點的指針?，F(xiàn)要刪除指針p所指的結(jié)點，正確的語句序列是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、任意一條軌道。現(xiàn)有編號為19的9列列車，駛?cè)氲拇涡蛞来问?, 4, 2, 5, 3, 9 1, 6 71 9,則n987654321入口出口軌道A 2B 3 C 4 D. 54.有一個100階的三對角矩陣M,其元mi,j(li100, lj1000)個元素的升序數(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語言程序段：short si=-32767；unsigned short usi=si；執(zhí)行上述兩條語句后，usi的值為A -32767 B 32767 C. 32768 D. 32769某計算機字長為32位，按字節(jié)編址，采用小端(Little Endian)方式存放數(shù)據(jù)。假定有一 個double型變量，其機器數(shù)表示為1122 3344 5566 7788H，存放在0000 8040H開始的連續(xù)存儲單 元中，則存儲單元0000 8046H中存放的是22H B. 33H C. 66H D. 77

5、H有如下C語言程序段：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單周期處理器中所有指令的指令周期為一個時鐘周期。下列關(guān)于單周期處理器的敘述 中，笹謖的是可以采用單總線結(jié)構(gòu)數(shù)據(jù)通路處理器時鐘頻率較低在指令執(zhí)行過程中控制信號不變D 每條指令的CPI為1下列關(guān)于總線設(shè)計的敘述中，錯誤的是并行總線傳輸比串行總線傳輸速度快采用信號線復(fù)用技術(shù)可減少信號線數(shù)量采用突發(fā)傳輸方式可提高總線數(shù)據(jù)傳輸率采用分離事務(wù)通信方式可提高總線利用率異常是指令執(zhí)

6、行過程中在處理器內(nèi)部發(fā)生的特殊事件，中斷是來自處理器外部的請求 事件。下列關(guān)于中斷或異常情況的敘述中，舖課的是“訪存時缺頁”屬于中斷“整數(shù)除以0”屬于異?！癉MA傳送結(jié)束”屬于中斷“存儲保護(hù)錯”屬于異常下列關(guān)于批處理系統(tǒng)的敘述中，正確的是-批處理系統(tǒng)允許多個用戶與計算機直接交互-批處理系統(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臺，現(xiàn)有3個并發(fā)執(zhí)行的作業(yè)，每個作業(yè)的輸入、 計算和輸出時間均分別為2 ms、3 ms和4 ms,且都按

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

8、能的取值，將頁分為四類：(0, 0)、(1, 0)、(0, 1)和(1, 1),則該算法淘汰頁的次序為A(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)指令實現(xiàn)進(jìn)程互斥的偽代碼如下所示。 do while(TSL( &lock)； critical section； lock=FALSE； while(TRUE)；下列與該實現(xiàn)機制相關(guān)的敘述中，正確的是ABCPU TOC o 1-

9、5 h z -while(TSL(&lock)語句應(yīng)在關(guān)中斷狀態(tài)下執(zhí)行某進(jìn)程的段表內(nèi)容如下所示。段長內(nèi)存起始地址權(quán)限狀態(tài)1006000只讀在內(nèi)存200一讀寫不在內(nèi)存3004000讀寫在內(nèi)存段號012 TOC o 1-5 h z 2400AB.4400CD某進(jìn)程訪問頁面的序列如下所示。,1,3, 4, 5, 6, 0,3, 2,3,2,丫 0,4, 0,3, 2,9,2,1,“ ” t時間若工作集的窗口大小為6,則在時刻的工作集為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；下列選項中，需要互斥執(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實現(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ù)據(jù)傳輸速率約是/24A. 8 kbps B. 20 kbps題3341圖35若主機H2向主機H4發(fā)送1H4向主機H2立即發(fā)送一個確認(rèn)幀，則除H4外，從物理層上能夠收到該確認(rèn)幀的主機還有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時，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均不能訪問InternetHl不能與H3進(jìn)行正常IP通信D H3不能與H4進(jìn)行正常IP通信40假設(shè)所有域名服務(wù)器均采用迭代查詢方式進(jìn)行域名解析。當(dāng)H4訪問規(guī)范域名為 www. abc. xy

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

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

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

16、通信方式向主機傳送7位 ASCII字符，通信規(guī)程中有1位奇校驗位和1位停止位，從D接收啟動命令到字符送入I/O端口需 要0.5 ms。請回答下列問題，要求說明理由。每傳送一個字符，在異步串行通信線上共需傳輸多少位?在設(shè)備D持續(xù)工作過程中，每秒 鐘最多可向I/0端口送入多少個字符？設(shè)備D采用中斷方式進(jìn)行輸入/輸出，示意圖如下：外設(shè)DCPU工作 完工作 完工作 完 TOC o 1-5 h z 1:成；:成:成-!Ij動 TU動 Tti啟請響返請響返請響動求應(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存在位頁框號HI E 丨 F | G |標(biāo)記數(shù)據(jù) 標(biāo)記數(shù)據(jù)請回答下列問題。AG?TLBB?4099CacheCache?對應(yīng)的 H 字段內(nèi)? Cache?Cache(Write Through)(WriteBack) ?(6 )(priority卅運行，進(jìn)程創(chuàng)建時由用戶指定一個nice作為靜態(tài)優(yōu)先數(shù)。為了動態(tài)調(diào)整優(yōu)先數(shù)，引入運行時間 cpuTime和等待時間waitTime，初值均為0。進(jìn)程處于執(zhí)行態(tài)時，cpuTime定時加1,且waitTime 0cpuTime 置 0 waitTime 1nicepriority=nice,?使用nice cpuTime和waitT

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

19、文件dir/dirl/file 1的第5000個字節(jié)讀入內(nèi) 存，則要訪問哪幾個簇？計算機學(xué)科專業(yè)基礎(chǔ)綜合試題參考答案(2016年)單項選擇題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 分)此時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é)點都是 度為k的分支結(jié)點，而第h層均為葉結(jié)點，即樹是“滿”樹。此時第j(iqvh)層結(jié)點數(shù)為k-1,結(jié)點

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

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