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

考研計(jì)算機(jī)專業(yè)基礎(chǔ)綜合（綜合應(yīng)用題）模擬試卷1（共9套）（共180題）考研計(jì)算機(jī)專業(yè)基礎(chǔ)綜合（綜合應(yīng)用題）模擬試卷第1套一、綜合應(yīng)用題(本題共20題，每題1.0分，共20分。)1、設(shè)有n個(gè)進(jìn)程共享一個(gè)互斥段，如果：(1)每次只允許一個(gè)進(jìn)程進(jìn)入互斥段；(2)每次最多允許m個(gè)進(jìn)程(m≤n)同時(shí)進(jìn)入互斥段。試問(wèn)：所采用的信號(hào)量初值是否相同?信號(hào)量值的變化范圍如何?標(biāo)準(zhǔn)答案：所采用的互斥信號(hào)量初值不同。(1)互斥信號(hào)量初值為1，變化范圍為[-n+1，1]。當(dāng)沒(méi)有進(jìn)程進(jìn)入互斥段時(shí)，信號(hào)量值為1；當(dāng)有1個(gè)進(jìn)程進(jìn)入互斥段但沒(méi)有進(jìn)程等待進(jìn)入互斥段時(shí)，信號(hào)量值為0；當(dāng)有1個(gè)進(jìn)程進(jìn)入互斥段且有一個(gè)進(jìn)程等待進(jìn)入互斥段時(shí)，信號(hào)量值為一1；最多可能有n—1個(gè)進(jìn)程等待進(jìn)入互斥段，故此時(shí)信號(hào)量的值應(yīng)為一(n—1)，也就是一n+1。(2)互斥信號(hào)量初值為m，變化范圍為[一n+m，m]。當(dāng)沒(méi)有進(jìn)程進(jìn)入互斥段時(shí)，信號(hào)量值為m；當(dāng)有1個(gè)進(jìn)程進(jìn)入互斥段但沒(méi)有進(jìn)程等待進(jìn)入互斥段時(shí)，信號(hào)量值為m一1；當(dāng)有m個(gè)進(jìn)程進(jìn)入互斥段且沒(méi)有一個(gè)進(jìn)程等待進(jìn)入互斥段時(shí)，信號(hào)量值為0：當(dāng)有m個(gè)進(jìn)程進(jìn)入互斥段且有一個(gè)進(jìn)程等待進(jìn)入互斥段時(shí)，信號(hào)量值為一1：最多可能有n一m個(gè)進(jìn)程等待進(jìn)入互斥段，故此時(shí)信號(hào)量的值應(yīng)為一(n—m)，也就是一n+m。知識(shí)點(diǎn)解析：暫無(wú)解析2、假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。(1)下面所示的序列中哪些是合法的?A．IOIIOIOOB．IOOIOIIOC．IIIOIOIOD．IIIOOIOO(2)通過(guò)對(duì)(1)的分析，寫(xiě)出一個(gè)算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false(假定被判定的操作序列已存入一維數(shù)組中)。標(biāo)準(zhǔn)答案：(1)A和D是合法序列，B和C是非法序列。(2)設(shè)被判定的操作序列已存入一維數(shù)組A中。intJudge(charA[]){／／判斷字符數(shù)組A中的輸入／輸出序列是否是合法序列。如是，返回true，／／否則返回falseinti=0；／／i為下標(biāo)intj=k=0;／／j和k分別為I和字母0的個(gè)數(shù)while(A[i]!=’＼0’){switch(A[i]){case’I’：j++；break；／／入棧次數(shù)增1case’0’；k++；if(k＞j){printf(”序列非法＼n”)；exit(0)；}}i++i／／不論A[i]是’I’或’0’，指針i均后移}if(j!=k){printf(”序列非法＼n”)；return(false)；}else{printf(”序列合法＼n”)；return(true)：}}}提示：在入棧出棧序列(即由’I’和’0’組成的字符串)的任一位置，入棧次數(shù)(’I’的個(gè)數(shù))都必須大于等于出棧次數(shù)(即’0’的個(gè)數(shù))，否則視作非法序列，立即給出信息，退出算法。整個(gè)序列(即讀到字符數(shù)組中字符串的結(jié)束標(biāo)記‘＼0’)，入棧次數(shù)必須等于出棧次數(shù)(題目中要求棧的初態(tài)和終態(tài)都為空)，否則視為非法序列。知識(shí)點(diǎn)解析：暫無(wú)解析3、假設(shè)一棵平衡二叉樹(shù)的每個(gè)結(jié)點(diǎn)都標(biāo)明了平衡因子b，試設(shè)計(jì)一個(gè)算法，求平衡二叉樹(shù)的高度。標(biāo)準(zhǔn)答案：因?yàn)槎鏄?shù)各結(jié)點(diǎn)已標(biāo)明了平衡因子b，故從根結(jié)點(diǎn)開(kāi)始記樹(shù)的層次。根結(jié)點(diǎn)的層次為1，每下一層，層次加1，直到層數(shù)最大的葉子結(jié)點(diǎn)，這就是平衡二叉樹(shù)的高度。當(dāng)結(jié)點(diǎn)的平衡因子b為0時(shí)，任選左右一分支向下查找，若b不為0，則沿左(當(dāng)b=1時(shí))或右(當(dāng)b=一1時(shí))向下查找。intHeight(BSTreet){／／求平衡二叉樹(shù)t的高度intlevel=0：BSTreep=t；while(P){level++：／／樹(shù)的高度增1if(p-＞bf＜0)P=p-＞rchild；／／bf=一1沿右分支向下／／bf是平衡因子，是二叉樹(shù)t結(jié)點(diǎn)的一個(gè)域，因篇幅所限，沒(méi)有寫(xiě)出其存儲(chǔ)定義elseP=P一＞lchild：／／bf＞=0沿左分支向下}／／whilereturn(level)：／／平衡二叉樹(shù)的高度}／／算法結(jié)束知識(shí)點(diǎn)解析：暫無(wú)解析4、對(duì)于一個(gè)B類IP地址，網(wǎng)絡(luò)號(hào)為129．250．0．0。如果將其分配給一個(gè)單位所用，單位內(nèi)有3000臺(tái)機(jī)器，分布在15個(gè)不同的地點(diǎn)。如選用子網(wǎng)掩碼為255．255．255．0，設(shè)計(jì)整個(gè)網(wǎng)絡(luò)的IP地址分配方案，并給出每個(gè)子網(wǎng)的IP地址表示范圍。標(biāo)準(zhǔn)答案：(1)計(jì)算各個(gè)子網(wǎng)中的主機(jī)個(gè)數(shù)，3000／15=200，平均每個(gè)地點(diǎn)200臺(tái)機(jī)器。如選255．255．255．0為掩碼，則每個(gè)網(wǎng)絡(luò)所連主機(jī)數(shù)=28-2=254＞200，共有子網(wǎng)數(shù)=28-2=254＞16，能滿足實(shí)際需求。(2)可給每個(gè)地點(diǎn)分配如下子網(wǎng)號(hào)碼：地點(diǎn)子網(wǎng)號(hào)(subnet-id)子網(wǎng)網(wǎng)絡(luò)號(hào)主機(jī)IP的范圍100000001129．250．1．0129．250．1．1—129．250．1．254200000010129．250．2．0129．250．2．1～129．250．2．254300000011129．250．3．0129．250．3．1—129．250．3．254400000100129．250．4．0129．250．4．1～129．250．4．254500000101129．250．5．0129．250．5．1—129．250．5．254600000110129．250．6．0129．250．6．1—129．250．6．254700000111129．250．7．0129．250．7．1～129．250．7．254800001000129．250．8．0129．250．8．1—129．250．8．254900001001129．250．9．0129．250．9．1—129．250．9．2541000001010129．250．10．0129．250．10．1—129．250．10．2541100001011129．250．11．0129．250．11．1～129．250．11．2541200001100129．250．12．0129．250．12．1～129．250．12．2541300001101129．250．13．0129．250．13．1—129．250．13．2541400001110129．250．14．0129．250．14．1—129．250．14．2541500001111129．250．15．0129．250．15．1—129．250．15．2541600010000129．250．16．0129．250．16．1—129．250．16．254知識(shí)點(diǎn)解析：暫無(wú)解析5、在TCP的擁塞控制中，慢開(kāi)始和擁塞避免算法是怎樣使用的?標(biāo)準(zhǔn)答案：慢開(kāi)始：在主機(jī)剛剛開(kāi)始發(fā)送報(bào)文段時(shí)可先將擁塞窗口cwnd設(shè)置為一個(gè)最大報(bào)文段MSS的數(shù)值。在每收到一個(gè)對(duì)新的報(bào)文段的確認(rèn)后，將擁塞窗口增加至多一個(gè)MSS的數(shù)值。用這樣的方法逐步增大發(fā)送端的擁塞窗口cwnd，可以使分組注入網(wǎng)絡(luò)的速率更加合理。擁塞避免：當(dāng)擁塞窗口值大于慢開(kāi)始門(mén)限時(shí)，停止使用慢開(kāi)始算法而改用擁塞避免算法。擁塞避免算法使發(fā)送端的擁塞窗口每經(jīng)過(guò)一個(gè)往返時(shí)延RTT就增加一個(gè)MSS的大小。知識(shí)點(diǎn)解析：暫無(wú)解析6、現(xiàn)有一個(gè)三段的指令流水線，各段經(jīng)過(guò)時(shí)間依次為△t，2△t，△t。請(qǐng)畫(huà)出該流水線連續(xù)處理三條不相關(guān)指令的時(shí)空?qǐng)D，并計(jì)算流水線的吞吐率、加速比和效率。標(biāo)準(zhǔn)答案：時(shí)空?qǐng)D如圖所示。流水線的吞吐翠Tp=3÷8×100％=37．5％加速比=(4×3)÷8=1．5效率E=(4×3)÷(8x3)×100％=50％知識(shí)點(diǎn)解析：暫無(wú)解析7、設(shè)有一個(gè)雙鏈表L，每個(gè)結(jié)點(diǎn)中除有prior、data和next這3個(gè)域外，還有一個(gè)訪問(wèn)頻度域freq，在鏈表被啟用之前，其值均初始化為零。每當(dāng)在鏈表進(jìn)行一次LocateNode(L，x)運(yùn)算時(shí)，令元素值為x的結(jié)點(diǎn)中freq域的值加1，并調(diào)整表中結(jié)點(diǎn)的次序，使其按訪問(wèn)頻度的遞減排列，以便使頻繁訪問(wèn)的結(jié)點(diǎn)總是靠近表頭。試寫(xiě)一符合上述要求的LocateNode運(yùn)算的算法。標(biāo)準(zhǔn)答案：typedefstructDuLNode{ElemTypedata；intfreq；structDuLNode*pred，*next；}*DList；DListlocate(DListL，ElemTypex){／／L是帶頭結(jié)點(diǎn)的按訪問(wèn)頻度遞減的雙向鏈表DListp=L一>next，q；／／p為L(zhǎng)表的工作指針，q為P的前驅(qū)，用于查找插入位置while(P&&p->data!=x)p=p一>next；／／查找值為x的結(jié)點(diǎn)if(!P){printf(”不存在所查結(jié)點(diǎn)＼n”)；exit(O)；}else{p一>freq++；／／令元素值為x的結(jié)點(diǎn)的freq域加1p->next->pred=p->pred：／／將P結(jié)點(diǎn)從鏈表上摘下p一>pred一>next。p一>next；q=p->pred：／／以下查找P結(jié)點(diǎn)的插入位置while(q!=L&&q一>freqfreq)q=q一>pred；p->next=q->next；q一>next一>pred=p：／／將P結(jié)點(diǎn)插入p一>pred=q；q一>next=P；}return(P)；／／返回值為x的結(jié)點(diǎn)的指針}提示：在算法中先查找數(shù)據(jù)x，查找成功時(shí)結(jié)點(diǎn)的訪問(wèn)頻度域增1，最后將該結(jié)點(diǎn)按頻度遞減插入鏈表中。知識(shí)點(diǎn)解析：暫無(wú)解析8、假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。(1)下面所示的序列中哪些是合法的?A．IOIIOIOOB．IOOIOIIOC．IIIOIOIOD．IIIOOIOO(2)通過(guò)對(duì)(1)的分析，寫(xiě)出一個(gè)算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false(假定被判定的操作序列已存入一維數(shù)組中)。標(biāo)準(zhǔn)答案：(1)A和D是合法序列，B和C是非法序列。(2)設(shè)被判定的操作序列已存入一維數(shù)組A中。intJudge(charA[]){／／判斷字符數(shù)組A中的輸入／輸出序列是否是合法序列。如是，返回true，／／否則返回falseinti=0：／／i為下標(biāo)intj=k=O；／／j和k分別為I和字母O的個(gè)數(shù)while(A[i]!=‘＼0’){switch(A[i]){case‘I’：j++；break；／／入棧次數(shù)增1case‘O’；k++；if(k>j){printf(“序列非法＼n”)；exit(0)；}}i++；／／不論A[i]是‘I’或‘O’，指針i均后移}if(j!=k){prjntf(“序列非法＼n”)；return(false)；}else{printf(“序列合法＼n”)；return(true)；}}}提示：在入棧出棧序列(即由‘I’和‘O’組成的字符串)的任一位置，入棧次數(shù)(‘I’的個(gè)數(shù))都必須大于等于出棧次數(shù)(即‘O’的個(gè)數(shù))，否則視作非法序列，立即給出信息，退出算法。整個(gè)序列(即讀到字符數(shù)組中字符串的結(jié)束標(biāo)記‘＼O’)，入棧次數(shù)必須等于出棧次數(shù)(題目中要求棧的初態(tài)和終態(tài)都為空)，否則視為非法序列。知識(shí)點(diǎn)解析：暫無(wú)解析9、雙符號(hào)位的作用是什么?它只出現(xiàn)在什么部件中?標(biāo)準(zhǔn)答案：雙符號(hào)位能容易檢查加、減運(yùn)算中的溢出情況。當(dāng)符號(hào)位相同，數(shù)值結(jié)果正確；當(dāng)符號(hào)位為01或10時(shí)，表示數(shù)值溢出。01表示兩個(gè)正數(shù)相加之和≥1的情況，通常稱數(shù)值“上溢”；10表示兩個(gè)負(fù)數(shù)相加之和小于一1的情況，通常稱為數(shù)值“下溢”。前面的1個(gè)符號(hào)位是正確的符號(hào)位。只有在算術(shù)和邏輯運(yùn)算部件中采用雙符號(hào)位。因?yàn)橹辉诎褍蓚€(gè)模4補(bǔ)碼的數(shù)值送往算術(shù)和邏輯運(yùn)算部件完成加、減運(yùn)算時(shí)，才把每個(gè)數(shù)的符號(hào)位的值同時(shí)送到算術(shù)和邏輯運(yùn)算部件的兩位符號(hào)位，所以只有在算術(shù)和邏輯運(yùn)算部件中采用雙符號(hào)位。知識(shí)點(diǎn)解析：暫無(wú)解析10、已知某8位機(jī)的主存采用半導(dǎo)體存儲(chǔ)器，地址碼為18位，若使用4K×4位RAM芯片組成該機(jī)所允許的最大主存空間，并選用模塊條的形式，問(wèn)：(1)若每個(gè)模塊條為32K×8位，共需幾個(gè)模塊條?(2)每個(gè)模塊內(nèi)共有多少片RAM芯片?(3)主存共需多少RAM芯片?CPU如何選擇各模塊條?標(biāo)準(zhǔn)答案：(1)由于主存地址碼給定18位，所以最大存儲(chǔ)空間為218=256KB，主存的最大容量為256KB。現(xiàn)每個(gè)模塊條的存儲(chǔ)容量為32KB，所以主存共需256KB÷32KB=8塊板。(2)每個(gè)模塊條的存儲(chǔ)容量為32KB，現(xiàn)使用4K×4位的RAM芯片拼成4K×8位(共8組)，用地址碼的低12位(A0一A11)直接接到芯片地址輸入端，然后用地址的高3位(A14一A12)通過(guò)3線一8線譯碼器輸出，分別接到8組芯片的選片端。共有8×2=16個(gè)RAM。(3)據(jù)前面所得，共需8個(gè)模塊條，每個(gè)模塊條上有16片芯片，故主存共需8×16=128片RAM芯片。知識(shí)點(diǎn)解析：暫無(wú)解析11、下圖所示的處理機(jī)邏輯框圖中，有兩條獨(dú)立的總線和兩個(gè)獨(dú)立的存儲(chǔ)器。已知指令存儲(chǔ)器IM最大容量為16384字(字長(zhǎng)18位)，數(shù)據(jù)存儲(chǔ)器DM最大容量是65536字(字長(zhǎng)16位)。各寄存器均有“打入”(Rin)和“送出”(Rout)控制命令，但圖中未標(biāo)出。設(shè)處理機(jī)格式為：加法指令可寫(xiě)為“ADDx(R1)”。其功能是(AC0)+((Ri)+X)→AC1，其中((Ri)+X)部分通過(guò)尋址方式指向數(shù)據(jù)存儲(chǔ)器，現(xiàn)取Ri為Ri。試畫(huà)出ADD指令從取指令開(kāi)始到執(zhí)行結(jié)束的操作序列圖，寫(xiě)明基本操作步驟和相應(yīng)的微操作控制信號(hào)。標(biāo)準(zhǔn)答案：加法指令“ADDX(Ri)”是一條隱含指令，其中一個(gè)操作數(shù)來(lái)自AC0，另一個(gè)操作數(shù)在數(shù)據(jù)存儲(chǔ)器中，地址由通用寄存器的內(nèi)容(Ri)加上指令格式中的X量值決定，可認(rèn)為這是一種變址尋址。因此，指令周期的操作流程圖如下圖所示。相應(yīng)的微操作控制信號(hào)列在框圖外。知識(shí)點(diǎn)解析：暫無(wú)解析12、簡(jiǎn)述DMA的工作流程。標(biāo)準(zhǔn)答案：以從磁盤(pán)讀入數(shù)據(jù)為例來(lái)說(shuō)明DMA方式的工作流程：當(dāng)CPu要從磁盤(pán)讀入一數(shù)據(jù)塊時(shí)，便向磁盤(pán)控制器發(fā)送一條讀命令，該命令被送入DMA控制器的命令寄存器CR中。同時(shí)，還須發(fā)送本次要將數(shù)據(jù)讀入的內(nèi)存起始目標(biāo)地址，該地址被送入DMA控制器的內(nèi)存地址寄存器MAR中；本次要讀的字(節(jié))數(shù)則送至DMA控制器的數(shù)據(jù)計(jì)數(shù)器DC中。另外，還須將磁盤(pán)中數(shù)據(jù)讀取的源地址直接送到DMA控制器的I／O控制邏輯上。然后，啟動(dòng)DMA控制器進(jìn)行數(shù)據(jù)傳送。此后，CPU便可去處理其他任務(wù)，而整個(gè)數(shù)據(jù)傳送便由DMA控制器負(fù)責(zé)控制。當(dāng)DMA控制器已從磁盤(pán)中讀入一個(gè)字(節(jié))的數(shù)據(jù)，并送入DMA控制器的數(shù)據(jù)寄存器DR后，再挪用一個(gè)存儲(chǔ)器周期，將該字(節(jié))傳送到MAR所指示的內(nèi)存單元中。接著，便對(duì)MAR內(nèi)容加1和將DC內(nèi)容減1。若DC內(nèi)容減1后不為0，表示傳送未完，便準(zhǔn)備再傳送下一個(gè)字(節(jié))，否則，由DMA控制器發(fā)出中斷請(qǐng)求。知識(shí)點(diǎn)解析：暫無(wú)解析13、一個(gè)n×n的對(duì)稱矩陣，如果以行或列為主序存入內(nèi)存，則其容量為多少?標(biāo)準(zhǔn)答案：n(n+1)／2(壓縮存儲(chǔ))或n2(不采用壓縮存儲(chǔ))。知識(shí)點(diǎn)解析：暫無(wú)解析14、試設(shè)計(jì)一算法，使得在盡可能少的時(shí)間內(nèi)重排數(shù)組，將所有取負(fù)值的關(guān)鍵字放在所有取非負(fù)值的關(guān)鍵字之前，并分析算法的時(shí)間復(fù)雜度。標(biāo)準(zhǔn)答案：采用類似于快速排序中的劃分思想。算法如下：voidpart(KeyTypeA[]，intn){inti=1；j=n；KeyTypetemp；while(i=0)j--；／／從右向左找負(fù)數(shù)while(i知識(shí)點(diǎn)解析：暫無(wú)解析今有4級(jí)流水線分別完成取值、指令譯碼并取數(shù)、運(yùn)算、送結(jié)果四步操作，現(xiàn)假設(shè)完成各步操作的時(shí)間依次為100ns，100ns，80ns，50ns。請(qǐng)回答下列問(wèn)題：15、流水線的操作周期應(yīng)設(shè)計(jì)為多少?標(biāo)準(zhǔn)答案：流水線的操作時(shí)鐘周期t按四步操作中最長(zhǎng)時(shí)間來(lái)考慮，所以t=100ns。知識(shí)點(diǎn)解析：暫無(wú)解析16、若相鄰兩條指令發(fā)生數(shù)據(jù)相關(guān)，而且在硬件上不采取措施，那么第二條指令要推遲多少時(shí)間進(jìn)行?標(biāo)準(zhǔn)答案：兩條指令發(fā)生數(shù)據(jù)相關(guān)沖突情況：ADDR1，R2，R3；R2+R3→R1SUBR4，R1，R5；R1—R5→R4兩條指令在流水線中執(zhí)行情況如下表所示。ADD指令在時(shí)鐘4時(shí)將結(jié)果寫(xiě)入寄存器堆(R1)，但SUB指令在時(shí)鐘3時(shí)讀寄存器堆(R1)。本來(lái)ADD指令應(yīng)先寫(xiě)入R1，SUB指令后讀R1，結(jié)果變成SUB指令先讀R1，ADD指令后寫(xiě)R1，因而發(fā)生兩條指令間的數(shù)據(jù)相關(guān)，如果硬件上不采取措施，第2條指令SUB至少應(yīng)推遲2個(gè)操作時(shí)鐘周期(2×100ns)。知識(shí)點(diǎn)解析：暫無(wú)解析17、如果在硬件設(shè)計(jì)上加以改進(jìn)，至少需推遲多少時(shí)間?標(biāo)準(zhǔn)答案：如果硬件上加以改進(jìn)(采取旁路技術(shù))，可推遲1個(gè)操作時(shí)鐘周期(100ns)。知識(shí)點(diǎn)解析：暫無(wú)解析18、試修改下面生產(chǎn)者一消費(fèi)者問(wèn)題解法中的錯(cuò)誤。producer;beginrepeatproduceraniteminnextp；wait(mutex)；wait(full)；buffer(in)：=nextp；signal(mutex)；untilfalse；endconsumer：beginrepeatwait(mutex)；wait(empty)；nextc：=buffer(out)；out：=out+1;signal(mutex)；consumeriteminnextc；untilfalse；end標(biāo)準(zhǔn)答案：producer；beginrepeatproduceraniteminnextp；wait(mutex)；wait(full)；／*應(yīng)為wait(empty)，而且還應(yīng)該在wait(mutex)的前面*／buffer(in)：=nextp；／木緩沖池?cái)?shù)組游標(biāo)應(yīng)前移：in：=(in+1)modn：*／signal(mutex)；／*signal(full)；*／untilfalse；endconsumer；beginrepeatwait(mutex)；wait(empty)；／*應(yīng)為wait(full)，而且還應(yīng)該在wait(mutex)的前面*／nextc：=buffer(out)；out：=out+1；／*考慮循環(huán)，應(yīng)改為：out：=(out+1)modn；*／signal(mutex)；／*signal(empty)；*／consumeriteminnextc：untilfalse；end知識(shí)點(diǎn)解析：暫無(wú)解析19、系統(tǒng)有5個(gè)進(jìn)程，其就緒時(shí)刻(指在該時(shí)刻已進(jìn)入就緒隊(duì)列)、服務(wù)時(shí)間如下表所示。分別計(jì)算采用先來(lái)先服務(wù)、短作業(yè)優(yōu)先、高響應(yīng)比優(yōu)先的平均周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間。標(biāo)準(zhǔn)答案：(1)采用先來(lái)先服務(wù)調(diào)度時(shí)，執(zhí)行作業(yè)的次序?yàn)镻1、P2、P3、P4、P5，如下表所示。(2)采用短作業(yè)優(yōu)先調(diào)度時(shí)，執(zhí)行作業(yè)的次序?yàn)镻1、P2、P5、P3、P4，如下表所示。(3)采用高響應(yīng)比優(yōu)先調(diào)度時(shí)，響應(yīng)比=響應(yīng)時(shí)間／運(yùn)行時(shí)間。在時(shí)刻0，只有進(jìn)程P1就緒，執(zhí)行P1，在時(shí)刻3結(jié)束。此時(shí)刻只有P2就緒，執(zhí)行P2，在時(shí)刻9結(jié)束。此時(shí)刻P3、P4、P5均就緒，計(jì)算它們的響應(yīng)比分別為2．25、1．6、1．5，則選擇執(zhí)行P3，在時(shí)刻13結(jié)束。此時(shí)刻P4、P5均就緒，計(jì)算它們的響應(yīng)比分別為2．4、3．5，則選擇執(zhí)行P5，在時(shí)刻15結(jié)束。此時(shí)刻只有P4就緒，執(zhí)行P4，在時(shí)刻20結(jié)束。整個(gè)執(zhí)行作業(yè)的次序?yàn)镻1、P2、P3、P5、P4，如下表所示。知識(shí)點(diǎn)解析：暫無(wú)解析20、何謂靜態(tài)鏈接、裝入時(shí)動(dòng)態(tài)鏈接和運(yùn)行時(shí)動(dòng)態(tài)鏈接?標(biāo)準(zhǔn)答案：(1)靜態(tài)鏈接是指事先進(jìn)行鏈接形成一個(gè)完整的裝入模塊，以后不再拆開(kāi)的鏈接方式。(2)裝入時(shí)動(dòng)態(tài)鏈接是指目標(biāo)模塊在裝入內(nèi)存時(shí)，邊裝入邊鏈接的鏈接方式。(3)運(yùn)行時(shí)的動(dòng)態(tài)鏈接是將某些目標(biāo)模塊的鏈接推遲到執(zhí)行時(shí)才進(jìn)行。知識(shí)點(diǎn)解析：暫無(wú)解析考研計(jì)算機(jī)專業(yè)基礎(chǔ)綜合（綜合應(yīng)用題）模擬試卷第2套一、綜合應(yīng)用題(本題共20題，每題1.0分，共20分。)1、何謂靜態(tài)鏈接、裝入時(shí)動(dòng)態(tài)鏈接和運(yùn)行時(shí)動(dòng)態(tài)鏈接?標(biāo)準(zhǔn)答案：(1)靜態(tài)鏈接是指事先進(jìn)行鏈接形成一個(gè)完整的裝入模塊，以后不再拆開(kāi)的鏈接方式。(2)裝入時(shí)動(dòng)態(tài)鏈接是指目標(biāo)模塊在裝入內(nèi)存時(shí)，邊裝入邊鏈接的鏈接方式。(3)運(yùn)行時(shí)的動(dòng)態(tài)鏈接是將某些目標(biāo)模塊的鏈接推遲到執(zhí)行時(shí)才進(jìn)行。知識(shí)點(diǎn)解析：暫無(wú)解析2、在TCP的擁塞控制中，慢開(kāi)始和擁塞避免算法是怎樣使用的?標(biāo)準(zhǔn)答案：慢開(kāi)始：在主機(jī)剛剛開(kāi)始發(fā)送報(bào)文段時(shí)可先將擁塞窗口cwnd設(shè)置為一個(gè)最大報(bào)文段MSS的數(shù)值。在每收到一個(gè)對(duì)新的報(bào)文段的確認(rèn)后，將擁塞窗口增加至多一個(gè)MSS的數(shù)值。用這樣的方法逐步增大發(fā)送端的擁塞窗口cwnd，可以使分組注入網(wǎng)絡(luò)的速率更加合理。擁塞避免：當(dāng)擁塞窗口值大于慢開(kāi)始門(mén)限時(shí)，停止使用慢開(kāi)始算法而改用擁塞避免算法。擁塞避免算法使發(fā)送端的擁塞窗口每經(jīng)過(guò)一個(gè)往返時(shí)延RTT就增加一個(gè)MSS的大小。知識(shí)點(diǎn)解析：暫無(wú)解析3、簡(jiǎn)述DMA的處理過(guò)程。標(biāo)準(zhǔn)答案：傳輸前的預(yù)處理是由CPU完成的。當(dāng)CPU執(zhí)行到讀寫(xiě)I／O設(shè)備調(diào)用語(yǔ)句時(shí)，啟動(dòng)DMA傳送過(guò)程，向DMA卡送入設(shè)備識(shí)別信號(hào)、啟動(dòng)設(shè)備，測(cè)試設(shè)備運(yùn)行狀態(tài)，送入內(nèi)存地址初值、傳送數(shù)據(jù)個(gè)數(shù)、DMA的功能控制信號(hào)等，之后，CPU繼續(xù)執(zhí)行原來(lái)程序。數(shù)據(jù)傳送在DMA卡控制下自動(dòng)完成。DMA卡向CPU發(fā)出請(qǐng)求總線使用權(quán)的信號(hào)，若總線空閑，總線控制器將送響應(yīng)回答信號(hào)給DMA卡，DMA卡取得總線使用權(quán)，清“0”DMA請(qǐng)求觸發(fā)器以撤銷(xiāo)請(qǐng)求總線的信號(hào)，并啟動(dòng)數(shù)據(jù)傳送過(guò)程。DMA在傳送過(guò)程中還要完成對(duì)內(nèi)存地址計(jì)數(shù)器和數(shù)據(jù)數(shù)量計(jì)數(shù)器的計(jì)數(shù)操作，并通過(guò)檢查數(shù)據(jù)數(shù)量計(jì)數(shù)器是否為O來(lái)決定要啟動(dòng)下一次傳送還是結(jié)束本批全部數(shù)據(jù)的傳送過(guò)程。傳送結(jié)束處理，是由數(shù)據(jù)數(shù)量計(jì)數(shù)器的值為0引發(fā)的。當(dāng)數(shù)據(jù)數(shù)量計(jì)數(shù)器的值為0時(shí)，DMA將向CPU發(fā)出中斷請(qǐng)求信號(hào)，CPU響應(yīng)這一請(qǐng)求后，轉(zhuǎn)入中斷服務(wù)程序，檢查是否結(jié)束數(shù)據(jù)傳送。知識(shí)點(diǎn)解析：暫無(wú)解析4、一個(gè)n×n的對(duì)稱矩陣，如果以行或列為主序存入內(nèi)存，則其容量為多少?標(biāo)準(zhǔn)答案：n(n+1)／2(壓縮存儲(chǔ))或n2(不采用壓縮存儲(chǔ))。提示：此問(wèn)題考查的知識(shí)點(diǎn)是數(shù)組的存放問(wèn)題。對(duì)稱矩陣可以只存上三角或下三角。所用空間為1，2，3，…，n之和。知識(shí)點(diǎn)解析：暫無(wú)解析5、判斷括號(hào)是否匹配是棧的主要應(yīng)用之一。設(shè)字符表達(dá)式存儲(chǔ)在數(shù)組E[n]中，‘#’為字符表達(dá)式的結(jié)束符。給出一個(gè)算法，用于判斷表達(dá)式中括號(hào)(’(’和’)’)是否配對(duì)。要求：(1)給出算法的基本設(shè)計(jì)思想。(2)根據(jù)設(shè)計(jì)思想，采用C或C++或Java語(yǔ)言描述算法，關(guān)鍵之處給出注釋。標(biāo)準(zhǔn)答案：(1)算法的基本思想：判斷表達(dá)式中括號(hào)是否匹配，可通過(guò)棧，簡(jiǎn)單說(shuō)是左括號(hào)時(shí)進(jìn)棧，右括號(hào)時(shí)退棧。退棧時(shí)，若棧頂元素是左括號(hào)，則新讀入的右括號(hào)與棧頂左括號(hào)就可消去。如此下去，輸入表達(dá)式結(jié)束時(shí)，棧為空則正確，否則括號(hào)不匹配。在讀入表達(dá)式結(jié)束符’#’時(shí)，棧中若只?！?’，表示括號(hào)全部配對(duì)成功；否則表示括號(hào)不匹配。另外，由于本題只是檢查括號(hào)是否匹配，故對(duì)從表達(dá)式中讀入的不是括號(hào)的那些字符，一律未作處理。因假設(shè)棧容量足夠大，因此入棧時(shí)未判斷溢出。(2)算法的設(shè)計(jì)如下：intexyx(charE[]，intn){／／判斷表達(dá)式中圓括號(hào)是否匹配chars[30]；／／s是一維數(shù)組，容量足夠大，用作存放括號(hào)的棧inttop=0；／／top用作棧頂指針s[top]=’#’；／／’#’先入棧，用于和表達(dá)式結(jié)束符號(hào)’#’匹配inti=0；／／字符數(shù)組E的工作指針while(E[i]!=’#’)／／逐字符處理字符表達(dá)式的數(shù)組switch(E[i]){case’(’：s[++top]=’(’；i++；break；case’)’：if(s[top]==’(’){top一一；i++；break；}else{printf(”括號(hào)不配對(duì)”)；exit(0)；}case’#’：if(s[top]==’#’){printf(”括號(hào)配對(duì)＼n”)；return(1)：}else{printf(”括號(hào)不配對(duì)＼n”)；return(0)；}／／括號(hào)不配對(duì)default：i++；／／讀入其他字符，不作處理}}知識(shí)點(diǎn)解析：暫無(wú)解析6、假定用兩個(gè)一維數(shù)組L[N]和R[N]作為有N個(gè)結(jié)點(diǎn)1，2，…，N的二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)。L[i]和R[i]分別指示結(jié)點(diǎn)i的左兒子和右兒子；L[i]=0(R[i]=0)表示i的左(右)兒子為空。試寫(xiě)一個(gè)算法，由L和R建立一個(gè)一維數(shù)組T[n]，使T[i]存放結(jié)點(diǎn)i的父親；然后再寫(xiě)一個(gè)判別結(jié)點(diǎn)U是否為結(jié)點(diǎn)V的后代的算法。標(biāo)準(zhǔn)答案：由指示結(jié)點(diǎn)i左兒子和右兒子的兩個(gè)一維數(shù)組L[i]和R[i]，很容易建立指示結(jié)點(diǎn)i的雙親的一維數(shù)組T[i]，根據(jù)T數(shù)組，判斷結(jié)點(diǎn)U是否是結(jié)點(diǎn)V后代的算法轉(zhuǎn)為判斷結(jié)點(diǎn)V是否是結(jié)點(diǎn)U的祖先的問(wèn)題。intGener|ation(intU，V，N，L[]，R[]，T[]){／／L[]和R[]是含有N個(gè)元素且指示二叉樹(shù)結(jié)點(diǎn)i左兒子和右兒子的一維數(shù)組／／本算法據(jù)此建立結(jié)點(diǎn)i的雙親數(shù)組T，并判斷結(jié)點(diǎn)U是否是結(jié)點(diǎn)V的后代inti：for(i=1；i<=N；i++)T[i]=0；／／T數(shù)組初始化for(i=1；i<=N；i++)／／根據(jù)L和R填寫(xiě)Tif(L[i]!=0)T[L[i]]=i；／／若結(jié)點(diǎn)i的左子女是L，則結(jié)點(diǎn)L的雙親是結(jié)點(diǎn)ifor(i=1；i<=N；i++)if(R[i]!=0)T[R[i]]=i；／／i的右子女是R，則R的雙親是iintparent=U；／／判斷U是否是V的后代while(parent!=V&&parent!=0)parent=T[parent]；if(parent==V){printf(“結(jié)點(diǎn)u是結(jié)點(diǎn)V的后代”)；return(1)；}else{printf(“結(jié)點(diǎn)U不是結(jié)點(diǎn)V的后代”)；return(0)；}}／／結(jié)束Generation知識(shí)點(diǎn)解析：暫無(wú)解析7、畫(huà)出如下圖所示的二叉樹(shù)所對(duì)應(yīng)的森林。標(biāo)準(zhǔn)答案：該二叉樹(shù)所對(duì)應(yīng)的森林如下圖所示，它由四棵樹(shù)組成。知識(shí)點(diǎn)解析：暫無(wú)解析8、某計(jì)算機(jī)主存容量為4M×16位，且存儲(chǔ)字長(zhǎng)與指令字長(zhǎng)相等，若該機(jī)指令系統(tǒng)可完成108種操作，操作碼位數(shù)固定，且有直接、變址、基址、相對(duì)、立即5種尋址方式，試回答：(1)畫(huà)出一地址指令格式并指出各字段的作用。(2)該指令直接尋址的最大范圍。(3)一次間址和多次間址的尋址范圍。(4)立即數(shù)的范圍(十進(jìn)制表示)。(5)相對(duì)尋址的位移量(十進(jìn)制表示)。(6)上述5種尋址方式的指令哪一種執(zhí)行時(shí)間最短?哪一種最長(zhǎng)?為什么?哪一種便于程序的浮動(dòng)?哪一種最適合處理數(shù)組問(wèn)題?(7)如何修改指令格式，使指令的尋址范圍可擴(kuò)大到4M?(8)為使一條轉(zhuǎn)移指令能夠轉(zhuǎn)移到主存的任一位置，可采取什么措施?標(biāo)準(zhǔn)答案：(1)27=128>108條指令，23=8>6種尋址方式。(2)直接尋址范圍26=64。(3)一次間址和多次間址的尋址范圍都是64K。(4)立即數(shù)范圍0～63。(5)位移量為一32～+31。(6)立即尋址執(zhí)行時(shí)間最短，因?yàn)椴僮鲾?shù)在指令中；多次間址時(shí)間最長(zhǎng)，因?yàn)橐啻卧L問(wèn)內(nèi)存。(7)4M=222，將指令字長(zhǎng)擴(kuò)展為2字節(jié)即32位。(8)可使用8086的段尋址，即可用段間尋址。知識(shí)點(diǎn)解析：暫無(wú)解析9、某多道程序設(shè)計(jì)系統(tǒng)配有一臺(tái)處理器和兩臺(tái)外設(shè)101、102，現(xiàn)有3個(gè)優(yōu)先級(jí)由高到低的J1、J2、J3都已裝入了主存，它們使用資源的先后順序和占用時(shí)間分別是：J1：102(30ms)，CPU(10ms)；101(30ms)，CPU(10ms)；J2：101(20ms)，CPU(20ms)；102(40ms)；J3：CPU(30ms)，101(20ms)。處理器調(diào)度采用可搶占的優(yōu)先數(shù)算法，忽略其他輔助操作時(shí)間，回答下列問(wèn)題。(1)分別計(jì)算作業(yè)J1、J2和J3從開(kāi)始到完成所用的時(shí)間。(2)3個(gè)作業(yè)全部完成時(shí)CPU的利用率。(3)3個(gè)作業(yè)全部完成時(shí)外設(shè)101的利用率。標(biāo)準(zhǔn)答案：為了清楚地描述作業(yè)執(zhí)行情況，我們對(duì)題目假設(shè)的情況分析如下：(1)J1占用102傳輸30ms時(shí)，J1傳輸完成，搶占J2的CPU，運(yùn)行10ms，再傳輸30ms，運(yùn)行10ms，完成。J1從開(kāi)始到完成所用的時(shí)間為：30+10+30+10=80(ms)。J2與其并行地在IO1上傳輸20ms，搶占J3的CPU，J2運(yùn)行10ms后，被J1搶占CPU，等待10ms之后，J2再次得到CPU，運(yùn)行10ms，J2啟動(dòng)102傳輸，40ms完成。J2從開(kāi)始到完成所用的時(shí)間為：20+10+10+10+40=90(ms)。J3在CPU上執(zhí)行20ms，被J2搶占CPU，等待30ms，再運(yùn)行10ms，等待10ms，J3啟動(dòng)101運(yùn)行20ms的傳輸，完成。J3從開(kāi)始到完成所用的時(shí)間為20+30+10+10+20=90(ms)。(2)三個(gè)作業(yè)全部完成時(shí)，CPU的利用率為(10+20+30+10)／90=7／9=78％。(3)三個(gè)作業(yè)全部完成時(shí)，外設(shè)IO1的利用率為(20+30+20)／90=7／9=78％。知識(shí)點(diǎn)解析：暫無(wú)解析10、設(shè)有三個(gè)進(jìn)程A、B、C，進(jìn)程A和進(jìn)程B各需要運(yùn)行3ms的處理器時(shí)間，而進(jìn)程C卻要24ms的處理器時(shí)間，分別考慮當(dāng)三個(gè)進(jìn)程到達(dá)順序?yàn)锳，B，C時(shí)及C，B，A時(shí)，用先來(lái)先服務(wù)進(jìn)行調(diào)度時(shí)各自的平均等待時(shí)間。標(biāo)準(zhǔn)答案：(1)當(dāng)三個(gè)進(jìn)程到達(dá)順序?yàn)锳、B、C時(shí)，按照先來(lái)先服務(wù)的順序，進(jìn)程A先占用處理器，進(jìn)程B需等待3ms后才能去占用處理器，進(jìn)程C在等待6ms的時(shí)間后可以占用處理器。于是，它們的平均等待時(shí)間為(0+3+6)÷3=3(ms)。(2)如果進(jìn)程是按C、B、A的次序排入隊(duì)列，則進(jìn)程C先占用處理器運(yùn)行24ms后才能讓進(jìn)程B占用，即進(jìn)程B需等待24ms，而進(jìn)程A在等了27ms后才可占用處理器，現(xiàn)在這三個(gè)進(jìn)程的平均等待時(shí)間為(27+24+0)÷3=17(ms)?？梢?jiàn)當(dāng)運(yùn)行時(shí)間長(zhǎng)的進(jìn)程先就緒時(shí)，先來(lái)先服務(wù)算法使系統(tǒng)效率受到影響。知識(shí)點(diǎn)解析：暫無(wú)解析11、某操作系統(tǒng)的磁盤(pán)文件空間共有500塊，若用字長(zhǎng)為32位的位示圖管理磁盤(pán)空間，試問(wèn)：(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í)自上至下、自左至右掃描位示圖跳過(guò)為1的位，找到第一個(gè)遇到的0位，根據(jù)它是第i字第j位算出對(duì)應(yīng)塊號(hào)，并分配出去。歸還時(shí)已知塊號(hào)，塊號(hào)÷32算出第i字第j位并把位示圖相應(yīng)位清零。知識(shí)點(diǎn)解析：暫無(wú)解析12、協(xié)議與服務(wù)有何區(qū)別?標(biāo)準(zhǔn)答案：網(wǎng)絡(luò)協(xié)議：為進(jìn)行網(wǎng)絡(luò)中的數(shù)據(jù)交換而建立的規(guī)則、標(biāo)準(zhǔn)或約定。協(xié)議是控制兩個(gè)對(duì)等實(shí)體進(jìn)行通信的規(guī)則的集合。在協(xié)議的控制下，兩個(gè)對(duì)等實(shí)體間的通信使得本層能夠向上一層提供服務(wù)，而要實(shí)現(xiàn)本層協(xié)議，還需要使用下面一層提供的服務(wù)。協(xié)議和服務(wù)的概念的區(qū)分：(1)協(xié)議的實(shí)現(xiàn)保證了能夠向上一層提供服務(wù)。本層的服務(wù)用戶只能看見(jiàn)服務(wù)而無(wú)法看見(jiàn)下面的協(xié)議。下面的協(xié)議對(duì)上層的服務(wù)用戶是透明的。(2)協(xié)議是“水平的”，即協(xié)議是控制兩個(gè)對(duì)等實(shí)體進(jìn)行通信的規(guī)則。但服務(wù)是“垂直的”，即服務(wù)是由下層通過(guò)層間接口向上層提供的。上層使用所提供的服務(wù)必須與下層交換一些命令，這些命令在OSI中稱為服務(wù)原語(yǔ)。知識(shí)點(diǎn)解析：暫無(wú)解析13、并發(fā)請(qǐng)求過(guò)程中服務(wù)器的處理方案及建立傳輸連接的過(guò)程有哪些?標(biāo)準(zhǔn)答案：解決服務(wù)器處理并發(fā)請(qǐng)求的方案基本上有兩種：一是采用并發(fā)服務(wù)處理器的方法，二是采用重復(fù)服務(wù)器的方法。客戶與并發(fā)服務(wù)器建立傳輸連接的工作過(guò)程為：(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)解析：暫無(wú)解析14、設(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(LinkedList1a){／／算術(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)!=’(’){pfintf(”括號(hào)不配對(duì)＼n”)；return(0)；}elsepop(S)；break；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(StackEmpty(s)｜｜StackGetTop(s)!=’{’){printf(”括號(hào)不配對(duì)＼n”)；return(0)；}elsepop(s)；break；}P=p一>link；／／后移指針}／／whileif(StackEmpty(S)){printf(”括號(hào)配對(duì)＼n”)；return(1)；}else{printf(”括號(hào)不配對(duì)＼n”)；return(0)；}}知識(shí)點(diǎn)解析：暫無(wú)解析某計(jì)算機(jī)字長(zhǎng)為16位，存儲(chǔ)器直接尋址空間為128字，變址時(shí)的位移量為-64～+63，16個(gè)通用寄存器均可作為變址寄存器。采用擴(kuò)展操作碼技術(shù)，設(shè)計(jì)～套指令系統(tǒng)格式，滿足下列尋址類型的要求：15、直接尋址的二地址指令3條。標(biāo)準(zhǔn)答案：由題意知道是多種尋址方式，為簡(jiǎn)化指令設(shè)計(jì)，選用擴(kuò)展操作碼方式，所以要求的指令數(shù)從(1)到(5)遞增順序設(shè)計(jì)。二地址直接尋址指令的操作碼部分應(yīng)為2位，故操作碼可定義成00、01、10，總的指令長(zhǎng)度可以是操作碼2位，地址碼為7位×2字段共14位。知識(shí)點(diǎn)解析：暫無(wú)解析16、變址尋址的一地址指令6條。標(biāo)準(zhǔn)答案：一地址變址尋址指令的操作碼可從11000開(kāi)始，順序遞增到11101為止，總的指令長(zhǎng)度可以是5位操作碼，4位寄存器編碼，7位地址碼，共16位。知識(shí)點(diǎn)解析：暫無(wú)解析17、寄存器尋址二地址指令8條。標(biāo)準(zhǔn)答案：二地址寄存器尋址指令的操作碼可以從11110000開(kāi)始，順序遞增到11110111為止，總的指令長(zhǎng)度可以是8位操作碼，寄存器共2。個(gè)，地址碼為4位×2字段=8位。知識(shí)點(diǎn)解析：暫無(wú)解析18、直接尋址的一地址指令12條。標(biāo)準(zhǔn)答案：一地址直接尋址指令的操作碼部分可以從111110000開(kāi)始，順序遞增到111111011為止，總的指令長(zhǎng)度是9位操作碼，7位地址碼，共16位。知識(shí)點(diǎn)解析：暫無(wú)解析19、零地址指令32條。標(biāo)準(zhǔn)答案：零地址指令的操作碼雖可從111111100000開(kāi)始，順序遞增到111111110000，但指令總長(zhǎng)是12位，而上述其他指令的長(zhǎng)度都可為16位，所以這里將表示32種不同零地址指令的5位移動(dòng)到16位指令的最后5位，因而從1111111000000000～1111111000011111。知識(shí)點(diǎn)解析：暫無(wú)解析20、數(shù)據(jù)鏈路(即邏輯鏈路)與鏈路(即物理鏈路)有何區(qū)別?“電路接通了”與“數(shù)據(jù)鏈路接通了”的區(qū)別何在?標(biāo)準(zhǔn)答案：(1)數(shù)據(jù)鏈路與鏈路的區(qū)別在于數(shù)據(jù)鏈路除鏈路外，還必須有一些必要的規(guī)程來(lái)控制數(shù)據(jù)的傳輸。因此，數(shù)據(jù)鏈路比鏈路多了實(shí)現(xiàn)通信規(guī)程所需要的硬件和軟件。(2)“電路接通了”表示鏈路兩端的結(jié)點(diǎn)交換機(jī)已經(jīng)開(kāi)機(jī)，物理連接已經(jīng)能夠傳送比特流了。但是，“電路接通了”不表示能進(jìn)行數(shù)據(jù)傳輸。在物理連接基礎(chǔ)上，再建立數(shù)據(jù)鏈路連接，才是“數(shù)據(jù)鏈路接通了”。此后，由于數(shù)據(jù)鏈路連接具有檢測(cè)、確認(rèn)和重傳等功能，才使不大可靠的物理鏈路變成可靠的數(shù)據(jù)鏈路，進(jìn)行可靠的數(shù)據(jù)傳輸。當(dāng)數(shù)據(jù)鏈路斷開(kāi)連接時(shí)，物理電路連接不一定跟著斷開(kāi)。知識(shí)點(diǎn)解析：暫無(wú)解析考研計(jì)算機(jī)專業(yè)基礎(chǔ)綜合（綜合應(yīng)用題）模擬試卷第3套一、綜合應(yīng)用題(本題共20題，每題1.0分，共20分。)1、試述分頁(yè)存儲(chǔ)管理的基本實(shí)現(xiàn)原理，并說(shuō)明如何實(shí)現(xiàn)從邏輯空間到物理空間的變換?標(biāo)準(zhǔn)答案：(1)實(shí)現(xiàn)原理。等分主存：把主存的存儲(chǔ)空間劃分成大小相等的片。用戶邏輯地址空間的分頁(yè)：把用戶的邏輯地址空間(虛地址空間)劃分成若干個(gè)與存儲(chǔ)塊大小相等的片，稱為頁(yè)面或頁(yè)(Page)。邏輯地址的表示：在分頁(yè)系統(tǒng)中，每個(gè)虛擬地址(相對(duì)地址)用一個(gè)數(shù)對(duì)(p，d)來(lái)表示。其中p是頁(yè)號(hào)，d是該虛擬地址在頁(yè)面號(hào)為p的頁(yè)中的相對(duì)地址，稱為頁(yè)內(nèi)地址(位移量)。主存分配原則：在分頁(yè)情況下，系統(tǒng)以存儲(chǔ)塊為單位把主存分給作業(yè)或進(jìn)程，并且分給一個(gè)作業(yè)的各存儲(chǔ)塊不一定是相鄰和連續(xù)的。進(jìn)程或作業(yè)的一個(gè)頁(yè)面裝入系統(tǒng)分給的某個(gè)存儲(chǔ)塊中，所以頁(yè)面與存儲(chǔ)塊對(duì)應(yīng)。頁(yè)表和頁(yè)表地址寄存器：為了便于管理和保護(hù)，系統(tǒng)為每個(gè)裝入主存的作業(yè)建立一張相應(yīng)的頁(yè)表，一旦這個(gè)作業(yè)被調(diào)度執(zhí)行，把它的頁(yè)表始址及大小裝入特定的頁(yè)表寄存器中。(2)作業(yè)執(zhí)行過(guò)程中CPU產(chǎn)生的每一個(gè)邏輯地址，由硬件地址變換機(jī)構(gòu)自動(dòng)將其分成兩部分，一部分為頁(yè)號(hào)，另一部分是頁(yè)內(nèi)位移量。如果頁(yè)表訪問(wèn)是合法的，則由頁(yè)表始址和頁(yè)號(hào)計(jì)算出所對(duì)應(yīng)的物理塊號(hào)：將物理塊號(hào)與邏輯地址中的位移量拼接，形成最終訪問(wèn)的物理地址。知識(shí)點(diǎn)解析：暫無(wú)解析2、從鍵盤(pán)上輸入一個(gè)逆波蘭表達(dá)式，用偽碼寫(xiě)出其求值程序。規(guī)定：逆波蘭表達(dá)式的長(zhǎng)度不超過(guò)一行，以$符作為輸入結(jié)束，操作數(shù)之間用空格分隔，操作符只可能有+、一、*、／四種運(yùn)算，例如：234—34+2*$。標(biāo)準(zhǔn)答案：逆波蘭表達(dá)式(即后綴表達(dá)式)求值規(guī)則如下：設(shè)立運(yùn)算數(shù)棧OPND，對(duì)表達(dá)式從左到右掃描(讀入)，當(dāng)表達(dá)式中掃描到數(shù)時(shí)，壓入OPND棧。當(dāng)掃描到運(yùn)算符時(shí)，從OPND退出兩個(gè)數(shù)，進(jìn)行相應(yīng)運(yùn)算，結(jié)果再壓入OPND棧。這個(gè)過(guò)程一直進(jìn)行到讀出表達(dá)式結(jié)束符$，這時(shí)OPND棧中只有一個(gè)數(shù)，就是結(jié)果。floatexpr(){／／從鍵盤(pán)輸入逆波蘭表達(dá)式，以’$’表示輸入結(jié)束，本算法求逆波蘭表達(dá)式的值floatOPND[30]；／／OPND是操作數(shù)棧init(OPND)：／／兩棧初始化floatnum=0．0：／／數(shù)字初始化scanf(”％C”，&x)；／／x是字符型變量while(X!=’$’){switch(x){case’0’：case’1’：caSe’2’：case’3’：case’4’：case’5’：case’6’：case’7’：case’8’：caSe’9’：while((x＞=’0’&&x＜=’9’)||X==．’)／／拼數(shù)if(X!=’．’){num=num*10+(ord(X)-ord(’0’))；scanf(”％c”，&x)；}／／處理整數(shù)else{／／處理小數(shù)部分scale=10．0：scanf(”％c”，&x)；while(x＞=’0’&&x＜=’9’){num=num+(ord(X)一ord(’0’))／scale：scale=scale*10；scanf(”％c”，&x)；}}／／elsepush(OPND，num)；num=0．0；／／數(shù)壓入棧，下個(gè)數(shù)初始化case’’：break：／／遇空格，繼續(xù)讀下一個(gè)字符case’+’：push(OPND，pop(OPND)+pop(OPND))；break；case’一’：xl=pop(OPND)；x2=pop(OPND)；push(OPND，x2一x1)；break；case’*’：push(OPND，pop(OPND)*pop(OPND))：break；case’／’：xl：pop(OPND)；x2=pop(OPND)；push(OPND，x2／x1)；break；default：／／其他符號(hào)不作處理}／／結(jié)束switchscanf(”％c”，＆x)；／／讀入表達(dá)式中下一個(gè)字符}／／結(jié)束while(x!=’$’)prinff("后綴表達(dá)式的值為％f")；pop(OPND)；}知識(shí)點(diǎn)解析：暫無(wú)解析3、已知某網(wǎng)絡(luò)中路由器A的路由表如下：如果此時(shí)該路由器收到路由器C發(fā)來(lái)的信息：給出該路由器更新后的路由表。標(biāo)準(zhǔn)答案：路由器A更新后的路由表如下：(1)對(duì)于網(wǎng)絡(luò)1，新的路由信息中給出了不同的下一跳，距離更短，需要作出改變。(2)對(duì)于網(wǎng)絡(luò)2，新的路由信息中給出了不同的下一跳，距離一樣，不變。(3)對(duì)于網(wǎng)絡(luò)3，新的路由信息中給出了不同的下一跳，距離更大，不改變。(4)對(duì)于網(wǎng)絡(luò)4，新的路由信息中沒(méi)有給出新信息，不改變。知識(shí)點(diǎn)解析：暫無(wú)解析4、設(shè)某機(jī)有5級(jí)中斷L0、L1、L2、L3、L4，其中斷響應(yīng)優(yōu)先次序?yàn)長(zhǎng)0最高、L1次之、…、L4最低?，F(xiàn)在要求將中斷處理次序改為L(zhǎng)1→L3→L0→L4→L2，試問(wèn)：(1)下表中各級(jí)中斷處理程序的各中斷級(jí)屏蔽值如何設(shè)置(每級(jí)對(duì)應(yīng)一位，該位為“0”表示允許中斷，該位為“1”表示中斷屏蔽)?(2)若這5級(jí)中斷同時(shí)都發(fā)出中斷請(qǐng)求，按更改后的次序畫(huà)出進(jìn)入各級(jí)中斷處理程序的過(guò)程示意圖。標(biāo)準(zhǔn)答案：(1)中斷處理程序如下：(2)示意圖如下：知識(shí)點(diǎn)解析：暫無(wú)解析5、假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。(1)下面所示的序列中哪些是合法的?A．IOIIOIOOB．IOOIOIIOC．IIIOIOIOD．IIIOOIOO(2)通過(guò)對(duì)(1)的分析，寫(xiě)出一個(gè)算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false(假定被判定的操作序列已存入一維數(shù)組中)。標(biāo)準(zhǔn)答案：(1)A和D是合法序列，B和C是非法序列。(2)設(shè)被判定的操作序列已存入一維數(shù)組A中。intJudge(charA[]){／／判斷字符數(shù)組A中的輸入／輸出序列是否是合法序列。如是，返回true，／／否則返回falseinti=0：／／i為下標(biāo)intj=k=O；／／j和k分別為I和字母O的個(gè)數(shù)while(A[i]!=‘＼0’){switch(A[i]){case‘I’：j++；break；／／入棧次數(shù)增1case‘O’；k++；if(k>j){printf(“序列非法＼n”)；exit(0)；}}i++；／／不論A[i]是‘I’或‘O’，指針i均后移}if(j!=k){prjntf(“序列非法＼n”)；return(false)；}else{printf(“序列合法＼n”)；return(true)；}}}提示：在入棧出棧序列(即由‘I’和‘O’組成的字符串)的任一位置，入棧次數(shù)(‘I’的個(gè)數(shù))都必須大于等于出棧次數(shù)(即‘O’的個(gè)數(shù))，否則視作非法序列，立即給出信息，退出算法。整個(gè)序列(即讀到字符數(shù)組中字符串的結(jié)束標(biāo)記‘＼O’)，入棧次數(shù)必須等于出棧次數(shù)(題目中要求棧的初態(tài)和終態(tài)都為空)，否則視為非法序列。知識(shí)點(diǎn)解析：暫無(wú)解析6、計(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ù)。它們是通過(guò)總線連接在一起的，其中總線包括數(shù)據(jù)總線、地址總線和控制總線。知識(shí)點(diǎn)解析：暫無(wú)解析7、假設(shè)程序PA和PB單獨(dú)執(zhí)行時(shí)所需的時(shí)間分別用TA和TB表示，并且假設(shè)TA=1h，TB=1．5h，其中處理器工作時(shí)間分別為T(mén)A=18min，TB=27min，如果采用多道程序設(shè)計(jì)方法，讓PA和PB并行工作，假定處理器利用率達(dá)到50％，系統(tǒng)開(kāi)銷(xiāo)為15min，請(qǐng)問(wèn)系統(tǒng)效率能提高多少?標(biāo)準(zhǔn)答案：(1)在串行情況下，兩個(gè)程序運(yùn)行時(shí)間共計(jì)2．5h；在并行方式下，處理器利用率為50％，說(shuō)明處理器的工作時(shí)間占總運(yùn)行時(shí)間的50％。根據(jù)已知條件，“處理器工作時(shí)間分別為T(mén)A=18rain，TB=27min”，即總運(yùn)行時(shí)間為(18+27)÷50％(min)，考慮到還有15min系統(tǒng)開(kāi)銷(xiāo)，故并行與串行的效率比為并行處理所需的時(shí)間÷串行處理所需要的時(shí)間總和=[(18+27)÷50％+15]÷2．5÷60=70％。(2)即采用多道處理技術(shù)之后，完成程序PA和程序PB所需的時(shí)間為串行處理方法的70％。因此可以說(shuō)效率提高了30％。知識(shí)點(diǎn)解析：暫無(wú)解析8、為使用戶進(jìn)程互斥地進(jìn)入臨界區(qū)，可以把整個(gè)臨界區(qū)實(shí)現(xiàn)成不可中斷的過(guò)程，即用戶有屏蔽所有中斷的能力。每當(dāng)用戶程序進(jìn)入臨界區(qū)的時(shí)候，屏蔽所有中斷；當(dāng)出了臨界區(qū)的時(shí)候，再開(kāi)放所有中斷。你認(rèn)為這種方法有什么缺點(diǎn)?標(biāo)準(zhǔn)答案：此題主要考查中斷概念在操作系統(tǒng)設(shè)計(jì)過(guò)程中的重要作用與臨界區(qū)的概念。用戶進(jìn)程進(jìn)入臨界區(qū)時(shí)屏蔽所有中斷，包括系統(tǒng)程序的中斷。假如屏蔽的是用戶進(jìn)程，確實(shí)可以保護(hù)臨界資源，但如果連系統(tǒng)所發(fā)出的中斷也被屏蔽的話，就會(huì)引起系統(tǒng)錯(cuò)誤。雖然系統(tǒng)外中斷往往與當(dāng)前運(yùn)行的程序無(wú)關(guān)，但如果是一些重要的硬件中斷，如電源故障等，就可能會(huì)引起錯(cuò)誤，故不可盲目屏蔽所有中斷。知識(shí)點(diǎn)解析：暫無(wú)解析9、什么是地址重定位?怎樣區(qū)分靜態(tài)重定位和動(dòng)態(tài)重定位?各有什么優(yōu)缺點(diǎn)?標(biāo)準(zhǔn)答案：(1)地址重定位：把作業(yè)地址空間中使用的邏輯地址變換成主存中物理地址的過(guò)程。(2)靜態(tài)重定位是在程序運(yùn)行之前由裝配程序完成的，動(dòng)態(tài)重定位是在程序執(zhí)行過(guò)程中由硬件地址變換機(jī)構(gòu)實(shí)現(xiàn)的。(3)靜態(tài)重定位的主要優(yōu)點(diǎn)是，無(wú)須增加硬件地址變換機(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ǔ)量超過(guò)可用存儲(chǔ)空間，用戶必須考慮覆蓋結(jié)構(gòu)。第三，用戶之間難以共享主存中的同一程序副本。(5)動(dòng)態(tài)重定位的主要優(yōu)點(diǎn)有：第一，用戶作業(yè)不要求分配連續(xù)的存儲(chǔ)空間。第二，用戶作業(yè)在執(zhí)行過(guò)程中可以動(dòng)態(tài)申請(qǐng)存儲(chǔ)空間和在主存中移動(dòng)。第三，有利于程序段的共享。(6)動(dòng)態(tài)重定位的主要缺點(diǎn)有：第一，需要附加的硬件支持。第二，實(shí)現(xiàn)存儲(chǔ)管理的軟件算法比較復(fù)雜。知識(shí)點(diǎn)解析：暫無(wú)解析10、請(qǐng)求分頁(yè)和簡(jiǎn)單分頁(yè)兩種存儲(chǔ)管理方案有何不同?缺頁(yè)中斷是如何發(fā)生的?發(fā)生缺頁(yè)中斷時(shí)如何處理?標(biāo)準(zhǔn)答案：(1)請(qǐng)求頁(yè)式管理在作業(yè)或進(jìn)程開(kāi)始執(zhí)行之前，不要求把作業(yè)或進(jìn)程的程序段和數(shù)據(jù)段一次性地全部裝入主存，而只把當(dāng)前需要的一部分頁(yè)面裝入主存，其他部分在作業(yè)執(zhí)行過(guò)程中需要時(shí)再?gòu)妮o存上調(diào)入主存。(2)當(dāng)調(diào)用頁(yè)不在主存時(shí)發(fā)生缺頁(yè)中斷。若主存中沒(méi)有空閑塊時(shí)，首先按照某種策略選擇某頁(yè)進(jìn)行淘汰，以騰出空閑塊供本次調(diào)入的頁(yè)占用。若被選中淘汰的頁(yè)面中的信息修改過(guò)(修改位=1)還必須將其寫(xiě)入輔存。如主存中有空閑塊，則根據(jù)該頁(yè)在輔存的地址調(diào)入所需頁(yè)面，并更新頁(yè)表，最后恢復(fù)被中斷的指令重新執(zhí)行。知識(shí)點(diǎn)解析：暫無(wú)解析11、一個(gè)完整的計(jì)算機(jī)網(wǎng)絡(luò)的定義應(yīng)包含哪些內(nèi)容?標(biāo)準(zhǔn)答案：(1)物理結(jié)構(gòu)：通過(guò)通信線路、通信設(shè)備將地理上分散的計(jì)算機(jī)連成一個(gè)整體。(2)邏輯結(jié)構(gòu)：在網(wǎng)絡(luò)協(xié)議控制下進(jìn)行信息傳輸。(3)主要目的：資源共享。知識(shí)點(diǎn)解析：暫無(wú)解析12、試述五層協(xié)議的網(wǎng)絡(luò)體系結(jié)構(gòu)的要點(diǎn)，包括各層的主要功能。標(biāo)準(zhǔn)答案：所謂五層協(xié)議的網(wǎng)絡(luò)體系結(jié)構(gòu)是為便于學(xué)習(xí)計(jì)算機(jī)網(wǎng)絡(luò)原理而采用的綜合了OSI七層模型和TCP／IP四層模型而得到的五層模型。五層協(xié)議的體系結(jié)構(gòu)如下圖所示：各層的主要功能如下：(1)應(yīng)用層：確定進(jìn)程之間通信的性質(zhì)以滿足用戶的需要。應(yīng)用層不僅要提供應(yīng)用進(jìn)程所需要的信息交換和遠(yuǎn)程操作，而且還要作為互相作用的應(yīng)用進(jìn)程的用戶代理，來(lái)完成一些為進(jìn)行語(yǔ)義上有意義的信息交換所必需的功能。(2)傳輸層：任務(wù)是負(fù)責(zé)主機(jī)中兩個(gè)進(jìn)程間的通信。(3)網(wǎng)絡(luò)層：負(fù)責(zé)為分組選擇合適的路由，使源主機(jī)傳輸層所傳下來(lái)的分組能夠交付到目的主機(jī)。(4)數(shù)據(jù)鏈路層：將在網(wǎng)絡(luò)層交下來(lái)的數(shù)據(jù)報(bào)組裝成幀，在兩個(gè)相鄰結(jié)點(diǎn)間的鏈路上實(shí)現(xiàn)幀的無(wú)差錯(cuò)傳輸。(5)物理層：透明地傳輸比特流。知識(shí)點(diǎn)解析：暫無(wú)解析13、數(shù)據(jù)鏈路層中的鏈路控制包括哪些功能?標(biāo)準(zhǔn)答案：數(shù)據(jù)鏈路層中的鏈路控制功能有：①鏈路管理。②幀定界。③流量控制。④差錯(cuò)控制。⑤將數(shù)據(jù)和控制信息區(qū)分開(kāi)。⑥透明傳輸。⑦尋址。知識(shí)點(diǎn)解析：暫無(wú)解析14、試述交換機(jī)的存儲(chǔ)轉(zhuǎn)發(fā)方式和直通轉(zhuǎn)發(fā)方式的優(yōu)缺點(diǎn)。標(biāo)準(zhǔn)答案：(1)存儲(chǔ)轉(zhuǎn)發(fā)方式：①轉(zhuǎn)發(fā)前要對(duì)幀進(jìn)行錯(cuò)誤校驗(yàn)，因此出錯(cuò)的幀不會(huì)被轉(zhuǎn)發(fā)，使帶寬不會(huì)被浪費(fèi)。②具有幀緩沖能力，因此允許在不同速率的端口之間進(jìn)行轉(zhuǎn)發(fā)操作。③幀完整地接收后才開(kāi)始執(zhí)行轉(zhuǎn)發(fā)操作，因此傳輸延遲較大，并且隨轉(zhuǎn)發(fā)幀的長(zhǎng)短而有所不同。④交換機(jī)內(nèi)的端口緩沖區(qū)的大小是有限的，當(dāng)負(fù)載較重時(shí)，幀會(huì)被丟棄，即負(fù)載較重時(shí)其性能會(huì)下降。(2)直通轉(zhuǎn)發(fā)方式：①轉(zhuǎn)發(fā)前不進(jìn)行錯(cuò)誤校驗(yàn)，因此出錯(cuò)的幀也被轉(zhuǎn)發(fā)，造成了帶寬的浪費(fèi)。②無(wú)幀緩沖能力，不能在不同速率的端口之間進(jìn)行轉(zhuǎn)發(fā)操作。③收到一幀最前面的目的地址就立即開(kāi)始執(zhí)行轉(zhuǎn)發(fā)操作，因此傳輸延遲小，并且所有幀的轉(zhuǎn)發(fā)延遲時(shí)間都是一樣的。④無(wú)丟幀現(xiàn)象。性能不會(huì)隨負(fù)載的輕重而變化。知識(shí)點(diǎn)解析：暫無(wú)解析15、假定圖G=(V，E)是有向圖，V={1，2，…，N}，N≥1，G以鄰接矩陣方式存儲(chǔ)，G的鄰接矩陣為A，即A是一個(gè)二維數(shù)組。如果i到j(luò)有邊，則A[i，j]=l，否則A[i，j]=0。請(qǐng)給出一個(gè)算法思想，該算法能判斷G是否是非循環(huán)圖(即G中是否存在回路)，要求算法的時(shí)間復(fù)雜性為O(n2)。標(biāo)準(zhǔn)答案：此題考查的知識(shí)點(diǎn)是圖的遍歷。采用深度優(yōu)先遍歷算法，在執(zhí)行DFS(v)時(shí)，若在退出DFS(v)前碰到某頂點(diǎn)v，其鄰接點(diǎn)是已經(jīng)訪問(wèn)的頂點(diǎn)v，則說(shuō)明v的子孫u有到v的回邊，即說(shuō)明有環(huán)；否則，無(wú)環(huán)。知識(shí)點(diǎn)解析：暫無(wú)解析16、寫(xiě)一個(gè)HeapInsert(R，key)算法，將關(guān)鍵字插入到堆R中，并保證插入后R仍是堆。請(qǐng)分析算法的時(shí)間復(fù)雜度。提示：將key先插入R中已有元素的尾部(即原堆的長(zhǎng)度加1的位置，插入后堆的長(zhǎng)度加1)，然后自下往上調(diào)整，使插入的關(guān)鍵字滿足堆性質(zhì)。標(biāo)準(zhǔn)答案：typedefstruct{KeyTypekey；InfoTypeotherinfo；}RecType；typedefstruct{RecTypeRec[MaxNum];／／MaxNum是一個(gè)常量intlen；}SeqList；HeapInsert(SeqListR，KeyTypekey){inti，j；R．Rec[++R．1en]．key=key；／／增加新值到原堆中已有元素的尾部且堆的長(zhǎng)度加1i=R．1en／2；j=R．len；while(i>0){／／調(diào)整為堆if(R．Rec[i]．key2R．len，調(diào)整是自底向上查找，最多查找到樹(shù)根，所以時(shí)間復(fù)雜度為O(log2R．len)。知識(shí)點(diǎn)解析：暫無(wú)解析17、網(wǎng)絡(luò)協(xié)議的三個(gè)要素是什么?備有什么含義?標(biāo)準(zhǔn)答案：網(wǎng)絡(luò)協(xié)議：為完成網(wǎng)絡(luò)通信而建立的規(guī)則、標(biāo)準(zhǔn)或約定。由以下三個(gè)要素組成：(1)語(yǔ)法：即數(shù)據(jù)與控制信息的結(jié)構(gòu)或格式。(2)語(yǔ)義：即需要發(fā)出何種控制信息，完成何種動(dòng)作以及作出何種響應(yīng)。(3)同步：即事件實(shí)現(xiàn)順序的詳細(xì)說(shuō)明。知識(shí)點(diǎn)解析：暫無(wú)解析設(shè)同一網(wǎng)絡(luò)中有四臺(tái)主機(jī)，主機(jī)1的IP地址為192．168．3．112，主機(jī)2的IP地址為192．168．3．120，主機(jī)3的IP地址為192．168．3．176，主機(jī)4的IP地址為192．168．3．222。共同的子網(wǎng)掩碼是255．255．255．224。請(qǐng)回答下列問(wèn)題：18、畫(huà)出網(wǎng)絡(luò)連接示意圖，并給出各個(gè)主機(jī)的子網(wǎng)地址和主機(jī)地址。標(biāo)準(zhǔn)答案：由于子網(wǎng)掩碼前27位為1，所以主機(jī)地址位數(shù)是5位，即每個(gè)IP地址的最后5位可以確定主機(jī)地址。網(wǎng)絡(luò)連接的示意圖如下所示：在此網(wǎng)絡(luò)中有三個(gè)子網(wǎng)：192．168．3．96網(wǎng)絡(luò)中包含了主機(jī)1和主機(jī)2；192．168．3．160中包含了主機(jī)3；192．168．3．192中包含了主機(jī)4。知識(shí)點(diǎn)解析：暫無(wú)解析19、如果需要加入第5臺(tái)主機(jī)5，使其能與主機(jī)4直接通信，其IP地址的設(shè)定范圍是多少?標(biāo)準(zhǔn)答案：由于主機(jī)5和主機(jī)4在同一個(gè)子網(wǎng)。所以主機(jī)5所在子網(wǎng)的子網(wǎng)地址為192．168．3．192。192的二進(jìn)制為11000000，最右邊5位為主機(jī)地址位數(shù)，去掉全0和全1，并且不能和主機(jī)4的IP地址192．168．3．222重復(fù)，所以其IP地址設(shè)定的范圍為192．168．3．193～192．168．3．221。知識(shí)點(diǎn)解析：暫無(wú)解析20、不改變主機(jī)1的物理地址，將其IP地址改為192．168．3．168，請(qǐng)問(wèn)它的直接廣播地址是多少?標(biāo)準(zhǔn)答案：168的二進(jìn)制為10101000，將最右邊的5位置1，即為其直接廣播地址，即192．168．3．191。知識(shí)點(diǎn)解析：暫無(wú)解析考研計(jì)算機(jī)專業(yè)基礎(chǔ)綜合（綜合應(yīng)用題）模擬試卷第4套一、綜合應(yīng)用題(本題共20題，每題1.0分，共20分。)1、分頁(yè)和分段有何區(qū)別?標(biāo)準(zhǔn)答案：(1)共同點(diǎn)是：分頁(yè)和分段都采用離散分配的方式，且都要通過(guò)地址映射機(jī)構(gòu)來(lái)實(shí)現(xiàn)地址變換。(2)不同點(diǎn)是：第一，從功能上看，頁(yè)是信息的物理單位，分頁(yè)是為實(shí)現(xiàn)離散分配方式，以消減內(nèi)存的外零頭，提高內(nèi)存的利用率，即滿足系統(tǒng)管理的需要，而不是用戶的需要；而段是信息的邏輯單位，它含有一組其意義相對(duì)完整的信息，目的是為了能更好地滿足用戶的需要。第二，頁(yè)的大小固定且由系統(tǒng)確定，而段的長(zhǎng)度卻不固定，決定于用戶所編寫(xiě)的程序。第三，分頁(yè)的作業(yè)地址空間是一維的，而分段的作業(yè)地址空間是二維的。知識(shí)點(diǎn)解析：暫無(wú)解析2、什么是USB總線?USB總線有什么特點(diǎn)?USB的數(shù)據(jù)傳輸方式有哪些?標(biāo)準(zhǔn)答案：(1)USB通用串行總線是一種通用萬(wàn)能插口，可以將下列的任一部件插入U(xiǎn)SB端口：顯示器、鍵盤(pán)、鼠標(biāo)、調(diào)制解調(diào)器、游戲桿、掃描儀、打印機(jī)、視頻相機(jī)等。還可以將一些uSB外設(shè)進(jìn)行串接，即多個(gè)設(shè)備共用PC一個(gè)端口。USB總線可提供電源，但如將多個(gè)耗電量大的外設(shè)串接起來(lái)有可能使總線過(guò)載，此時(shí)可使用一個(gè)自供電的集線器來(lái)補(bǔ)充功耗。另外USB外設(shè)可以熱插拔。(2)根據(jù)設(shè)備對(duì)系統(tǒng)資源需求的不同，在USB標(biāo)準(zhǔn)中規(guī)定了四種不同的數(shù)據(jù)傳輸方式：①等時(shí)傳輸方式；②中斷傳輸方式；③控制傳輸方式；④批處理方式。知識(shí)點(diǎn)解析：暫無(wú)解析3、寫(xiě)出從哈希表中刪除關(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，qip=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；flee(p)；}／／被刪除關(guān)鍵字是鏈表中第一個(gè)結(jié)點(diǎn)else{q一>next=p一>next；free(P)；}}知識(shí)點(diǎn)解析：暫無(wú)解析4、已知32位寄存器中存放的變量x的機(jī)器碼為C0000004H，請(qǐng)問(wèn)：(1)當(dāng)x是無(wú)符號(hào)整數(shù)時(shí)，x的真值是多少?x／2的真值是多少?x／2存放在R1中的機(jī)器碼是什么?2x的真值是多少?2x存放在Rl中的機(jī)器碼是什么?(2)當(dāng)x是帶符號(hào)整數(shù)(補(bǔ)碼)時(shí)，x的真值是多少?x／2的真值是多少?x／2存放在R1中的機(jī)器碼是什么?2x的真值是多少?2x存放在R1中的機(jī)器碼是什么?標(biāo)準(zhǔn)答案：算術(shù)移位的對(duì)象是帶符號(hào)數(shù)，在移位過(guò)程中必須保持操作數(shù)的符號(hào)不變。當(dāng)左移1位時(shí)，如不產(chǎn)生溢出，則數(shù)值乘以2；而右移1位時(shí)，如不考慮因移出舍去的末位尾數(shù)，則數(shù)值除以2。因此，對(duì)于無(wú)符號(hào)整數(shù)，所有二進(jìn)制位均為數(shù)值位，而對(duì)于帶符號(hào)數(shù)，最高位為符號(hào)位。2x即左移1位，x／2即右移1位。(1)x是無(wú)符號(hào)整數(shù)，C0000004H的真值為231+230+22。x／2是由x邏輯右移1位得到的，即(231+230+22)÷2，其真值為230+229+2，存放在R1中的機(jī)器碼是01100000000000000000000000000010轉(zhuǎn)換成十六進(jìn)制為60000002H。2x是由x邏輯左移1位得到110000000000000000000000000001000真值發(fā)生溢出，存放在R1中的機(jī)器碼是10000000000000000000000000001000，轉(zhuǎn)換成十六進(jìn)制為80000008H。(2)機(jī)器碼C0000004H的二進(jìn)制補(bǔ)碼表示為1，1000000000000000000000000000100這是一個(gè)負(fù)數(shù)，得到的二進(jìn)制真值為一0111111111111111111111111111100對(duì)應(yīng)的十進(jìn)制真值為一(230一22)。x／2是由x算術(shù)右移1位得到的，其真值為一(229一2)，用二進(jìn)制真值表示為一1100000000000000000000000000010存放在R1中的機(jī)器碼是1，1100000000000000000000000000100轉(zhuǎn)換成十六進(jìn)制表示為E0000002H。知識(shí)點(diǎn)解析：暫無(wú)解析5、CPU執(zhí)行一段程序時(shí)，Cache完成存取的次數(shù)為5000次，主存完成存取的次數(shù)為200次。已知Cache存取周期為40ns，主存儲(chǔ)取周期為160ns。求：(1)Cache的命中率H。(2)Cache-主存系統(tǒng)的訪問(wèn)效率e。(3)平均訪問(wèn)時(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訪問(wèn)效率：e=1÷[r+(1一r)H]=1÷[4+(1—4)×0．96]=89．3％(3)平均訪問(wèn)時(shí)間：Ta=Tc／e=40÷0．893=45ns知識(shí)點(diǎn)解析：暫無(wú)解析6、處理機(jī)管理具有哪些功能?它們的主要任務(wù)是什么?標(biāo)準(zhǔn)答案：(1)進(jìn)程控制、進(jìn)程同步、進(jìn)程通信和調(diào)度。(2)進(jìn)程控制的主要任務(wù)是為作業(yè)創(chuàng)建進(jìn)程、撤銷(xiāo)已結(jié)束的進(jìn)程以及控制進(jìn)程在運(yùn)行過(guò)程中的狀態(tài)轉(zhuǎn)換。進(jìn)程同步的主要任務(wù)是對(duì)諸進(jìn)程的運(yùn)行進(jìn)行調(diào)節(jié)。進(jìn)程通信的任務(wù)是實(shí)現(xiàn)在相互合作進(jìn)程之間的信息交換。調(diào)度分為作業(yè)調(diào)度和進(jìn)程調(diào)度，作業(yè)調(diào)度的基本任務(wù)是從預(yù)備隊(duì)列中按照一定的算法，選擇若干個(gè)作業(yè)，為它們分配必要的資源；而進(jìn)程調(diào)度的任務(wù)是從進(jìn)程的就緒隊(duì)列中按照一定的算法選出一新進(jìn)程，把處理機(jī)分配給它，并為它設(shè)置運(yùn)行現(xiàn)場(chǎng)，使進(jìn)程投入運(yùn)行。知識(shí)點(diǎn)解析：暫無(wú)解析7、并發(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)的開(kāi)銷(xiāo)。假設(shè)進(jìn)程創(chuàng)建時(shí)間和完全占有CPu運(yùn)行的確切時(shí)間如下表所示。已知其I／O繁忙率為80％，處理機(jī)的利用率為20％。請(qǐng)計(jì)算并填寫(xiě)下列空格和圖表空格處。標(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開(kāi)始，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)程l還剩余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)過(guò)剛才計(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)程O(píng)退出后再計(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)程l退出以后，進(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ù)此，填寫(xiě)下列各個(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％因此，表格填寫(xiě)如下：甘特圖中空白括號(hào)填寫(xiě)如下圖所示：知識(shí)點(diǎn)解析：暫無(wú)解析8、試修改下面生產(chǎn)者一消費(fèi)者問(wèn)題解法中的錯(cuò)誤。producer：beginrepeatproduceranite