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

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

3、符 的 哈 夫 曼 編 碼 依 次 是0100,10,0000,0101,001,011,11,0001 ，則編碼序列 的譯碼結(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 的頂點(diǎn)個數(shù)為 3，度為 3 的頂點(diǎn)個數(shù)為 4，其他頂點(diǎn)的度均小于 3。圖 G 所含的頂點(diǎn)個數(shù)至少是 7 。A. 10B. 11C. 13D. 158. 下列二叉樹中，可能成為折半查找判定樹（不含外部結(jié)點(diǎn)）的是 8 。A.B.C.D.9. 下列應(yīng)用中，適合使用 B+樹的是 9 。

4、A. 編譯器中的詞法分析B. 關(guān)系數(shù)據(jù)庫系統(tǒng)中的索引C. 網(wǎng)絡(luò)中的路由表快速查找D. 操作系統(tǒng)的磁盤空閑塊管理10. 在內(nèi)部排序中，若選擇了歸并排序而沒有選擇插入排序，則可能的理由是 10。I.歸并排序的程序代碼更短II.歸并排序的占用空間更少III.歸并排序的運(yùn)行效率更高A. 僅 IIB. 僅 IIIC. 僅 I、IID. 僅 I、III11. 下列排序方法中，若將順序存儲更換為鏈?zhǔn)酱鎯?，則算法的時間效果會降低的是11 。I.插入排序II.選擇排序III.起泡排序IV.希爾排序V.堆排序A. 僅 I、IIB. 僅 II、IIIC. 僅 III、IVD. 僅 IV、V12. 假定計算機(jī) M1

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

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

7、107 條，每個地址字段為 6 位，則指令字長至少應(yīng)該是 16 。A. 24 位B. 26 位C. 28 位D. 32 位17. 下列關(guān)于超標(biāo)量流水線特性的敘述中，正確的是 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. M

8、M 用 RAM 和 ROM 實(shí)現(xiàn)， CS用 ROM 實(shí)現(xiàn)19. 下列關(guān)于指令流水線數(shù)據(jù)通路的敘述中，錯誤的是 19 。A. 包含生成控制信號的控制部件B. 包含算法邏輯運(yùn)算部件（ ALU）C. 包含通用寄存器組和取指部件D. 由組合邏輯電路和時序邏輯電路組合而成20. 下列關(guān)于多總線結(jié)構(gòu)的敘述中，錯誤的是 20 。A. 靠近 CPU的總線速度較快B. 存儲器總線可支持突發(fā)傳送方式C. 總線之間須通過橋接器相連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

9、/O 端口和 I/O 端口之間D. 通用寄存器和 I/O 端口之間22. 下列關(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è)到達(dá)系統(tǒng)的時刻和運(yùn)行時間如下表所示。作業(yè) 到達(dá)時間 t 運(yùn)行時間J1 0 3J2 1 3J3 1 2J4 3 1系統(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)用的

10、過程包括如下主要操作：1) 返回用戶態(tài)2) 執(zhí)行陷入（ trap）指令3) 傳遞系統(tǒng)調(diào)用參數(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ī)按字節(jié)編址，其動態(tài)分區(qū)內(nèi)存管理采用最佳適應(yīng)算法，每次分配和回收內(nèi)存后都對空閑分區(qū)鏈重新排序。當(dāng)前空閑分區(qū)信息如下所示。分區(qū)起始地址 20K 500K 1000K 200K分區(qū)大小 40KB 80KB 100KB 200KB回收起始地址為 60K、大小為 140KB 的分區(qū)后，系統(tǒng)中空閑分區(qū)的數(shù)量、空閑分區(qū)鏈第一個分區(qū)的起始地址和

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

12、素包括響應(yīng)時間、系統(tǒng)開銷和進(jìn)程數(shù)量等。28. 與單道程序系統(tǒng)相比，多道程序系統(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. 下列選項(xiàng)中，磁盤邏輯格式化程序所做的工作是 29 。I.對磁盤進(jìn)行分區(qū)II.建立文件系統(tǒng)的根目錄III.確定磁盤扇區(qū)校驗(yàn)碼所占位數(shù)IV.對保存空閑磁盤塊信息的數(shù)據(jù)結(jié)構(gòu)進(jìn)行初始化A. 僅 IIB. 僅 II、IVC. 僅 III、IVD. 僅 I、II、IV30. 某文件系統(tǒng)中，針對每個文件，用戶類別分為 4 類：安全管理員、文件

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

14、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ò)中，若主機(jī) 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-78-9b,00-1

16、2-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ò) /16 劃分

17、為 128 個規(guī)模相同的子網(wǎng)，則每個子網(wǎng)可分配的最大 IP地址個數(shù)是 38 。A. 254B. 256C. 510D. 51239. 若甲向乙發(fā)起了一個 TCP連接， 最大段長 MSS=KB，RTT=5ms，乙開辟的接收緩存為64KB，則甲從連接建立蒽至發(fā)送窗口達(dá)到 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ù)器的 TCP 21 端口建立

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

19、?。ù鷥r）生成樹（ MST）。請回答下列問題。(1) 對下列圖 G，從頂點(diǎn) A 開始求 G 的 MST，依次給出按算法選出的邊。(2) 圖 G 的 MST 是唯一的嗎？(3) 對任意的帶權(quán)連通圖，滿足什么條件時，其 MST是唯一的？43. 已知 ，計算 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 += power;6 7 return sum;8 將 f1 中的 int 都改為 float ，可得到計算

20、 f(n)的另一個函數(shù) f2。假設(shè)unsigned 和 int型數(shù)據(jù)都占 32 位， float 采用 IEEE 754單精度標(biāo)準(zhǔn)。請回答下列問題。(1) 當(dāng) n=0 時，f1 會出現(xiàn)死循環(huán)， 為什么？若將 f1 中的變量i 和 n 都定義為 int 型，則 f1 是否還會出現(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，為什么不相等？(4) f(31)=232-1，而 f1(31)的返回值卻為 -1，為什么？若使 f1(n)的返回

21、值與 f(n)相等，則最大的 n 是多少？(5) F2(127)的機(jī)器數(shù)為 7F80 0000H，對應(yīng)的值是什么？若使 f2(n) 的結(jié)果不溢出， 則最大的 n 是什么？若使 f2(n) 的結(jié)果精確（無舍入） ，則最大的 n 是多少？44. 在按字節(jié)編址的計算機(jī) M 上，題43 中 f1 的部分源程序（部分）與對應(yīng)的機(jī)器級代碼（包括指令的虛擬地址）如下：int f1(unsigned n)1 55 push ebp for(unsigned i = 0; i <=n-1; i+) . 20 E 39 4D F4 cmp dword ptrebp-0Ch, ecx power *= 2;

22、23 D1 E2 shl edx, l return sum; 35 F C3 ret其中，機(jī)器級代碼行包括行號、虛擬地址、機(jī)器指令和匯編指令。請回答下列問題。(1) 計算機(jī) M 是 RISC還是 CISC？為什么？(2) f1 的機(jī)器指令代碼共占多少字節(jié)？要求給出計算過程。(3) 第 20 條指令 cmp 通過 i 減 n-1實(shí)現(xiàn)對 i 和 n-1 的比較。 執(zhí)行 f1(0)過程中， 當(dāng) i=0時， cmp 指令執(zhí)行后，進(jìn) / 借位標(biāo)志CF的內(nèi)容是什么？要求給出計算過程。(4) 第 23 條指令 shl 通過左移操作實(shí)現(xiàn)了 power*2 運(yùn)算，在 f2 中能否也用 shl 指令實(shí)現(xiàn)powe

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