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

2019年全國(guó)碩士研究生招生考試

計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考

計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合試題一、單項(xiàng)選擇題：1~40小題，每小題2分，共80分。下列每題給出的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)符合試題要求。設(shè)n是描述問(wèn)題規(guī)模的非負(fù)整數(shù)，下列程序段的時(shí)間復(fù)雜度是x=0；while(n>=(x+l)*(x+l))2.3.4.5.6.7.8.9.x=x+l；A.O(logn)B.O(n1/2)C.O(n)D.2.3.4.5.6.7.8.9.x=x+l；A.O(logn)B.O(n1/2)C.O(n)D.O(n2)若將一棵樹(shù)T轉(zhuǎn)化為對(duì)應(yīng)的二又樹(shù)BT,則下列對(duì)BT的遍歷中，其遍歷序列與T的后根遍歷序列相同的是A.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷對(duì)n個(gè)互不相同的符號(hào)進(jìn)行哈夫曼編碼。若生成的哈夫曼樹(shù)共有115個(gè)結(jié)點(diǎn)，則n的值是A.56B.57C.58D.60在任意一棵非空平衡二又樹(shù)(AVL樹(shù))L中，刪除某結(jié)點(diǎn)v之后形成平衡二又樹(shù)T2，再將w插入T2形成平衡二又樹(shù)T3。下列關(guān)于T1與T3的敘述中，正確的是若v是T1的葉結(jié)點(diǎn)，則T1與T3可能不相同II,若v不是T1的葉結(jié)點(diǎn)，則T1與T3一定不相同m.若v不是T1的葉結(jié)點(diǎn)，則T1與t3一定相同A.僅IB.僅IIC.僅I、I下圖所示的AOE網(wǎng)表示一項(xiàng)包含8個(gè)活動(dòng)的工程?；顒?dòng)d的最早開(kāi)始時(shí)間和最遲開(kāi)始時(shí)間分別是A.3和7B.12和12C.12和14D.15和15用有向無(wú)環(huán)圖描述表達(dá)式(x+y)*((x+y)/x)，需要的頂點(diǎn)個(gè)數(shù)至少是A.5B.6C.8D.9選擇一個(gè)排序算法時(shí)，除算法的時(shí)空效率外，下列因素中，還需要考慮的是i.數(shù)據(jù)的規(guī)模II.數(shù)據(jù)的存儲(chǔ)方式m.算法的穩(wěn)定性a.僅mb.僅i、ic.僅I、m、ivV.數(shù)據(jù)的初始狀態(tài)d.i、ii、m、w現(xiàn)有長(zhǎng)度為11且初始為空的散列表HT,散列函數(shù)是H(key)=key%7,采用線性探查(線性探測(cè)再散列)法解決沖突將關(guān)鍵字序列87,40,30,6,11,22,98,20依次插入到日丁后，HT查找失敗的平均查找長(zhǎng)度是A.4B.5.25C.6D.6.29設(shè)主串T="abaabaabcabaabc”，模式串S="abaabc”，采用KMP算法進(jìn)行模式匹配，到匹配成功時(shí)為止，在匹配過(guò)程中進(jìn)行的單個(gè)字符間的比較次數(shù)是A.9B.10C.12D.15A.5,2,16,12,28,60,32,72B.2,16,5,28,12,60,32,72C.2,12,16,5,28,32,72,60D.5,2,12,28,16,32,72,60設(shè)外存上有120個(gè)初始?xì)w并段，進(jìn)行12路歸并時(shí)，為實(shí)現(xiàn)最佳歸并，需要補(bǔ)充的虛段個(gè)數(shù)是A.1B.2C.3D.4下列關(guān)于馮?諾依曼結(jié)構(gòu)計(jì)算機(jī)基本思想的敘述中，錯(cuò)誤的是程序的功能都通過(guò)中央處理器執(zhí)行指令實(shí)現(xiàn)指令和數(shù)據(jù)都用二進(jìn)制表示，形式上無(wú)差別指令按地址訪問(wèn)，數(shù)據(jù)都在指令中直接給出程序執(zhí)行前，指令和數(shù)據(jù)需預(yù)先存放在存儲(chǔ)器中考慮以下C語(yǔ)言代碼：unsignedshortusi=65535；shortsi=usi；執(zhí)行上述程序段后，si的值是-1B.-32767C.-32768D.-65535下列關(guān)于缺頁(yè)處理的敘述中，錯(cuò)誤的是缺頁(yè)是在地址轉(zhuǎn)換時(shí)CPU檢測(cè)到的一種異常缺頁(yè)處理由操作系統(tǒng)提供的缺頁(yè)處理程序來(lái)完成缺頁(yè)處理程序根據(jù)頁(yè)故障地址從外存讀入所缺失的頁(yè)缺頁(yè)處理完成后回到發(fā)生缺頁(yè)的指令的下一條指令執(zhí)行某計(jì)算機(jī)采用大端方式，按字節(jié)編址。某指令中操作數(shù)的機(jī)器數(shù)為1234FF00H，該操作數(shù)采用基址尋址方式，形式地址(用補(bǔ)碼表示)為FF12H，基址寄存器內(nèi)容為F0000000H，則該操作數(shù)的LSB(最低有效字節(jié))所在的地址是F000FF12HB.F000FF15HC.EFFFFF12HD.EFFFFF15H下列有關(guān)處理器時(shí)鐘脈沖信號(hào)的敘述中，錯(cuò)誤的是時(shí)鐘脈沖信號(hào)由機(jī)器脈沖源發(fā)出的脈沖信號(hào)經(jīng)整形和分頻后形成時(shí)鐘脈沖信號(hào)的寬度稱(chēng)為時(shí)鐘周期，時(shí)鐘周期的倒數(shù)為機(jī)器主頻時(shí)鐘周期以相鄰狀態(tài)單元間組合邏輯電路的最大延遲為基準(zhǔn)確定處理器總是在每來(lái)一個(gè)時(shí)鐘脈沖信號(hào)時(shí)就開(kāi)始執(zhí)行一條新的指令某指令功能為R[r2]jR[r1]+M[R[r0]]，其兩個(gè)源操作數(shù)分別采用寄存器、寄存器間接尋址方式。對(duì)于下列給定部件，該指令在取數(shù)及執(zhí)行過(guò)程中需要用到的是通用寄存器組(GPRs)□.算術(shù)邏輯單元(ALU)存儲(chǔ)器(Memory)□.指令譯碼器(ID)僅I、口B.僅I、口、口C.僅口、口、IVD.僅I、口、口在采用“取指、譯碼/取數(shù)、執(zhí)行、訪存、寫(xiě)回”5段流水線的處理器中，執(zhí)行如下指令序列，其中s0、s1、s2、s3和t2表示寄存器編號(hào)。I1：adds2，s1，s0//R[s2]—R[s1]+R[s0]I2：loads3，0(t2)//R[s3]-M[R[t2]+0]I3：adds2，s2s3//R[s2]-R[s2]+R[s3]I4：stores2，0(t2)//M[R[t2]+0]—R[s2]下列指令對(duì)中，不存在數(shù)據(jù)冒險(xiǎn)的是I1和I3B.I2和I3C.I2和I4D.I3和I4假定一臺(tái)計(jì)算機(jī)采用3通道存儲(chǔ)器總線，配套的內(nèi)存條型號(hào)為DDR3-1333，即內(nèi)存條所接插的存儲(chǔ)器總線的工作頻率為1333MHz、總線寬度為64位，則存儲(chǔ)器總線的總帶寬大約是A.10.66GB/sB.32GB/sC.64GB/sD.96GB/s下列關(guān)于磁盤(pán)存儲(chǔ)器的敘述中，錯(cuò)誤的是磁盤(pán)的格式化容量比非格式化容量小扇區(qū)中包含數(shù)據(jù)、地址和校驗(yàn)等信息磁盤(pán)存儲(chǔ)器的最小讀寫(xiě)單位為一個(gè)字節(jié)磁盤(pán)存儲(chǔ)器由磁盤(pán)控制器、磁盤(pán)驅(qū)動(dòng)器和盤(pán)片組成某設(shè)備以中斷方式與CPU進(jìn)行數(shù)據(jù)交換，CPU主頻為1GHz，設(shè)備接口中的數(shù)據(jù)緩沖寄存器為32位，設(shè)備的數(shù)據(jù)傳輸率為50kB/s。若每次中斷開(kāi)銷(xiāo)(包括中斷響應(yīng)和中斷處理)為1000個(gè)時(shí)鐘周期，則CPU用于該設(shè)備輸入/輸出的時(shí)間占整個(gè)CPU時(shí)間的百分比最多是A.1.25%B.2.5%C.5%D.12.5%下列關(guān)于DMA方式的敘述中，正確的是DMA傳送前由設(shè)備驅(qū)動(dòng)程序設(shè)置傳送參數(shù)數(shù)據(jù)傳送前由DMA控制器請(qǐng)求總線使用權(quán)□.數(shù)據(jù)傳送由DMA控制器直接控制總線完成DMA傳送結(jié)束后的處理由中斷服務(wù)程序完成A.僅I、□B.僅口、口、口C.僅口、口、IVD?I、口、口、IV

