1、2017 年 考 研 計 算 機 統 考 408 真 題一、單項選擇題1 .以下函數的時間復雜度是1 Qint func(int n)A. int i = 0; sum = 0;while( sum < n) sum += +i;return i;B. O(logn)C. O(n1/2)D. O(n)E. O(nlogn)2 .以下關于棧的表達中,錯誤的選項是2 qI .采用非遞歸方式重寫遞歸程序時必須使用棧II .函數調用時,系統要用棧保存必要的信息III .只要確定了入棧的次序,即可確定出棧次序IV棧是一種受限的線性表,允許在其兩端進行操作A.僅IIV 僅 I、II、IIIC.僅 I

2、、III、IVD.僅 II、III、IV3 .適用于壓縮存儲稀疏矩陣白兩種存儲結構是3.A.三元組表和十字鏈表B.三元組表和鄰接矩陣C.十字鏈表和二叉鏈表D.鄰接矩陣和十字鏈表4 .要使一棵非空二叉樹的先序序列與中序序列相同,其所有非葉結點須滿足的條件是4.A.只有左子樹8. 只有右子樹C.結點的度均為1D.結點的度均為25 .一棵二叉樹的樹形如以下圖所示,其后序序列為e,a,c,b,d,g,f,樹中與結點a同層的結點是5.A. cB. dC. fD. g6 .字符集a,b,c,d,e,f,g,h,假設各字符的哈夫曼編碼依次是0100,10,0000,0101,001,011,11,0001

3、,那么編碼序列的譯碼結果是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的頂點個數為3,度為3的頂點個數為4,其他頂點的度均小于 3.圖G所含的頂點個數至少是7.A.B.C.D.10111315A.B.8.卜列二叉樹中,可能成為折半查找判定樹不含外部結點的是9 .以下應用中,適合使用B+樹的是9.A.編譯器中的詞法分析B.關系數據庫系統中的索引C.網絡中的路由表快速查找D.操作系統的磁盤空閑塊治理1010 .在內部排序中,假設選擇了歸并排序而沒有選擇插入排序,那么可能的理由

4、是I.歸并排序的程序代碼更短11 .歸并排序的占用空間更少111 .歸并排序的運行效率更高A.僅 II112 IIIC.僅 I、IID.僅 I、III11.以下排序方法中,假設將順序存儲更換為鏈式存儲,那么算法的時間效果會降低的是_11.I .插入排序II .選擇排序III .起泡排序IV希爾排序V堆排序A.僅 I、IIIV 僅 II、IIIC.僅 III、IVD.僅 IV、V12 .假定計算機 M1和M2具有相同的指令集體系結構(ISA),主頻分別為1.5GHz和 1.2GHz.在M1和M2上運行某基準程序 P,平均CPI分別為2和1,那么程序P在 M1和M2上運行時間的比值是12 qA.

5、0.4B. 0.625C. 1.6D. 2.513 .某計算機主存按字節編址, 由4個64M*8位的DRAM芯片采用交叉編址方式構成, 并與寬度為32位的存儲器總線相連,主存每次最多讀寫32位數據.假設double型變量x的主存地址為804 001AH,那么讀取x需要的存儲周期是13 .A. 1B. 2C. 3D. 414 .某C語言程序段如下： for(i = 0; i <= 9; i+) lemp = 1;for(j < 0; j <= I; j+) temp *= aj; sum += temp;以下關于數組a的訪問局部性的描述中,正確的選項是14 qA.時間局部性和空

6、間局部性皆有B.無時間局部性,有空間局部性C.有時間局部性,無空間局部性D.時間局部性和空間局部性皆無15.以下尋址方式中,最適合按下標順序訪問一維數組元素的是 15_.A. 相對尋址B.存放器尋址C.直接尋址D. 變址尋址16 .某計算機按字節編址,指令字長固定且只有兩種指令格式,其中三地址指令29條,二地址指令107條,每個地址字段為 6位,那么指令字長至少應該是16 .A. 24 位B. 26 位C. 28 位D. 32 位17 .以下關于超標量流水線特性白表達中,正確的選項是 16 .I .能縮短流水線功能段的處理時間II .能在一個時鐘周期內同時發射多條指令III .能結合動態調度技

7、術提升指令執行并行性A.僅 IIB.僅 I、IIIC.僅 II、IIID. I、II 和 III18 .以下關于主存儲器MM和限制存儲器C9的表達中,錯誤的選項是18 .A. MM 在 CPU外,CS在 CPU 內B. MM按地址訪問,CS按內存訪問C. MM存儲指令和數據,CS存儲微指令D. MM用RAM和ROM實現,CS用ROM實現19 .以下關于指令流水線數據通路的表達中,錯誤的選項是19 .A.包含生成限制信號的限制部件B.包含算法邏輯運算部件ALUC.包含通用存放器組和取指部件D.由組合邏輯電路和時序邏輯電路組合而成20 .以下關于多總線結構的表達中,錯誤的選項是20 qA.靠近CP

