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

1、2017年考研計(jì)算機(jī)統(tǒng)考408真題一、單項(xiàng)選擇題下列函數(shù)的時(shí)間復(fù)雜度是int fun c(i nt n)1.int i = 0; sum = 0;while( sum < n) sum += +i; return i;2.3.4.A.B.C.D.O(log n)O(n1/2) 0(n)O(nl og n)下列關(guān)于棧的敘述中，錯(cuò)誤的是I. 采用非遞歸方式重寫遞歸程序時(shí)必須使用棧II. 函數(shù)調(diào)用時(shí)，系統(tǒng)要用棧保存必要的信息III. 只要確定了入棧的次序，即可確定出棧次序IV棧是一種受限的線性表，允許在其兩端進(jìn)行操作A.僅1B.僅 1、 II、 IIIC.僅 1、III、IVD.僅 II、HI

2、、IV適用于壓縮存儲(chǔ)稀疏矩陣的兩種存儲(chǔ)結(jié)構(gòu)是A.B.C.D.二兀組表和十字鏈表 三元組表和鄰接矩陣 十字鏈表和二叉鏈表 鄰接矩陣和十字鏈表要使一棵非空二叉樹的先序序列與中序序列相同, _4_。只有左子樹 只有右子樹 結(jié)點(diǎn)的度均為1 結(jié)點(diǎn)的度均為2其所有非葉結(jié)點(diǎn)須滿足的條件是A.B.C.D.e,a,c,b,d,g,f，樹中與結(jié)點(diǎn)a同層5.已知一棵二叉樹的樹形如下圖所示，其后序序列為 的結(jié)點(diǎn)是5。A. cB. dC.fD.g已知字符集a,b,c,d,e,f,g,h， 若各字符的哈夫曼編碼依次0100,10,0000,0101,001,011,11,0001，則編碼序列的譯碼結(jié)果是6。A.a c g

3、 a b f hB.a d b a g b bC.a f b e a g dD.a f e e f g d已知無向圖G含有16條邊，其中度為4的頂點(diǎn)個(gè)數(shù)為3，度為3的頂點(diǎn)個(gè)數(shù)為其他也頂點(diǎn)的度均小于 3。圖G所含的頂點(diǎn)個(gè)數(shù)至少是7。A.10B.11C.13D.156.7.下列二叉樹中，可能成為折半查找判定樹（不含外部結(jié)點(diǎn)）的是是4,8 。9.D.C.下列應(yīng)用中，適合使用B+樹的是9 。10A.B.C.編譯器中的詞法分析 關(guān)系數(shù)據(jù)庫系統(tǒng)中的索引 網(wǎng)絡(luò)中的路由表快速查找 操作系統(tǒng)的磁盤空閑塊管理D.10.在內(nèi)部排序中，若選擇了歸并排序而沒有選擇插入排序，則可能的理由是OI. 歸并排序的程序代碼更短I

4、I. 歸并排序的占用空間更少III. 歸并排序的運(yùn)行效率更高A.僅IIB.僅IIIC.僅 1、IID.僅1、山11.下列排序方法中,11若將順序存儲(chǔ)更換為鏈?zhǔn)酱鎯?chǔ)，則算法的時(shí)間效果會(huì)降低的是OI.插入排序II選擇排序III.起泡排序IV希爾排序V堆排序A.B.C.僅 I、II僅II、山僅山、僅IV、IVD.12.假定計(jì)算機(jī)VM11.2GHzo 在 M1和M2上運(yùn)行某基準(zhǔn)程序P,平均CPI分別為2和1，則程序P在M1和M2上運(yùn)行時(shí)間的比值是12 OA.0.4B.0.625C.1.6D.2.5某計(jì)算機(jī)主存按字節(jié)編址，由4個(gè)64M*8位的DRAM芯片采用交叉編址方式構(gòu)成，并與寬度為32位的存儲(chǔ)器總線

