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

1、2017 年考研計算機統(tǒng)考題408 真2017 年考研計算機統(tǒng)考 408 真題 一、 單項選擇題1. 下列函數(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)于棧的敘述中，錯誤的是 2 。I. 采用非遞歸方式重寫遞歸程序時必須使 用棧II. 函數(shù)調(diào)用時，系統(tǒng)要用棧保存必要的信 息III. 只要確定了入棧的次序， 即可確定出棧 次序IV. 棧是一種受限的線性表，允許在其兩端 進行操作A.

2、僅IB. 僅 I 、II 、IIIC. 僅 I 、III 、IVD. 僅 II 、III 、IV3. 適 用于壓縮存儲稀疏矩陣的兩種存儲結(jié)構(gòu)是3 。A. 三 元組表和十字鏈表B. 三 元組表和鄰接矩陣C. 十字鏈表和二叉鏈表D. 鄰接矩陣和十字鏈表4. 要使一棵非空二叉樹的先序序列與中序序列相同，其所有非葉結(jié)點須滿足的條件是 4。A. 只 有左子樹B. 只有右子樹C. 結(jié)點的度均為 1D. 結(jié)點的度均為 25. 已知一棵二叉樹的樹形如下圖所示， 其后序序 列為 e,a,c,b,d,g,f ，樹中與結(jié)點 a 同層的結(jié) 點是 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. 已知無向圖 G含有 16 條邊，其中度為 4 的頂 點個數(shù)為 3，度為 3 的頂點個數(shù)為 4，其他頂 點的度均小于 3。圖 G所含的頂點個數(shù)至少是7 。A. 10B.11C.13D.15不A.編譯器中的詞法分析B.關(guān)系數(shù)據(jù)庫系統(tǒng)中的索引C.網(wǎng)絡(luò)中的路由表快速查找D.操

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

5、 1.5GHz和 1.2GHz。在 M1和 M2上運行某基準程序 P，平均 CPI 分 別為 2 和 1，則程序 P在 M1和 M2上運行時間 的比值是 12 。A. 0.4B. 0.625C. 1.6D. 2.513. 某計算機主存按字節(jié)編址，由 4 個 64M*8 位的 DRAM芯片采用交叉編址方式構(gòu)成，并與 寬度為 32 位的存儲器總線相連，主存每次最 多讀寫 32 位數(shù)據(jù)。若 double 型變量 x 的主存地址為 804 001AH，則讀取 x 需要的存儲周期 是 13 。A. 1B. 2C. 3D. 414. 某 C語言程序段如下： for(i = 0; i = 9; i+) le

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

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

8、水線數(shù)據(jù)通路的敘述中， 錯 誤的是 19 。A. 包含生成控制信號的控制部件B. 包含算法邏輯運算部件（ ALU）C. 包含通用寄存器組和取指部件D. 由組合邏輯電路和時序邏輯電路組合而成20. 下列關(guān)于多總線結(jié)構(gòu)的敘述中，錯誤的是 20。A. 靠近 CPU的總線速度較快B. 存儲器總線可支持突發(fā)傳送方式C. 總線之間須通過橋接器相連D. PC I_Express*16 采用并行傳輸方式21. I/O 指令實現(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)的敘述中， 錯誤的是22。A. 在一條指令執(zhí)行結(jié)束時響應(yīng)中斷B. 中斷處理期間 CPU處于關(guān)中斷狀態(tài)C. 中斷請求的產(chǎn)生與當(dāng)前指令的執(zhí)行無關(guān)D. CPU通過采樣中斷請求信號檢測中斷請求23. 假設(shè) 4 個作業(yè)到達系統(tǒng)的時刻和運行時間 如下表所示。作業(yè)到達時間 t運行時間J103J213J312J431系統(tǒng)在 t=2 時開始作業(yè)調(diào)度。 若分別采用先 來先服務(wù)和短作業(yè)優(yōu)先調(diào)度算法， 則選中的 作業(yè)分別是 23A. J2、J3B. J1、J4C. J2、J4D. J1、J324. 執(zhí)行系統(tǒng)調(diào)用的過程包括如下主要操作：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. 某計算機按字節(jié)編址， 其動態(tài)分區(qū)內(nèi)存管理 采用最佳適應(yīng)算法， 每次分配和回收內(nèi)存后都 對空閑分區(qū)鏈重新排序。 當(dāng)前空閑分區(qū)信息如 下所示。分區(qū)起 始地址20K500K1000K200K分區(qū)大 小40KB80KB100KB200KB回收起始地址為 60K、大小為 140KB的分區(qū) 后，系統(tǒng)中空閑分區(qū)的數(shù)量、 空閑分區(qū)鏈第 一個分區(qū)的起始地址和大小分別是 25 。A. 3、20K、380KBB. 3、500K、80KBC.

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

12、 多道程序系統(tǒng)的優(yōu)先 是 28 。I. CPU 利用率高II. 系統(tǒng)開銷小III. 系統(tǒng)吞吐量大IV. I/O 設(shè)備利用率高A. 僅 I 、IIIB. 僅 I 、IVC. 僅 II 、IIID. 僅 I 、III 、IV29. 下列選項中，磁盤邏輯格式化程序所做的工作是 29I. 對磁盤進行分區(qū)II. 建立文件系統(tǒng)的根目錄III. 確定磁盤扇區(qū)校驗碼所占位數(shù)IV. 對保存空閑磁盤塊信息的數(shù)據(jù)結(jié)構(gòu)進行 初始化A. 僅 IIB. 僅 II 、IVC. 僅 III 、IVD. 僅 I 、II 、IV30. 某文件系統(tǒng)中， 針對每個文件， 用戶類別分 為 4 類：安全管理員、 文件主、文件主的伙伴、

