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

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

2、僅IB. 僅 I 、II 、IIIC. 僅 I 、III 、IVD. 僅 II 、III 、IV3. 適 用于壓縮存儲(chǔ)稀疏矩陣的兩種存儲(chǔ)結(jié)構(gòu)是3 。A. 三 元組表和十字鏈表B. 三 元組表和鄰接矩陣C. 十字鏈表和二叉鏈表D. 鄰接矩陣和十字鏈表4. 要使一棵非空二叉樹(shù)的先序序列與中序序列相同，其所有非葉結(jié)點(diǎn)須滿足的條件是 4。A. 只 有左子樹(shù)B. 只有右子樹(shù)C. 結(jié)點(diǎn)的度均為 1D. 結(jié)點(diǎn)的度均為 25. 已知一棵二叉樹(shù)的樹(shù)形如下圖所示， 其后序序 列為 e,a,c,b,d,g,f ，樹(shù)中與結(jié)點(diǎn) a 同層的結(jié) 點(diǎn)是 5 。A. cB. dC. fD. g6. 已知字符集 a,b,c,d,

3、e,f,g,h ，若各字符的 哈夫曼編碼依次是 0100,10,0000,0101,001,011,11,0001 ，則編 碼序列 0100011001001011110101的譯碼結(jié)果 是 6 。A. a c g a b f hB. a d b a g b bC. a f b e a g dD. a f e e f g d7. 已知無(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.15不A.編譯器中的詞法分析B.關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)中的索引C.網(wǎng)絡(luò)中的路由表快速查找D.操

4、作系統(tǒng)的磁盤(pán)空閑塊管理10. 在內(nèi)部排序中， 若選擇了歸并排序而沒(méi)有選 擇插入排序，則可能的理由是 10 。I. 歸并排序的程序代碼更短II. 歸并排序的占用空間更少III. 歸并排序的運(yùn)行效率更高A. 僅 IIB. 僅 IIIC. 僅 I 、IID. 僅 I 、III11. 下列排序方法中， 若將順序存儲(chǔ)更換為鏈?zhǔn)酱鎯?chǔ)，則算法的時(shí)間效果會(huì)降低的是11。I. 插入排序II. 選擇排序III. 起泡排序IV. 希爾排序V. 堆排序A. 僅 I 、IIB. 僅 II 、IIIC. 僅 III 、IVD. 僅 IV 、V12. 假定計(jì)算機(jī) M1和 M2具有相同的指令集體系結(jié)構(gòu)（ ISA），主頻分別為

5、 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.513. 某計(jì)算機(jī)主存按字節(jié)編址，由 4 個(gè) 64M*8 位的 DRAM芯片采用交叉編址方式構(gòu)成，并與 寬度為 32 位的存儲(chǔ)器總線相連，主存每次最 多讀寫(xiě) 32 位數(shù)據(jù)。若 double 型變量 x 的主存地址為 804 001AH，則讀取 x 需要的存儲(chǔ)周期 是 13 。A. 1B. 2C. 3D. 414. 某 C語(yǔ)言程序段如下： for(i = 0; i = 9; i+) le

6、mp = 1;for(j 0; j = I; j+) temp *= aj;sum += temp;下列關(guān)于數(shù)組 a 的訪問(wèn)局部性的描述中， 正 確的是 14。A. 時(shí)間局部性和空間局部性皆有B. 無(wú)時(shí)間局部性，有空間局部性C. 有時(shí)間局部性，無(wú)空間局部性D. 時(shí)間局部性和空間局部性皆無(wú)15. 下列尋址方式中， 最適合按下標(biāo)順序訪問(wèn)一 維數(shù)組元素的是 15 。A. 相對(duì)尋址B. 寄存器尋址C. 直接尋址D. 變址尋址16. 某計(jì)算機(jī)按字節(jié)編址， 指令字長(zhǎng)固定且只有 兩種指令格式，其中三地址指令 29 條，二地 址指令 107 條，每個(gè)地址字段為 6 位，則指令 字長(zhǎng)至少應(yīng)該是 16。A. 24

