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

考研計(jì)算機(jī)專業(yè)基礎(chǔ)綜合（綜合應(yīng)用題）模擬試卷2（共9套）（共180題）考研計(jì)算機(jī)專業(yè)基礎(chǔ)綜合（綜合應(yīng)用題）模擬試卷第1套一、綜合應(yīng)用題(本題共20題，每題1.0分，共20分。)1、為什么說(shuō)操作系統(tǒng)是由中斷驅(qū)動(dòng)的?標(biāo)準(zhǔn)答案：(1)所有并發(fā)程序都是由中斷(特別是時(shí)鐘中斷)驅(qū)動(dòng)的，故操作系統(tǒng)中屬于這一類的程序也是由中斷驅(qū)動(dòng)的。(2)第二類是直接面對(duì)用戶態(tài)“被動(dòng)”地為用戶服務(wù)的程序。系統(tǒng)初啟后，這類程序一般是不運(yùn)行的，僅當(dāng)用戶態(tài)程序執(zhí)行了相應(yīng)的系統(tǒng)調(diào)用時(shí)它才被調(diào)用、執(zhí)行。而正如上面所說(shuō)，系統(tǒng)調(diào)用指令的執(zhí)行是經(jīng)中斷(自陷)機(jī)構(gòu)處理的。因此，在這種意義上，操作系統(tǒng)中的這一類程序也是由中斷驅(qū)動(dòng)的。(3)第三類是那些既不主動(dòng)運(yùn)行，也不直接面對(duì)用戶態(tài)的程序。它們是隱藏在操作系統(tǒng)內(nèi)部，由前兩類程序所調(diào)用的程序。既然前兩類程序都是由中斷驅(qū)動(dòng)的，則此類程序當(dāng)然也應(yīng)該是由中斷驅(qū)動(dòng)的。知識(shí)點(diǎn)解析：暫無(wú)解析2、已知單鏈表L是一個(gè)遞增有序表，試寫一高效算法，刪除表中值大于min且小于max的結(jié)點(diǎn)(若表中有這樣的結(jié)點(diǎn))，同時(shí)釋放被刪結(jié)點(diǎn)的空間，這里min和max是兩個(gè)給定的參數(shù)。標(biāo)準(zhǔn)答案：struetnode{Datatypedata；structnode*next；}ListNode；typedefListNode*LinkList；voidDeleteList(LinkListL，DataTypemin，DataTypemax){ListNode*P，*q，*h;P=L一＞next；／／采用代表頭結(jié)點(diǎn)的單鏈表while(P&＆p一＞data＜=min){／／找比min大的前一個(gè)元素位置q=p；p=p一>next;}p=q;／／保存這個(gè)元素位置while(q＆＆q一＞data＜max)q=q一＞next；／／找比max小的最后一個(gè)元素位置while(p一＞next!=q){h=p一＞next；p=p一＞next；free(h)；／／釋放空間}p一＞next=q；／／把斷點(diǎn)鏈上}提示：首先想到的是拿鏈表中的元素一個(gè)個(gè)地與max和min比較，然后刪除這個(gè)結(jié)點(diǎn)。其實(shí)因?yàn)橐阎涫怯行蜴湵恚灾灰业酱笥趍in的結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)，再找到小于max的結(jié)點(diǎn)，然后一并把中間的全部摘掉就可以了。知識(shí)點(diǎn)解析：暫無(wú)解析3、假設(shè)K1,…，Kn是n個(gè)關(guān)鍵詞，試解答：(1)試用二叉查找樹的插入算法建立一棵二叉查找樹，即當(dāng)關(guān)鍵詞的插入次序?yàn)镵1，K2，…，Kn時(shí)，用算法建立一棵以LLINK—RIJNK鏈接表示的二叉查找樹。(2)設(shè)計(jì)一個(gè)算法，打印出該二叉查找樹的嵌套括號(hào)表示結(jié)構(gòu)。假定該二叉查找樹的嵌套括號(hào)表示結(jié)構(gòu)為B(A，D(C，E))。標(biāo)準(zhǔn)答案：(1)非遞歸建立二叉排序樹，在二叉排序樹上插入的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)。typedefstruetnode{Elemtypedata；struetnode*LLINK，*RLINK：}node*BiTree；voidCreate_BST(B／Treebst，datatypeK[]，intn){／／以存儲(chǔ)在數(shù)組K中的n個(gè)關(guān)鍵字，建立一棵初始為空的二叉排序樹inti；BiTreeP，f；for(i=1；i＜=n；i++){P=bst：f=null；／／在調(diào)用Create_BST時(shí)，bst=nullwhile(P!=null)if(P-＞data＜K[i]){f=P；P=p一＞RLINK；}I／f是P的雙親elseif(p-＞data＞K[i]){f=p：P=p一＞LLINK；}S=(BiTree)malloc(sizeof(B／Node))；／／申請(qǐng)結(jié)點(diǎn)空間s-＞data=K[i]；s-＞LLINK=null；s一＞RLINK=null；if(f==null)bst=S：／／根結(jié)點(diǎn)elseif(s一＞data＜f一＞data)f-＞LLINK=s；／／左子女elsef一＞RLINK=s：／／右子樹根結(jié)點(diǎn)的值大于等于根結(jié)點(diǎn)的值}}(2)本題要求輸出遍歷二又排序樹的嵌套括號(hào)表示。其算法思想是，若二叉排序樹非空，則輸出根結(jié)點(diǎn)，再輸出其左右子樹。在輸出其左右子樹前，要輸出左括號(hào)，在輸出其右子樹前要輸出逗號(hào)，在輸出其右子樹后要輸出右括號(hào)，在左右子樹均空情況下，則不輸出括號(hào)。voidPrint(BiTreet){／／以嵌套括號(hào)表示結(jié)構(gòu)打印二叉排序樹if(t!=null){printf(t-＞data)：／／打印根結(jié)點(diǎn)值if(t一＞LLINK||t-＞LLINK)；／／左子女和右子女中至少有一個(gè)不空printf(”(”)；／／輸出左括號(hào)Print(t-＞LLINK)；／／輸出左子樹的嵌套括號(hào)表示if(t-＞RLINK)printf(”，”)；／／若右子樹不空，輸出逗號(hào)Print(t一＞RLINK)：／／輸出右子樹的嵌套括號(hào)表示printf(”)”)；／／輸出右括號(hào)}}知識(shí)點(diǎn)解析：暫無(wú)解析4、寫出從哈希表中刪除關(guān)鍵字為K的一個(gè)記錄的算法。設(shè)哈希函數(shù)為H，解決沖突的方法為鏈地址法。標(biāo)準(zhǔn)答案：用鏈地址法解決沖突的哈希表是一個(gè)指針數(shù)組，數(shù)組分量均是指向單鏈表的指針，(第i個(gè))單鏈表結(jié)點(diǎn)有兩個(gè)域，一個(gè)是哈希地址為i的關(guān)鍵字，另一個(gè)是指向同義詞結(jié)點(diǎn)的指針。刪除算法與單鏈表上刪除算法類似。typedefstructnode{keytypekey；structnode*next：}HSNode*HSList；typedefstructnode*HLK；voidDelete(HLKHT[]，keytypeK){／／用鏈地址法解決沖突，從哈希表中刪去關(guān)鍵字為K的記錄inti=H(K)；／／用哈希函數(shù)確定關(guān)鍵字K的哈希地址if(HT[i]==null){printf(”無(wú)被刪除記錄＼n”)；exit(0)；}HLKP，q；p=H[i]：q=p；／／p指向當(dāng)前記錄(關(guān)鍵字)，q是P的前驅(qū)while(P&&p一＞key!=k){q=P；P=P一＞next；}if(P==null){printf(”無(wú)被刪除記錄”)；exit(0)；}if(q==H[i]){HT[i]=HT[i]．next；free(P)；}／／被刪除關(guān)鍵字是鏈表中第一個(gè)結(jié)點(diǎn)else{q一＞next=p一＞next；free(P)；}}知識(shí)點(diǎn)解析：暫無(wú)解析5、寫出快速排序的非遞歸算法。標(biāo)準(zhǔn)答案：設(shè)對(duì)記錄R[1．．n]進(jìn)行快速排序，要求用非遞歸算法。利用一個(gè)包含有l(wèi)ow和high兩個(gè)整數(shù)成員的記錄數(shù)組stack[]作為棧，low和high成員分別指示某個(gè)子文件的首、尾記錄的下標(biāo)號(hào)。算法如下：voidquicksort(SeqListR，intn){／／設(shè)待排序記錄放在R[1．．n]中，下標(biāo)從1開始inti，j，low，high，top=0；struct{intlow，high；}stack[Max]；／／Max為一個(gè)大于n的常量RecTypetemp；top=1；stack[top]．low=1；stack[top]．high=n；／／入棧while(top＞0){／／棧非空，則取出一個(gè)子文件進(jìn)行劃分low=stack[top]．low；high=stack[top]．high；top一一；／／出棧i=low；j=high；temp=R[i]；do{while(i＜j&&R[i]．key＞temp．key)j--；if(i＜j){R[i]=R[j]；i++；while(i＜j&&R[i]．key＜temp．key)i++；if(i＜j){R[j]=R[i]；j一一；}}}while(i==j)；／／劃分結(jié)束R[i]=temp；／／基元元素插入if(i+1＜high){／／右子文件有兩個(gè)以上記錄，則首、尾位置入棧top++：stack[top]．low=i+1；stack[top]．high=high；}if(low＜i一1){／／左子文件有兩個(gè)以上記錄，則首、尾位置入棧top++；stack[top]．low=low；stack[top]．high=i一1；}}}知識(shí)點(diǎn)解析：暫無(wú)解析6、物理層要解決什么問題?物理層的主要特點(diǎn)是什么?試給出數(shù)據(jù)通信系統(tǒng)的模型并說(shuō)明其主要組成構(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)傳送過來(lái)的信號(hào)，并將其轉(zhuǎn)換為能夠被目的設(shè)備處理的信息。例如，調(diào)制解調(diào)器接收來(lái)自傳輸線路上的模擬信號(hào)，并將其轉(zhuǎn)換成數(shù)字比特流。②終點(diǎn)：終點(diǎn)設(shè)備從接收器獲取傳送過來(lái)的信息。知識(shí)點(diǎn)解析：暫無(wú)解析7、以孩子一兄弟表示法存儲(chǔ)的森林的葉子結(jié)點(diǎn)數(shù)(要求描述結(jié)構(gòu))。標(biāo)準(zhǔn)答案：當(dāng)森林(樹)以孩子兄弟表示法存儲(chǔ)時(shí)，若結(jié)點(diǎn)沒有孩子(fch=null)，則它必是葉子，總的葉子結(jié)點(diǎn)個(gè)數(shù)是孩子子樹(fch)上的葉子數(shù)和兄弟(nsib)子樹上葉結(jié)點(diǎn)個(gè)數(shù)之和。typedefstructnode{elemTypedata；／／數(shù)據(jù)域structnode*fch，*nsib；／／孩子與兄弟域}*Tree；intLeaves(Treet){／／計(jì)算以孩子一兄弟表示法存儲(chǔ)的森林的葉子數(shù)if(t)if(t一>fch=：null)／／若結(jié)點(diǎn)無(wú)孩子，則該結(jié)點(diǎn)必是葉子return(1+Leaves(t->nsib))；／／返回葉子結(jié)點(diǎn)和其兄弟子樹中的葉子結(jié)點(diǎn)數(shù)elsereturn(Leaves(t->fch)+Leaves(t->nsib))；／／孩子子樹和兄弟子樹中葉子數(shù)之和}知識(shí)點(diǎn)解析：暫無(wú)解析8、已知深度為h的二叉樹采用順序存儲(chǔ)結(jié)構(gòu)已存放于數(shù)組BT[1．2h一1]中，請(qǐng)寫一非遞歸算法，產(chǎn)生該二叉樹的二叉鏈表結(jié)構(gòu)。設(shè)二叉鏈表中鏈結(jié)點(diǎn)的構(gòu)造為(lchild，data，rchild)，根結(jié)點(diǎn)所在鏈結(jié)點(diǎn)的指針由T給出。標(biāo)準(zhǔn)答案：二叉樹采用順序存儲(chǔ)結(jié)構(gòu)(一維數(shù)組)是按完全二叉樹的形狀存儲(chǔ)的，不是完全二叉樹的二叉樹順序存儲(chǔ)時(shí)，要加“虛結(jié)點(diǎn)”。數(shù)組中的第一個(gè)元素是根結(jié)點(diǎn)。本題中采用隊(duì)列結(jié)構(gòu)。typedefstruct{BiTreebt：／／二叉樹結(jié)點(diǎn)指針intBum；}tnode：／／Bum是結(jié)點(diǎn)在一維數(shù)組中的編號(hào)tnodeQ[maxsize]；／／循環(huán)隊(duì)列，容量足夠大voidcreat(BiTreeT，ElemTypeBT[]){／／深度h的二叉樹存于一維數(shù)組BT[1．2h一1]中／／本算法生成該二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)tnodetq：／／tq是隊(duì)列元素intlen，i：／／數(shù)組長(zhǎng)度len=strlen(BT)；T=(BiTree)malloc(sizeof(BiNode))；／／申請(qǐng)結(jié)點(diǎn)T一>data=BT[1]；／／根結(jié)點(diǎn)數(shù)據(jù)tq．bt=T；tq．num=1；Q[1]：tq；／／根入隊(duì)列front=0；rear=1；／／循環(huán)隊(duì)列頭、尾指針while(front!=rear){／／當(dāng)隊(duì)列不空時(shí)循環(huán)front=(front+1)％maxsize；tq=Q[front]；p=tq．bt；i=tq．num；／／出隊(duì)，取出結(jié)點(diǎn)及編號(hào)if(BT[2*i]==‘#’||2*i>len)p->lchild=null；／／左子樹為空，‘#’表示虛結(jié)點(diǎn)else{／／建立左子女結(jié)點(diǎn)并入隊(duì)列p一>lchild=(BiTree)malloc(sizeof(BiNode))；／／申請(qǐng)結(jié)點(diǎn)空間p一>lchild一>data=BT[2*i]：／／左子女?dāng)?shù)據(jù)tq．bt=p一>lchild；tq．Bum=2*i；rear=(rear+1)％maxsize；／／計(jì)算隊(duì)尾位置Q[rear]=tq；／／左子女結(jié)點(diǎn)及其編號(hào)入隊(duì)}if(BT[2*i+1]==‘#’||2*i+l>len)p一>rchild=null；／／右子樹為空else{／／建立右子女結(jié)點(diǎn)并入隊(duì)列p一>rchild=(BiTree)malloc(sizeof(BiNode)；／／申請(qǐng)結(jié)點(diǎn)空間p一>rchild一>data=BT[2*i+1]；tq．bt=p一>rchild；tq．Bum=2*i+1；rear=(Fear+1)％maxsize；Q[rear]=tq：／／計(jì)算隊(duì)尾位置，右子女及其編號(hào)入隊(duì)}}／／while}提示：本題中的虛結(jié)點(diǎn)用‘#’表示，應(yīng)根據(jù)二叉樹的結(jié)點(diǎn)數(shù)據(jù)的類型而定。知識(shí)點(diǎn)解析：暫無(wú)解析9、已有鄰接表表示的有向圖，請(qǐng)編程判斷從第u頂點(diǎn)至第v頂點(diǎn)是否有簡(jiǎn)單路徑，若有則打印出該路徑上的頂點(diǎn)。標(biāo)準(zhǔn)答案：voidAllpath(AdjListg，vertypeU，vertypev){／／求有向圖g中頂點(diǎn)u到頂點(diǎn)v的所有簡(jiǎn)單路徑，初始調(diào)用形式inttop=0，S[]：S[++top]=u；visited[U]=1；while(top>0||P){P=g[S[top]]．firstarc；／／第一個(gè)鄰接點(diǎn)while(Pf=null&&visited[p一>adjvex]==1)P=p->next；／／下一個(gè)訪問鄰接點(diǎn)表if(P==null)top--：／／退棧else{i=p一>adjvex;／／取鄰接點(diǎn)(編號(hào))if(i==V){／／找到從u到v的一條簡(jiǎn)單路徑，輸出for(k=1；k<=top；k++)printf(”％3d”，s[k])：printf(tt％3d＼n”，v)：}／／ifelse{visited[i]=1；s[++top]=i；}／／else深度優(yōu)先遍歷}／／else}／／while}知識(shí)點(diǎn)解析：暫無(wú)解析10、假設(shè)CPU執(zhí)行某段程序時(shí)，950次從Cache得到數(shù)據(jù)，50次從主存得到數(shù)據(jù)，已知Cache存取周期為50ns，主存存取周期為200ns(設(shè)每次訪問時(shí)，Cache訪問與主存訪問并發(fā)進(jìn)行，如Cache命中則中斷主存的訪問)。求：(1)Cache的命中率。(2)平均訪問時(shí)間。(3)Cache一主存系統(tǒng)的效率。標(biāo)準(zhǔn)答案：(1)Cache未命中情況下才需要從主存取數(shù)據(jù)，故Cache的命中率=Cache命中次數(shù)÷(Cache命中次數(shù)+Cache未命中次數(shù))=950÷(950+50)=0．95(2)平均訪問時(shí)間=(9．50×50ns+50×200ns)÷1000=57．5ns(3)Cache-主存系統(tǒng)的效率=Cache存取周期／平均訪問時(shí)間=50÷57．5×100％=87．0％知識(shí)點(diǎn)解析：暫無(wú)解析11、某計(jì)算機(jī)字長(zhǎng)為16位，存儲(chǔ)器直接尋址空間為128字，變址時(shí)的位移量為一64～+63，16個(gè)通用寄存器均可作為變址寄存器。采用擴(kuò)展操作碼技術(shù)，設(shè)計(jì)一套指令系統(tǒng)格式，滿足下列尋址類型的要求：(1)直接尋址的二地址指令3條。(2)變址尋址的一地址指令6條。(3)寄存器尋址二地址指令8條。(4)直接尋址的一地址指令12條。(5)零地址指令32條。標(biāo)準(zhǔn)答案：由題意知道是多種尋址方式，為簡(jiǎn)化指令設(shè)計(jì)，選用擴(kuò)展操作碼方式，所以要求的指令數(shù)從(1)到(5)遞增順序設(shè)計(jì)。(1)二地址直接尋址指令的操作碼部分應(yīng)為2位，故操作碼可定義成00、01、10，總的指令長(zhǎng)度可以是操作碼2位，地址碼為7位×2字段共14位。(2)一地址變址尋址指令的操作碼可從11000開始，順序遞增到11101為止，總的指令長(zhǎng)度可以是5位操作碼，4位寄存器編碼，7位地址碼，共16位。(3)二地址寄存器尋址指令的操作碼可以從11110000開始，順序遞增到11110111為止，總的指令長(zhǎng)度可以是8位操作碼，寄存器共24個(gè)，地址碼為4位×2字段=8位。(4)一地址直接尋址指令的操作碼部分可以從111110000開始，順序遞增到111111011為止，總的指令長(zhǎng)度是9位操作碼，7位地址碼，共16位。(5)零地址指令的操作碼雖可從111111100000開始，順序遞增到111111110000，但指令總長(zhǎng)是12位，而上述其他指令的長(zhǎng)度都可為16位，所以這里將表示32種不同零地址指令的5位移動(dòng)到16位指令的最后5位，因而從1111111000000000～111111100001111。知識(shí)點(diǎn)解析：暫無(wú)解析12、為什么說(shuō)操作系統(tǒng)是由中斷驅(qū)動(dòng)的?標(biāo)準(zhǔn)答案：(1)所有并發(fā)程序都是由中斷(特別是時(shí)鐘中斷)驅(qū)動(dòng)的，故操作系統(tǒng)中屬于這一類的程序也是由中斷驅(qū)動(dòng)的。(2)第二類是直接面對(duì)用戶態(tài)“被動(dòng)”地為用戶服務(wù)的程序。系統(tǒng)初啟后，這類程序一般是不運(yùn)行的，僅當(dāng)用戶態(tài)程序執(zhí)行了相應(yīng)的系統(tǒng)調(diào)用時(shí)它才被調(diào)用、執(zhí)行。而正如上面所說(shuō)，系統(tǒng)調(diào)用指令的執(zhí)行是經(jīng)中斷(自陷)機(jī)構(gòu)處理的。因此，在這種意義上，操作系統(tǒng)中的這一類程序也是由中斷驅(qū)動(dòng)的。(3)第三類是那些既不主動(dòng)運(yùn)行，也不直接面對(duì)用戶態(tài)的程序。它們是隱藏在操作系統(tǒng)內(nèi)部，由前兩類程序所調(diào)用的程序。既然前兩類程序都是由中斷驅(qū)動(dòng)的，則此類程序當(dāng)然也應(yīng)該是由中斷驅(qū)動(dòng)的。知識(shí)點(diǎn)解析：暫無(wú)解析13、并發(fā)使得處理機(jī)的利用率得到提高，其主要原因是處理機(jī)與I/O可以同時(shí)為多個(gè)進(jìn)程服務(wù)，也即處理機(jī)與I／O設(shè)備真正地并行。但是處理機(jī)的利用率提高并不是簡(jiǎn)單地將兩個(gè)進(jìn)程的處理機(jī)利用率相加，而是遵循～定的規(guī)律?，F(xiàn)在有一個(gè)計(jì)算機(jī)系統(tǒng)采用多道程序技術(shù)實(shí)現(xiàn)了并發(fā)，調(diào)度算法采用時(shí)間片輪轉(zhuǎn)，時(shí)間片很小可以不計(jì)進(jìn)程并發(fā)時(shí)的次序。忽略計(jì)算機(jī)系統(tǒng)的開銷。假設(shè)進(jìn)程創(chuàng)建時(shí)間和完全占有CPU運(yùn)行的確切時(shí)間如下表所示。已知其I／O繁忙率為80％，處理機(jī)的利用率為20％。請(qǐng)計(jì)算并填寫下列空格和圖表空格處。標(biāo)準(zhǔn)答案：本題考查的是并發(fā)進(jìn)程之間的計(jì)算。計(jì)算機(jī)引入多道程序設(shè)計(jì)技術(shù)主要是為提高處理機(jī)的利用率。在多道程序并發(fā)的情況下，處理機(jī)的利用率呈現(xiàn)出如下的規(guī)律：U=1—pn其中，U為處理機(jī)利用率，P為I／O繁忙率，n為并發(fā)進(jìn)程數(shù)。據(jù)此，對(duì)題目給定的數(shù)據(jù)進(jìn)行計(jì)算，并將結(jié)果填入表格中。當(dāng)1個(gè)進(jìn)程運(yùn)行時(shí)，處理機(jī)利用率為20％，這個(gè)進(jìn)程獨(dú)享該處理機(jī)，所以20％的利用率均被使用。在時(shí)刻10：00到10：10期間，進(jìn)程0獨(dú)享處理機(jī)。這期間，進(jìn)程0實(shí)際的處理機(jī)時(shí)間為10分鐘×20％=2分鐘。當(dāng)2個(gè)進(jìn)程運(yùn)行時(shí)，根據(jù)公式計(jì)算得到處理機(jī)利用率為36％，2個(gè)進(jìn)程共享處理機(jī)，所以每個(gè)進(jìn)程的處理機(jī)的利用率為18％。在時(shí)刻10：10到10：15期間，進(jìn)程0和1共享處理機(jī)。這期間，進(jìn)程0和1各自實(shí)際的處理機(jī)時(shí)間為5×36％÷2=0．9分鐘。當(dāng)3個(gè)進(jìn)程運(yùn)行時(shí)，根據(jù)公式計(jì)算得到處理機(jī)利用率為49％，3個(gè)進(jìn)程共享處理機(jī)，所以每個(gè)進(jìn)程的處理機(jī)的利用率為16％。在時(shí)刻10：15到10：20期間，進(jìn)程0、1和2共享處理機(jī)。這期間，進(jìn)程0、1和2各自實(shí)際的處理機(jī)時(shí)間為5×49％÷3=0．8分鐘。當(dāng)4個(gè)進(jìn)程運(yùn)行時(shí)，根據(jù)公式計(jì)算得到處理機(jī)利用率為59％，4個(gè)進(jìn)程共享處理機(jī)，所以每個(gè)進(jìn)程的處理機(jī)的利用率為15％。從時(shí)刻10：20開始，4個(gè)進(jìn)程并發(fā)。那么，從圖中可以看到，進(jìn)程0已經(jīng)運(yùn)行了3．7分鐘，進(jìn)程1運(yùn)行了1．7分鐘，進(jìn)程2運(yùn)行了0．8分鐘，進(jìn)程3剛運(yùn)行。根據(jù)題目給出的每個(gè)進(jìn)程實(shí)際占有處理機(jī)的時(shí)間，可以看出，進(jìn)程0還剩余時(shí)間0．3分鐘，進(jìn)程1還剩余1．3分鐘，進(jìn)程2還剩余1．2分鐘，進(jìn)程3還剩余2分鐘，顯然，在并發(fā)并且平均使用處理機(jī)的情況下，進(jìn)程結(jié)束的次序應(yīng)該為0、2、1、3。首先我們計(jì)算進(jìn)程0還需要運(yùn)行多長(zhǎng)時(shí)間結(jié)束。經(jīng)過剛才計(jì)算得知，進(jìn)程0還剩余0．3分鐘，那么，在進(jìn)程4并發(fā)，處理機(jī)利用率為每進(jìn)程15％的情況下，尚需要時(shí)間為0．3÷15％=2分鐘，由此得知，到10：22時(shí)，進(jìn)程0結(jié)束。進(jìn)程0退出后再計(jì)算剩余進(jìn)程的剩余時(shí)間，進(jìn)程1，2，3分別為1．0、0．9、1．7分鐘，上面已經(jīng)分析，下一個(gè)結(jié)束的進(jìn)程是進(jìn)程2，所以，我們計(jì)算0．9÷16％=5．6分鐘。注意，此時(shí)是3個(gè)進(jìn)程并發(fā)了，處理機(jī)的利用率為每進(jìn)程16％，此處切記不可疏忽。到10：27．6，進(jìn)程2結(jié)束。同理，進(jìn)程2退出以后再計(jì)算剩余進(jìn)程的剩余時(shí)間，進(jìn)程1、3分別為0．1、0．8分鐘，上面已經(jīng)分析，下一個(gè)結(jié)束的進(jìn)程是進(jìn)程1，所以，0．1÷18％=0．6分鐘。注意，此時(shí)是2個(gè)進(jìn)程并發(fā)了，處理機(jī)的利用率為每進(jìn)程18％。到10：28．2，進(jìn)程1結(jié)束。同樣計(jì)算，進(jìn)程1退出以后，進(jìn)程3的剩余時(shí)間為0．7分鐘，計(jì)算得出0．7÷20％=3．5分鐘，而此時(shí)處理機(jī)的利用率為每進(jìn)程20％。到10：31．7，進(jìn)程3結(jié)束。據(jù)此，填寫下列各個(gè)表格和空格。根據(jù)題意計(jì)算得到U1=1—0．8=0．2=20％U2=1-0．82=0．36=36％U3=1—0．83=0．49=49％U4=1一0．84=0．59=59％因此，表格填寫如下：甘特圖中空白括號(hào)填寫如下圖所示：知識(shí)點(diǎn)解析：暫無(wú)解析14、引入動(dòng)態(tài)重定位的目的是什么?標(biāo)準(zhǔn)答案：(1)為了在程序執(zhí)行過程中，每當(dāng)訪問指令或數(shù)據(jù)時(shí)，將要訪問的程序或數(shù)據(jù)的邏輯地址轉(zhuǎn)換成物理地址，引入了動(dòng)態(tài)重定位。(2)可在系統(tǒng)中增加一個(gè)重定位寄存器，用它來(lái)裝入(存放)程序在內(nèi)存中的起始地址，程序在執(zhí)行時(shí)真正訪問的內(nèi)存地址是相對(duì)地址與重定位寄存器中的地址相加而形成的，從而實(shí)現(xiàn)動(dòng)態(tài)重定位。知識(shí)點(diǎn)解析：暫無(wú)解析15、為什么要引入動(dòng)態(tài)分段存儲(chǔ)管理?它與請(qǐng)求頁(yè)式存儲(chǔ)管理有什么區(qū)別?標(biāo)準(zhǔn)答案：(1)一個(gè)大的進(jìn)程可能包含很多個(gè)程序模塊。對(duì)它們進(jìn)行鏈接要花費(fèi)大量的CPu時(shí)間，而實(shí)際執(zhí)行時(shí)則可能只用到其中的一小部分模塊。因此，從減少CPU開銷和減少存儲(chǔ)空間浪費(fèi)的角度來(lái)看，靜態(tài)鏈接是不合適的，因此引入動(dòng)態(tài)分段存儲(chǔ)管理。(2)它與請(qǐng)求頁(yè)式存儲(chǔ)管理的區(qū)別：第一，分頁(yè)的作業(yè)地址空間是單一的線性地址空間，而分段作業(yè)的地址空間是二維的。第二，頁(yè)是信息的物理單位，大小固定；段是信息的邏輯單位，其長(zhǎng)度不定。第三，分頁(yè)管理實(shí)現(xiàn)的是單段式虛擬存儲(chǔ)系統(tǒng)，而分段存儲(chǔ)管理實(shí)現(xiàn)的是多段式虛擬存儲(chǔ)系統(tǒng)。知識(shí)點(diǎn)解析：暫無(wú)解析16、數(shù)據(jù)鏈路層中的鏈路控制包括哪些功能?標(biāo)準(zhǔn)答案：數(shù)據(jù)鏈路層中的鏈路控制功能有：①鏈路管理。②幀定界。③流量控制。③差錯(cuò)控制。⑤將數(shù)據(jù)和控制信息區(qū)分開。⑥透明傳輸。⑦尋址。知識(shí)點(diǎn)解析：暫無(wú)解析17、什么是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)為解決并行所帶來(lái)的死鎖問題，在wait操作中引入AND條件，其基本思想是將進(jìn)程在整個(gè)運(yùn)行過程中所需要的所有臨界資源一次性地全部分配給進(jìn)程，用完后一次性釋放。(2)解決生產(chǎn)者一消費(fèi)者問題可描述如下：varmutex，empty，full：semaphore：=1，n，0；buffer：array[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)解析：暫無(wú)解析在一個(gè)采用分頁(yè)式虛擬存儲(chǔ)管理的系統(tǒng)中，有一用戶作業(yè)，它依次要訪問的字地址序列是115，228，120，88，446，102，321，432，260，167。若分配給作業(yè)可使用的主存空間共300個(gè)字，作業(yè)的頁(yè)面大小為100個(gè)字，且第0頁(yè)已經(jīng)裝入主存，請(qǐng)回答下列問題：18、按FIFO頁(yè)面調(diào)度算法將產(chǎn)生多少次缺頁(yè)中斷?寫出依次淘汰的頁(yè)號(hào)。標(biāo)準(zhǔn)答案：由于作業(yè)的頁(yè)面大小為100個(gè)字，因而主存塊的大小也為100個(gè)字?，F(xiàn)該作業(yè)可使用的主存空間共300個(gè)字，即共可使用三個(gè)主存塊。根據(jù)作業(yè)依次要訪問的字地址，可以得到作業(yè)將依次訪問的頁(yè)如下：現(xiàn)只有第0頁(yè)已經(jīng)在主存但尚有兩塊主存空間可供使用，所以作業(yè)執(zhí)行時(shí)依次訪問第1頁(yè)和第2頁(yè)時(shí)均要產(chǎn)生缺頁(yè)中斷，但不必淘汰已在主存中的頁(yè)面，可把第1頁(yè)和第2頁(yè)裝入到可使用的主存塊中，現(xiàn)在主存中已有0、1、2三個(gè)頁(yè)面的信息。在進(jìn)行第三、第四次訪問時(shí)不會(huì)產(chǎn)生缺頁(yè)中斷，而在第五次訪問第4頁(yè)時(shí)將產(chǎn)生一次缺頁(yè)中斷。此時(shí)，若采用FIFO算法應(yīng)淘汰最先裝入主存的第0頁(yè)，而采用LRU算法則應(yīng)淘汰最近最久沒有使用的第2頁(yè)。顯然，進(jìn)行第六次訪問不會(huì)產(chǎn)生缺頁(yè)中斷，而在第七次訪問時(shí)必須經(jīng)缺頁(yè)中斷處理來(lái)裝入第3頁(yè)。為此，F(xiàn)IFO算法會(huì)淘汰第1頁(yè)，LRU算法會(huì)淘汰第0頁(yè)。于是，作業(yè)繼續(xù)執(zhí)行時(shí)，對(duì)FIFO算法來(lái)說(shuō)，將在第十次訪問時(shí)再產(chǎn)生一次缺頁(yè)中斷，為了裝入當(dāng)前需用的第1頁(yè)而應(yīng)淘汰第2頁(yè)：對(duì)LRU算法來(lái)說(shuō)，將在第九次訪問時(shí)產(chǎn)生缺頁(yè)中斷，為了裝入當(dāng)前需用的第2頁(yè)而應(yīng)淘汰第1頁(yè)，在隨后的第十次訪問時(shí)仍將產(chǎn)生缺頁(yè)中斷，為了把第1頁(yè)重新裝入而應(yīng)淘汰第3頁(yè)?？梢姡碏lFO頁(yè)面調(diào)度算法將產(chǎn)生五次缺頁(yè)中斷，依次淘汰的頁(yè)面為0、1、2。按LRU頁(yè)面調(diào)度算法將產(chǎn)生六次缺頁(yè)中斷，依次淘汰的頁(yè)面為2、0、1、3。按FIFO頁(yè)面調(diào)度算法將在后繼的第五、七、十次訪問時(shí)再產(chǎn)生三次缺頁(yè)中斷。因而共產(chǎn)生五次缺頁(yè)中斷，依次淘汰的頁(yè)號(hào)為0、1、2。知識(shí)點(diǎn)解析：暫無(wú)解析19、按LRU頁(yè)面調(diào)度算法將產(chǎn)生多少次缺頁(yè)中斷?寫出依次淘汰的頁(yè)號(hào)。標(biāo)準(zhǔn)答案：按LRU頁(yè)面調(diào)度算法將在后繼的第五、七、九、十次訪問時(shí)再產(chǎn)生四次缺頁(yè)中斷。因而共產(chǎn)生六次缺頁(yè)中斷，依次淘汰的頁(yè)號(hào)為2、0、1、3。知識(shí)點(diǎn)解析：暫無(wú)解析20、簡(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ā)來(lái)的任何數(shù)據(jù)分組，只等待連接確認(rèn)應(yīng)答分組。而A在發(fā)出的分組超時(shí)后，重復(fù)發(fā)送同樣的分組，這樣就形成了死鎖。知識(shí)點(diǎn)解析：暫無(wú)解析考研計(jì)算機(jī)專業(yè)基礎(chǔ)綜合（綜合應(yīng)用題）模擬試卷第2套一、綜合應(yīng)用題(本題共20題，每題1.0分，共20分。)1、有三個(gè)進(jìn)程PA、PB和PC合作解決文件打印問題：PA將文件記錄從磁盤讀入主存的緩沖區(qū)1，每執(zhí)行一次讀一個(gè)記錄；PB將緩沖區(qū)1的內(nèi)容復(fù)制到緩沖區(qū)2，每執(zhí)行一次復(fù)制一個(gè)記錄；PC將緩沖區(qū)2的內(nèi)容打印出來(lái)，每執(zhí)行一次打印一個(gè)記錄。緩沖區(qū)的大小等于一個(gè)記錄的大小。請(qǐng)用P、V操作來(lái)保證文件的正確打印。標(biāo)準(zhǔn)答案：本題考查用P、V操作解決進(jìn)程的同步互斥問題。(1)進(jìn)程PA、PB、PC之間的關(guān)系為：PA與PB共用一個(gè)單緩沖區(qū)，PB又與PC共用一個(gè)單緩沖區(qū)，其合作方式如下圖所示。當(dāng)緩沖區(qū)1為空時(shí)，進(jìn)程PA可將一個(gè)記錄讀入其中；若緩沖區(qū)1中有數(shù)據(jù)且緩沖區(qū)2為空，則進(jìn)程PB可將記錄從緩沖區(qū)1復(fù)制到緩沖區(qū)2中；若緩沖區(qū)2中有數(shù)據(jù)，則進(jìn)程PC可以打印記錄。在其他條件下，相應(yīng)進(jìn)程必須等待。事實(shí)上，這是一個(gè)生產(chǎn)者一消費(fèi)者問題。為遵循這一同步規(guī)則。應(yīng)設(shè)置4個(gè)信號(hào)量empty1、empty2、fulll、full2，信號(hào)量emptyl和empty2分別表示緩沖區(qū)1緩沖區(qū)2是否為空，其初值為1；信號(hào)量fulll和full2分別表示緩區(qū)1及緩沖區(qū)2是否有記錄可供處理，其初值為0。(2)相應(yīng)的進(jìn)程描述如下：semaphoreemptyl=1：／／緩沖區(qū)1是否為空semaphorefulll=0：／／緩沖區(qū)1是否有記錄可供處理semaphoreempty2=1；／／緩沖區(qū)2是否為空semaphorefull2=0：／／緩沖區(qū)2是否有記錄可供處理cobegin{processPA(){while(TRuE){從磁盤讀入一條記錄：P(emptyl)；將記錄存入緩沖區(qū)1；V(fulll)；}}processPB(){while(TRuE){P(fulll)；從緩沖區(qū)1中取出一條記錄；V(empty1)：P(empty2)；將取出的記錄存入緩沖區(qū)2；V(full2)：}}processPC(){while(TRUE){P(full2)：從緩沖區(qū)2中取出一條記錄；V(empty2)；將取出的記錄打印出來(lái)：}}}coend知識(shí)點(diǎn)解析：暫無(wú)解析2、在采用首次適應(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)解析：暫無(wú)解析3、兩個(gè)整數(shù)序列A=a1，a2，a3，…，am和B=b1，b2，b3，…，bn已經(jīng)存入兩個(gè)單鏈表中，設(shè)計(jì)一個(gè)算法，判斷序列B是否是序列A的子序列。標(biāo)準(zhǔn)答案：typedefstructLNode{intdata；structLNode*next；}*Linkedlist；intPattern(LinkedListA，B){／／A和B分別是數(shù)據(jù)域?yàn)檎麛?shù)的單鏈表，本算法判斷鏈表B是否是／／鏈表A的子序列。如是，返回1；否則，返回0，表示失敗。Linkedlist*P，*pre，*q；p=A：／／p為鏈表A的工作指針，本題假定鏈表A和鏈表B均無(wú)頭結(jié)點(diǎn)pre=p：／／pre記住每趟比較中鏈表A的開始結(jié)點(diǎn)q=B：／／q是鏈表B的工作指針while(p&&q)if(p一>data==q一>data){P=p一>next；q=q一>next；}else{pre=pre->next；P=pre；／／鏈表A新的開始比較結(jié)點(diǎn)q=B：／／q從鏈表B第一結(jié)點(diǎn)開始if(q==null)return(1)；／／鏈表B是鏈表A的子序列elsereturn(0)；／／鏈表B不是鏈表A的子序列}}／／算法結(jié)束知識(shí)點(diǎn)解析：暫無(wú)解析4、已知一個(gè)帶有頭結(jié)點(diǎn)的單鏈表L，其結(jié)點(diǎn)結(jié)構(gòu)由兩部分組成：數(shù)據(jù)域data，指針域link。設(shè)計(jì)一個(gè)算法，以最高效的方法實(shí)現(xiàn)在單鏈表中刪除數(shù)據(jù)域最小值結(jié)點(diǎn)。要求：(1)給出算法的基本設(shè)計(jì)思想。(2)根據(jù)設(shè)計(jì)思想，采用C或C++或Java語(yǔ)言描述算法，關(guān)鍵之處給出注釋。標(biāo)準(zhǔn)答案：(1)算法的基本思想：?jiǎn)捂湵碇袆h除結(jié)點(diǎn)，為使結(jié)點(diǎn)刪除后不出現(xiàn)“斷鏈”，應(yīng)知道被刪結(jié)點(diǎn)的前驅(qū)。而“最小值結(jié)點(diǎn)”是在遍歷整個(gè)鏈表后才能知道。所以算法應(yīng)首先遍歷鏈表，求得最小值結(jié)點(diǎn)及其前驅(qū)。遍歷結(jié)束后再執(zhí)行刪除操作。(2)算法的設(shè)計(jì)如下：typedefstructLNode{intdata；structLNode*next；}LNode*Linkedlist：LinkedListDelete(LinkedListL){／／L是帶頭結(jié)點(diǎn)的單鏈表，本算法刪除其最小值結(jié)點(diǎn)Linkedlist*P，*q，*pre：P=L一>next；／／p為工作指針，指向待處理的結(jié)點(diǎn)。假定鏈表非空pre=L；／／pre指向最小值結(jié)點(diǎn)的前驅(qū)q=P；／／q指向最小值結(jié)點(diǎn)，初始假定第一元素結(jié)點(diǎn)是最小值結(jié)點(diǎn)while(p一>next!=null){if(P一>next一>datadata){pre=P；q=P一>nexti}／／查最小值結(jié)點(diǎn)P=P一>next；／／指針后移}pre一>next=q一>next；／／從鏈表上刪除最小值結(jié)點(diǎn)free(q)；／／釋放最小值結(jié)點(diǎn)空間}／／結(jié)束算法delete知識(shí)點(diǎn)解析：暫無(wú)解析5、請(qǐng)利用兩個(gè)棧s1和s2來(lái)模擬一個(gè)隊(duì)列。已知棧的三個(gè)運(yùn)算定義如下：(1)push(st，x)：元素x入st棧；(2)pop(st，x)：st棧頂元素出棧，賦給變量x：(3)sempty(st)：判st棧是否為空。那么如何利用棧的運(yùn)算來(lái)實(shí)現(xiàn)該隊(duì)列的三個(gè)運(yùn)算：(1)enqueue：插入一個(gè)元素入隊(duì)列；(2)dequeue：刪除一個(gè)元素出隊(duì)列：(3)queue_empty：判隊(duì)列為空。(請(qǐng)寫明算法的思想及必要的注釋。)標(biāo)準(zhǔn)答案：棧的特點(diǎn)是后進(jìn)先出，隊(duì)列的特點(diǎn)是先進(jìn)先出。所以，用兩個(gè)棧sl和s2模擬一個(gè)隊(duì)列時(shí)，s1作輸入棧，逐個(gè)元素壓棧，以此模擬隊(duì)列元素的入隊(duì)。當(dāng)需要出隊(duì)時(shí)，將棧s1退棧并逐個(gè)壓入棧s2中，s1中最先入棧的元素，在s2中處于棧頂。s2退棧，相當(dāng)于隊(duì)列的出隊(duì)，實(shí)現(xiàn)了先進(jìn)先出。顯然，只有棧s2為空且s1也為空，才算是隊(duì)列空。(1)intenqueue(stacks1，elemtpx){／／s1是容量為n的棧，棧中元素類型是elemtp。本算法將x入棧，／／若入棧成功返回1，否則返回0if(top1==n&&!sempty(s2))／／top1是棧s1的棧頂指針，是全局變量{printf(“棧滿”)；return(0)；}／／s1滿s2非空，這時(shí)s1不能再入棧if(top1==n&&sempty(s2))／／若s2為空，先將s1退棧，元素再壓棧到s2{while(!sempty(s1)){pop(s1，x)；push(s2，x)；}push(s1，x)；return(1)；／／x入棧，實(shí)現(xiàn)了隊(duì)列元素的入隊(duì)}(2)voiddequeue(stacks2，s1){／／s2是輸出棧，本算法將s2棧頂元素退棧，實(shí)現(xiàn)隊(duì)列元素的出隊(duì)if(!sempty(s2))／／棧s2不空，則直接出隊(duì){pop(s2，x)；printf(“出隊(duì)元素為”，x)；}else／／處理s2空棧if(sempty(s1)){printf(“隊(duì)列空”)；exit(0)；}／／若輸入棧也為空，則判定隊(duì)空else／／先將棧s1倒入s2中，再做出隊(duì)操作{while(!sempty(s1)){pop(s1，x)；push(s2，x)；}pop(s2，x)；／／s2退棧相當(dāng)于隊(duì)列出隊(duì)printf(“出隊(duì)元素”，x)；}(3)intquelle_empty(){／／本算法判用棧s1和s2模擬的隊(duì)列是否為空if(sempty(s1)&&sempty(s2))return(1)；／／隊(duì)列空elsereturn(0)；／／隊(duì)列不空}提示：算法中假定棧s1和棧s2容量相同。出隊(duì)從棧s2出，當(dāng)s2為空時(shí)，若s1不空，則將s1倒入s2再出棧。入隊(duì)在s1，當(dāng)s1滿后，若s2空，則將s1倒入s2，之后再入隊(duì)。因此隊(duì)列的容量為兩棧容量之和。元素從棧s1倒入s2，必須在s2空的情況下才能進(jìn)行，即在要求出隊(duì)操作時(shí)，若s2空，則不論s1元素多少(只要不空)，就要全部倒入s2中。知識(shí)點(diǎn)解析：暫無(wú)解析6、畫出如下圖所示的二叉樹所對(duì)應(yīng)的森林。標(biāo)準(zhǔn)答案：該二又樹所對(duì)應(yīng)的森林如下圖所示，它由四棵樹組成。知識(shí)點(diǎn)解析：暫無(wú)解析7、已知二叉樹T的結(jié)點(diǎn)形式為(llink，data，count，rlink)，在樹中查找值為X的結(jié)點(diǎn)，若找到，則記數(shù)(count)加l；否則，作為一個(gè)新結(jié)點(diǎn)插入樹中，插入后仍為二叉排序樹，寫出其非遞歸算法。標(biāo)準(zhǔn)答案：typedefstructnode{datatypedata；intcount；structnode；*llink，*rlink；}BiTNode，*BSTree；voidSearch_InsertX(BSTreet，datatypeX){／／在二叉排序樹t中查找值為X的結(jié)點(diǎn)，若查到，則其結(jié)點(diǎn)的count域值增1，／／否則，將其插入到二叉排序樹中BSTreep=t；while(p!=null&&P->data!=X){／／查找值為X的結(jié)點(diǎn)，f指向當(dāng)前結(jié)點(diǎn)的雙親f=p；if(p一>datarlink；elsep=p一>llink；}if(!p){／／無(wú)值為x的結(jié)點(diǎn)，插入之p=(BiTNode*)malloc(sizeof(BiTNode))；p一>data=X；p一>llink=null；p一>rlink=null；if(f->data>X)f一>llink=p；elsef一>rlink=p：}elsep->count++；／／查詢成功，值域?yàn)閄的結(jié)點(diǎn)的count增1}知識(shí)點(diǎn)解析：暫無(wú)解析8、寫一個(gè)建立堆的算法：從空堆開始，依次讀入元素，調(diào)用上題中堆插入算法將其插入堆中。標(biāo)準(zhǔn)答案：建立堆的算法如下：voidBuildHeap(SeqListR，KeyTypeA[n]){／／類型定義inti；R．1en=0：／／初始化for(i=0；i知識(shí)點(diǎn)解析：暫無(wú)解析9、設(shè)某機(jī)中，CPU的地址總線為A15～A0，數(shù)據(jù)總線為D7～D0(A0、D0為最低位)。存儲(chǔ)器地址空間為3000H～67FFH。其中3000H～4FFFH為ROM區(qū)，選用4K×2的ROM芯片；5000H～67FFH為RAM區(qū)，選用2K×4的SRAM芯片。請(qǐng)問：(1)組成該存儲(chǔ)器需要多少片ROM芯片和SRAM芯片?(2)ROM芯片、SRAM芯片各需連接CPU的哪幾根地址線和數(shù)據(jù)線?(3)應(yīng)如何設(shè)置片選信號(hào)，分別寫出各片選信號(hào)的邏輯表達(dá)式。標(biāo)準(zhǔn)答案：(I)已知數(shù)據(jù)總線為8位，ROM區(qū)為3000H～4FFFFH，故ROM的容量為8K×8b；ROM芯片數(shù)=(8K×8b)÷(4K×2b)=8片(分為2組，每組4片)。RAM區(qū)為5000H～67FFH，故RAM的容量為6K×8b；SRAM芯片數(shù)=(6K×8b)÷(2K×4b)=6片(分為3組，每組2片)。(2)ROM芯片的容量為4K×2，具有12根地址線、2根數(shù)據(jù)線，因此ROM芯片的地址線連接CPU地址線的低12位A11～A0，每組ROM內(nèi)的4片芯片分別連接CPU數(shù)據(jù)線的D7D6、D5D4、D3D2、D1D0。SRAM芯片的容量為2K×4，具有11根地址線、4根數(shù)據(jù)線，因此SRAM芯片的地址線連接CPU地址線的低11位A10～A0，每組SRAM內(nèi)的2片芯片分別連接CPU數(shù)據(jù)線的D7D6D5D4、D3D2D1D0。(3)ROM區(qū)有2個(gè)片選信號(hào)，RAM區(qū)有3個(gè)片選信號(hào)，共需5個(gè)片選信號(hào)，根據(jù)地址分配的要求，各片選信號(hào)的邏輯表達(dá)式如下：CS0=A15A14A13A12CS1=A15A14A13A12CS2=A15A14A13A12A11CS3=A15A14A13A12A11CS4=A15A14A13A12A11知識(shí)點(diǎn)解析：暫無(wú)解析10、什么是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)為解決并行所帶來(lái)的死鎖問題，在wait操作中引入AND條件，其基本思想是將進(jìn)程在整個(gè)運(yùn)行過程中所需要的所有臨界資源一次性地全部分配給進(jìn)程，用完后一次性釋放。(2)解決生產(chǎn)者一消費(fèi)者問題可描述如下：varmutex，empty，full：semaphore：=1，n，0；buffer：array[0．．n一1]ofitem：in，out：integer：=0，0：beginparbeginproducer：beginrepeat……produceaniteminnextp；……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)解析：暫無(wú)解析11、我們?yōu)槟撑R界區(qū)設(shè)置一把鎖W，當(dāng)W=1時(shí)表示關(guān)鎖，W=0時(shí)表示鎖已打開。試寫出開鎖原語(yǔ)和關(guān)鎖原語(yǔ)，并利用它們?nèi)?shí)現(xiàn)互斥。標(biāo)準(zhǔn)答案：(1)開鎖原語(yǔ)：unlock(W)：W=0；關(guān)鎖原語(yǔ)：lock(W)；if(W==1)dono_op；W=1；(2)利用開關(guān)鎖原語(yǔ)實(shí)現(xiàn)互斥：vatW：semaphore：=0；beginparbeginprocess：beginrepeatlock(W)；criticalsectionunlock(W)：remaindersectionuntilfalse；endparend知識(shí)點(diǎn)解析：暫無(wú)解析12、試述最佳、最差、最先適應(yīng)算法的基本思想，并指出它們各自的優(yōu)缺點(diǎn)。標(biāo)準(zhǔn)答案：(1)最佳適應(yīng)算法：為一作業(yè)選擇分區(qū)時(shí)總是尋找其大小最接近于作業(yè)所要求的存儲(chǔ)空間。優(yōu)點(diǎn)：如果存儲(chǔ)空間中具有正好是所要求大小的空閑區(qū)，則必然被選中；如果不存在這樣的空閑區(qū)，也只對(duì)比要求稍大的空閑區(qū)劃分，而不會(huì)去劃分一個(gè)更大的空閑區(qū)。(2)最差適應(yīng)算法：為作業(yè)選擇存儲(chǔ)空間時(shí)總是尋找最大的空閑區(qū)。(3)最先適應(yīng)算法：將空閑區(qū)按其在存儲(chǔ)空間中的起始地址遞增的順序排列。為作業(yè)分配存儲(chǔ)空間時(shí)，從空閑區(qū)鏈的始端開始查找，選擇第一個(gè)滿足要求的空閑區(qū)，而不管它究竟有多大。知識(shí)點(diǎn)解析：暫無(wú)解析13、請(qǐng)求分頁(yè)和簡(jiǎn)單分頁(yè)兩種存儲(chǔ)管理方案有何不同?缺頁(yè)中斷是如何發(fā)生的?發(fā)生缺頁(yè)中斷時(shí)如何處理?標(biāo)準(zhǔn)答案：(1)請(qǐng)求頁(yè)式管理在作業(yè)或進(jìn)程開始執(zhí)行之前，不要求把作業(yè)或進(jìn)程的程序段和數(shù)據(jù)段一次性地全部裝入主存，而只把當(dāng)前需要的一部分頁(yè)面裝入主存，其他部分在作業(yè)執(zhí)行過程中需要時(shí)再?gòu)妮o存上調(diào)入主存。(2)當(dāng)調(diào)用頁(yè)不在主存時(shí)發(fā)生缺頁(yè)中斷。若主存中沒有空閑塊時(shí)，首先按照某種策略選擇某頁(yè)進(jìn)行淘汰，以騰出空閑塊供本次調(diào)入的頁(yè)占用。若被選中淘汰的頁(yè)面中的信息修改過(修改位=1)還必須將其寫入輔存。如主存中有空閑塊，則根據(jù)該頁(yè)在輔存的地址調(diào)入所需頁(yè)面，并更新頁(yè)表，最后恢復(fù)被中斷的指令重新執(zhí)行。知識(shí)點(diǎn)解析：暫無(wú)解析14、計(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)解析：暫無(wú)解析15、假設(shè)Internet的2個(gè)自治系統(tǒng)構(gòu)成的網(wǎng)絡(luò)如下圖所示：自治系統(tǒng)ASl由路由器R1連接2個(gè)子網(wǎng)構(gòu)成：自治系統(tǒng)AS2由路由器R2、R3互聯(lián)并連接3個(gè)子網(wǎng)構(gòu)成。各子網(wǎng)地址、R2的接口名、R1與R3的部分接口IP地址如圖所示：請(qǐng)回答下列問題：假設(shè)路由表結(jié)構(gòu)如下表所示，請(qǐng)利用路由聚合技術(shù)，給出R2的路由表，要求包括到圖中所有子網(wǎng)的路由，且路由表中的路由項(xiàng)盡可能少。標(biāo)準(zhǔn)答案：在路由聚合過程中，需要將原本較小的網(wǎng)絡(luò)合成一個(gè)大的網(wǎng)絡(luò)，而在這個(gè)大的網(wǎng)絡(luò)中包含了原有的比較小的網(wǎng)絡(luò)。在自治域ASl中，子網(wǎng)153．14．5．0／25和子網(wǎng)153．14．5．128／25是兩個(gè)網(wǎng)絡(luò)，且兩個(gè)網(wǎng)絡(luò)的網(wǎng)絡(luò)號(hào)均為25位，將其寫成32位標(biāo)準(zhǔn)的IP地址格式為：可以聚合為子網(wǎng)153．14．5．0／24。在As2中，子網(wǎng)194．17．20．0／25和子網(wǎng)194．17．21．0／24可以聚合為子網(wǎng)194．17．20．0／23，但缺少194．17．20．128／25；子網(wǎng)194．17．20．128／25單獨(dú)連接到R2的接口E0。于是可以得到R2的路由表如下：知識(shí)點(diǎn)解析：暫無(wú)解析16、試計(jì)算一個(gè)包括5段鏈路的傳輸連接的單程端到端時(shí)延。5段鏈路中有2段是衛(wèi)星鏈路，每條衛(wèi)星鏈路又由上行鏈路和下行鏈路兩部分組成，可以取這兩部分的傳播時(shí)延之和為250ms。每一個(gè)廣域網(wǎng)的范圍為1500km，其傳播時(shí)延可按150000km／s來(lái)計(jì)算。各數(shù)據(jù)鏈路速率為48kb／s，幀長(zhǎng)為960b。標(biāo)準(zhǔn)答案：5段鏈路的傳播時(shí)延=250×2+(1500／150000)×3×1000=530ms。5段鏈路的發(fā)送時(shí)延=960／(48×1000)×5×1000=100ms。所以5段鏈路單程端到端時(shí)延=530+100=630ms。知識(shí)點(diǎn)解析：暫無(wú)解析設(shè)某計(jì)算機(jī)有變址尋址、間接尋址和相對(duì)尋址等尋址方式。設(shè)當(dāng)前指令的地址碼部分為001AH，正在執(zhí)行的指令所在地址為1F05H，變址寄存器中的內(nèi)容為23A0H。已知存儲(chǔ)器的部分地址及相應(yīng)內(nèi)容，見下表：17、當(dāng)執(zhí)行取數(shù)指令時(shí)，如為變址尋址方式，取出的數(shù)為多少?標(biāo)準(zhǔn)答案：變址尋址的尋址過程如下：變址尋址工作原理：指令地址碼部分給出的地址A和指定的變址寄存器x的內(nèi)容通過加法器相加，所得的和作為地址從存儲(chǔ)器中讀出所需的操作數(shù)。因此，操作數(shù)S=((Rx)+A)=(23AOH+001AH)=(23BAH)=1748H。知識(shí)點(diǎn)解析：暫無(wú)解析18、如為間接尋址，取出的數(shù)為多少?標(biāo)準(zhǔn)答案：間接尋址的尋址過程如下：變址尋址工作原理：對(duì)于存儲(chǔ)器一次間址的情況，需訪問兩次存儲(chǔ)器才能取得數(shù)據(jù)第一次從存儲(chǔ)器讀出操作數(shù)地址；第二次從該地址中讀取操作數(shù)。因此，操作數(shù)S=((A))=((001AH))=(23AOH)=2600H知識(shí)點(diǎn)解析：暫無(wú)解析19、當(dāng)執(zhí)行轉(zhuǎn)移指令時(shí)，轉(zhuǎn)移地址為多少?標(biāo)準(zhǔn)答案：轉(zhuǎn)移指令使用相對(duì)尋址，其過程如下：轉(zhuǎn)移地址=(PC)+A=1F06H+1H+001AH=1F21H。知識(shí)點(diǎn)解析：暫無(wú)解析20、IPv6是為了解決什么問題而提出的?它與IPv4相比有哪些優(yōu)勢(shì)?說(shuō)說(shuō)它們之間的區(qū)別。標(biāo)準(zhǔn)答案：IPv6是為了解決IPv4地址不足的問題而提出的。其優(yōu)點(diǎn)總結(jié)起來(lái)有以下幾點(diǎn)：(1)擴(kuò)展了路由和尋址的能力：IPv6把IP地址由32位增加到128位，從而能夠支持更大的地址空間，估計(jì)在地球表面每平方米有4×1018個(gè)IPv6地址，使IP地址在可預(yù)見的將來(lái)不會(huì)用完。IPv6地址的編碼采用類似于CIDR的分層分級(jí)結(jié)構(gòu)，如同電話號(hào)碼。簡(jiǎn)化了路由，加快了路由速度。在多點(diǎn)傳播地址中增加了一個(gè)“范圍”域，從而使多點(diǎn)傳播不僅僅局限在子網(wǎng)內(nèi)，而是可以橫跨不同的子網(wǎng)、不同的局域網(wǎng)。(2)報(bào)頭格式的簡(jiǎn)化：IPv4報(bào)頭格式中一些冗余的域或被丟棄或被列為擴(kuò)展報(bào)頭，從而降低了包處理和報(bào)頭帶寬的開銷。雖然：IPv6的地址是IPv4地址的4倍，但報(bào)頭只有它的2倍大。(3)對(duì)可選項(xiàng)更大的支持：IPv6的可選項(xiàng)不放入報(bào)頭，而是放在一個(gè)個(gè)獨(dú)立的擴(kuò)展頭部。如果不指定路由器不會(huì)打開處理擴(kuò)展頭部，這大大改變了路由性能。IPv6放寬了對(duì)可選項(xiàng)長(zhǎng)度的嚴(yán)格要求(IPv4的可選項(xiàng)總長(zhǎng)最多為40字節(jié))，并可根據(jù)需要隨時(shí)引入新選項(xiàng)。IPv6的很多新的特點(diǎn)就是由選項(xiàng)來(lái)提供的，如對(duì)IP層安全(IPSee)的支持，對(duì)巨報(bào)(jumbogram)的支持以及對(duì)IP層漫游(Mobile-IP)的支持等。(4)QoS的功能：因特網(wǎng)不僅可以提供各種信息，縮短人們之間的距離，還可以進(jìn)行網(wǎng)上娛樂。網(wǎng)上VOD現(xiàn)正被商家炒得熱火朝天，而大多還只是準(zhǔn)VOD的水平，且只能在局域網(wǎng)上實(shí)現(xiàn)，因特網(wǎng)上的VOD很不理想。問題在于IPv4的報(bào)頭雖然有服務(wù)類型字段，實(shí)際上現(xiàn)在的路由器實(shí)現(xiàn)中都忽略了這一字段。在IPv6的頭部，有兩個(gè)相應(yīng)的優(yōu)先權(quán)和流標(biāo)識(shí)字段，允許把數(shù)據(jù)報(bào)指定為某一信息流的組成部分，并可對(duì)這些數(shù)據(jù)報(bào)進(jìn)行流量控制。如對(duì)于實(shí)時(shí)通信即使所有分組都丟失也要保持恒速，所以優(yōu)先權(quán)最高，而一個(gè)新聞分組延遲幾秒鐘也沒什么感覺，所以其優(yōu)先權(quán)較低。IPv6指定這兩個(gè)字段是每一IPv6結(jié)點(diǎn)都必須實(shí)現(xiàn)的。(5)身份驗(yàn)證和保密：在IPv6中加入了關(guān)于身份驗(yàn)證、數(shù)據(jù)一致性和保密性的內(nèi)容。知識(shí)點(diǎn)解析：暫無(wú)解析考研計(jì)算機(jī)專業(yè)基礎(chǔ)綜合（綜合應(yīng)用題）模擬試卷第3套一、綜合應(yīng)用題(本題共20題，每題1.0分，共20分。)1、某一計(jì)算機(jī)系統(tǒng)采用虛擬頁(yè)式存儲(chǔ)管理方式，當(dāng)前在處理機(jī)上執(zhí)行的某一個(gè)進(jìn)程的頁(yè)表如下所示，所有的數(shù)字均為十進(jìn)制，每一項(xiàng)的起始編號(hào)是0，并且所有的地址均按字節(jié)編址，每頁(yè)的大小為1024B。(1)將下列邏輯地址轉(zhuǎn)換為物理地址，寫出計(jì)算過程，對(duì)不能計(jì)算的說(shuō)明為什么?0793，1197，2099，3320，4188，5332(2)假設(shè)程序欲訪問第2頁(yè)，頁(yè)面置換算法為改進(jìn)的CLOCK算法，請(qǐng)問該淘汰哪頁(yè)?如何修改頁(yè)表?上述地址的轉(zhuǎn)換結(jié)果是否改變?變成多少?標(biāo)準(zhǔn)答案：本題考查邏輯地址到物理地址的轉(zhuǎn)換、頁(yè)面置換等。地址轉(zhuǎn)換過程一般是先將邏輯頁(yè)號(hào)取出，然后查找頁(yè)表，得到頁(yè)框號(hào)，將頁(yè)框號(hào)與頁(yè)內(nèi)偏移量相加，即可獲得物理地址。若取不到頁(yè)框號(hào)，那么該頁(yè)不在內(nèi)存，于是產(chǎn)生缺頁(yè)中斷，開始請(qǐng)求調(diào)頁(yè)。若內(nèi)存有足夠的物理頁(yè)面，那么可以再分配一個(gè)新的頁(yè)面。若沒有頁(yè)面了，就必須在現(xiàn)有的頁(yè)面之中找到一個(gè)頁(yè)，將新的頁(yè)與之置換，這個(gè)頁(yè)可以是系統(tǒng)中的任意一頁(yè)，也可以是本進(jìn)程中的一頁(yè)。若是系統(tǒng)中的一頁(yè)，則這種置換方式稱為全局置換；若是本進(jìn)程的頁(yè)面，則稱為局部置換。置換時(shí)為盡可能地減少缺頁(yè)中斷次數(shù)，可以有多種算法來(lái)應(yīng)用，本題使用的是改進(jìn)的CLOcK算法。這種算法必須使用頁(yè)表中的引用位和修改位，由這2位組成4種級(jí)別，沒有引用和沒有修改的頁(yè)面最先淘汰，沒有引用但修改了的頁(yè)面其次，再次淘汰引用了但是沒有修改的頁(yè)面，最后淘汰既引用又修改了的頁(yè)面，當(dāng)頁(yè)面的引用位和修改位相同時(shí)，隨機(jī)淘汰一頁(yè)。(1)根據(jù)題意，每頁(yè)1024B，地址又是按字節(jié)編址，計(jì)算邏輯地址的頁(yè)號(hào)和頁(yè)內(nèi)偏移量，合成物理地址如下表所示。(2)第2頁(yè)不在內(nèi)存，產(chǎn)生缺頁(yè)中斷，根據(jù)改進(jìn)的CLOCK算法，第3頁(yè)為沒有引用和沒修改的頁(yè)面，故淘汰。新頁(yè)面進(jìn)入，頁(yè)表修改如下：因?yàn)轫?yè)面2調(diào)入是為了使用，所以頁(yè)面2的引用位必須改為1。地址轉(zhuǎn)換變?yōu)槿缦卤恚褐R(shí)點(diǎn)解析：暫無(wú)解析2、利用比較的方法進(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è)葉子，則說(shuō)明尚有兩種狀態(tài)沒有分辨出來(lái)。我們知道，若二又樹高度是h，則葉子結(jié)點(diǎn)個(gè)數(shù)最多為2h-1；反之，若有u個(gè)葉子結(jié)點(diǎn)，則二叉樹的高度至少為(log2u)+1。這就是說(shuō)，描述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í)點(diǎn)解析：暫無(wú)解析3、比較IEEE802．11使用的CSMA／CA與IEEE802．3使用的CSMA／CD之間的區(qū)別。標(biāo)準(zhǔn)答案：CSMA／CA協(xié)議的關(guān)鍵在于沖突避免，它與CSMA／CD中的沖突檢測(cè)有著本質(zhì)的區(qū)別。CSMA／CA不是在發(fā)送過程中監(jiān)聽是否發(fā)生了沖突，而是事先就要設(shè)法避免沖突的發(fā)生。采用這種方法的原因是由于無(wú)線信道的特殊性質(zhì)而使得在無(wú)線網(wǎng)絡(luò)中檢測(cè)信道是否存在沖突比較困難：要檢測(cè)沖突，設(shè)備必須能夠在發(fā)送數(shù)據(jù)的同時(shí)接收數(shù)據(jù)，以便檢測(cè)是否發(fā)生沖突，這對(duì)于無(wú)線網(wǎng)絡(luò)設(shè)備是非常難以實(shí)現(xiàn)的。無(wú)線介質(zhì)上的信號(hào)強(qiáng)度的動(dòng)態(tài)范圍很大，因此發(fā)送站無(wú)法用信號(hào)強(qiáng)度的變化來(lái)檢測(cè)是否發(fā)生了沖突。CSMA／CA協(xié)議中發(fā)送過程的“載波檢測(cè)多路訪問”部分是在兩個(gè)層次上進(jìn)行的，一個(gè)是物理層次，另一個(gè)是虛擬層次。物理層次上的載波檢測(cè)機(jī)制與IEEE802．3以太網(wǎng)使用的載波偵聽基本相同。要發(fā)送數(shù)據(jù)的站點(diǎn)首先要偵聽介質(zhì)上有無(wú)信號(hào)，如果信道處于“空閑”狀態(tài)，它就可以開始發(fā)送數(shù)據(jù)。如果信道上有信號(hào)傳播，它就推遲自己的傳輸而繼續(xù)監(jiān)聽直到信道空閑。任何站點(diǎn)當(dāng)檢測(cè)到信道由忙變閑時(shí)，都必須通過退避算法與其他站點(diǎn)一起競(jìng)爭(zhēng)信道的訪問權(quán)，而不是直接訪問信道。虛擬層次上的載波檢測(cè)是通過接收到其他站點(diǎn)要占用介質(zhì)的通告而主動(dòng)推遲本站的發(fā)送來(lái)實(shí)現(xiàn)的，其效果相當(dāng)于“檢測(cè)”到信道忙而延遲發(fā)送。虛擬載波檢測(cè)利用了IEEE802．11幀中的“傳輸持續(xù)時(shí)間”字段。每一站點(diǎn)的MAC層將檢查接收到的幀中的“傳輸持續(xù)時(shí)間”字段，如果發(fā)現(xiàn)該字段的值大于當(dāng)前站點(diǎn)的網(wǎng)絡(luò)分配矢量NAV的值，就用該字段的值更新本站點(diǎn)的NAV。站點(diǎn)要發(fā)送數(shù)據(jù)時(shí)，NAV從設(shè)定的值開始不斷減1，當(dāng)NAV的值減為0，且物理層報(bào)告信道空閑時(shí)，它就可以開始發(fā)送數(shù)據(jù)。知識(shí)點(diǎn)解析：暫無(wú)解析4、設(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)解析：暫無(wú)解析5、有兩個(gè)集合A和B，利用帶頭結(jié)點(diǎn)鏈表表示，設(shè)頭指針分別為la和lb。兩集合的鏈表元素皆為遞增有序。設(shè)計(jì)一個(gè)算法，將A與B合并，合并后仍然保持整個(gè)鏈表中的數(shù)據(jù)依次遞增。不得利用額外的結(jié)點(diǎn)空間，只能在A和B的原有結(jié)點(diǎn)空間上完成。要求：(1)給出算法的基本設(shè)計(jì)思想。(2)根據(jù)設(shè)計(jì)思想，采用C或C++或Java語(yǔ)言描述算法，關(guān)鍵之處給出注釋。(3)分別給出算法各部分的時(shí)間復(fù)雜度。標(biāo)準(zhǔn)答案：(1)算法的基本設(shè)計(jì)思想：分別從A、B的頭結(jié)點(diǎn)開始，依次比較A、B中元素的內(nèi)容，如果A中的元素值大于B中的元素值，則將B中的結(jié)點(diǎn)插入結(jié)果鏈表，反之將A中的結(jié)點(diǎn)插入結(jié)果鏈表。由于題目中要求將結(jié)果鏈表中的結(jié)點(diǎn)按元素值的大小依次遞增地排列。因此，如果A、B中兩個(gè)元素值相同，只將其中的一個(gè)加入結(jié)果鏈表。(2)算法的設(shè)計(jì)如下：typedefstructLNode{intdata；structINode*next；}*Linkedlist；LinkedListunion(IAnkedListla，lb){pa=la一>next；pb=lb一>next；／／設(shè)工作指針pa和pbpc=la；／／pc為結(jié)果鏈表當(dāng)前結(jié)點(diǎn)的前驅(qū)指針while(pa&&pb){if(pa->datadata){pc->next=pa；pc=pa；pa=pa-＞next}elseif(pa->data>pb->data){pc->next=pb；pc=pb；pb=pb一>next；}else{／／處理pa一>data=pb一>data．pc->next=pa：pc=pa；pa=pa一>next；u=pb；pb=pb一>next；flee(u)；}}if(pa)pc一>next=pa；／／若la表未空，則鏈入結(jié)果表elsepc->next=pb；／／若lb表未空，則鏈入結(jié)果表free(lb)：／／釋放lb頭結(jié)點(diǎn)return(1a)；}(3)本題中的主要操作是依次比較A、B鏈表中的數(shù)據(jù)元素值的大小，因此時(shí)間復(fù)雜度為O(n)。知識(shí)點(diǎn)解析：暫無(wú)解析6、試寫一算法，判斷以鄰接表方式存儲(chǔ)的有向圖中是否存在由頂點(diǎn)Vi到頂點(diǎn)Vj的路徑(i≠j)。(注意：算法中涉及的圖的基本操作必須在存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)。)標(biāo)準(zhǔn)答案：算法1：intvisited[]=0；／／全局變量，訪問數(shù)組初始化intdfs(AdjListg，vi){／／以鄰接表存儲(chǔ)的有向圖g，判斷vi到vj是否有通路，返回1或0visited[vi]=1；／／visited是訪問數(shù)組，設(shè)頂點(diǎn)的信息就是頂點(diǎn)編號(hào)p=g[vi]．firstarc；／／第一個(gè)鄰接點(diǎn)while(p!=null){j=p一>adjvex；if(vj==j){flag=1；return(1)；}／／vi和vj有通路if(visited[j]==0)dfs(g，j)；p=p一>next：}／／whileif(!flag)return(0)；}算法2：輸出vi到vj的路徑，其思想是用一個(gè)棧存放遍歷的頂點(diǎn)，遇到頂點(diǎn)vj時(shí)輸出路徑。voiddfs(AdjListg，inti){／／頂點(diǎn)vi和頂點(diǎn)vj問是否有路徑，如有，則輸出inttop=0，stack[]；／／stack是存放頂點(diǎn)編號(hào)的棧visited[i]=1；／／visited數(shù)組在進(jìn)入dfs前已初始化stack[++top]=i；p=g[i]．firstarc；／／求第一個(gè)鄰接點(diǎn)while(p){if(P一>adjvex==j){stack[++top]=j；printf(“頂點(diǎn)vi和vj的路徑為：＼n”)；for(i=1；i<=top；i++)printf(“％4d”，stack[i])；exit(0)；}elseif(visited[p一>adjvex]==0){dfs(g，g一>adjvex)；top--；P=p一>next；}}}算法3：非遞歸算法求解。intJudge(AdjListg，inti，j){／／判斷13．個(gè)頂點(diǎn)以鄰接表示的有向圖g中，頂點(diǎn)vi各vj是否有路徑，／／有則返回1，否則返回0。for(i=1；i<=n；i++)visited[i]=0；／／訪問標(biāo)記數(shù)組初始化intstack[]，top=0；stack[++top]=vi；while(top>0){k=stack[top--]；p=g[k]．firstarc；while(P!=null&&visited[p一>adjvex]==1)P=p->next；／／查第k個(gè)鏈表中第一個(gè)未訪問的弧結(jié)點(diǎn)if(p==null)top--：else{i=p一>adjvex；if(i==j)return(1)；／／頂點(diǎn)vi和vj間有路徑else{visited[i]=1；stack[++top]=i；}}}whilereturn(0)；}／／頂點(diǎn)vi和vj間無(wú)通路提示：此題考查的知識(shí)點(diǎn)是圖的遍歷。在有向圖中，判斷頂點(diǎn)vi和頂點(diǎn)vj間是否有路徑，可采用搜索的方法，從頂點(diǎn)vi出發(fā)，不論是深度優(yōu)先搜索(DFS)還是寬度優(yōu)先搜索(BFS)，在未退出DFS函數(shù)或BFS函數(shù)前，若訪問到vj，則說(shuō)明有通路，否則無(wú)通路。設(shè)一全程變量flag，初始化為0，若有通路，則flag=1。知識(shí)點(diǎn)解析：暫無(wú)解析7、用C語(yǔ)言或PASCAL編寫一用鏈接表(LinkedList)解決沖突的哈希表插入函數(shù)。標(biāo)準(zhǔn)答案：本題仍用上面已定義的存儲(chǔ)結(jié)構(gòu)。首先計(jì)算關(guān)鍵字K的哈希地址，若該哈希地址的頭指針為空，則直接插入；否則，先在該鏈表上查找，若查找失敗，則插入鏈表；若查找成功，則不再插入。typedefstructnode{keytypekey；structnode*next；}HSNode*HSList：typedefstructnode*HLK：voidInsert(HLKHT[]；keytypeK){／／用鏈接表解決沖突的哈希表插入函數(shù)i=H(K)；／／計(jì)算關(guān)鍵字K的哈希地址if(HT[i]==null)／／關(guān)鍵字K所在鏈表為空{(diào)s=(HSNode*)malloc(sizeof(HSNode))；s一>key=k；s->next=HT[i]：HT[i]=s；}else{／／在鏈表中查詢關(guān)鍵字Kp=HT[i]；while(P&&p一>key!=k)P=p->next：if(!p){／／鏈表中無(wú)關(guān)鍵字K，應(yīng)該插入s：(HSNode*)malloc(sizeof(HSNode))；s一>next=HT[i]；HT[i]=s；}／／插入后成為哈希地址為i的鏈表中的第一個(gè)結(jié)點(diǎn)}}知識(shí)點(diǎn)解析：暫無(wú)解析8、編寫對(duì)有序表進(jìn)行順序查找的算法，并畫出對(duì)有序表進(jìn)行順序查找的判定樹。假設(shè)每次查找時(shí)的給定值為隨機(jī)值，且查找成功和不成功的概率也相等，試求進(jìn)行每一次查找時(shí)和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值。標(biāo)準(zhǔn)答案：intSearch(rectypeR[]，intn，K){／／在具有n個(gè)元素的有序表R中，順序查找值為K的結(jié)點(diǎn)，查找成功返回其位置，／／否則返回一1表示失敗inti=0：while(iK)return(一1)ii++：}／／whilereturn一1；}在等概率的情況下，則查找成功的平均查找長(zhǎng)度為(n+1)／2，查找失敗的平均查找長(zhǎng)度為(n+2)／2(失敗位置除小于第一個(gè)，還存在大于最后一個(gè))。若查找成功和不成功的概率也相等，則查找成功時(shí)和關(guān)鍵字比較的個(gè)數(shù)的期望值約為(n+1)／4。知識(shí)點(diǎn)解析：暫無(wú)解析9、冒泡排序方法是把大的元素向上移(氣泡的上浮)，也可以把小的元素向下移(氣泡的下沉)。請(qǐng)給出上浮和下沉過程交替的冒泡排序算法。標(biāo)準(zhǔn)答案：voidBubbleSort2(inta[]，intn){／／相鄰兩趟向相反方向起泡的冒泡排序算法intchange=1：low=0；high=n一1；／／冒泡的上下界while(lowa[i+1]){a[i]←→a[i+1]；change=1；}／／有交換，修改標(biāo)