計算機考研真題及復習資料

2012年全國碩士硏究生入學統(tǒng)一考試一計算機專業(yè)基礎綜合試題2012年全國碩士硏究生入學統(tǒng)一考試一計算機專業(yè)基礎綜合試題#計算機專業(yè)基礎綜合試題參考答案一、單項選擇題：每小題2分，共80分。1-5BAABC6-10CCADA11-15DDBDD16-20ACCCD21-25DBCBB26-30ADABC31-35ABBCA36-40BCADD二、綜合應用題：41~47小題，共70分?！窘馕觥?1)對于長度分別為m，n的兩個有序表的合并過程，最壞情況下需要一直比較到兩個表尾元素，比較次數(shù)為m+n-1次。已知需要5次兩兩合并，故可設總比較次數(shù)為X-5，X就是以N個葉子結(jié)點表示升序表，以升序表的表長表示結(jié)點權重，構造的二叉樹的帶權路徑長度。故只需設計方案使得X最小。這樣受哈夫曼樹和最佳歸并樹思想的啟發(fā)，設計哈夫曼樹如下：這樣，最壞情況下比較的總次數(shù)為：N=(10+35)X4+(40+50+60)X3+2005=825(2)N(N>2)個不等長升序表的合并策略：以N個葉子結(jié)點表示升序表，以升序表的表長表示結(jié)點權重，構造哈夫曼樹。合并時，從深度最大的結(jié)點所代表的升序表開始合并，依深度次序一直進行到根結(jié)點。理由：N個有序表合并需要進行N-1次兩兩合并，可設最壞情況下的比較總次數(shù)為X-N+1,X就是以N個葉子結(jié)點表示升序表，以升序表的表長表示結(jié)點權重，構造的二叉樹的帶權路徑長度。根據(jù)哈夫曼樹的特點，上述設計的比較次數(shù)是最小的。【解析】(1)算法思想：順序遍歷兩個鏈表到尾結(jié)點時，并不能保證兩個鏈表同時到達尾結(jié)點。這是因為兩個鏈表的長度不同。假設一個鏈表比另一個鏈表長k個結(jié)點，我們先在長鏈表上遍歷k個結(jié)點，之后同步遍歷兩個鏈表。這樣我們就能夠保證它們同時到達最后一個結(jié)點了。由于兩個鏈表從第一個公共結(jié)點到鏈表的尾結(jié)點都是重合的。所以它們肯定同時到達第一個公共結(jié)點。于是得到算法思路：遍歷兩個鏈表求的它們的長度L1，L2；比較L1,L2,找出較長的鏈表，并求L=|L1-L2|;先遍歷長鏈表的L各結(jié)點；④同步遍歷兩個鏈表，直至找到相同結(jié)點或鏈表結(jié)束。算法的C語言代碼描述LinkListSearch_First_Common(LinkListLl,LinkListL2){//本算法實現(xiàn)線性時間內(nèi)找到兩個單鏈表的第一個公共結(jié)點intlen1=Length(Ll);,len2=Length(L2);LinkListlongList,shortlist;//分另U指向較長和較短的鏈表if(len1>len2){longList=Ll->next;shortlist=L2—〉next;L=len1-len2;//表長之差}else{longList=L2-〉next;shortlist=Ll->next;L=len2-len1;//表長之差}While(L--)longList=longList-〉next;while(longList!=NULL){if(longList==shortList)//同步尋找共同結(jié)點returnlongList;else{longList=longList->next;shortlist=shortlist->next;}}//whilereturnNULL;}算法的時間復雜度為O(lenl+len2)，空間復雜度為0(1)。43.【解析】MIPS=CPU主頻x10_6/CPI=80M/4=20；平均每條指令訪存1.5次,Cache的命中率為99%，故每秒Cache缺失的次數(shù)=20Mx1.5x1%=300000(次)；在不使用DMA傳送的情況下，所有主存的存取操作都需要經(jīng)過CPU，所以主存帶寬至少應為20M/sx1.5x4B=120MB/s。由于頁式虛擬存儲方式的頁表始終位于內(nèi)存，則產(chǎn)生缺頁異常的只能是指令的訪存。每秒產(chǎn)生缺頁中斷20M/sx1.5x0.0005%=150次。因此平均每秒發(fā)出的DMA請求次數(shù)至少是150x4KB/4B=150K次。(3)優(yōu)先響應DMA請求。DMA通常連接高速I/0設備，若不及時處理可能丟失數(shù)據(jù)。當4體低位交叉存儲器穩(wěn)定運行時，能提供的最大帶寬為4x4B/50ns=320MB/s。44.【解析】x的機器碼為［x］補111111011111B，即指令執(zhí)行前(R1)=FDFFH,右移1位后位1111111011111111B，即指令執(zhí)行后(R1)=FEFFH。至少需要4+(5-1)=8個時鐘周期數(shù)。I3的ID段被阻塞的原因：因為I3與I1和I2都存在數(shù)據(jù)相關，需等到I1和I2將結(jié)果寫回寄存器后，I3才能讀寄存器內(nèi)容，所以I3的ID段被阻塞。I4的IF段被阻塞的原因：因為I4的前一條指令I3在ID段被阻塞，所以I4的IF段被阻塞4）因2*x操作有左移和加法兩種實現(xiàn)方法，故x=x*2+a對應的指令序列為I1LOADR1，[x]I2LOADR2，[a]I3SHLR1//或者ADDR1，R1I4ADDR1，R2I5STORER2，[x]這5條指令在流水線中執(zhí)行過程如下圖所示。時間單元指令123456789101112131415161711IFIDEXMWB12IFIDEXMWB13IFIDEXMWBI4IFIDEXMWB15IFIDEXMWB故執(zhí)行x=x*2+a語句最少需要17個時鐘周期。45.【解析】（1）頁框號為21。因為起始駐留集為空，而0頁對應的頁框為空閑鏈表中的第三個空閑頁框（21），其對應的頁框號為21。（2）頁框號為32。理由：因11>10故發(fā)生第三輪掃描，頁號為1的頁框在第二輪已處于空閑頁框鏈表中，此刻該頁又被重新訪問，因此應被重新放回駐留集中，其頁框號為32。（3）頁框號為41。理由：因為第2頁從來沒有被訪問過，它不在駐留集中，因此從空閑頁框鏈表中取出鏈表頭的頁框41，頁框號為41。（4）合適。理由：如果程序的時間局部性越好，從空閑頁框鏈表中重新取回的機會越大，該策略的優(yōu)勢越明顯。46.【解析】（1）文件系統(tǒng)中所能容納的磁盤塊總數(shù)為4TB/1KB=232。要完全表示所有磁盤塊，索引項中的塊號最少要占32/8=4B。而索引表區(qū)僅采用直接索引結(jié)構，故512B的索引表區(qū)能容納512B/4B=128個索引項。每個索引項對應一個磁盤塊，所以該系統(tǒng)可支持的單個文件最大長度是128x1KB=128KB。（2）這里的考查的分配方式不同于我們所熟悉的三種經(jīng)典分配方式，但是題目中給出了詳細的解釋。所求的單個文件最大長度一共包含兩部分：預分配的連續(xù)空間和直接索引區(qū)。連續(xù)區(qū)塊數(shù)占2B,共可以表示2]6個磁盤塊，即226B。直接索引區(qū)共504B/6B=84個索引項。所以該系統(tǒng)可支持的單個文件最大長度是226B+84KB。為了使單個文件的長度達到最大，應使連續(xù)區(qū)的塊數(shù)字段表示的空間大小盡可能接近系統(tǒng)最大容量4TB。分別設起始塊號和塊數(shù)分別占4B，這樣起始塊號可以尋址的范圍是232個磁盤塊，共4TB，即整個系統(tǒng)空間。同樣的，塊數(shù)字段可以表示最多232個磁盤塊，共4TB。47.【解析】（1）由于題47-a表中1、3、4號分組的原IP地址均為192.168.0.8（c0a80008H），所以1,3,4號分組是由H發(fā)送的。題47-a表中1號分組封裝的TCP段的FLAG為02H（即SYN=1,ACK=0）,seq=846b41c5H，2號分組封裝的TCP段的FLAG為12H（即SYN=1，ACK=1），seq=e0599fefH，ack=846b41c6H，3號分組封裝的TCP段的FLAG為10H（即ACK=1），seq=846b41c6H，ack=e0599ff0H,所以1、2、3號分組完成了TCP連接建立過程。由于快速以太網(wǎng)數(shù)據(jù)幀有效載荷的最小長度為46字節(jié)，表中3、5號分組的總長度為40(28H)字節(jié)，小于46字節(jié)，其余分組總長度均大于46字節(jié)。所以3、5號分組通過快速以太網(wǎng)傳輸時進行了填充。由3號分組封裝的TCP段可知，發(fā)送應用層數(shù)據(jù)初始序號為seq=846b41c6H，由5號分組封裝的TCP段可知，ack為se