13、其他用戶；訪問權(quán)限分為 5 種：完全控制、執(zhí) 行、修改、讀取、寫入。若文件控制塊中用二 進制位串表示文件權(quán)限， 為表示不同類別用戶 對一個文件的訪問權(quán)限， 則描述文件權(quán)限的位 數(shù)至少應(yīng)為 30。A. 5B. 9C. 12D. 2031. 若文件 f1 的硬鏈接為 f2 ，兩個進程分別打 開 f1 和 f2 ，獲得對應(yīng)的文件描述符為 fd1 和fd2 ，則下列敘述中，正確的是 31 。I.f1 和 f2 的讀寫指針位置保持相同II.f1 和 f2 共享同一個內(nèi)存索引結(jié)點III. fd1 和 fd2 分別指向各自的用戶打開文 件表中的一項A. 僅 IIIB. 僅 II 、IIIC. 僅 I 、II

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

15、道在無噪聲情況下的極限數(shù)據(jù)傳輸速 率不小于信噪比為 30dB 條件下的極限數(shù)據(jù)傳 輸速率，則信號狀態(tài)至少是34 。A. 4B. 8C. 16D. 3235. 在下圖所示的網(wǎng)絡(luò)中， 若主機 H 發(fā)送一個封 裝訪問 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報文的協(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 個規(guī)模相 同的子網(wǎng)，則每個子網(wǎng)可分配的最大 IP 地址 個數(shù)是 38。A. 254B. 256C. 510D. 51239. 若甲向乙發(fā)起了一個 TCP 連接，最大段長 MSS=K，BRTT=5m，s 乙開辟的接收緩存為 64KB， 則甲從連接建立蒽至發(fā)送窗口達到 32KB，需 經(jīng)過的時間至少是 38 。A. 25msB. 30msC. 160msD. 165ms40. 下列關(guān)于 FTP 協(xié)議的敘述中，錯誤的是40。A. 數(shù)據(jù)連接在每次數(shù)據(jù)傳輸完畢后就關(guān)閉B. 控制連接在整個會話期間保持打開狀態(tài)C. 服務(wù)器與客戶端的 TCP 20端口建立數(shù)據(jù)連接D. 客戶端與服務(wù)

18、器的 TCP 21 端口建立控制連接 二、 綜合應(yīng)用題41. 請設(shè)計一個算法， 將給定的表達式樹 （二叉 樹）轉(zhuǎn)換為等價的中綴表達式 （通過括號反映 操作符的計算次序）并輸出。例如，當(dāng)下列兩 棵表達式作為算法的輸入時：輸出的等價中綴表達式分別為(a+b)*(c+(-d) 和(a*b)+(-(-c-d)。二叉樹結(jié)點定義如下： Typedef struct node char data10; / 存儲操作數(shù) 或操作符Struct node * left, * right;BTree;要求：(1) 給出算法的基本設(shè)計思想。(2) 根據(jù)設(shè)計思想，采用 C或 C+語言描述算法， 關(guān)鍵之處給出注釋。42.

19、 使用 Prim (普里姆)算法求帶權(quán)連通圖的 最小(代價)生成樹(MST)。請回答下列問題。(1) 對下列圖 G，從頂點 A 開始求 G的 MST，依 次給出按算法選出的邊。(2) 圖 G的 MST是唯一的嗎？(3) 對任意的帶權(quán)連通圖， 滿足什么條件時， 其 MST是唯一的？43. 已知 f(n) = in=0 2i = 2n+1 - 1 =，計算 f(n) 的 C 語言函數(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 ，可得到計算 f(n) 的另一個函數(shù) f2 。假設(shè) unsigned 和 int 型數(shù)據(jù)都占 32 位，float 采用 IEEE 754 單 精度標準。請回答下列問題。(1) 當(dāng) n=0 時，f1 會出現(xiàn)死循環(huán)，為什么？若將 f1 中的變量 i 和 n 都定義為 int 型，則 f1 是否還會出現(xiàn)死循環(huán)？為什么？(2) f1(23) 和 f2(23) 的返回值是否相等？機器 數(shù)各是什么(用十六進制表示)？(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) 的機器數(shù)為 7F80 0000H，對應(yīng)的值 是什么？若使 f2(n) 的結(jié)果不溢出，則最大的 n 是什么？若使 f2(n) 的結(jié)果精確(無舍入) ， 則最大的 n 是多少？44. 在按字節(jié)編址的計算機 M 上，題 43 中 f1 的部分源程序(部分)與對應(yīng)的機器級代碼(包 括指令的虛擬地址)如下：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 其中，機器級代碼行包括行號、虛擬地址、 機器指令和匯編指令。請回答下列問題。(1) 計算機 M是 RISC還是 CISC？為什么？(2) f1 的機器指令代碼共占多少字節(jié)？要求給 出計算過程。(3) 第 20 條指令 cmp通過 i 減 n-1 實現(xiàn)對 i 和 n-1 的比較。執(zhí)行 f1(0) 過程中，當(dāng) i=0 時， cmp指令執(zhí)行后，

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