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

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

2、結(jié)構(gòu)是3。三元組表和十字鏈表三元組表和鄰接矩陣十字鏈表和二叉鏈表鄰接矩陣和十字鏈表要使一棵非空二叉樹的先序序列與中序序列相同，其所有非葉結(jié)點須滿足的條件是4。只有左子樹只有右子樹結(jié)點的度均為1結(jié)點的度均為2已知一棵二叉樹的樹形如下圖所示， 其后序序列為的結(jié)點是5。e,a,c,b,d,g,，f樹中與結(jié)點a 同層-WORD 格式 - 可編輯 -cd-WORD 格式 - 可編輯 -fg已 知 字 符 集 a,b,c,d,e,f,g,h ， 若 各 字 符 的 哈 夫 曼 編 碼 依 次是0100,10,0000,0101,001,011,11,00，01則編碼序列010001100100101111

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

4、序，則可能的理由是10。僅 II僅 III僅 I、 II僅 I、 III下列排序方法中，若將順序存儲更換為鏈式存儲，則算法的時間效果會降低的是11。插入排序選擇排序起泡排序希爾排序V.堆排序僅 I、 II僅 II 、 III僅 III 、 IV僅 IV 、 V假定計算機M1 和M2具有相同的指令集體系結(jié)構(gòu)（ISA），主頻分別為1.5GHz 和1.2GHz。在M1和 M2上運行某基準程序P，平均CPI 分別為2 和 1，則程序P 在M1 和M2A.0.40.62上運行時間的比值是12。B.5C.1.6D.2.5某計算機主存按字節(jié)編址，由 4 個 64M*8位的 DRAM芯片采用交叉編址方式構(gòu)成，

5、并與寬度為32 位的存儲器總線相連，主存每次最多讀寫 32位數(shù)據(jù)。若double型變量 x 的主存地址為123804 001AH，則讀取x 需要的存儲周期是13。-WORD 格式 - 可編輯 -4某 C 語言程序段如下： for(i = 0; i= 9; i+)lemp = 1;for(j 0; j = I; j+) temp *= aj; sum += temp;-WORD 格式 - 可編輯 -下列關(guān)于數(shù)組a 的訪問局部性的描述14中，正確的是。時間局部性和空間局部性皆有無時間局部性，有空間局部性有時間局部性，無空間局部性時間局部性和空間局部性皆無下列尋址方式中，最適合按下標順序訪問一維15

6、數(shù)組元素的是。相對尋址寄存器尋址直接尋址變址尋址某計算機按字節(jié)編址，指令字長固定且只有兩種指令格式，其中三地址指令29 條，二地址指令107 條，每個地址字段為6 位，則指令字長至少應(yīng)該是16。24 位26 位28 位32 位下列關(guān)于超標量流水線特性的敘述16中，正確的是。僅 II僅 I、 III僅 II 、 IIII、 II和 III下列關(guān)于主存儲器（MM ）和控制存儲器（CS）的敘18述中，錯誤的是。MM 在 CPU 外， CS在 CPU 內(nèi)MM 按地址訪問，CS按內(nèi)存訪問MM 存儲指令和數(shù)據(jù)，CS 存儲微指令MM 用 RAM 和 ROM 實現(xiàn)， CS 用 ROM 實現(xiàn)下列關(guān)于指令流水線數(shù)

7、據(jù)通路的敘述19中，錯誤的是。包含生成控制信號的控制部件包含算法邏輯運算部件（ALU ）包含通用寄存器組和取指部件由組合邏輯電路和時序邏輯電路組合而成下列關(guān)于多總線結(jié)構(gòu)的敘述中，20錯誤的是?？拷?CPU 的總線速度較快存儲器總線可支持突發(fā)傳送方式總線之間須通過橋接器相連PC I_Express*16采用并行傳輸方式-WORD 格式 - 可編輯 -I/O指令實現(xiàn)的數(shù)據(jù)傳送通常21發(fā)生在。I/O設(shè)備和 I/O端口之間通用寄存器和I/O設(shè)備之間I/O端口和 I/O端口之間-WORD 格式 - 可編輯 -通用寄存器和I/O端口之間下列關(guān)于多重中斷系統(tǒng)的敘述22中，錯誤的是。在一條指令執(zhí)行結(jié)束時響應(yīng)中