7、 位B. 26 位C. 28位D. 32位17. 下列關(guān)于超標(biāo)量流水線特性的敘述中， 正確 的是 16 。I. 能縮短流水線功能段的處理時(shí)間II. 能在一個(gè)時(shí)鐘周期內(nèi)同時(shí)發(fā)射多條指令I(lǐng)II. 能結(jié)合動(dòng)態(tài)調(diào)度技術(shù)提高指令執(zhí)行并 行性A. 僅 IIB. 僅 I 、IIIC. 僅 II 、IIID. I 、II 和 III18. 下列關(guān)于主存儲(chǔ)器 （MM）和控制存儲(chǔ)器（CS） 的敘述中，錯(cuò)誤的是18 。A. MM在 CPU外， CS在 CPU內(nèi)B. MM按地址訪問(wèn)， CS按內(nèi)存訪問(wèn)C. MM存儲(chǔ)指令和數(shù)據(jù)， CS存儲(chǔ)微指令D. MM用 RAM和 ROM實(shí)現(xiàn)， CS用 ROM實(shí)現(xiàn)19. 下列關(guān)于指令流

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

9、關(guān)于多重中斷系統(tǒng)的敘述中， 錯(cuò)誤的是22。A. 在一條指令執(zhí)行結(jié)束時(shí)響應(yīng)中斷B. 中斷處理期間 CPU處于關(guān)中斷狀態(tài)C. 中斷請(qǐng)求的產(chǎn)生與當(dāng)前指令的執(zhí)行無(wú)關(guān)D. CPU通過(guò)采樣中斷請(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í)開(kāi)始作業(yè)調(diào)度。 若分別采用先 來(lái)先服務(wù)和短作業(yè)優(yōu)先調(diào)度算法， 則選中的 作業(yè)分別是 23A. J2、J3B. J1、J4C. J2、J4D. J1、J324. 執(zhí)行系統(tǒng)調(diào)用的過(guò)程包括如下主要操作：1) 返回用戶態(tài)2) 執(zhí)行陷入( trap )指令3) 傳遞系統(tǒng)調(diào)用

10、參數(shù)4) 執(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)25. 某計(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 。A. 3、20K、380KBB. 3、500K、80KBC.

11、4、 20K、180KBD. 4、 500K、80KB26. 某文件系統(tǒng)的簇和磁盤(pán)扇區(qū)大小分別為1KB和 512B。若一個(gè)文件的大小為 1026B，則 系統(tǒng)分配給該文件的磁盤(pán)空間大小是26 。A. 1026BB. 1536BC. 1538BD. 2048B27. 下列有關(guān)基于時(shí)間片的進(jìn)程調(diào)度的敘述中， 錯(cuò)誤的是 27 。A. 時(shí)間片越短，進(jìn)程切換的次數(shù)越多， 系統(tǒng)開(kāi)銷 也越大B. 當(dāng)前進(jìn)程的時(shí)間片用完后， 該進(jìn)程狀態(tài)由執(zhí)行 態(tài)變?yōu)樽枞麘B(tài)C. 時(shí)鐘中斷發(fā)生后，系統(tǒng)會(huì)修改當(dāng)前進(jìn)程在時(shí)間 片內(nèi)的剩余時(shí)間D. 影響時(shí)間片大小的主要因素包括響應(yīng)時(shí)間、 系 統(tǒng)開(kāi)銷和進(jìn)程數(shù)量等。28. 與單道程序系統(tǒng)相比，

12、 多道程序系統(tǒng)的優(yōu)先 是 28 。I. CPU 利用率高II. 系統(tǒng)開(kāi)銷小III. 系統(tǒng)吞吐量大IV. I/O 設(shè)備利用率高A. 僅 I 、IIIB. 僅 I 、IVC. 僅 II 、IIID. 僅 I 、III 、IV29. 下列選項(xiàng)中，磁盤(pán)邏輯格式化程序所做的工作是 29I. 對(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)行 初始化A. 僅 IIB. 僅 II 、IVC. 僅 III 、IVD. 僅 I 、II 、IV30. 某文件系統(tǒng)中， 針對(duì)每個(gè)文件， 用戶類別分 為 4 類：安全管理員、 文件主、文件主的伙伴、

