2017年考研計(jì)算機(jī)統(tǒng)考408真題

2017年考研計(jì)算機(jī)統(tǒng)考408真題一、單項(xiàng)選擇題1. 下列函數(shù)的時(shí)間復(fù)雜度是 1 。intfunc(intn){inti=0;sum=0;while(sum<n)sum+=++i;returni;}O(logn)O(n1/2)O(n)O(nlogn)2.下列關(guān)于棧的敘述中，錯(cuò)誤的是2。I.采用非遞歸方式重寫(xiě)遞歸程序時(shí)必須使用棧II.函數(shù)調(diào)用時(shí)，系統(tǒng)要用棧保存必要的信息III.只要確定了入棧的次序，即可確定出棧次序IV.棧是一種受限的線性表，允許在其兩端進(jìn)行操作僅I僅I、II、III僅I、III、IV僅II、III、IV3.適用于壓縮存儲(chǔ)稀疏矩陣的兩種存儲(chǔ)結(jié)構(gòu)是3。三元組表和十字鏈表三元組表和鄰接矩陣十字鏈表和二叉鏈表鄰接矩陣和十字鏈表4. 要使一棵非空二叉樹(shù)的先序序列與中序序列相同， 其所有非葉結(jié)點(diǎn)須滿(mǎn)足的條件是。只有左子樹(shù)只有右子樹(shù)結(jié)點(diǎn)的度均為1結(jié)點(diǎn)的度均為25. 已知一棵二叉樹(shù)的樹(shù)形如下圖所示，其后序序列為的結(jié)點(diǎn)是 5 。

e,a,c,b,d,g,f，樹(shù)中與結(jié)點(diǎn)