8、斷中斷處理期間CPU 處于關(guān)中斷狀態(tài)中斷請求的產(chǎn)生與當前指令的執(zhí)行無關(guān)CPU 通過采樣中斷請求信號檢測中斷請求假設(shè) 4 個作業(yè)到達系統(tǒng)的時刻和運行時間如下表所示。作業(yè)到達時間t運行時間J103J213J312J431系統(tǒng)在 t=2 時開始作業(yè)調(diào)度。若分別采用先來先服務(wù)和短作業(yè)優(yōu)先調(diào)度算法，則選中的作業(yè)分別是 23J2 、 J3J1 、 J4J2 、 J4J1 、 J3執(zhí)行系統(tǒng)調(diào)用的過程包括如下主要操作：返回用戶態(tài)執(zhí)行陷入（ trap ）指令傳遞系統(tǒng)調(diào)用參數(shù)執(zhí)行相應(yīng)的服務(wù)程序是。A.2)3)1)4)B.2)3)3)1)C.3)2)4)1)D.3)4)2)1)正確的執(zhí)行順序24某計算機按字節(jié)編址，

9、其動態(tài)分區(qū)內(nèi)存管理采用最佳適應(yīng)算法，每次分配和回收內(nèi)存后都對空閑分區(qū)鏈重新排序。當前空閑分區(qū)信息如下所示。分區(qū)起始地址20K500K1000K200K分區(qū)大小40KB80KB100KB200KB回收起始地址為60K、大小為140KB 的分區(qū)后，系統(tǒng)中空閑分區(qū)的數(shù)量、空閑分區(qū)鏈第一個分區(qū)的起始地址和大小分別是3、 20K、380KB3、 500K、80KB4、 20K、180KB25 。-WORD 格式 - 可編輯 -4、 500K、80KB某文件系統(tǒng)的簇和磁盤扇區(qū)大小分別為則系統(tǒng)分配給該文件的磁盤空1KB 和 512B。若一個文件的大小為1026B，A.1026BB.1536BC.1538BD

10、.2048B間大小是26。-WORD 格式 - 可編輯 -下列有關(guān)基于時間片的進程調(diào)度的敘述27中，錯誤的是。時間片越短，進程切換的次數(shù)越多，系統(tǒng)開銷也越大當前進程的時間片用完后，該進程狀態(tài)由執(zhí)行態(tài)變?yōu)樽枞麘B(tài)時鐘中斷發(fā)生后，系統(tǒng)會修改當前進程在時間片內(nèi)的剩余時間影響時間片大小的主要因素包括響應(yīng)時間、系統(tǒng)開銷和進程數(shù)量等。與單道程序系統(tǒng)相比，多道程序系統(tǒng)的優(yōu)先是CPU 利用率高系統(tǒng)開銷小系統(tǒng)吞吐量大IV.I/O設(shè)備利用率高僅 I、 III僅 I、 IV僅 II 、 III僅 I、 III 、 IV下列選項中，磁盤邏輯格式化程序所做的工作是對磁盤進行分區(qū)建立文件系統(tǒng)的根目錄確定磁盤扇區(qū)校驗碼所占位

11、數(shù)。對保存空閑磁盤塊信息的數(shù)據(jù)結(jié)構(gòu)進行初始化僅 II僅 II 、 IV僅 III 、 IV僅 I、 II 、 IV30.某文件系統(tǒng)中，針對每個文件，用戶類別分為4 類：安全管理員、文件主、文件主的伙伴、其他用戶；訪問權(quán)限分為5 種：完全控制、執(zhí)行、修改、讀取、寫入。若文件控制塊中用二進制位串表示文件權(quán)限，權(quán)限，則描述文件權(quán)限的位為表示不同類別用戶對一個文件的訪問數(shù)至少應(yīng)為30。59122031.若文件 f1 的硬鏈接為f2，兩個進程分別打開f1 和 f2，獲得對應(yīng)的文件描述符為fd1和 fd2 ，則下列敘述中，正確的是31 。f1 和 f2 的讀寫指針位置保持相同f1和 f2 共享同一個內(nèi)存索

