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

1、2017年全國(guó)碩士研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題一、單項(xiàng)選擇題：第140小題，每小題2分，共80分。下列每題給出的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)最符 合試題要求。1.int func(int n)int i=0, sum=0;while(sum n) sum += +i; return i;A O(logn)B O(n1/2)C. O(n)D. O(nlogn)2.采用非遞歸方式重寫遞歸辭時(shí)必須使用棧函數(shù)調(diào)用時(shí)，系統(tǒng)要用棧保存必要的信息只要確定了入桟奶，即可確定出棧奶棧是一種受限的線性表，允許在其兩端進(jìn)行操作A.僅Ib.僅I、II、mC.僅 I、HI、WD.僅I

2、I、III、IV3.-AB.三CD.4.要使一棵非空二叉樹的先序序列與中序序列相同，其所有非葉結(jié)點(diǎn)須滿足的條件是.丿D25.已知一棵二叉樹的樹形如下圖所示，其后序序列為eac,b,d,g,f,樹中與結(jié)點(diǎn)a同層的結(jié)點(diǎn)是Bd6已知字符集aAc,d,e,f,g,h,若各字符的哈夫曼編碼依次是0100, 10, 0000, 0101, 001, 011 11, 0001,則編碼序列0100011001001011110101的譯碼結(jié)果是,A acgabfhB adbagbbafbeagdD afeefgd7G含有16條邊，其中度為43,度為3的頂點(diǎn)個(gè)數(shù)為4,其他頂點(diǎn)的度均小于3。圖G肪A 10B 11

3、C. 13D. 15&AB. 5CD；歸并排序的程序代碼更短歸并排序的占用空間更少m.歸并排序的運(yùn)行效率更高ABC.僅 I、II D.僅 I、IU11.插人排序II.選擇排序in.起泡排序iv.希爾排序V.堆排序僅 I、II B.僅II、IUC.僅III、IV D.僅IV、VM1 和 M2ISA)1.5GHz 和 1.2 GHz。在 M1 和 M2 上P CPI 21P M1 和 M2 上0.4B. 0.625C. 1.6D. 2.5 TOC o 1-5 h z 464M 8 DRAM32儲(chǔ)器總線相連，主存每次最多讀寫32位軸。若double型變量x的主存臧為804 001AH，則讀取x需要的

4、存儲(chǔ)周期 數(shù)是o1B. 2C. 3D. 4Cfor(i=0;i=9;i+)temp = 1;for(j=0；j =i;j+) temp *= aj;sum += temp；aABCD15.ABCD1629條，二地址指令107條，每個(gè)624 位B. 26 位C. 28 位D. 32 位17.I 能縮短流水線功能段的處理時(shí)間能在一個(gè)時(shí)鐘周期內(nèi)同時(shí)發(fā)射多條指令m.能結(jié)合動(dòng)態(tài)調(diào)度技術(shù)提高指令執(zhí)行并行性ABC.僅II、III D. I、II和HI18MMCS)丨A MM在CPU外，CS在CPU內(nèi)MM按地址訪問，CS按內(nèi)容訪問MM存儲(chǔ)指令和數(shù)據(jù)，CS存儲(chǔ)微指令MM用RAM和ROM實(shí)現(xiàn)，CS用ROM實(shí)現(xiàn) 下

5、列關(guān)于指令流水線數(shù)據(jù)通路的敘述中，錯(cuò)誤的是o包含生成控制信號(hào)的控制部件包含算術(shù)邏輯運(yùn)算部件(ALU)包含通用寄存器組和取指部件由組戯輯電路和時(shí)序邏輯電路組合而成 下列關(guān)于多總線結(jié)構(gòu)的敘述中，錯(cuò)誤的是。靠近CPU的總線速度較快存儲(chǔ)器總線可支持突發(fā)傳送方式總線之間須通過橋接器相連D PC I-Express X16采用并行傳輸方式 I/O指令實(shí)現(xiàn)的數(shù)據(jù)傳送通常發(fā)生在A I/O設(shè)備和I/O端口之間B.通用寄存器和I/O設(shè)備之間C. I/O端口和I/O端口之間D.通用寄存器和I/O端口之間 下列關(guān)于多重中斷系統(tǒng)的敘述中，錯(cuò)誤的是。在一條指令執(zhí)仃結(jié)束時(shí)響應(yīng)中斷中斷處理期間CPU處于關(guān)中斷狀態(tài)中斷請(qǐng)求的產(chǎn)