13、其他用戶；訪問(wèn)權(quán)限分為 5 種：完全控制、執(zhí) 行、修改、讀取、寫(xiě)入。若文件控制塊中用二 進(jìn)制位串表示文件權(quán)限， 為表示不同類別用戶 對(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 分別指向各自的用戶打開(kāi)文 件表中的一項(xiàng)A. 僅 IIIB. 僅 II 、IIIC. 僅 I 、II

14、D. I 、II 和 III32. 系統(tǒng)將數(shù)據(jù)從磁盤(pán)讀到內(nèi)存的過(guò)程包括以 下操作：1) DMA控制器發(fā)出中斷請(qǐng)求2) 初始化 DMA控制器并啟動(dòng)磁盤(pán)3) 從磁盤(pán)傳輸一塊數(shù)據(jù)到內(nèi)存緩沖區(qū)4) 執(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)33. 假設(shè) OSI 參考模型的應(yīng)用層欲發(fā)送 400B的 數(shù)據(jù)(無(wú)拆分)，除物理層和應(yīng)用層之處，其他各層在封裝 PDU時(shí)均引入 20B 的額外開(kāi)銷， 則應(yīng)用層數(shù)據(jù)傳輸效率約為33 。A. 80%B. 83%C. 87%D. 91%34. 若信