12、引結(jié)點fd1和 fd2 分別指向各自的用戶打開文件表中的一項僅 III僅 II 、 III僅 I、 II-WORD 格式 - 可編輯 -I、 II和 III系統(tǒng)將數(shù)據(jù)從磁盤讀到內(nèi)存的過程包括以下操作：DMA控制器發(fā)出中斷請求初始化 DMA控制器并啟動磁盤從磁盤傳輸一塊數(shù)據(jù)到內(nèi)存緩沖區(qū)-WORD 格式 - 可編輯 -執(zhí)行“ DMA結(jié)束”中斷服務(wù)程序是。A.3)1)2)4)B.2)3)1)4)C.2)1)3)4)D.1)2)4)3)正確的執(zhí)行順序32假設(shè) OSI 參考模型的應(yīng)用層欲發(fā)送400B 的數(shù)據(jù)（無拆分），除物理層和應(yīng)用層之處，其他各層在封裝PDU 時均引入 20B 的額外開銷，則應(yīng)用層數(shù)據(jù)

13、傳輸效率約為33。A.80%B.83%C.87%D.91%不小于信噪比為態(tài)至少是34限數(shù)。A.4B.8C.16D.32若信道在無噪聲情況下的極限數(shù)據(jù)傳輸速率據(jù)傳輸速率，則信號狀30dB 條件下的極35.在下圖所示的網(wǎng)絡(luò)中，若主機H 發(fā)送一個封裝訪問InternetIP 分組的IEEE802.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

14、-56-78-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.-WORD 格式 - 可編輯 -B.C.37. 直接封裝RIP， OSPF， BGP 報文的協(xié)議分別是37。A.TCP、 UDP 、 IPB.TCP、 IP、 UDPC.UDP、 TCP、 IPD.UDP、 IP、 TCP38. 若將網(wǎng)絡(luò)/16 劃分為128 個規(guī)D.55模相同的子網(wǎng)，則每個子網(wǎng)可分配的最

15、大IP地址個數(shù)是38。A.254-WORD 格式 - 可編輯 -B.256C.510D.512若甲向乙發(fā)起了一個TCP 連接，最大段長MSS=KB，RTT=5ms ，乙開辟的接收緩存為64KB，則甲從連接建立蒽至發(fā)送窗口達到32KB，需經(jīng)過的時間至少是38。25ms30ms160ms165ms下列關(guān)于FTP 協(xié)議的敘述中，錯誤的是40。數(shù)據(jù)連接在每次數(shù)據(jù)傳輸完畢后就關(guān)閉控制連接在整個會話期間保持打開狀態(tài)服務(wù)器與客戶端的TCP 20 端口建立數(shù)據(jù)連接客戶端與服務(wù)器的TCP 21 端口建立控制連接二、綜合應(yīng)用題請設(shè)計一個算法，將給定的表達式樹（二叉樹）轉(zhuǎn)換為等價的中綴表達式（通過括號反映操作符的計

