考研408計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合真題及答案

1、考研408計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合真題及答案019年全國碩士研究生招生考試計算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題一、單項選擇題：1小題，每小題2分，共80分。下列每題給出的四個選項中,只有一個選項符合試題要求。1. 設(shè)是描述問題規(guī)模的非負(fù)整數(shù)，下列程序段的時間復(fù)雜度是x=0；wh(n=(+l）(x+l)x=+l； o(lgn) . (n1/2） c.o(n) d. (n）2. 若將一棵樹t轉(zhuǎn)化為對應(yīng)的二又樹bt,則下列對bt的遍歷中，其遍歷序列與t的后根遍歷序列相同的是a. 先序遍歷 b. 中序遍歷 后序遍歷 .按層遍歷.對n個互不相同的符號進(jìn)行哈夫曼編碼。若生成的哈夫曼樹共有115

2、個結(jié)點(diǎn),則n的值是a. 56 b . . 60. 在任意一棵非空平衡二又樹(vl樹)t1中,刪除某結(jié)點(diǎn)v之后形成平衡二又樹t2,再將w插入2形成平衡二又樹t3。下列關(guān)于與t的敘述中,正確的是i.若v是t的葉結(jié)點(diǎn)，則與t3可能不相同若v不是t1的葉結(jié)點(diǎn),則與t3一定不相同.若v不是t的葉結(jié)點(diǎn)，則t1與t3一定相同a. 僅i b 僅ii c. 僅i、 d. 僅i、下圖所示的aoe網(wǎng)表示一項包含個活動的工程。活動d的最早開始時間和最遲開始時間分別是a. 3和 12和2 c. 2和 . 15和6. 用有向無環(huán)圖描述表達(dá)式(xy)*（(x+y）/x)，需要的頂點(diǎn)個數(shù)至少是. b. . d. 7.選擇一個

3、排序算法時，除算法的時空效率外，下列因素中，還需要考慮的是.數(shù)據(jù)的規(guī)模 .數(shù)據(jù)的存儲方式算法的穩(wěn)定性 .數(shù)據(jù)的初始狀態(tài)僅 僅i、c.僅、iv di、8 現(xiàn)有長度為1且初始為空的散列表ht，散列函數(shù)是(key）key7,采用線性探查(線性探測再散列)法解決沖突將關(guān)鍵字序列87，0,30，6，1，2,8,20依次插入到h后,h查找失敗的平均查找長度是a.4 b.5.25 c 6 d. 6.299. 設(shè)主串“abbaabcaabc”,模式串s=“abc”,采用kmp算法進(jìn)行模式匹配,到匹配成功時為止,在匹配過程中進(jìn)行的單個字符間的比較次數(shù)是. 9 . 0 c2 d151. 排序過程中,對尚未確定最終

4、位置的所有元素進(jìn)行一遍處理稱為一“趟”。下列序列中,不可能是快速排序第二趟結(jié)果的是a. 5，2,16，1,28，0,32,.，16，5，28，12,60,32，2c. 2,2,16,5，3，2，0d,2,2,8，1,，72,6011. 設(shè)外存上有120個初始?xì)w并段,進(jìn)行12路歸并時,為實(shí)現(xiàn)最佳歸并,需要補(bǔ)充的虛段個數(shù)是a. 1 b2 c. 3 d. 412. 下列關(guān)于馮諾依曼結(jié)構(gòu)計算機(jī)基本思想的敘述中,錯誤的是. 程序的功能都通過中央處理器執(zhí)行指令實(shí)現(xiàn)b.指令和數(shù)據(jù)都用二進(jìn)制表示，形式上無差別.指令按地址訪問,數(shù)據(jù)都在指令中直接給出d. 程序執(zhí)行前，指令和數(shù)據(jù)需預(yù)先存放在存儲器中13.考慮以下

5、c語言代碼：nsignedshort usi=6535;shortsi=ui;執(zhí)行上述程序段后，i的值是a. -1 b.-36 c.-37 . -35. 下列關(guān)于缺頁處理的敘述中,錯誤的是a 缺頁是在地址轉(zhuǎn)換時cpu檢測到的一種異常b 缺頁處理由操作系統(tǒng)提供的缺頁處理程序來完成c. 缺頁處理程序根據(jù)頁故障地址從外存讀入所缺失的頁d. 缺頁處理完成后回到發(fā)生缺頁的指令的下一條指令執(zhí)行15 某計算機(jī)采用大端方式，按字節(jié)編址。某指令中操作數(shù)的機(jī)器數(shù)為1234ff00，該操作數(shù)采用基址尋址方式,形式地址（用補(bǔ)碼表示)為ff1h，基址寄存器內(nèi)容為00 000h,則該操作數(shù)的lsb（最低有效字節(jié))所在的地

6、址是a f000 f1h b. f005h c eff ff2h d. eff ff516. 下列有關(guān)處理器時鐘脈沖信號的敘述中,錯誤的是a 時鐘脈沖信號由機(jī)器脈沖源發(fā)出的脈沖信號經(jīng)整形和分頻后形成.時鐘脈沖信號的寬度稱為時鐘周期,時鐘周期的倒數(shù)為機(jī)器主頻c. 時鐘周期以相鄰狀態(tài)單元間組合邏輯電路的最大延遲為基準(zhǔn)確定.處理器總是在每來一個時鐘脈沖信號時就開始執(zhí)行一條新的指令7. 某指令功能為rrrr1+mrr,其兩個源操作數(shù)分別采用寄存器、寄存器間接尋址方式。對于下列給定部件，該指令在取數(shù)及執(zhí)行過程中需要用到的是i.通用寄存器組（gps） 算術(shù)邏輯單元(alu).存儲器（mer) 指令譯碼器(

7、)a. 僅i、 b.僅、. 僅、v . 僅、1 在采用“取指、譯碼/取數(shù)、執(zhí)行、訪存、寫回”5段流水線的處理器中，執(zhí)行如下指令序列，其中s0、s1、s2、s3和t2表示寄存器編號。1:add s，s1，s0 rsr1+rsi2:load 3，0(t2) /rs3mt2+3：adds2，s2 s3 /r2rs2rs3i4：stores2,0(t2) /mrt22下列指令對中,不存在數(shù)據(jù)冒險的是a. i和i3 b. 和i3 c. i2和i4 di3和i49. 假定一臺計算機(jī)采用3通道存儲器總線,配套的內(nèi)存條型號為dr-1333,即內(nèi)存條所接插的存儲器總線的工作頻率為1333 mhz、總線寬度為4位

8、,則存儲器總線的總帶寬大約是a .66 gb/s b.2 gbs gs d. g/s.下列關(guān)于磁盤存儲器的敘述中，錯誤的是a. 磁盤的格式化容量比非格式化容量小. 扇區(qū)中包含數(shù)據(jù)、地址和校驗等信息c. 磁盤存儲器的最小讀寫單位為一個字節(jié)d. 磁盤存儲器由磁盤控制器、磁盤驅(qū)動器和盤片組成1某設(shè)備以中斷方式與cpu進(jìn)行數(shù)據(jù)交換,cu主頻為1 hz，設(shè)備接口中的數(shù)據(jù)緩沖寄存器為3位，設(shè)備的數(shù)據(jù)傳輸率為50kb/s。若每次中斷開銷(包括中斷響應(yīng)和中斷處理)為1000個時鐘周期，則cpu用于該設(shè)備輸入輸出的時間占整個cpu時間的百分比最多是. .5% . 2.5% c5% d. 12 5%22. 下列關(guān)

9、于dma方式的敘述中，正確的是. dma傳送前由設(shè)備驅(qū)動程序設(shè)置傳送參數(shù)ii數(shù)據(jù)傳送前由dma控制器請求總線使用權(quán).數(shù)據(jù)傳送由da控制器直接控制總線完成i.ma傳送結(jié)束后的處理由中斷服務(wù)程序完成a. 僅i、 b. 僅、c僅、iv d i、i23下列關(guān)于線程的描述中，錯誤的是.內(nèi)核級線程的調(diào)度由操作系統(tǒng)完成. 操作系統(tǒng)為每個用戶級線程建立一個線程控制塊c. 用戶級線程間的切換比內(nèi)核級線程間的切換效率高d 用戶級線程可以在不支持內(nèi)核級線程的操作系統(tǒng)上實(shí)現(xiàn)24 下列選項中，可能將進(jìn)程喚醒的事件是i. i/結(jié)束 . 某進(jìn)程退出臨界區(qū) . 當(dāng)前進(jìn)程的時間片用完a. 僅i b. 僅 c. 僅i、 d. i

10、、5 下列關(guān)于系統(tǒng)調(diào)用的敘述中，正確的是i.在執(zhí)行系統(tǒng)調(diào)用服務(wù)程序的過程中，cu處于內(nèi)核態(tài).操作系統(tǒng)通過提供系統(tǒng)調(diào)用避免用戶程序直接訪問外設(shè).不同的操作系統(tǒng)為應(yīng)用程序提供了統(tǒng)一的系統(tǒng)調(diào)用接口i.系統(tǒng)調(diào)用是操作系統(tǒng)內(nèi)核為應(yīng)用程序提供服務(wù)的接口a. 僅、i 僅ii、ic.僅i、iv d. 僅i、26. 下列選項中，可用于文件系統(tǒng)管理空閑磁盤塊的數(shù)據(jù)結(jié)構(gòu)是i.位圖 索引節(jié)點(diǎn) .空閑磁盤塊鏈 .文件分配表(ft)a. 僅、 . 僅、c. 僅、 d. 僅、. 系統(tǒng)采用二級反饋隊列調(diào)度算法進(jìn)行進(jìn)程調(diào)度。就緒隊列q采用時間片輪轉(zhuǎn)調(diào)度算法,時間片為10m;就緒隊列q采用短進(jìn)程優(yōu)先調(diào)度算法；系統(tǒng)優(yōu)先調(diào)度q1隊列

11、中的進(jìn)程,當(dāng)q1為空時系統(tǒng)才會調(diào)度q2中的進(jìn)程;新創(chuàng)建的進(jìn)程首先進(jìn)入q1;q1中的進(jìn)程執(zhí)行一個時間片后,若未結(jié)束，則轉(zhuǎn)入q2。若當(dāng)前1、q2為空,系統(tǒng)依次創(chuàng)建進(jìn)程l、p2后即開始進(jìn)程調(diào)度pl、p需要的cu時間分別為0ms和20ms，則進(jìn)程1、p2在系統(tǒng)中的平均等待時間為.5 ms b. 20 c. 15 ms . 0 m28 在分段存儲管理系統(tǒng)中,用共享段表描述所有被共享的段。若進(jìn)程1和共享段s,下列敘述中,錯誤的是a 在物理內(nèi)存中僅保存一份段s的內(nèi)容b.段s在p1和2中應(yīng)該具有相同的段號c p1和p2共享段s在共享段表中的段表項d.p1和p2都不再使用段s時才回收段s所占的內(nèi)存空間29. 某

12、系統(tǒng)采用lu頁置換算法和局部置換策略,若系統(tǒng)為進(jìn)程預(yù)分配了個頁框，進(jìn)程訪問頁號的序列為，2，7,5,3,5，2,7，6，則進(jìn)程訪問上述頁的過程中，產(chǎn)生頁置換的總次數(shù)是a b. 4 . 5 d. 63. 下列關(guān)于死鎖的敘述中，正確的是. 可以通過剝奪進(jìn)程資源解除死鎖i. 死鎖的預(yù)防方法能確保系統(tǒng)不發(fā)生死鎖ii. 銀行家算法可以判斷系統(tǒng)是否處于死鎖狀態(tài).當(dāng)系統(tǒng)出現(xiàn)死鎖時，必然有兩個或兩個以上的進(jìn)程處于阻塞態(tài)a. 僅ii、 . 僅i、c僅i、 d 僅i、3.某計算機(jī)主存按字節(jié)編址,采用二級分頁存儲管理,地址結(jié)構(gòu)如下所示頁目錄號（0位) 頁號(1位) 頁內(nèi)偏移(12位)虛擬地址050 125h對應(yīng)的頁