6、生與當(dāng)前指令的執(zhí)行無關(guān)CPU通過采樣中斷請(qǐng)求信號(hào)檢測(cè)中斷請(qǐng)求23 .假設(shè)4個(gè)作業(yè)到達(dá)系統(tǒng)的時(shí)刻和運(yùn)行時(shí)間如下表所示。作業(yè)到達(dá)時(shí)刻t運(yùn)行時(shí)間J103J213J312J431系統(tǒng)在t=2時(shí)開始作業(yè)調(diào)度。若分別采用先來先服務(wù)和短作業(yè)優(yōu)先調(diào)度算法，則選中的作業(yè)分別是A J2、 J3B. J1、J4C. J2、J4D. J1、J3執(zhí)行系統(tǒng)調(diào)用的過程包括如下主要操作:返回用戶態(tài)傳遞系統(tǒng)調(diào)用參數(shù) 正確的執(zhí)行順序是 A -迢-C.-阿XD執(zhí)行陷人(trap)指令執(zhí)行相應(yīng)的服務(wù)爾-某計(jì)算機(jī)按字節(jié)編址，其動(dòng)態(tài)分區(qū)內(nèi)存管理采用最佳適應(yīng)算法，每次分配和回收內(nèi)存后都對(duì)空閑分區(qū)鏈重新分區(qū)起始地址20 K500 K1000

7、 K200 K分區(qū)大小40 KB80 KB100 KB200 KB排序。當(dāng)前空閑分區(qū)信息如下表所示。回收起始地址為60 K、大小為140 KB的分區(qū)后，系統(tǒng)中空閑分區(qū)的數(shù)量、空閑分區(qū)鏈第一個(gè)分區(qū)的起始地址和大小分別是、A 3、20 K、380 KB3、500 K、80 KB4、20 K、180 KBD. 4、500 K、80 KB某文件系統(tǒng)的簇和磁盤扇區(qū)大小分別為1KB和512 B。若一個(gè)文件的大小為1 026B,則系統(tǒng)分配給該文件的磁盤空間大小是oA 1026 BB. 1536 BC 1538 BD. 2048 B 下列有關(guān)基于時(shí)間片的進(jìn)程調(diào)度的敘述中，錯(cuò)誤的是。時(shí)間片越短，進(jìn)程切換的次數(shù)越

8、多，系統(tǒng)也越大當(dāng)前進(jìn)程的時(shí)間片用完后，該進(jìn)程狀態(tài)由執(zhí)行態(tài)變?yōu)樽枞麘B(tài)時(shí)鐘中斷發(fā)生后，系統(tǒng)會(huì)修改當(dāng)前進(jìn)程在時(shí)間片內(nèi)的剩余時(shí)間影響時(shí)間片大小的主要因素包括響應(yīng)時(shí)間、系統(tǒng)開銷和進(jìn)程數(shù)量等 與單道酣系統(tǒng)相比，多道程序系統(tǒng)的優(yōu)點(diǎn)是。I. CPU利用率高II.系統(tǒng)開銷小系統(tǒng)吞吐量大IV.I/O設(shè)備利用率高A.僅I、IIIB.僅I、IV僅II、IIID.僅 I、皿、IV 下列選項(xiàng)中，磁盤邏輯格式化程序所做的工作是o對(duì)磁盤進(jìn)行分區(qū)建立文件系統(tǒng)的根目錄確定磁盤扇區(qū)校驗(yàn)碼所占位數(shù)對(duì)保存空閑磁盤塊信息的數(shù)據(jù)結(jié)構(gòu)進(jìn)行初始化A.僅IIB.僅II、IVC.僅III、WD.僅 I、II、IV某文件系統(tǒng)中，針對(duì)每個(gè)文件，用戶類

