考研計(jì)算機(jī)專業(yè)基礎(chǔ)綜合（綜合應(yīng)用題）模擬試卷3（共100題）

考研計(jì)算機(jī)專業(yè)基礎(chǔ)綜合（綜合應(yīng)用題）模擬試卷3（共5套）（共100題）考研計(jì)算機(jī)專業(yè)基礎(chǔ)綜合（綜合應(yīng)用題）模擬試卷第1套一、綜合應(yīng)用題(本題共20題，每題1.0分，共20分。)1、線性表(a1，a2，a3，…，an)中元素遞增有序且按順序存儲(chǔ)于計(jì)算機(jī)內(nèi)。要求設(shè)計(jì)一算法用最少時(shí)間在表中查找數(shù)值為x的元素，并將其與后繼元素位置相交換。如果線性表中找不到該元素，則將該元素插入表中并使表中元素仍遞增有序。(1)給出算法的基本設(shè)計(jì)思想。(2)根據(jù)設(shè)計(jì)思想，采用C或C++或Java語言描述算法，關(guān)鍵之處給出注釋。(3)分別給出算法各部分的時(shí)間復(fù)雜度。標(biāo)準(zhǔn)答案：(1)順序存儲(chǔ)的線性表遞增有序，可以順序查找，也可折半查找。題目要求“用最少的時(shí)間在表中查找數(shù)值為x的元素”，這里應(yīng)使用折半查找方法。(2)算法的設(shè)計(jì)如下：voidsearchExchangeInsert(ElemTypea[]，ElemTypex){intlow=0：inthigh=n一1：intmid；／／low和high指向線性表下界和上界的下標(biāo)while(low＜=high){mid=(low+high)／2；／／找中間位置if(a[mid]==x)break；／／找到x，退出while循環(huán)elseif(a[mid]＜x)low=mid+1；／／~tj中點(diǎn)mid的右部去查elsehigh=mid一1：／／到中點(diǎn)mid的左部去查}if(a[mid]==x&&mid!=n){／／若最后一個(gè)元素與x相等，／／則不存在與其后繼交換的操作t=a[mid]；a[mid]=a[mid+1]；a[mid+1]=t；}／／數(shù)值x與其后繼元素位置交換if(low＞high){／／查找失敗，插入數(shù)據(jù)元素xinti；for(i=n—1：i＞high；i一一)a[i+1]=a[i]；／／后移元素a[low]=x；／／插入x}／／結(jié)束插入}(3)在利用折半查找的方法查找x的過程中時(shí)間復(fù)雜度為O(nlog2n)；交換元素位置時(shí)的時(shí)間復(fù)雜度為O(1)；當(dāng)查找不成功時(shí)，插入元素時(shí)的時(shí)間復(fù)雜度為O(n)。知識(shí)點(diǎn)解析：暫無解析2、設(shè)二叉排序樹的各元素值均不相同，采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，試分別設(shè)計(jì)遞歸和非遞歸算法按遞減序打印所有左子樹為空、右子樹非空的結(jié)點(diǎn)的數(shù)據(jù)域的值。標(biāo)準(zhǔn)答案：(1)遞歸算法voidDecPrint(BSTreet){／／遞減序輸出二叉排序樹t中所有左子樹為空、右子樹非空的結(jié)點(diǎn)數(shù)據(jù)域的值if(t){DecPrint(t一＞rchild)：if(!t一＞lchild&&t一＞rchild)printf(t一＞data：4)；DecPrint(t一＞lchild)：}}(2)非遞歸算法voidDecPrint(BSTreet){／／遞減序輸出二叉排序樹t中所有左子樹為空、右子樹非空的結(jié)點(diǎn)的值BSTrees[]；／／s是二叉排序樹結(jié)點(diǎn)指針的棧，容量足夠大inttop=0：while(t||top＞0){while(t){s[++top]=t；t=t-＞rchild；}／／沿右分支向下if(top＞0){t=s[top--]；if(!t一＞lchild&&t一＞rchild)printf(t一＞data：4)：t=t一＞lchild；／／去左分支}／／if}／／while}／／算法結(jié)束知識(shí)點(diǎn)解析：暫無解析3、某模型機(jī)的數(shù)據(jù)通路結(jié)構(gòu)如下圖所示。用寄存器傳送語句(如PC→MAR)，擬出下列指令從讀取到執(zhí)行的完整流程。(1)數(shù)據(jù)傳送指令MOVx(R0)，Y(R1)，源和目的操作數(shù)地址均采用變址尋址，第1個(gè)參數(shù)X為源操作數(shù)的形式地址，第2個(gè)參數(shù)為目的操作數(shù)的形式地址，分別位于指令的第2個(gè)和第3個(gè)存儲(chǔ)字。(2)數(shù)據(jù)求反指令COM一一(R0)，采用自減型寄存器間接尋址，結(jié)果送回自減后的地址單元。標(biāo)準(zhǔn)答案：(1)MOVX(R0)，Y(R1)指令執(zhí)行流程中的前3步是完成取指令都有的公操作；接下來的5步是去主存中取源操作數(shù)，把取出的數(shù)放在暫存器C中；然后的4步是形成目的操作數(shù)地址；最后2步完成傳送操作。①PC→MAR，Read；取指令②M→MDR→IR③PC+1→PC④PC→MAR，Read；取源操作數(shù)形式地址⑤M→MDR→C⑥PC+1→PC⑦C+R0→MAR，Read；形成源操作數(shù)有效地址，并取源操作數(shù)⑧M→MDR→C：源操作數(shù)暫存C中⑨PC→MAR，Read；取目的操作數(shù)形式地址⑩M→MDR→DPC+1→PCD+R1→MAR；形成目的操作數(shù)有效地址C→MDR；將源操作數(shù)送存儲(chǔ)器數(shù)據(jù)寄存器MDR｝M，Write；將源操作數(shù)寫入目的有效地址中(2)COM一一(R0)指令執(zhí)行流程中的前3步是取指令操作；接下來的2步是去主存中取源操作數(shù)，把取出的數(shù)放在暫存器D中：然后將D的內(nèi)容取反，寫入目的地址中。①PC→MAR，Read；取指令②M→MDR→IR③PC+I→PC④R0→1→R0，R0-1→MAR，Read;修改R0的內(nèi)容(源和目的操作數(shù)地址)⑤M→MDR→D；取出源操作數(shù)⑥D(zhuǎn)→MDR；將源操作數(shù)取反⑦M(jìn)DR→M，Write；寫入目的地址中知識(shí)點(diǎn)解析：暫無解析4、已知一個(gè)雙向鏈表，其結(jié)點(diǎn)結(jié)構(gòu)為數(shù)據(jù)域data、左指針域Uink、右指針域rlink；設(shè)指針P指向雙向鏈表中的某個(gè)結(jié)點(diǎn)。寫出一個(gè)算法，實(shí)現(xiàn)P所指向的結(jié)點(diǎn)和它的前綴結(jié)點(diǎn)之間順序的互換。要求：(1)給出算法的基本設(shè)計(jì)思想。(2)根據(jù)設(shè)計(jì)思想，采用C或C++或Java語言描述算法，關(guān)鍵之處給出注釋。標(biāo)準(zhǔn)答案：(1)算法的基本思想：已知雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)P，與前驅(qū)交換涉及4個(gè)結(jié)點(diǎn)(P結(jié)點(diǎn)，前驅(qū)結(jié)點(diǎn)，前驅(qū)的前驅(qū)結(jié)點(diǎn)，后繼結(jié)點(diǎn))、6條鏈。(2)算法的設(shè)計(jì)如下：typedefstructDuLNode{intdata；structDuLNode*llink，*rlink：}DuLNode*Linkedlist；voidExchange(LinkedListP){／／將P所指結(jié)點(diǎn)與其前驅(qū)結(jié)點(diǎn)交換Linkedlist*q：q=p一>llink；q->llink->rlink=P：／／p的前驅(qū)的前驅(qū)之后繼為Pp->llink=q->llink：／／p的前驅(qū)指向其前驅(qū)的前驅(qū)q->rlink=p一>rlink；／／p的前驅(qū)的后繼為P的后繼q->llink=P：／／p與其前驅(qū)交換P->rlink->llink=q：／／p的后繼的前驅(qū)指向原P的前驅(qū)p->rlink=q：／／p的后繼指向其原來的前驅(qū)}知識(shí)點(diǎn)解析：暫無解析5、G=(V，E)是一個(gè)帶有權(quán)的連通圖，如圖所示。(1)什么是G的最小生成樹?(2)G如圖所示，請(qǐng)找出G的所有最小生成樹。標(biāo)準(zhǔn)答案：(1)無向連通圖的生成樹包含圖中全部n個(gè)頂點(diǎn)，以及足以使圖連通的n—1條邊。而最小生成樹則是各邊權(quán)值之和最小的生成樹。(2)最小生成樹有兩棵。下面給出頂點(diǎn)集合和邊集合，編以三元組(Vi，Vj，W)形式，其中W代表權(quán)值。V(G)={1，2，3，4，5}El(G)={(4，5，2)，(2，5，4)，(2，3，5)，(1，2，7)}；E2(G)={(4，5，2)，(2，4，4)，(2，3，5)，(1，2，7)}提示：此題考查的知識(shí)點(diǎn)是最小生成樹的定義。該題說明圖的最小生成樹不唯一，但權(quán)值和唯一，出現(xiàn)兩個(gè)或兩個(gè)以上的情況是因?yàn)橛袡?quán)值相同的邊。牢記Prim(選圖的頂點(diǎn))、Kruskal(選圖的邊，邊上權(quán)值排序)兩種算法的區(qū)別及算法步驟。知識(shí)點(diǎn)解析：暫無解析6、CPU執(zhí)行一段程序時(shí)，Cache完成存取的次數(shù)為5000次，主存完成存取的次數(shù)為200次。已知Cache存取周期為40ns，主存儲(chǔ)取周期為160ns。求：(1)Cache的命中率H。(2)Cache-主存系統(tǒng)的訪問效率e。(3)平均訪問時(shí)間T。標(biāo)準(zhǔn)答案：(1)命中率H=Nc／(Nc+Nm)=5000÷(5000+200)=5000÷5200=0．96(2)主存慢于Cache的倍率：R=Tm／Tc=160ns÷40ns=4訪問效率：e=1÷[r+(1一r)H]=1÷[4+(1—4)×0．96]=89．3％(3)平均訪問時(shí)間：Ta=Tc／e=40÷0．893=45ns知識(shí)點(diǎn)解析：暫無解析7、下圖是一個(gè)簡(jiǎn)化的CPU與主存連接結(jié)構(gòu)示意圖(圖中省略了所有多路選擇器)。其中有一個(gè)累加寄存器AC、一個(gè)狀態(tài)寄存器和其他四個(gè)寄存器(主存地址寄存器MAR、主存數(shù)據(jù)寄存器MDR、程序計(jì)數(shù)器PC和指令寄存器IR)，各部件及其之間的連線表示數(shù)據(jù)通路，箭頭表示信息傳送方向。要求：(1)寫出圖中a、b、c、d四個(gè)寄存器的名稱。(2)簡(jiǎn)述圖中指令從主存取到控制器的過程。(3)說明數(shù)據(jù)從主存取出、運(yùn)算、寫回主存所經(jīng)過的數(shù)據(jù)通路(假定數(shù)據(jù)地址已在MAR中)。標(biāo)準(zhǔn)答案：(1)b單向連接微控制器，由微控制器的作用不難得知b是指令寄存器(IR)；a和c直接連接主存，只可能是MDR和MAR，c到主存是單向連接，a和主存雙向連接，根據(jù)指令執(zhí)行的特點(diǎn)，MAR只單向給主存?zhèn)魉偷刂?，而MDR既存放從主存中取出的數(shù)據(jù)又要存放將要寫入主存的數(shù)據(jù)，因此c為主存地址寄存器(MAR)，a為主存數(shù)據(jù)寄存器(MDR)。d具有自動(dòng)加1的功能，且單向連接MAR，不難得出為程序計(jì)數(shù)器(PC)。因此，a為MDR，b為IR，c為MAR，d為PC。(2)先從程序計(jì)數(shù)器(PC)中取出指令地址，將指令地址送入主存地址寄存器(MAR)，在相關(guān)的控制下從主存中取出指令送至主存數(shù)據(jù)寄存器(MDR)，然后將MDR中的指令送至指令寄存器(IR)，最后流向微控制器，供微控制器分析并執(zhí)行指令。因此，取指令的數(shù)據(jù)通路為：PC→MAR，M(MAR)→MDR→IR→控制器。(3)與(2)的分析類似，根據(jù)MAR中的地址去主存取數(shù)據(jù)，將取出的數(shù)據(jù)送至主存數(shù)據(jù)寄存器(MDR)，然后將MDR中的數(shù)據(jù)送至ALu進(jìn)行運(yùn)算，運(yùn)算的結(jié)果送至累加器(AC)，運(yùn)算結(jié)束后將AC中的結(jié)果送至MDR，最后將MDR中的數(shù)據(jù)寫入主存。因此，從主存取出、運(yùn)算和寫回主存所經(jīng)過的數(shù)據(jù)通路為：MAR→M，M(MAR)→MDR→ALU，ALU→AC，AC→MDR→M(MAR)。知識(shí)點(diǎn)解析：暫無解析8、兄弟倆共同使用一個(gè)賬號(hào)，每次限存或取10元，存錢與取錢的進(jìn)程分別如下所示：intamount=0：SAVE(){intm1：m1=amount：m1=m1+10：amount=m1：}TAKE(){intm2；m2=amount：m2=m2一10：amount=m2：}由于兄弟倆可能同時(shí)存錢和取錢，因此兩個(gè)進(jìn)程是并發(fā)的。若哥哥先存了兩次錢，但在第三次存錢時(shí)弟弟在取錢。請(qǐng)問：(1)最后賬號(hào)amount上面可能出現(xiàn)的值是多少?(2)如何用P、V操作實(shí)現(xiàn)兩并發(fā)進(jìn)程的互斥執(zhí)行?標(biāo)準(zhǔn)答案：本題考查P、V操作實(shí)現(xiàn)進(jìn)程的互斥。(1)哥哥存兩次錢后，共享變量amount的值為20。哥哥的第三次存錢與弟弟的取錢同時(shí)進(jìn)行，如果兩者順序執(zhí)行，則最后amount的值為20；如果在一個(gè)進(jìn)程的執(zhí)行過程中進(jìn)行CPU調(diào)度，轉(zhuǎn)去執(zhí)行另一進(jìn)程，則最后amount的值取決于amount=m1及amount=m2的執(zhí)行先后次序，若前者先執(zhí)行，則最后amount的值為10，若后者先執(zhí)行，則最后amount的值為30。因此，最后賬號(hào)amount上可能出現(xiàn)的值有10、20、30。(2)在上述問題中，共享變量amount是一個(gè)臨界資源，為了實(shí)現(xiàn)兩并發(fā)進(jìn)程對(duì)它的互斥訪問，可為它設(shè)置一初值為1的互斥信號(hào)量mutex，并將上述算法修改為：intamount=0；semaphoremutex=1；／／g斥訪問amount變量的信號(hào)量cobegin{processSAVE(){intm1；P(mutex)：m1=amount：m1=m1+10：amount=m1；V(mutex)：}processTAKE(){intm2；P(mutex)；m2=amount：m2=m2—10；amount=m2；V(mutex)；}}coend知識(shí)點(diǎn)解析：暫無解析9、在采用首次適應(yīng)算法回收內(nèi)存時(shí)，可能出現(xiàn)哪幾種情況?應(yīng)怎樣處理這些情況?標(biāo)準(zhǔn)答案：(1)回收區(qū)與插入點(diǎn)的前一個(gè)分區(qū)相鄰接，此時(shí)可將回收區(qū)與插入點(diǎn)的前一分區(qū)合并，不再為回收分區(qū)分配新表項(xiàng)，而只修改前鄰接分區(qū)的大小。(2)回收區(qū)與插入點(diǎn)的后一分區(qū)相鄰接，此時(shí)合并兩區(qū)，然后用回收區(qū)的首址作為新空閑區(qū)的首址，大小為兩者之和。(3)回收區(qū)同時(shí)與插入點(diǎn)的前后兩個(gè)分區(qū)鄰接，此時(shí)將三個(gè)分區(qū)合并，使用前鄰接分區(qū)的首址，大小為三區(qū)之和，取消后鄰接分區(qū)的表項(xiàng)。(4)回收區(qū)沒有鄰接空閑分區(qū)，則應(yīng)為回收區(qū)單獨(dú)建立一個(gè)新表項(xiàng)，填寫回收區(qū)的首址和大小，并根據(jù)其首址，插入到空閑鏈中的適當(dāng)位置。知識(shí)點(diǎn)解析：暫無解析10、為什么說分段系統(tǒng)較之分頁系統(tǒng)更易于實(shí)現(xiàn)信息共享和保護(hù)?標(biāo)準(zhǔn)答案：(1)對(duì)于分頁系統(tǒng)，每個(gè)頁面是分散存儲(chǔ)的，為了實(shí)現(xiàn)信息共享和保護(hù)，則頁面之間需要一一對(duì)應(yīng)起來，為此需要建立大量的頁表項(xiàng)。(2)對(duì)于分段系統(tǒng)，每個(gè)段都從0開始編址，并采用～段連續(xù)的地址空間，這樣在實(shí)現(xiàn)共享和保護(hù)時(shí)，只需為所要共享和保護(hù)的程序設(shè)置一個(gè)段表項(xiàng)，將其中的基址與內(nèi)存地址一一對(duì)應(yīng)起來即可。知識(shí)點(diǎn)解析：暫無解析11、什么是地址重定位?怎樣區(qū)分靜態(tài)重定位和動(dòng)態(tài)重定位?各有什么優(yōu)缺點(diǎn)?標(biāo)準(zhǔn)答案：(1)地址重定位：把作業(yè)地址空間中使用的邏輯地址變換成主存中物理地址的過程。(2)靜態(tài)重定位是在程序運(yùn)行之前由裝配程序完成的，動(dòng)態(tài)重定位是在程序執(zhí)行過程中由硬件地址變換機(jī)構(gòu)實(shí)現(xiàn)的。(3)靜態(tài)重定位的主要優(yōu)點(diǎn)是，無須增加硬件地址變換機(jī)構(gòu)，因此可在一般計(jì)算機(jī)上實(shí)現(xiàn)。(4)靜態(tài)重定位的主要缺點(diǎn)有：第一，要求給每個(gè)作業(yè)分配一個(gè)連續(xù)的存儲(chǔ)空間，且在作業(yè)的整個(gè)執(zhí)行期間不能再移動(dòng)，因此也就不能實(shí)現(xiàn)重新分配主存，不利于主存空間的充分利用。第二，用戶必須事先確定所需的存儲(chǔ)量，若所需的存儲(chǔ)量超過可用存儲(chǔ)空間，用戶必須考慮覆蓋結(jié)構(gòu)。第三，用戶之間難以共享主存中的同一程序副本。(5)動(dòng)態(tài)重定位的主要優(yōu)點(diǎn)有：第一，用戶作業(yè)不要求分配連續(xù)的存儲(chǔ)空間。第二，用戶作業(yè)在執(zhí)行過程中可以動(dòng)態(tài)申請(qǐng)存儲(chǔ)空間和在主存中移動(dòng)。第三，有利于程序段的共享。(6)動(dòng)態(tài)重定位的主要缺點(diǎn)有：第一，需要附加的硬件支持。第二，實(shí)現(xiàn)存儲(chǔ)管理的軟件算法比較復(fù)雜。知識(shí)點(diǎn)解析：暫無解析12、一個(gè)UNIX文件F的存取權(quán)限為rwxr-x---，該文件的文件主uid=12，gid=1，另一個(gè)用戶的uid=6，gid=1，是否允許該用戶執(zhí)行文件F?標(biāo)準(zhǔn)答案：F的存取權(quán)限為rwxr-x---，表示文件主可對(duì)F進(jìn)行讀、寫及執(zhí)行操作，同組用戶可對(duì)F進(jìn)行讀及執(zhí)行操作，但其他用戶不能對(duì)F操作。因?yàn)榱硪挥脩舻慕M標(biāo)識(shí)符gid相同，所以允許該用戶執(zhí)行文件F。知識(shí)點(diǎn)解析：暫無解析13、計(jì)算機(jī)網(wǎng)絡(luò)是由哪些元素組成的?標(biāo)準(zhǔn)答案：計(jì)算機(jī)網(wǎng)絡(luò)由網(wǎng)絡(luò)軟件和網(wǎng)絡(luò)硬件兩大部分組成。網(wǎng)絡(luò)軟件主要包括：網(wǎng)絡(luò)協(xié)議、通信軟件、網(wǎng)絡(luò)操作系統(tǒng)等；網(wǎng)絡(luò)硬件主要包括網(wǎng)絡(luò)結(jié)點(diǎn)(又稱網(wǎng)絡(luò)單元)和通信鏈路。知識(shí)點(diǎn)解析：暫無解析14、網(wǎng)絡(luò)層有哪些設(shè)備?各自的特點(diǎn)有哪些?標(biāo)準(zhǔn)答案：(1)路由器在互聯(lián)網(wǎng)中，兩臺(tái)主機(jī)之間傳送數(shù)據(jù)的通路有很多條，數(shù)據(jù)包從一臺(tái)主機(jī)出發(fā)，中途要經(jīng)過多個(gè)站點(diǎn)才能到達(dá)另一臺(tái)主機(jī)。這些中間站點(diǎn)通常由被稱為路由器的設(shè)備擔(dān)當(dāng)，其作用就是為數(shù)據(jù)包選擇一條合適的傳送路徑。路由器工作在OSI模型的網(wǎng)絡(luò)層，是根據(jù)數(shù)據(jù)包中的邏輯地址(網(wǎng)絡(luò)地址)而不是MAC地址來轉(zhuǎn)發(fā)數(shù)據(jù)包的。路由器的主要工作是為經(jīng)過路由器的每個(gè)數(shù)據(jù)包尋找一條最佳傳輸路徑，并將該數(shù)據(jù)包有效地傳送到目的站點(diǎn)。路由器不僅有網(wǎng)橋的全部功能，還具有路徑的選擇功能，可根據(jù)網(wǎng)絡(luò)的擁塞程度自動(dòng)選擇適當(dāng)?shù)穆窂絺魉蛿?shù)據(jù)。路由器與網(wǎng)橋的不同之處在于，它并不是使用路由表來找到其他網(wǎng)絡(luò)中指定設(shè)備的地址，而是依靠其他的路由器來完成任務(wù)。也就是說，網(wǎng)橋是根據(jù)路由表來轉(zhuǎn)發(fā)或過濾數(shù)據(jù)包，而路由器是使用它的信息來為每一個(gè)數(shù)據(jù)包選擇最佳路徑。路由器有靜態(tài)和動(dòng)態(tài)之分。靜態(tài)路由器需要管理員來修改所有的網(wǎng)絡(luò)路由表，一般只用于小型的網(wǎng)間互聯(lián)：而動(dòng)態(tài)路由器能根據(jù)指定的路由協(xié)議來完成修改路由器信息。(2)第三層交換機(jī)隨著技術(shù)的發(fā)展，有些交換機(jī)也具備了路由的功能。這些具有路由功能的交換機(jī)要在網(wǎng)絡(luò)層對(duì)數(shù)據(jù)包進(jìn)行操作，因此被稱為第三層交換機(jī)。知識(shí)點(diǎn)解析：暫無解析15、設(shè)有一個(gè)n×n的上三角矩陣(aij)，將其上三角中的元素按先行后列的順序存于數(shù)組B[m]中，使得B[k]=aij且k=f1(i)f2(j)+c，請(qǐng)推導(dǎo)出函數(shù)f1、f2和常數(shù)c，要求f1和f2中不含常數(shù)項(xiàng)。標(biāo)準(zhǔn)答案：上三角矩陣第1行有n個(gè)元素，第i一1行有n一(i一1)+1個(gè)元素，第1行到第i一1行是等腰梯形，而第i行上第j個(gè)元素(即aij)是第i行上第j-i+1個(gè)元素，故元素aij在一維數(shù)組中的存儲(chǔ)位置(下標(biāo)k)為：k=(n+(n一(i一1)+1))(i一1)／2+(j-i+1)=(2n-i+2)(i一1)／2+j-i+1進(jìn)一步整理為：知識(shí)點(diǎn)解析：暫無解析16、設(shè)有15000個(gè)無序的元素，希望用最快的速度挑選出其中前10最大的元素。在快速排序、堆排序、歸并排序、基數(shù)排序和希爾排序中，宜采用哪種方法并說明理由?標(biāo)準(zhǔn)答案：上面所說的幾種排序方法中，排序速度都很快，但快速排序、歸并排序、基數(shù)排序和希爾排序都是在排序結(jié)束后才能確定數(shù)據(jù)元素的全部序列，而排序過程中無法知道部分連續(xù)位置上的最終元素。而堆排序則是每次輸出一個(gè)堆頂元素(即最大或最小值的元素)，然后對(duì)堆進(jìn)行再調(diào)整，保證堆頂元素總是當(dāng)前剩下元素的最大或最小的，從而可知，如果在一個(gè)大量數(shù)據(jù)的文件中，如含有15000個(gè)元素的記錄文件中選取前10個(gè)最大的元素，宜采用堆排序。知識(shí)點(diǎn)解析：暫無解析17、操作系統(tǒng)必須具備的功能有哪些?標(biāo)準(zhǔn)答案：(1)用戶接口：操作系統(tǒng)與用戶的接口也簡(jiǎn)稱為用戶接口。(2)處理機(jī)管理：處理機(jī)管理的主要任務(wù)是對(duì)處理機(jī)的分配和運(yùn)行實(shí)施有效管理。(3)存儲(chǔ)管理：存儲(chǔ)管理的主要任務(wù)包括為多道程序的并發(fā)運(yùn)行提供良好環(huán)境，為用戶使用存儲(chǔ)器提供方便，提高存儲(chǔ)器的利用率，為盡量多的用戶提供足夠大的存儲(chǔ)空間。(4)設(shè)備管理：設(shè)備管理的主要任務(wù)有：為用戶分配I／O設(shè)備，完成用戶程序請(qǐng)求的I／O操作，提高CPU和輸入／輸出設(shè)備的利用率，改善人機(jī)界面。(5)文件管理：現(xiàn)代計(jì)算機(jī)系統(tǒng)的外部存儲(chǔ)器中，都以文件形式存放著大量的信息。操作系統(tǒng)必須配置相應(yīng)的文件管理機(jī)構(gòu)來管理這些信息。知識(shí)點(diǎn)解析：暫無解析某多道程序設(shè)計(jì)系統(tǒng)配有一臺(tái)處理器和兩臺(tái)外設(shè)101、102，現(xiàn)有3個(gè)優(yōu)先級(jí)由高到低的J1、J2、J3都已裝入了主存，它們使用資源的先后順序和占用時(shí)間分別是：j1：IO2(30ms)，CPU(10ms)；IO1(30ms)，CPU(10ms)；J2：IO1(20ms)，CPU(20ms)；IO2(40ms)；J3：CPU(30ms)，IO1(20ms)。處理器調(diào)度采用可搶占的優(yōu)先數(shù)算法，忽略其他輔助操作時(shí)間，回答下列問題。18、分別計(jì)算作業(yè)J1、J2和J3從開始到完成所用的時(shí)間。標(biāo)準(zhǔn)答案：為了清楚地描述作業(yè)執(zhí)行情況，我們對(duì)題目假設(shè)的情況分析如下：J1占用IO2傳輸30ms時(shí)，J1傳輸完成，搶占J2的CPU，運(yùn)行10ms，再傳輸30ms，運(yùn)行10ms，完成。J1從開始到完成所用的時(shí)間為：30+10+304+10=80(ms)。J2與其并行地在I1上傳輸20ms，搶占J3的CPU，J2運(yùn)行10ms后，被J1搶占CPU，等待10ms之后，J2再次得到CPU，運(yùn)行10ms，J2啟動(dòng)IO2傳輸，40ms完成。J2從開始到完成所用的時(shí)間為：20+10+10+10+40=90(ms)。J3在CPU上執(zhí)行20ms，被J2搶占CPU，等待30ms，再運(yùn)行10ms，等待10ms，J3啟動(dòng)IO1運(yùn)行20ms的傳輸，完成。J3從開始到完成所用的時(shí)間為20+304-10+10+20=90(ms)。知識(shí)點(diǎn)解析：暫無解析19、3個(gè)作業(yè)全部完成時(shí)CPU的利用率。標(biāo)準(zhǔn)答案：三個(gè)作業(yè)全部完成時(shí)，CPU的利用率為(10+20+30+10)／90=7／9=7．8％。知識(shí)點(diǎn)解析：暫無解析20、3個(gè)作業(yè)全部完成時(shí)外設(shè)IO1的利用率。標(biāo)準(zhǔn)答案：三個(gè)作業(yè)全部完成時(shí)，外設(shè)IO1的利用率為(20+30+20)／90=7／9=78％。知識(shí)點(diǎn)解析：暫無解析考研計(jì)算機(jī)專業(yè)基礎(chǔ)綜合（綜合應(yīng)用題）模擬試卷第2套一、綜合應(yīng)用題(本題共20題，每題1.0分，共20分。)1、什么是AND信號(hào)量?請(qǐng)利用AND信號(hào)量寫出生產(chǎn)者一消費(fèi)者問題的解法。標(biāo)準(zhǔn)答案：此題主要考查進(jìn)程與死鎖的相關(guān)轉(zhuǎn)換內(nèi)容。(1)為解決并行所帶來的死鎖問題，在wait操作中引入AND條件，其基本思想是將進(jìn)程在整個(gè)運(yùn)行過程中所需要的所有臨界資源一次性地全部分配給進(jìn)程，用完后一次性釋放。(2)解決生產(chǎn)者一消費(fèi)者問題可描述如下：varmutex，empty，full：semaphore：=1，n，0；buffer．a(chǎn)rray[0．．n一1]ofitem；in，out：integer：=0，0；beginparbeginproducer：beginrepeatproduceaniteminnextp；wait(empty)：wait(s1，s2，s3，…，sn)：／／s1，s2，s3，…，sn為執(zhí)行生產(chǎn)者進(jìn)程除empty外其余的條件wait(mutex)；buffer(in)：=nextp：in：=(in+1)modn：signal(mutex)：signal(full)；signal(s1，s2，s3，…，sn)；untilfalse；endconsumer：beginrepeatwait(full)；wait(k1，k2，k3，…，kn)：／／k1，k2，k3，…，kn為執(zhí)行生產(chǎn)者進(jìn)程除full外其余的條件wait(mutex)；nextc：=buffer(out)：out：=(out+1)modn；signal(mutex)；signal(empty)；signal(k1，k2，k3，…，kn)；consumetheiteminnextc；untilfalse；endparendend知識(shí)點(diǎn)解析：暫無解析2、設(shè)計(jì)一個(gè)算法，判斷一個(gè)算術(shù)表達(dá)式中的括號(hào)是否配對(duì)。算術(shù)表達(dá)式保存在帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)域：ch和link，其中ch域?yàn)樽址愋汀?biāo)準(zhǔn)答案：表達(dá)式中的括號(hào)有以下三對(duì)：’(’、’)’、’[’、’]’、’{’、’}’，使用棧，當(dāng)為左括號(hào)時(shí)入棧，右括號(hào)時(shí)，若棧頂是其對(duì)應(yīng)的左括號(hào)，則退棧，若不是其對(duì)應(yīng)的左括號(hào)，則結(jié)論為括號(hào)不配對(duì)。當(dāng)表達(dá)式結(jié)束，若棧為空，則結(jié)論表達(dá)式括號(hào)配對(duì)；否則，結(jié)論表達(dá)式括號(hào)不配對(duì)。intMatch(LinkedListla){／／算術(shù)表達(dá)式存儲(chǔ)在以la為頭結(jié)點(diǎn)的單循環(huán)鏈表中，本算法判斷括號(hào)是否正確配對(duì)charS[]；／／s為字符棧，容量足夠大P=la一＞link；／／p為工作指針，指向待處理結(jié)點(diǎn)StackInit(S)；／／初始化棧swhile(P!=la){／／循環(huán)到頭結(jié)點(diǎn)為止switch(p-＞ch){case’(’：push(s，p-＞ch)；break；case’)’：if(StackEmpty(s)||StackGetTop(s)!=’(’){printf(”括號(hào)不配對(duì)＼n”)；return(0)：}elsepop(S)：break；case’[’：push(s，p一＞ch)；break；case’[’：if(StaekEmpty(s)IlStackGetTop(s)!=’[’){printf(”括號(hào)不配對(duì)＼n”)；return(0)；}elsepop(S)；break；case’{’：push(s，p-＞ch)；break；case’}’：if(StackEmpty(s)IIStackGetTop(s)!=’{’){printf(”括號(hào)不配對(duì)＼n”)；return(0)；}elsepop(s)：break；}P=p-＞link；／／后移指針}／／whileif(StackEmpty(s))fprintf("括號(hào)配對(duì)＼n")；return(1)；}else{printf(”括號(hào)不配對(duì)＼n”)；return(0)；}}知識(shí)點(diǎn)解析：暫無解析3、計(jì)算機(jī)網(wǎng)絡(luò)由哪些部分組成?什么是通信子網(wǎng)和資源子網(wǎng)?試述這種層次結(jié)構(gòu)觀的特點(diǎn)以及各層的作用。標(biāo)準(zhǔn)答案：(1)計(jì)算機(jī)網(wǎng)絡(luò)由通信子網(wǎng)和資源子網(wǎng)組成。(2)資源子網(wǎng)是指計(jì)算機(jī)網(wǎng)絡(luò)資源的擁有者，它們?yōu)榫W(wǎng)絡(luò)提供資源。通信子網(wǎng)是由通信控制處理機(jī)構(gòu)成的，為資源子網(wǎng)提供信息傳輸服務(wù)。(3)通信控制處理機(jī)構(gòu)成的通信子網(wǎng)是網(wǎng)絡(luò)的內(nèi)層，或骨架層，是網(wǎng)絡(luò)的重要組成部分。網(wǎng)上主機(jī)負(fù)責(zé)數(shù)據(jù)處理，是計(jì)算機(jī)網(wǎng)絡(luò)資源的擁有者，它們組成了網(wǎng)絡(luò)的資源子網(wǎng)，是網(wǎng)絡(luò)的外層。通信子網(wǎng)為資源子網(wǎng)提供信息傳輸服務(wù)，資源子網(wǎng)上用戶間的通信是建立在通信子網(wǎng)的基礎(chǔ)上。沒有通信子網(wǎng)，網(wǎng)絡(luò)不能工作，而沒有資源子網(wǎng)，通信子網(wǎng)的傳輸也失去了意義，兩者合起來組成了統(tǒng)一的資源共享的兩層網(wǎng)絡(luò)。將通信子網(wǎng)的規(guī)模進(jìn)一步擴(kuò)大，使之變成社會(huì)公有的數(shù)據(jù)通信網(wǎng)。知識(shí)點(diǎn)解析：暫無解析4、簡(jiǎn)述為什么在傳輸連接建立時(shí)要使用三次握手，如不建立連接可能會(huì)出現(xiàn)什么情況?標(biāo)準(zhǔn)答案：我們知道，三次握手完成兩個(gè)重要的功能，既要雙方做好發(fā)送數(shù)據(jù)的準(zhǔn)備工作(雙方都知道彼此已準(zhǔn)備好)，也要允許雙方就初始序列號(hào)進(jìn)行協(xié)商，這個(gè)序列號(hào)在握手過程中被發(fā)送和確認(rèn)?，F(xiàn)在把三次握手改成僅需要兩次握手，死鎖是可能發(fā)生的。作為例子，考慮計(jì)算機(jī)A和B之間的通信，假定B給A發(fā)送一個(gè)連接請(qǐng)求分組，A收到了這個(gè)分組，并發(fā)送了確認(rèn)應(yīng)答分組。按照兩次握手的協(xié)定，A認(rèn)為連接已經(jīng)成功地建立了，可以開始發(fā)送數(shù)據(jù)分組?？墒?，B在A的應(yīng)答分組在傳輸中被丟失的情況下，將不知道A是否已準(zhǔn)備好，不知道A建議什么樣的序列號(hào)，B甚至懷疑A是否收到自己的連接請(qǐng)求分組。在這種情況下，B認(rèn)為連接還未建立成功，將忽略A發(fā)來的任何數(shù)據(jù)分組，只等待連接確認(rèn)應(yīng)答分組。而A在發(fā)出的分組超時(shí)后，重復(fù)發(fā)送同樣的分組，這樣就形成了死鎖。知識(shí)點(diǎn)解析：暫無解析5、今有4級(jí)流水線分別完成取值、指令譯碼并取數(shù)、運(yùn)算、送結(jié)果四步操作，現(xiàn)假設(shè)完成各步操作的時(shí)間依次為100ns，100ns，80ns，50ns。請(qǐng)回答下列問題：(1)流水線的操作周期應(yīng)設(shè)計(jì)為多少?(2)若相鄰兩條指令發(fā)生數(shù)據(jù)相關(guān)，而且在硬件上不采取措施，那么第二條指令要推遲多少時(shí)間進(jìn)行?(3)如果在硬件設(shè)計(jì)上加以改進(jìn)，至少需推遲多少時(shí)間?標(biāo)準(zhǔn)答案：(1)流水線的操作時(shí)鐘周期t按四步操作中最長(zhǎng)時(shí)間來考慮，所以t=100ns。(2)兩條指令發(fā)生數(shù)據(jù)相關(guān)沖突情況：ADDR1，R2，R3；R2+R3→R1SUBR4，R1，R5；R1一R5→R4兩條指令在流水線中執(zhí)行情況如下表所示。ADD指令在時(shí)鐘4時(shí)將結(jié)果寫入寄存器堆(R1)，但SUB指令在時(shí)鐘3時(shí)讀寄存器堆(R1)。本來ADD指令應(yīng)先寫入R1，SUB指令后讀R1，結(jié)果變成SUB指令先讀R1，ADD指令后寫R1，因而發(fā)生兩條指令間的數(shù)據(jù)相關(guān)，如果硬件上不采取措施，第2條指令SUB至少應(yīng)推遲2個(gè)操作時(shí)鐘周期(2×100ns)。(3)如果硬件上加以改進(jìn)(采取旁路技術(shù))，可推遲1個(gè)操作時(shí)鐘周期(100ns)。知識(shí)點(diǎn)解析：暫無解析6、已知一棵二叉樹的前序序列為：A，B，D，G，J，E，H，C，F(xiàn)，I，K，L；中序序列為：D，J，G，B，E，H，A，C，K，I，L，F(xiàn)。(1)寫出該二叉樹的后序序列。(2)畫出該二叉樹。(3)求該二叉樹的高度以及該二叉樹中度為2、1、0的結(jié)點(diǎn)個(gè)數(shù)。標(biāo)準(zhǔn)答案：此題只需從前序序列、中序序列得到唯一確定的二叉樹即可。(1)J，G，D，H，E，B，K，L，I，F(xiàn)，C，A。(2)二叉樹的形式如下圖所示：(3)高度是5，度為0的結(jié)點(diǎn)個(gè)數(shù)為4，度為1的結(jié)點(diǎn)個(gè)數(shù)為5，度為2的結(jié)點(diǎn)個(gè)數(shù)為3。知識(shí)點(diǎn)解析：暫無解析7、計(jì)算機(jī)硬件系統(tǒng)由哪幾個(gè)功能部件組成?每個(gè)部件完成的主要功能是什么?標(biāo)準(zhǔn)答案：計(jì)算機(jī)硬件是由運(yùn)算器、控制器、存儲(chǔ)器、輸入設(shè)備和輸出設(shè)備組成的。運(yùn)算器：數(shù)據(jù)處理，完成算術(shù)運(yùn)算和邏輯運(yùn)算?？刂破鳎簭拇鎯?chǔ)器中取出指令，并進(jìn)行指令譯碼。存儲(chǔ)器：存儲(chǔ)數(shù)據(jù)與程序。輸入設(shè)備：輸入數(shù)據(jù)，并且把人讀數(shù)據(jù)變?yōu)闄C(jī)讀數(shù)據(jù)。輸出設(shè)備：輸出數(shù)據(jù)，并且把機(jī)讀數(shù)據(jù)變?yōu)槿俗x數(shù)據(jù)。它們是通過總線連接在一起的，其中總線包括數(shù)據(jù)總線、地址總線和控制總線。知識(shí)點(diǎn)解析：暫無解析8、某指令流水線分為五級(jí)，分別完成取址(IF)、譯碼并取數(shù)(ID)、執(zhí)行(EX)、訪存(MEM)、寫結(jié)果(WR)。設(shè)完成各階段操作的時(shí)間依次為：90ns，60ns，70ns，100ns，50ns。試問：流水線的時(shí)鐘周期應(yīng)取何值?若第一條和第二條指令發(fā)生數(shù)據(jù)相關(guān)，第二條指令需推遲多少時(shí)間才能不發(fā)生錯(cuò)誤?若相鄰兩條指令發(fā)生數(shù)據(jù)相關(guān)，而不推遲第二條指令的執(zhí)行可采取什么措施?標(biāo)準(zhǔn)答案：流水線的時(shí)鐘周期應(yīng)取其中最長(zhǎng)的時(shí)間段，即100ns。第二條指令需推遲300ns(即等待上一條指令完成EX、MEM、WR三個(gè)周期后才能開始ID，才能不發(fā)生錯(cuò)誤。若相鄰兩條指令發(fā)生數(shù)據(jù)相關(guān)而不推遲第二條指令的執(zhí)行，可采取的措施是在訪存與執(zhí)行之間設(shè)置相關(guān)專用通路。知識(shí)點(diǎn)解析：暫無解析9、某計(jì)算機(jī)有如下部件：ALU，移位器，主存M，主存數(shù)據(jù)寄存器MDR，主存地址寄存器MAR，指令寄存器IR，通用寄存器R0一R1，暫存器C和D。(1)請(qǐng)將各邏輯部件組成一個(gè)數(shù)據(jù)通路，并標(biāo)明數(shù)據(jù)流向。(2)畫出“ADDR1，(R2)+”指令的指令周期流程圖，指令功能是(R1)+((R2))→R1。標(biāo)準(zhǔn)答案：(1)各功能部件連接成如下圖所示數(shù)據(jù)通路：(2)此指令為RS型指令，一個(gè)操作數(shù)在R1中，另一個(gè)操作數(shù)在R2為地址的內(nèi)存單元中，相加結(jié)果放在R1中。送當(dāng)前指令地址到MAR，取當(dāng)前指令到IR，PC+1，為取下條指令做好準(zhǔn)備。提示：①取R1操作數(shù)→C暫存器。②送地址到MAR。③取出內(nèi)存單元中的操作數(shù)→D暫存器。④相加后將和數(shù)→R1。知識(shí)點(diǎn)解析：暫無解析10、有一臺(tái)磁盤機(jī)，平均尋道時(shí)間為30ms，平均旋轉(zhuǎn)等待時(shí)間為120ms，數(shù)據(jù)傳輸速率為500B／ms，磁盤機(jī)上存放著1000件每件3000B的數(shù)據(jù)?，F(xiàn)欲把一件數(shù)據(jù)取走，更新后再放回原處。假設(shè)一次取出或?qū)懭胨钑r(shí)間為：平均尋道時(shí)間+平均等待時(shí)間+數(shù)據(jù)傳送時(shí)間。另外，使用cPu更新信息所需時(shí)間為4ms，且更新時(shí)間同輸入／輸出操作不相重疊。試問：(1)更新磁盤上全部數(shù)據(jù)需要多少時(shí)間?(2)若磁盤及旋轉(zhuǎn)速度和數(shù)據(jù)傳輸率都提高一倍，更新全部數(shù)據(jù)需要多少時(shí)間?標(biāo)準(zhǔn)答案：(1)磁盤上總數(shù)據(jù)量為1000×3000B=3000000B讀出全部數(shù)據(jù)所需時(shí)間為3000000B÷500B／ms=6000ms重新寫入全部數(shù)據(jù)所需時(shí)間為6000ms。所以，更新磁盤上全部數(shù)據(jù)所需的時(shí)間為2x(平均尋道時(shí)間+平均等待時(shí)間+數(shù)據(jù)傳送時(shí)間)+CPU更新時(shí)間=2×(30+120+6000)ms+4ms=12304ms(2)磁盤機(jī)旋轉(zhuǎn)速度提高一倍后，平均等待時(shí)間為60ms；數(shù)據(jù)傳輸率提高一倍后，數(shù)據(jù)傳送時(shí)間變?yōu)?000000B÷1000B／ms=3000ms更新全部數(shù)據(jù)所需時(shí)間為2×(30+60+3000)ms+4ms=6184ms知識(shí)點(diǎn)解析：暫無解析11、磁盤機(jī)由6個(gè)盤片組成，其中專設(shè)1個(gè)盤面為伺服面，其他的盤面作為記錄數(shù)據(jù)的盤面。盤存儲(chǔ)區(qū)域內(nèi)直徑為6．1cm，外直徑為12．9cm，道密度為220tpm，位密度為6000bpm，平均尋道時(shí)間為10ms，磁盤轉(zhuǎn)速為7200rpm。假定π=3，試計(jì)算：(1)數(shù)據(jù)盤面數(shù)和柱面數(shù)；(2)盤組容量是多少字節(jié)?(3)數(shù)據(jù)傳輸率是多少字節(jié)／秒?(4)從任一磁道讀取80000個(gè)字節(jié)數(shù)據(jù)的平均存取時(shí)間是多少?(5)假定系統(tǒng)配備上述磁盤機(jī)15臺(tái)，每個(gè)磁道分為64個(gè)扇區(qū)，試為該磁盤系統(tǒng)設(shè)計(jì)一個(gè)地址方案。標(biāo)準(zhǔn)答案：磁盤機(jī)有多個(gè)盤片，每個(gè)盤片有兩個(gè)盤面，每個(gè)盤面上有若干磁道，各記錄面上相同編號(hào)(位置)的諸磁道構(gòu)成一個(gè)圓柱面。通常將一條磁道劃分為若干個(gè)段，每個(gè)段稱為一個(gè)扇區(qū)或扇段，每個(gè)扇區(qū)存放一個(gè)定長(zhǎng)信息塊。(1)由于磁盤機(jī)有一個(gè)盤面是伺服盤，實(shí)際的數(shù)據(jù)盤面數(shù)=6×2—1=11(個(gè))柱面數(shù)=[(外直徑一內(nèi)直徑)／2]×道密度=[(12．9—6．1)／2]×220=748(個(gè))(2)以最內(nèi)圈磁道的周長(zhǎng)當(dāng)作每條磁道的長(zhǎng)度，故該盤組的存儲(chǔ)容量(非格式化容量)為：位密度×內(nèi)圈磁道的周長(zhǎng)×柱面數(shù)×數(shù)據(jù)盤面數(shù)=6000×π×6．1×748×11=903434400b=112929300B(3)數(shù)據(jù)傳輸率=轉(zhuǎn)速×每道的容量=120轉(zhuǎn)／s×13725B=1647000B／s(4)磁盤旋轉(zhuǎn)一圈時(shí)間為×60≈8．3ms平均存取時(shí)間=平均尋道時(shí)間+平均等待時(shí)間+讀取數(shù)據(jù)的時(shí)間=10+8．3／2+80000／1647000=10+4．15+48．6=62．75ms(5)磁盤系統(tǒng)共15臺(tái)磁盤機(jī)，驅(qū)動(dòng)器號(hào)(4位)；共有748個(gè)圓柱面，柱面號(hào)(10位)；共有11個(gè)記錄面，記錄面號(hào)(4位)；每個(gè)磁道有64個(gè)扇區(qū)，扇區(qū)號(hào)(6位)。最終的地址方案是：驅(qū)動(dòng)器號(hào)(4位)，柱面號(hào)(10位)，記錄面號(hào)(4位)，扇區(qū)號(hào)(6位)。知識(shí)點(diǎn)解析：暫無解析12、兄弟倆共同使用一個(gè)賬號(hào)，每次限存或取10元，存錢與取錢的進(jìn)程分別如下所示：intamount=0：SAVE(){intm1：m1=amount：m1=m1+10：amount=m1：}TAKE(){intm2；m2=amount：m2=m2一10：amount=m2：}由于兄弟倆可能同時(shí)存錢和取錢，因此兩個(gè)進(jìn)程是并發(fā)的。若哥哥先存了兩次錢，但在第三次存錢時(shí)弟弟在取錢。請(qǐng)問：(1)最后賬號(hào)amount上面可能出現(xiàn)的值是多少?(2)如何用P、V操作實(shí)現(xiàn)兩并發(fā)進(jìn)程的互斥執(zhí)行?標(biāo)準(zhǔn)答案：本題考查P、V操作實(shí)現(xiàn)進(jìn)程的互斥。(1)哥哥存兩次錢后，共享變量amount的值為20。哥哥的第三次存錢與弟弟的取錢同時(shí)進(jìn)行，如果兩者順序執(zhí)行，則最后amount的值為20；如果在一個(gè)進(jìn)程的執(zhí)行過程中進(jìn)行CPU調(diào)度，轉(zhuǎn)去執(zhí)行另一進(jìn)程，則最后amount的值取決于amount=m1及amount=m2的執(zhí)行先后次序，若前者先執(zhí)行，則最后amount的值為10，若后者先執(zhí)行，則最后amount的值為30。因此，最后賬號(hào)amount上可能出現(xiàn)的值有10、20、30。(2)在上述問題中，共享變量amount是一個(gè)臨界資源，為了實(shí)現(xiàn)兩并發(fā)進(jìn)程對(duì)它的互斥訪問，可為它設(shè)置一初值為1的互斥信號(hào)量mutex，并將上述算法修改為：intamount=0；semaphoremutex=1；／／g斥訪問amount變量的信號(hào)量cobegin{processSAVE(){intm1；P(mutex)：m1=amount：m1=m1+10：amount=m1；V(mutex)：}processTAKE(){intm2；P(mutex)；m2=amount：m2=m2—10；amount=m2；V(mutex)；}}coend知識(shí)點(diǎn)解析：暫無解析13、網(wǎng)絡(luò)協(xié)議的三個(gè)要素是什么?各有什么含義?標(biāo)準(zhǔn)答案：網(wǎng)絡(luò)協(xié)議：為完成網(wǎng)絡(luò)通信而建立的規(guī)則、標(biāo)準(zhǔn)或約定。由以下三個(gè)要素組成：(1)語法：即數(shù)據(jù)與控制信息的結(jié)構(gòu)或格式。(2)語義：即需要發(fā)出何種控制信息，完成何種動(dòng)作以及作出何種響應(yīng)。(3)同步：即事件實(shí)現(xiàn)順序的詳細(xì)說明。知識(shí)點(diǎn)解析：暫無解析14、數(shù)據(jù)鏈路層中的鏈路控制包括哪些功能?標(biāo)準(zhǔn)答案：數(shù)據(jù)鏈路層中的鏈路控制功能有：①鏈路管理。②幀定界。③流量控制。④差錯(cuò)控制。⑤將數(shù)據(jù)和控制信息區(qū)分開。⑥透明傳輸。⑦尋址。知識(shí)點(diǎn)解析：暫無解析15、有5個(gè)元素，其入棧次序?yàn)锳，B，C，D，E，在各種可能的出棧次序中，以元素C，D最先出棧(即C第一個(gè)且D第二個(gè)出棧)的次序有哪幾個(gè)?標(biāo)準(zhǔn)答案：3個(gè)：C，D，E，B，A；C，D，B，E，A；C，D，B，A，E。提示：此題考查的知識(shí)點(diǎn)是棧的后進(jìn)先出特點(diǎn)。按題意，C先出，說明A，B已入棧，D出棧再出棧，E可以入棧就出棧，可以有序列C，D，E，B，A。也可以B先出E再入，再出，得序列C，D，B，E，A。還可以B，A都出棧后，E再入棧出棧，得序列C，D，B，A，E。只有這三種情況。知識(shí)點(diǎn)解析：暫無解析16、試比較脫機(jī)I／／O和聯(lián)機(jī)I／O。標(biāo)準(zhǔn)答案：(1)脫機(jī)輸入／輸出方式是為了解決人機(jī)矛盾及CPU和I／O設(shè)備之間速度不匹配而提出的。它減少了CPU的空閑等待時(shí)間，提高了I／O速度，具體內(nèi)容是將用戶程序和數(shù)據(jù)在一臺(tái)外圍機(jī)的控制下，預(yù)先從低速輸入設(shè)備輸入到磁帶上，當(dāng)CPU需要這些程序和數(shù)據(jù)時(shí)再直接從磁帶機(jī)高速輸入到內(nèi)存，從而大大加快了程序的輸入過程，減少了CPU等待輸入的時(shí)間，這就是脫機(jī)輸入技術(shù)；當(dāng)程序運(yùn)行完畢或告一段落，CPU需要輸出時(shí)，無須直接把計(jì)算結(jié)果送至低速輸出設(shè)備，而是把結(jié)果高速地輸出到磁帶上，然后在外圍機(jī)的控制下，把磁帶上的計(jì)算結(jié)果由相應(yīng)的輸出設(shè)備輸出，這就是脫機(jī)輸出技術(shù)。(2)若這種輸入／輸出操作在主機(jī)控制下進(jìn)行則稱為聯(lián)機(jī)輸入/輸出方式。知識(shí)點(diǎn)解析：暫無解析某系統(tǒng)有R1、R2和R3三種資源，在T0時(shí)刻P1、P2、P3和P4四個(gè)進(jìn)程對(duì)資源的占用和需求情況如下表所示，此時(shí)系統(tǒng)的可用資源向量為(2，1，2)。試問：17、系統(tǒng)是否處于安全狀態(tài)?如安全，請(qǐng)給出一個(gè)安全序列。標(biāo)準(zhǔn)答案：利用安全性算法對(duì)T0時(shí)刻的資源分配情況進(jìn)行分析，可得到如下表所示的安全性檢測(cè)情況。可以看出，此時(shí)存在一個(gè)安全序列{P2，P3，P4，P1}，故該系統(tǒng)是安全的。知識(shí)點(diǎn)解析：暫無解析18、如果此時(shí)P1和P2均發(fā)出資源請(qǐng)求向量Request(1，0，1)，為了保證系統(tǒng)的安全性，應(yīng)該如何分配資源給這兩個(gè)進(jìn)程，7說明你所采用的策略的原因。標(biāo)準(zhǔn)答案：若此時(shí)P1發(fā)出資源請(qǐng)求Request1(1，0，1)，按銀行家算法進(jìn)行檢查：Request1(1，0，1)≤Need1(2，2，2)Request1(1，0，1)≤AVailable(2，1，2)試分配并修改相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，由此形成的資源分配情況如下表所示。知識(shí)點(diǎn)解析：暫無解析19、如果(2)中兩個(gè)請(qǐng)求立即得到滿足，系統(tǒng)此刻是否處于死鎖狀態(tài)?標(biāo)準(zhǔn)答案：如果(2)中兩個(gè)請(qǐng)求立即得到滿足，此刻系統(tǒng)并沒有立即進(jìn)入死鎖狀態(tài)，因?yàn)檫@時(shí)所有進(jìn)程沒有提出新的資源申請(qǐng)，全部進(jìn)程均沒有因資源請(qǐng)求沒有得到滿足而進(jìn)入阻塞狀態(tài)。只有當(dāng)進(jìn)程提出資源請(qǐng)求，且全部進(jìn)程都進(jìn)入阻塞狀態(tài)時(shí)，系統(tǒng)才處于死鎖狀態(tài)。知識(shí)點(diǎn)解析：暫無解析20、空閑磁盤空間的管理常采用哪幾種方式?UNIX系統(tǒng)采用的是何種方式?標(biāo)準(zhǔn)答案：空閑磁盤空間的管理常采用以下幾種方法：(1)空閑表法：屬于連續(xù)分配方式，它與內(nèi)存管理中的動(dòng)態(tài)分區(qū)分配方式相似。(2)空閑鏈表法：將所有空閑盤區(qū)鏈接成一條空閑鏈。根據(jù)構(gòu)成鏈的基本元素不同，可分為空閑盤塊鏈和空閑盤區(qū)鏈。(3)位示圖法。利用二進(jìn)制的一位來表示磁盤中每一個(gè)盤塊的使用情況，磁盤上的所有盤塊都有一個(gè)二進(jìn)制位與之對(duì)應(yīng)，從而由所有盤塊所對(duì)應(yīng)的位構(gòu)成一個(gè)集合，即位示圖。(4)成組鏈接法。結(jié)合空閑表法和空閑鏈表法而形成。UNIX系統(tǒng)采用的是成組鏈接法。知識(shí)點(diǎn)解析：暫無解析考研計(jì)算機(jī)專業(yè)基礎(chǔ)綜合（綜合應(yīng)用題）模擬試卷第3套一、綜合應(yīng)用題(本題共20題，每題1.0分，共20分。)1、為什么要引入段頁式存儲(chǔ)管理?說明在段頁式存儲(chǔ)管理系統(tǒng)中的地址變換過程。標(biāo)準(zhǔn)答案：(1)為了獲得分段在邏輯上的優(yōu)點(diǎn)和分頁在管理存儲(chǔ)空間方面的優(yōu)點(diǎn)，兼用分段和分頁兩種方法，設(shè)計(jì)出了段頁式存儲(chǔ)管理技術(shù)來實(shí)現(xiàn)對(duì)存儲(chǔ)器的管理。(2)地址變換過程如下：首先，由段表控制寄存器確定段表在主存中的位置。其次，將虛地址中的段號(hào)和控制寄存器中的段表大小比較，以確保其訪問的有效性。最后，硬件地址轉(zhuǎn)換機(jī)構(gòu)根據(jù)虛地址中的段號(hào)S，得到欲訪問段在該作業(yè)的段表中的表目，并驗(yàn)證存取權(quán)限，以確保本次存儲(chǔ)訪問是允許的。然后，檢查分段存在標(biāo)識(shí)(判狀態(tài)位)，如果訪問的段在主存，則通過段表找到該段的頁表存放地址，再根據(jù)虛地址中的頁號(hào)P查頁表，找到該頁所對(duì)應(yīng)的內(nèi)存塊號(hào)與虛地址中的頁內(nèi)地址d相加形成物理地址；若訪問的分段不在主存，則由硬件產(chǎn)生缺段中斷。如果一完整的分段不在主存，則說明該段所有的頁面均不在主存，因而也沒有相應(yīng)的頁表。操作系統(tǒng)對(duì)缺頁中斷響應(yīng)后，必須重新構(gòu)造其頁表，并裝入一個(gè)或多個(gè)所需的頁面。此時(shí)，開始繼續(xù)執(zhí)行本次的存儲(chǔ)訪問。當(dāng)頁表的位置和大小確定后，其存儲(chǔ)訪問過程如先前描述過的頁面系統(tǒng)一樣進(jìn)行。知識(shí)點(diǎn)解析：暫無解析2、段頁式存儲(chǔ)管理方式中如何實(shí)現(xiàn)地址變換?標(biāo)準(zhǔn)答案：首先，必須配置一段表寄存器，在其中存放段表始址和段長(zhǎng)TL。進(jìn)行地址變換時(shí)，先利用段號(hào)S，與段長(zhǎng)TL進(jìn)行比較，若S＜TL，表示未越界(若S≥TL，表示段號(hào)太大，訪問越界，產(chǎn)生越界中斷信號(hào))，于是利用段表始址和段號(hào)來求出該段對(duì)應(yīng)的段表項(xiàng)在段表中的位置，從中求出該段的頁表始址，并利用邏輯地址中的段內(nèi)頁號(hào)P來獲得對(duì)應(yīng)頁的頁表項(xiàng)位置，從中讀出該頁所在的物理塊號(hào)b，再用塊號(hào)b和頁內(nèi)地址構(gòu)成物理地址。知識(shí)點(diǎn)解析：暫無解析3、二叉排序樹采用二叉鏈表存儲(chǔ)。寫一個(gè)算法，刪除結(jié)點(diǎn)值是X的結(jié)點(diǎn)。要求刪除該結(jié)點(diǎn)后，此樹仍然是一棵二叉排序樹，并且高度沒有增長(zhǎng)(注意：可不考慮被刪除的結(jié)點(diǎn)是根的情況)。標(biāo)準(zhǔn)答案：在二叉排序樹上刪除結(jié)點(diǎn)，首先要查找該結(jié)點(diǎn)。查找成功后，若該結(jié)點(diǎn)無左子樹，則可直接將其右子樹的根結(jié)點(diǎn)接到其雙親結(jié)點(diǎn)上；若該結(jié)點(diǎn)有左子樹，則將其左子樹中按中序遍歷的最后一個(gè)結(jié)點(diǎn)代替該結(jié)點(diǎn)，從而不增加樹的高度。voidDelete(BSTreebst，keytypeX){／／在二叉排序樹bst上，刪除其關(guān)鍵字為X的結(jié)點(diǎn)BSTreef，P=bst：while(P&&p一＞key!=X)／／查找值為X的結(jié)點(diǎn)if(p一＞key＞X){f=P；p=p-＞lehild；}else{f=p；P=p一＞rehild；}if(P==null){prinff(”無關(guān)鍵字為x的結(jié)點(diǎn)＼n”)；exit(0)：}if(p-＞lchild==null){／／被刪結(jié)點(diǎn)無左子樹if(f一＞lchild==P)f一＞lchild=P一＞rchild；／／將被刪結(jié)點(diǎn)的右子樹接到其雙親上elsef一＞rchild=p一＞rchild；}else{q=p；s=p-＞lchild；／／被刪結(jié)點(diǎn)有左子樹while(s-＞rchild!=null)／／查左子樹中最右下的結(jié)點(diǎn)(中序最后結(jié)點(diǎn)){q=s；s=s-＞rchild；}p-＞key=s-＞key；／／結(jié)點(diǎn)值用其左子樹最右下的結(jié)點(diǎn)的值代替if(q==p)p一＞lchild=s一＞lchild；／／被刪結(jié)點(diǎn)左子樹的根結(jié)點(diǎn)無右子女elseq-＞rchild=s-＞lchild：／／s是被刪結(jié)點(diǎn)左子樹中序序列最后一個(gè)結(jié)點(diǎn)free(s)；}}知識(shí)點(diǎn)解析：暫無解析4、試述CSMA／CD介質(zhì)訪問控制技術(shù)的工作原理。標(biāo)準(zhǔn)答案：CSMA／CD介質(zhì)訪問控制技術(shù)被廣泛應(yīng)用于以太網(wǎng)中。CSMA／CD的工作原理是：當(dāng)某個(gè)站點(diǎn)要發(fā)送數(shù)據(jù)時(shí)，它首先監(jiān)聽介質(zhì)：(1)如果介質(zhì)是空閑的，則發(fā)送；(2)如果介質(zhì)是忙的，則繼續(xù)監(jiān)聽，一旦發(fā)現(xiàn)介質(zhì)空閑，就立即發(fā)送：(3)站點(diǎn)在發(fā)送幀的同時(shí)需要繼續(xù)監(jiān)聽是否發(fā)生沖突(碰撞)，若在幀發(fā)送期間檢測(cè)到?jīng)_突，就立即停止發(fā)送，并向介質(zhì)發(fā)送一串阻塞信號(hào)以強(qiáng)化沖突，保證讓總線上的其他站點(diǎn)都知道已發(fā)生了沖突；(4)發(fā)送了阻塞信號(hào)后，等待一段隨機(jī)時(shí)間，返回步驟(1)重試。知識(shí)點(diǎn)解析：暫無解析5、CSMA／CA是如何實(shí)現(xiàn)“沖突避免”的?標(biāo)準(zhǔn)答案：采用三種機(jī)制來實(shí)現(xiàn)：預(yù)約信道、正向確認(rèn)和RTS／CTS機(jī)制。(1)預(yù)約信道。發(fā)送站點(diǎn)利用“傳輸持續(xù)時(shí)間”字段向所有其他無線站點(diǎn)通告本站點(diǎn)將要占用信道多長(zhǎng)時(shí)間，以便讓其他站在這段時(shí)間內(nèi)不要發(fā)送數(shù)據(jù)，以避免沖突。(2)正向確認(rèn)機(jī)制。IEEE802．11規(guī)定若接收站點(diǎn)正確收到以它為目的地的數(shù)據(jù)幀時(shí)，就應(yīng)向發(fā)送數(shù)據(jù)幀的站點(diǎn)發(fā)送一個(gè)ACK幀作為接收成功的肯定回答，否則將不采取任何動(dòng)作。發(fā)送站點(diǎn)在發(fā)送完數(shù)據(jù)幀的規(guī)定時(shí)間內(nèi)若沒有收到ACK幀，就需要多次重發(fā)數(shù)據(jù)幀，直到收到ACK幀為止。(3)RTS／CTS機(jī)制。通過請(qǐng)求發(fā)送RTS／允許發(fā)送CTS選項(xiàng)，以解決隱蔽站的沖突問題。知識(shí)點(diǎn)解析：暫無解析6、說明頁表的組成與程序邏輯地址到內(nèi)存物理地址的變換過程?？毂硎且欢ㄒ械膯?說明快表內(nèi)容的組成與讀寫原理。標(biāo)準(zhǔn)答案：頁表由若干表項(xiàng)組成，每個(gè)虛頁號(hào)對(duì)應(yīng)頁表中的一個(gè)表項(xiàng)，表項(xiàng)的內(nèi)容可以由如下部分組成：最重要的是一個(gè)虛頁被分配在主存中的實(shí)際頁號(hào)，還可能包括頁裝入(有效)位、修改標(biāo)記位、替換控制位、其他保護(hù)位等組成的控制位字段。地址變換過程：用虛地址中的虛頁號(hào)與頁表基地址相加，求出對(duì)應(yīng)該虛頁的頁表表項(xiàng)在主存中的實(shí)際地址，從該表項(xiàng)的實(shí)頁號(hào)字段取出實(shí)頁號(hào)再拼上虛地址中的頁內(nèi)地址，就得到讀主存數(shù)據(jù)用的實(shí)際地址。為了解決當(dāng)要讀頁內(nèi)的某個(gè)存儲(chǔ)單元時(shí)，需讀兩次主存才能取得要讀的數(shù)據(jù)的問題(讀兩次主存過程：首先要讀一次主存，通過查頁表求出實(shí)存地址，然后再讀一次主存)，設(shè)立一個(gè)完全用快速硬件實(shí)現(xiàn)的容量很小的快速頁表，又稱轉(zhuǎn)換旁路緩沖器，用于存放在頁表中使用最頻繁的、為數(shù)不多的那些表項(xiàng)的內(nèi)容?？毂碇饕刑擁撎?hào)和實(shí)頁號(hào)兩項(xiàng)內(nèi)容。經(jīng)快表實(shí)現(xiàn)的地址轉(zhuǎn)換過程：用虛地址中的虛頁號(hào)去與快表中虛頁號(hào)字段的內(nèi)容相比較，與哪個(gè)表項(xiàng)中的虛頁號(hào)相同，則可以取出該表項(xiàng)中的實(shí)頁號(hào)，并與頁內(nèi)地址拼接出主存實(shí)際地址。這一過程可以很快完成，類似于高速緩；中存儲(chǔ)器的運(yùn)行原理。當(dāng)在快表中找不到該虛頁號(hào)時(shí)，就要到主存中經(jīng)慢表找出該虛頁號(hào)對(duì)應(yīng)的實(shí)頁號(hào)，在得到一個(gè)主存實(shí)際地址的同時(shí)用該虛頁號(hào)和實(shí)頁號(hào)替換快表的一個(gè)表項(xiàng)的內(nèi)容，以反映這次操作的形勢(shì)。知識(shí)點(diǎn)解析：暫無解析7、有5個(gè)元素，其入棧次序?yàn)锳，B，C，D，E，在各種可能的出棧次序中，以元素C，D最先出棧(即C第一個(gè)且D第二個(gè)出棧)的次序有哪幾個(gè)?標(biāo)準(zhǔn)答案：3個(gè)：C，D，E，B，A；C，D，B，E，A；C，D，B，A，E。提示：此題考查的知識(shí)點(diǎn)是棧的后進(jìn)先出特點(diǎn)。按題意，C先出，說明A，B已入棧，D出棧再出棧，E可以入棧就出棧，可以有序列C，D，E，B，A。也可以B先出E再入，再出，得序列C，D，B，E，A。還可以B，A都出棧后，E再入棧出棧，得序列C，D，B，A，E。只有這三種情況。知識(shí)點(diǎn)解析：暫無解析8、設(shè)排序二叉樹中結(jié)點(diǎn)的結(jié)構(gòu)由三個(gè)域構(gòu)成：數(shù)據(jù)域data，指向左兒子結(jié)點(diǎn)的指針域left，指向右兒子結(jié)點(diǎn)的指針域right。設(shè)data域?yàn)檎麛?shù)，該二叉樹樹根結(jié)點(diǎn)地址為T?，F(xiàn)給出一個(gè)正整數(shù)x。請(qǐng)編寫非遞歸程序，實(shí)現(xiàn)將data域的值小于等于x的結(jié)點(diǎn)全部刪除。標(biāo)準(zhǔn)答案：利用二叉排序樹的性質(zhì)，從根結(jié)點(diǎn)開始查找，若根結(jié)點(diǎn)的值小于等于x，則根結(jié)點(diǎn)及其左子樹均應(yīng)刪除，然后以右子樹的根結(jié)點(diǎn)為樹根，重新開始查找。若根結(jié)點(diǎn)的值大于x，則順左子樹向下查找，直到某結(jié)點(diǎn)的值小于等于戈，則該結(jié)點(diǎn)及其左子樹均應(yīng)刪除。下面設(shè)計(jì)一查找算法，確定被刪除子樹的根結(jié)點(diǎn)，再設(shè)計(jì)一刪除算法，刪除以被刪結(jié)點(diǎn)為根的子樹。typedefstructnode{intdata；structnode*left，*right；}BiTNode，*BSTree；voidDelTree(BSTreer){／／非遞歸刪除以r為根的二叉排序樹BSTreeS[]；／／棧，容量足夠大，棧中元素是二叉排序樹結(jié)點(diǎn)的指針BSTreeP；inttop=0；while(r!=null||top>0){while(r!=null){S[++top]=r；r=r一>left；}／／沿左分支向下if(top>0)／／退棧，沿棧頂結(jié)點(diǎn)的右子樹向下刪除，釋放被刪除結(jié)點(diǎn)空間{P=S[top--]；r=p->right；free(P)；}}}／／DelTreevoidDeleteAllx(BSTreeT，intx){／／在二叉排序樹T中，刪除所有小于等于x的結(jié)點(diǎn)BSTreep=T，q；while(T&&T一>data<=X){／／根結(jié)點(diǎn)的值小于等于xP=T；T=T一>right；p一>right=null；DelTree(P)；}／／刪除二叉樹P，刪除持續(xù)到”根”結(jié)點(diǎn)值大于x或T為空樹為止if(T){q=T;P=T一>left；while(P&&P一>data>x){／／沿根結(jié)點(diǎn)左分支向下，查小于等于x的結(jié)點(diǎn)while(P&&p一>data>x){q=p;p=p一>left；}／／q記P的雙親if(P)／／p結(jié)點(diǎn)的值小于等于X{q一>left=P一>right；p一>right=null；DelTree(P)；}P=q一>left；／／再查原P的右子樹中小于等于X的結(jié)點(diǎn)}}}知識(shí)點(diǎn)解析：暫無解析9、某模型機(jī)的數(shù)據(jù)通路結(jié)構(gòu)如下圖所示。用寄存器傳送語句(如PC→MAR)，擬出下列指令從讀取到執(zhí)行的完整流程。(1)數(shù)據(jù)傳送指令MOVX(R0)，Y(R1)，源和目的操作數(shù)地址均采用變址尋址，第1個(gè)參數(shù)X為源操作數(shù)的形式地址，第2個(gè)參數(shù)為目的操作數(shù)的形式地址，分別位于指令的第2個(gè)和第3個(gè)存儲(chǔ)字。(2)數(shù)據(jù)求反指令COM一一(R0)，采用自減型寄存器間接尋址，結(jié)果送回自減后的地址單元。標(biāo)準(zhǔn)答案：(1)MOVX(R0)，Y(R1)指令執(zhí)行流程中的前3步是完成取指令都有的公操作；接下來的5步是去主存中取源操作數(shù)，把取出的數(shù)放在暫存器C中；然后的4步是形成目的操作數(shù)地址；最后2步完成傳送操作。①PC→MAR，Read；取指令②M→MDR→IR③PC+1→PC④PC→MAR，Read；取源操作數(shù)形式地址⑤M→MDR→C⑥PC+1→PC⑦C+R0→MAR，Read；形成源操作數(shù)有效地址，并取源操作數(shù)⑧M→MDR→C；源操作數(shù)暫存c中⑨PC→MAR，Read；取目的操作數(shù)形式地址⑩M→MDR→DPC+1→PCD+R1→MAR；形成目的操作數(shù)有效地址C→MDR；將源操作數(shù)送存儲(chǔ)器數(shù)據(jù)寄存器MDR→M，Write；將源操作數(shù)寫入目的有效地址中(2)COM--(R0)指令執(zhí)行流程中的前3步是取指令操作；接下來的2步是去主存中取源操作數(shù)，把取出的數(shù)放在暫存器D中；然后將D的內(nèi)容取反，寫入目的地址中。①PC→MAR，Read；取指令②M→MDR→IR③PC+1→PC④R0一1→R0，R0-1→MAR，Read；修改R0的內(nèi)容(源和目的操作數(shù)地址)⑤M→MDR→D；取出源操作數(shù)⑥D(zhuǎn)→MDR；將源操作數(shù)取反⑦M(jìn)DR→M，Write；寫入目的地址中知識(shí)點(diǎn)解析：暫無解析10、試分析，在第一級(jí)磁盤容錯(cuò)技術(shù)和第二級(jí)磁盤容錯(cuò)技術(shù)中，各采取了哪些容錯(cuò)措施?什么是寫后讀校驗(yàn)?標(biāo)準(zhǔn)答案：在第一級(jí)磁盤容錯(cuò)技術(shù)中，包括以下容錯(cuò)措施：(1)雙份目錄和雙份文件分配表。在磁盤上存放的文件目錄和文件分配表FAT均為文件管理所用的重要數(shù)據(jù)結(jié)構(gòu)，所以為之建立備份。(2)在系統(tǒng)每次加電啟動(dòng)時(shí)都要對(duì)兩份目錄和兩份FAT進(jìn)行檢查，以驗(yàn)證它們的一致性。在第二級(jí)磁盤容錯(cuò)技術(shù)中，包括以下容錯(cuò)措施：(1)磁盤鏡像。在同一磁盤控制器下增設(shè)一個(gè)完全相同的磁盤驅(qū)動(dòng)器，在每次向文件服務(wù)器的主磁盤寫入數(shù)據(jù)后，都要采用寫后讀校驗(yàn)方式將數(shù)據(jù)再同樣地寫到備份磁盤上，使兩者具有完全相同的位像圖。(2)磁盤雙工。將兩臺(tái)磁盤驅(qū)動(dòng)器分別接到兩個(gè)磁盤控制器上，同樣使這兩臺(tái)磁盤機(jī)鏡像成對(duì)，從而在磁盤控制器發(fā)生故障時(shí)起到數(shù)據(jù)保護(hù)的作用。在磁盤雙工時(shí)，由于每一個(gè)磁盤都有自己的獨(dú)立通道，故可以同時(shí)(并行)地將數(shù)據(jù)寫入磁盤。在讀入數(shù)據(jù)時(shí)，可采用分離搜索技術(shù)，從響應(yīng)快的通道上取得數(shù)據(jù)，因而加快了對(duì)數(shù)據(jù)的讀取速度。(3)熱修復(fù)重定向和寫后讀校驗(yàn)。兩者均用于防止將數(shù)據(jù)寫入有缺陷的盤塊中。就熱修復(fù)重定向而言，系統(tǒng)將一定的磁盤容量作為熱修復(fù)重定向區(qū)，用于存放當(dāng)發(fā)現(xiàn)盤塊有缺陷時(shí)的待寫數(shù)據(jù)，并對(duì)寫入該區(qū)的所有數(shù)據(jù)進(jìn)行登記，方便將來對(duì)數(shù)據(jù)進(jìn)行訪問。而寫后讀校驗(yàn)則是為了保證所有寫入磁盤的數(shù)據(jù)都能寫入到完好的盤塊中，故在每次從內(nèi)存緩沖區(qū)向磁盤中寫入一個(gè)數(shù)據(jù)塊后，應(yīng)立即從磁盤上讀出該數(shù)據(jù)塊并送至另一緩沖區(qū)中，再將該緩沖區(qū)中內(nèi)容與原內(nèi)存緩沖區(qū)中在寫后仍保留的數(shù)據(jù)進(jìn)行比較。若兩者一致，便認(rèn)為此次寫入成功，可繼續(xù)寫入下一個(gè)盤塊；否則，則重寫。若重寫后兩者仍不一致，則認(rèn)為該盤塊有缺陷，此時(shí)便將應(yīng)寫入該盤塊的數(shù)據(jù)寫入熱修復(fù)重定向區(qū)中，并將該損壞盤塊的地址記錄在壞盤塊表中。知識(shí)點(diǎn)解析：暫無解析11、某操作系統(tǒng)的磁盤文件空間共有500塊，若用字長(zhǎng)為32位的位示圖管理磁盤空間，試問：(1)位示圖需多少個(gè)字?(2)第i字第j位對(duì)應(yīng)的塊號(hào)是多少?(3)給出申請(qǐng)／歸還一塊的工作流程。標(biāo)準(zhǔn)答案：(1)位示圖占用字?jǐn)?shù)為500÷32=16(向上取整)個(gè)字。(2)第i字第j位對(duì)應(yīng)的塊號(hào)N=32×i+j。(3)申請(qǐng)時(shí)自上至下、自左至右掃描位示圖跳過為1的位，找到第一個(gè)遇到的0位，根據(jù)它是第i字第j位算出對(duì)應(yīng)塊號(hào)，并分配出去。歸還時(shí)已知塊號(hào)，塊號(hào)÷32算出第i字第j位并把位示圖相應(yīng)位清零。知識(shí)點(diǎn)解析：暫無解析12、簡(jiǎn)述字節(jié)多路通道、數(shù)組選擇通道和數(shù)組多路通道。標(biāo)準(zhǔn)答案：(1)字節(jié)多路通道含有許多非分配型子通道并分別連接在低速、中速I／O設(shè)備上，子通道按時(shí)間片輪轉(zhuǎn)方式共享，按字節(jié)方式進(jìn)行數(shù)據(jù)傳送。具體而言，當(dāng)?shù)谝粋€(gè)子通道控制其I／O設(shè)備完成一字節(jié)的交換后，便立即騰出字節(jié)多路通道(主通道)給第二個(gè)子通道使用；當(dāng)?shù)诙€(gè)子通道也交換完一字節(jié)后，又把主通道讓給第三個(gè)子通道使用。以此類推。轉(zhuǎn)輪一周后，重又返回由第一個(gè)子通道去使用主通道。(2)數(shù)組選擇通道只含有一個(gè)分配型子通道，一段時(shí)間內(nèi)只能執(zhí)行一道通道程序、控制一臺(tái)設(shè)備按數(shù)組方式進(jìn)行數(shù)據(jù)傳送。通道被某臺(tái)設(shè)備占用后便一直處于獨(dú)占狀態(tài)，直至設(shè)備數(shù)據(jù)傳輸完畢釋放該通道，故通道利用率較低。因此這種方式主要用于連接多臺(tái)高速設(shè)備。(3)數(shù)組多路通道是將數(shù)組選擇通道傳輸速率高和字節(jié)多路通道能使各子通道分時(shí)并行操作的優(yōu)點(diǎn)相結(jié)合而形成的一種新通道。其含有多個(gè)非分配型子通道并分別連接在高速、中速I／O設(shè)備上，子通道按時(shí)間片輪轉(zhuǎn)方式共享主通道，按數(shù)組方式進(jìn)行數(shù)據(jù)傳送，因而既具有很高的數(shù)據(jù)傳輸速率，又能獲得令人滿意的通道利用率。知識(shí)點(diǎn)解析：暫無解析13、計(jì)算機(jī)網(wǎng)絡(luò)是由哪些元素組成的?標(biāo)準(zhǔn)答案：計(jì)算機(jī)網(wǎng)絡(luò)由網(wǎng)絡(luò)軟件和網(wǎng)絡(luò)硬件兩大部分組成。網(wǎng)絡(luò)軟件主要包括：網(wǎng)絡(luò)協(xié)議、通信軟件、網(wǎng)絡(luò)操作系統(tǒng)等；網(wǎng)絡(luò)硬件主要包括網(wǎng)絡(luò)結(jié)點(diǎn)(又稱網(wǎng)絡(luò)單元)和通信鏈路。知識(shí)點(diǎn)解析：暫無解析14、簡(jiǎn)述移動(dòng)IP的通信過程。標(biāo)準(zhǔn)答案：移動(dòng)主機(jī)在不同子網(wǎng)間漫游，其數(shù)據(jù)包的通信過程如下：(1)本地代理和外地代理不停地向網(wǎng)上發(fā)送代理廣告消息，以聲明自己的存在。(2)移動(dòng)主機(jī)收到這些消息，確定自己是在本地網(wǎng)還是在外地網(wǎng)。(3)如果移動(dòng)主機(jī)發(fā)現(xiàn)自己仍在本地網(wǎng)，即收到的是本地代理發(fā)來的消息，則不啟動(dòng)移動(dòng)功能。如果是從外地網(wǎng)絡(luò)重新返回的，則向本地代理發(fā)出取消注冊(cè)的消息，聲明自己回到了本地網(wǎng)。(4)當(dāng)移動(dòng)主機(jī)檢測(cè)到它移動(dòng)到外地網(wǎng)時(shí)，則獲得接管地址(CoA)。(5)然后移動(dòng)主機(jī)向本地代理登記，表明自己已離開本地網(wǎng)，把所獲得的接管地址通知本地代理。(6)登記完畢后，所有發(fā)給移動(dòng)主機(jī)的數(shù)據(jù)包被本地代理截獲，經(jīng)本地代理封裝后，通過隧道發(fā)到外地網(wǎng)絡(luò)的外地代理FA(第一種CoA地址)或移動(dòng)主機(jī)自身(第二種CoA地址)。第一種情況下，外地代理再把數(shù)據(jù)包轉(zhuǎn)發(fā)給移動(dòng)主機(jī)。此時(shí)，數(shù)據(jù)包在不同子網(wǎng)間傳送成功。(7)移動(dòng)主機(jī)發(fā)送數(shù)據(jù)到一般的IP主機(jī)時(shí)，按正常的IP尋址方法發(fā)送，不必通過本地代理。上述工作過程有效地解決了移動(dòng)主機(jī)在子網(wǎng)間漫游通信的問題。但是，卻在路由上存在著問題。當(dāng)移動(dòng)主機(jī)發(fā)送數(shù)據(jù)時(shí)，不管它是在本地網(wǎng)絡(luò)還是在外地網(wǎng)絡(luò)，它始終保留了它的本地網(wǎng)絡(luò)地址，當(dāng)它發(fā)送數(shù)據(jù)包時(shí)，可以用通常的IP協(xié)議發(fā)送。反之，當(dāng)一般IP主機(jī)給移動(dòng)主機(jī)發(fā)送數(shù)據(jù)包時(shí)，首先到達(dá)移動(dòng)主機(jī)的本地代理(HA)。HA再根據(jù)收到的移動(dòng)主機(jī)當(dāng)前的接管地址CoA(假定為第一種地址)，將數(shù)據(jù)包發(fā)往外地網(wǎng)絡(luò)，由外地代理最終將數(shù)據(jù)包發(fā)給移動(dòng)主機(jī)，這就出現(xiàn)了路由的“三角問題”。最差的情況是當(dāng)發(fā)送數(shù)據(jù)包的一般IP主機(jī)靠近移動(dòng)主機(jī)所在的外地網(wǎng)絡(luò)或移動(dòng)主機(jī)已經(jīng)漫游到發(fā)送主機(jī)所在的網(wǎng)絡(luò)時(shí)，發(fā)送的數(shù)據(jù)包卻仍要先到達(dá)移動(dòng)主機(jī)的本地代理，再由本地代理發(fā)到外地代理，最后到達(dá)移動(dòng)主機(jī)，這不僅增大了傳輸延遲，同時(shí)對(duì)一些延遲敏感的業(yè)務(wù)如音頻、視頻等造成極大的損害。其次，數(shù)據(jù)包在網(wǎng)絡(luò)中運(yùn)行時(shí)間過長(zhǎng)，浪費(fèi)了網(wǎng)絡(luò)資源，增加了網(wǎng)絡(luò)負(fù)擔(dān)。知識(shí)點(diǎn)解析：暫無解析15、并發(fā)請(qǐng)求過程中服務(wù)器的處理方案及建立傳輸連接的過程有哪些?標(biāo)準(zhǔn)答案：解決服務(wù)器處理并發(fā)請(qǐng)求的方案基本上有兩種：一是采用并發(fā)服務(wù)處理器的方法，二是采用重復(fù)服務(wù)器的方法?？蛻襞c并發(fā)服務(wù)器建立傳輸連接的工作過程為：(1)主服務(wù)器在固定的端口號(hào)上準(zhǔn)備接收客戶的連接請(qǐng)求：(2)客戶向服務(wù)器發(fā)出連接建立請(qǐng)求：(3)主服務(wù)器接收到客戶的連接請(qǐng)求后，激活相應(yīng)的從服務(wù)器：(4)主服務(wù)器通知客戶從服務(wù)器的端口號(hào)，并關(guān)閉與客戶的連接：(5)從服務(wù)器準(zhǔn)備接收客戶的連接建立請(qǐng)求：(6)客戶向從服務(wù)器發(fā)送連接建立請(qǐng)求。知識(shí)點(diǎn)解析：暫無解析16、利用比較的方法進(jìn)行排序，在最壞的情況下能達(dá)到的最好時(shí)間復(fù)雜性是什么?請(qǐng)給出詳細(xì)證明。標(biāo)準(zhǔn)答案：假定待排序的記錄有n個(gè)。由于含n個(gè)記錄的序列可能出現(xiàn)的狀態(tài)有n!個(gè)，則描述n個(gè)記錄排序過程的判定樹必須有n!個(gè)葉子結(jié)點(diǎn)。因?yàn)槿羯僖粋€(gè)葉子，則說明尚有兩種狀態(tài)沒有分辨出來。我們知道，若二叉樹高度是h，則葉子結(jié)點(diǎn)個(gè)數(shù)最多為2h-1；反之，若有u個(gè)葉子結(jié)點(diǎn)，則二叉樹的高度至少為(log2u)+1。這就是說，描述n個(gè)記錄排序的判定樹必定存在一條長(zhǎng)度為log2(n!)的路徑。即任何一個(gè)借助“比較”進(jìn)行排序的算法，在最壞情況下所需進(jìn)行的比較次數(shù)至少是log2(n!)。根據(jù)斯特林公式，有l(wèi)og2(n!)=O(nlog2n)。即借助于“比較”進(jìn)行排序的算法在最壞情況下能達(dá)到的最好時(shí)間復(fù)雜度為O(nlog2n)。知識(shí)點(diǎn)解析：暫無解析設(shè)某機(jī)有5級(jí)中斷L0、L1、L2、L3、L4，其中斷響應(yīng)優(yōu)先次序?yàn)長(zhǎng)0最高、L1次之、…、L4最低?，F(xiàn)在要球?qū)⒅袛嗵幚泶涡蚋臑長(zhǎng)1→L3→L0→L4→L2，試問：17、下表中各級(jí)中斷處理程序的各中斷級(jí)屏蔽值如何設(shè)置(每級(jí)對(duì)應(yīng)一位，該位為“0”表示允許中斷，該位為“1”表示中斷屏蔽)?標(biāo)準(zhǔn)答案：中斷處理程序如下：知識(shí)點(diǎn)解析：暫無解析18、若這5級(jí)中斷同時(shí)都發(fā)出中斷請(qǐng)求，按更改后的次序畫出進(jìn)入各級(jí)中斷處理程序的過程示意圖。標(biāo)準(zhǔn)答案：示意圖如下：知識(shí)點(diǎn)解析：暫無解析19、網(wǎng)絡(luò)協(xié)議的三個(gè)要素是什么?備有什么含義?標(biāo)準(zhǔn)答案：網(wǎng)絡(luò)協(xié)議：為完成網(wǎng)絡(luò)通信而建立的規(guī)則、標(biāo)準(zhǔn)或約定。由以下三個(gè)要素組成：(1)語法：即數(shù)據(jù)與控制信息的結(jié)構(gòu)或格式。(2)語義：即需要發(fā)出何種控制信息，完成何種動(dòng)作以及作出何種響應(yīng)。(3)同步：即事件實(shí)現(xiàn)順序的詳細(xì)說明。知識(shí)點(diǎn)解析：暫無解析20、物理層要解決什么問題?物理層的主要特點(diǎn)是什么?試給出數(shù)據(jù)通信系統(tǒng)的模型并說明其主要組成構(gòu)件的作用。標(biāo)準(zhǔn)答案：(1)物理層考慮的是怎樣才能在連接各種計(jì)算機(jī)的傳輸媒體上傳輸數(shù)據(jù)比特流，而不是指連接計(jì)算機(jī)的具體的物理設(shè)備或具體的傳輸媒體。(2)現(xiàn)有的網(wǎng)絡(luò)中物理設(shè)備和傳輸媒體種類繁多，通信手段也有許多不同的方式。物理層的作用正是．要盡可能地屏蔽掉這些差異，使數(shù)據(jù)鏈路層感覺不到這些差異，這樣數(shù)據(jù)鏈路層只需要考慮如何完成本層的協(xié)議和服務(wù)，而不必考慮網(wǎng)絡(luò)具體的傳輸媒體是什么。物理層的重要任務(wù)是確定與傳輸媒體的接口的一些特性。(3)一個(gè)數(shù)據(jù)通信系統(tǒng)可劃分為三大部分：源系統(tǒng)(發(fā)送端)、傳輸系統(tǒng)(或傳輸網(wǎng)絡(luò))和目的系統(tǒng)(接收端)。源系統(tǒng)一般包括以下兩個(gè)部分：①源點(diǎn)：源點(diǎn)設(shè)備產(chǎn)生要傳輸?shù)臄?shù)據(jù)。例如正文輸入到PC，產(chǎn)生輸出的數(shù)字比特流。②發(fā)送器：通常源點(diǎn)生成的數(shù)據(jù)要通過發(fā)送器編碼后才能在傳輸系統(tǒng)中進(jìn)行傳輸。例如，調(diào)制解調(diào)器將PC輸出的數(shù)字比特流轉(zhuǎn)換成能夠在電話線上傳輸?shù)哪M信號(hào)。目的系統(tǒng)一般包括以下兩部分：①接收器：接收傳輸系統(tǒng)傳送過來的信號(hào)，并將其轉(zhuǎn)換為能夠被目的設(shè)備處理的信息。例如，調(diào)制解調(diào)器接收來自傳輸線路上的模擬信號(hào)，并將其轉(zhuǎn)換成數(shù)字比特流。②終點(diǎn)：終點(diǎn)設(shè)備從接收器獲取傳送過來的信息。知識(shí)點(diǎn)解析：暫無解析考研計(jì)算機(jī)專業(yè)基礎(chǔ)綜合（綜合應(yīng)用題）模擬試卷第4套一、綜合應(yīng)用題(本題共20題，每題1.0分，共20分。)1、OSPF協(xié)議采用什么路由算法?有什么特點(diǎn)?標(biāo)準(zhǔn)答案：OSPF是一種基于鏈路狀態(tài)的路由協(xié)議，需要每個(gè)路由器向其同一管理域的所有其他路由器發(fā)送鏈路狀態(tài)廣播信息。在OSPF的鏈路狀態(tài)廣播中包括所有接口信息、所有的量度和其他一些變量。利用OSPF的路由器首先必須收集有關(guān)的鏈路狀態(tài)信息，并根據(jù)一定的算法計(jì)算出到每個(gè)結(jié)點(diǎn)的最短路徑。而基于距離一向量的路由協(xié)議僅向其鄰接路由器發(fā)送有關(guān)路由更新信息。與RIP不同，OSPF將一個(gè)自治域再劃分為區(qū)，相應(yīng)地有兩種類型的路由選擇方式：當(dāng)源和目的地在同一區(qū)時(shí)，采用區(qū)內(nèi)路由選擇；當(dāng)源和目的地在不同區(qū)時(shí)，則采用區(qū)間路由選擇。這就大大減少了網(wǎng)絡(luò)開銷，并增加了網(wǎng)絡(luò)的穩(wěn)定性。當(dāng)一個(gè)區(qū)內(nèi)的路由器出了故障時(shí)并不影響自治域內(nèi)其他區(qū)路由器的正常工作，這也給網(wǎng)絡(luò)的管理、維護(hù)帶來方便。知識(shí)點(diǎn)解析：暫無解析2、試比較單播、組播和廣播三種傳輸方式的區(qū)別。標(biāo)準(zhǔn)答案：(1)單播傳輸：在發(fā)送者和每一接收者之間實(shí)現(xiàn)點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)連接。如果一個(gè)發(fā)送者同時(shí)給多個(gè)接收者傳輸相同的數(shù)據(jù)，也必須相應(yīng)地復(fù)制多份相同的數(shù)據(jù)包。如果有大量主機(jī)希望獲得數(shù)據(jù)包的同一副本時(shí)，將導(dǎo)致發(fā)送者負(fù)擔(dān)沉重、延遲長(zhǎng)、網(wǎng)絡(luò)擁塞，為保證一定的服務(wù)質(zhì)量需增加硬件和帶寬。(2)組播傳輸：在發(fā)送者和每一接收者之間實(shí)現(xiàn)點(diǎn)對(duì)多點(diǎn)網(wǎng)絡(luò)連接。如果一個(gè)發(fā)送者同時(shí)給多個(gè)接收者傳輸相同的數(shù)據(jù)，只需復(fù)制一份相同的數(shù)據(jù)包。它提高了數(shù)據(jù)傳送效率，減少了骨干網(wǎng)絡(luò)出現(xiàn)擁塞的可能性。(3)廣播傳輸：是指在IP子網(wǎng)內(nèi)廣播數(shù)據(jù)包，所有在子網(wǎng)內(nèi)部的主機(jī)都將收到這些數(shù)據(jù)包。廣播意味著網(wǎng)絡(luò)向子網(wǎng)每一個(gè)主機(jī)都投遞一份數(shù)據(jù)包，不論這些主機(jī)是否樂于接收該數(shù)據(jù)包。所以廣播的使用范圍非常小，只在本地子網(wǎng)內(nèi)有效，通過路由器和交換機(jī)網(wǎng)絡(luò)設(shè)備控制廣播傳輸。知識(shí)點(diǎn)解析：暫無解析3、設(shè)某計(jì)算機(jī)有變址尋址、間接尋址和相對(duì)尋址等尋址方式。設(shè)當(dāng)前指令的地址碼部分為00lAH，正在執(zhí)行的指令所在地址為1F05H，變址寄存器中的內(nèi)容為23A0H。(1)當(dāng)執(zhí)行取數(shù)指令時(shí)，如為變址尋址方式，取出的數(shù)為多少?(2)如為間接尋址，取出的數(shù)為多少?(3)當(dāng)執(zhí)行轉(zhuǎn)移指令時(shí)，轉(zhuǎn)移地址為多少?標(biāo)準(zhǔn)答案：(1)變址尋址的尋址過程如下：變址尋址工作原理：指令地址碼部分給出的地址A和指定的變址寄存器x的內(nèi)容通過加法器相加，所得的和作為地址從存儲(chǔ)器中讀出所需的操作數(shù)。因此，操作數(shù)S：((Rx)+A)=(23AOH+001AH)=(23BAH)=1748H。(2)間接尋址的尋址過程如下：變址尋址工作原理：對(duì)于存儲(chǔ)器一次問址的情況，需訪問兩次存儲(chǔ)器才能取得數(shù)據(jù)第一次從存儲(chǔ)器讀出操作數(shù)地址：第二次從該地址中讀取操作數(shù)。因此，操作數(shù)S=((A))=((001AH))=(23AOH)=2600H。(3)轉(zhuǎn)移指令使用相對(duì)尋址，其過程如下：轉(zhuǎn)移地址=(PC)+A=1F06H+1H+001AH=1F21H。知識(shí)點(diǎn)解析：暫無解析4、從鍵盤上輸入一個(gè)逆波蘭表達(dá)式，用偽碼寫出其求值程序。規(guī)定：逆波蘭表達(dá)式的長(zhǎng)度不超過一行，以$符作為輸入結(jié)束，操作數(shù)之間用空格分隔，操作符只可能有+、一、*、／四種運(yùn)算，例如：234—34+2*$。標(biāo)準(zhǔn)答案：逆波蘭表達(dá)式(即后綴表達(dá)式)求值規(guī)則如下：設(shè)立運(yùn)算數(shù)棧OPND，對(duì)表達(dá)式從