5、相連，主存每次最多讀寫32位數(shù)據(jù)。若double型變量x的主存地址為 804 001AH,則讀取x需要的存儲(chǔ)周期是13 OA.1B.2C.3D.413.和M2具有相同的指令集體系結(jié)構(gòu)（ISA）,主頻分別為1.5GHz和14.某C語言程序段如下：for(i = 0; i <= 9; i+)lemp = 1;for(j < 0; j <= I; j+) temp *= aj; sum += temp;A.時(shí)間局部性和空間局部性皆有B.無時(shí)間局部性，有空間局部性C.有時(shí)間局部性，無空間局部性D.時(shí)間局部性和空間局部性皆無下列尋址方式中，最適合按下標(biāo)順序訪問一維數(shù)組兀素的是15 。A

6、.相對(duì)尋址B.寄存器尋址C.直接尋址D.變址尋址某計(jì)算機(jī)按字節(jié)編址，指令字長(zhǎng)固定且只有兩種指令格式，其中三地址指令二地址指令107條，每個(gè)地址字段為 6位，則指令字長(zhǎng)至少應(yīng)該是16A.24位B.26位C.28位D.32位下列關(guān)于數(shù)組a的訪問局部性的描述中，正確的是15.16.O29條,16 。14 。下列關(guān)于超標(biāo)量流水線特性的敘述中，正確的是I. 能縮短流水線功能段的處理時(shí)間II. 能在一個(gè)時(shí)鐘周期內(nèi)同時(shí)發(fā)射多條指令I(lǐng)II. 能結(jié)合動(dòng)態(tài)調(diào)度技術(shù)提高指令執(zhí)行并行性17.A.僅IIB.僅1、山C.僅II、山D.1、II 和 III下列關(guān)于主存儲(chǔ)器（MM ）和控制存儲(chǔ)器（CS的敘述中A.MM在CPU

7、外，CS在CPU內(nèi)B.MM按地址訪問，CS按內(nèi)存訪問C.MM存儲(chǔ)指令和數(shù)據(jù)，CS存儲(chǔ)微指令D.MM用RAM和ROM實(shí)現(xiàn)，CS用ROM實(shí)現(xiàn)下列關(guān)于指令流水線數(shù)據(jù)通路的敘述中，錯(cuò)誤的是A.包含生成控制信號(hào)的控制部件B.包含算法邏輯運(yùn)算部件（ALU）C.包含通用寄存器組和取指部件D.由組合邏輯電路和時(shí)序邏輯電路組合而成下列關(guān)于多總線結(jié)構(gòu)的敘述中，錯(cuò)誤的是20 。A.-" - - 一 ' . - / 靠近CPU的總線速度較快B.存儲(chǔ)器總線可支持突發(fā)傳送方式C.總線之間須通過橋接器相連D.PC l_Ex press*16采用并行傳輸方式I/O指令實(shí)現(xiàn)的數(shù)據(jù)傳送通常發(fā)牛在21 。A.I/

8、O設(shè)備和I/O端口之間B.通用寄存器和I/O設(shè)備之間C.I/O端口和I/O端口之間D.通用寄存器和I/O端口之間18.19.20.，錯(cuò)誤的是19 。18 。21.22.下列關(guān)于多重中斷系統(tǒng)的敘述中，錯(cuò)誤的是22 。分區(qū)起始地址20K500K1000K200K分區(qū)大小40KB80KB100KB200KB回收起始地址為 60K、大小為140KB的分區(qū)后，系統(tǒng)中空閑分區(qū)的數(shù)量、空閑分區(qū) 鏈第一個(gè)分區(qū)的起始地址和大小分別是A.B.在一條指令執(zhí)行結(jié)束時(shí)響應(yīng)中斷 中斷處理期間CPU處于關(guān)中斷狀態(tài) 中斷請(qǐng)求的產(chǎn)生與當(dāng)前指令的執(zhí)行無關(guān) CPU通過采樣中斷請(qǐng)求信號(hào)檢測(cè)中斷請(qǐng)求作業(yè)到達(dá)時(shí)間t運(yùn)行時(shí)間J103J21