9、別分為4類：安全管理員、文件主、文件主的伙伴、其他用戶；訪問 TOC o 1-5 h z 權(quán)限分為5種：完全控制、執(zhí)行、修改、讀取、寫入。若文件控制塊中用二進(jìn)制位串表示文件權(quán)限，為表示不同類別 用戶對(duì)一個(gè)文件的訪問權(quán)限，則描述文件權(quán)限的位數(shù)至少應(yīng)為。A.5B. 9C. 12D. 20若文件fl的硬鏈接為包 兩他程分別打開fl和f2,獲得對(duì)應(yīng)的文件描述符為fidl和血，則下列敘述中，正確的是。I . f1和f2的讀寫指針位置保持相同f1和f2共享同一個(gè)內(nèi)存索引結(jié)點(diǎn)fd1和fd2分別指向各自的用戶打開文件表中的一項(xiàng)A.僅 IB.僅II、IH C.僅 I、II D. I、II和HI系統(tǒng)將數(shù)據(jù)從磁盤讀

10、到內(nèi)存的過程包括以下操作：DMA控制器發(fā)出中斷請(qǐng)求初始化DMA控制器并啟動(dòng)磁盤從磁盤傳輸一塊數(shù)據(jù)到內(nèi)存緩沖區(qū)執(zhí)行QMA結(jié)束,中斷服務(wù)程序 TOC o 1-5 h z 正確的執(zhí)行順序是A.竊0型B.竊0C.D.33 .假設(shè)OSI結(jié)模型的應(yīng)用層欲竝400 B的數(shù)據(jù)（無拆分），除物軀和應(yīng)用層之外，其他各層在封裝PDU 時(shí)均引人20 B的額外開銷，則應(yīng)用層數(shù)據(jù)傳輸效率約為oA. 80%B. 83%C. 87%D. 91%若信道在無噪聲情況下的極限數(shù)據(jù)傳輸速率不小于信噪比為30dB條件下的極限數(shù)據(jù)傳輸速率，則信號(hào)狀態(tài)數(shù)至少是-A 4B. 8C. 16D. 32在下圖所示的網(wǎng)絡(luò)中,若主機(jī)H 竝一個(gè)封裝訪問

11、Internet的IP分組的IEEE 802.11數(shù)據(jù)幀F(xiàn),則幀F(xiàn)的地址1、地址2和地址3分別是。A. 00-12-34-56-78-9a, 00-12-34-56-78-9b, 00-12-34-56-78-9c00-12-34-56-78-9b, 00-12-34-56-78-9a, 00-12-34-56-78-9cC 00-12-34-56-78-9b, 00-12-34-56-78-9c, 00-12-34-56-78-9aD 00-12-34-56-78-9a, 00-12-34-56-78-9c, 00-12-34-56-78-9b36下列IPIPIPIP地址的是oA E C D

12、 55RIP、OSPF、EGP 報(bào)A TCP、UDP、IPE. TCP、IP、UDPC UDP、TCP、IPD UDP、IP、TCP TOC o 1-5 h z /16劃分為128IP地址個(gè)數(shù)是。A. 254E 256C 510D. 512TCPMSS=1 KB, RTT = 5 ms,乙開辟的接收緩存為64 KB,則甲從連接建立成功至發(fā)送窗口達(dá)到32 KB,需磔的時(shí)間至少是oA. 25 msB. 30 msC 160 msD. 165 msFTP協(xié)遴扌CTCP20DTCP21二、綜合應(yīng)用題：第4147小題，共70分。（15 夕計(jì)算次序）并輸出。例如，當(dāng)下列兩棵表達(dá)式樹作為算法的輸人時(shí)：輸出的