15、道在無(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 分組的 IEEE 802.11 數(shù)據(jù) 幀 F，則幀 F 的地址 1 、地址 2 和地址 3 分別 是 35 。A. 00-12-34-56-78-9a,00-12-34-56-78-9b,00-12-34-56-78-9cB. 00-12-34-56-78-9b,00-12-34-56-78-9a,00-12-34-56-78-9cC. 00-12-34-56-7

16、8-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. 下列 IP 地址中，只能作為 IP 分組源 IP 地 址但不能作為目的 IP 地址是 36 。A. B. C. D. 5537. 直接封裝 RIP，OSPF，BGP報(bào)文的協(xié)議分別是37 。A. TCP、UDP、IPB. TCP、IP、UDPC. UDP、TCP、IPD. UDP、IP、TCP38. 若將網(wǎng)絡(luò) 21.3.

17、0.0/16 劃分為 128 個(gè)規(guī)模相 同的子網(wǎng)，則每個(gè)子網(wǎng)可分配的最大 IP 地址 個(gè)數(shù)是 38。A. 254B. 256C. 510D. 51239. 若甲向乙發(fā)起了一個(gè) TCP 連接，最大段長(zhǎng) MSS=K，BRTT=5m，s 乙開(kāi)辟的接收緩存為 64KB， 則甲從連接建立蒽至發(fā)送窗口達(dá)到 32KB，需 經(jīng)過(guò)的時(shí)間至少是 38 。A. 25msB. 30msC. 160msD. 165ms40. 下列關(guān)于 FTP 協(xié)議的敘述中，錯(cuò)誤的是40。A. 數(shù)據(jù)連接在每次數(shù)據(jù)傳輸完畢后就關(guān)閉B. 控制連接在整個(gè)會(huì)話期間保持打開(kāi)狀態(tài)C. 服務(wù)器與客戶端的 TCP 20端口建立數(shù)據(jù)連接D. 客戶端與服務(wù)

18、器的 TCP 21 端口建立控制連接 二、 綜合應(yīng)用題41. 請(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)定義如下： Typedef struct node char data10; / 存儲(chǔ)操作數(shù) 或操作符Struct node * left, * right;BTree;要求：(1) 給出算法的基本設(shè)計(jì)思想。(2) 根據(jù)設(shè)計(jì)思想，采用 C或 C+語(yǔ)言描述算法， 關(guān)鍵之處給出注釋。42.

19、 使用 Prim (普里姆)算法求帶權(quán)連通圖的 最小(代價(jià))生成樹(shù)(MST)。請(qǐng)回答下列問(wèn)題。(1) 對(duì)下列圖 G，從頂點(diǎn) A 開(kāi)始求 G的 MST，依 次給出按算法選出的邊。(2) 圖 G的 MST是唯一的嗎？(3) 對(duì)任意的帶權(quán)連通圖， 滿足什么條件時(shí)， 其 MST是唯一的？43. 已知 f(n) = in=0 2i = 2n+1 - 1 =，計(jì)算 f(n) 的 C 語(yǔ)言函數(shù) f1 如下：1 int f1(unsigned n)2 int sum = 1, power = 1;3 for(unsigned i =0; i = n-1; i+)4 power *= 2;5 sum += po

20、wer;67 return sum;8將 f1 中的 int 都改為 float ，可得到計(jì)算 f(n) 的另一個(gè)函數(shù) f2 。假設(shè) unsigned 和 int 型數(shù)據(jù)都占 32 位，float 采用 IEEE 754 單 精度標(biāo)準(zhǔn)。請(qǐng)回答下列問(wèn)題。(1) 當(dāng) n=0 時(shí)，f1 會(huì)出現(xiàn)死循環(huán)，為什么？若將 f1 中的變量 i 和 n 都定義為 int 型，則 f1 是否還會(huì)出現(xiàn)死循環(huán)？為什么？(2) f1(23) 和 f2(23) 的返回值是否相等？機(jī)器 數(shù)各是什么(用十六進(jìn)制表示)？(3) F1(24) 和 f2(24) 的返回值分別為 33 554 431 和 33 554 432.0

21、，為什么不相等？(4) f(31)=2 32-1 ，而 f1(31) 的返回值卻為 -1 ， 為什么？若使 f1(n) 的返回值與 f(n) 相等，則 最大的 n 是多少？(5) F2(127) 的機(jī)器數(shù)為 7F80 0000H，對(duì)應(yīng)的值 是什么？若使 f2(n) 的結(jié)果不溢出，則最大的 n 是什么？若使 f2(n) 的結(jié)果精確(無(wú)舍入) ， 則最大的 n 是多少？44. 在按字節(jié)編址的計(jì)算機(jī) M 上，題 43 中 f1 的部分源程序(部分)與對(duì)應(yīng)的機(jī)器級(jí)代碼(包 括指令的虛擬地址)如下：int f1(unsigned n)1 00401020 55push ebpfor(unsigned i

22、 = 0; i =n-1; i+)20 0040105E3 9 4D F4cmpdwordptrebp-0Ch, ecx power *= 2;23 00401066 D1 E2shl edx, lreturn sum;35 0040107FC 3 ret 其中，機(jī)器級(jí)代碼行包括行號(hào)、虛擬地址、 機(jī)器指令和匯編指令。請(qǐng)回答下列問(wèn)題。(1) 計(jì)算機(jī) M是 RISC還是 CISC？為什么？(2) f1 的機(jī)器指令代碼共占多少字節(jié)？要求給 出計(jì)算過(guò)程。(3) 第 20 條指令 cmp通過(guò) i 減 n-1 實(shí)現(xiàn)對(duì) i 和 n-1 的比較。執(zhí)行 f1(0) 過(guò)程中，當(dāng) i=0 時(shí)， cmp指令執(zhí)行后，

23、進(jìn) / 借位標(biāo)志 CF的內(nèi)容是什 么？要求給出計(jì)算過(guò)程。(4) 第 23 條指令 shl 通過(guò)左移操作實(shí)現(xiàn)了 power*2 運(yùn)算，在 f2 中能否也用 shl 指令實(shí) 現(xiàn) power*2 ？為什么？45. 假定題 44 給出的計(jì)算機(jī) M采用二級(jí)分布虛 擬存儲(chǔ)管理方式，邪氣地址格式如下：頁(yè)目錄號(hào)( 10頁(yè)表索引( 10頁(yè)內(nèi)偏移量位)位)(12位)請(qǐng)針對(duì)題 43 的函數(shù) f1 和題 44 中的機(jī)器指 令代碼，回答下列問(wèn)題。(1) 函數(shù) f1 的機(jī)器指令代碼占多少頁(yè)？(2) 取第 1 條指令 (push ebp) 時(shí)，若在進(jìn)行地 址變換的過(guò)程中需要訪問(wèn)內(nèi)存中的頁(yè)目錄和 頁(yè)表，而會(huì)分別訪問(wèn)它們各自的第幾個(gè)表項(xiàng) (編號(hào)從 0 開(kāi)始)？(3) 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 和 thread3 ，其偽代碼如下所示/ 復(fù) 數(shù) 的 結(jié)thread1thread3構(gòu)類型定義typedefcnum w;cnum w;structw=w.a =1;add