2019年全國碩士研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考

2019年全國碩士研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題一、單項(xiàng)選擇題(第1~40小題，每小題2分，共80分。下列每題給出的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)最符合試題要求)1．設(shè)n是描述問題規(guī)模的非負(fù)整數(shù)，下列程序段的時(shí)間復(fù)雜度是。 x=0; whilenxx x=x+1;A．O(logn)B．O(n1/2)C．O(n)D．O(n2)2．若將一棵樹T轉(zhuǎn)化為對應(yīng)的二叉樹BT，則下列對BT的遍歷中，其遍歷序列與T的后根遍歷序列相同的是。A．先序遍歷B．中序遍歷C．后序遍歷D．按層遍歷3．對n個(gè)互不相同的符號進(jìn)行哈夫曼編碼。若生成的哈夫曼樹共有115個(gè)結(jié)點(diǎn)，則n的值是。是AB．57C．58D．604．在任意一棵非空平衡二叉樹(AVL樹)T1中，刪除某結(jié)點(diǎn)v之后形成平衡二叉樹T2，再將v插入T2形成平衡二叉樹T3。下列關(guān)于T1與T3的敘述中，正確的是。II．若v不是T1的葉結(jié)點(diǎn)，則T1與T3一定不相同III．若v不是T1的葉結(jié)點(diǎn)，則T1與T3一定相同5．下圖所示的AOE網(wǎng)表示一項(xiàng)包含8個(gè)活動(dòng)的工程?；顒?dòng)d的最早開始時(shí)間和最遲開始時(shí)間分別是。6．用有向無環(huán)圖描述表達(dá)式(x+y)((x+y)/x)，需要的頂點(diǎn)個(gè)數(shù)至少是。ABC．8D．97．選擇一個(gè)排序算法時(shí)，除算法的時(shí)空效率，下列因素中，還需要考慮的是。I．?dāng)?shù)據(jù)的規(guī)模II．?dāng)?shù)據(jù)的存儲方式III．算法的穩(wěn)定性IV．?dāng)?shù)據(jù)的初始狀態(tài)8．現(xiàn)有長度為11且初始為空的散列表HT，散列函數(shù)是H(key)=key%7，采用線性探查 (線性探測再散列)法解決沖突。將關(guān)鍵字序列87,40,30,6,11,22,98,20依次插入HT后，HT查找失敗的平均查找長度是。A．4B．5.25C．6D．6.299．設(shè)主串T="abaabaabcabaabc"，模式串S="abaabc"，采用KMP算法進(jìn)行模式匹配，到匹配成功時(shí)為止，在匹配過程中進(jìn)行的單個(gè)字符間的比較次數(shù)是。ABC．12D．1510．排序過程中，對尚未確定最終位置的所有元素進(jìn)行一遍處理稱為一“趟”。下列序列中，不可能是快速排序第二趟結(jié)果的是。A．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,6011．設(shè)外存上有120個(gè)初始?xì)w并段，進(jìn)行12路歸并時(shí)，為實(shí)現(xiàn)最佳歸并，需要補(bǔ)充的虛段個(gè)數(shù)是。12．下列關(guān)于馮·諾依曼結(jié)構(gòu)計(jì)算機(jī)基本思想的敘述中，錯(cuò)誤的是。A．程序的功能都通過中央處理器執(zhí)行指令實(shí)現(xiàn)B．指令和數(shù)據(jù)都用二進(jìn)制數(shù)表示，形式上無差別C．指令按地址訪問，數(shù)據(jù)都在指令中直接給出D．程序執(zhí)行前，指令和數(shù)據(jù)需預(yù)先存放在存儲器中13．考慮以下C語言代碼：unsignedunsignedshortusi=65535;shortsi=usi;執(zhí)行上述程序段后，si的值是。A．-1B．-32767C．-32768D．-6553514．下列關(guān)于缺頁處理的敘述中，錯(cuò)誤的是。A．缺頁是在地址轉(zhuǎn)換時(shí)CPU檢測到的一種異常B．缺頁處理由操作系統(tǒng)提供的缺頁處理程序來完成C．缺頁處理程序根據(jù)頁故障地址從外存讀入所缺失的頁D．缺頁處理完成后回到發(fā)生缺頁的指令的下一條指令執(zhí)行15．某計(jì)算機(jī)采用大端方式，按字節(jié)編址。某指令中操作數(shù)的機(jī)器數(shù)為1234FF00H，該操作數(shù)采用基址尋址方式，形式地址(用補(bǔ)碼表示)為FF12H，基址寄存器的內(nèi)容為F0000000H，則該操作數(shù)的LSB(最低有效字節(jié))所在的地址是。A．F000FF12HB．F000FF15HC．EFFFFF12HD．EFFFFF15H16．下列有關(guān)處理器時(shí)鐘脈沖信號的敘述中，錯(cuò)誤的是。A．時(shí)鐘脈沖信號由機(jī)器脈沖源發(fā)出的脈沖信號經(jīng)整形和分頻后形成B．時(shí)鐘脈沖信號的寬度稱為時(shí)鐘周期，時(shí)鐘周期的倒數(shù)為機(jī)器主頻C．時(shí)鐘周期以相鄰狀態(tài)單元間組合邏輯電路的最大延遲為基準(zhǔn)確定D．處理器總是在每來一個(gè)時(shí)鐘脈沖信號時(shí)就開始執(zhí)行一條新的指令17．某指令功能為R[r2]←R[r1]+M[R[r0]]，其兩個(gè)源操作數(shù)分別采用寄存器、寄存器間接尋址方式。對于下列給定部件，該指令在取數(shù)及執(zhí)行過程中需要用到的是。I．通用寄存器組(GPRs)II．算術(shù)邏輯單元(ALU)2019年全國碩士研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題III．存儲器(Memory)IV．指令譯碼器(ID)18．在采用“取指、譯碼/取數(shù)、執(zhí)行、訪存、寫回”5段流水線的處理器中，執(zhí)行如下指sssst寄存器編號。II1：adds2,s1,s0I3：adds2,s2,s3t下列指令對中，不存在數(shù)據(jù)冒險(xiǎn)的是。AIIBIICIID．I3和I419．假定一臺計(jì)算機(jī)采用3通道存儲器總線，配套的內(nèi)存條型號為DDR3-1333，即內(nèi)存條所接插的存儲器總線的工作頻率為1333MHz，總線寬度為64位，則存儲器總線的總帶寬大約是。A．10.66GB/sB．32GB/sC．64GB/sD．96GB/s20．下列關(guān)于磁盤存儲器的敘述中，錯(cuò)誤的是。A．磁盤的格式化容量比非格式化容量小B．扇區(qū)中包含數(shù)據(jù)、地址和校驗(yàn)等信息C．磁盤存儲器的最小讀寫單位為一字節(jié)D．磁盤存儲器由磁盤控制器、磁盤驅(qū)動(dòng)器和盤片組成21．某設(shè)備以中斷方式與CPU進(jìn)行數(shù)據(jù)交換，CPU主頻為1GHz，設(shè)備接口中的數(shù)據(jù)緩沖寄存器為32位，設(shè)備的數(shù)據(jù)傳輸率為50kB/s。若每次中斷開銷(包括中斷響應(yīng)和中斷處理)為1000個(gè)時(shí)鐘周期，則CPU用于該設(shè)備輸入/輸出的時(shí)間占整個(gè)CPU時(shí)間的百分比最多是。A．1.25%B．2.5%C．5%D．12.5%22．下列關(guān)于DMA方式的敘述中，正確的是。I．DMA傳送前由設(shè)備驅(qū)動(dòng)程序設(shè)置傳送參數(shù)II．?dāng)?shù)據(jù)傳送前由DMA控制器請求總線使用權(quán)III．?dāng)?shù)據(jù)傳送由DMA控制器直接控制總線完成IV．DMA傳送結(jié)束后的處理由中斷服務(wù)程序完成23．下列關(guān)于線程的描述中，錯(cuò)誤的是。A．內(nèi)核級線程的調(diào)度由操作系統(tǒng)完成B．操作系統(tǒng)為每個(gè)用戶級線程建立一個(gè)線程控制塊C．用戶級線程間的切換比內(nèi)核級線程間的切換效率高D．用戶級線程可以在不支持內(nèi)核級線程的操作系統(tǒng)上實(shí)現(xiàn)24．下列選項(xiàng)中，可能會將進(jìn)程喚醒的事件是。I．I/O結(jié)束II．某進(jìn)程退出臨界區(qū)III．當(dāng)前進(jìn)程的時(shí)間片用完II25．下列關(guān)于系統(tǒng)調(diào)用的敘述中，正確的是。I．在執(zhí)行系統(tǒng)調(diào)用服務(wù)程序的過程中，CPU處于內(nèi)核態(tài)II．操作系統(tǒng)通過提供系統(tǒng)調(diào)用避免用戶程序直接訪問外設(shè)III．不同的操作系統(tǒng)為應(yīng)用程序提供了統(tǒng)一的系統(tǒng)調(diào)用接口IV．系統(tǒng)調(diào)用是操作系統(tǒng)內(nèi)核為應(yīng)用程序提供服務(wù)的接口26.下列選項(xiàng)中，可用于文件系統(tǒng)管理空閑磁盤塊的數(shù)據(jù)結(jié)構(gòu)是。I．位圖II．索引結(jié)點(diǎn)III．空閑磁盤塊鏈IV．文件分配表(FAT)27．系統(tǒng)采用二級反饋隊(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)才會調(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)程P1、P2后即開始進(jìn)程調(diào)度，P1、P2需要的CPU時(shí)間分別為30ms和20ms，則進(jìn)程P1、P2在系統(tǒng)中的平均等待時(shí)間為。A．25msB．20msC．15msD．10ms28．在分段存儲管理系統(tǒng)中，用共享段表描述所有被共享的段。若進(jìn)程P1和P2共享段S，下列敘述中，錯(cuò)誤的是。A．在物理內(nèi)存中僅保存一份段S的內(nèi)容BSP和P2中應(yīng)該具有相同的段號C．P1和P2共享段S在共享段表中的段表項(xiàng)D．P1和P2都不再使用段S時(shí)才回收段S所占的內(nèi)存空間29．某系統(tǒng)釆用LRU頁置換算法和局部置換策略，若系統(tǒng)為進(jìn)程P預(yù)分配了4個(gè)頁框，進(jìn)程P訪問頁號的序列為0,1,2,7,0,5,3,5,0,2,7,6，則進(jìn)程訪問上述頁的過程中，產(chǎn)生頁置換的總次數(shù)是。ABC．5D．630．下列關(guān)于死鎖的敘述中，正確的是。I．可以通過剝奪進(jìn)程資源解除死鎖II．死鎖的預(yù)防方法能確保系統(tǒng)不發(fā)生死鎖III．銀行家算法可以判斷系統(tǒng)是否處于死鎖狀態(tài)IV．當(dāng)系統(tǒng)出現(xiàn)死鎖時(shí)，必然有兩個(gè)或兩個(gè)以上的進(jìn)程處于阻塞態(tài)31．某計(jì)算機(jī)主存按字節(jié)編址，采用二級分頁存儲管理，地址結(jié)構(gòu)如下所示：頁目錄號(10位)頁號(10位)頁內(nèi)偏移(12位)虛擬地址20501225H對應(yīng)的頁目錄號、頁號分別是。AHHBHHCHHD01H、401H32．在下列動(dòng)態(tài)分區(qū)分配算法中，最容易產(chǎn)生內(nèi)存碎片的是。A．首次適應(yīng)算法B．最壞適應(yīng)算法C．最佳適應(yīng)算法D．循環(huán)首次適應(yīng)算法33．OSI參考模型的第5層(自下而上)完成的主要功能是。A．差錯(cuò)控制B．路由選擇C．會話管理D．?dāng)?shù)據(jù)表示轉(zhuǎn)換34．100BaseT快速以太網(wǎng)使用的導(dǎo)向傳輸介質(zhì)是。A．雙絞線B．單模光纖C．多模光纖D．同軸電纜2019年全國碩士研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題35．對于滑動(dòng)窗口協(xié)議，若分組序號采用3比特編號，發(fā)送窗口大小為5，則接收窗口最大是。ABC．4D．536．假設(shè)一個(gè)采用CSMA/CD協(xié)議的10Mb/s局域網(wǎng)，最小幀長是128B，則在一個(gè)沖突域內(nèi)兩個(gè)站點(diǎn)之間的單向傳播延時(shí)最多是。A．2.56μsB．5.12μsC．10.24μsD．20.48μs16.0/20劃分為5個(gè)子網(wǎng)，則可能的最小子網(wǎng)的可分配IP地址數(shù)是。A．126B．254C．510D．102238．某客戶通過一個(gè)TCP連接向服務(wù)器發(fā)送數(shù)據(jù)的部分過程如題38圖所示。客戶在t0時(shí)刻第一次收到確認(rèn)序列號ack_seq=100的段，并發(fā)送序列號seq=100的段，但發(fā)生丟失。若TCP支持快速重傳，則客戶重新發(fā)送seq=100段的時(shí)刻是。AtBtC．t3D．t438圖39．若主機(jī)甲主動(dòng)發(fā)起一個(gè)與主機(jī)乙的TCP連接，甲、乙選擇的初始序列號分別為2018和2046，則第三次握手TCP段的確認(rèn)序列號是。A．2018B．2019C．2046D．204740．下列關(guān)于網(wǎng)絡(luò)應(yīng)用模型的敘述中，錯(cuò)誤的是。A．在P2P模型中，結(jié)點(diǎn)之間具有對等關(guān)系B．在客戶/服務(wù)器(C/S)模型中，客戶與客戶之間可以直接通信C．在C/S模型中，主動(dòng)發(fā)起通信的是客戶，被動(dòng)通信的是服務(wù)器D．在向多用戶分發(fā)一個(gè)文件時(shí)，P2P模型通常比C/S模型所需的時(shí)間短二、綜合應(yīng)用題(第41~47小題，共70分)Laaaanan,an)采用帶頭結(jié)點(diǎn)的單鏈表保存，鏈表中的結(jié)點(diǎn)定義如下：typedeftypedefstructnode{{intdata;structnode*next;}NODE；請?jiān)O(shè)計(jì)一個(gè)空間復(fù)雜度為O(1)且時(shí)間上盡可能高效的算法，重新排列L中的各結(jié)點(diǎn)，得到(1)給出算法的基本設(shè)計(jì)思想。(2)根據(jù)設(shè)計(jì)思想，采用C或C++語言描述算法，關(guān)鍵之處給出注釋。(3)說明你所設(shè)計(jì)的算法的時(shí)間復(fù)雜度。42．(10分)請?jiān)O(shè)計(jì)一個(gè)隊(duì)列，要求滿足：①初始時(shí)隊(duì)列為空；②入隊(duì)時(shí)，允許增加隊(duì)列占用空間；③出隊(duì)后，出隊(duì)元素所占用的空間可重復(fù)使用，即整個(gè)隊(duì)列所占用的空間只增不減；④入隊(duì)操作和出隊(duì)操作的時(shí)間復(fù)雜度始終保持為O(1)。請回答下列問題：(1)該隊(duì)列是應(yīng)選擇鏈?zhǔn)酱鎯Y(jié)構(gòu)，還是應(yīng)選擇順序存儲結(jié)構(gòu)？(2)畫出隊(duì)列的初始狀態(tài)，并給出判斷隊(duì)空和隊(duì)滿的條件。(3)畫出第一個(gè)元素入隊(duì)后的隊(duì)列狀態(tài)。(4)給出入隊(duì)操作和出隊(duì)操作的基本過程。43．(8分)有n(n≥3)位哲學(xué)家圍坐在一張圓桌邊，每位哲學(xué)家交替地就餐和思考。在圓桌中心有m(m≥1)個(gè)碗，每兩位哲學(xué)家之間有一根筷子。每位哲學(xué)家必須取到一個(gè)碗和兩側(cè)的筷子后，才能就餐，進(jìn)餐完畢，將碗和筷子放回原位，并繼續(xù)思考。為使盡可能多的哲學(xué)家同時(shí)就餐，且防止出現(xiàn)死鎖現(xiàn)象，請使用信號量的P、V操作[wait()、signal()操作]描述上述過程中的互斥與同步，并說明所用信號量及初值的含義。44．(7分)某計(jì)算機(jī)系統(tǒng)中的磁盤有300個(gè)柱面，每個(gè)柱面有10個(gè)磁道，每個(gè)磁道有200個(gè)扇區(qū)，扇區(qū)大小為512B。文件系統(tǒng)的每個(gè)簇包含2個(gè)扇區(qū)。請回答下列問題：(1)磁盤的容量是多少？(2)假設(shè)磁頭在85號柱面上，此時(shí)有4個(gè)磁盤訪問請求，簇號分別為100260、60005、101660和110560。若采用最短尋道時(shí)間優(yōu)先(SSTF)調(diào)度算法，則系統(tǒng)訪問簇的先后次序是什么？(3)第100530簇在磁盤上的物理地址是什么？將簇號轉(zhuǎn)換成磁盤物理地址的過程是由I/O系統(tǒng)的什么程序完成的？序(陰影部分)及其在32位計(jì)算機(jī)M上的部分機(jī)器級代碼如下：intintf1(intn){10040100055pushebp………1100401018837D0801120040101C7E17cmpjledwordptr[ebp+8],1f1+35h(00401035)returnn*f1(n-1);130040101E140040102115004010241600401025…190040103020004010338B450883E801E8D6FFFFFF…0FAFC1EB05moveax,dwordptr[ebp+8]subeax,1pusheaxcallf1(00401000)…imuleax,ecxjmpf1+3Ah(0040103a)2019年全國碩士研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題elseelsereturn1;2100401035B801000000moveax,1}}…2600401040…300040104A…3BEC…C3…cmpebp,esp…ret其中，機(jī)器級代碼行包括行號、虛擬地址、機(jī)器指令和匯編指令，計(jì)算機(jī)M按字節(jié)編址，int型數(shù)據(jù)占32位。請回答下列問題：(1)計(jì)算f(10)需要調(diào)用函數(shù)f1多少次？執(zhí)行哪條指令會遞歸調(diào)用f1？(2)上述代碼中，哪條指令是條件轉(zhuǎn)移指令？哪幾條指令一定會使程序跳轉(zhuǎn)執(zhí)行？(3)根據(jù)第16行的call指令，第17行指令的虛擬地址應(yīng)是多少？已知第16行的call指令采用相對尋址方式，該指令中的偏移量應(yīng)是多少(給出計(jì)算過程)？已知第16行的call指令的后4字節(jié)為偏移量，M是采用大端方式還是采用小端方式？(4)f(13)=6227020800，但f1(13)的返回值為1932053504，為什么兩者不相等？要使f1(13)能返回正確的結(jié)果，應(yīng)如何修改f1的源程序？(5)第19行的imul指令(帶符號整數(shù)乘)的功能是R[eax]←R[eax]×R[ecx]，當(dāng)乘法器輸出的高、低32位乘積之間滿足什么條件時(shí)，溢出標(biāo)志OF=1？要使CPU在發(fā)生溢出時(shí)轉(zhuǎn)異常處理，編譯器應(yīng)在imul指令后應(yīng)加一條什么指令？46．(7分)對于題45，若計(jì)算機(jī)M的主存地址為32位，釆用分頁存儲管理方式，頁大小KBpush指令和第30行的ret指令是否在同一頁中(說明理由)？若指令Cache有64行，采用4路組相聯(lián)映射方式，主存塊大小為64B，則32位主存地址中，哪幾位表示塊內(nèi)地址？哪幾位表示Cache組號？哪幾位表示標(biāo)記(tag)信息？讀取第16行的call指令時(shí)，只可能在指令Cache的哪一組中命中(說明理由)？47．(9分)某網(wǎng)絡(luò)拓?fù)淙珙}47圖所示，其中R為路由器，主機(jī)H1~H4的IP地址配置以及R的各接口IP地址配置如圖中所示?，F(xiàn)有若干以太網(wǎng)交換機(jī)(無VLAN功能)和路由器兩類網(wǎng)絡(luò)互連設(shè)備可供選擇。47圖請回答下列問題：(1)設(shè)備1、設(shè)備2和設(shè)備3分別應(yīng)選擇什么類型的網(wǎng)絡(luò)設(shè)備？(2)設(shè)備1、設(shè)備2和設(shè)備3中，哪幾個(gè)設(shè)備的接口需要配置IP地址？為對應(yīng)的接口配置正確的IP地址。(3)為確保主機(jī)H1~H4能夠訪問Internet，R需要提供什么服務(wù)？(4)若主機(jī)H3發(fā)送一個(gè)目的地址為192.168.1.127的IP數(shù)據(jù)報(bào)，網(wǎng)絡(luò)中哪幾個(gè)主機(jī)會接收該數(shù)據(jù)報(bào)？2019年計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題參考答案一、單項(xiàng)選擇題C41．解答：1)算法的基本設(shè)計(jì)思想：取第一個(gè)元素，再摘取倒數(shù)第一個(gè)元素……依次合并而成的。為了方便鏈表后半段取元素，需要先將L后半段原地逆置[題目要求空間復(fù)雜度為O(1)，不能借助棧]，否則每取最后一個(gè)結(jié)點(diǎn)都需要遍歷一次鏈表。①先找出鏈表L的中間結(jié)點(diǎn)，為此設(shè)置兩個(gè)指針p和q，指針p每次走一步，指針q每次走兩步，當(dāng)指針q到達(dá)鏈尾時(shí)，指針p正好在鏈表的中間結(jié)點(diǎn)；②然后將L的后半段結(jié)點(diǎn)原地逆置。③從單鏈表前后兩段中依次各取一個(gè)結(jié)點(diǎn)，按要求重排。2)算法實(shí)現(xiàn)：voidvoidchange_list(NODE*h){NODE*p,*q,*r,*s;p=q=h;while(q->next!=NULL)//尋找中間結(jié)點(diǎn){p=p->next;//p走一步q=q->next;ifqnextNULLq=q->next;//q走兩步}q=p->next;//p所指結(jié)點(diǎn)為中間結(jié)點(diǎn)，q為后半段鏈表的首結(jié)點(diǎn)p->next=NULL;while(q!=NULL)//將鏈表后半段逆置{r=q->next;2019年全國碩士研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題qq->next=p->next;p->next=q;q=r;}s=h->next;q=p->next;p->next=NULL;{r=q->next;q->next=s->next;s->next=q;s=q->next;q=r;}}//s指向前半段的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)，即插入點(diǎn)//q指向后半段的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)//將鏈表后半段的結(jié)點(diǎn)插入到指定位置//r指向后半段的下一個(gè)結(jié)點(diǎn)//s指向前半段的下一個(gè)插入點(diǎn)3)第1步找中間結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(n)，第2步逆置的時(shí)間復(fù)雜度為O(n)，第3步合并鏈表的時(shí)間復(fù)雜度為O(n)，所以該算法的時(shí)間復(fù)雜度為O(n)。42．解答：1)順序存儲無法滿足要求②的隊(duì)列占用空間隨著入隊(duì)操作而增加。根據(jù)要求來分析：要求①容易滿足；鏈?zhǔn)酱鎯Ψ奖汩_辟新空間，要求②容易滿足；對于要求③，出隊(duì)后的結(jié)點(diǎn)并不真正釋放，用隊(duì)頭指針指向新的隊(duì)頭結(jié)點(diǎn)，新元素入隊(duì)時(shí)，有空余結(jié)點(diǎn)則無須開辟新空間，賦值到隊(duì)尾后的第一個(gè)空結(jié)點(diǎn)即可，然后用隊(duì)尾指針指向新的隊(duì)尾結(jié)點(diǎn)，這就需要設(shè)計(jì)成一個(gè)首尾相接的循環(huán)單鏈表，類似于循環(huán)隊(duì)列的思想。設(shè)置隊(duì)頭、隊(duì)尾指針后，鏈?zhǔn)疥?duì)列的入隊(duì)操作和出隊(duì)操作的時(shí)間復(fù)雜度均為O(1)，要求④可以滿足。因此，采用鏈?zhǔn)酱鎯Y(jié)構(gòu)(兩段式單向循環(huán)鏈表)，隊(duì)頭指針為front，隊(duì)尾指針為rear。2)該循環(huán)鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)，可以參考循環(huán)隊(duì)列，不同之處在于循環(huán)鏈?zhǔn)疥?duì)列可以方便增加空間，出隊(duì)的結(jié)點(diǎn)可以循環(huán)利用，入隊(duì)時(shí)空間不夠也可以動(dòng)態(tài)增加。同樣，循環(huán)鏈?zhǔn)疥?duì)列也要區(qū)分隊(duì)滿和隊(duì)空的情況，這里參考循環(huán)隊(duì)列犧牲一個(gè)單元來判斷。初始時(shí)，創(chuàng)建只有一個(gè)空閑結(jié)點(diǎn)的循環(huán)單鏈表，頭指針front和尾指針rear均指向空閑結(jié)點(diǎn)，如下圖所示。隊(duì)空的判定條件：front==rear。隊(duì)滿的判定條件：front==rear->next。3)插入第一個(gè)元素后的狀態(tài)如下圖所示。4)操作的基本過程如下：43．解答：回顧傳統(tǒng)的哲學(xué)家問題，假設(shè)餐桌上有n個(gè)哲學(xué)家、n根筷子，那么可以用這種方法避免死鎖(王道單科書上提供了這一思路)：限制至多允許n一1個(gè)哲學(xué)家同時(shí)“搶”筷子，那么至少會有1個(gè)哲學(xué)家可以獲得兩根筷子并順利進(jìn)餐，于是不可能發(fā)生死鎖的情況。本題可以用碗這個(gè)限制資源來避免死鎖：當(dāng)碗的數(shù)量m小于哲學(xué)家的數(shù)量n時(shí)，可以直接讓碗的資源量等于m，確保不會出現(xiàn)所有哲學(xué)家都拿一側(cè)筷子而無限等待另一側(cè)筷子進(jìn)而造成死鎖的情況；當(dāng)碗的數(shù)量m大于等于哲學(xué)家的數(shù)量n時(shí)，為了讓碗起到同樣的限制效果，我們nn一1個(gè)哲學(xué)家同時(shí)進(jìn)餐，所以得到碗的資源量為min{n一1,m}。在進(jìn)行PV操作時(shí)，碗的資源量起限制哲學(xué)家取筷子的作用，所以需要先對碗的資源量進(jìn)行P操作。具體過程如下：///信號量semaphorebowl;semaphorechopsticks[n];for(inti=0;i<n;i++)chopsticks[i]=1;bowl=min(n-1,m);CoBegin思考;就餐;V(chopsticks[i]);n}CoEnd//用于協(xié)調(diào)哲學(xué)家對碗的使用//用于協(xié)調(diào)哲學(xué)家對筷子的使用//設(shè)置兩個(gè)哲學(xué)家之間筷子的數(shù)量//bowl≤n-1，確保不死鎖//取碗//取左邊筷子//取右邊筷子44．解答：1)磁盤容量=磁盤的柱面數(shù)每個(gè)柱面的磁道數(shù)每個(gè)磁道的扇區(qū)數(shù)每個(gè)扇區(qū)的大小=(300×10×200×512/1024)KB=3×105KB。2)磁頭在85號柱面上，對SSTF算法而言，總是訪問當(dāng)前柱面距離最近的地址。注意每個(gè)簇包含2個(gè)扇區(qū)，通過計(jì)算得到，85號柱面對應(yīng)的簇號為85000~85999。通過比較得出，系統(tǒng)最先訪問離85000~85999最近的100260，隨后訪問離100260最近的101660，然后訪問2019年全國碩士研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題3)第100530簇在磁盤上的物理地址由其所在的柱面號、磁道號、扇區(qū)號構(gòu)成。柱面號=L簇號/每個(gè)柱面的簇?cái)?shù)」=L100530/(10×200/2)」=100。磁道號=L(簇號%每個(gè)柱面的簇?cái)?shù))/每個(gè)磁道的簇?cái)?shù)」=L530/(200/2)」=5。扇區(qū)號=扇區(qū)地址%每個(gè)磁道的扇區(qū)數(shù)=(530×2)%200=60。將簇號轉(zhuǎn)換成磁盤物理地址的過程由磁盤驅(qū)動(dòng)程序完成。45．解答：1)計(jì)算f(10)需要調(diào)用函數(shù)f1共10次，執(zhí)行第16行的call指令會遞歸調(diào)用f1。2)第12行的jle指令是條件轉(zhuǎn)移指令，其含義為小于等于時(shí)轉(zhuǎn)移，本行代碼的意義為：當(dāng)n≤1時(shí)，跳轉(zhuǎn)至地址00401035H。第16行的call指令為函數(shù)調(diào)用指令，第20行的jmp指令為無條件轉(zhuǎn)移指令，第30行的ret指令為子程序的返回指令，這三條指令一定會使程序跳轉(zhuǎn)執(zhí)行。3)其長度計(jì)算機(jī)M上按字節(jié)編址，第16行的call指令的虛擬地址為00401025H，長度為5