16、算次序）并輸出。例如，當下列兩棵表達式作為算法的輸入時：輸出的等價中綴表達式分別為(a+b)*(c+(-d) 和 (a*b)+(-(-c-d) 。二叉樹結(jié)點定義如下：Typedef struct nodechar data10;/存儲操作數(shù)或操作符Struct node * left, * right;BTree;要求：給出算法的基本設(shè)計思想。根據(jù)設(shè)計思想，采用C 或 C+ 語言描述算法，關(guān)鍵之處給出注釋。使用Prim （普里姆）算法求帶權(quán)連通圖的最?。ù鷥r）生成樹（MST）。請回答下列問題。對下列圖G ，從頂點A開始求G的 MST ，依次給出按算法選出的邊。圖 G 的 MST 是唯一的嗎？-

17、WORD 格式 - 可編輯 -對任意的帶權(quán)連通圖，滿足什么條件時，其MST 是唯一的？43. 已知1，計算f(n)的 C 語言函數(shù)int f1(unsigned n)f1 如下：2int sum = 1, power = 1;3for(unsigned i =0; i = n-1; i+)4power *= 2;5sum += power;67return sum;8將 f1 中的int 都改為float ，可得到計算f(n)的另一個函數(shù) f2。假設(shè)unsigned和 int型數(shù)據(jù)都占32 位， float 采用 IEEE 754 單精度標準。請回答下列問題。當 n=0 時， f1 會出現(xiàn)死循

18、環(huán)，為什么？若將f1 中的變量 i 和 n都定義為 int 型，則 f1 是否還會出現(xiàn)死循環(huán)？為什么？f1(23)和 f2(23) 的返回值是否相等？機器數(shù)各是什么（用十六進制表示）？(3) F1(24)和 f2(24) 的返回值分別為33 554 431和 33 554 432.0，為什么不相等？(4) f(31)=232-1，而 f1(31) 的返回值卻為-1，為什么？若使f1(n) 的返回值與 f(n)相等，則最大的n 是多少？(5)F2(127)的機器數(shù)為7F80 0000H，對應(yīng)的值是什么？若使f2(n) 的結(jié)果不溢出，則最大的 n 是什么？若使f2(n) 的結(jié)果精確（無舍入） ，則

19、最大的n 是多少？在按字節(jié)編址的計算機M 上，題 43 中 f1 的部分源程序（部分） 與對應(yīng)的機器級代碼（包括指令的虛擬地址）如下：int f1(unsigned n)10040102055push ebp?for(unsigned i = 0; i =n-1; i+)?.?cmp dword ptrebp-200040105E39 4D F40Ch, ecx?power *= 2;?2300401066D1 E2shl edx, l?-WORD 格式 - 可編輯 -return sum;?350040107FC3ret其中，機器級代碼行包括行號、虛擬地址、機器指令和匯編指令。請回答下列問題

20、。計算機 M 是 RISC 還是 CISC？為什么？f1 的機器指令代碼共占多少字節(jié)？要求給出計算過程。第 20 條指令 cmp 通過 i 減 n-1 實現(xiàn)對 i 和 n-1 的比較。 執(zhí)行f1(0)過程中， 當 i=0 時， cmp 指令執(zhí)行后，進/借位標志 CF 的內(nèi)容是什么？要求給出計算過程。-WORD 格式 - 可編輯 -第 23 條指令 shl 通過左移操作實現(xiàn)了power*2 運算，在 f2 中能否也用 shl 指令實現(xiàn) power*2 ？為什么？假定題44 給出的計算機M 采用二級分布虛擬存儲管理方式，邪氣地址格式如下：頁目錄號（10位）頁表索引（10 位）頁內(nèi)偏移量（12 位）

21、請針對題43 的函數(shù)f1 和題44 中的機器指令代碼，回答下列問題。函數(shù) f1 的機器指令代碼占多少頁？取第 1 條指令(push ebp)時，若在進行地址變換的過程中需要訪問內(nèi)存中的頁目錄和頁表，而會分別訪問它們各自的第幾個表項（編號從0開始）？M 的 I/O采用中斷控制方式。若進程P 在調(diào)用 f1 之前通過scanf()獲取 n 的值，則在執(zhí)行scanf()的過程中，進程P 的狀態(tài)會如何變化？ CPU 是否會進入內(nèi)核態(tài)？某進程中有3 個并發(fā)執(zhí)行的線程thread1、thread2/復(fù)數(shù)的結(jié)構(gòu)類型定義thread1 typedef structcnum w;float a;w= add(x,y);和 thread3 ，其偽代碼如下所示。thread3cnum w;w.a =1;float b;? cnum;w.b = 1;z = add(z,w);cnum x, y, z;/