13、目錄號、頁號分別是a. 081、11 b.08h、401h c 20h、101h d.201h、4013. 在下列動態(tài)分區(qū)分配算法中，最容易產(chǎn)生內(nèi)存碎片的是a 首次適應(yīng)算法 b.最壞適應(yīng)算法 c. 最佳適應(yīng)算法 d. 循環(huán)首次適應(yīng)算法3 osi參考模型的第層（自下而上)完成的主要功能是a. 差錯控制b. 路由選擇c. 會話管理d數(shù)據(jù)表示轉(zhuǎn)換34. 100set快速以太網(wǎng)使用的導(dǎo)向傳輸介質(zhì)是a 雙絞線b. 單模光纖 多模光纖d. 同軸電纜35 對于滑動窗口協(xié)議，如果分組序號采用3比特編號，發(fā)送窗口大小為5,則接收窗口最大是a. b. c 4 . 536.假設(shè)一個采用csma/cd協(xié)議的0bps局

14、域網(wǎng),最小幀長是128b，則在一個沖突域內(nèi)兩個站點(diǎn)之間的單向傳播延時最多是a. 2.56 s . .12 s c10.24 d 0.48 7. 若將0. 00. 1. 2劃分為5個子網(wǎng),則可能的最小子網(wǎng)的可分配i地址數(shù)是a. 126 b. 254 c.510d02238. 某客戶通過一個tcp連接向服務(wù)器發(fā)送數(shù)據(jù)的部分過程如題38圖所示?？蛻粼趖0時刻第一次收到確認(rèn)序列號ak_sq=100的段，并發(fā)送序列號seq10的段，但發(fā)生丟失。若tcp支持快速重傳，則客戶重新發(fā)送seq=10段的時刻是. 1 b. t2c.t3 d. t439. 若主機(jī)甲主動發(fā)起一個與主機(jī)乙的tp連接，甲、乙選擇的初始序