下列關(guān)于線程的描述中，錯(cuò)誤的是內(nèi)核級(jí)線程的調(diào)度由操作系統(tǒng)完成操作系統(tǒng)為每個(gè)用戶級(jí)線程建立一個(gè)線程控制塊用戶級(jí)線程間的切換比內(nèi)核級(jí)線程間的切換效率高用戶級(jí)線程可以在不支持內(nèi)核級(jí)線程的操作系統(tǒng)上實(shí)現(xiàn)下列選項(xiàng)中，可能將進(jìn)程喚醒的事件是i.i/o結(jié)束□.某進(jìn)程退出臨界區(qū)m.當(dāng)前進(jìn)程的時(shí)間片用完A.僅IB.僅口C.僅I、□D.I、口、□下列關(guān)于系統(tǒng)調(diào)用的敘述中，正確的是I.在執(zhí)行系統(tǒng)調(diào)用服務(wù)程序的過(guò)程中，CPU處于內(nèi)核態(tài).操作系統(tǒng)通過(guò)提供系統(tǒng)調(diào)用避免用戶程序直接訪問(wèn)外設(shè).不同的操作系統(tǒng)為應(yīng)用程序提供了統(tǒng)一的系統(tǒng)調(diào)用接口IV.系統(tǒng)調(diào)用是操作系統(tǒng)內(nèi)核為應(yīng)用程序提供服務(wù)的接口A.僅I、IVB.僅II、IIIC.僅I、□、IVD.僅I、口、口下列選項(xiàng)中，可用于文件系統(tǒng)管理空閑磁盤(pán)塊的數(shù)據(jù)結(jié)構(gòu)是I.位圖□.索引節(jié)點(diǎn)m.空閑磁盤(pán)塊鏈□.文件分配表（FAT）A.僅I、□B.僅口、口、口C.僅1、口D.僅口、口、□系統(tǒng)采用二級(jí)反饋隊(duì)列調(diào)度算法進(jìn)行進(jìn)程調(diào)度。就緒隊(duì)列Q1采用時(shí)間片輪轉(zhuǎn)調(diào)度算法，時(shí)間片為10ms；就緒隊(duì)列Q2采用短進(jìn)程優(yōu)先調(diào)度算法；系統(tǒng)優(yōu)先調(diào)度Q1隊(duì)列中的進(jìn)程，當(dāng)Q1為空時(shí)系統(tǒng)才會(huì)調(diào)度Q2中的進(jìn)程；新創(chuàng)建的進(jìn)程首先進(jìn)入Q1；Q1中的進(jìn)程執(zhí)行一個(gè)時(shí)間片后，若未結(jié)束，則轉(zhuǎn)入Q2。若當(dāng)前Q1、Q2為空，系統(tǒng)依次創(chuàng)建進(jìn)程Pl、P2后即開(kāi)始進(jìn)程調(diào)度Pl、P2需要的CPU時(shí)間分別為30ms和20ms，貝9進(jìn)程P1、P2在系統(tǒng)中的平均等待時(shí)間為A.25msB.20msC.15msD.10ms在分段存儲(chǔ)管理系統(tǒng)中，用共享段表描述所有被共享的段。若進(jìn)程P1和P2共享段S，下列敘述中，錯(cuò)誤的是在物理內(nèi)存中僅保存一份段S的內(nèi)容段S在P1和P2中應(yīng)該具有相同的段號(hào)P1和P2共享段S在共享段表中的段表項(xiàng)P1和P2都不再使用段S時(shí)才回收段S所占的內(nèi)存空間某系統(tǒng)采用LRU頁(yè)置換算法和局部置換策略，若系統(tǒng)為進(jìn)程P預(yù)分配了某系統(tǒng)采用LRU頁(yè)置換算法和局部置換策略，若系統(tǒng)為進(jìn)程P預(yù)分配了4個(gè)頁(yè)框，進(jìn)程P訪問(wèn)頁(yè)號(hào)的序列為0，1，2，7，0，5，3，5，0，2，7，6,則進(jìn)程訪問(wèn)上述頁(yè)的過(guò)程中，產(chǎn)生頁(yè)置換的總次數(shù)是A.3B.4C.5D.6下列關(guān)于死鎖的敘述中，正確的是可以通過(guò)剝奪進(jìn)程資源解除死鎖死鎖的預(yù)防方法能確保系統(tǒng)不發(fā)生死鎖銀行家算法可以判斷系統(tǒng)是否處于死鎖狀態(tài)口.當(dāng)系統(tǒng)出現(xiàn)死鎖時(shí)，必然有兩個(gè)或兩個(gè)以上的進(jìn)程處于阻塞態(tài)A.僅II、口B.僅I、口、口C.僅I、口、口D.僅I、口、口某計(jì)算機(jī)主存按字節(jié)編址，采用二級(jí)分頁(yè)存儲(chǔ)管理，地址結(jié)構(gòu)如下所示頁(yè)目錄號(hào)（10位）頁(yè)號(hào)（10位）頁(yè)內(nèi)偏移（12位）虛擬地址20501225H對(duì)應(yīng)的頁(yè)目錄號(hào)、頁(yè)號(hào)分別是A.081H、101H081H、401H201H、101H201H、401HD.循環(huán)首次適應(yīng)算法D.數(shù)據(jù)表示轉(zhuǎn)換D.D.循環(huán)首次適應(yīng)算法D.數(shù)據(jù)表示轉(zhuǎn)換D.同軸電纜發(fā)送窗口大小為5,則接收窗口最大是A.首次適應(yīng)算法B.最壞適應(yīng)算法C.最佳適應(yīng)算法OSI參考模型的第5層（自下而上）完成的主要功能是A.差錯(cuò)控制B.路由選擇C.會(huì)話管理100BaseT快速以太網(wǎng)使用的導(dǎo)向傳輸介質(zhì)是A.雙絞線B.單模光纖C.多模光纖對(duì)于滑動(dòng)窗口協(xié)議，如果分組序號(hào)采用3比特編號(hào)，A.2B.3C.4D.5假設(shè)一個(gè)采用CSMA/CD協(xié)議的100Mbps局域網(wǎng)，最小幀長(zhǎng)是128B,則在一個(gè)沖突域內(nèi)兩個(gè)站點(diǎn)之間的單向傳播延時(shí)最多是A.2.56四B.5.12四C.10.24gsD.20.48gs若將101.200.16.0/20劃分為5個(gè)子網(wǎng)，則可能的最小子網(wǎng)的可分配IP地址數(shù)是題38圖D.1022A.126B.254C.510某客戶通過(guò)一個(gè)TCP連接向服務(wù)器發(fā)送數(shù)據(jù)的部分過(guò)程如題38圖所示?？蛻粼趖0時(shí)刻第一次收到確認(rèn)序列號(hào)ack_seq=100的段，并發(fā)送序列號(hào)seq=100的段，但發(fā)生丟失。若TCP支持快速重傳，則客戶重新發(fā)送seq=100段的時(shí)刻是題38圖D.1022A.JB.t2C.t3D.t4若主機(jī)甲主動(dòng)發(fā)起一個(gè)與主機(jī)乙的TCP連接，甲、乙選擇的初始序列號(hào)分別為2018和2046，則第三次握手TCP段的確認(rèn)序列號(hào)是A.2018B.2019C.2046D.2047下列關(guān)于網(wǎng)絡(luò)應(yīng)用模型的敘述中，錯(cuò)誤的是在P2P模型中，結(jié)點(diǎn)之間具有對(duì)等關(guān)系在客戶/服務(wù)器(C/S)模型中，客戶與客戶之間可以直接通信在C/S模型中，主動(dòng)發(fā)起通信的是客戶，被動(dòng)通信的是服務(wù)器在向多用戶分發(fā)一個(gè)文件時(shí)，P2P模型通常比C/S模型所需時(shí)間短二、綜合應(yīng)用題：41~47小題，共70分。(13分)設(shè)線性表L=(a1，a2,a...，an-2,a-1，a。)采用帶頭結(jié)點(diǎn)的單鏈表保存，鏈表中結(jié)點(diǎn)定義如下：typedefstructnode(intdata；structnode*next；}NODE；請(qǐng)?jiān)O(shè)計(jì)一個(gè)空間復(fù)雜度為O(1)且時(shí)間上盡可能高效的算法，重新排列L中的各結(jié)點(diǎn)，得到線性表L'=(a1，an，a2，an-1，電，"…"要求：給出算法的基本設(shè)計(jì)思想根據(jù)設(shè)計(jì)思想，采用C或C++語(yǔ)言描述算法，關(guān)鍵之處給出注釋。說(shuō)明你所設(shè)計(jì)的算法的時(shí)間復(fù)雜度。(10分)請(qǐng)?jiān)O(shè)計(jì)一個(gè)隊(duì)列，要求滿足：①初始時(shí)隊(duì)列為空；②入隊(duì)時(shí)，允許增加隊(duì)列占用空間；③出隊(duì)后，出隊(duì)元素所占用的空間可重復(fù)使用，即整個(gè)隊(duì)列所占用的空間只增不減；④人隊(duì)操作和出隊(duì)操作的時(shí)間復(fù)雜度始終保持為0(1)。請(qǐng)回答下列問(wèn)題：該隊(duì)列應(yīng)該選擇鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，還是順序存儲(chǔ)結(jié)構(gòu)？畫(huà)出隊(duì)列的初始狀態(tài)，并給出判斷隊(duì)空和隊(duì)滿的條件畫(huà)出第一個(gè)元素入隊(duì)后的隊(duì)列狀態(tài)。給出入隊(duì)操作和出隊(duì)操作的基本過(guò)程。(8分)有n(n>3)位哲學(xué)家圍坐在一張圓桌邊，每位哲學(xué)家交替地就餐和思考。在圓桌中心有m(m>1)個(gè)碗，每?jī)晌徽軐W(xué)家之間有1根筷子。每位哲學(xué)家必須取到一個(gè)碗和兩側(cè)的筷子之后，才能就餐，進(jìn)餐完畢，將碗和筷子放回原位，并繼續(xù)思考。為使盡可能多的哲學(xué)家同時(shí)就餐，且防止出現(xiàn)死鎖現(xiàn)象，請(qǐng)使用信號(hào)量的P、V操作(wait()、signal()操作)描述上述過(guò)程中的互斥與同步，并說(shuō)明所用信號(hào)量及初值的含義。(7分)某計(jì)算機(jī)系統(tǒng)中的磁盤(pán)有300個(gè)柱面，每個(gè)柱面有10個(gè)磁道，每個(gè)磁道有200個(gè)扇區(qū)，扇區(qū)大小為512B。文件系統(tǒng)的每個(gè)簇包含2個(gè)扇區(qū)。請(qǐng)回答下列問(wèn)題：磁盤(pán)的容量是多少？假設(shè)磁頭在85號(hào)柱面上，此時(shí)有4個(gè)磁盤(pán)訪問(wèn)請(qǐng)求，簇號(hào)分別為：100260、60005、101660和110560。若采用最短尋道時(shí)間優(yōu)先(SSTF)調(diào)度算法，則系統(tǒng)訪問(wèn)簇的先后次序是什么？第100530簇在磁盤(pán)上的物理地址是什么？將簇號(hào)轉(zhuǎn)換成磁盤(pán)物理地址的過(guò)程是由I/O系統(tǒng)的什么程