9、3J312J431系統(tǒng)在t=2時(shí)開始作業(yè)調(diào)度。若分別采用先來先服務(wù)和短作業(yè)優(yōu)先調(diào)度算法，則選中的作業(yè)分別是23C.D.23.假設(shè)4個(gè)作業(yè)到達(dá)系統(tǒng)的時(shí)刻和運(yùn)行時(shí)間如下表所示。A.J2、J3B.J1、J4C.J2、J4D.J1、J324.執(zhí)行系統(tǒng)調(diào)用的過程包括如下主要操作:1)2)3)4)返回用戶態(tài)執(zhí)行陷入(trap)指令 傳遞系統(tǒng)調(diào)用參數(shù)執(zhí)行相應(yīng)的服務(wù)程序正確的執(zhí)行順序是24。A.B.2)2)3)3)3)3)2)4)1)3)4)2)4)1)1)1)C.D.25.某計(jì)算機(jī)按字節(jié)編址，其動(dòng)態(tài)分區(qū)內(nèi)存管理采用最佳適應(yīng)算法，每次分配和回收內(nèi) 存后都對(duì)空閑分區(qū)鏈重新排序。當(dāng)前空閑分區(qū)信息如下所示。25 。

10、26.某文件系統(tǒng)的簇和磁盤扇區(qū)大小分別為 則系統(tǒng)分配給該文件的磁盤空間大小是1KB和512B。若一個(gè)文件的大小為1026B，26 。A.3、20K、380KBB.3、500K、80KBC.4、20K、180KBD.4、500K、80KBA.1026BB.1536BC.1538BD.2048B27 。27.下列有關(guān)基于時(shí)間片的進(jìn)程調(diào)度的敘述中，錯(cuò)誤的是28.29.30.A.B.C.D.時(shí)間片越短，進(jìn)程切換的次數(shù)越多，系統(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ù)量等

11、。與單道程序系統(tǒng)相比，多道程序系統(tǒng)的優(yōu)先是I. CPU利用率高II. 系統(tǒng)開銷小III. 系統(tǒng)吞吐量大IV. I/O設(shè)備利用率高A.僅1、IIIB.僅1、IVC.僅II、IIID.僅1、山、IV下列選項(xiàng)中，磁盤邏輯格式化程序所做的工作是I. 對(duì)磁盤進(jìn)行分區(qū)II. 建立文件系統(tǒng)的根目錄III. 確定磁盤扇區(qū)校驗(yàn)碼所占位數(shù)IV對(duì)保存空閑磁盤塊信息的數(shù)據(jù)結(jié)構(gòu)進(jìn)行初始化A.僅IIB.僅II、IVC.僅山、IVD.僅1、II、IV某文件系統(tǒng)中，針對(duì)每個(gè)文件，用戶類別分為 的伙伴、其他用戶；訪問權(quán)限分為 文件控制塊中用二進(jìn)制位串表示文件權(quán)限， 權(quán)限，則描述文件權(quán)限的位數(shù)至少應(yīng)為A.B.C.91228 。2

12、9 。4類：安全管理員、文件主、文件主5種：完全控制、執(zhí)行、修改、讀取、寫入。若 為表示不同類別用戶對(duì)一個(gè)文件的訪問30。20D.31.若文件f1的硬鏈接為f2,兩個(gè)進(jìn)程分別打開f1和f2，獲得對(duì)應(yīng)的文件描述符為fd1和fd2，則下列敘述中，正確的是31。I. f1和f2的讀寫指針位置保持相同II. f1和f2共享同一個(gè)內(nèi)存索引結(jié)點(diǎn)III. fd1和fd2分別指向各自的用戶打開文件表中的一項(xiàng)A.僅IIIB.僅II、山C.僅 1、IID.1、II 和 IIIDMA控制器發(fā)出中斷請(qǐng)求 初始化DMA控制器并啟動(dòng)磁盤 從磁盤傳輸一塊數(shù)據(jù)到內(nèi)存緩沖區(qū) 執(zhí)行“ DMA結(jié)束”中斷服務(wù)程序系統(tǒng)將數(shù)據(jù)從磁盤讀到