15、列號分別為0和2046，則第三次握手tp段的確認(rèn)序列號是a 21 b.09 c 06 d 20740.下列關(guān)于網(wǎng)絡(luò)應(yīng)用模型的敘述中,錯誤的是a 在p模型中,結(jié)點(diǎn)之間具有對等關(guān)系b. 在客戶/服務(wù)器(cs）模型中，客戶與客戶之間可以直接通信在c/s模型中，主動發(fā)起通信的是客戶，被動通信的是服務(wù)器d在向多用戶分發(fā)一個文件時，p2p模型通常比s模型所需時間短二、綜合應(yīng)用題：414小題,共70分。41.(13分)設(shè)線性表l(a1，a2，a，an，1,a。)采用帶頭結(jié)點(diǎn)的單鏈表保存,鏈表中結(jié)點(diǎn)定義如下:ypeef tuct ode int ta；tructnode* nex； noe；請設(shè)計一個空間復(fù)雜

16、度為o(1）且時間上盡可能高效的算法，重新排列l(wèi)中的各結(jié)點(diǎn)，得到線性表l=（a1,a,2，a-1，a3,an-2)。要求:(1） 給出算法的基本設(shè)計思想（)根據(jù)設(shè)計思想，采用c或+語言描述算法,關(guān)鍵之處給出注釋。(3) 說明你所設(shè)計的算法的時間復(fù)雜度。42.(10分)請設(shè)計一個隊列,要求滿足:初始時隊列為空;入隊時,允許增加隊列占用空間;出隊后,出隊元素所占用的空間可重復(fù)使用，即整個隊列所占用的空間只增不減;人隊操作和出隊操作的時間復(fù)雜度始終保持為o()。請回答下列問題：(1) 該隊列應(yīng)該選擇鏈?zhǔn)酱鎯Y(jié)構(gòu)，還是順序存儲結(jié)構(gòu)?(2) 畫出隊列的初始狀態(tài)，并給出判斷隊空和隊滿的條件(3)畫出第一個

