計算機專業(yè)（基礎綜合）模擬試卷1（共471題）

計算機專業(yè)（基礎綜合）模擬試卷1（共9套）（共471題）計算機專業(yè)（基礎綜合）模擬試卷第1套一、單選題(本題共40題，每題1.0分，共40分。)1、6個元素以6、5、4、3、2、1的順序進棧，下列不合法的出棧序列是()A、5、4、3、6、1、2B、4、5、3、1、2、6C、3、4、6、5、2、1D、2、3、4、1、5、6標準答案：C知識點解析：考查出棧序列的合法性。這類題通常采用手動模擬法。A選項：6入，5入，5出，4入，4出，3入，3出，6出，2入，1入，l出，2出；B選項：6入，5入，4入，4出，5出，3入，3出，2入，1入，1出，2出，6出；D選項：6入，5入，4入，3入，2入，2出，3出，4出，1入，1出，5出，6出；C選項：無對應的合法出棧順序。技巧：對于已入棧且尚未出棧的序列，要保證先入棧的一定不能在后入棧的前面出棧。選項C中的6在5前入棧，5沒有出棧，6卻出棧了，所以不合法，其他都符合規(guī)律。2、用鏈表方式存儲的隊列(有頭尾指針非循環(huán))，在進行刪除運算時()。A、僅修改頭指針B、僅修改尾指針C、頭、尾指針都要修改D、頭、尾指針可能都要修改標準答案：D知識點解析：考查鏈隊列的插入和刪除。鏈隊列有頭、尾兩個指針：插入元素時，在鏈隊列尾部插入一個新結點，并修改尾指針；刪除元素時，在鏈隊列頭部刪除一個結點，并修改頭指針。因此，通常出隊操作是不需要修改尾指針的。但當鏈隊列中只有一個元素時，當這個唯一的元素出隊時，需要將尾指針置為NULL(不帶頭結點)或指向頭結點(帶頭結點)。3、一棵二叉樹的前序遍歷序列為1234567，它的中序遍歷序列可能是()。A、3124567B、1234567C、4135627D、2153647標準答案：B知識點解析：考查二叉樹的遍歷序列、由遍歷序列構造二叉樹。二叉樹前序遍歷與中序遍歷的關系相當于以前序序列為入棧順序，以中序序列為出棧順序的棧，A選項中，3先出棧那么第二個出棧的將是2或者4、5、6、7。不可能為1。同理C、D皆不滿足條件。4、右圖所示的二叉樹是()。A、二叉判定樹B、二叉排序樹C、二叉平衡樹D、堆標準答案：B知識點解析：考查幾種特殊二叉樹的特點。二叉判定樹描述了折半查找的過程，肯定是高度平衡的，因此不可能是A。對于B，此圖中所有結點的關鍵值均大于左子樹中結點關鍵值，且均小于右子樹中所有結點的關鍵值，B符合。對于c，此圖中存在不平衡子樹，錯誤。對于D，此圖不符合小根堆或大根堆的定義。5、含有20個結點的平衡二叉樹的最大深度為()。A、4B、5C、6D、7標準答案：C知識點解析：考查平衡二叉樹的性質。在平衡二叉樹的結點最少情況下，遞推公式為N0=0，N1=1，N2=2，Nh=1+Nh—1+Nh—2(h為平衡二叉樹高度，Nh為構造此高度的平衡二叉樹所需最少結點數(shù))。通過遞推公式可得，構造5層平衡二叉樹至少需12個結點，構造6層至少需要20個。6、一個有n個頂點和n條邊的無向圖一定是()。A、連通的B、不連通的C、無環(huán)的D、有環(huán)的標準答案：D知識點解析：考查圖的基本性質。n個頂點構成連通圖至少需要，n—1條邊(生成樹)，但若再增加1條邊，則必然會構成環(huán)。如果一個無向圖有n個頂點和n—1條邊，可以使它連通但沒有環(huán)(即生成樹)，但再加一條邊，在不考慮重邊的情形下，就必然會構成環(huán)。7、己知有向圖G=(V，A)，其中V={a,b,c,d,e)，A={，，，，，}，對該圖進行拓撲排序，下面序列中不是拓撲排序的是()。A、a,d,c,b,eB、d,a,b,c,eC、a,b,d,c,eD、a,b,c,d,e標準答案：D知識點解析：考查拓撲排序。拓撲排序的方法：1)從AOV網(wǎng)中選擇一個沒有前驅的頂點(入度為0)，并輸出它；2)從AOV網(wǎng)中刪去該頂點，以及從該頂點發(fā)出的全部有向邊；3)重復上述兩步，直到剩余的網(wǎng)中不再存在沒有前驅的頂點為止。選項D中，刪去a、b及其對應的出邊后，c的入度不為0，此有邊<(d,c>，故不是拓撲序列。選項A、B、D均為拓撲序列。解答本類題時，建議讀者根據(jù)邊集合畫出草圖。8、散列表的地址范圍為0—17，散列函數(shù)為：H(k)=kmod17。采用線性探測法處理沖突，將關鍵字序列26,25,72,38,8，18,59依次存儲到散列表中。元素59存放在散列表中的地址是()。A、8B、9C、10D、11標準答案：D知識點解析：考查散列表的構造過程。任何散列函數(shù)都不可能絕對的避免沖突，因此采用合理的沖突處理方法，為沖突的關鍵字尋找下一個“空”位置。將前面各元素分別放入散列表中，其中8、9、10的位置分別存放25、26、8。元素59經(jīng)過哈希函數(shù)計算應該存入位置59mod17=8，發(fā)生沖突，采用線性探測再散列，—依次比較9、10、11，發(fā)現(xiàn)11為空，所以將其放入地址11中。各關鍵字對應的散列地址見下表。9、排序趟數(shù)與序列的原始狀態(tài)有關的排序方法是()。A、插入排序B、選擇排序C、冒泡排序D、快速排序標準答案：C知識點解析：考查各種排序算法的性質。插入排序和選擇排序的排序趟數(shù)始終為n—1，與序列的初態(tài)無關。對于冒泡排序，如果序列初態(tài)基本有序，可以在一趟排序后檢查是否有元素交換，如果沒有說明已排好序，不用再繼續(xù)排序。對于快速排序，每個元素要確定它的最終位置都需要一趟排序，所以無論序列原始狀態(tài)如何，都需要n趟排序，只不過對于不同的初態(tài)，每一趟處理的時間效率不同，初試狀態(tài)約接近有序，效率越低。注意：快速排序與初始序列有關，但這個有關是指排序的效率，而不是排序的趟數(shù)。10、對關鍵字序列{23,17,72,60,25,8,68,71,52}進行堆排序，輸出兩個最小關鍵字后的剩余堆是()。A、{23,72,60,25,68,71,52}B、{23,25,52,60,71,72,68}C、{71,25,23,52,60,72,68}D、{23,25,68,52,60,72,71}標準答案：D知識點解析：考查堆排序的執(zhí)行過程。篩選法初始建堆為{8,17,23,52,25,72,68,71,60)，輸出8后重建的堆為{17,25,23,52,60,72,68,71}，輸出17后重建的堆為{23,25,68,52,60,72,71}。建議讀者在解題時畫草圖。11、若對29個記錄只進行三趟多路平衡歸并，則選取的歸并路數(shù)至少是()。A、2B、3C、4D、5標準答案：C知識點解析：考查多路平衡歸并。m路平衡歸并就是將m個有序表組合成一個新的有序表。每經(jīng)過一趟歸并后，剩下的記錄數(shù)是原來的1／m，則經(jīng)過3趟歸并后｜29／m3｜=1，4為最小滿足條件的數(shù)。【注意】本題中4和5均能滿足，但6不滿足，若m=6，則只需2趟歸并便可排好序。因此，還需要滿足m2＜29，也即只有4和5才能滿足。12、下列關于指令字長、機器字長和存儲字長的說法中，正確的是()。Ⅰ．指令字長等于機器字長的前提下，取指周期等于機器周期Ⅱ．指令字長等于存儲字長的前提下，取指周期等于機器周期Ⅲ．指令字長和機器字長的長度沒有必然聯(lián)系Ⅳ．為了硬件設計方便，指令字長都和存儲字長一樣大A、Ⅰ、Ⅲ和ⅣB、Ⅱ、Ⅲ和ⅣC、Ⅱ和ⅢD、Ⅰ和Ⅳ標準答案：C知識點解析：本題考查各種字長的區(qū)別與聯(lián)系。指令字長通常取存儲字長的整數(shù)倍，如果指令字長等于存儲字長的2倍，則需要2次訪存，取指周期等于機器周期的2倍，如果指令字長等于存儲字長，取指周期等于機器周期，但是存儲字長和機器字長也沒有必然聯(lián)系，所以不能確定取指周期和機器周期的關系，故Ⅰ錯誤、Ⅱ正確。指令字長取決于操作碼的長度、操作數(shù)地址的長度和操作數(shù)地址的個數(shù)，與機器字長沒有必然的聯(lián)系，但為了硬件設計方便，指令字長一般取字節(jié)或存儲字長的整數(shù)倍，Ⅲ正確。指令字長一般取字節(jié)或存儲字長的整數(shù)倍，Ⅳ錯誤。注意：指令字長是指指令中包含二進制代碼的位數(shù)；機器字長是CPU一次能處理的數(shù)據(jù)長度，通常等于內部寄存器的位數(shù)；存儲字長是一個存儲單元存儲的二進制代碼(存儲字)的長度。13、已知[X]補=8CH，計算機的機器字長為8位二進制數(shù)編碼，則[X／4]補為()。A、8CHB、18HC、E3HD、F1H標準答案：C知識點解析：本題考查有符號數(shù)的算術移位運算。有符號數(shù)的乘2運算相當于對該數(shù)的二進制位進行左移1位的運算，符號位不變；除2運算相當于對該數(shù)的二進制位進行右移1位的運算，符號位不變。本題中，[X]補=8CH=(10001100)2，所以[X／4]補需要對(10001100)2算術右移2位(符號位保持不變)，因為數(shù)字是補碼表示且是負數(shù)，所以需要在移入位補1，其結果是(11100011)2=E3H。注：若是對于移位操作規(guī)則不熟悉的同學，可以先把補碼轉換為十進制數(shù)，再進行手動除以4后最后轉換成補碼較為保險。14、在C語言中，若有如下定義：inta=5，b=8；floatx=4．2，y=3．4；則表達式：(noat)(a+b)／2+(int)x％(int)y的值是()。A、7．500000B、7C、7．000000D、8標準答案：A知識點解析：本題考查強制類型轉換及混合運算中的類型提升。具體的計算步驟如下：a+b=13；(float)(a+b)=13．000000；(noat)(a+b)／2=6．500000；(int)x=4；(int)y：3；(int)x％(int)y=1；加號前是float，加號后是int，兩者的混合運算的結果類型提升為float型。故表達式的值為7．500000。強制類型轉換：格式為“TYPEb=(TYPE)a”，執(zhí)行后，返回一個具有TYPE類型的數(shù)值。類型提升：不同類型數(shù)據(jù)的混合運算時，遵循“類型提升”的原則，即較低類型轉換為較高類型。15、設存儲器容量為32字，字長為64位。模塊數(shù)m=4，采用低位交叉方式。存儲周期T=200ns，數(shù)據(jù)總線寬度為64位，總線傳輸周期r=50ns。則該交叉存儲器在連續(xù)讀出4個字的帶寬是()。A、32×107bit／sB、8×107bit／sC、73×107bit／sD、18×107bit／s標準答案：C知識點解析：本題考查交叉存儲器的性能分析。低位交叉存儲器連續(xù)讀出4個字所需的時間為：t=T+(m一1)*r=200ns+3*50ns=350ns=3．5×10—7s。故帶寬為：W=64×4b／(3．5×10—7s)=73×107b／s。注意：在低位交叉存儲器中，連續(xù)的地址分布在相鄰的塊中，而同一模塊內的地址都是不連續(xù)的。這種存儲器采用分時啟動的方法，可以在不改變每個模塊存取周期的前提下，提高整個主存的速度。16、下列關于Cache和虛擬存儲器的說法中，錯誤的有()。Ⅰ．當Cache失效(即不命中)時，處理器將會切換進程，以更新Cache中的內容Ⅱ．當虛擬存儲器失效(如缺頁)時，處理器將會切換進程，以更新主存中的內容Ⅲ．Cache和虛擬存儲器由硬件和OS共同實現(xiàn)，對應用程序員均是透明的Ⅳ．虛擬存儲器的容量等于主存和輔存的容量之和A、Ⅰ和ⅣB、Ⅲ和ⅣC、Ⅰ、Ⅱ和ⅢD、Ⅰ、Ⅲ和Ⅳ標準答案：D知識點解析：本題考查Cache和虛擬存儲器的特性。Cache失效與虛擬存儲器失效的處理方法不同，Cache完全由硬件實現(xiàn)，不涉及到軟件端；虛擬存儲器由硬件和OS共同完成，缺頁時才會發(fā)出缺頁中斷，故Ⅰ錯誤、Ⅱ正確、Ⅲ錯誤。在虛擬存儲器中，虛擬存儲器的容量應小于等于主存和輔存的容量之和，Ⅳ錯誤。注意：虛存的大小要同時滿足2個條件：(1)虛存的大小≤內存容量和外存容量之和，這是硬件的硬性條件規(guī)定的，若虛存大小超過了這個容量則沒有相應的空間來供虛存使用。(2)虛存的大小≤計算機的地址位數(shù)能容納的最大容量，比如你的地址是32位的，那么假設按字節(jié)編址，一個地址代表1B的存儲空間的話，那虛存的大小≤4GB(2的32次方B)。這是因為如果虛存的大小超過4GB，那么32位的地址將無法訪問全部虛存，也就是說4GB以后的空間是浪費掉的，相當于沒有一樣，沒有任何意義。實際虛存的容量是取條件(1)、(2)的交集，也就是說，兩個條件都要滿足，只滿足一個是不行的。注意：Cache和虛擬存儲器都是基于程序訪問的局部性原理，但他們實現(xiàn)的方法和作用均不太相同。Cache是為了解決CPU—主存的速度矛盾，而虛存是為了解決主存容量不足，限制程序并行數(shù)量的問題。17、下列關于基址尋址和變址尋址的說法中，正確的是()。Ⅰ．兩者都擴大指令的尋址范圍Ⅱ．變址尋址適合于編制循環(huán)程序Ⅲ．基址尋址適合于多道程序設計Ⅳ．基址寄存器的內容由操作系統(tǒng)確定，在執(zhí)行的過程中可變Ⅴ．變址寄存器的內容由用戶確定，在執(zhí)行的過程中不可變A、Ⅰ、Ⅱ和ⅢB、Ⅰ、Ⅱ和ⅤC、Ⅱ和ⅢD、Ⅱ、Ⅲ、Ⅳ和Ⅴ標準答案：A知識點解析：本題考查基址尋址和變址尋址的區(qū)別。兩者的有效地址都加上了對應寄存器的內容，都擴大了指令的尋址范圍，Ⅰ正確。變址尋址適合處理數(shù)組、編制循環(huán)程序，Ⅱ正確?；穼ぶ酚欣诙嗟莱绦蛟O計，Ⅲ正確?；芳拇嫫鞯膬热萦刹僮飨到y(tǒng)或管理程序確定，在執(zhí)行過程中其內容不變，而變址寄存器的內容由用戶確定，在執(zhí)行過程中其內容可變，故Ⅳ和V錯誤。注意：基址尋址和變址尋址的真實地址EA都是形式地址A加上一個寄存器中的內容。18、下列部件不屬于運算器的是()。A、狀態(tài)寄存器B、通用寄存器C、ALUD、數(shù)據(jù)高速緩存標準答案：D知識點解析：本題考查運算器的組成。數(shù)據(jù)高速緩存是專門存放數(shù)據(jù)的Cache，不屬于運算器。注意：運算器應包括算術邏輯單元、暫存寄存器、累加器、通用寄存器組、程序狀態(tài)字寄存器、移位器等?？刂破鲬ㄖ噶畈考?、時序部件、微操作信號發(fā)生器(控制單元)、中斷控制邏輯等，指令部件包括程序計數(shù)器(PC)、指令寄存器(IR)和指令譯碼器(ID)。19、流水線計算機中，下列語句發(fā)生的數(shù)據(jù)相關類型是()。ADDR1，R2，R3；(R2)+(R3)→R1ADDR4，R1，R5；(R1)+(R5)→R4A、寫后寫B(tài)、讀后寫C、寫后讀D、讀后讀標準答案：C知識點解析：本題考查流水線的數(shù)據(jù)相關。在這兩條指令中，都對R1進行操作，其中前面對R1寫操作，后面對R1讀操作，因此發(fā)生寫后讀相關。數(shù)據(jù)相關包括RAW(寫后讀)、WAW(寫后寫)、WAR(讀后寫)。設有i和j兩條指令，i指令在前，j指令在后，則三種相關的含義：*RAW(寫后讀)：指令j試圖在指令i寫入寄存器前舊讀出該寄存器的內容，這樣指令j就會錯誤地讀出該寄存器舊的內容。*WAR(讀后寫)：指令j試圖在指令i讀出該寄存器前就寫入該寄存器，這樣指令i就會錯誤地讀出該寄存器的新內容。*WAW(寫后寫)：指令j試圖在指令i寫入寄存器前就寫入該寄存器，這樣兩次寫的先后次序被顛倒，就會錯誤地使由指令i寫入的值稱為該寄存器的內容。20、在以下描述PCI總線的基本概念中，正確的描述是()。Ⅰ．PCI總線是一個與處理器無關的高速外圍總線Ⅱ．PCI總線的基本傳輸機制是猝發(fā)式傳送Ⅲ．PCI設備一定是主設備Ⅳ．系統(tǒng)中只允許有一條PCI總線A、僅ⅠB、僅ⅡC、Ⅱ、Ⅲ和ⅣD、Ⅰ和Ⅱ標準答案：D知識點解析：本題考查PCI總線。PCI的特點主要有：與CPU及時鐘頻率無關；即插即用；采用猝發(fā)傳送方式；擴展性好，可以采用多級PCI總線，可知Ⅰ和Ⅱ正確、Ⅳ錯誤?？偩€連接的既然有主設備，就肯定有從設備，從設備主設備并不是固定的，Ⅲ錯誤。注意：PCI總線是常見的總線標準，如聲卡、顯卡、網(wǎng)卡等常用的插口。21、在總線上，()信息的傳輸為單向傳輸。Ⅰ．地址Ⅱ．數(shù)據(jù)Ⅲ．控制Ⅳ．狀態(tài)A、Ⅰ、Ⅱ和ⅣB、Ⅲ和ⅣC、Ⅰ和ⅡD、Ⅰ、Ⅲ和Ⅳ標準答案：D知識點解析：考查總線的分類與特點。地址、控制和狀態(tài)信息都是單向傳輸?shù)?，?shù)據(jù)信息是雙向傳輸?shù)摹?2、設CPU與I／O設備以中斷方式進行數(shù)據(jù)傳送，CPU響應中斷時，該I／O設備接口控制器送給CPU的中斷向量表(中斷向量表存放中段向量)的指針是0800H，0800H單元中的值為1200H。則該I／O設備的中斷服務程序在主存中的入口地址為()。A、0800HB、0801HC、1200HD、120lH標準答案：C知識點解析：本題考查中斷向量。中斷向量就是中斷服務程序的入口地址，所以需要找到指定的中斷向量，而中斷向量是保存在中斷向量表中的。0800H是中斷向量表的地址，所以0800H的內容即是中斷向量。23、下列關于進程和線程的敘述中，正確的是()。Ⅰ．一個進程可包含多個線程，各線程共享進程的虛擬地址空間Ⅱ．一個進程可包含多個線程，各線程共享棧Ⅲ．當一個多線程進程(采用一對一線程模型)中某個線程被阻塞后，其他線程將繼續(xù)工作Ⅳ．當一個多線程進程中某個線程被阻塞后，該阻塞進程將被撤銷A、Ⅰ、Ⅱ、ⅢB、Ⅰ、ⅢC、Ⅱ、ⅢD、Ⅱ、Ⅳ標準答案：B知識點解析：本題考查線程的實現(xiàn)方式?？忌⒁庹莆者M程與線程的區(qū)別和聯(lián)系，以及在具體執(zhí)行中線程與進程扮演的角色和線程的屬性。在多線程模型中，進程依然是資源分配的基本單元，而線程是最基本的CPU執(zhí)行單元，它們共享進程的邏輯地址空間，但各個線程有自己的棧空間。故Ⅰ對、Ⅱ錯。在一對一線程模型中，一個線程每個用戶級線程都映射到一個內核級線程，一個線程被阻塞不影響該進程的其他線程運行狀態(tài)，Ⅲ對、Ⅳ錯。假如Ⅳ對的話，凡是遇到等待I／O輸出的線程，都被撤銷，這顯然是不合理的，某個進程被阻塞只會把該進程加入阻塞隊列，當它得到等待的資源時，就會回到就緒隊列。24、()調度算法有利于CPU繁忙型的進程，而不利于I／O繁忙型的進程。A、時間片輪轉B、先來先服務C、短進程優(yōu)先D、優(yōu)先級調度標準答案：B知識點解析：本題考查各種調度算法的特點。FCFS調度算法比較有利于長作業(yè)，而不利于短作業(yè)。所謂CPU繁忙型的作業(yè)，是指該類作業(yè)需要大量的CPU時間進行計算，而很少請求I／O操作，故采用FCFS可從容完成計算。I／O繁忙型的作業(yè)是指CPU處理時，需頻繁的請求I／O操作，導致操作完成后還要重新排隊等待調度，所以CPU繁忙型作業(yè)更接近于長作業(yè)，若采用FCFS則等待時間過長。而時間片輪轉法對于短作業(yè)和長作業(yè)的時間片都一樣，所以地位也近乎一樣。優(yōu)先級調度有利于優(yōu)先級高的進程，而優(yōu)先級和作業(yè)時間長度是沒有什么必然聯(lián)系的。25、Ⅳ個進程共享M臺打印機(其中N＞M)，假設每臺打印機為臨界資源，必須獨占使用，則打印機的互斥信號量的取值范圍為()。A、—(Ⅳ—1)～MB、—(N—M)～MC、—(N—M)～1D、—(N—1)～1標準答案：B知識點解析：考查進程同步的信號量機制。具有多個臨界資源的系統(tǒng)有可能為多個進程提供服務。當沒有進程要求使用打印機時，打印機信號量的初值應為打印機的數(shù)量，而當一個進程要求使用打印機時，打印機的信號量就減一，當全部進程要求使用打印機時，信號量就為M—N=一(N—M)。綜上所述信號量的取值范圍是：阻塞隊列中的進程個數(shù)～臨界資源個數(shù)。因此本題中的取值范圍為一(N一M)～M。26、關于優(yōu)先級大小的論述中，錯誤的是()。Ⅰ．計算型作業(yè)的優(yōu)先級，應高于I／O型作業(yè)的優(yōu)先級Ⅱ．短作業(yè)的優(yōu)先級，應高于長作業(yè)的優(yōu)先級Ⅲ．用戶進程的優(yōu)先級，應高于系統(tǒng)進程的優(yōu)先級Ⅳ．資源要求多的作業(yè)的優(yōu)先級應高于對資源要求少的優(yōu)先級A、Ⅰ和ⅣB、Ⅲ和ⅣC、Ⅰ、Ⅲ和ⅣD、Ⅰ、Ⅱ、Ⅲ和Ⅳ標準答案：D知識點解析：本題考查進程的優(yōu)先級。由于I／O操作需要及時完成，它沒有辦法長時間保存所要輸入輸出的數(shù)據(jù)，通常I／O型作業(yè)的優(yōu)先級要高于計算型作業(yè)，Ⅰ錯誤；系統(tǒng)進程的優(yōu)先級應高于用戶進程。作業(yè)的優(yōu)先級與長作業(yè)、短作業(yè)或者是系統(tǒng)資源要求的多少沒有必然的關系。在動態(tài)優(yōu)先級中，隨著進程執(zhí)行時間增加其優(yōu)先級降低，隨著作業(yè)等待時間的增加其優(yōu)先級應上升Ⅱ、Ⅲ錯誤。而資源要求低的作業(yè)應當給予較高的優(yōu)先級讓其更早完成釋放出占有資源以便其他作業(yè)順利進行，若給資源要求多的作業(yè)更高的優(yōu)先級，那么在沒有有效手段避免死鎖的情況下，多個資源要求多的作業(yè)共同工作容易造成死鎖。Ⅳ錯誤。答案選D。27、假設系統(tǒng)有5個進程，A、B、C三類資源。某時刻進程和資源狀態(tài)如下：下面敘述正確的是()。A、系統(tǒng)不安全B、該時刻，系統(tǒng)安全，安全序列為C、該時刻，系統(tǒng)安全，安全序列為D、該時刻，系統(tǒng)安全，安全序列為標準答案：D知識點解析：本題考查系統(tǒng)的安全狀態(tài)和安全序列。當Available為(2,3,3)時，可以滿足P4,P5中任一進程的需求；這兩個進程結束后釋放資源，Available為(7,4,11)此時可以滿足P1,P2,P3中任一進程的需求，故該時刻系統(tǒng)處于安全狀態(tài)，安全序列中只有D滿足條件。28、支持程序存放在不連續(xù)內存中的存儲管理方法有()。Ⅰ．動態(tài)分區(qū)分配Ⅱ．固定分區(qū)分配Ⅲ．分頁式分配Ⅳ．段頁式分配Ⅴ．分段式分配A、Ⅰ和ⅡB、Ⅲ和ⅣC、Ⅲ、Ⅳ和ⅤD、Ⅰ、Ⅲ、Ⅳ和Ⅴ標準答案：C知識點解析：本題考查非連續(xù)分配管理方式。非連續(xù)分配允許一個程序分散地裝入不相鄰的內存分區(qū)中。動態(tài)分區(qū)分配和固定分區(qū)分配都屬于連續(xù)分配方式，而非連續(xù)分配有分頁式分配、分段式分配和段頁式分配三種。29、下面關于虛擬存儲器的論述中，正確的是()。A、在段頁式系統(tǒng)中以段為單位管理用戶的邏輯空間，以頁為單位管理內存的物理空間，有了虛擬存儲器才允許用戶使用比內存更大的地址空間B、為了提高請求分頁系統(tǒng)中內存的利用率允許用戶使用不同大小的頁面C、為了能讓更多的作業(yè)同時運行，通常只裝入10％～30％的作業(yè)即啟動運行D、最佳適應算法是實現(xiàn)虛擬存儲器的常用算法標準答案：A知識點解析：本題考查虛擬存儲器的特性。頁面的大小是由操作系統(tǒng)決定的，不同的操作系統(tǒng)的分頁機制可能不同，對用戶是透明的，B錯誤。虛擬存儲器只裝入部分作業(yè)到內存是為了從邏輯上擴充內存，有些較小的程序一頁便可全部裝入就沒有10％～30％的說法，C選項說得太絕對，C錯誤。最佳適應算法是動態(tài)分區(qū)分配中的算法，D錯誤。30、從下列關于目錄檢索的說法中，正確的是()。A、由于Hash具有較快的檢索速度，故現(xiàn)代操作系統(tǒng)中都用它來替代傳統(tǒng)的順序檢索法B、在利用順序檢索法時，對樹型目錄應采用文件的路徑名，且應從根目錄開始逐級檢索C、在利用順序檢索法時，只要路徑名的一個分量名未找到，便應停止查找D、在順序檢索法時的查找完成后，即可得到文件的物理地址標準答案：C知識點解析：本題考查目錄檢索的原理。實現(xiàn)用戶對文件的按名存取，系統(tǒng)先利用用戶提供的文件名形成檢索路徑，對目錄進行檢索。在順序檢索中，路徑名的一個分量未找到，說明路徑名中的某個目錄或文件不存在，就不需要繼續(xù)再檢索了，C正確。目錄的查詢方式有兩種：順序檢索法和Hash法，通常還是采用順序檢索法，A錯誤。在樹型目錄中，為了加快文件檢索速度，可設置當前目錄，于是文件路徑可以從當前目錄開始查找，B錯誤。在順序檢索法查找完成后，得到的是文件的邏輯地址，D錯誤。31、設某文件為鏈接文件，由5個邏輯記錄組成，每個邏輯記錄的大小與磁盤塊的大小相等，均為512字節(jié)，并依次存放在50，121，75，80，63號磁盤塊上。若要存取文件的第1569邏輯字節(jié)處的信息，則應訪問()號磁盤塊。A、3B、80C、75D、63標準答案：B知識點解析：本題考查磁盤的性質。1569=512*3+33，故要訪問字節(jié)位于第4個磁盤塊上，對應的盤塊號為80。32、下列有關設備管理概念的敘述中，()是不正確的。Ⅰ．通道可視為一種軟件，其作用是提高了CPU的利用率Ⅱ．編制好的通道程序是存放在主存儲器中的Ⅲ．用戶給出的設備編號是設備的物理號Ⅳ．來自通道的I／O中斷事件應該由設備管理負責A、Ⅰ和ⅢB、Ⅰ和ⅣC、Ⅱ、Ⅲ和ⅣD、Ⅱ和Ⅲ標準答案：A知識點解析：本題考查設備管理的知識點。通道是一種硬件、或特殊的處理器，它有自身的指令，故Ⅰ錯誤。通道沒有自己的內存，通道指令存放在主機的內存中，也就是說通道與CPU共享內存，故Ⅱ正確。為了實現(xiàn)設備獨立性，用戶使用邏輯設備號來編寫程序，故給出的編號為邏輯編號，故Ⅲ錯誤。來自通道的I／O中斷事件是屬于輸入／輸出的問題，故應該由設備管理負責，故Ⅳ正確。綜上，Ⅰ、Ⅲ錯誤。注意：通道作為一種特殊的硬件或者處理器，具有諸多特征，它與一般處理器的區(qū)別，以及與DMA方式的區(qū)別要認真理解。33、設待傳送數(shù)據(jù)總長度為L位，分組長度為P位，其中頭部開銷長度為H位，源結點到目的結點之間的鏈路數(shù)為h，每個鏈路上的延遲時間為D秒，數(shù)據(jù)傳輸率為Bbps，電路交換建立連接的時間為S秒，則電路交換方式傳送完所有數(shù)據(jù)需要的時間是()秒。A、hD+L／BB、S+hD+L／BC、S+hD+PL／((P—H)B)D、S+L／B標準答案：B知識點解析：本題考查計算機網(wǎng)絡的性能指標。計算機網(wǎng)絡的各種性能指標(尤其是時延、吞吐率)是重要考點，時延主要包括發(fā)送時延(也叫傳輸時延)和傳播時延。電路交換首先建立連接，然后再進行數(shù)據(jù)傳輸，因此傳送所有數(shù)據(jù)所需的時間是連接建立時間，鏈路延遲，發(fā)送時間的和，即S+hD+L／B。注意，這里對電路交換不熟悉的同學容易選到C，事實上，電路交換建立鏈接以后便開始直接傳送數(shù)據(jù)，是不用進行分組的，傳送完數(shù)據(jù)后在斷開鏈接，所以本題跟分組相關的信息全是多余的。34、以下各項中，不是數(shù)據(jù)報服務特點的是()。A、每個分組自身攜帶有足夠多的信息，它的傳送被單獨處理B、在整個傳送過程中，不需要建立虛電路C、使所有分組按順序到達目的端系統(tǒng)D、網(wǎng)絡結點要為每個分組做出路由選擇標準答案：C知識點解析：本題考查數(shù)據(jù)報的特點。數(shù)據(jù)報服務具有如下特點：1)發(fā)送分組前不需要建立連接。2)網(wǎng)絡盡最大努力交付，傳輸不保證可靠性，為每個分組獨立地選擇路由。3)發(fā)送的分組中要包括發(fā)送端和接收端的完整地址，以便可以獨立傳輸。4)網(wǎng)絡具有冗余路徑，對故障的適應能力強。5)收發(fā)雙方不獨占某一鏈路，資源利用率較高。由于數(shù)據(jù)報提供無連接的網(wǎng)絡服務，只盡最大努力交付而沒有服務質量保證，因此所有分組到達是無序的，故C選項錯誤。35、考慮建立一個CSMA／CD網(wǎng)，電纜長度為1km，不使用中繼器，傳輸速率為1Gbps，電纜中信號的傳播速率是200000km／s，則該網(wǎng)絡中最小幀長是()。A、10000bitB、1000bitC、5000bitD、20000bit標準答案：A知識點解析：本題考查CSMA／CD協(xié)議的最小幀長。在發(fā)送的同時要進行沖突檢測，這就要求在能檢測出沖突的最大時間內數(shù)據(jù)不能發(fā)送完畢，否則沖突檢測不能有效地工作。所以，當發(fā)送的數(shù)據(jù)幀太短時，必須進行填充。最小幀長：數(shù)據(jù)傳輸速率×爭用期。爭用期=網(wǎng)絡中兩站點最大的往返傳播時間2τ=2×(1／200000)=0．00001；最小幀長=1000000000×0．00001=10000bit。36、在一條點對點鏈路上，為了減少地址的浪費，子網(wǎng)掩碼應該指定為()。A、255．255．255．252B、255．255．255．248C、255．255．255．240D、255．255．255．196標準答案：A知識點解析：在一條點對點的鏈路上，存在兩臺主機，即只需給這個網(wǎng)絡分配2個主機位(22—2=2)即可(減掉的地址是主機號為全0和全1的地址)，故在該網(wǎng)絡中主機段必須至少是2位，子網(wǎng)掩碼應該指定為255．255．255．252。37、某同學在校園網(wǎng)訪問因特網(wǎng)，從該同學打開計算機電源到使用命令ftp202．38．70．25連通文件服務器的過程中，()協(xié)議可能沒有使用到。A、IPB、ICMPC、ARPD、DHCP標準答案：B知識點解析：考查各種協(xié)議的應用。剛開機時ARP表為空，當需要和其他主機進行通信時，數(shù)據(jù)鏈路層需要使用MAC地址，因此就會用到ARP協(xié)議。在校園網(wǎng)訪問因特網(wǎng)時，肯定會使用到IP協(xié)議。而此時訪問的是因特網(wǎng)，因特網(wǎng)為外網(wǎng)，所以就需要通過DHCP分配公網(wǎng)地址。而ICMP協(xié)議主要用于發(fā)送ICMP差錯報告報文和。ICMP詢問報文，則不一定會用到。38、某路由器的路由表如下所示。如果它收到一個目的地址為192．168．10．23的IP數(shù)據(jù)報，那么它為該數(shù)據(jù)報選擇的下一路由器地址為()。A、192．168．1．35B、192．168．2．66C、直接投遞D、丟棄標準答案：B知識點解析：經(jīng)過與路由表比較，發(fā)現(xiàn)該目的地址沒有與之對應的要達到的網(wǎng)絡地址，而在該路由表中有默認路由，根據(jù)相關規(guī)定，只要目的網(wǎng)絡都不匹配，一律選擇默認路由。所以下一跳的地址就是默認路由所對應的IP地址，即192．168．2．66．39、一個長度為3000字節(jié)的UDP數(shù)據(jù)報。在數(shù)據(jù)鏈路層使用以太網(wǎng)來進行傳輸，為了正確傳輸，則需要將其拆分成()個IP數(shù)據(jù)片。A、2B、3C、4D、不拆分標準答案：B知識點解析：本題考查以太網(wǎng)中IP數(shù)據(jù)報的分片。因為IP數(shù)據(jù)報被封裝在鏈路層數(shù)據(jù)報中，故鏈路層的MTU(最大傳輸單元)嚴格地限制著IP數(shù)據(jù)報的長度。以太網(wǎng)幀的MTU是1500B，IP頭部長度為20B，因此以太網(wǎng)的最大數(shù)據(jù)載荷是1480B，因此3000B的數(shù)據(jù)必須進行分片，3000=1480+1480+40共3片。40、TCP是互聯(lián)網(wǎng)中的傳輸層協(xié)議，TCP協(xié)議進行流量控制的方式是()。A、使用停等ARQ協(xié)議B、使用后退N幀ARQ協(xié)議C、使用固定大小的滑動窗口協(xié)議D、使用可變大小的滑動窗口協(xié)議標準答案：D知識點解析：本題考查TCP協(xié)議的流量控制方式。TCP協(xié)議采用滑動窗口機制來實現(xiàn)流量控制，同時根據(jù)接收端給出的接收窗口的數(shù)值發(fā)送方來調節(jié)自己的發(fā)送窗口，即使用可變大小的滑動窗口協(xié)議。二、綜合應用題(本題共17題，每題1.0分，共17分。)請回答下列問題：41、試證明若圖中各條邊的權值各不相同，則它的最小生成樹唯一。標準答案：反證法：假設有兩棵不同的最小生成樹，則這兩棵不同的最小生成樹的邊的并集在圖中是有環(huán)的，在最小生成樹中要去掉環(huán)中權值最大的邊，與假設顯然矛盾。知識點解析：暫無解析42、prim算法和kruskal算法生成的最小生成樹一定相同嗎?標準答案：不一定。當圖的最小生成樹不唯一時，則用prim算法和kruskal算法生成的最小生成樹不一定相同。而當自己手算并非計算機執(zhí)行算法時，就算相同的算法也有可能因為不同的選擇而使得最小生成樹不同。知識點解析：暫無解析43、畫出下列帶權圖G的所有最小生成樹。標準答案：圖G的最小生成樹如下：根據(jù)kruskal算法，先把c—d的邊(權值20)加入集合，而接下來選擇下一條邊時，因為有兩條權值為40的邊可以選擇，那么因為不同的選擇就會生成出不同的最小生成樹，若選擇b—d，然后同樣出現(xiàn)c—d與a—C的選擇，而不管先選擇哪條邊，另一條邊也會成為下一個選擇的對象，所以這里不影響樹的結構，最后答案為左邊這棵樹，而當之前第二次選擇邊的時候，選擇c—b則會是右邊的最小生成樹。知識點解析：暫無解析44、在數(shù)組中，某個數(shù)字減去它右邊的數(shù)字得到一個數(shù)對之差。求所有數(shù)對之差的最大值。例如，在數(shù)組{2，4，1，16，7，5，11，9}中，數(shù)對之差的最大值是11，是16減去5的結果。(1)給出算法的基本設計思想。(2)根據(jù)設計思想，采用C或C++語言描述算法，關鍵之處給出注釋。(3)說明你所設計算法的時間復雜度。標準答案：分治法。把數(shù)組分成兩個子數(shù)組，其實沒有必要拿左邊子數(shù)組中較小的數(shù)字去和右邊子數(shù)組中較大的數(shù)字作減法?？梢韵胂螅瑪?shù)對之差的最大值只可能是下面三種情況之一：①被減數(shù)和減數(shù)都在第一個子數(shù)組中，即第一個子數(shù)組中的數(shù)對之差的最大值；②被減數(shù)和減數(shù)都在第二個子數(shù)組中，即第二個子數(shù)組中數(shù)對之差的最大值；③被減數(shù)在第一個子數(shù)組中，是第一個子數(shù)組的最大值。減數(shù)在第二個子數(shù)組中，是第二個子數(shù)組的最小值。這三個差值的最大者就是整個數(shù)組中數(shù)對之差的最大值。在前面提到的三種情況中，得到第一個子數(shù)組的最大值和第二子數(shù)組的最小值不是一件難事，但如何得到兩個子數(shù)組中的數(shù)對之差的最大值?這其實是原始問題的子問題，可以遞歸地解決。下面是這種思路的參考代碼：intMaxDiff_Solutionl(intnumbers[]，unsignedlength){if(numbers==NULL｜｜lenath＜2)return0；intmax，min；returnMaxDiffCore(numbers，numbers+length—1，&max，&min)；}intMaxDiffCore(int*start，int*end，int*max，int*min){if(end==start){*max=*min=*start；return0；}int*middle=start+(end—start)／2；intmaxLeft，minLeft；intleftDiff=MaxDiffCore(start，middle，&maxLeft，&minLeft)；intmaxRight，minRight，intrightDiff=MaxDiffCore(middle+1，end，&maxRight，&minRight)；intcrossDiff=maxLeft—minRight；*max=(maxLeft＞maxRight)?maxLeft：maxRight；*min=(minLeft＜minRight)?minLeft：minRight；intmaxDiff=(leftDiff＞rightDiff)?leftDiff：rightDiff；maxDiff=(maxDiff＞crossDiff)?maxDiff：crossDiff；returnmaxDiff；}知識點解析：暫無解析假設有兩個整數(shù)x和y，x=一68，y=一80，采用補碼形式(含1位符號位)表示，x和y分別存放在寄存器A和B中。另外，還有兩個寄存器C和D。A、B、C、D都是8位的寄存器。請回答下列問題：(要求最終用十六進制表示二進制序列)45、寄存器A和B中的內容分別是什么?標準答案：本題考查補碼的機內表示、補碼的運算和溢出判斷。因x=一68=一(1000100)2，則[—68]補=10111100=BCH；因y=一80=一(1010000)2，則[—80]補=10110000=BOH，所以寄存器A和B中的內容分別是BCH、BOH。知識點解析：暫無解析46、x和y相加后的結果存放在C寄存器中，寄存器C中的內容是什么?此時，溢出標志位OF是什么?符號標志位SF是什么?進位標志位CF是什么?標準答案：[x+y]補=[x]補+[y]補=10111100+10ll0000=101101100=6CH，所以寄存器C中的內容是6CH，其真值為108。此時，溢出標志位OF為1，表示溢出，即說明寄存器C中的內容不是真正的結果；符號標志位SF為0，表示結果為正數(shù)(溢出標志為1，說明符號標志有錯)；進位標志位CF為1，僅表示加法器最高位有進位，對運算結果不說明什么。知識點解析：暫無解析47、x和y相減后的結果存放在D寄存器中，寄存器D中的內容是什么?此時，溢出標志位OF是什么?符號標志位SF是什么?進位標志位CF是什么?標準答案：[x—y]補=[x]補+[—y]補=10111100+01010000=100001100=0CH,最高位前面的一位被丟棄(取模運算)，結果為12，所以寄存器D中的內容是0CH，其真值為12。此時，溢出標志位OF為0，表示不溢出，即：寄存器D中的內容是真正的結果；符號標志位SF為0，表示結果為正數(shù)；進位標志位CF為1，僅表示加法器最高位有進位，對運算結果不說明什么。知識點解析：暫無解析下圖所示的處理機邏輯框圖中，有兩條獨立的總線和兩個獨立的存儲器。己知指令存儲器IM最大容量為16384字(字長18位)，數(shù)據(jù)存儲器DM最大容量為65536字(字長16位)。各寄存器均有“打入”(Rin)和“送出”(Rououtt)控制命令，但圖中未標出。48、請指出下列各寄存器的位數(shù)：程序計數(shù)器PC、指令寄存器IR、累加器．AC0和ACl、通用寄存器R0—R7、指令存儲器地址寄存器IAR、指令存儲器數(shù)據(jù)寄存器IDR．、數(shù)據(jù)存儲器地址寄存器DAR、數(shù)據(jù)存儲器數(shù)據(jù)寄存器DDR。標準答案：本題考查數(shù)據(jù)通路與指令的執(zhí)行步驟。指令存儲器有16384字，即容量有16384=214字，PC和IAR為14位；字長18位，IR和IDR為18位。數(shù)據(jù)存儲器有65536字，即容量有65536=216字，DAR為16位；AC0～AC1、R0～R2和DDR的字長應和數(shù)據(jù)字長相等，均為16位。知識點解析：暫無解析49、設處理機的指令格式為：加法指令可寫為“ADDX(R1)”。其功能是(AC0)+((Ri)+X)→AC1，其中((Ri)+X)部分通過尋址方式指向數(shù)據(jù)存儲器，現(xiàn)取Ri為R1。試畫出ADD指令從取指令開始到執(zhí)行結束的操作序列圖，寫明基本操作步驟和相應的微操作控制信號。(假設PC+1→PC有專門的部件和信號控制)標準答案：加法指令“ADDx(Ri)”是一條隱含指令，其中一個操作數(shù)來自AC0，另一個操作數(shù)在數(shù)據(jù)存儲器中，地址由通用寄存器的內容(Ri)加上指令格式中的X量值決定，可認為這是一種變址尋址。指令周期的操作流程圖如下圖：相應的微操作控制信號列在框圖外。知識點解析：暫無解析50、在一間酒吧里有3個音樂愛好者隊列，第1隊的音樂愛好者只有隨身聽，第2隊只有音樂磁帶，第3隊只有電池。而要聽音樂就必須隨身聽，音樂磁帶和電池這3種物品俱全。酒吧老板一次出售這3種物品中的任意兩種。當一名音樂愛好者得到這3種物品并聽完一首樂曲后，酒吧老板才能再一次出售這3種物品中的任意兩種。于是第2名音樂愛好者得到這3種物品，并開始聽樂曲。全部買賣就這樣進行下去。試用P，V操作正確解決這一買賣。標準答案：本題考查用PV操作解決進程的同步互斥問題。第1隊音樂愛好者要競爭“待出售的音樂磁帶和電池”，而且在初始狀態(tài)下，系統(tǒng)并無“待出售的音樂磁帶和電池”，故可為該種資源設置一初值為0的信號量buy1；同樣，需設置初值為0的buy2、buy3分別對應“待出售的隨身聽和電池”、“待出售的隨身聽和音樂磁帶”。另外，為了同步買者的付費動作和賣者的給貨動作，還需設置信號量payment和goods，以保證買者在付費后才能得到所需商品。信號量musicover用來同步音樂愛好者聽樂曲和酒吧老師的下一次出售行為。具體的算法描述如下：semaphorebuy1=buy2=buy3=0；semaphorepayment=0；semaphoregoods=0；semaphoremusic_oVer=0；cobegin{processboss(){／／酒吧老板while(TRUE){／／拿出任意兩種物品出售；if《出售的是音樂磁帶和電池)V(buy1)；elseif(出售的是隨身聽和電池)V(buy2)；elseif(出售的是隨身聽和音樂磁帶)V(buy3)；P(payment)；／／等待付費V(goods)；／／給貨P(musicover)；／／等待樂曲結束}}processfan1()(／／第1隊音樂愛好者while(TRUE){／／因為一個進程代表一隊，而不是一個愛好者，／／所以這里是／／while(true)，下同P(buy1)；／／等有音樂磁帶和電池出售V(payment)；／／付費P(goods)；／／取貨欣賞一曲樂曲；V(musicover)；／／通知老板樂曲結束}}processfan2(){／／第2隊音樂愛好者while(TRUE){P(buy2)；／／等有隨身聽和電池出售V(payment)；／／付費p(goods)；／／取貨欣賞一曲樂曲，V(musicover)；／／通知老板樂曲結束}}processfan3(){／／第3隊音樂愛好者while(TRUE){P(buy3)；／／等有隨身聽和音樂磁帶出售V(payment；／／付費P(goods)；／／取貨欣賞一曲樂曲，V(musicover)；／／通知老板樂曲結束}}}Coend知識點解析：暫無解析某機按字節(jié)編址，主存容量為1MB，采用兩路組相聯(lián)方式(每組僅有兩塊)的Cache容量為64KB，每個數(shù)據(jù)塊為256B。己知訪問開始前第2組(組號為1)的地址陣列內容如下圖所示(第一列為組內塊號)。Cache采用LRU替換策略。51、分別說明主存地址中標記(Tag)、組號和塊內地址三部分的位置和位數(shù)。標準答案：本題考查Cache與主存的映射、替換算法。在采用全相聯(lián)和組相聯(lián)映像方式從主存向Cache傳送一個新塊，而Cache中的空間己被占滿時，就需要把原來存儲的一塊替換掉。LRU算法(最近最少使用法)是把CPU近期最少使用的塊作為被替換的塊。按字節(jié)編址，每個數(shù)據(jù)塊為256B，則塊內地址為8位；主存容量為1MB，則主存地址為20位；Cache容量為64KB，Cache共有256塊，采用兩路組相連，所以Cache共有128組(64K÷(2×256))，則組號為7位；標記(Tag)的位數(shù)為20一7—8=5位。主存和Cache的地址格式如下圖所示：注意：求解標記、組號和塊內地址的方法如下：①塊內地址位數(shù)=log2(數(shù)據(jù)塊大小)②組號位數(shù)=log2(Cache的總組數(shù))③標記號=主存總地址位數(shù)．塊內地址位數(shù)．組號位數(shù)知識點解析：暫無解析52、若CPU要順序訪問地址為20124H、58100H、60140H和60138H等4個主存單元。上述4個數(shù)能否直接從Cache中讀取，若能，請給出實際訪問的Cache地址。第4個數(shù)訪問結束時，上圖中的內容將如何變化。標準答案：將CPU要順序訪問的4個數(shù)的地址寫成二進制，可以發(fā)現(xiàn)：20124H=00100000000100100100B，組號為1，是第2組的塊，根據(jù)題中陣列內容的圖可知，現(xiàn)在Cache內有這個塊，第1次訪問命中，實際訪問的Cache地址為0124H。58100H=01011000000100000000B，組號為1，是第2組的塊，根據(jù)題中陣列內容的圖可知，現(xiàn)在Cache內有這個塊，第2次訪問命中，實際訪問的Cache地址為0100H。60140H=01100000000101000000B，組號為1，是第2組的塊，但Cache中無此塊，第3次訪問不命中，根據(jù)LRU算法，替換掉第O塊位置上的塊，變化后的地址陣列如下圖。60138H=01100000000100111000B，組號為1，是第2組的塊，與上一個地址處于同一個塊，此時這個快己調入Cache中，所以第4次訪問命中，實際訪問的Cache地址為0138H。第4個數(shù)訪問結束時，地址陣列的內容與剛才相同。注意：就論壇上對于組相聯(lián)映射的理解存在一些誤區(qū)，這里就來解釋一下，很多同學自己捏造出來了一個組內塊號的概念，覺得Cache地址或者主存地址中會存在一個組內塊號，同學們經(jīng)常問如果沒有這個組內塊號．怎么能在一個組內定位到想要的塊的信息?首先這里我們重新回顧一下組相聯(lián)的概念，組相聯(lián)映射實際上是一種組與組間采用直接映射而組內采用全相聯(lián)映射的映射方式，組間直接映射大多數(shù)人都不會有什么疑問，而組相聯(lián)映射在組內又是怎么找塊的呢?既然剛才說了，組內是采用全相聯(lián)的映射方式，我們不妨再回顧一下全相聯(lián)映射中查找目標塊的方法，即用給定的主存地址的標記號與所有的Cache塊中的標記位進行比較，直到找到一樣的。組相聯(lián)映射也是把這個標記號與組內所有塊的標記號進行比較來查找塊的位置的，當現(xiàn)在比較這塊的標記號和主存地址中的標記號相同時，即代表這塊就是要找的內容。當然，因為一般組內塊數(shù)比較少，可以設立多個比較器進行同時比較，這樣可以加快比較的速度。知識點解析：暫無解析53、若Cache完成存取的次數(shù)為5000次，主存完成存取的次數(shù)為200次。已知Cache存取周期為40ns，主存存取周期為160ns，求該Cache／主存系統(tǒng)的訪問效率。(注：默認為Cache與主存同時訪問)標準答案：Cache的命中率H=Nc／(Nc+Nm)=5000／(5000+200)=5000／5200=25／26，主存慢于Cache的倍率r=Tm／Tc=160ns／40ns=4，訪問效率e=l／[H+r(1一H)]=1／[25／26+4×(1—25／26)]=89．7％。知識點解析：暫無解析考慮某路由器具有下列路由表項：54、假設路由器接收到一個目的地址為142．150．71．132的IP分組，請確定該路由器為該IP分組選擇的下一跳，并解釋說明。標準答案：在使用CIDR時會有多個匹配結果，應從匹配結果選擇具有最長網(wǎng)絡前綴的路由。首先142．150．0．0／16和142．150．71．132是相匹配的，前面16位相同，下面分析其他項：①142．150．64．0／24和142．150．71．132不匹配，因為前24位不相同。②142．150．71．128／28和142．150．71．132的前24位是匹配的，只需看后面4位是否一樣，128的二進制為10000000，132的二進制為10000100，前4位相同，故匹配了28位。③142．150．71．128／30和142．150．71．132的前24位是匹配的，但后面的6位中第6位不一樣，故不匹配。因此，根據(jù)最長網(wǎng)絡前綴的匹配原則，應根據(jù)第2個路由表項轉發(fā)，下一跳路由為B。知識點解析：暫無解析55、在上面的路由器由表中增加一條路由表項，該路由表項使以142．150．71．132為目的地址的IP分組選擇“A”作為下一跳，而不影響其他目的地址的IP分組轉發(fā)。標準答案：欲達到題目的要求，只需構造一個網(wǎng)絡前綴和該地址匹配32位就行了，即針對142．150．71．132的特定主機路由，增加的表項為：網(wǎng)絡前綴142．150．71．132／32、下一跳A。知識點解析：暫無解析56、在上面的路由表中增加一條路由表項，使所有目的地址與該路由表中任何路由表項都不匹配的IP分組被轉發(fā)到下一跳“E”。標準答案：增加1條默認路由：網(wǎng)絡前綴0．0．0．0／0、下一跳E。知識點解析：暫無解析57、將142．150．64．0／24劃分為4個規(guī)模盡可能大的等長子網(wǎng)，給出子網(wǎng)掩碼及每個子網(wǎng)的可分配地址范圍。標準答案：要劃分成4個規(guī)模盡可能大的子網(wǎng)，則需要從主機位中劃出2位作為子網(wǎng)位(22=4，CIDR廣泛使用之后允許子網(wǎng)位可以全0和全1)。各子網(wǎng)地址分別為：142．150．64．00000000；142．150．64．01000000；142．150．64．10000000；142．150．64．11000000。子網(wǎng)掩碼應該為255．255．255．192?？煞峙涞刂贩秶鑼⒅鳈C號中全0和全1的都去掉。因此各子網(wǎng)的地址分配方案如下：子網(wǎng)地址：142．150．64．0／26地址范圍：142．150．64．1～142．150．64．62子網(wǎng)地址：142．150．64．64／26地址范圍：142．150．64．65～142．150．64．126子網(wǎng)地址：142．150．64．128／26地址范圍：142．150．64．129～142．150．64．190子網(wǎng)地址：142．150．64．192／26地址范圍：142．150．64．193～142．150．64．254知識點解析：暫無解析計算機專業(yè)（基礎綜合）模擬試卷第2套一、單選題(本題共40題，每題1.0分，共40分。)1、現(xiàn)在有3個同時到達的作業(yè)J1、J2和J3，它們的執(zhí)行時間分別為T1、T2和T3，且T1＜T2＜T3。如果該系統(tǒng)中有兩個CPU，各自按照單道方式運行且采用短作業(yè)優(yōu)先算法，則平均周轉時間是()。A、(T1+T2+T3)／3B、(2T1+T2+T3)／3C、(T1+2T2+T3)／3D、(2T1+T2+T3)／3或(T1+2T2+T3)／3標準答案：B知識點解析：J1、J2和J3同時在0時刻到達，按短作業(yè)優(yōu)先算法，選擇兒和J2執(zhí)行，則兒和J2等待時間為0。又因為T1＜T2，所以J1先于J2完成，即在T2時刻，釋放CPU，J3開始，則J3的等待時間為T1。然后J2完成，最后J3完成。J1周轉時間為T1。J2周轉時間為T2。J3周轉時間為T1+T3。所以平均周轉時間為(2T1+T2+T3)／3。周轉時間=等待時間+運行時間=結束時間-到達時間2、在下列遍歷算法中，在遍歷序列中葉結點之間的次序可能與其他算法不同的算法是()。A、先序遍歷算法B、中序遍歷算法C、后序遍歷算法D、層次遍歷算法標準答案：D知識點解析：考查各種遍歷算法的特點。先序、中序和后序遍歷算法訪問葉結點的順序都一樣，而層序遍歷算法在二叉樹的葉結點不在同一層上時，可能先遍歷后面的葉結點。因此選D。3、計算機的外圍設備是指()。A、主存儲器B、外存儲器C、除主機外的其他設備D、除CPU外的其他設備標準答案：C知識點解析：外圍設備是相對主機而言，即除CPU和主存儲器外的其他設備。4、某個磁盤系統(tǒng)采用最短尋道時間優(yōu)先(SSTF)磁盤調度算法，假設有一個請求柱面讀寫磁盤請求隊列如下：7、136、58、100、72，當前磁頭位置是80柱面。請問，磁盤總移動距離是()。A、80B、136C、229D、244標準答案：C知識點解析：表2-7是磁盤移動距離。根據(jù)SSTF磁盤調度算法，相應請求順序為72、58、100、136、7。因此，總的移動距離是8+14+42+36+129=229。此類問題的做法是：按照請求磁道的大小順序排列，然后算出兩個方向上最近磁道的距離，決定磁頭移動方向即可。5、計算機要對聲音信號進行處理時，必須將它們轉換成數(shù)字聲音信號。最基本的聲音信號數(shù)字化方法是取樣一量化法。若量化后的每個聲音樣本用2個字節(jié)表示，則量化分辨率是()。A、1／2B、1／1024C、1／65536D、1／131072標準答案：C知識點解析：量化后的每個聲音樣本用2個字節(jié)(16位)表示，216：65536，其倒數(shù)就是量化的分辨率。6、在DMA方式下，數(shù)據(jù)從內存?zhèn)魉偷酵庠O經(jīng)過的路徑是()。A、內存→數(shù)據(jù)總線→外設B、內存→DMAC→外設C、內存→CPU→總線→外設D、外設→內存標準答案：B知識點解析：在DMA方式下，數(shù)據(jù)從主存?zhèn)魉偷酵庠O需要通過DMA控制器中的數(shù)據(jù)緩沖寄存器。7、路由器收到的分組的TTL值為0，那么路由器將()。A、把該分組返回發(fā)送方B、丟棄該分組C、繼續(xù)轉發(fā)D、本地提交標準答案：B知識點解析：本題考查IP報頭字段以及路由轉發(fā)。路由器對TTL為零的數(shù)據(jù)分組進行丟棄處理，并向源主機返回時間超時的ICMP報文，因此答案是B。8、已知[X]補=C6H，計算機的機器字長為8位二進制數(shù)編碼，則[X/4]補為()。A、8CHB、18HC、E3HD、FIH標準答案：C知識點解析：對某個數(shù)據(jù)進行乘2運算相當于對該數(shù)據(jù)二進制數(shù)進行不帶符號位左移一位的運算，對某個數(shù)據(jù)進行除2運算相當于對該數(shù)據(jù)二進制數(shù)進行不帶符號位右移一位的運算。本題中，由于[X/2]補=C6H=(11000110)2，所以求解[X/4]補則需將(11000110)2進行不帶符號位右移一位的運算，其結果是(11100011)2=E3H。如果此題是求[X]補，則需將(11000110)2進行不帶符號位左移一位的運算，其結果是(10001100)2=8CH。9、原碼乘法時，符號位單獨處理，乘積的符號是()。A、兩個操作數(shù)符號相“與”B、兩個操作數(shù)符號相“或”C、兩個操作數(shù)符號相“異或”D、兩個操作數(shù)中絕對值較大數(shù)的符號標準答案：C知識點解析：原碼的符號位為“1”表示負數(shù)，為“0”表示正數(shù)。原碼乘法時，符號位單獨處理，乘積的符號是兩個操作數(shù)符號相“異或”，同號為正，異號為負。[歸納總結]凡是原碼運算，不論加減乘除，符號位都單獨處理，其中乘除運算的結果符號由參加運算的兩個操作數(shù)符號“異或”得到。10、在計算機體系結構中，CPU內部包括程序計數(shù)器PC、存儲器數(shù)據(jù)寄存器MDR、指令寄存器IR和存儲器地址寄存器MAR等。若CPU要執(zhí)行的指令為：MOVR0，#100(即將數(shù)值100傳送到寄存器R0中)，則CPU首先要完成的操作是()。A、100→R0B、100→MDRC、PC→MARD、PC→IR標準答案：C知識點解析：無論運行什么類型的指令，CPU首先需要取指令，取指令階段的第一個操作就是將指令地址(程序計數(shù)器PC中的內容)送往存儲器地址寄存器。取指周期完成的微操作序列是公共的操作，與具體指令無關，取指公共操作如下：(1)將程序計數(shù)器PC中的內容送至存儲器地址寄存器MAR，記作(PC)→MAR；(2)向主存發(fā)讀命令，記作Read；(3)從主存中取出的指令送到存儲器數(shù)據(jù)寄存器MDR，記作M(MAR)→MDR；(4)將MDR的內容送至指令寄存器IR中，記作(MDR)→IR；(5)將PC的內容遞增，為取下一條指令做好準備，記作(PC)+1→PC。11、一個分頁存儲管理系統(tǒng)中，地址長度為32位，其中頁號占10位，則系統(tǒng)中頁面的大小為()。A、28字節(jié)B、210字節(jié)C、222字節(jié)D、232字節(jié)標準答案：C知識點解析：頁內偏移為22位，所以最大長度為222字節(jié)。12、某路由器的路由表如下所示。如果它收到一個目的地址為192．168．10．23的IP數(shù)據(jù)報，那么它為該數(shù)據(jù)報選擇的下一路由器地址為()。A、192．168．1．35B、192．168．2．66C、直接投遞D、丟棄標準答案：B知識點解析：經(jīng)過與路由表比較，發(fā)現(xiàn)該目的地址沒有與之對應的要達到的網(wǎng)絡地址，而在該路由表中有默認路由，根據(jù)相關規(guī)定，只要目的網(wǎng)絡都不匹配，一律選擇默認路由。所以下一跳的地址就是默認路由所對應的IP地址，即192．168．2．66．13、一個UDP用戶的數(shù)據(jù)報的數(shù)據(jù)部分長為8192字節(jié)。那么通過以太網(wǎng)來傳播該UDP數(shù)據(jù)報時，最后一個IP分片的數(shù)據(jù)長度是()。A、1500B、1480C、800D、600標準答案：C知識點解析：UDP頭部長為8字節(jié)，因此該UDP數(shù)據(jù)報總長度為8200字節(jié)，以太網(wǎng)幀的最大數(shù)據(jù)域為1500，再減去20的IP頭部，得到每個IP分片的最大數(shù)據(jù)域長度應該是1480，則最后一個數(shù)據(jù)分片的長度應該是8200-(5×1480)：800字節(jié)。14、已知一算術表達式的中綴形式為A＋B*C—D／E，后綴形式為ABC＋DE／－，其前綴形式為()。A、－A＋B*CD/EB、-A+B*CD/EC、－＋*ABC/DED、－＋A*BC／DE標準答案：D知識點解析：將算術表達式的中綴形式作為一棵二叉樹的中序遍歷序列，將后綴形式作為這棵二叉樹的后序遍歷序列，再由二又樹的中序遍歷序列和后序遍歷序列唯一的確定這棵二叉樹，在對其進行先序遍歷，就可得出算術表達式的前綴形式。15、在操作系統(tǒng)中，P，V操作是一種()。A、機器指令B、系統(tǒng)調用命令C、作業(yè)控制命令D、低級進程通信原語標準答案：D知識點解析：P，V操作是原子操作。16、在操作系統(tǒng)中，用戶在使用I／O設備時，通常采用()。A、物理設備名B、邏輯設備名C、虛擬設備名D、設備序號標準答案：B知識點解析：設備管理通常將邏輯設備和物理設備分開，邏輯設備是用戶使用的。系統(tǒng)設置了一張邏輯設備表，用于將應用程序中所使用的邏輯設備名映射為物理設備名。17、微程序存放在CPU的哪個部件中()。A、主存儲器B、存儲器控制器C、控制存儲器D、輔助存儲器標準答案：C知識點解析：微程序存放在控制存儲器中，選C。注意區(qū)別存控與控存的區(qū)別，控存用來存放微程序，而存控是用來管理協(xié)調CPU、DMA控制器等對主存儲器訪問的部件。18、有一個文件含有10000個文件塊，若將其順序結構存放，則對文件塊順序查找的平均時間為5000個單位。若按索引順序文件的結構存放，每個索引為100個文件塊，則順序查找次數(shù)是()。A、500B、100C、50D、10標準答案：B知識點解析：本題考查的是文件的邏輯結構。順序文件在按順序查找文件內容時，必須按順序一個一個去讀取，最快在第一個就讀取到，最慢一直讀到最后一個文件塊，所以平均為一半，計算結果是10000÷2＝5000。(若采用二分法不會有這么多次)。當采用索引順序文件時，文件的內容已經(jīng)按照索引的關鍵詞排好了序(例如按字母順序等)。并建立了索引表，索引表一般將一定數(shù)量的文件塊組織成一組，本題中以100個一組，所以分成10000÷100＝100組，按順序查找法，查找這100組平均需要100÷2＝50次，找到以后在組內繼續(xù)查找，平均需要100÷2＝50次，所以共需要50＋50＝100次。19、通過改變載波信號的相位值來表示數(shù)字信號1、0的方法是()。A、ASKB、FSKC、PSKD、PPP標準答案：C知識點解析：本題考查數(shù)字調制的基本概念，使用某個頻率的正弦載波，使其的振幅、頻率或相位隨著數(shù)字信號的變化而變化，稱為調制；相反的過程稱為解調；數(shù)字調制具有三種基本形式即移幅鍵控法ASK、移頻鍵控法FSK和移相鍵控法PSK。在ASK方式下，用載波的兩種不同幅度來表示二進制的兩種狀態(tài)。在FSK方式下，用載波頻率附近的兩種不同頻率來表示二進制的兩種狀態(tài)。在PSK方式下，用載波信號相位移動來表示數(shù)據(jù)。因此答案為C。20、某機器指令字長12位，有零地址、一地址、二地址三種指令，地址碼長4位，采用擴展操作碼技術。若二地址指令和一地址指令條數(shù)都取最大值，則該機指令條數(shù)最多為()。A、16B、46C、48D、4366標準答案：B知識點解析：根據(jù)題意，二地址指令的操作碼長度為12-4×2=4，留一個編碼用于擴展，故最多可定義15條二地址指令；一地址指令擴展長度為4位，留一個編碼用于擴展，故最多可定義15條一地址指令；零地址指令可在一地址指令的基礎上擴展4位，故最多可定義16條零地址指令，根據(jù)題意，該機指令條數(shù)最多為(15+15+16=)46條。21、一個文件系統(tǒng)目錄結構如下圖，文件采用的物理結構是鏈式結構，文件F1由500個邏輯記錄組成，每個磁盤塊均可存放20個邏輯記錄，現(xiàn)在欲讀取F1中的第406號記錄，文件系統(tǒng)的根目錄現(xiàn)已存放在內存，則最少需要讀()個磁盤塊，才能取出F1的第406個記錄。A、24B、25C、26D、27標準答案：A知識點解析：在最好的情況下，所找的目錄項都在文件的第一個磁盤塊中，要讀取F1中的第406個記錄，首先從根目錄中找到目錄B的磁盤地址，將其讀入內存(第一次訪盤)；在最好的情況下，能從目錄B的第一個磁盤塊中找出目錄文件E的磁盤地址，并讀入內存(第二次訪盤)；在最好的情況下，能從目錄E的第一個磁盤塊中找出文件F1的文件控制塊的磁盤地址，并讀入內存(第三次訪盤)，文件F1由500個邏輯記錄構成，每個磁盤塊均可存放20個邏輯記錄，因此文件F1需要25個磁盤塊，第406個記錄在第21個磁盤塊上，讀取第406個記錄需要21次訪盤，總共要24次訪盤。22、下列敘述中，正確的是()。Ⅰ．非空循環(huán)單鏈表head的尾結點p滿足p→next=headⅡ．帶頭結點的循環(huán)單鏈表的頭指針為head，如果head→next→next→next=head成立，則該單鏈表的長度為3Ⅲ．靜態(tài)鏈表中的指針表示的是下一個元素在數(shù)組中的位置Ⅳ．將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法時間復雜度為O(1)A、僅Ⅰ、Ⅱ、ⅢB、Ⅰ、Ⅱ、Ⅲ、ⅣC、僅Ⅰ、ⅢD、僅Ⅰ、Ⅲ、Ⅳ標準答案：C知識點解析：Ⅰ：非空循環(huán)單鏈表的尾結點指針應該指向鏈表頭，即p→next=head，故Ⅰ正確。Ⅱ：head指向頭結點，head→next就指向第一個結點。既然head→next→next→Rext=head，說明此循環(huán)鏈表共有3個結點(包含頭結點)，而單鏈表中增加頭結點僅儀是為了更方便地進行插入和刪除操作，它并不存儲線性表的元素，不能算為單鏈表結點，故此單鏈表的長度為2，故Ⅱ錯誤。Ⅲ：靜態(tài)鏈表中的指針所存儲的不再是鏈表中的指針域，而是其下一個結點在數(shù)組中的位置，即數(shù)組下標，故Ⅲ正確。Ⅳ：將鏈表連接起來只需O(1)的操作，但找到具有m個結點鏈表的尾結點需遍歷該鏈表，所以時間復雜度應該為O(m)，故Ⅳ錯誤。23、在IP數(shù)據(jù)報報頭中有兩個有關長度的字段，一個為報頭長度(IHL)字段，一個為總長度(totallength)字段，下面說法正確的是()。A、報頭長度字段和總長度字段都以8比特為計數(shù)單位B、報頭長度字段以8比特為計數(shù)單位，總長度字段以32比特為計數(shù)單位C、報頭長度字段以32比特為計數(shù)單位，總長度字段以8比特為計數(shù)單位D、報頭長度字段和總長度字段都以32比特為計數(shù)單位標準答案：C知識點解析：本題考查IPv4報文結構，報文長度也就是首部長度，占4個bit，以4字節(jié)為單位，必須是4字節(jié)的整數(shù)倍，而總長度是首部和數(shù)據(jù)之和的長度，單位是字節(jié)，因此答案是C。24、為了保證操作系統(tǒng)本身的安全，()是必須加以保護的。A、從內核模式轉換到用戶模式B、從存儲操作系統(tǒng)內核的空間讀取數(shù)據(jù)C、從存儲操作系統(tǒng)內核的空間讀取指令D、打開定時器標準答案：D知識點解析：打開定時器會影響系統(tǒng)的時間。25、設數(shù)組S[n]作為兩個棧S1和S2的存儲空間，對任何一個棧只有當S[n]全滿時才不能進行進棧操作。為這兩個棧分配空間的最佳方案是()。A、S1的棧底位置為O，S2的棧底位置為n一1B、S1的棧底位置為O，S2的棧底位置為n／2C、S1的棧底位置為O，S2的棧底位置為nD、S1的棧底位置為0，S2的棧底位置為1標準答案：A知識點解析：利用棧底位置不變的特性，可讓兩個順序棧共享一個一維數(shù)據(jù)空間，以互補余缺，實現(xiàn)方法是：將兩個棧的棧底位置分別設在存儲空間的兩端，讓它們的棧頂各自向中間延伸。這樣，兩個棧的空間就可以相互調節(jié)，只有在整個存儲空間被占滿時才發(fā)生上溢，這樣一來產(chǎn)生上溢的概率要小得多。26、若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和f．ront的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和Iront的值分別是()。A、1和5B、2和4C、4和2D、5和1標準答案：B知識點解析：出隊1個元素后，front=(front+1)％MAXQSIZE，front的值是4；入隊兩個元素后，rear=(rear+2)％MAXQSIZE，rear的值是2。27、下列說法中，錯誤的是()。Ⅰ．假設幀序號有3位，采用連續(xù)ARQ協(xié)議，發(fā)送窗口的最大值為4Ⅱ．對于窗口大小為n的滑動窗口，最多可以有n幀已發(fā)送但沒有確認Ⅲ．在后退N幀協(xié)議中，如果發(fā)送窗口的大小是16，那么至少需要4位的序列號才能保證協(xié)議不出錯A、僅Ⅰ、ⅡB、僅ⅢC、僅Ⅱ、ⅢD、Ⅰ、Ⅱ、Ⅲ標準答案：D知識點解析：Ⅰ：連續(xù)ARQ協(xié)議包括后退N幀協(xié)議和選擇重傳協(xié)議。如果幀序號為3位，當采用后退N幀協(xié)議時，發(fā)送窗口的最大值為23-1=7；當采用選擇重傳協(xié)議時，發(fā)送窗口的最大值為23-1=4，故Ⅰ錯誤。Ⅱ：在連續(xù)ARQ協(xié)議中，如果總的窗口大小為n，發(fā)送窗口的大小最大為n-1(當采用后退N幀協(xié)議時可以達到)。例如：假設窗口大小為8(0～7)，如果發(fā)送窗口大小為8，則當0～7號幀都發(fā)出去時，接收方已經(jīng)收到了，并且發(fā)出確認。但是發(fā)送方卻沒有收到確認，導致0～7號幀超時重傳，而此時接收方就判斷不出這個是重傳的還是新一輪的幀，導致錯誤，故Ⅱ錯誤。Ⅲ：首先需要清楚后退N幀協(xié)議的最大發(fā)送窗口為2n-1(其中n為幀號的位數(shù))，題目中已經(jīng)說明發(fā)送窗口的大小為16，也就是說如果要使得協(xié)議不出錯，必須滿足16≤2n-1，所以n至少要等于5，故Ⅲ錯誤。28、設n、m為一棵二叉樹上的兩個結點，在中序遍歷時，n在m前的條件是()。A、n在m右方B、n是m祖先C、n在m左方D、n是m子孫標準答案：C知識點解析：中序遍歷時，先訪問左子樹，再訪問根結點。n在m前，則n必須在m的左子樹中。因此本題答案為C。29、用直接插入排序對下面4個序列進行遞增排序，元素比較次數(shù)最少的是()。A、94，32，40，90，80，46，21，69B、32，40，21，46，69，94，90，80C、21，32，46，40，80，69，90，94D、90，69，80，46，21，32，94，40標準答案：C知識點解析：對于直接插入排序，原始序列越接近有序，則比較次數(shù)越少，觀察序列，C選項最接近有序。說明：本題目測即可，如果要嚴格來比較，則可用線性代數(shù)中求逆序數(shù)的方法，序列逆序數(shù)越小則越接近有序。對于序列中某個元素a，其逆序數(shù)為序列中a之后比a小的元素的個數(shù)，整個序列的逆序數(shù)為所有元素逆序數(shù)之和。對于A，各元素逆序數(shù)為94：7；32：1；40：1；90：4；80：3；46：1；21：0；69：0。因此，序列A的逆序數(shù)為7+1+1+4+3+1+0+0=17。對于B，各元素逆序數(shù)為32：1；40：1；21：0；46：0；69：0；94：2；90：1；80：0。因此，序列A的逆序數(shù)為1+1+0+0+0