13、內(nèi)存的過程包括以下操作:1)2)3)4)34.正確的執(zhí)行順序是32 。A.B.C.3)2)2)1)1)3)1)2)2)1)3)4)4)4)4)3)D.33.假設(shè)OSI參考模型的應(yīng)用層欲發(fā)送 400B的數(shù)據(jù)（無拆分），除物理層和應(yīng)用層之處, 其他各層在封裝 PDU時(shí)均引入20B的額外開銷，則應(yīng)用層數(shù)據(jù)傳輸效率約為_33。A.80%B.83%C.87%D.91%34.若信道在無噪聲情況下的極限數(shù)據(jù)傳輸速率不小于信噪比為 據(jù)傳輸速率，則信號(hào)狀態(tài)至少是34 。A.B.C.816D.35.在下圖所示的網(wǎng)絡(luò)中，若主機(jī) 據(jù)幀F(xiàn),則幀F(xiàn)的地址1、地址32HDn 12-24=5&=T&(<

14、A.B.C.30dB條件下的極限數(shù)H發(fā)送一個(gè)封裝訪問In ternet IP分組的IEEE 802.11數(shù) 2和地址3分別是 35。AHInierticl00-12-3456 78-9b00-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-

15、78-9bD.36.下列IP地址中，只能作為IP分組源IP地址但不能作為目的IP地址是A.O.O.O.O36 。B.C.D.37.直接封裝 RIP, OSPF BGP報(bào)文的協(xié)議分別是37 。55A.TCP UDP、IPB.TCP IP、UDPC.UDP、TCP IPD.UDP、IP、TCP若將網(wǎng)絡(luò) /16地址個(gè)數(shù)是38 。A.254B.256劃分為128個(gè)規(guī)模相同的子網(wǎng)，則每個(gè)子網(wǎng)可分配的最大IP38.C. 510D. 512MSS=KB RTT=5ms,乙開辟的接收緩存為32KB,需經(jīng)過的時(shí)間至少是38 。39

16、.若甲向乙發(fā)起了一個(gè) TCP連接，最大段長(zhǎng)64KB,則甲從連接建立蒽至發(fā)送窗口達(dá)到A.25msB.30msC.160msD.165ms下列關(guān)于FTP協(xié)議的敘述中，錯(cuò)誤的是40 。A.數(shù)據(jù)連接在每次數(shù)據(jù)傳輸完畢后就關(guān)閉B.控制連接在整個(gè)會(huì)話期間保持打開狀態(tài)C.服務(wù)器與客戶端的TCP 20端口建立數(shù)據(jù)連接D.客戶端與服務(wù)器的TCP 21端口建立控制連接40.二、綜合應(yīng)用題41.請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，將給定的表達(dá)式樹（二叉樹）轉(zhuǎn)換為等價(jià)的中綴表達(dá)式（通過括 號(hào)反映操作符的計(jì)算次序）并輸出。例如，當(dāng)下列兩棵表達(dá)式作為算法的輸入時(shí)：(a+b)*(c+(-d)和(a*b)+(-(-c-d)。輸出的等價(jià)中綴表達(dá)式

17、分別為二叉樹結(jié)點(diǎn)定義如下：Typ edef struct node char data10;Struct n ode * left, * right;BTree;要求：（1）給出算法的基本設(shè)計(jì)思想。（2）根據(jù)設(shè)計(jì)思想，采用C或C+語言描述算法，關(guān)鍵之處給出注釋。42.使用Prim （普里姆）算法求帶權(quán)連通圖的最小（代價(jià)）生成樹（MST）。請(qǐng)回答下列問題。對(duì)下列圖G,從頂點(diǎn)A開始求G的MST,/存儲(chǔ)操作數(shù)或操作符(1)依次給出按算法選出的邊。對(duì)任意的帶權(quán)連通圖，滿足什么條件時(shí)，其MST是唯一的?43.已知 f(n) = Zi=0 2i = 2n+11 =1IB，計(jì)算f(n)的C語言函數(shù)f1如下:

18、1234int f1( un sig ned n) int sum = 1, po wer = 1;for(un sig ned i =0; i <= n-1; i+) po wer *= 2;sum += po wer; return sum;8將f1中的型數(shù)據(jù)都占 請(qǐng)回答下列問題。當(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)的返回值分別為 33 554 431和33 554 432.0，為什么不相等？ f(31)

19、=232-1，而f1(31)的返回值卻為-1,為什么？若使f1(n)的返回值與f(n)相等， 則最大的n是多少？F2(127)的機(jī)器數(shù)為7F80 0000H,對(duì)應(yīng)的值是什么？若使f2(n)的結(jié)果不溢出，則最大的n是什么？若使f2(n)的結(jié)果精確(無舍入)，則最大的n是多少？44.在按字節(jié)編址的計(jì)算機(jī)M上，題43中f1的部分源程序(部分)與對(duì)應(yīng)的機(jī)器級(jí)代碼(包括指令的虛擬地址)如下：int f1( un sig ned n)0040102055int都改為float，可得到計(jì)算f(n)的另一個(gè)函數(shù)f2。假設(shè)unsigned和int 32位，float采用IEEE 754單精度標(biāo)準(zhǔn)。(1)push

20、 ebpfor(un sig ned i = 0; i <=n-1; i+)200040105E39 4D F4cmp dword p treb p-OCh, ecxpo wer *= 2;2300401066 D1 E2shl edx, lreturn sum;35其中，機(jī)器級(jí)代碼行包括行號(hào)、虛擬地址、機(jī)器指令和匯編指令。 請(qǐng)回答下列問題。計(jì)算機(jī)M是RISC還是CISC？為什么？f1的機(jī)器指令代碼共占多少字節(jié)？要求給出計(jì)算過程。第20條指令cmp通過i減n-1實(shí)現(xiàn)對(duì)i和n-1的比較。執(zhí)行f1(0)過程中，當(dāng)i=0 時(shí)，cmp指令執(zhí)行后，進(jìn)/借位標(biāo)志CF的內(nèi)容是什么？要求給出計(jì)算過程。第

21、23條指令shl通過左移操作實(shí)現(xiàn)了 power*2運(yùn)算，在f2中能否也用shl指令0040107F C3ret(1)實(shí)現(xiàn)power*2 ?為什么？頁表索引（10位）頁內(nèi)偏移量（12位）頁目錄號(hào)（10位）請(qǐng)針對(duì)題43的函數(shù)f1和題44中的機(jī)器指令代碼，回答下列問題。（1）45.假定題44給出的計(jì)算機(jī) M采用二級(jí)分布虛擬存儲(chǔ)管理方式，邪氣地址格式如下:函數(shù)f1的機(jī)器指令代碼占多少頁？取第1條指令（push ebp）時(shí)，若在進(jìn)行地址變換的過程中需要訪問內(nèi)存中的頁 目錄和頁表，而會(huì)分別訪問它們各自的第幾個(gè)表項(xiàng)（編號(hào)從0開始）？M的I/O采用中斷控制方式。若進(jìn)程 P在調(diào)用f1之前通過scanf（）獲取n的值, 則在執(zhí)行scanf（）的過程中，進(jìn)程P的狀態(tài)會(huì)如何變化？CPU是否會(huì)進(jìn)入內(nèi)核態(tài)？46.某進(jìn)程中有3個(gè)并發(fā)執(zhí)行的線程 thread1、thread2和thread3，其偽代碼如下所示。/復(fù)數(shù)的結(jié)構(gòu)類型定義thread1thread3typ edef structcnum w;cnum w;float a;w= add(x,y);w.a =1;float b;w.b = 1; cnum;z =