17、元素入隊后的隊列狀態(tài)。(4） 給出入隊操作和出隊操作的基本過程。43(8分)有n(n3)位哲學(xué)家圍坐在一張圓桌邊，每位哲學(xué)家交替地就餐和思考。在圓桌中心有(m1）個碗,每兩位哲學(xué)家之間有1根筷子。每位哲學(xué)家必須取到一個碗和兩側(cè)的筷子之后，才能就餐,進(jìn)餐完畢,將碗和筷子放回原位,并繼續(xù)思考。為使盡可能多的哲學(xué)家同時就餐，且防止出現(xiàn)死鎖現(xiàn)象，請使用信號量的p、v操作（wai（)、sl()操作）描述上述過程中的互斥與同步，并說明所用信號量及初值的含義。(分)某計算機(jī)系統(tǒng)中的磁盤有30個柱面,每個柱面有10個磁道,每個磁道有200個扇區(qū)，扇區(qū)大小為51b。文件系統(tǒng)的每個簇包含2個扇區(qū)。請回答下列問題：

18、(1）磁盤的容量是多少?(2）假設(shè)磁頭在85號柱面上，此時有4個磁盤訪問請求，簇號分別為:10260、60005、1160和110。若采用最短尋道時間優(yōu)先(sstf)調(diào)度算法,則系統(tǒng)訪問簇的先后次序是什么?(3)第00530簇在磁盤上的物理地址是什么?將簇號轉(zhuǎn)換成磁盤物理地址的過程是由/o系統(tǒng)的什么程序完成的?45(16分)已知f(n)！n(l)（n-2)21,計算f(n)的c語言函數(shù)fl的源程序（陰影部分)及其在32位計算機(jī)m上的部分機(jī)器級代碼如下:其中,機(jī)器級代碼行包括行號、虛擬地址、機(jī)器指令和匯編指令，計算機(jī)m按字節(jié)編址,it型數(shù)據(jù)占32位。請回答下列問題:(1)計算f(10)需要調(diào)用函

19、數(shù)f多少次？執(zhí)行哪條指令會遞歸調(diào)用1？()上述代碼中，哪條指令是條件轉(zhuǎn)移指令?哪幾條指令一定會使程序跳轉(zhuǎn)執(zhí)行?(3)根據(jù)第16行call指令，第17行指令的虛擬地址應(yīng)是多少？已知第16行al指令采用相對尋址方式，該指令中的偏移量應(yīng)是多少(給出計算過程）?已知第6行l(wèi)指令的后4字節(jié)為偏移量，m采用大端還是小端方式?（4)(1)=227 0 800，但f1(1)的返回值為13 053 04，為什么兩者不相等？要使f1（1)能返回正確的結(jié)果，應(yīng)如何修改f1源程序？（5)第1行imuleax，ex表示有符號數(shù)乘法，乘數(shù)為a和recx,當(dāng)乘法器輸出的高、低32位乘積之間滿足什么條件時，溢出標(biāo)志o=1?要