8、U的總線速度較快B.存儲器總線可支持突發傳送方式C.總線之間須通過橋接器相連D. PC I_Express*16采用并行傳輸方式21 . I/O指令實現的數據傳送通常發生在 20A. I/O設備和I/O端口之間B.通用存放器和I/O設備之間C. I/O端口和I/O端口之間D.通用存放器和I/O端口之間22.以下關于多重中斷系統的表達中,錯誤的選項是一22_OA.在一條指令執行結束時響應中斷B.中斷處理期間CPU處于關中斷狀態C.中斷請求的產生與當前指令的執行無關D. CPU通過采樣中斷請求信號檢測中斷請求23 .假設4個作業到達系統的時刻和運行時間如下表所示.作業到達時間t運行時間J103J2

9、13J312J431系統在t=2時開始作業調度.假設分別采用先來先效勞和短作業優先調度算法,那么選中的作業分別是23A.J2、J3B.J1、J4C.J2、J4D.J1、J324 .執行系統調用的過程包括如下主要操作:1返回用戶態2執行陷入trap指令3傳遞系統調用參數4執行相應的效勞程序正確的執行順序是24 .A. 2)3)1)4)B. 2)3)3)1)C. 3)2)4)1)D. 3)4)2)1)25.某計算機按字節編址,其動態分區內存治理采用最正確適應算法,每次分配和回收內 存后都對空閑分區鏈重新排序.當前空閑分區信息如下所示.分區起始地址20K500K1000K200K分區大小40KB80

10、KB100KB200KB回收起始地址為60K、大小為140KB的分區后,系統中空閑分區的數量、空閑分區鏈第一個分區的起始地址和大小分別是25 .A.3、20K、380KBB.3、500K、80KBC.4、20K、180KBD.4、500K、80KB26.某文件系統的簇和磁盤扇區大小分別為1KB和512B.假設一個文件的大小為 1026B,那么系統分配給該文件的磁盤空間大小是26 .A. 1026BB. 1536BC. 1538BD. 2048B27 .以下有關基于時間片的進程調度的表達中,錯誤的選項是27 qA.時間片越短,進程切換的次數越多,系統開銷也越大B.當前進程的時間片用完后,該進程狀

11、態由執行態變為阻塞態C.時鐘中斷發生后,系統會修改當前進程在時間片內的剩余時間D.影響時間片大小的主要因素包括響應時間、系統開銷和進程數量等.28 .與單道程序系統相比,多道程序系統的優先是 28_OI .CPU利用率高II .系統開銷小III .系統吞吐量大IV .I/O設備利用率高A.僅 I、IIIB.僅 I、IVC.僅 II、IIID.僅 I、III、IV29.以下選項中,磁盤邏輯格式化程序所做的工作是29 .I .對磁盤進行分區II .建立文件系統的根目錄III .確定磁盤扇區校驗碼所占位數IV對保存空閑磁盤塊信息的數據結構進行初始化A.僅 IIB.僅 II、IVC.僅 III、IVD

12、.僅 I、II、IV30 .某文件系統中,針對每個文件,用戶類別分為 4類：平安治理員、文件主、文件主 的伙伴、其他用戶；訪問權限分為 5種：完全限制、執行、修改、讀取、寫入.假設 文件限制塊中用二進制位串表示文件權限,為表示不同類別用戶對一個文件的訪問權限,那么描述文件權限白位數至少應為30 .A. 5B. 9C. 12D. 2031 .假設文件fl的硬鏈接為f2,兩個進程分別翻開 fl和f2,獲得對應的文彳描述符為fd1和fd2,那么以下表達中,正確的選項是31 .I .f1和f2的讀寫指針位置保持相同II .f1和f2共享同一個內存索引結點III .fd1和fd2分別指向各自的用戶翻開文

13、件表中的一項A.僅 IIIB.僅 II、IIIC.僅 I、IID. I、II 和 III32 .系統將數據從磁盤讀到內存的過程包括以下操作：1) DMA限制器發出中斷請求2)初始化DMA限制器并啟動磁盤3)從磁盤傳輸一塊數據到內存緩沖區4)執行" DMA結束中斷效勞程序 正確的執行順序是32 qA. 3)1)2)4)B. 2)3)1)4)C. 2)1)3)4)D. 1)2)4)3)33 .假設OSI參考模型的應用層欲發送400B的數據無拆分,除物理層和應用層之處,其他各層在封裝 PDU時均引入20B的額外開銷,那么應用層數據傳輸效率約為_33 .A. 80%B. 83%C. 87%D

14、. 91%34 .假設信道在無噪聲情況下的極限數據傳輸速率不小于信噪比為30dB條件下的極限數據傳輸速率,那么信號?態至少是34 .A. 4B. 8C. 16D. 3235 .在以下圖所示的網絡中,假設主機H發送一個封裝訪問InternetIP分組的IEEE 802.11數據幀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