13、等價(jià)中綴表達(dá)式分別為(a+b)*(c*(-d)和(a*b)+(-(c-d)。二叉樹結(jié)點(diǎn)定義如下：typedef struct nodechar data 10 ;/存儲(chǔ)操作數(shù)或操作符struct node *left, *right;BTree;要求：侈c或C+語(yǔ)(8Prim(MST)。請(qǐng)回答下列問題。GAG的MST圖G的MST是唯一的嗎？return sum;fl intfloat,可得至！計(jì)算f(n)的另一個(gè)函數(shù)f2。假設(shè)unsigned和int型數(shù)據(jù)都占32位，float采用IEEE754n=0 f1f1中的變量i和n都定義為int型，則f1是否還會(huì)出現(xiàn)死循環(huán)？為什么？f1(23)f2(

14、23)於f1(24)和f2(24)的返回值分別為33 554 431和33 554 432.0,為什么不相等？f(31)=232-1f1(31)-1,f1(n)f(n)nf2(127)7F80 0000Hf2(nnf2(n)的結(jié)果精確(無舍人)，則最大的n是多少？(10M上，題43中f1的部分源程序(陰影部分)與對(duì)應(yīng)的機(jī)器級(jí)代碼(包括指令的虛擬地址)如下：int fl ( unsigned n)10040102055push ebpfor( unsigned i = 0； ileft=NULL&root-right=NULL)/若為葉結(jié)點(diǎn)printf (%sz/, root-data) ;/輸

15、出操作數(shù)，不加括號(hào)elseif (deepl) printf ( (z/) ；/若有達(dá)式貝!l加 1 層括號(hào)BtreeToExp(root-left, deep+1);-data) ;/操作符BtreeToExp(root-right, deep+1);if (deepl) printf ;/若有達(dá)式貝!|加 1 層括號(hào)【評(píng)分說明】若考生設(shè)計(jì)的算法滿足題目的功能要求，則、根據(jù)所實(shí)現(xiàn)算法的策略及輸出結(jié)果給分，細(xì) 則見下表。分?jǐn)?shù)備注15采用中序遍歷算法且正確，括號(hào)嵌套正確，層數(shù)適當(dāng)。14采用中序遍歷算法且正確，括號(hào)嵌套正確，但括號(hào)嵌套層數(shù)過多。例如， 表達(dá)式最外層加上括號(hào)，或操作數(shù)加括號(hào)如(a)。

16、11采用中序遍歷算法，但括號(hào)嵌套層數(shù)不完全正確。例如，左右括號(hào)數(shù)量不 匹配。9采用中序遍歷算法，但沒有考慮括號(hào)。W7其他若考生采用其他方法得到正確結(jié)果，可參照的評(píng)分標(biāo)準(zhǔn)給分。如果程序中使用了求結(jié)點(diǎn)深度等輔助函數(shù)，但沒有給出相應(yīng)的實(shí)現(xiàn)過程，只要考生進(jìn)行了必要的說明，可不扣 分。若在算法的基本設(shè)計(jì)思想描述中因文字表達(dá)沒有清晰反映出算法思路，但在算法實(shí)現(xiàn)中能夠表達(dá)出算法思想且 正確的，可參照的標(biāo)準(zhǔn)給分。若算法的基本設(shè)計(jì)思想描述或算法實(shí)現(xiàn)中部分正確，可參照中各種情況的相應(yīng)給分標(biāo)準(zhǔn)酌情給分。參考答案中只給出了使用C語(yǔ)言的版本，使用C+語(yǔ)言的答案參照以上評(píng)分標(biāo)準(zhǔn)。解析：PrimSSS就成樹。S 中頂點(diǎn)為

17、A,為(A,D)、(A,B)、(A,E),選擇(A,D)加入 SSA、D(A,B)、(A,E)、(D,E)、(C,D)(D,E)，力口入 S。SA、D、E(A,B)、(C,D)、(C,E)(C,E) S。SA、D、E、C(A,B)、(B,C)(B,C) S。S依次選出的邊為：(A, D),(D, E),(C, E),(B, C) 4 分評(píng)分說明每正確選對(duì)一條邊且次序正確，給1分。若考生選擇的邊正確，但次序不完全正確，酌情給分。G MST2 分邊大，所以此圖的MST唯一。MST是唯一的。(2分)此題不要求回答 充分必要條件，所以回答一個(gè)限制邊權(quán)值的充分條件即可?！驹u(píng)分說明】若考生答案中給出的是其

18、他充分條件，例如帶權(quán)連通圖的所有邊的權(quán)值均不相同，同樣給 分。若考生給出的充分條件對(duì)圖的頂點(diǎn)數(shù)和邊數(shù)做了某些限制，例如，限制了圖中頂點(diǎn)的個(gè)數(shù)(頂點(diǎn)個(gè)數(shù)少 于3個(gè))、限制了圖的粋(圖中沒有環(huán))等，則最高給1分。答案部分正確，酌幡分。Or：由于i和n是unsigned型,故i=n-1是無符號(hào)數(shù)比較,n=0時(shí),n-1的機(jī)器數(shù)為全1,值是232-1,為unsigned 型可表示的最大數(shù)，條件“i=n-l”永真，因此出現(xiàn)死循環(huán)。(2分)若i和n改為int類型，貝環(huán)會(huì)出現(xiàn)死循環(huán)。(1分)因?yàn)椤癷=n-l”是帶符號(hào)整數(shù)比較，n=0時(shí)，n-1的值是-1,當(dāng)i=0時(shí)條件“i=n-l”不成立，此時(shí)退出for循環(huán)。

19、 (1分)f1 (23)與f2 (23)的返回值相等。(1分)f (23) =223+1-1=224-1,它的二進(jìn)制形式是24個(gè)1。int占32位，沒有 溢出。float有1個(gè)符號(hào)位，8個(gè)指數(shù)位，23個(gè)底數(shù)位，23個(gè)底數(shù)位可以表示24位的底數(shù)。所以兩者返回值相等。f1 (23)的機(jī)器數(shù)是 OOFF FFFFH,(1 分)f2 (23)的機(jī)器數(shù)是 4B7F FFFFH。(1 分)顯而易見前者是24個(gè)1,即0000 0000 1111 1111 1111 1111 1111 1111,后者符號(hào)位是0,指數(shù)位為23+1273=1001 0110 ,底數(shù)位是 111 1111 1111 1111 11

20、11 1111 。當(dāng)n=24時(shí)，f(24)=1 1111 1111 1111 1111 1111 1111 B,而f loat型數(shù)只有24位有效位，舍入后數(shù)值增大, 所以 f2 (24)比 f1 (24)大 1。( 1 分)【評(píng)分說明】只要說明f2(24)需舍人處理即可給分。顯然f (31)已超出了 int型姻的表示范圍，用f1 (31)實(shí)現(xiàn)時(shí)得到的機(jī)器數(shù)為32個(gè)1,作為int型數(shù)解釋時(shí) 其值為T,即f1(31)的返回值為-1。(1分)因?yàn)閕nt型最大可表示數(shù)是0后面加31個(gè)1,故使f1(n)的返回值與f(n)相等的最大n值是30。(1分)【評(píng)分說明】對(duì)于第二問，只要給出n=30即可給分。IE

21、EE 754標(biāo)準(zhǔn)用“階碼全1、融全0”表示無窮大。f2返回值為float型，機(jī)器數(shù)7F80 0000H對(duì)應(yīng)的值是+ 8。(1 分)當(dāng)n=126時(shí)，f(126)=2127-1=1.1“1X2126,對(duì)應(yīng)階碼為127+126=253,尾數(shù)部舲人后階碼加1,最終階碼為254, 是IEEE 754單精度格式表示的最大階碼。故使f2結(jié)果不溢出的最大n值為126。( 1分)當(dāng)n=23時(shí)，f (23)為24位1, float型數(shù)有24位有效位，所以不需舍人，結(jié)果精確。故使f2獲得精確結(jié)果的最大 n值為23。(1分)【評(píng)分說明】對(duì)于第二問，只要給出n=23,即可給分。對(duì)于第三問，只要給出n=126,即可給分。

22、解析：M 為 CISC。(1 分)M的指令長(zhǎng)短不一，不符合RISC指令系統(tǒng)特點(diǎn)。(1分)f1的機(jī)器代碼占96B。(1分)因?yàn)閒1的第一條指令pushebp所在的虛擬地址為0040 1020H,最后一條指令“ret”所在的虛擬地址為0040 107FH，所以，f1 的機(jī)令代碼長(zhǎng)度為 0040 107FH - 0040 1020H + 1 = 60H = 96 個(gè)字節(jié)。(1 分)CF=1。(1 分)cmp指令實(shí)現(xiàn)i與n-1的比較功能，進(jìn)行的是減法運(yùn)算。在執(zhí)行f1(0)過程中，n=0,當(dāng)i=0時(shí)，i=0000 0000H, 并且n-1=FFFF FFFFH。因此，當(dāng)執(zhí)行第20條指令時(shí)，在補(bǔ)碼加/減運(yùn)