a同層cdfg已知字符集{a,b,c,d,e,f,g,h}，若各字符的哈夫曼編碼依次是0100,10,0000,0101,001,011,11,0001，則編碼序列0100011001001011110101的譯碼結(jié)果是6。acgabfhadbagbbafbeagdafeefgd7.已知無(wú)向圖G含有16條邊，其中度為4的頂點(diǎn)個(gè)數(shù)為3，度為3的頂點(diǎn)個(gè)數(shù)為4，其他頂點(diǎn)的度均小于3。圖G所含的頂點(diǎn)個(gè)數(shù)至少是7。A.10B.11C.13D.158.下列二叉樹(shù)中，可能成為折半查找判定樹(shù)（不含外部結(jié)點(diǎn)）的是8。A.B.C.D.9. 下列應(yīng)用中，適合使用 B+樹(shù)的是 9 。編譯器中的詞法分析關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)中的索引網(wǎng)絡(luò)中的路由表快速查找操作系統(tǒng)的磁盤(pán)空閑塊管理10.在內(nèi)部排序中，若選擇了歸并排序而沒(méi)有選擇插入排序，則可能的理由是10。僅II僅III僅I、II僅I、III下列排序方法中，若將順序存儲(chǔ)更換為鏈?zhǔn)酱鎯?chǔ)，則算法的時(shí)間效果會(huì)降低的是11。I.插入排序II.選擇排序III.起泡排序IV.希爾排序V.堆排序僅I、II僅II、III僅III、IV僅IV、V12.假定計(jì)算機(jī)M1和M2具有相同的指令集體系結(jié)構(gòu)（ISA），主頻分別為1.5GHz和1.2GHz。在M1和M2上運(yùn)行某基準(zhǔn)程序P，平均CPI分別為2和1，則程序P在M1和M2上運(yùn)行時(shí)間的比值是12。A.0.4B.0.625C.1.6D.2.5某計(jì)算機(jī)主存按字節(jié)編址，由4個(gè)64M*8位的DRAM芯片采用交叉編址方式構(gòu)成，并與寬度為32位的存儲(chǔ)器總線相連，主存每次最多讀寫(xiě)32位數(shù)據(jù)。若double型變量x的主存地址為804001AH，則讀取x需要的存儲(chǔ)周期是13。A.1B.2C.3D.4某C語(yǔ)言程序段如下：for(i=0;i<=9;i++){ lemp=1;for(j<0;j<=I;j++)temp*=a[j];sum+=temp;}下列關(guān)于數(shù)組a的訪問(wèn)局部性的描述中，正確的是14。時(shí)間局部性和空間局部性皆有無(wú)時(shí)間局部性，有空間局部性有時(shí)間局部性，無(wú)空間局部性時(shí)間局部性和空間局部性皆無(wú)15.下列尋址方式中，最適合按下標(biāo)順序訪問(wèn)一維數(shù)組元素的是15。相對(duì)尋址寄存器尋址直接尋址變址尋址某計(jì)算機(jī)按字節(jié)編址，指令字長(zhǎng)固定且只有兩種指令格式，其中三地址指令29條，二地址指令 107條，每個(gè)地址字段為 6位，則指令字長(zhǎng)至少應(yīng)該是 16 。24位26位28位32位17.下列關(guān)于超標(biāo)量流水線特性的敘述中，正確的是16。僅II僅I、III僅II、IIII、II和III18.下列關(guān)于主存儲(chǔ)器（MM）和控制存儲(chǔ)器（CS）的敘述中，錯(cuò)誤的是18。MM在CPU外，CS在CPU內(nèi)MM按地址訪問(wèn)，CS按內(nèi)存訪問(wèn)MM存儲(chǔ)指令和數(shù)據(jù)，CS存儲(chǔ)微指令MM用RAM和ROM實(shí)現(xiàn)，CS用ROM實(shí)現(xiàn)19.下列關(guān)于指令流水線數(shù)據(jù)通路的敘述中，錯(cuò)誤的是19。包含生成控制信號(hào)的控制部件包含算法邏輯運(yùn)算部件（ALU）包含通用寄存器組和取指部件由組合邏輯電路和時(shí)序邏輯電路組合而成20.下列關(guān)于多總線結(jié)構(gòu)的敘述中，錯(cuò)誤的是20?？拷麮PU的總線速度較快存儲(chǔ)器總線可支持突發(fā)傳送方式總線之間須通過(guò)橋接器相連PCI_Express*16采用并行傳輸方式21.I/O指令實(shí)現(xiàn)的數(shù)據(jù)傳送通常發(fā)生在21。I/O設(shè)備和I/O端口之間通用寄存器和I/O設(shè)備之間I/O端口和I/O端口之間通用寄存器和I/O端口之間22.下列關(guān)于多重中斷系統(tǒng)的敘述中，錯(cuò)誤的是22。在一條指令執(zhí)行結(jié)束時(shí)響應(yīng)中斷中斷處理期間CPU處于關(guān)中斷狀態(tài)中斷請(qǐng)求的產(chǎn)生與當(dāng)前指令的執(zhí)行無(wú)關(guān)CPU通過(guò)采樣中斷請(qǐng)求信號(hào)檢測(cè)中斷請(qǐng)求假設(shè)4個(gè)作業(yè)到達(dá)系統(tǒng)的時(shí)刻和運(yùn)行時(shí)間如下表所示。作業(yè)到達(dá)時(shí)間t運(yùn)行時(shí)間J103J213J312J431系統(tǒng)在t=2時(shí)開(kāi)始作業(yè)調(diào)度。若分別采用先來(lái)先服務(wù)和短作業(yè)優(yōu)先調(diào)度算法，則選中的作業(yè)分別是 23J2、J3J1、J4J2、J4J1、J3執(zhí)行系統(tǒng)調(diào)用的過(guò)程包括如下主要操作：返回用戶(hù)態(tài)執(zhí)行陷入（trap）指令傳遞系統(tǒng)調(diào)用參數(shù)執(zhí)行相應(yīng)的服務(wù)程序正確的執(zhí)行順序是24。A. 2) 3) 1) 4)B. 2) 3) 3) 1)C. 3) 2) 4) 1)D. 3) 4) 2) 1)某計(jì)算機(jī)按字節(jié)編址，其動(dòng)態(tài)分區(qū)內(nèi)存管理采用最佳適應(yīng)算法，每次分配和回收內(nèi)存后都對(duì)空閑分區(qū)鏈重新排序。當(dāng)前空閑分區(qū)信息如下所示。分區(qū)起始地址20K500K1000K200K分區(qū)大小40KB80KB100KB200KB回收起始地址為60K、大小為140KB的分區(qū)后，系統(tǒng)中空閑分區(qū)的數(shù)量、空閑分區(qū)鏈第一個(gè)分區(qū)的起始地址和大小分別是25。3、20K、380KB3、500K、80KB4、20K、180KB4、500K、80KB26.某文件系統(tǒng)的簇和磁盤(pán)扇區(qū)大小分別為1KB和512B。若一個(gè)文件的大小為1026B，則系統(tǒng)分配給該文件的磁盤(pán)空間大小是26。A.1026BB.1536BC.1538B2048B27.下列有關(guān)基于時(shí)間片的進(jìn)程調(diào)度的敘述中，錯(cuò)誤的是27。時(shí)間片越短，進(jìn)程切換的次數(shù)越多，系統(tǒng)開(kāi)銷(xiāo)也越大當(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)開(kāi)銷(xiāo)和進(jìn)程數(shù)量等。28.與單道程序系統(tǒng)相比，多道程序系統(tǒng)的優(yōu)先是28。I.CPU利用率高II.系統(tǒng)開(kāi)銷(xiāo)小III.系統(tǒng)吞吐量大IV.I/O設(shè)備利用率高A.僅I、IIIB.僅I、IVC.僅II、IIID.僅I、III、IV29.下列選項(xiàng)中，磁盤(pán)邏輯格式化程序所做的工作是29。I.對(duì)磁盤(pán)進(jìn)行分區(qū)II.建立文件系統(tǒng)的根目錄III.確定磁盤(pán)扇區(qū)校驗(yàn)碼所占位數(shù)IV.對(duì)保存空閑磁盤(pán)塊信息的數(shù)據(jù)結(jié)構(gòu)進(jìn)行初始化僅II僅II、IV僅III、IV僅I、II、IV30.某文件系統(tǒng)中，針對(duì)每個(gè)文件，用戶(hù)類(lèi)別分為4類(lèi)：安全管理員、文件主、文件主的伙伴、其他用戶(hù)；訪問(wèn)權(quán)限分為5種：完全控制、執(zhí)行、修改、讀取、寫(xiě)入。若文件控制塊中用二進(jìn)制位串表示文件權(quán)限，為表示不同類(lèi)別用戶(hù)對(duì)一個(gè)文件的訪問(wèn)權(quán)限，則描述文件權(quán)限的位數(shù)至少應(yīng)為30。A.5B.9C.12D.2031.若文件f1的硬鏈接為f2，兩個(gè)進(jìn)程分別打開(kāi)f1和f2，獲得對(duì)應(yīng)的文件描述符為fd1和fd2，則下列敘述中，正確的是31。I.f1和f2的讀寫(xiě)指針位置保持相同II.f1和f2共享同一個(gè)內(nèi)存索引結(jié)點(diǎn)III.fd1和fd2分別指向各自的用戶(hù)打開(kāi)文件表中的一項(xiàng)僅III僅II、III僅I、III、II和III系統(tǒng)將數(shù)據(jù)從磁盤(pán)讀到內(nèi)存的過(guò)程包括以下操作：DMA控制器發(fā)出中斷請(qǐng)求初始化DMA控制器并啟動(dòng)磁盤(pán)從磁盤(pán)傳輸一塊數(shù)據(jù)到內(nèi)存緩沖區(qū)執(zhí)行“DMA結(jié)束”中斷服務(wù)程序正確的執(zhí)行順序是32。A. 3) 1) 2) 4)B. 2) 3) 1) 4)C. 2) 1) 3) 4)D. 1) 2) 4) 3)假設(shè)OSI參考模型的應(yīng)用層欲發(fā)送400B的數(shù)據(jù)（無(wú)拆分），除物理層和應(yīng)用層之處，其他各層在封裝PDU時(shí)均引入20B的額外開(kāi)銷(xiāo)，則應(yīng)用層數(shù)據(jù)傳輸效率約為33。80%83%87%91%34.若信道在無(wú)噪聲情況下的極限數(shù)據(jù)傳輸速率不小于信噪比為30dB條件下的極限數(shù)據(jù)傳輸速率，則信號(hào)狀態(tài)至少是34。A.4B.8C.16D.3235.在下圖所示的網(wǎng)絡(luò)中，若主機(jī)H發(fā)送一個(gè)封裝訪問(wèn)InternetIP分組的IEEE802.11數(shù)據(jù)幀F(xiàn)，則幀F(xiàn)的地址1、地址2和地址3分別是35。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-9c00-12-34-56-78-9b,00-12-34-56-78-9c,00-12-34-56-78-9a00-12-34-56-78-9a,00-12-34-56-78-9c,00-12-34-56-78-9b36.下列IP地址中，只能作為 IP分組源IP地址但不能作為目的 IP地址是 36 。55直接封裝RIP，OSPF，BGP報(bào)文的協(xié)議分別是37。TCP、UDP、IPTCP、IP、UDPUDP、TCP、IPUDP、IP、TCP38.若將網(wǎng)絡(luò) /16劃分為 128個(gè)規(guī)模相同的子網(wǎng)，則每個(gè)子網(wǎng)可分配的最大 IP地址個(gè)數(shù)是 38 。254256510512若甲向乙發(fā)起了一個(gè)TCP連接，最大段長(zhǎng)MSS=KB，RTT=5ms，乙開(kāi)辟的接收緩存為64KB，則甲從連接建立蒽至發(fā)送窗口達(dá)到 32KB，需經(jīng)過(guò)的時(shí)間至少是 38 。25ms30ms160ms165ms40.下列關(guān)于FTP協(xié)議的敘述中，錯(cuò)誤的是 40 。數(shù)據(jù)連接在每次數(shù)據(jù)傳輸完畢后就關(guān)閉控制連接在整個(gè)會(huì)話期間保持打開(kāi)狀態(tài)服務(wù)器與客戶(hù)端的TCP20端口建立數(shù)據(jù)連接客戶(hù)端與服務(wù)器的TCP21端口建立控制連接二、綜合應(yīng)用題請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，將給定的表達(dá)式樹(shù)（二叉樹(shù)）轉(zhuǎn)換為等價(jià)的中綴表達(dá)式（通過(guò)括號(hào)反映操作符的計(jì)算次序）并輸出。例如，當(dāng)下列兩棵表達(dá)式作為算法的輸入時(shí)：輸出的等價(jià)中綴表達(dá)式分別為 (a+b)*(c+(-d))和(a*b)+(-(-c-d))。二叉樹(shù)結(jié)點(diǎn)定義如下：Typedefstructnode{ chardata[10]; //存儲(chǔ)操作數(shù)或操作符Structnode*left,*right;}BTree;要求：給出算法的基本設(shè)計(jì)思想。根據(jù)設(shè)計(jì)思想，采用C或C++語(yǔ)言描述算法，關(guān)鍵之處給出注釋。42.

使用 Prim（普里姆）算法求帶權(quán)連通圖的最?。ù鷥r(jià)）生成樹(shù)（ MST）。請(qǐng)回答下列問(wèn)題。對(duì)下列圖G，從頂點(diǎn)A開(kāi)始求G的MST，依次給出按算法選出的邊。圖G的MST是唯一的嗎？對(duì)任意的帶權(quán)連通圖，滿(mǎn)足什么條件時(shí)，其MST是唯一的？43.已知，計(jì)算f(n)的C語(yǔ)言函數(shù)f1如下：1intf1(unsignedn)2{intsum=1,power=1;3for(unsignedi=0;i<=n-1;i++)4{power*=2;5sum+=power;6}7returnsum;8}將f1中的int都改為float，可得到計(jì)算 f(n)的另一個(gè)函數(shù) f2。假設(shè)unsigned和int型數(shù)據(jù)都占 32位，float采用IEEE754單精度標(biāo)準(zhǔn)。請(qǐng)回答下列問(wèn)題。當(dāng)n=0時(shí)，f1會(huì)出現(xiàn)死循環(huán)，為什么？若將f1中的變量i和n都定義為int型，則f1是否還會(huì)出現(xiàn)死循環(huán)？為什么？f1(23)和f2(23)的返回值是否相等？機(jī)器數(shù)各是什么（用十六進(jìn)制表示）？F1(24)和f2(24)的返回值分別為33554431和33554432.0，為什么不相等？f(31)=232-1，而f1(31)的返回值卻為-1，為什么？若使f1(n)的返回值與f(n)相等，則最大的n是多少？(5)F2(127)的機(jī)器數(shù)為 7F800000H，對(duì)應(yīng)的值是什么？若使 f2(n)的結(jié)果不溢出，則最大的n是什么？若使 f2(n)的結(jié)果精確（無(wú)舍入），則最大的 n是多少？在按字節(jié)編址的計(jì)算機(jī)M上，題43中f1的部分源程序（部分）與對(duì)應(yīng)的機(jī)器級(jí)代碼（包括指令的虛擬地址）如下：intf1(unsignedn)1 00401020 55 pushebp?? ?? ??for(unsignedi=0;i<=n-1;i++)?..????200040105E394DF4cmpdwordptr[ebp-0Ch],ecx??????{power*=2;?? ?? ??23 00401066 D1E2 shledx,l?? ?? ??returnsum;?? ?? ??35 0040107F C3 ret其中，機(jī)器級(jí)代碼行包括行號(hào)、虛擬地址、機(jī)器指令和匯編指令。請(qǐng)回答下列問(wèn)題。計(jì)算機(jī)M是RISC還是CISC？為什么？f1的機(jī)器指令代碼共占多少字節(jié)？要求給出計(jì)算過(guò)程。第20條指令cmp通過(guò)i減n-1實(shí)現(xiàn)對(duì)i和n-1的比較。執(zhí)行f1(0)過(guò)程中，當(dāng)i=0時(shí)，cmp指令執(zhí)行后，進(jìn)/借位標(biāo)志CF的內(nèi)容是什么？要求給出計(jì)算過(guò)程。第23條指令shl通過(guò)左移操作實(shí)現(xiàn)了power*2運(yùn)算，在f2中能否也用shl指令實(shí)現(xiàn)power*2？為什么？假定題44給出的計(jì)算機(jī)M采用二級(jí)分布虛擬存儲(chǔ)管理方式，邪氣地址格式如下：頁(yè)目錄號(hào)（10位）請(qǐng)針對(duì)題43的函數(shù)f1和題

頁(yè)表索引（10位） 頁(yè)內(nèi)偏移量（12位）44中的機(jī)器指令代碼，回答下列問(wèn)題。函數(shù)f1的機(jī)器指令代碼占多少頁(yè)？取第1條指令(pushebp)時(shí)，若在進(jìn)行地址變換的過(guò)程中需要訪問(wèn)內(nèi)存中的頁(yè)目錄和頁(yè)表，而會(huì)分別訪問(wèn)它們各自的第幾個(gè)表項(xiàng)（編號(hào)從 0開(kāi)始）？M的I/O采用中斷控制方式。若進(jìn)程P在調(diào)用f1之前通過(guò)scanf()獲取n的值，則在執(zhí)行scanf()的過(guò)程中，進(jìn)程P的狀態(tài)會(huì)如何變化？CPU是否會(huì)進(jìn)入內(nèi)核態(tài)？46.某進(jìn)程中有 3個(gè)并發(fā)執(zhí)行的線程 thread1、thread2//復(fù)數(shù)的結(jié)構(gòu)類(lèi)型定義 thread1typedefstruct {{ cnumw;floata; w=add(x,y);

和thread3，其偽代碼如下所示。thread3{cnumw;w.a=1;floatb;}cnum;

}

??

w.b=1;z=