15、-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.37 .直接圭裝 RIP, OSPF BGP報文的協議分別是37 .A. TCP UDP、IPB. TCP IP、UDPC. UDP、TCR IPD. UDP、IP、TCP38 .假設將網絡劃分為128個規模相同的子網,那么每個子網可分配的最大IP地址個數是38 .A. 254B. 256C. 510D. 51239

16、.假設甲向乙發起了一個 TCP連接,最大段長MSS=KB, RTT=5ms,乙開辟的接收緩存為 64KB,那么甲從連接建立慈至發送窗口到達32KB,需經過的時間至少是38 .A. 25msB. 30msC. 160msD. 165ms40 .以下關于FTP協議的表達中,錯誤的選項是40 .A.數據連接在每次數據傳輸完畢后就關閉B.限制連接在整個會話期間保持翻開狀態C.效勞器與客戶端的 TCP 20端口建立數據連接D.客戶端與效勞器的 TCP 21端口建立限制連接、綜合應用題41 .請設計一個算法,將給定的表達式樹(二叉樹)轉換為等價的中綴表達式(通過括 號反映操作符的計算次序)并輸出.例如,當

17、以下兩棵表達式作為算法的輸入時： 輸出的等價中綴表達式分別為(a+b)*(c+(-d)和(a*b)+(-(-c-d).二叉樹結點定義如下：Typedef struct nodechar data10;/存儲操作數或操作符Struct node * left, * right;BTree;要求：(1)給出算法的根本設計思想.(2)根據設計思想,采用 C或C+語言描述算法,關鍵之處給出注釋.42 .使用Prim (普里姆)算法求帶權連通圖的最小(代價)生成樹(MST).請答復下歹U問題.(1)對以下圖G,從頂點A開始求G的MST,依次給出按算法選出的邊.(2)圖G的MST是唯一的嗎？(3)對任意的

18、帶權連通圖,滿足什么條件時,其MST是唯一的？ii-t Jf43 .f(n)IB,計算f(n)的C語言函數f1如下：1 int f1(unsigned n)2 int sum = 1, power = 1;3 for(unsignedi =0; i <= n-1; i+)4 power *= 2;5 sum += power;6 7 return sum;8 將f1中的int都改為float,可得到計算f(n)的另一個函數f2.假設unsigned和int 型數據都占32位,float采用IEEE 754單精度標準.請答復以下問題.(1)當n=0時,f1會出現死循環,為什么？假設將f1中

19、的變量i和n都定義為int型, 那么f1是否還會出現死循環？為什么？(2) f1(23)和f2(23)的返回值是否相等？機器數各是什么(用十六進制表示)？(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)的機器數為7F80 0000H,對應的值是什么？假設使 f2(n)的結果不溢出,那么 最大的n是什么？假設使f2(n)的結果精確(無舍入),那么最大的n是多少？44.在按字節編址

20、的計算機M上,題43中f1的局部源程序(局部)與對應的機器級代碼(包括指令的虛擬地址)如下：int f1(unsigned n)push ebp0040102055for(unsigned i = 0; i <=n-1; i+) 200040105E39 4D F4cmp dword ptrebp-0Ch, ecx power *= 2;2300401066 D1 E2shl edx, lreturn sum;350040107F C3ret其中,機器級代碼行包括彳丁號、虛擬地址、機器指令和匯編指令.請答復以下問題.(1)計算機M是RISC還是CIS.為什么？(2) f1的機器指令代碼共

21、占多少字節？要求給出計算過程.(3)第20條指令cmp通過i減n-1實現對i和n-1的比擬.執行f1(0)過程中,當i=0 時,cmp指令執行后,進/借位標志CF的內容是什么？要求給出計算過程.(4)第23條指令shl通過左移操彳實現了 power*2運算,在f2中能否也用shl指令 實現power*2 ?為什么？45.假定題44給出的計算機 M采用二級分布虛擬存儲治理方式,邪氣地址格式如下：頁目錄號(10位)頁表索引(10位)頁內偏移量(12位)請針題43的函數f1和題44中的機器指令代碼,答復以下問題.(1)函數f1的機器指令代碼占多少頁？(2)取第1條指令(push ebp)時,假設在進行地址變換的過程中需要訪問內存中的頁 目錄和頁表,而會分別訪問它們各自的第幾個表項(編號從0開始)？(3) M的I/O采用中斷限制方式.假設進程P在調用f1之前通過scanf()獲取n的值,那么在執行scanf()的過程中,進程P的狀態會如何變化？CPU是否會進入內核態？46.某進程中有3個并發執行的線程 thread1、thread2和thread3 ,其偽代碼如下所示./復數的結構類型定義typedef structthread1 thread3 cnum w;cnum