20、使cpu在發(fā)生溢出時轉(zhuǎn)異常處理,編譯器應(yīng)在ul指令后加一條什么指令?6.(7分)對于題45,若計算機(jī)m的主存地址為32位，采用分頁存儲管理方式，頁大小為kb,則第1行ush指令和第30行t指令是否在同一頁中(說明理由)？若指令cae有64行,采用4路組相聯(lián)映射方式,主存塊大小為64，則3位主存地址中，哪幾位表示塊內(nèi)地址？哪兒位表示cche組號?哪幾位表示標(biāo)記(tag)信息?讀取第16行l(wèi)指令時，只可能在指令cache的哪一組中命中(說明理由)?4.(9分)某網(wǎng)絡(luò)拓?fù)淙珙}47圖所示,其中r為路由器，主機(jī)hh4的ip地址配置以及r的各接口ip地址配置如圖中所示?，F(xiàn)有若干臺以太網(wǎng)交換機(jī)（無la功能)

21、和路由器兩類網(wǎng)絡(luò)互連設(shè)備可供選擇。請回答下列問題:()設(shè)備1、設(shè)備2和設(shè)備3分別應(yīng)選擇什么類型網(wǎng)絡(luò)設(shè)備？(2）設(shè)備、設(shè)備和設(shè)備中,哪幾個設(shè)備的接口需要配置p地址?并為對應(yīng)的接口配置正確的ip地址。(3)為確保主機(jī)h1能夠訪問interne，r需要提供什么服務(wù)？(4)若主機(jī)3發(fā)送一個目的地址為921681.127的ip數(shù)據(jù)報,網(wǎng)絡(luò)中哪幾個主機(jī)會接收該數(shù)據(jù)報?201年全國碩士研究生招生考試計算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題參考答案一、單項選擇題12.b3.c4.a5.c6a7dc9.1d11.b12.3.a1.d15d16.d7.b18.c19.20.c21.a2.d23.b24.

22、c25c2b27.c8.29.c30.b31a32c33.a.b36b37.b38.c3d0.二、綜合應(yīng)用題41.【答案要點(diǎn)】（）算法的基本設(shè)計思想：算法分3步完成。第步,采用兩個指針交替前行，找到單鏈表的中間結(jié)點(diǎn);第2步，將單鏈表的后半段結(jié)點(diǎn)原地逆置;第步,從單鏈表前后兩段中依次各取一個結(jié)點(diǎn),按要求重排。(2)算法實(shí)現(xiàn)：()算法的時間復(fù)雜度:參考答案的時間復(fù)雜度為o(n)。42. 【答案要點(diǎn)】(1）采用鏈?zhǔn)酱鎯Y(jié)構(gòu)(兩段式單向循環(huán)鏈表),隊頭指針為front,隊尾指針為rr。(2)初始時，創(chuàng)建只有一個空閑結(jié)點(diǎn)的兩段式單向循環(huán)鏈表，頭指針fr與尾指針rar均指向空閑結(jié)點(diǎn)。如下圖所示。隊空的判定

23、條件：font=ar。隊滿的判定條件:frnt=rear-nxt。(3)插入第一個元素后的隊列狀態(tài):(4）操作的基本過程:3【答案要點(diǎn)】信號量smphoebowl；/用于協(xié)調(diào)哲學(xué)家對碗的使用seaphre chotksn；/用于協(xié)調(diào)哲學(xué)家對筷子的使用for(nt i=;i；i+)chopksalue=1；/設(shè)置兩個哲學(xué)家之間筷子的數(shù)量bol.vlu=n（n-1,m)；/olvaluen1，確保不死鎖cobeginhle(r） /哲學(xué)家的程序思考；p(bol)；/取碗p（chopstcksi）;/取左邊筷子（copstck(i+）mdn)；取右邊筷子就餐;v（chopstici)；(hopsic

24、s(i+1)mod );(bl);coend4.【答案要點(diǎn)】(1)磁盤容量=(300200512/024）kb=05 kb()依次訪問的簇是100 6、101660、10 560、6 005。(3)第0 530簇在磁盤上的物理地址由其所在的柱面號、磁頭號、扇區(qū)號構(gòu)成其所在的柱面號為10530/(020/2)=10。10050(10200/)530，磁頭號為530/(200/)=5。扇區(qū)號為(530)%200=60。將簇號轉(zhuǎn)換成磁盤物理地址的過程由磁盤驅(qū)動程序完成。45【答案要點(diǎn)】(1)計算f(0)需要調(diào)用函數(shù)f1共10次執(zhí)行第16行call 指令會遞歸調(diào)用f1。(2）第12行jle指令是條件轉(zhuǎn)移指令。第16行call指令、第20行jmp指令、第30行et指令一定會使程序跳轉(zhuǎn)