序完成的？45.(16分)已知f(n)=n!=nx(n-l)x(n-2)x...x2x1,計(jì)算f(n)的C語(yǔ)言函數(shù)fl的源程序(陰影部分)及其在32位計(jì)算機(jī)M上的部分機(jī)器級(jí)代碼如下：45.inLri(Juln)II004(1100055push?1>P110040I01S83110040I01S83m脾diCinjjdwirirdI'Lrebp*8],1120040I0IC*17睥t\+35h(0040ICIJ5)returnn/fl(n-l)；U0040ICME8B4508fiiJwririlp<r[cl-*P+81400401021S3EB1)1仁踮,IIS00401024501600401015ESD6FFKRFF函IIf](00401000)IQ0040IQ3OOFAPCtiikiuleaxiek20(SCM(J1033Eli05jmpfl+3Ah(0040103a)elwrctuni3a21cmoioas0100QG00mrs*eaK,12600401040ECCJ^Ipcbp*p6J7|fl300040104A￡3fri其中，機(jī)器級(jí)代碼行包括行號(hào)、虛擬地址、機(jī)器指令和匯編指令，計(jì)算機(jī)M按字節(jié)編址，int型數(shù)據(jù)占32位。請(qǐng)回答下列問(wèn)題：計(jì)算f(10)需要調(diào)用函數(shù)fl多少次？執(zhí)行哪條指令會(huì)遞歸調(diào)用fl？上述代碼中，哪條指令是條件轉(zhuǎn)移指令？哪幾條指令一定會(huì)使程序跳轉(zhuǎn)執(zhí)行？根據(jù)第16行call指令，第17行指令的虛擬地址應(yīng)是多少？已知第16行call指令采用相對(duì)尋址方式，該指令中的偏移量應(yīng)是多少(給出計(jì)算過(guò)程)？已知第16行call指令的后4字節(jié)為偏移量，M采用大端還是小端方式？f(13)=6227020800但f1(13)的返回值為1932053504為什么兩者不相等？要使f1(13)能返回正確的結(jié)果，應(yīng)如何修改f1源程序？第19行imuleax,ecx表示有符號(hào)數(shù)乘法，乘數(shù)為R[eax]和R[ecx]，當(dāng)乘法器輸出的高、低32位乘積之間滿足什么條件時(shí)，溢出標(biāo)志OF=1？要使CPU在發(fā)生溢出時(shí)轉(zhuǎn)異常處理，編譯器應(yīng)在imul指令后加一條什么指令？(7分)對(duì)于題45,若計(jì)算機(jī)M的主存地址為32位，采用分頁(yè)存儲(chǔ)管理方式，頁(yè)大小為4KB，則第1行push指令和第30行ret指令是否在同一頁(yè)中(說(shuō)明理由)？若指令Cache有64行，采用4路組相聯(lián)映射方式，主存塊大小為64B，則32位主存地址中，哪幾位表示塊內(nèi)地址？哪兒位表示Cache組號(hào)？哪幾位表示標(biāo)記(tag)信息？讀取第16行call指令時(shí)，只可能在指令Cache的哪一組中命中(說(shuō)明理由)？(9分)某網(wǎng)絡(luò)拓?fù)淙珙}47圖所示，其中R為路由器，主機(jī)H1?H4的IP地址配置以及R的各接口IP地址配置如圖中所示。現(xiàn)有若干臺(tái)以太網(wǎng)交換機(jī)(無(wú)VLAN功能)和路由器兩類(lèi)網(wǎng)絡(luò)互連設(shè)備可供選擇。請(qǐng)回答下列問(wèn)題：設(shè)備1、設(shè)備2和設(shè)備3分別應(yīng)選擇什么類(lèi)型網(wǎng)絡(luò)設(shè)備？⑵設(shè)備1、設(shè)備2和設(shè)備3中，哪幾個(gè)設(shè)備的接口需要配置IP地址？并為對(duì)應(yīng)的接口配置正確的IP地址。(3)為確保主機(jī)H1?H4能夠訪問(wèn)Internet，R需要提供什么服務(wù)？⑷若主機(jī)H3發(fā)送一個(gè)目的地址為192.168.1.127的IP數(shù)據(jù)報(bào)，網(wǎng)絡(luò)中哪幾個(gè)主機(jī)會(huì)接收該數(shù)據(jù)報(bào)？

2019年全國(guó)碩士研究生招生考試計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合試題參考答案1.B2.B3.C4.A5.C6.A7.D1.B2.B3.C4.A5.C6.A7.D8.C9.B10.D11.B12.C13.A14.D15.D16.D17.B18.C19.B20.C21.A22.D23.B24.C25.C26.B27.C28.B29.C30.B31.A32.C33.C34.A35.B36.B37.B38.C39.D40.B一、單項(xiàng)選擇題采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(兩段式單向循環(huán)鏈表)，隊(duì)頭指針為front，隊(duì)尾指針為rear。初始時(shí)，創(chuàng)建只有一個(gè)空閑結(jié)點(diǎn)的兩段式單向循環(huán)鏈表，頭指針front與尾指針rear均指向空閑結(jié)點(diǎn)。如下二、綜合應(yīng)用題【答案要點(diǎn)】算法的基本設(shè)計(jì)思想：算法分3步完成。第1步，采用兩個(gè)指針交替前行，找到單鏈表的中間結(jié)點(diǎn)；第2步，將單鏈表的后半段結(jié)點(diǎn)原地逆置；第3步，從單鏈表前后兩段中依次各取一個(gè)結(jié)點(diǎn)，按要求重排。算法實(shí)現(xiàn)：midNODE*h)INODE+p,*q.*T,掌虻p.q=h.while{qfgd!=MULL}//手援中同培點(diǎn)Ip=走—步q=if(q->nnxlJ■NULL)q=//q走期步Iq=p所措■￡&弗為中何拈盤(pán)Z北舊'F段鏈表的首細(xì)點(diǎn)p->n<*xl=NULL：whjlK(q!=NULL)//將tif溟啟半度逆置Ir—q-\sif-;p->iiexl=q-r：K=h-》w舛打K榕舛MTEt的第一1■敷壁結(jié).Pi,UllWtAA弓=[irmL；〃q指皿后華成的第一十敝旭培點(diǎn)p-K呻"=NULL；whikiqI=NULLj〃將憂徑后年段的站點(diǎn)抽人到指定位置|raqrgjd；//「檎向后牛段的下一個(gè)皓點(diǎn)qpXnE-&->fliexE:〃將q所指站點(diǎn)抽入到稿所指堵成之后,n=q->neKn//，指晰誨半段的下一個(gè)哺人點(diǎn)算法的時(shí)間復(fù)雜度：參考答案的時(shí)間復(fù)雜度為O(n)。隊(duì)空的判定條件：front==rear。隊(duì)滿的判定條件：front==rear->next。插入第一個(gè)元素后的隊(duì)列狀態(tài)：操作的基本過(guò)程:人瓦操也北(frmil==rtdr—iUftit)//甌讖用在質(zhì)；1「瓦?回臆人一個(gè)新的空卬埔點(diǎn)；人1從元度促有到村如所店結(jié)點(diǎn)中；計(jì)小=『頒-Mem返回捎成n作,若[front-=倒『)//所空期出職*■.或回;耿Rg所布薯就中浦元素cjmnt*0tL【答案要點(diǎn)】〃信號(hào)量semaphorebowl；//用于協(xié)調(diào)哲學(xué)家對(duì)碗的使用semaphorechopsticks[n]；//用于協(xié)調(diào)哲學(xué)家對(duì)筷子的使用for(inti=0；i<n；i++)chopsticks[i].value=1；//設(shè)置兩個(gè)哲學(xué)家之間筷子的數(shù)量bowl.value=min(n-1，m)；//bowl.valueWn-1，確保不死鎖CoBeginwhile(True)(//哲學(xué)家i的程序思考；P(bowl)；//取碗P(chopsticks[i])；〃取左邊筷子P(chopsticks[(i+l)MODn])；//取右邊筷子就餐；(chopsticks[i])；(chopsticks[(i+1)MODn])；V(bowl)；}CoEnd【答案要點(diǎn)】磁盤(pán)容量=(300x10x200x512/1024)KB=3x105KB依次訪問(wèn)的簇是100260、101660、110560、60005。第100530簇在磁盤(pán)上的物理地址由其所在的柱面號(hào)、磁頭號(hào)、扇區(qū)號(hào)構(gòu)成其所在的柱面號(hào)為[100530/(10x200/2)[=100。100530%(10x200/2)=530，磁頭號(hào)為[530/(200/2)[=5。扇區(qū)號(hào)為(530x2)%200=60。將簇號(hào)轉(zhuǎn)換成磁盤(pán)物理地址的過(guò)程由磁盤(pán)驅(qū)動(dòng)程序完成?！敬鸢敢c(diǎn)】計(jì)算f(l0)需要調(diào)用函數(shù)f1共10次執(zhí)行第16行ca