23、算器中執(zhí)行“0減FFFFFFFFH”的操作，即0000 0000H + 0000 0000H+1 = 0000 0001H此時(shí)，進(jìn)位輸出C = 0,減法運(yùn)算時(shí)的借位標(biāo)志CF = C1 = 1。(2分)f2中不能用shl指令實(shí)現(xiàn)power*2。(1分)因?yàn)閟hl指令用來將一個(gè)整數(shù)的所有有效數(shù)位作為一個(gè)整體左移；而f2中的變量power是float型，其機(jī)器數(shù)中 不包含最高有效數(shù)位，但包含了階碼部分，將其作為一個(gè)整體左移時(shí)并不能實(shí)現(xiàn)“乘2”的功能，因而f2中不能用shl 指令實(shí)現(xiàn)power*2。(2分)浮點(diǎn)數(shù)運(yùn)算比整型運(yùn)算要復(fù)雜，耗時(shí)也較長(zhǎng)。解析：（1分置。（2）push ebp指令的刪地址的最高

24、10位（頁(yè)目錄號(hào)）為00 0000 0001,中間10位（頁(yè)表索引）為00 0000 0001, 所以，取該指令時(shí)訪問了頁(yè)目錄的第1個(gè)表項(xiàng)，（1分）在對(duì)應(yīng)的頁(yè)表中訪問了第1個(gè)表項(xiàng)。（1分）（3）scanf（）P1P序喚醒，變?yōu)榫途w態(tài)。（1分）P被調(diào)度辭調(diào)度，變?yōu)檫\(yùn)行態(tài)。（1分）CPU狀態(tài)會(huì)從用戶態(tài)變?yōu)閮?nèi)核態(tài)。（1分）;先找出線程對(duì)在各個(gè)變量上的互斥、并發(fā)關(guān)系。如果是一讀一寫或兩個(gè)都是寫，那么這就是互斥關(guān)系。每一個(gè)互 斥關(guān)系都需要一個(gè)信號(hào)量進(jìn)行調(diào)節(jié)。semaphore mutex_y1=1; /mutex_y1 用于 threadl 與 thread3 對(duì)變量 y 的問。 semaphore mutex_y2=1; /mutex_y2 用于 thread2 與 thread3 對(duì)變量 y 的可 semaphore mutex_z=1; /mutex