計(jì)算機(jī)專業(yè)（基礎(chǔ)綜合）模擬試卷2（共458題）

計(jì)算機(jī)專業(yè)（基礎(chǔ)綜合）模擬試卷2（共9套）（共458題）計(jì)算機(jī)專業(yè)（基礎(chǔ)綜合）模擬試卷第1套一、單選題(本題共40題，每題1.0分，共40分。)1、設(shè)n是描述問題規(guī)模的非負(fù)整數(shù)，下面程序片段的時(shí)間復(fù)雜度是()。voidfun(intn){inti，k；for(i=1；i<=n；i十十)for(j=1；j<=n；j十十){k=1：while(k<=n)k=5*k：}}A、O(n2log2n)B、O(nlog5n)C、O(n2log5n)D、O(n3)標(biāo)準(zhǔn)答案：C知識點(diǎn)解析：基本運(yùn)算語句是k=5*k，設(shè)其執(zhí)行時(shí)間為T(n)。對于j每循環(huán)一次，該語句的執(zhí)行次數(shù)為m，有：5m≤n，即m≤log5n。所以：2、操作系統(tǒng)在運(yùn)行中會采用調(diào)度策略選擇新進(jìn)程占用CPU完成其功能。下面的選項(xiàng)中，操作系統(tǒng)不會調(diào)度新進(jìn)程的時(shí)機(jī)是()。A、當(dāng)前運(yùn)行進(jìn)程的時(shí)間片用完B、當(dāng)前運(yùn)行進(jìn)程出錯(cuò)后阻塞C、運(yùn)行進(jìn)程要等待某一個(gè)事件的發(fā)生D、新進(jìn)程被創(chuàng)建進(jìn)入就緒隊(duì)列標(biāo)準(zhǔn)答案：D知識點(diǎn)解析：本題考查進(jìn)程調(diào)度的時(shí)機(jī)。運(yùn)行著的進(jìn)程由于分配的時(shí)間到，或者運(yùn)行結(jié)束，或者需要等待事件的發(fā)生(例如等待鍵盤響應(yīng))，或者出錯(cuò)，或者自我阻塞等均可以引起激活調(diào)度程序進(jìn)行重新調(diào)度，選擇一個(gè)新的就緒進(jìn)程占有處理機(jī)運(yùn)行。新的進(jìn)程加入就緒隊(duì)列不是引起調(diào)度的直接原因，當(dāng)CPU正在處理其他進(jìn)程的請求時(shí)，該進(jìn)程仍然需要等待。即使在采用高優(yōu)先級優(yōu)先調(diào)度算法的系統(tǒng)中，一個(gè)最高優(yōu)先級的進(jìn)程進(jìn)入就緒隊(duì)列，仍舊需要考慮是否允許搶先，當(dāng)不允許搶先時(shí)仍然需要等待。3、某二叉樹的高度為50，樹中只有度為O和度為2的結(jié)點(diǎn)，那么此二叉樹中所包含的結(jié)點(diǎn)數(shù)最少為()。A、88B、90C、99D、100標(biāo)準(zhǔn)答案：C知識點(diǎn)解析：除根結(jié)點(diǎn)層只有1個(gè)結(jié)點(diǎn)外，其他各層均有兩個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)總數(shù)=2×(50-1)+l=99。4、MIPS(每秒百萬次指令數(shù))和MFL()PS(每秒百萬次浮點(diǎn)運(yùn)算數(shù))是衡量CPU性能的兩個(gè)指標(biāo)，其中()。A、MIPS適合衡量向量處理機(jī)的性能，MFLOPS適合衡量標(biāo)量處理機(jī)的性能B、MIPS適合衡量標(biāo)量處理機(jī)的性能，MFLOPS適合衡量向量處理機(jī)的性能C、MIPS反映計(jì)算機(jī)系統(tǒng)的峰值性能，MFLOPS反映計(jì)算機(jī)系統(tǒng)的持續(xù)性能D、MIPS反映計(jì)算機(jī)系統(tǒng)的持續(xù)性能，MFLOPS反映計(jì)算機(jī)系統(tǒng)的峰值性能標(biāo)準(zhǔn)答案：B知識點(diǎn)解析：MIPS反映的是單位時(shí)間內(nèi)執(zhí)行定點(diǎn)指令的條數(shù)，MLOPS是基于所完成的浮點(diǎn)操作次數(shù)而不是指令數(shù)。同一個(gè)程序，不同計(jì)算機(jī)運(yùn)行所需的指令數(shù)會不同，但所用到的浮點(diǎn)運(yùn)算次數(shù)卻是相同的。5、為提高查找效率，對有65025個(gè)元素的有序順序表建立索引順序結(jié)構(gòu)，在最好情況下查找到表中已有元素，需要執(zhí)行()次關(guān)鍵字比較。A、10B、14C、20D、21標(biāo)準(zhǔn)答案：B知識點(diǎn)解析：首先需要知道折半查找成功的平均查找長度為log2(n+1)-1。為使查找效率最高，可對有65025個(gè)元素的有序順序表分塊，每塊有=255個(gè)元素。為每一塊建立一個(gè)索引項(xiàng)，索引表共255個(gè)索引項(xiàng)。若對索引表和每一塊都采用折半查找，則查找效率最高，計(jì)算可得ASLIndexSeqSearch=ASLIndex+ASLBlock=log2(255+1)一1+log2(255+1)一1=14下面補(bǔ)充一些關(guān)于折半查找的概念。補(bǔ)充(1)：折半查找的時(shí)間復(fù)雜度為O(log2n)。補(bǔ)充(2)：折半查找是基于隨機(jī)存儲方式的算法，必須用順序表而不能用鏈表。補(bǔ)充(3)：對于折半查找，假設(shè)h表示判定樹的高度，如果有n個(gè)元素，則判定樹的高度為h=[log2(n+1)]或者h(yuǎn)=[log2(n+1)]+16、下列關(guān)于進(jìn)程狀態(tài)敘述正確的是()。Ⅰ．—次I/O操作的結(jié)束，有可能導(dǎo)致一個(gè)進(jìn)程由就緒變?yōu)檫\(yùn)行Ⅱ．一個(gè)運(yùn)行的進(jìn)程用完了分配給它的時(shí)間片后，它的狀態(tài)變?yōu)樽枞螅?dāng)系統(tǒng)中就緒進(jìn)程隊(duì)列非空時(shí)，也可能沒有運(yùn)行進(jìn)程Ⅳ．某個(gè)進(jìn)程由多個(gè)內(nèi)核線程組成，其中的一個(gè)線程被調(diào)度進(jìn)入運(yùn)行，有的繼續(xù)留在就緒隊(duì)列，有的被阻塞，則此時(shí)進(jìn)程的狀態(tài)是運(yùn)行狀態(tài)A、Ⅰ、ⅡB、ⅢC、ⅣD、全錯(cuò)標(biāo)準(zhǔn)答案：C知識點(diǎn)解析：Ⅰ錯(cuò)誤，一次I/O操作結(jié)束后，該I/O資源有可能被請求該資源的資源占有，從而使其從阻塞狀態(tài)轉(zhuǎn)變?yōu)榫途w狀態(tài)。等待I/O資源的進(jìn)程狀態(tài)是阻塞狀態(tài)，且進(jìn)程獲得CPU運(yùn)行是通過調(diào)度得到的，而不是獲得資源，該敘述錯(cuò)的很明顯。Ⅱ錯(cuò)誤，運(yùn)行進(jìn)程用完時(shí)間片后，是由運(yùn)行態(tài)變?yōu)榫途w狀態(tài)。Ⅲ錯(cuò)誤，就緒進(jìn)程隊(duì)列非空時(shí)，處理機(jī)不應(yīng)空閑，所以一定有運(yùn)行進(jìn)程。Ⅳ正確，在多線程操作系統(tǒng)中，把線程作為獨(dú)立運(yùn)行的基本單位，所以此時(shí)的進(jìn)程已不再是一個(gè)可執(zhí)行的實(shí)體。雖然如此，進(jìn)程仍具有與執(zhí)行相關(guān)的狀態(tài)。例如，所謂進(jìn)程處于“執(zhí)行”狀態(tài)，實(shí)際上是指該進(jìn)程中的某個(gè)線程正在執(zhí)行。只有當(dāng)所有線程都阻塞了，該進(jìn)程才會被認(rèn)為是阻塞，只要有一個(gè)進(jìn)程是運(yùn)行態(tài)，該進(jìn)程就是運(yùn)行態(tài)；若沒有線程運(yùn)行，只要有一個(gè)線程就緒，則該進(jìn)程就是就緒態(tài)。綜上所述，本題選C。7、以下IP地址中，路由器不進(jìn)行轉(zhuǎn)發(fā)的有()。Ⅰ．10．1．32．7Ⅱ．192．168，32．2Ⅲ．172．30．1．3Ⅳ．172．35．32．244A、僅Ⅰ、Ⅱ、ⅢB、僅Ⅱ、ⅢC、僅Ⅰ、Ⅲ、ⅣD、僅Ⅳ標(biāo)準(zhǔn)答案：A知識點(diǎn)解析：路由器對于專用網(wǎng)地址（私有地址）是不進(jìn)行轉(zhuǎn)發(fā)的。私有地址總結(jié)如下：A類～55（記住10開頭即可）B類172.16，0.0～55（這個(gè)死記）C類～55（記住192.168開頭即可）8、下面關(guān)于交換機(jī)的說法中，正確的是()。A、以太網(wǎng)交換機(jī)可以連接運(yùn)行不同網(wǎng)絡(luò)層協(xié)議的網(wǎng)絡(luò)B、從工作原理上講，以太網(wǎng)交換機(jī)是一種多端口網(wǎng)橋C、集線器是一種特殊的交換機(jī)D、通過交換機(jī)連接的一組工作站形成一個(gè)沖突域標(biāo)準(zhǔn)答案：B知識點(diǎn)解析：本題考查交換機(jī)和集線器的區(qū)別。選項(xiàng)A，交換機(jī)是數(shù)據(jù)鏈路層設(shè)備，對于網(wǎng)絡(luò)層來說是透明的，表述有問題。選項(xiàng)C，集線器是物理層設(shè)備，和交換機(jī)不在同一個(gè)層次。選項(xiàng)D，交換機(jī)的優(yōu)勢就是每個(gè)端口是一個(gè)沖突域，整個(gè)交換機(jī)是一個(gè)廣播域，因此答案是B。9、一個(gè)C類地址，采用了255．255．255．240作為子網(wǎng)掩碼，那么這個(gè)C類地址可以劃分為()個(gè)子網(wǎng)。A、16B、32C、64D、128標(biāo)準(zhǔn)答案：A知識點(diǎn)解析：先將子網(wǎng)掩碼轉(zhuǎn)換成二進(jìn)制得到11111111．11111111．111l1111．1111000。C類的主機(jī)號是8位的，現(xiàn)在用高4位來表示子網(wǎng)，因此可以得到16個(gè)子網(wǎng)。10、一個(gè)C類網(wǎng)絡(luò)的子網(wǎng)掩碼為255．255．252．252，則該C類網(wǎng)絡(luò)的主機(jī)數(shù)目是()。A、2046B、1022C、510D、128標(biāo)準(zhǔn)答案：D知識點(diǎn)解析：本題考查IPv4子網(wǎng)劃分，首先明確C類網(wǎng)絡(luò)的掩碼是255．255．0．255，而252的二進(jìn)制是11111100，由此可知可劃分26=64個(gè)子網(wǎng)，每個(gè)子網(wǎng)的主機(jī)數(shù)為22-2=2，因此該C類網(wǎng)絡(luò)的主機(jī)數(shù)目是64×2=128，因此答案是D。11、文件系統(tǒng)中若文件的物理結(jié)構(gòu)采用連續(xù)結(jié)構(gòu)，則文件控制塊FCB中有關(guān)文件的物理位置的信息包括()。Ⅰ．首塊地址Ⅱ．文件長度Ⅲ．索引表地址A、只有ⅢB、Ⅰ和ⅡC、Ⅱ和ⅢD、Ⅰ和Ⅲ標(biāo)準(zhǔn)答案：C知識點(diǎn)解析：連續(xù)結(jié)構(gòu)不需要用到索引表，那么文件控制塊中也就不可能有索引表地址信息，因此排除A、C、D選項(xiàng)，選B。12、在虛擬分頁存儲管理系統(tǒng)中，若進(jìn)程訪問的頁面不在主存，且主存中沒有可用的空閑幀時(shí)，系統(tǒng)正確的處理順序?yàn)?)。A、決定淘汰頁→頁面調(diào)出→缺頁中斷→頁面調(diào)入B、決定淘汰頁→頁面調(diào)入→缺頁中斷→頁面調(diào)出C、缺頁中斷→決定淘汰頁→頁面調(diào)出→頁面調(diào)入D、缺頁中斷→決定淘汰頁→頁面調(diào)入→頁面調(diào)出標(biāo)準(zhǔn)答案：C知識點(diǎn)解析：根據(jù)缺頁中斷的處理流程，產(chǎn)生缺頁中斷后，首先去內(nèi)存尋找空閑物理塊，若內(nèi)存沒有空閑物理塊，則使用相應(yīng)的頁面置換算法決定淘汰頁面，然后調(diào)出該淘汰頁面；最后在調(diào)入該進(jìn)程需要訪問的頁面，所以整個(gè)流程可以歸結(jié)為：缺頁中斷→決定淘汰頁→頁面調(diào)出→頁面調(diào)入。13、一個(gè)IPv6包中“通信量類”字段的值為0，表明()。A、該包優(yōu)先級最低，擁塞時(shí)可以被丟棄B、該包優(yōu)先級最高，擁塞時(shí)不能被丟棄C、該包中沒有用戶數(shù)據(jù)，只有首部D、該包不可進(jìn)行路由器轉(zhuǎn)發(fā)標(biāo)準(zhǔn)答案：A知識點(diǎn)解析：IPv6首部總結(jié)，如圖4-12所示。版本(version)——4bit，它指明了協(xié)議的版本，對于IPv6，該字段總是6。通信量類(trafficclass)——8bit，這是為了區(qū)分不同的IPv6數(shù)據(jù)報(bào)的類別或優(yōu)先級。已經(jīng)定義了0～15共16個(gè)優(yōu)先級，0的優(yōu)先級最低。0～7表示允許延遲，8～15表示高優(yōu)先級，需要固定速率傳輸。流標(biāo)號(flowlabel)——20bit，“流”是互聯(lián)網(wǎng)上從特定源點(diǎn)到特定終點(diǎn)的一系列數(shù)據(jù)報(bào)，“流”所經(jīng)過的路徑上的路由器都保證指明的服務(wù)質(zhì)量。所有屬于同一個(gè)流的數(shù)據(jù)報(bào)都具有同樣的流標(biāo)號。有效載荷長度(payloadlength)——16bit，它指明IPv6數(shù)據(jù)報(bào)除基本首部以外的字節(jié)數(shù)(所有擴(kuò)展首部都算在有效載荷之內(nèi))，其最大值是64KB。下一個(gè)首部(nextheader)——8bit，它相當(dāng)于IPv4的協(xié)議字段或可選字段。跳數(shù)限制(hoplimit)——8bit，源站在數(shù)據(jù)報(bào)發(fā)出時(shí)即設(shè)定跳數(shù)限制。路由器在轉(zhuǎn)發(fā)數(shù)據(jù)報(bào)時(shí)將跳數(shù)限制字段中的值減1。當(dāng)跳數(shù)限制的值為零時(shí)，就要將此數(shù)據(jù)報(bào)丟棄。源地址——128bit，數(shù)據(jù)報(bào)的發(fā)送站的IP地址。目的地址——128bit，數(shù)據(jù)報(bào)的接收站的IP地址。14、微程序存放在CPU的哪個(gè)部件中()。A、主存儲器B、存儲器控制器C、控制存儲器D、輔助存儲器標(biāo)準(zhǔn)答案：C知識點(diǎn)解析：微程序存放在控制存儲器中，選C。注意區(qū)別存控與控存的區(qū)別，控存用來存放微程序，而存控是用來管理協(xié)調(diào)CPU、DMA控制器等對主存儲器訪問的部件。15、用戶程序在用戶態(tài)下使用陷入指令而引起的中斷是()。A、故障中斷B、外部中斷C、不可屏蔽中斷D、訪管中斷標(biāo)準(zhǔn)答案：D知識點(diǎn)解析：本題考查用戶態(tài)和內(nèi)核態(tài)及其轉(zhuǎn)換的概念。在操作系統(tǒng)管理下的計(jì)算機(jī)中，為保護(hù)系統(tǒng)的安全，對一部分處理機(jī)的指令限定使用對象，即只有操作系統(tǒng)才可以執(zhí)行。而當(dāng)用戶需要使用這些特權(quán)指令時(shí)，必須調(diào)用特定的訪管指令，也稱陷入指令，顧名思義由用戶態(tài)陷入到內(nèi)核態(tài)，從而從用戶態(tài)轉(zhuǎn)入內(nèi)核態(tài)，繼而可以執(zhí)行特權(quán)指令；訪管指令引起的中斷稱為訪管中斷，它是用戶使用特權(quán)指令的唯一人口。16、下列所示關(guān)系中，不是信號量能實(shí)現(xiàn)的功能是()。A、進(jìn)程同步B、進(jìn)程互斥C、執(zhí)行的前趨關(guān)系D、進(jìn)程的并發(fā)執(zhí)行標(biāo)準(zhǔn)答案：D知識點(diǎn)解析：本題考查信號量的功能，在多道程序技術(shù)系統(tǒng)中，信號量機(jī)制是一種有效的實(shí)現(xiàn)進(jìn)程同步與互斥的工具。信號量可以實(shí)現(xiàn)的功能有：進(jìn)程的同步與互斥，進(jìn)程執(zhí)行的前趨關(guān)系，進(jìn)程執(zhí)行的前趨關(guān)系實(shí)質(zhì)上是指進(jìn)程的同步關(guān)系。除此以外，只有進(jìn)程的并發(fā)執(zhí)行不需要信號量來控制，因此正確答案為D。17、計(jì)算機(jī)系統(tǒng)中，不屬于DMA控制器的是()。A、命令／狀態(tài)寄存器B、內(nèi)存地址寄存器C、數(shù)據(jù)寄存器D、堆棧指針寄存器標(biāo)準(zhǔn)答案：D知識點(diǎn)解析：本題考查IO設(shè)備中DMA設(shè)備的組成。DMA設(shè)備與CPU有三類信號線：數(shù)據(jù)線、地址線和控制線。一般要DMA設(shè)備工作，必須有命令／狀態(tài)寄存器，這個(gè)寄存器控制DMA的工作模式并反映給CPU它當(dāng)前的狀態(tài)，地址寄存器存放DMA作業(yè)時(shí)的源地址和目標(biāo)地址，數(shù)據(jù)寄存器存放要DMA轉(zhuǎn)移的數(shù)據(jù)，只有堆棧指針寄存器不需要在DMA控制器中存放。堆棧一般在計(jì)算機(jī)內(nèi)存中開辟有統(tǒng)一的區(qū)域。18、假定有兩個(gè)帶符號整數(shù)x、y用8位補(bǔ)碼表示，x=63，y=—31，則x—y的機(jī)器數(shù)及其相應(yīng)的溢出標(biāo)志OF分別是()。A、SDH．0B、SEH、0C、SDH．1D、SEH、1標(biāo)準(zhǔn)答案：B知識點(diǎn)解析：因?yàn)閤=63，y=—31，則x—y=94，而帶符號的8位整數(shù)補(bǔ)碼所能表示的范圍是—128～127，所以94在其范圍之內(nèi)，沒有溢出，即OF標(biāo)志為0，將結(jié)果轉(zhuǎn)化為機(jī)器數(shù)為SEH。此種題型在2009年，2014年的統(tǒng)考卷當(dāng)中已經(jīng)出現(xiàn)，現(xiàn)在對于這種在選擇題當(dāng)中出現(xiàn)補(bǔ)碼加減運(yùn)算或者是涉及浮點(diǎn)數(shù)加減計(jì)算的情況，總結(jié)如下：(1)涉及浮點(diǎn)數(shù)計(jì)算或者是復(fù)雜的補(bǔ)碼的計(jì)算，不要立刻去按照補(bǔ)碼的規(guī)則和浮點(diǎn)數(shù)加減規(guī)則去運(yùn)算，不要關(guān)注題干給你的一些無用信息（比如浮點(diǎn)數(shù)的各運(yùn)算步驟之類的）。(2)觀察題干給你的兩個(gè)數(shù)，可以試著加加看，或者減減看，看結(jié)果到底為多少，然后看這個(gè)結(jié)果是否在寄存器所能表示的數(shù)（一般是補(bǔ)碼）的范圍之內(nèi)。如果不能表示，那一定是溢出了，如果能表示，再把這個(gè)結(jié)果化為二進(jìn)制或者十六進(jìn)制。19、下列關(guān)于并行微程序控制器的說法正確的是()。A、現(xiàn)行微指令的執(zhí)行與取下一條微指令的操作并行B、現(xiàn)行微指令的執(zhí)行與取下一條微指令的操作串行C、兩條或更多微指令的執(zhí)行在時(shí)間上并行D、兩條或更多微指令的取微指令操作在時(shí)間上并行標(biāo)準(zhǔn)答案：A知識點(diǎn)解析：并行微程序控制器中，在執(zhí)行現(xiàn)行微指令的同時(shí)，取下一條微指令，A選項(xiàng)的描述正確。20、在一個(gè)采用虛擬存儲管理的系統(tǒng)中，計(jì)算機(jī)的數(shù)據(jù)位和地址位寬均為32位，假設(shè)當(dāng)前系統(tǒng)中存在10個(gè)進(jìn)程，主存的容量是2GB，輔存的容量為500GB，在這樣的系統(tǒng)中，所有進(jìn)程虛存的總空間大小是()。A、4GBB、40GBC、2GBD、502GB標(biāo)準(zhǔn)答案：B知識點(diǎn)解析：本題考查虛擬存儲器的最大空間的問題。虛擬存儲器空間的最大值與實(shí)際存儲容量沒有關(guān)系，僅與其地址系統(tǒng)的位寬有關(guān)，32位的系統(tǒng)其最大虛存每個(gè)進(jìn)程都是4GB。若系統(tǒng)中存在10個(gè)進(jìn)程，則總虛擬存儲空間是所有進(jìn)程虛擬存儲空間之和。本題中為40GB。但是若要問，虛存的實(shí)際容量是多少時(shí)，則要考慮主存和輔存的大小，若主存和輔存之和小于最大虛擬存儲空間40GB，則應(yīng)是主存和虛存的實(shí)際容量之和。若大于40GB，則多余的部分是沒有用的(僅指虛擬存儲的外存，因?yàn)橛脖P的主要作用是存儲文件，僅用一部分來作為虛存的外存)。21、如果I／O設(shè)備和存儲設(shè)備之間的數(shù)據(jù)交換不經(jīng)過CPU來完成，則這種交換方式是()。A、程序查詢方式B、中斷方式C、DMA方式D、外部總線方式標(biāo)準(zhǔn)答案：C知識點(diǎn)解析：暫無解析22、下列文件物理結(jié)構(gòu)中，適合隨機(jī)訪問且易于文件擴(kuò)展的是()。A、連續(xù)結(jié)構(gòu)B、索引結(jié)構(gòu)C、鏈?zhǔn)浇Y(jié)構(gòu)且磁盤塊定長D、鏈?zhǔn)浇Y(jié)構(gòu)且磁盤塊變長標(biāo)準(zhǔn)答案：B知識點(diǎn)解析：索引結(jié)構(gòu)適合隨機(jī)訪問且易于文件擴(kuò)展。23、某公司獲得了一個(gè)IP地址段，在不分子網(wǎng)的情況下，最多可以容納65534個(gè)主機(jī)，那么這個(gè)地址屬于()。A、A類地址B、B類地址C、C類地D、D類地址標(biāo)準(zhǔn)答案：B知識點(diǎn)解析：B類地址的主機(jī)號的長度是16位，再去點(diǎn)全“0”和全“1"兩個(gè)地址，還可以分配65534個(gè)主機(jī)。24、下列關(guān)于TCP和UDP的說法正確的是()。A、兩者都是面向無連接的B、兩者都是面向連接的C、TCP是面向連接而UDP是面向無連接的D、TCP無連接而UDP是面向連接的標(biāo)準(zhǔn)答案：C知識點(diǎn)解析：TCP／IP參考模型的傳輸層上有兩個(gè)主要的協(xié)議，用戶數(shù)據(jù)報(bào)協(xié)議UDP(無連接)和傳輸控制協(xié)議TCP(面向連接)，主要區(qū)別如下：(1)TOP是基于連接的，UDP是基于無連接，這是本質(zhì)的區(qū)別，其他區(qū)別都是為之服務(wù)的。(2)對系統(tǒng)資源的要求：TCP較多，UDP少。(3)UDP數(shù)據(jù)包結(jié)構(gòu)較簡單，而TCP為了保證流量控制和擁塞控制，數(shù)據(jù)包結(jié)構(gòu)較為復(fù)雜。(4)TCP采用流模式，并進(jìn)行編號，但UDP采用數(shù)據(jù)報(bào)模式(5)TCP保證數(shù)據(jù)正確性，UDP可能丟包；TOP保證數(shù)據(jù)順序，UDP不保證。本題考查TCP和UDP的傳輸特性，TCP可靠有連接，UDP不可靠無連接，因此答案是C。25、現(xiàn)在可以使用()來編寫Web頁面。A、HTTPB、HTMLC、MIMED、XML標(biāo)準(zhǔn)答案：B知識點(diǎn)解析：HTML(超文本標(biāo)記語言)是用來描述格式化文檔的語言，用來編寫Web頁面。26、下面關(guān)于圖的存儲結(jié)構(gòu)的敘述中正確的是()。A、用鄰接矩陣存儲圖占用空間大小只與圖中頂點(diǎn)有關(guān)，與邊數(shù)無關(guān)B、用鄰接矩陣存儲圖占用空間大小只與圖中邊數(shù)有關(guān)，與頂點(diǎn)無關(guān)C、用鄰接表存儲圖占用空間大小只與圖中頂點(diǎn)數(shù)有關(guān)，與邊數(shù)無關(guān)D、用鄰接表存儲圖占用空間大小只與圖中邊數(shù)有關(guān)，與頂點(diǎn)數(shù)無關(guān)標(biāo)準(zhǔn)答案：A知識點(diǎn)解析：暫無解析27、利用棧求表達(dá)式的值時(shí)，設(shè)立運(yùn)算數(shù)棧S。假設(shè)棧S只有兩個(gè)存儲單元，在下列表達(dá)式中，不發(fā)生溢出的是()。A、A—B*(C—D)B、(A—B)*C—DC、(A—B*C)—DD、(A—B)*(C—D)標(biāo)準(zhǔn)答案：B知識點(diǎn)解析：利用棧求表達(dá)式的值時(shí)，需要設(shè)立運(yùn)算符棧和運(yùn)算數(shù)棧，下面僅舉一例。例如，求2×(5—3)+6/2的過程如表6—2所示。從上述的計(jì)算過程中，考生可以自行對A、B、C、D選項(xiàng)進(jìn)行練習(xí)，運(yùn)算數(shù)棧S的大小分別至少為4、2、3、3，只有B選項(xiàng)滿足條件。28、設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1，則T中的葉子數(shù)是()。A、5B、6C、7D、8標(biāo)準(zhǔn)答案：D知識點(diǎn)解析：由二叉樹性質(zhì)的推廣，度為4的樹應(yīng)該有1+n2+2n3+3n4個(gè)葉結(jié)點(diǎn)(ni表示度為i的結(jié)點(diǎn)數(shù)目)，與度為1的結(jié)點(diǎn)的個(gè)數(shù)無關(guān)。因此，如果用n0表示葉結(jié)點(diǎn)的個(gè)數(shù)，則應(yīng)該有n0=1+2+2×1+3×1=8。29、在讀寫硬盤的一個(gè)物理記錄塊時(shí)，不需要的參數(shù)是()。A、柱面(磁道)號B、盤片(磁頭)C、簇號D、扇區(qū)號標(biāo)準(zhǔn)答案：C知識點(diǎn)解析：在讀寫硬盤的一個(gè)物理記錄塊時(shí)，需要的參數(shù)是磁道號、磁頭號和扇區(qū)號。30、通道方式的工作過程中，下列步驟的正確順序是()。①組織I／O操作②向CPU發(fā)出中斷請求③編制通道程序④啟動I／O通道A、①→②→③→④B、②→③→①→④C、④→③→②→①D、③→④→①→②標(biāo)準(zhǔn)答案：D知識點(diǎn)解析：考查通道的工作過程。通道的基本工作過程(以一次數(shù)據(jù)傳送為例)如下：①在用戶程序中使用訪管指令進(jìn)入操作系統(tǒng)管理程序，由CPIU通過管理程序組織一個(gè)通道程序，并使用I／O指令啟動通道(此后CPU并行運(yùn)行應(yīng)用程序)。②通道處理器執(zhí)行CPU為其組織的通道程序，完成指定的數(shù)據(jù)的輸入／輸出工作。③通道程序結(jié)束后，向CPU發(fā)出中斷請求。CPU響應(yīng)此中斷請求后，第二次進(jìn)入操作系統(tǒng)，調(diào)用管理程序?qū)斎耄敵鲋袛噙M(jìn)行處理。31、假設(shè)有一個(gè)信道的帶寬是3000Hz，其信噪比為20dB，那么這個(gè)信道可以獲得的理論最大傳輸速率是()。A、1KbpsB、32KbpsC、20KbpsD、64Kbps標(biāo)準(zhǔn)答案：C知識點(diǎn)解析：SNR=10log10(S／N)，題目中SNR=20dB，因此S／N=100。再使用香農(nóng)定理可以得到信道的理論速率上限C=Wlog2(1+S／N)=3000×log2(1+100)≈20(Kbps)。32、假定主存按字節(jié)編址，Cache共有64行，采用4路組相聯(lián)映射方式，主存塊大小為32字節(jié)，所有編號都從0開始，則主存第3000號單元所在主存塊對應(yīng)的Cache組號是()。A、1B、5C、13D、29標(biāo)準(zhǔn)答案：C知識點(diǎn)解析：因?yàn)橹鞔姘醋止?jié)編址，每塊32B，故第3000號單元(從0開始編制)所在的塊號為3000／32=93；又因?yàn)镃ache采用四路組相連，一共64行(可看成64塊)，一共有64／4=16組，于是按照主存塊號對應(yīng)Cache組號，映射后第93塊在Cache中的組號為93％16=13。答案選C。33、分時(shí)系統(tǒng)中，為使多個(gè)用戶能夠同時(shí)與系統(tǒng)交互，最關(guān)鍵的問題是()。A、計(jì)算機(jī)具有足夠的運(yùn)行速度B、內(nèi)存容量應(yīng)足夠大C、系統(tǒng)能及時(shí)地接收多個(gè)用戶輸入D、能在一短的時(shí)間內(nèi)，使所有用戶程序都能運(yùn)行標(biāo)準(zhǔn)答案：D知識點(diǎn)解析：本題考查分時(shí)系統(tǒng)的特點(diǎn)。34、關(guān)于FTP主要應(yīng)用功能的敘述正確的是()。A、FTP使用戶和遠(yuǎn)程主機(jī)相連，從而對主機(jī)內(nèi)的各種資源進(jìn)行各種操作，如文件的讀、寫、執(zhí)行、修改等B、FTP的功能類似于TelnetC、FTP的主要功能在于文件傳輸，但FTP客戶端在一定的范圍內(nèi)也有執(zhí)行修改等其他文件的功能D、FTP使用戶同遠(yuǎn)程主機(jī)相連，類似于遠(yuǎn)程主機(jī)的仿真終端用戶，從而應(yīng)用遠(yuǎn)程主機(jī)的資源標(biāo)準(zhǔn)答案：C知識點(diǎn)解析：FTP(文件傳輸協(xié)議)，主要功能有：(1)把本地計(jì)算機(jī)上的一個(gè)或多個(gè)文件傳送到遠(yuǎn)程計(jì)算機(jī)，或從遠(yuǎn)程計(jì)算機(jī)上獲取一個(gè)或多個(gè)文件。(2)提供對本地計(jì)算機(jī)和遠(yuǎn)程計(jì)算機(jī)的目錄操作功能。(3)客戶端在一定的范圍內(nèi)對文件進(jìn)行改名、刪除、顯示文件內(nèi)容等。35、在微程序控制中，機(jī)器指令和微指令的關(guān)系是()。A、每一條機(jī)器指令由一條微指令解釋執(zhí)行B、每一條機(jī)器指令由一段微程序解釋執(zhí)行C、每一條微指令由一條機(jī)器指令解釋執(zhí)行D、每一段微程序由若干條機(jī)器指令解釋執(zhí)行標(biāo)準(zhǔn)答案：B知識點(diǎn)解析：在微程序控制中一條機(jī)器指令對應(yīng)一個(gè)微程序，每一個(gè)微程序包含若干條微指令，每一條微指令對應(yīng)一個(gè)或幾個(gè)微操作命令。當(dāng)計(jì)算機(jī)運(yùn)行時(shí)，逐條執(zhí)行微程序中的每一條微命令，就相應(yīng)的完成了一條機(jī)器指令的全部操作。36、下而元件存取速度最快的是()。A、CacheB、寄存器C、外存D、內(nèi)存標(biāo)準(zhǔn)答案：B知識點(diǎn)解析：速度快慢排序如下：寄存器>Cache>內(nèi)存>外存。37、將N個(gè)關(guān)鍵字映射到一個(gè)Hash表中，用鏈地址法解決沖突。在這個(gè)Hash表中查找一個(gè)關(guān)鍵字所需的操作為()。A、Hash映射N次，鏈結(jié)點(diǎn)比較最多1次B、Hash映射1次，鏈結(jié)點(diǎn)比較最多N次C、Hash映射N／2次，鏈結(jié)點(diǎn)比較最多N／2次D、Hash映射N-1次，鏈結(jié)點(diǎn)比較最多1次標(biāo)準(zhǔn)答案：B知識點(diǎn)解析：查找一個(gè)關(guān)鍵字只需一次Hash映射就可找到關(guān)鍵字所在的鏈表，緊接著在該鏈表中從頭到尾依次查找每個(gè)元素是否是所要查找的關(guān)鍵字，此時(shí)最多需N次鏈表結(jié)點(diǎn)的比較。38、在IP數(shù)據(jù)報(bào)報(bào)頭中有兩個(gè)有關(guān)長度的字段，一個(gè)為報(bào)頭長度(IHL)字段，一個(gè)為總長度(totallength)字段，下面說法正確的是()。A、報(bào)頭長度字段和總長度字段都以8比特為計(jì)數(shù)單位B、報(bào)頭長度字段以8比特為計(jì)數(shù)單位，總長度字段以32比特為計(jì)數(shù)單位C、報(bào)頭長度字段以32比特為計(jì)數(shù)單位，總長度字段以8比特為計(jì)數(shù)單位D、報(bào)頭長度字段和總長度字段都以32比特為計(jì)數(shù)單位標(biāo)準(zhǔn)答案：C知識點(diǎn)解析：IHL實(shí)段以4字節(jié)為單位，totallength字段以字節(jié)為單位。39、支持多道程序的操作系統(tǒng)，區(qū)別于其他操作系統(tǒng)的主要特征為()。A、多用戶、進(jìn)程的獨(dú)立性、進(jìn)程之間的同步與通信B、進(jìn)程的獨(dú)立性、進(jìn)程之間的同步與通信、動態(tài)存儲分配C、進(jìn)程的獨(dú)立性、動態(tài)存儲分配、虛存D、多內(nèi)核結(jié)構(gòu)、進(jìn)程的獨(dú)立性、動態(tài)存儲分配標(biāo)準(zhǔn)答案：B知識點(diǎn)解析：A是多用戶操作系統(tǒng)區(qū)別于其他操作系統(tǒng)的特點(diǎn)。40、三哲學(xué)家進(jìn)餐問題的偽代碼如下，f1，f2，f3是三根筷子，則()。A、可能死鎖，p1或p2或p3都有可能饑餓B、不可能死鎖．但p1或p2或p3都有可能饑餓C、不可能死鎖，但只有p1或p2有可能饑餓D、不可能死鎖。但只有p2或p3有可能饑餓標(biāo)準(zhǔn)答案：B知識點(diǎn)解析：p1、p2和p3不滿足死鎖的四個(gè)必要條件中的循環(huán)等待條件，故不可能發(fā)生死鎖。排除A。設(shè)p3先申請到f3，若此時(shí)p2先于p1申請到f1，則此時(shí)p2好和p3任意一個(gè)申請到f2都可執(zhí)行完畢，假設(shè)是p2申請到了f2執(zhí)行完畢，釋放f2，f1，則p3可獲得f2執(zhí)行完畢，倘若p2緊接著又申請到了f1，p3執(zhí)行完后緊接著又申請到了f3；如此循環(huán)則p1始終沒有機(jī)會獲得處理機(jī)執(zhí)行而發(fā)生饑餓現(xiàn)象。以此類推p2和p3都有可能發(fā)生饑餓現(xiàn)象。故選B。二、綜合應(yīng)用題(本題共9題，每題1.0分，共9分。)下圖所示為雙總線結(jié)構(gòu)機(jī)器的數(shù)據(jù)通路，IR為指令寄存器，PC為程序計(jì)數(shù)器(具有自增功能)，M為主存(受R／W信號控制)，AR為地址寄存器，DR為數(shù)據(jù)緩沖寄存器，ALU由加、減控制信號決定完成何種操作，控制信號G控制的是一個(gè)門電路。另外，線上標(biāo)注有小圈表示有控制信號，例中yi表示y寄存器的輸入控制信號，R1o為寄存器R1的輸出控制信號，未標(biāo)字符的線為直通線，不受控制。41、“ADDR2，R0”指令完成(R0)+(R2)→R0的功能操作，畫出其指令周期流程圖，假設(shè)該指令的地址已放入PC中。并列出相應(yīng)的微操作控制信號序列。標(biāo)準(zhǔn)答案：知識點(diǎn)解析：暫無解析42、若將“取指周期”縮短為一個(gè)CPU周期，請先畫出修改數(shù)據(jù)通路，后畫出指令周期流程圖。標(biāo)準(zhǔn)答案：[*]知識點(diǎn)解析：暫無解析43、在(2)的基礎(chǔ)上，將“執(zhí)行周期”也縮短為一個(gè)CPu周期，先修改運(yùn)算器數(shù)據(jù)通路，后畫出指令周期流程圖。此時(shí)加法指令速度比(1)提高幾倍?標(biāo)準(zhǔn)答案：[*]知識點(diǎn)解析：暫無解析完成以下各小題。44、什么是Belady現(xiàn)象?為什么會產(chǎn)生這種現(xiàn)象?標(biāo)準(zhǔn)答案：如果某種換頁算法，在增加頁框數(shù)之后反而可能導(dǎo)致更多缺頁，這種反常情形稱為Belady現(xiàn)象。知識點(diǎn)解析：暫無解析45、頁面置換算法FIFO為什么會出現(xiàn)Belady現(xiàn)象?簡述理由。標(biāo)準(zhǔn)答案：FIFO換頁策略將最早換人頁框的頁面換出，而不考慮該頁面是否最近使用過，這違背了局部性原理。當(dāng)頁框數(shù)較大時(shí)，由于包含的頁面更多，歷史記錄更全面，就有可能使最近頻繁使用但較早進(jìn)入頁框的頁面被換出，從而出現(xiàn)Belady異常。知識點(diǎn)解析：暫無解析46、頁面置換算法LRU為什么不會出現(xiàn)Belady現(xiàn)象?簡述理由。標(biāo)準(zhǔn)答案：LRU換頁策略將最近最長時(shí)間未使用的頁面換出，符合局部性原理。當(dāng)頁框數(shù)較大時(shí)，最近最長未使用的情況更全面，因此缺頁數(shù)不會增加。知識點(diǎn)解析：暫無解析假定A和B是試圖在一個(gè)以太網(wǎng)上發(fā)送的兩個(gè)站。每個(gè)站都有一個(gè)穩(wěn)定的幀的隊(duì)列準(zhǔn)備發(fā)送，A的幀編號是A1，A2和A3等，B的幀編號是B1，B2和B3等。再假定指數(shù)后退的基本單元時(shí)間是T=51．2微秒?，F(xiàn)在A和B同時(shí)嘗試發(fā)送1號幀，碰撞，并且剛好分別選擇了0×T和1×T的退避時(shí)間，也就是說，A贏得了這一次競爭，發(fā)送A1，B需要等待。在這次傳送結(jié)束時(shí)，B嘗試再發(fā)送B1．而A則嘗試發(fā)送A2。這一輪的首次嘗試產(chǎn)生碰撞，此時(shí)，A的退避時(shí)間從0×T和1×T中選擇，而B則從0×T，…，3×T中選擇。47、給出A贏得第2次退避競爭的概率。標(biāo)準(zhǔn)答案：A可以選擇KA=0或1；B可以選擇KB=0，1，2，3。如果(KA，KB)選擇(0，1)，(0，2)，(0，3)，(1，2)，(1，3)中的一個(gè)組合，那么將是A贏得這第2次競爭，其概率是5／8。知識點(diǎn)解析：暫無解析48、假定A已贏得了第2次退避競爭。A在成功發(fā)送A2后，接著嘗試發(fā)送A3。當(dāng)B再次嘗試發(fā)送B1時(shí)，A和B再次碰撞。給出A贏得這第3次退避競爭的概率。標(biāo)準(zhǔn)答案：現(xiàn)在A是在一次成功發(fā)送之后，可以選擇KA=0或1；KB是在它的第3次碰撞之后，可能的選擇是0，1，2，…，7。如果KA=0，那么KB中有7種選擇使得A贏；如果KA=1，那么KB中有6種選擇使得A贏。所以A贏得這第3次競爭的概率是13／16。知識點(diǎn)解析：暫無解析49、給出A贏得所有其余后退競爭的概率的合理下限值。標(biāo)準(zhǔn)答案：A贏得第2次競爭的概率=5／8>1／2A贏得第3次競爭的概率=13／16>3／4類似地，A贏得第4次競爭的概率>7／8一般地，A贏得第i次競爭的概率>(1—1／2i一1)因此，假定A已經(jīng)贏得第1至第3次競爭，那么A贏得所有其余的后退競爭的概率將不低于：(1—1／8)×(1一1／16)×(1一1／32)×(1一1／64)×…≈1—1／8—1／16—1／32—1／64一…=6／8=3／4知識點(diǎn)解析：暫無解析計(jì)算機(jī)專業(yè)（基礎(chǔ)綜合）模擬試卷第2套一、單選題(本題共40題，每題1.0分，共40分。)1、設(shè)有一個(gè)遞歸算法如下：intX(intn)；if(n＜=3)return1；elsereturnX(n一2)+X(n一4)+1；試問計(jì)算X(X(5))時(shí)需要調(diào)用()次X函數(shù)。A、2B、3C、4D、5標(biāo)準(zhǔn)答案：C知識點(diǎn)解析：該遞歸算法的定義為：即當(dāng)參數(shù)值小于等于3的時(shí)候，整個(gè)流程調(diào)用X(n)一次，而當(dāng)參數(shù)值大于3的時(shí)候，整個(gè)流程調(diào)用X(n)至少3次(第一次即本次調(diào)用，第二次為X(n—2)，第三次為X(n—4))。X(X(5))遞歸調(diào)用的執(zhí)行結(jié)果如下：一個(gè)方塊代表一次調(diào)用，一共調(diào)用了4次。2、設(shè)有一個(gè)10階對稱矩陣A，采用壓縮存儲方式，以行序?yàn)橹鞔鎯?，a1，1為第一個(gè)元素，其,存儲地址為1，每個(gè)元素占一個(gè)地址空間，則a8,5的地址可能是()。A、13B、33C、18D、40標(biāo)準(zhǔn)答案：B知識點(diǎn)解析：考查特殊矩陣的存儲。對稱矩陣可以存儲其下三角，也可以存儲其上三角。數(shù)組下標(biāo)從1開始，當(dāng)存儲下三角元素時(shí)，在a8,5的前面有7行，第1行有1個(gè)元素，第2行有2個(gè)元素，…，第7行有7個(gè)元素，這7行共有(1+7)×7／2=28個(gè)元素，在第8行中，a8,5的前面有4個(gè)元素，所以，a8,5前面有28+4=32個(gè)元素，其地址為33。當(dāng)存儲上三角元素時(shí)，a8,5對應(yīng)于a5,8，地址為38，無此選項(xiàng)，故只可能選B。3、若一棵深度為6的完全二叉樹的第6層有3個(gè)葉子結(jié)點(diǎn)，則該二叉樹共有()個(gè)葉子結(jié)點(diǎn)。A、17B、18C、19D、20標(biāo)準(zhǔn)答案：A知識點(diǎn)解析：考查完全二叉樹性質(zhì)。完全二叉樹第5層共有24=16個(gè)結(jié)點(diǎn)。第6層最左邊有3個(gè)葉子結(jié)點(diǎn)，對應(yīng)第5層最左邊2個(gè)結(jié)點(diǎn)，所以第5層右邊有16—2=14個(gè)葉子結(jié)點(diǎn)，因此共有17個(gè)葉子結(jié)點(diǎn)。4、在一棵非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊()。A、只有右子樹上的所有結(jié)點(diǎn)B、只有右子樹上的部分結(jié)點(diǎn)C、只有左子樹上的部分結(jié)點(diǎn)D、只有左子樹上的所有結(jié)點(diǎn)標(biāo)準(zhǔn)答案：A知識點(diǎn)解析：考查中序遍歷。根據(jù)中序遍歷的定義可知，在輸出根結(jié)點(diǎn)后，才去中序遞歸地遍歷根結(jié)點(diǎn)的右子樹，因此根結(jié)點(diǎn)右邊只有右子樹上的所有結(jié)點(diǎn)。5、如右圖所示為一棵平衡二叉樹(字母不是關(guān)鍵字)，在結(jié)點(diǎn)D的右子樹上插入結(jié)點(diǎn)F后，會導(dǎo)致該平衡二叉樹失去平衡，則調(diào)整后的平衡二叉樹中平衡因子的絕對值為1的分支結(jié)點(diǎn)數(shù)為()。A、0B、1C、2D、3標(biāo)準(zhǔn)答案：B知識點(diǎn)解析：考查平衡二叉樹的旋轉(zhuǎn)。由于在結(jié)點(diǎn)A的右孩子(R)的右子樹(R)上插入新結(jié)點(diǎn)F，A的平衡因子由一1減至一2，導(dǎo)致以A為根的子樹失去平衡，需要進(jìn)行RR旋轉(zhuǎn)(左單旋)。RR旋轉(zhuǎn)的過程如上圖所示，將A的右孩子C向左上旋轉(zhuǎn)代替A成為根結(jié)點(diǎn)，將A結(jié)點(diǎn)向左下旋轉(zhuǎn)成為C的左子樹的根結(jié)點(diǎn)，而C的原來的左子樹E則作為A的右子樹。故，調(diào)整后的平衡二叉樹中平衡因子的絕對值為1的分支結(jié)點(diǎn)數(shù)為1。注意：平衡旋轉(zhuǎn)的操作都是在插入操作后，引起不平衡的最小不平衡子樹上進(jìn)行的，只要將這個(gè)最小不平衡子樹調(diào)整平衡，則其上級結(jié)點(diǎn)也將恢復(fù)平衡。6、下列說法中，正確的是()。A、對于有n個(gè)結(jié)點(diǎn)的二叉樹，其高度為[log2n]B、完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有左孩子，則它必是葉結(jié)點(diǎn)C、高度為h(h＞0)的完全二叉樹對應(yīng)的森林所含的樹的個(gè)數(shù)一定是hD、一棵樹中的葉子數(shù)一定等于其對應(yīng)的二叉樹的葉子數(shù)標(biāo)準(zhǔn)答案：B知識點(diǎn)解析：若結(jié)點(diǎn)數(shù)為n的二叉樹是一棵單支樹，其高度為n，只有完全二叉樹才具有A性質(zhì)。完全二叉樹中最多只存在一個(gè)度為1的結(jié)點(diǎn)且該結(jié)點(diǎn)只有左孩子，若不存在左孩子，則一定也不存在右孩子，因此必是葉結(jié)點(diǎn)，B正確。只有滿二叉樹才具有C性質(zhì)，如下圖所示：在樹轉(zhuǎn)換為二叉樹時(shí)，若有幾個(gè)葉子結(jié)點(diǎn)有共同的雙親結(jié)點(diǎn)，則轉(zhuǎn)換為二叉樹后只有一個(gè)葉子(最右邊的葉子)，如下圖所示，D錯(cuò)誤。7、以下關(guān)于圖的敘述中，正確的是()。A、強(qiáng)連通有向圖的任何頂點(diǎn)到其他所有頂點(diǎn)都有弧B、圖與樹的區(qū)別在于圖的邊數(shù)大于或等于頂點(diǎn)數(shù)C、無向圖的連通分量指無向圖中的極大連通子圖D、假設(shè)有圖G={V，{E}}，頂點(diǎn)集，則V’和{E’}構(gòu)成G的子圖標(biāo)準(zhǔn)答案：C知識點(diǎn)解析：考查圖的基本性質(zhì)。強(qiáng)連通有向圖的任何頂點(diǎn)到其他所有頂點(diǎn)都有路徑，但未必有弧，A錯(cuò)誤。圖與樹的區(qū)別是邏輯上的，而不是邊數(shù)的區(qū)別，圖的邊數(shù)也可能小于樹的邊數(shù)。若E’中的邊對應(yīng)的頂點(diǎn)不是V’中的元素時(shí)，則V’和{E’}無法構(gòu)成圖，D錯(cuò)誤。8、如右圖所示，在下面的5個(gè)序列中，符合深度優(yōu)先遍歷的序列有多少個(gè)()。1．a(chǎn)ebfdc2．a(chǎn)cfdeb3．a(chǎn)edfcb4．a(chǎn)efdbc5．a(chǎn)ecfdbA、5B、4C、3D、2標(biāo)準(zhǔn)答案：D知識點(diǎn)解析：考查圖的深度優(yōu)先遍歷。僅1和4正確。以2為例，遍歷到c之后，與c鄰接且未被訪問的結(jié)點(diǎn)為空集，所以a的鄰接點(diǎn)b或e入棧，顯然2不符合這種情況。以3為例，因?yàn)楸闅v要按棧退回，所以是先b后c，而不是先c后b。9、一組數(shù)據(jù)(30,20,10,15,35,1,10,5)，用堆排序(小頂堆)的篩選方法建立的初始堆為()。A、1,5,15,20,35,10,30,10B、1,10,30,10,5,15,35,20C、1,5,10,15,35,30,10,20D、A、B和C均不正確標(biāo)準(zhǔn)答案：C知識點(diǎn)解析：考查初始堆的建立。首先對以第「n／2」個(gè)結(jié)點(diǎn)為根的子樹(也即最后一個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)為根的子樹)篩選，使該子樹成為堆，之后向前依次對各結(jié)點(diǎn)為根的子樹進(jìn)行篩選，直到篩選到根結(jié)點(diǎn)。從「n／2」～1依次篩選堆的過程如下圖所示：10、串’acaba’的next數(shù)組值為()。A、01234B、01212C、01121D、01230標(biāo)準(zhǔn)答案：C知識點(diǎn)解析：考查串的next數(shù)組。(1)設(shè)next[1]=0，next[2]=1。(2)當(dāng)j=3，此時(shí)k=next[j—1]=—next[2]=1，觀察S[2]與S[k](S[1])是否相等，S[2]=c，S[1]=a，S[2]=S[1]，此時(shí)k=next[k]=0，所以next[j]=1。(3)當(dāng)j=4，此時(shí)k=next[j—1]=next[3]=1，觀察S[3]與S[k](S[1])是否相等，S[3]=a，S[1]=a，S[2]=S[1]，所以next[j]=k+1=2。(4)當(dāng)j=5，此時(shí)k=next[j—1]=next[4]=2，觀察S[4]與S[k](S[2])是否相等，S[4]=b，S[2]=c，S[4]!=S[2]，所以k=next[k]=1。(5)此時(shí)S[k]=S[1]=a，S[4]!=S[1]，所以k=next[k]=next[1]=0，所以next[j]=1。此時(shí)可知next數(shù)組為01121，選C。11、一組經(jīng)過第一趟2．路歸并排序后的記錄的關(guān)鍵字為(25,50,15,35,80,85,20,40,36,70)，其中包含5個(gè)長度為2的有序表，用2．路歸并排序方法對該序列進(jìn)行第二趟歸并后的結(jié)果為()。A、15,25,35,50,80,20,85,40,70,36B、15,25,35,50,20,40,80,85,36,70C、15,25,50,35,80,85,20,36,40,70D、15,25,35,50,80,20,36,40,70,85標(biāo)準(zhǔn)答案：B知識點(diǎn)解析：考查歸并排序的執(zhí)行過程。第一趟歸并時(shí)，將每個(gè)關(guān)鍵字看成一個(gè)有序表，兩兩進(jìn)行歸并；第二趟歸并時(shí)，將第一趟結(jié)果的5個(gè)長度為2的有序表歸并，得到2個(gè)長度為4的有序表和1個(gè)長度為2的有序表。由于這里是采用2．路歸并，而且是第二趟排序，所以每4個(gè)元素放在一起歸并，可將序列劃分為{25,50,15,35}，{80,85,20,40}和{36,70}，分別對它們進(jìn)行排序?yàn)閧15,25,35,50}，{20,40,80,85}和{36,70}。注意：區(qū)分遞歸和非遞歸的歸并排序。12、已知一臺時(shí)鐘頻率為2GHz的計(jì)算機(jī)的CPI為1．2。某程序P在該計(jì)算機(jī)上的指令條數(shù)為4×109條。若在該計(jì)算機(jī)上，程序P從開始啟動到執(zhí)行結(jié)束所經(jīng)歷的時(shí)間是4s，則運(yùn)行P所用CPU時(shí)間占整個(gè)CPU時(shí)間的百分比大約是()o，A、40％B、60％C、80％D、100％標(biāo)準(zhǔn)答案：B知識點(diǎn)解析：本題考查根據(jù)時(shí)鐘頻率、指令條數(shù)和CPI來計(jì)算程序執(zhí)行時(shí)間。程序的執(zhí)行時(shí)間=(指令條數(shù)×CPI)／主頻=1．2×4×109／2GHz=2．4s，所占百分比為(2．4／4)×100％=60％。13、在補(bǔ)碼表示的機(jī)器中，若寄存器R中原來存的數(shù)為9EH，執(zhí)行一條指令后現(xiàn)存的數(shù)為CFH，則表明該指令不可能是()。A、XOR異或運(yùn)算指令B、IMUL有符號數(shù)乘法指令C、SAR算術(shù)右移指令D、ADD加法指令標(biāo)準(zhǔn)答案：B知識點(diǎn)解析：本題考查進(jìn)制數(shù)的轉(zhuǎn)換以及各種運(yùn)算操作。將寄存器R的前、后內(nèi)容轉(zhuǎn)為二進(jìn)制：10011110和11001111。XOR指令，和0101000l異或即可，A正確；SAR指令，算術(shù)右移一位可以得到結(jié)果，C正確；ADD指令，加上31H即可，D正確。有符號乘法指令則找不到可以相乘的整數(shù)，B錯(cuò)誤。14、下列關(guān)于浮點(diǎn)數(shù)的說法中，正確的是()。Ⅰ．最簡單的浮點(diǎn)數(shù)舍入處理方法是恒置“1”法Ⅱ．IEEE754標(biāo)準(zhǔn)的浮點(diǎn)數(shù)進(jìn)行乘法運(yùn)算的結(jié)果肯定不需要做“左規(guī)”處理Ⅲ．浮點(diǎn)數(shù)加減運(yùn)算的步驟中，對階的處理原則是小階向大階對齊Ⅳ．當(dāng)補(bǔ)碼表示的尾數(shù)的最高位與尾數(shù)的符號位(數(shù)符)相同時(shí)表示規(guī)格化Ⅴ．在浮點(diǎn)運(yùn)算過程中如果尾數(shù)發(fā)生溢出，則應(yīng)進(jìn)入相應(yīng)的中斷處理A、Ⅱ、Ⅲ和ⅤB、Ⅱ和ⅢC、Ⅰ、Ⅱ和ⅢD、Ⅱ、Ⅲ、Ⅳ和Ⅴ標(biāo)準(zhǔn)答案：B知識點(diǎn)解析：本題考查浮點(diǎn)數(shù)的運(yùn)算。最簡單的舍入處理方法是直接截?cái)?，不進(jìn)行任何其他處理(截?cái)喾?，Ⅰ錯(cuò)誤。IEEE754標(biāo)準(zhǔn)的浮點(diǎn)數(shù)的尾數(shù)都是大于等于1的，所以乘法運(yùn)算的結(jié)果也是大于等于1，故不需要“左規(guī)”(注意：有可能需要右規(guī))，Ⅱ正確；對階的原則是小階向大階看齊，Ⅲ正確。當(dāng)補(bǔ)碼表示的尾數(shù)的最高位與尾數(shù)的符號位(數(shù)符)相異時(shí)表示規(guī)格化，Ⅳ錯(cuò)誤。浮點(diǎn)運(yùn)算過程中，尾數(shù)出現(xiàn)溢出并不表示真正的溢出，只有將此數(shù)右歸后，再根據(jù)階碼判斷是否溢出，Ⅴ錯(cuò)誤。注意：浮點(diǎn)數(shù)運(yùn)算的過程分為對階、尾數(shù)求和、規(guī)格化、舍入和溢出判斷，每個(gè)過程的細(xì)節(jié)均需掌握，本題的5個(gè)選項(xiàng)涉及到了這5個(gè)過程。15、下列的說法中，正確的是()。Ⅰ．雙端口存儲器可以同時(shí)訪問同一區(qū)間、同一單元Ⅱ．雙端口存儲器當(dāng)兩個(gè)端口的地址碼相同時(shí)，必然會發(fā)生沖突Ⅲ．高位多體交叉存儲器的設(shè)計(jì)依據(jù)了程序的局部性原理Ⅳ．高位四體交叉存儲器可能在一個(gè)存儲周期內(nèi)連續(xù)訪問四個(gè)模塊A、Ⅰ和ⅢB、Ⅱ和ⅢC、Ⅰ和ⅣD、只有Ⅰ標(biāo)準(zhǔn)答案：C知識點(diǎn)解析：本題考查雙端口存儲器和交叉存儲器的特點(diǎn)。雙端口RAM的兩個(gè)端口具有2組相互獨(dú)立的地址線、數(shù)據(jù)線和讀寫控制線，因此可以同時(shí)訪問同一區(qū)間、同一單元，Ⅰ正確，但是其中任一個(gè)端口都不可有寫操作；當(dāng)兩個(gè)端口同時(shí)對相同的單元進(jìn)行讀操作時(shí)，則不會發(fā)生沖突，Ⅱ錯(cuò)誤。高位多體交叉存儲器由于在單個(gè)存儲器中字是連續(xù)存放的，所以不能保證程序的局部性原理；而低位多體交叉存儲器由于是交叉存放，所以能很好地滿足程序的局部性原理，ⅡI錯(cuò)誤。高位四體交叉存儲器雖然不能滿足程序的連續(xù)讀取，但仍可能一次連續(xù)讀出彼此地址相差一個(gè)存儲體容量的4個(gè)字，只是這么讀的概率較小，Ⅳ正確。注意：高位多體交叉存儲器仍然是順序存儲器。16、下列說法中，錯(cuò)誤的是()。Ⅰ．虛擬存儲器技術(shù)提高了計(jì)算機(jī)的速度Ⅱ．存取時(shí)間是指連續(xù)兩次讀操作所需的最小時(shí)間間隔Ⅲ．Cache與主存統(tǒng)一編址，Cache的地址空間是主存地址空間的一部分Ⅳ．主存都是由易失性的隨機(jī)讀寫存儲器構(gòu)成的A、Ⅱ和ⅢB、Ⅲ和ⅣC、Ⅰ、Ⅱ和ⅣD、Ⅰ、Ⅱ、Ⅲ和Ⅳ標(biāo)準(zhǔn)答案：D知識點(diǎn)解析：考查存儲器的多個(gè)知識點(diǎn)。實(shí)際上，虛存是為了解決多道程序并行條件下的內(nèi)存不足而限制了程序最多運(yùn)行的道數(shù)而提出的，即為了解決內(nèi)存不足，虛擬存儲器進(jìn)行虛實(shí)地址轉(zhuǎn)換，需要多次訪存(先查找頁表)，增加了延遲，降低了計(jì)算機(jī)速度，是一種時(shí)間換空間的做法，Ⅰ錯(cuò)誤。Ⅱ描述的是存取周期的概念，Ⅱ錯(cuò)誤。Cache有自己獨(dú)立的地址空間，通過不同的映射方式映射到主存的地址空間，Ⅲ錯(cuò)誤。主存也可以由ROM組成，如可用于部分操作系統(tǒng)的固化固話、自舉程序等，Ⅳ錯(cuò)誤。注：虛存和Cache都是計(jì)算機(jī)存儲體系中重要的部分，它們的區(qū)別和聯(lián)系一定要弄清楚，虛存是為了解決內(nèi)存不足提出的，即是容量問題，使用一部分的輔存來對內(nèi)存進(jìn)行一定的擴(kuò)充，但是這樣會導(dǎo)致整體速度的下降，是用時(shí)間換空間的做法；而Cache則是為了緩和CPU與主存的矛盾而設(shè)立的，會提高整個(gè)存儲體系的速度，是一種用金錢換時(shí)間的做法。17、虛擬存儲器中的頁表有快表和慢表之分，下面關(guān)于頁表的敘述中正確的是()。A、快表與慢表都存儲在主存中，但快表比慢表容量小B、快表采用了優(yōu)化的搜索算法，因此查找速度快C、快表比慢表的命中率高，因此快表可以得到更多的搜索結(jié)果D、快表采用高速存儲器件組成，按照查找內(nèi)容訪問，因此比慢表查找速度快標(biāo)準(zhǔn)答案：D知識點(diǎn)解析：本題考查快表和慢表的關(guān)系?？毂碛址QTLB，采用高速相聯(lián)存儲器來存儲可能需要使用的頁的對應(yīng)表項(xiàng)。而慢表存儲在內(nèi)存中?？毂聿捎玫氖窍嗦?lián)存儲器，它的速度快來源于硬件本身，而不是依賴搜索算法來查找的，慢表通常是依賴于查找算法，故A和B錯(cuò)誤?？毂砼c慢表的命中率沒有必然聯(lián)系，快表僅是慢表的一個(gè)部分拷貝，不能夠得到比慢表更多的結(jié)果，因此C錯(cuò)誤。18、在計(jì)算機(jī)體系結(jié)構(gòu)中，CPU內(nèi)部包括程序計(jì)數(shù)器PC、存儲器數(shù)據(jù)寄存器MDR、指令寄存器IR和存儲器地址寄存器MAR等。若CPU要執(zhí)行的指令為：MOVR0，#100(即將數(shù)值100傳送到寄存器R0中)，則CPU首先要完成的操作是()。A、100—>R0B、100—>MDRC、PC—>MARD、PC—>IR標(biāo)準(zhǔn)答案：C知識點(diǎn)解析：本題考查取指周期完成的操作。CPU首先需要取指令，取指令階段的第一個(gè)操作就是將指令地址(程序計(jì)數(shù)器PC中的內(nèi)容)送往存儲器地址寄存器。題干中雖然給出了一條具體的指令“MOVR0，#100”，實(shí)際上CPU首先要完成的操作是取指令，與具體指令是沒有關(guān)系的。注意：取指周期完成的微操作序列是公共的操作，與具體指令無關(guān)。19、下列關(guān)于微指令編碼方式的說法中，錯(cuò)誤的是()。Ⅰ．字段直接編碼可以用較少的二進(jìn)制信息表示較多的微操作命令信號，例如有兩組互斥微命令中，微命令個(gè)數(shù)分別為8和9，則只分別需要3位和4為即可表示Ⅱ．直接編碼無須進(jìn)行譯碼，微指令的微命令字段中每一位都代表一個(gè)微命令Ⅲ．垂直型微指令以較長的微程序結(jié)構(gòu)換取較短的微指令結(jié)構(gòu)，因而執(zhí)行效率高、靈活性強(qiáng)都高于水平型微指令Ⅳ．字段間接編碼中，一個(gè)字段的譯碼輸出需要依靠另外某一個(gè)字段的輸入A、Ⅰ、Ⅲ和ⅣB、Ⅱ、Ⅲ和ⅣC、Ⅱ和ⅣD、Ⅰ、Ⅱ、Ⅲ和Ⅳ標(biāo)準(zhǔn)答案：A知識點(diǎn)解析：本題考查微指令的編碼方式。編碼的是對微指令的控制字段進(jìn)行編碼，以形成控制信號；目的是在保證速度的情況下，盡量縮短微指令字長。微命令個(gè)數(shù)為8時(shí)，需要4位，假設(shè)只用3位，將會造成每個(gè)編碼都會輸出一個(gè)微命令，事實(shí)上，微命令的編碼需要預(yù)留一個(gè)字段表示不輸出，I錯(cuò)誤。垂直型微指令的缺點(diǎn)是微程序長、執(zhí)行速度慢、工作效率低，Ⅲ錯(cuò)誤。字段間接編碼中的一個(gè)字段的某些微命令還需由另一個(gè)字段中的某些微命令來解釋，即受到某一個(gè)字段的譯碼輸出，Ⅳ錯(cuò)誤。一般進(jìn)行微程序控制器的設(shè)計(jì)時(shí)要注意三個(gè)原則：①微指令字長盡可能短②微程序長度盡可能短③提高微程序的執(zhí)行速度20、在系統(tǒng)總線中，地址總線的位數(shù)與()相關(guān)。A、機(jī)器字長B、實(shí)際存儲單元個(gè)數(shù)C、存儲字長D、存儲器地址寄存器標(biāo)準(zhǔn)答案：D知識點(diǎn)解析：本題考查地址總線。地址總線的位數(shù)和實(shí)際存儲單元個(gè)數(shù)、機(jī)器字長還有儲存字長都是無關(guān)的，如32位的地址線，可以僅僅用2GB的內(nèi)存。而MAR的位數(shù)和其是相關(guān)的，一般這二者是相等的。注意：地址總線的位數(shù)和最大存儲單元個(gè)數(shù)相關(guān)，也和MAR的位數(shù)相關(guān)。地址總線的寬度決定了CPU可以訪存的最大物理地址空間。如32位的地址線，按字節(jié)尋址的可尋址的最大容量為232bit=4GB。關(guān)于計(jì)算機(jī)各個(gè)字長以及總線長度的關(guān)系可以總結(jié)如下：機(jī)器字長是指計(jì)算機(jī)進(jìn)行一次運(yùn)算所能處理的二進(jìn)制數(shù)據(jù)的位數(shù)。機(jī)器字長也就是運(yùn)算器進(jìn)行定點(diǎn)數(shù)運(yùn)算的字長，通常也是CPU內(nèi)部數(shù)據(jù)通路的寬度，也等于CPU內(nèi)通用寄存器的位數(shù)；另外，CPU的位數(shù)和操作系統(tǒng)的位數(shù)沒有絕對的關(guān)系，但是CPU的位數(shù)一定要大于等于操作系統(tǒng)的位數(shù)。存儲字長是指一個(gè)存儲單元存儲一串二進(jìn)制代碼(存儲字)的位數(shù)。指令字長是指機(jī)器指令中二進(jìn)制代碼的總位數(shù)。指令字長取決于從操作碼的長度、操作數(shù)地址的長度和操作數(shù)地址的個(gè)數(shù)。指令還分為變長型和定長型，對于變長型指令，不同類型指令的字長是不同的，不過通常都是存儲字長的整數(shù)倍?？偩€(指的是非CPU內(nèi)部總線)一般分為控制總線、地址總線和數(shù)據(jù)總線(當(dāng)然，有些總線結(jié)構(gòu)中把地址和數(shù)據(jù)總線融合再一起進(jìn)行時(shí)分復(fù)用，以周期的不同來區(qū)分傳送的是地址還是數(shù)據(jù)，這種做法可以有效地減少總線寬度)?？刂瓶偩€的數(shù)目一般是等于CPU需要向外傳遞控制信號的數(shù)目，當(dāng)然也可以把一些互斥的控制信號放在一根控制總線中；而地址總線的數(shù)目一般等于地址寄存器的數(shù)目，而按字節(jié)編址的系統(tǒng)的內(nèi)存最大容量不應(yīng)超過2nB(n為地址寄存器的位數(shù))，但是它和內(nèi)存容量本身并沒有任何必然聯(lián)系；數(shù)據(jù)總線一般等于數(shù)據(jù)寄存器的位數(shù)(數(shù)據(jù)寄存器的位數(shù)又一般等于CPU的位數(shù))，但是也并非絕對，因?yàn)镃PU可以用少于該位數(shù)的總線(比如位數(shù)的二分之一)分周期(對應(yīng)的就是兩個(gè)傳送周期)來傳送一次數(shù)據(jù)。21、關(guān)于外中斷(故障除外)和DMA，下列哪個(gè)說法是正確的()。Ⅰ．DMA請求和中斷請求同時(shí)發(fā)生時(shí)，響應(yīng)DMA請求Ⅱ．DMA請求、非屏蔽中斷、可屏蔽中斷都要在當(dāng)前指令結(jié)束之后才能被響應(yīng)Ⅲ．非屏蔽中斷請求優(yōu)先級最高，可屏蔽中斷請求優(yōu)先級最低Ⅳ．如果不開中斷，所有中斷請求均不能響應(yīng)Ⅴ．在DMA方式中，數(shù)據(jù)的傳送完全不用CPU干預(yù)A、Ⅰ和ⅤB、Ⅰ和ⅣC、ⅠD、Ⅱ和Ⅲ標(biāo)準(zhǔn)答案：C知識點(diǎn)解析：本題考查外中斷方式和DMA方式的區(qū)別。和中斷方式相比，DMA連接的是高速設(shè)備，其優(yōu)先級高于中斷請求，以防止數(shù)據(jù)丟失，Ⅰ正確。DMA請求的響應(yīng)時(shí)間可以發(fā)生在每個(gè)機(jī)器周期結(jié)束時(shí)，只要CPU不占用總線，而中斷請求的響應(yīng)時(shí)間只能發(fā)生在每條指令執(zhí)行完畢，Ⅱ錯(cuò)誤。通常情況下，DMA的優(yōu)先級要高于外中斷，所以DMA優(yōu)先級一般要比非屏蔽中斷請求要高，Ⅲ錯(cuò)誤。如果不開中斷，非屏蔽中斷(以及內(nèi)中斷)仍可響應(yīng)，Ⅳ錯(cuò)誤。在．DMA方式的預(yù)處理和后處理中，需要CPU的干預(yù)，只是在傳送的過程中不需要CPU的干預(yù)，Ⅴ錯(cuò)誤。注意：中斷方式具有對異常時(shí)間的處理能力，而DMA方式僅局限于完成傳送數(shù)據(jù)塊的能力。22、通道方式的工作過程中，下列步驟的正確順序是()。①組織I／O操作②向CPU發(fā)出中斷請求③編制通道程序④啟動I／O通道A、①→②→③→④B、②→③→①→④C、④→③→②→①D、③→④→①→②標(biāo)準(zhǔn)答案：D知識點(diǎn)解析：考查通道的工作過程。通道的基本工作過程(以一次數(shù)據(jù)傳送為例)如下：①在用戶程序中使用訪管指令進(jìn)入操作系統(tǒng)管理程序，由CPIU通過管理程序組織一個(gè)通道程序，并使用I／O指令啟動通道(此后CPU并行運(yùn)行應(yīng)用程序)。②通道處理器執(zhí)行CPU為其組織的通道程序，完成指定的數(shù)據(jù)的輸入／輸出工作。③通道程序結(jié)束后，向CPU發(fā)出中斷請求。CPU響應(yīng)此中斷請求后，第二次進(jìn)入操作系統(tǒng)，調(diào)用管理程序?qū)斎耄敵鲋袛噙M(jìn)行處理。23、多用戶系統(tǒng)有必要保證進(jìn)程的獨(dú)立性，保證操作系統(tǒng)本身的安全，但為了向用戶提供更大的靈活性，應(yīng)盡可能少地限制用戶進(jìn)程。下面列出的各操作中，()是必須加以保護(hù)的。A、從內(nèi)核(kernel)模式轉(zhuǎn)換到用戶(user)模式B、從存放操作系統(tǒng)內(nèi)核的空間讀取數(shù)據(jù)C、從存放操作系統(tǒng)內(nèi)核的空間讀取指令D、打開定時(shí)器標(biāo)準(zhǔn)答案：D知識點(diǎn)解析：本題考查用戶態(tài)與核心態(tài)。打開定時(shí)器屬于時(shí)鐘管理的內(nèi)容，對時(shí)鐘的操作必須加以保護(hù)，否則，一個(gè)用戶進(jìn)程可以在時(shí)間片還未到之前把時(shí)鐘改回去，從而導(dǎo)致時(shí)間片永遠(yuǎn)不會用完，那么該用戶進(jìn)程就可以一直占用CPU，這顯然不合理。從用戶模式到內(nèi)核模式是通過中斷實(shí)現(xiàn)的，中斷的處理過程很復(fù)雜，需要加以保護(hù)，但從內(nèi)核模式到用戶模式則不需要加以保護(hù)。讀取操作系統(tǒng)內(nèi)核的數(shù)據(jù)和指令是靜態(tài)操作，顯然無需加以保護(hù)。24、下列關(guān)于進(jìn)程狀態(tài)的說法中，正確的是()。Ⅰ．從運(yùn)行態(tài)到阻塞態(tài)的轉(zhuǎn)換是進(jìn)程的“自主”行為Ⅱ．從阻塞態(tài)到就緒態(tài)的轉(zhuǎn)換是由協(xié)作進(jìn)程決定的Ⅲ．一次I／O操作的結(jié)束，將會導(dǎo)致一個(gè)進(jìn)程由就緒變?yōu)檫\(yùn)行Ⅳ．一個(gè)運(yùn)行的進(jìn)程用完了分配給它的時(shí)間片后，它的狀態(tài)變?yōu)樽枞酰谶M(jìn)程狀態(tài)轉(zhuǎn)換中，“就緒一阻塞"是不可能發(fā)生的A、Ⅰ、Ⅱ和ⅢB、Ⅰ、Ⅱ和ⅤC、Ⅰ、Ⅱ和ⅣD、Ⅰ、Ⅱ、Ⅲ和Ⅴ標(biāo)準(zhǔn)答案：B知識點(diǎn)解析：本題考查進(jìn)程的狀態(tài)與轉(zhuǎn)換。從運(yùn)行態(tài)到阻塞態(tài)的轉(zhuǎn)換是由進(jìn)程自身決定的，它是由于進(jìn)程的時(shí)間片用完，“主動”調(diào)用程序轉(zhuǎn)入就緒態(tài)。進(jìn)程的阻塞和喚醒是由block和wakeup原語實(shí)現(xiàn)的，block原語是由被阻塞進(jìn)程自我調(diào)用實(shí)現(xiàn)的，而wakeup原語則是由一個(gè)與被喚醒進(jìn)程相合作或其他相關(guān)的進(jìn)程調(diào)用實(shí)現(xiàn)的，故Ⅰ和Ⅱ正確。I／O操作結(jié)束不會直接導(dǎo)致一個(gè)進(jìn)程從就緒變?yōu)檫\(yùn)行，只是當(dāng)有等待該設(shè)備的進(jìn)程時(shí)，I／O操作結(jié)束時(shí)會把該進(jìn)程由阻塞變?yōu)榫途w，Ⅲ錯(cuò)誤。一個(gè)進(jìn)程時(shí)間片到了以后，將會從運(yùn)行變?yōu)榫途w狀態(tài)，Ⅳ錯(cuò)誤。只有在運(yùn)行中的進(jìn)程當(dāng)請求某一資源或等待某一事件時(shí)，才會轉(zhuǎn)入到阻塞態(tài)，因此不可能直接從就緒態(tài)轉(zhuǎn)到阻塞態(tài)，Ⅴ正確。答案選B。25、設(shè)有3個(gè)作業(yè)，它們的到達(dá)時(shí)間和運(yùn)行時(shí)間如下表所示，并在一臺處理機(jī)上按單道方式運(yùn)行。如按高響應(yīng)比優(yōu)先算法，則作業(yè)執(zhí)行的次序和平均周轉(zhuǎn)時(shí)間依次為()。A、J1,J2,J3、1．73B、J1,J3,J2、1．83C、J1,J3,J2、2．08D、J1,J2,J3、1．83標(biāo)準(zhǔn)答案：B知識點(diǎn)解析：本題考查高響應(yīng)比優(yōu)先調(diào)度和平均周轉(zhuǎn)時(shí)間。高響應(yīng)比優(yōu)先調(diào)度算法綜合考慮了進(jìn)程的等待時(shí)間和執(zhí)行時(shí)間，響應(yīng)比=(等待時(shí)間+執(zhí)行時(shí)間)／執(zhí)行時(shí)間。J1第一個(gè)提交，也第一個(gè)執(zhí)行，J1在10：00執(zhí)行完畢，這時(shí)J2、J3都已到達(dá)。J2的響應(yīng)比=(1．5+l、)／1=2．5，J3的響應(yīng)比=(0．5+0．25)／’0．25=3，故第二個(gè)執(zhí)行J3；第三個(gè)執(zhí)行J2。平均周轉(zhuǎn)時(shí)間=(J1的周轉(zhuǎn)時(shí)間+J2的周轉(zhuǎn)時(shí)間+J3的周轉(zhuǎn)時(shí)間)／3=[2+(1．75+1)+(0．5+0．25)]／3=5．5／3=1．83。26、設(shè)有n個(gè)進(jìn)程共用一個(gè)相同的程序段，假設(shè)每次最多允許m個(gè)進(jìn)程(m≤n)同時(shí)進(jìn)入臨界區(qū)，則信號量S的初值為()。A、mB、nC、m—nD、—m標(biāo)準(zhǔn)答案：A知識點(diǎn)解析：本題考查互斥信號量的設(shè)置。互斥信號量的初值應(yīng)為可用資源數(shù)，在本題中為可同時(shí)進(jìn)入臨界區(qū)的資源數(shù)。每當(dāng)一個(gè)進(jìn)程進(jìn)入臨界區(qū)，S減1，減到—(n—m)為止，此時(shí)共有｜S｜個(gè)進(jìn)程在等待進(jìn)入。27、利用銀行家算法進(jìn)行安全序列檢查時(shí)，不需要的參數(shù)是()。A、系統(tǒng)資源總數(shù)B、滿足系統(tǒng)安全的最少資源數(shù)C、用戶最大需求數(shù)D、用戶己占有的資源數(shù)標(biāo)準(zhǔn)答案：B知識點(diǎn)解析：本題考查銀行家算法。安全性檢查一般要用到進(jìn)程所需的最大資源數(shù)，減去進(jìn)程占用的資源數(shù)，得到進(jìn)程為滿足進(jìn)程運(yùn)行尚需要的可能最大資源數(shù)，而系統(tǒng)擁有的最大資源數(shù)減去已分配掉的資源數(shù)得到剩余的資源數(shù)，比較剩余的資源數(shù)是否滿足進(jìn)程運(yùn)行尚需要的可能最大資源數(shù)就可以得到當(dāng)前狀態(tài)是否安全的結(jié)論。而滿足系統(tǒng)安全的最少資源數(shù)并沒有這么一個(gè)說法。28、在一個(gè)請求分頁系統(tǒng)中，采用LRU頁面置換算法時(shí)，假如一個(gè)作業(yè)的頁面走向?yàn)?，3，2，1，1，3，5，1，3，2，1，5。當(dāng)分配給該作業(yè)的物理塊數(shù)分別為3和4時(shí)，則在訪問過程中所發(fā)生的缺頁率分別為()。A、50％、33％B、25％、100％C、25％、33％D、50％、75％標(biāo)準(zhǔn)答案：A知識點(diǎn)解析：本題考查頁面置換的相關(guān)計(jì)算。當(dāng)物理塊數(shù)為3時(shí)，缺頁情況如下表所示：缺頁次數(shù)為6，缺頁率為6／12=50％。當(dāng)物理塊數(shù)為4時(shí)，缺頁情況如下表所示：缺頁次數(shù)為4，缺頁率為4／12=33％。29、如下程序在頁式虛存系統(tǒng)中執(zhí)行，程序代碼位于虛空間O頁，A為128"128的數(shù)組，在虛空間以行為主序存放，每頁存放128個(gè)數(shù)組元素。工作集大小為2個(gè)頁框(開始時(shí)程序代碼已在內(nèi)存，占1個(gè)頁框)，用LRU算法，下面兩種對A初始化的程序引起的頁故障數(shù)分別為()。程序1：for(j=1；J＜=128；J++)for(i=1，i＜=128；i++)A[i][j]=0；程序2：for(i=1，i＜=128；i++)for(j=1，j＜=128；J++)A[i][j]=0；A、128*128，128B、128，12*128C、64，64*64D、64*64，64標(biāo)準(zhǔn)答案：A知識點(diǎn)解析：本題考查缺頁中斷的計(jì)算。進(jìn)程的工作集是2個(gè)頁框，其中一個(gè)頁框始終被程序代碼占用，所以可供數(shù)據(jù)使用的內(nèi)存空間只有一個(gè)頁框。在虛空間以行為主序存放，每頁存放128個(gè)數(shù)組元素，所以每一行占～頁。程序1訪問數(shù)組的方式為先行后列，每一次訪問都是針對不同的行，所以每一次都會產(chǎn)生缺頁中斷，一共128×128次。程序2訪問數(shù)組的方式是先列后行，每次訪問不同行時(shí)會產(chǎn)生缺頁中斷，一共128次。30、現(xiàn)代操作系統(tǒng)中，文件系統(tǒng)都有效地解決了文件重名(即允許不同用戶的文件可以具有相同的文件名)問題，系統(tǒng)是通過()來實(shí)現(xiàn)這一功能的。A、重名翻譯機(jī)構(gòu)B、建立索引表C、樹型目錄結(jié)構(gòu)D、建立指針標(biāo)準(zhǔn)答案：C知識點(diǎn)解析：本題考查文件的目錄結(jié)構(gòu)。樹型目錄結(jié)構(gòu)解決了多用戶之間的文件命名問題，即在不同目錄下可以有相同的文件名。31、下列敘述中，錯(cuò)誤的是()。Ⅰ．索引順序文件也是一種特殊的順序文件，因此通常存放在磁帶上Ⅱ．索引順序文件既能順序訪問，又能隨機(jī)訪問Ⅲ．存儲在直接存取存儲器上面的文件也能順序訪問，但一般效率較差Ⅳ．在磁帶上的順序文件中添加新記錄時(shí)，必須復(fù)制整個(gè)文件A、Ⅰ和ⅣB、Ⅱ和ⅣC、Ⅰ和ⅡD、Ⅰ、Ⅱ和Ⅳ標(biāo)準(zhǔn)答案：A知識點(diǎn)解析：本題考查文件的物理結(jié)構(gòu)。對于Ⅰ，直接存取存儲器(磁盤)既不像RAM那樣隨機(jī)地訪問任一個(gè)存儲單元，也不像順序存取存儲器(如磁帶)那樣完全順序存取，而是介于兩者之間，存取信息時(shí)通常先尋找整個(gè)存儲器的某個(gè)小區(qū)域(如磁盤上的磁道)再在小區(qū)域順序查找。所以我認(rèn)為直接存取不完全等于隨機(jī)存取。索引順序文件如果存放在磁帶上，則無法實(shí)現(xiàn)隨機(jī)訪問，也就失去了索引的意義。Ⅱ顯然正確。磁盤上的文件可以直接訪問，也可以順序訪問，但如果順序訪問的話，就比較低效了，Ⅲ正確。對于Ⅳ，在順序文件的最后添加新的記錄時(shí)，則不必須復(fù)制整個(gè)文件。32、下列關(guān)于設(shè)備獨(dú)立性的論述中，正確的是()。A、設(shè)備獨(dú)立性是I／O設(shè)備具有獨(dú)立執(zhí)行I／O功能的一種特性B、設(shè)備獨(dú)立性是指用戶程序獨(dú)立于具體使用的物理設(shè)備的一種特性C、設(shè)備獨(dú)立性是指獨(dú)立實(shí)現(xiàn)設(shè)備共享的一種特性D、設(shè)備獨(dú)立性是指設(shè)備驅(qū)動獨(dú)立于具體使用的物理設(shè)備的一種特性標(biāo)準(zhǔn)答案：B知識點(diǎn)解析：本題考查設(shè)備獨(dú)立性的定義。設(shè)備獨(dú)立性的定義就是指用戶程序獨(dú)立于具體物理設(shè)備的一種特性，引入設(shè)備的獨(dú)立性是為了提高設(shè)備分配的靈活性和設(shè)備的利用率等。33、在OSI參考模型中，上層協(xié)議實(shí)體與下層協(xié)議實(shí)體之間的邏輯接口稱為服務(wù)訪問點(diǎn)(SAP)。在Intemet數(shù)據(jù)幀中，目的地址“0x000F781C6001”屬于()的服務(wù)訪問點(diǎn)。A、數(shù)據(jù)鏈路層B、網(wǎng)絡(luò)層C、傳輸層D、應(yīng)用層標(biāo)準(zhǔn)答案：A知識點(diǎn)解析：此題引用了OSI／RM中服務(wù)訪問點(diǎn)的概念，但考查的卻是TCP／IP參考模型的知識。在TCP／IP參考模型中，網(wǎng)絡(luò)接口層的SAP是MAC地址；在網(wǎng)際層(也可稱為網(wǎng)絡(luò)層)使用的是IP協(xié)議，其SAP便是IP地址；而傳輸層使用的主要協(xié)議為TCP和UDP，TCP使用的SAP是TCP的端口號，UDP使用的SAP是UDP的端口號。在Internet數(shù)據(jù)幀中，地址“0×000F781C6001”是一個(gè)48位的地址，在TCP／IP模型中，只有網(wǎng)絡(luò)設(shè)備(例如網(wǎng)卡和無線網(wǎng)卡)的物理地址是48位的，因此該地址屬于數(shù)據(jù)鏈路層的服務(wù)訪問點(diǎn)。34、一個(gè)傳輸數(shù)字信號的模擬信道的信號功率是0．62w，噪音功率是0．02w，頻率范圍是3．5～3．9MHz，該信道的最高數(shù)據(jù)傳輸速率是()。A、1MbpsB、2MbpsC、4MbpsD、8Mbps標(biāo)準(zhǔn)答案：B知識點(diǎn)解析：本題考查香農(nóng)定理的應(yīng)用。題干中已說明是有噪聲的信道，因此應(yīng)聯(lián)想到香農(nóng)定理，而對于無噪聲的信道，則應(yīng)聯(lián)想到奈奎斯特定理。首先計(jì)算信噪比S／N=0．62／0．02=31；帶寬W=3．9—3．5=0．4MHz，由香農(nóng)定理可知最高數(shù)據(jù)傳輸率V=W×log2(1+S／N)=0．4×log2(1+31)=2Mbps。35、在簡單停止-等待協(xié)議中，為了解決重復(fù)幀的問題，需要采用()。A、幀序號B、定時(shí)器C、ACK機(jī)制D、NAK機(jī)制標(biāo)準(zhǔn)答案：A知識點(diǎn)解析：本題考查簡單停止．等待協(xié)議機(jī)制。在停止等待協(xié)議中，如果在規(guī)定時(shí)間內(nèi)沒有收到接收方的確認(rèn)幀信息，發(fā)送方就會重新發(fā)送該幀，也就是發(fā)送了重復(fù)幀。為了避免因?yàn)橹貜?fù)幀引起不必要的錯(cuò)誤，簡單停止—等待協(xié)議采用了幀序號機(jī)制，即：在規(guī)定的時(shí)間內(nèi)未接收到確認(rèn)幀，即重新發(fā)送；此時(shí)接收到的幀為重復(fù)幀，而序號與前面一幀是相同的。接收端連續(xù)接收到的幀如果序號相同，則認(rèn)為是重復(fù)幀；如果幀序號不同，則理解為僅僅是內(nèi)容相同的不同的幀，所以A答案正確。有同學(xué)會選擇C答案，實(shí)際上ACK機(jī)制是用于TCP協(xié)議中的擁塞控制機(jī)制，并不是專門為了解決重復(fù)幀問題的。36、一個(gè)2Mbps的網(wǎng)絡(luò)，線路長度為1km,傳輸速度為20m／ms,分組大小為100字節(jié)，應(yīng)答幀大小可以忽略。若采用“停止一等待”協(xié)議，則實(shí)際數(shù)據(jù)速率是()。A、2MbpsB、1MbpsC、8KbpsD、16Kbps標(biāo)準(zhǔn)答案：C知識點(diǎn)解析：本題考查“停止—等待”協(xié)議的效率分析。停止．等待協(xié)議每發(fā)送完一個(gè)分組，需要收到確認(rèn)后才能發(fā)送下一個(gè)分組。發(fā)送延遲=8×100÷(2×1000000)=0．0004s，傳播延遲=1000m÷20m／ms=50ms=0．05s，最小間隔=0．0004s+0．05s×2=0．1004s。故數(shù)據(jù)速率=8×100bit÷0．1004s≈8Kbps。37、R1和R2是一個(gè)自治系統(tǒng)中采用RIP路由協(xié)議的兩個(gè)相鄰路由器，R1的路由表如表l所示，當(dāng)Rl收到R2發(fā)送的報(bào)文(見表2)后，R1更新的3個(gè)路由表項(xiàng)中距離值從上到下依次為()。A、0、4、3B、0、4、4C、0、5、3D、0、5、4標(biāo)準(zhǔn)答案：D知識點(diǎn)解析：對比表1和表2發(fā)現(xiàn)，R1到達(dá)目的網(wǎng)絡(luò)20．0．0．0的距離為7，而表2中R2到達(dá)目的網(wǎng)絡(luò)20．0．0．0的距離為4。由于7＞4+1，此時(shí)R1經(jīng)過R2到達(dá)目的網(wǎng)絡(luò)20．0．0．0的路由距離變短了，所以R1要根據(jù)R2提供的數(shù)據(jù)修改相應(yīng)路由項(xiàng)的距離值為5。R1到達(dá)目的網(wǎng)絡(luò)30．0．0．0的距離為4，而表2中R2到達(dá)目的網(wǎng)絡(luò)30．0．0．0的距離為3。由于4=3+1，顯然R1經(jīng)過R2到達(dá)目的網(wǎng)絡(luò)30．0．0．0，并不能得到更短的路由距離，所以R1無需進(jìn)行更新操作，將保持該路由表項(xiàng)原來的參數(shù)。當(dāng)R1收到R2發(fā)送的報(bào)文后，按照以下規(guī)律更新路由表信息：1)如果R1的路由表沒有某項(xiàng)路由記錄，則R1在路由表中增加該項(xiàng)，由于要經(jīng)過R2轉(zhuǎn)發(fā)，所以距離值要在R2提供的距離值基礎(chǔ)上加1。2)如果R1的路由表中的表項(xiàng)路由記錄比R2發(fā)送的對應(yīng)項(xiàng)的距離值加1還要大，則R1在路由表中修改該項(xiàng)，距離值根據(jù)R2提供的值加1。可見，對于路由器距離值為O的直連網(wǎng)絡(luò)，則無需進(jìn)行更新操作，其路由距離保持為0。38、路由器收到一個(gè)數(shù)據(jù)包，其目的地址為195．26．17．4，該地址屬于()子網(wǎng)。A、195．26．0．0／21B、195．26．16．0／20C、195．26．8．0／22D、195．26．20．0／22標(biāo)準(zhǔn)答案：B知識點(diǎn)解析：目的地址195．26．17．4轉(zhuǎn)換為二進(jìn)制的表達(dá)方式為：11000011．00011010．00010001．00000100。對該IP取20、21、22位的子網(wǎng)掩碼，就可以得到該IP所對應(yīng)的子網(wǎng)：195．26．16．0／20、195．26．16．0／21、195．26．16．0／22。從而可以得出該地址屬于195．26．16．0／20的子網(wǎng)。39、假設(shè)在沒有發(fā)生擁塞的情況下，在一條往返時(shí)間RTT為10ms的線路上采用慢開始控制策略。如果接收窗口的大小為24KB，最大報(bào)文段MSS為2KB。那么發(fā)送方能發(fā)送出一個(gè)完全窗口(也就是發(fā)送窗口達(dá)到24KB)需要的時(shí)間是()。A、30msB、60msC、50msD、40ms標(biāo)準(zhǔn)答案：D知識點(diǎn)解析：本題考查對TCP擁塞控制的慢開始算法的理解。按照慢開始算法，發(fā)送窗口的初始值為擁塞窗口的初始值即MSS的大小2KB，然后一次增大為4KB，8KB，16KB，然后是接收窗口的大小24KB，即達(dá)到第一個(gè)完全窗口。因此達(dá)到第一個(gè)完全窗口所需的時(shí)間為4×RTT=40ms。慢開始算法考慮了網(wǎng)絡(luò)容量與接收端容量，要求每個(gè)發(fā)送端維護(hù)2個(gè)窗口：接收窗口和擁塞窗口，兩個(gè)窗口的較小值就為發(fā)送窗口。所謂“慢開始”就是由小到大逐漸增大發(fā)送端的擁塞窗口數(shù)值。其基本原理是：在連接建立時(shí)，將擁塞窗口的大小初始化為一個(gè)MSS的大小，此后擁塞窗口每經(jīng)過一個(gè)RTT，就按指數(shù)規(guī)律增長一次，直到出現(xiàn)報(bào)文段傳輸超時(shí)或達(dá)到所設(shè)定的慢開始門限值ssthresh。四種擁塞控制算法是TCP協(xié)議的核心所在，解題時(shí)或畫出擁塞窗口變化曲線圖，或列出擁塞窗口大小變化序列，尤其要注意在拐點(diǎn)處的變化情況。40、一臺域名服務(wù)器希望解析域名www.google．com，如果這臺主機(jī)配置的DNS地址為a，Internet的根域名服務(wù)器為b，而存儲域名www．google．com與其IP地址對應(yīng)關(guān)系的域名服務(wù)器為c，那么這臺主機(jī)通常先查詢()。A、域名服務(wù)器aB、域名服務(wù)器bC、域名服務(wù)器cD、不確定標(biāo)準(zhǔn)答案：A知識點(diǎn)解析：本題考查域名解析的過程。主機(jī)發(fā)出DNS查詢報(bào)文時(shí)，該報(bào)文首先被送往該本地域名服務(wù)器。本地域名服務(wù)器不能立即回答該查詢時(shí)，就以DNS客戶的身份向某一根域名服務(wù)器查詢。若根域名服務(wù)器也沒有該主機(jī)的信息時(shí)(但此時(shí)其一定知道該主機(jī)的授權(quán)域名服務(wù)器的IP地址)，有兩種做法：1)遞歸查詢：根域名服務(wù)器向該主機(jī)的授權(quán)域名服務(wù)器發(fā)送DNS查詢報(bào)文，查詢結(jié)果再逐級返回給原主機(jī)；2)迭代查詢：根域名服務(wù)器把授權(quán)域名服務(wù)器的IP地址返回給本地域名服務(wù)器，由本地域名服務(wù)器再去查詢。不管采用何種查詢方式，首先都要查詢本地域名服務(wù)器。該主機(jī)配置的DNS地址a即為其本地域名服務(wù)器地址。二、綜合應(yīng)用題(本題共17題，每題1.0分，共17分。)41、對于一個(gè)堆棧、若其入棧序列為1，2,3，……，n，不同的出入棧操作將產(chǎn)生不同的出棧序列。其出棧序列的個(gè)數(shù)正好等于結(jié)點(diǎn)個(gè)數(shù)為n的二叉樹的個(gè)數(shù)，且與不同形態(tài)的二叉樹一一對應(yīng)。請簡要敘述一種從堆棧輸入(固定為1，2,3，……，n)／輸出序列對應(yīng)一種二叉樹形態(tài)的方法，并以入棧序列1，2，3(即n=3)為例加以說明。標(biāo)準(zhǔn)答案：由于二叉樹前序遍歷序列和中序遍歷序列可唯一確定一棵二叉樹。因此，若入棧序列為1,2,3，……，n相當(dāng)于前序遍歷序列是1,2,3，……n，出棧序列就是該前序遍歷對應(yīng)的二叉樹的中序序列的數(shù)目，而中序遍歷的過程實(shí)質(zhì)就是一個(gè)結(jié)點(diǎn)進(jìn)棧和出棧的過程。二叉樹的形態(tài)確定了結(jié)點(diǎn)進(jìn)棧和出棧的順序，也就確定了結(jié)點(diǎn)的中序序列。當(dāng)結(jié)點(diǎn)入棧序列為{1,2,3}時(shí)，出棧序列可能為：{3,2,1}，{2,3,1}，{2,1,3}，{1,3,2}，{1,2,3}，它們對應(yīng)二叉樹如下：【擴(kuò)展】進(jìn)棧出棧操作與二叉樹中序遍歷的關(guān)系：①一個(gè)結(jié)點(diǎn)進(jìn)棧后有兩種處理方式：要么立刻出棧(沒有左孩子)：或者下一個(gè)結(jié)點(diǎn)進(jìn)棧(有左孩子)。②一個(gè)結(jié)點(diǎn)出棧后也有兩種處理方式：要么繼續(xù)出棧(沒有右孩子)；或者下一個(gè)結(jié)點(diǎn)進(jìn)棧(有右孩子)。知識點(diǎn)解析：暫無解析已知一棵二叉樹采用二叉鏈表存儲，結(jié)點(diǎn)構(gòu)造為root指向根結(jié)點(diǎn)。請編寫算法判斷該二叉樹是否是平衡二叉樹，即二叉樹中任意結(jié)點(diǎn)的左右子樹的深度相差不超過1，例如下圖所示的二叉樹就是一棵平衡二叉樹。要求：42、給出算法的基本設(shè)計(jì)思想。標(biāo)準(zhǔn)答案：基本的基本設(shè)計(jì)思想：設(shè)置二叉樹的平衡標(biāo)記balance，以標(biāo)記返回二叉樹bt是否為平衡二叉樹，若為平衡二叉樹，則返回1，否則返回0；h為二叉樹bt的高度。采用前序遍歷的遞歸算法：①若bt為空，則高度為0，balance=1。②若bt僅有根結(jié)點(diǎn)，則高度為1，balance=1。③否則，對bt的左、右子樹執(zhí)行遞歸運(yùn)算，返回左、右子樹的高度和平衡標(biāo)記，bt的高度為最高子樹的高度加1。若左、右子樹的高度差大于1，則balance=0；若左、右子樹的高度差小于1，且左、右子樹都平衡時(shí)，balance=1，否則balance=0。知識點(diǎn)解析：暫無解析43、根據(jù)設(shè)計(jì)思想，采用C或C++語言描述算法，關(guān)鍵之處給出注釋。標(biāo)準(zhǔn)答案：算法的實(shí)現(xiàn)加下：voidJudge_AVL(BjiTreebt，int&balance，int&h){intbl，br，hl，hr；／／左、右子樹的平衡標(biāo)記和高度if，(bt==NULL){／／空樹，高度為0h=0，balance=1；}elseif(p—>ichi