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

計(jì)算機(jī)專業(yè)（基礎(chǔ)綜合）模擬試卷2（共6套）（共300題）計(jì)算機(jī)專業(yè)（基礎(chǔ)綜合）模擬試卷第1套一、單選題(本題共40題，每題1.0分，共40分。)1、交互式操作系統(tǒng)中為了能使多個(gè)用戶同時(shí)與系統(tǒng)進(jìn)行交互，最關(guān)鍵的問題是()。A、計(jì)算機(jī)要有足夠快的運(yùn)行速度B、能快速進(jìn)行內(nèi)外存之間的信息交換C、系統(tǒng)能夠及時(shí)接收多個(gè)用戶的輸入D、一段時(shí)間內(nèi)所有用戶的程序都能運(yùn)行標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：交互式操作系統(tǒng)有時(shí)又稱為分時(shí)操作系統(tǒng)，它將時(shí)間分成一個(gè)個(gè)的片段，輪流分給每個(gè)用戶，用戶將分到的時(shí)間片段用于本進(jìn)程的運(yùn)行。交互式系統(tǒng)強(qiáng)調(diào)交互，所以，對(duì)用戶的輸入及時(shí)響應(yīng)就顯得非常重要，而分時(shí)方式最能夠及時(shí)地響應(yīng)用戶的請(qǐng)求，因?yàn)榉謺r(shí)系統(tǒng)能夠頻繁地給多個(gè)用戶分配時(shí)間。因此如何保證操作系統(tǒng)能及時(shí)地接收多個(gè)用戶的輸入就成了交互式操作系統(tǒng)設(shè)計(jì)的目標(biāo)，也是交互式系統(tǒng)需要解決的關(guān)鍵問題。2、TCP／IP模型由以下層次構(gòu)成()。A、物理層、數(shù)據(jù)鏈路層、網(wǎng)絡(luò)層、傳輸層、會(huì)話層、表示層、應(yīng)用層B、網(wǎng)絡(luò)接口層、互聯(lián)網(wǎng)層、傳輸層、應(yīng)用層C、物理層、數(shù)據(jù)鏈路層、網(wǎng)絡(luò)層、傳輸層、應(yīng)用層D、局域網(wǎng)層、廣域網(wǎng)層、互聯(lián)網(wǎng)層標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：A屬于OSI的7層模型。3、在因特網(wǎng)中，以下說法正確的是()。I．主機(jī)通常需要實(shí)現(xiàn)TCP協(xié)議Ⅱ．路由器必須實(shí)現(xiàn)TCP協(xié)議Ⅲ．主機(jī)必須實(shí)現(xiàn)IP協(xié)議Ⅳ．路由器必須實(shí)現(xiàn)IP協(xié)議A、I、Ⅱ和ⅢB、I、Ⅱ和ⅣC、I、Ⅲ和ⅣD、Ⅱ、Ⅲ和Ⅳ標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：主機(jī)是終端設(shè)備，需實(shí)現(xiàn)整個(gè)五層協(xié)議，而路由器是網(wǎng)絡(luò)層設(shè)備，僅需實(shí)現(xiàn)網(wǎng)絡(luò)層及其以下層的協(xié)議即物理層，數(shù)據(jù)鏈路層和網(wǎng)絡(luò)層三個(gè)層次的協(xié)議。而TCP是傳輸層協(xié)議，路由器無需實(shí)現(xiàn)此協(xié)議故排除Ⅱ，即A、B、D均錯(cuò)。4、已知小寫英文字母“a”的ASCII碼值為61H，現(xiàn)字母“g”被存放在某個(gè)存儲(chǔ)單元中，若采用偶校驗(yàn)(假設(shè)最高位作為校驗(yàn)位)，則該存儲(chǔ)單元中存放的十六進(jìn)制數(shù)是()。A、66HB、E6HC、67HD、E7H標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：因?yàn)椤癮”的ASCII碼值為61H，而“g”是第7號(hào)字母，所以“g”的ASCII碼值應(yīng)為67H＝1100111B。標(biāo)準(zhǔn)的ASCII碼為7位，在7位數(shù)前面增加1位校驗(yàn)位?，F(xiàn)“g”的ASCIl碼中1的個(gè)數(shù)有5個(gè)，按照偶校驗(yàn)規(guī)則，存儲(chǔ)單元中存放的是整個(gè)校驗(yàn)碼(包括校驗(yàn)位和信息位)，為11100111B＝E7H。[歸納總結(jié)]此題涉及兩個(gè)知識(shí)點(diǎn)，第一是ASCII編碼表順序排列問題，第二是奇偶檢驗(yàn)碼的編碼規(guī)則問題。由若干位有效信息(如一個(gè)字節(jié))，再加上一個(gè)二進(jìn)制位(校驗(yàn)位)組成校驗(yàn)碼，偶校驗(yàn)就是整個(gè)校驗(yàn)碼中“1”的個(gè)數(shù)為偶數(shù)個(gè)。[解題技巧]在ASCII碼中，數(shù)字和英文字母都是按順序排列的，只要知道其中一個(gè)數(shù)字或英文字母的二進(jìn)制代碼，不要查表就可以推導(dǎo)出其他數(shù)字或字母的二進(jìn)制代碼。此題容易誤選C，這是因?yàn)椤癵”的ASCII碼中確實(shí)為67H，但整個(gè)校驗(yàn)碼中1的個(gè)數(shù)必須是偶數(shù)個(gè)，所以正確選項(xiàng)為D。5、[x]補(bǔ)=1．x1x2)x3x4，則當(dāng)滿足()時(shí)，x>一1／2成立。A、x1必為0，x2～x4至少有一個(gè)為1B、x1必為0，x2～x4任意C、x1必為1，x2～x4至少有一個(gè)為1D、x1必為1，x2～x4任意標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：可采用排除法，1．0001符合A、B選項(xiàng)的要求，其值一15／16<一1／2，排除A、B；1．1000符合D選項(xiàng)的要求，其值=一1／2，排除D；故選C。6、3個(gè)進(jìn)程共享4個(gè)同類資源，這些資源的分配與釋放只能一次一個(gè)。已知每一個(gè)進(jìn)程最多占有兩個(gè)該類資源，則該系統(tǒng)()。A、有某進(jìn)程可能用于得不到該類資源B、必然有死鎖C、進(jìn)程請(qǐng)求該類資源立刻能得到D、必然無死鎖標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：根據(jù)題意，則任意時(shí)刻總有一個(gè)進(jìn)程可以獲得其所有資源，從而能在有限的時(shí)間內(nèi)運(yùn)行完畢，所以系統(tǒng)那個(gè)必然無死鎖。7、數(shù)據(jù)序列F={2，1，4，9，8，10，6，20)只能是下列排序算法中的()的兩趟排序后的結(jié)果。A、快速排序B、冒泡排序C、選擇排序D、插入排序標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：對(duì)于后三種排序方法兩趟排序后，序列的首部或尾部的兩個(gè)元素應(yīng)是有序的兩個(gè)極值，而給定的序列不滿足。8、虛擬頁式存儲(chǔ)管理中，CPU須具備必要的物理硬件的支持，而不是必需的單元是()。A、缺頁中斷機(jī)構(gòu)B、地址加法器C、cacheD、地址寄存器標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：在虛擬頁式存儲(chǔ)管理中，除了有主存和輔存以外，為滿足虛擬技術(shù)，CPU還需要有缺頁中斷機(jī)制；為滿足頁式存儲(chǔ)管理，CPU中需要有地址加法器和地址寄存器來計(jì)算頁表到頁框的映射，而cache并不是必需的，因?yàn)閏ache的存在只是提高了CPU尋址的效率，并不是虛擬頁式存儲(chǔ)技術(shù)的重要單元，缺少cache，CPU每次執(zhí)行一個(gè)雙字的指令(以32位為例)或取一個(gè)數(shù)據(jù)均需要二次訪問內(nèi)存，當(dāng)然這是很不利的，可能會(huì)實(shí)際上造成虛擬頁式的使用障礙。增加了cache，使得虛擬頁式存儲(chǔ)技術(shù)的實(shí)際使用提供了方便。9、實(shí)時(shí)系統(tǒng)中的進(jìn)程調(diào)度，通常采用()算法。A、先來先服務(wù)B、時(shí)間片輪轉(zhuǎn)C、搶占式的優(yōu)先數(shù)高者優(yōu)先D、響應(yīng)比高者優(yōu)先標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：實(shí)時(shí)系統(tǒng)為了滿足用戶實(shí)時(shí)交互以及對(duì)重要事件的迅速反應(yīng)，所以采取搶占式的優(yōu)先數(shù)高者優(yōu)先。10、最好情況下的算法時(shí)間復(fù)雜度為O(n)的是()。A、插入排序B、歸并排序C、快速排序D、堆排序標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：直接插入排序在最好情況下，即待排序列已按關(guān)鍵碼有序時(shí)，每趟操作只需1次比較，不需移動(dòng)?？偙容^次數(shù)=n-1次。所以時(shí)間復(fù)雜度為O(n)。歸并排序和堆排序在平均情況和最好情況下的時(shí)間復(fù)雜度為O(nlogn)?？焖倥判蛟谄骄闆r下的時(shí)間復(fù)雜度為O(nlogn)，最壞情況下的時(shí)間復(fù)雜度為O(n2)。11、浮點(diǎn)數(shù)加減運(yùn)算過程一般包括對(duì)階、尾數(shù)運(yùn)算、規(guī)格化、舍入和判斷溢出等步驟。設(shè)浮點(diǎn)數(shù)的階碼和尾數(shù)均采用補(bǔ)碼表示，且位數(shù)分別為5位和7位(均含2位符號(hào)位)。若有兩個(gè)數(shù)X=27×29／32，Y=5×5／8，則用浮點(diǎn)加法計(jì)算X+Y的最終結(jié)果是()。A、001111100010B、001110100010C、010000010001D、發(fā)生溢出標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：根據(jù)題意，X可記為00，111；00，11101(分號(hào)前為階碼，分號(hào)后為尾數(shù))，Y可記為00，101；00，10100；首先對(duì)階，X、Y階碼相減，即00，111-00，101=00，111+11，011=00，010(最高位進(jìn)位自然丟棄)，可知X的階碼比Y的階碼大2，根據(jù)小階向大階看齊的原則，將Y的階碼加2，尾數(shù)右移2位，得Y為00，111，00，00101；尾數(shù)相加，即00，11101+00，00101=01，00010，尾數(shù)相加結(jié)果符號(hào)位為01，故需進(jìn)行右規(guī)；規(guī)格化，將尾數(shù)右移1位，階碼加1，得X+Y為01，000；00，10001，階碼符號(hào)位為01，說明發(fā)生溢出。12、下列關(guān)于無向連通圖特性的敘述中，正確的是()。Ⅰ．所有頂點(diǎn)的度之和為偶數(shù)Ⅱ．邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1Ⅲ．至少有一個(gè)頂點(diǎn)的度為1A、只有ⅠB、只有ⅡC、Ⅰ和ⅡD、Ⅰ和Ⅲ標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：不正確的是C，深度優(yōu)先搜索和廣度優(yōu)先搜索的時(shí)間算雜度相同，均為O(n+e)。13、下列選項(xiàng)中，描述浮點(diǎn)數(shù)操作速度的指標(biāo)是()。A、MIPSB、CPIC、IPCD、MFLOP標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：衡量計(jì)算機(jī)系統(tǒng)速度的指標(biāo)中，CPI表示每條指令平均所需的時(shí)鐘周期數(shù)；IPC表示每個(gè)時(shí)鐘周期平均執(zhí)行的指令條數(shù)；MIPS表示每秒百萬條指令數(shù)；MFLOP常用于衡量浮點(diǎn)運(yùn)算速度，表示每秒百萬條浮點(diǎn)運(yùn)算數(shù)。14、一個(gè)文件的絕對(duì)路徑名的出發(fā)點(diǎn)是()。A、當(dāng)前目錄B、根目錄C、磁盤盤符D、公共目錄標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：本題考查文件路徑名的概念。文件的路徑名是從根目錄到目標(biāo)文件所經(jīng)歷的路徑上各符號(hào)名的集合。路徑名有二種形式，第一種是絕對(duì)路徑名，它由根目錄出發(fā)，沿著目錄的路徑直到文件，絕對(duì)路徑名總是從根目：錄出發(fā)，并且是唯一的。第二種是相對(duì)路徑名，它與工作目錄(也稱當(dāng)前目錄)一起使用，用戶一般預(yù)先指定一個(gè)目錄為當(dāng)前目錄，這時(shí)，所有的路徑名均從當(dāng)前目錄出發(fā)，這樣的路徑名，只要不是從根目錄出發(fā)的，都稱為相對(duì)路徑名。15、A、聚合到202．87．96．0／21B、聚合到202．87．104．0／21C、聚合到202．87．96．O／19D、不可以聚合標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：因?yàn)樗鼈兊那皟蓚€(gè)字節(jié)都相同，第三個(gè)字節(jié)的前三位都是001，所以它們可以聚合成202．87．96．0／19。16、考慮一條具有10ms往返時(shí)延的線路上采用慢開始擁塞控制而不發(fā)生網(wǎng)絡(luò)擁塞的情況。接收窗口24KB，且報(bào)文段的最大長為2KB。那么需要()發(fā)送第一個(gè)完全窗口。A、20msB、30msC、40msD、50ms標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：已知最大報(bào)文段式2KB，開始的突發(fā)量分別是2KB、4KB、8KB、16KB，接下來即為24KB，因?yàn)椴荒艹^接收窗口，因此，需要40ms才能發(fā)送第一個(gè)完全窗口。17、FTP客戶和服務(wù)器之間一般需要建立的連接個(gè)數(shù)是()。A、1B、2C、3D、4標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：本題考查FTP的基本原理，F(xiàn)TP客戶與服務(wù)器之間一般要建立兩個(gè)連接，一個(gè)是控制連接，一個(gè)是數(shù)據(jù)連接，控制連接在整個(gè)會(huì)話期間一直保持打開，F(xiàn)TP客戶發(fā)出的傳送請(qǐng)求通過控制連接發(fā)送給服務(wù)器端的控制進(jìn)程，但控制連接不用來傳送文件。實(shí)際用于傳輸文件的是“數(shù)據(jù)連接”。服務(wù)器端的控制進(jìn)程在接收到FTP客戶發(fā)送來的文件傳輸請(qǐng)求后就創(chuàng)建“數(shù)據(jù)傳送進(jìn)程”和“數(shù)據(jù)連接”，用來連接客戶端和服務(wù)器端的數(shù)據(jù)傳送進(jìn)程。數(shù)據(jù)傳送進(jìn)程實(shí)際完成文件的傳送，在傳送完畢后關(guān)閉“數(shù)據(jù)傳送連接"并結(jié)束運(yùn)行。因此答案是B。18、若循環(huán)隊(duì)列以數(shù)組Q[0．．m-1]作為其存儲(chǔ)結(jié)構(gòu)，變量rear表示循環(huán)隊(duì)列中的隊(duì)尾元素的實(shí)際位置，其移動(dòng)按rear=(rear+1)MODm進(jìn)行，變量length表示當(dāng)前循環(huán)隊(duì)列中的元素個(gè)數(shù)，則循環(huán)隊(duì)列的隊(duì)首元素的實(shí)際位置是()。A、rear-lengthB、(rear-length+m)MODmC、(1+rear+m-length)MODmD、m-length標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：按照循環(huán)隊(duì)列的定義，因?yàn)樵匾苿?dòng)按照rear=(rear+1)MODm進(jìn)行，則當(dāng)數(shù)組Q[m一1]存放了元素之后，下一個(gè)入隊(duì)的元素將存放到Q[0]中，因此隊(duì)列的首元素的實(shí)際位置是(rear—length+1+m)MODm。19、馮.諾依曼計(jì)算機(jī)中，取指令的操作()。A、由機(jī)器指令控制完成B、由微指令控制完成C、不需任何指令控制，由控制器自動(dòng)完成D、以上說法都不正確標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：馮.諾依曼計(jì)算機(jī)中，控制器能夠根據(jù)程序計(jì)數(shù)器PC的內(nèi)容自動(dòng)完成取指令的操作，取指過程不需要任何指令的控制。20、若G是一個(gè)具有36條邊的非連通無向圖(不含自回路和多重邊)，則圖G的結(jié)點(diǎn)數(shù)至少是()。A、11B、10C、9D、8標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：n個(gè)結(jié)點(diǎn)的無向圖中，邊數(shù)e≤n(n－1)／2，將e＝36代入，有n≥9，現(xiàn)已知無向圖非連通，則n＝10。21、進(jìn)程從運(yùn)行狀態(tài)轉(zhuǎn)換為就緒狀態(tài)的可能原因是()。A、被調(diào)度程序選中占用處理機(jī)B、等待某一事件C、等待的事件已經(jīng)發(fā)生D、時(shí)間片用完標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：就緒狀態(tài)是指一個(gè)進(jìn)程獲得了除處理機(jī)以外的一切資源，當(dāng)?shù)玫秸{(diào)度時(shí)，就由就緒狀態(tài)轉(zhuǎn)換為運(yùn)行狀態(tài)；運(yùn)行狀態(tài)就是一個(gè)進(jìn)程在處理機(jī)上正在運(yùn)行。當(dāng)初與運(yùn)行狀態(tài)的進(jìn)程在運(yùn)行過程中所分配的時(shí)間片用完，則會(huì)被強(qiáng)制撤離處理機(jī)，以便調(diào)度其他進(jìn)程運(yùn)行。由于原先運(yùn)行的進(jìn)程是非自愿地離開運(yùn)行狀態(tài)，所以沒有其他的事件相關(guān)，只有繼續(xù)在就緒隊(duì)列中等候下一次的調(diào)度，所以D是正確的。A的情形是由就緒狀態(tài)轉(zhuǎn)換為運(yùn)行狀態(tài)；B的情形是由運(yùn)行狀態(tài)轉(zhuǎn)換為阻塞狀態(tài)；C的情形是由阻塞狀態(tài)轉(zhuǎn)換為就緒狀態(tài)，故選D。本題主要考查學(xué)生對(duì)進(jìn)程狀態(tài)以及相互轉(zhuǎn)換的關(guān)系，難度也并不高，改變一下問題的問法，A，B，C三個(gè)答案均會(huì)有可能。22、在操作系統(tǒng)中，要對(duì)并發(fā)進(jìn)程進(jìn)行同步的原因是()。A、進(jìn)程的有限時(shí)間性B、進(jìn)程具有動(dòng)態(tài)性C、并發(fā)進(jìn)程推進(jìn)的不確定性D、進(jìn)程具有結(jié)構(gòu)性標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：進(jìn)程同步是指多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上的協(xié)調(diào)。這些進(jìn)程會(huì)互相競爭以及相互合作，在一些關(guān)鍵點(diǎn)上可能需要前后順序操作。由于并發(fā)造成系統(tǒng)的不確定性，運(yùn)行中不知誰先誰后，因此當(dāng)二個(gè)進(jìn)程需要協(xié)調(diào)時(shí)必須互相等待或者互通消息。由于不確定性，造成并發(fā)執(zhí)行的進(jìn)程在執(zhí)行次序上本身無規(guī)律可循，因此需要系統(tǒng)對(duì)這些相關(guān)進(jìn)程進(jìn)行同步。由此，正確答案應(yīng)為C。23、如圖6-1所示一臺(tái)路由器連接3個(gè)以太網(wǎng)，假設(shè)主機(jī)C上要發(fā)送一個(gè)IP分組，使得主機(jī)D和主機(jī)E都會(huì)接收它，而子網(wǎng)3和子網(wǎng)4上的主機(jī)都不會(huì)接收它，那么該IP分組的目標(biāo)IP地址是()。A、255．255．255．255B、130．130．20．255C、127．0．0．1D、130．130．19．255標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：本題考查路由器的功能和IPv4地址的特點(diǎn)，主機(jī)D屬于子網(wǎng)130．130．19．0，主機(jī)E屬于130．130．20．0，分別屬于不同的網(wǎng)絡(luò)，可以同時(shí)接收的IP分組必定是廣播報(bào)文，題目又要求該廣播報(bào)文不能轉(zhuǎn)發(fā)到子網(wǎng)3，和子網(wǎng)4，則這個(gè)廣播報(bào)文必定是有限廣播地址255．255．255．255，路由器可以割斷廣播報(bào)，因此答案是A。24、若進(jìn)棧序列為a，b，c，則通過出棧操作可能得到a，b，c的不同排列個(gè)數(shù)為()。A、4B、5C、6D、7標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：若進(jìn)棧序列為a，b，c，可以考慮所有進(jìn)棧出棧情況，則可能得到a，b，c的出棧序列是abc，acb，bac，bca，cba。25、某計(jì)算機(jī)字長8位，采用補(bǔ)碼表示小數(shù)。若某數(shù)真值為-0．1001，則它在該計(jì)算機(jī)中的機(jī)器數(shù)形式為()。A、10111B、10110111C、10111000D、10110000標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：-0．1001=-0．1001000，將-0．1001000連符號(hào)位在內(nèi)取反加1即可得-0．1001000的補(bǔ)碼形式：1．0111000。26、在補(bǔ)碼表示的機(jī)器中，若寄存器A中原存的數(shù)為9EH，現(xiàn)存的數(shù)為CFH，則表明執(zhí)行的一條指令是()。A、算術(shù)左移B、邏輯左移C、算術(shù)右移D、邏輯右移標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：寄存器A中原存內(nèi)容10011110，現(xiàn)存內(nèi)容11001111，說明執(zhí)行了一條算術(shù)右移指令。27、在Internet上有許多協(xié)議，下面的選項(xiàng)中能夠正確表示協(xié)議層次關(guān)系的是()。A、

B、

C、

D、

標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：本題考查各種協(xié)議所處于的層次，選項(xiàng)B中ARP協(xié)議是處于網(wǎng)絡(luò)層，不是和TCP一樣處于傳輸層，選項(xiàng)C中UDP協(xié)議是和TCP協(xié)議一起處于傳輸層，選項(xiàng)D中LLC不是和IP一起處于網(wǎng)絡(luò)層，而是在MAC層之上共同組成了數(shù)據(jù)鏈路層，因此答案是A。28、判斷有向圖是否存在回路，除了可以利用拓?fù)渑判蚍椒ㄍ猓€可以利用的是()。A、求關(guān)鍵路徑的方法B、求最短路徑的迪杰斯特拉方法C、深度優(yōu)先遍歷算法D、廣度優(yōu)先遍歷算法標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：當(dāng)有向圖中無回路時(shí)，從某頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷時(shí)，出棧的順序?yàn)槟嫦虻耐負(fù)湫蛄小?9、若某條指令的操作數(shù)的地址就包含在指令中，則這條指令的尋址方式是()。A、直接尋址B、立即尋址C、寄存器尋址D、間接尋址標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：若指令中包含著操作數(shù)的有效地址，則指令的尋址方式就是直接尋址。30、如果一臺(tái)主機(jī)的IP地址為192．168．0．10，子網(wǎng)掩碼為255．255．255．224，那么主機(jī)所在網(wǎng)絡(luò)的網(wǎng)絡(luò)號(hào)占IP地址的位數(shù)是()。A、24B、25C、27D、28標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：本題考查子網(wǎng)劃分，224的二進(jìn)制是11100000，因此子網(wǎng)占3個(gè)bit，網(wǎng)絡(luò)號(hào)是192．168．0．111，因此是27位，答案是C。31、下列選項(xiàng)中，降低進(jìn)程優(yōu)先級(jí)的合理時(shí)機(jī)是()。A、進(jìn)程時(shí)間片用完B、進(jìn)程剛完成I／O，進(jìn)入就緒隊(duì)列C、進(jìn)程長期處于就緒隊(duì)列D、進(jìn)程從就緒狀態(tài)轉(zhuǎn)換為運(yùn)行狀態(tài)標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：進(jìn)程時(shí)間片用完可以降低其優(yōu)先級(jí)，完成I／O的進(jìn)程應(yīng)該提升其優(yōu)先級(jí)，處于就緒隊(duì)列等待調(diào)度的進(jìn)程一般不會(huì)改變其優(yōu)先級(jí)。這類題目一般在采用多級(jí)反饋隊(duì)列調(diào)度算法的系統(tǒng)中應(yīng)用。其具體算法為：設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)。第一個(gè)隊(duì)列的優(yōu)先級(jí)最高，第二隊(duì)次之，其余隊(duì)列優(yōu)先級(jí)依次降低。賦予各個(gè)隊(duì)列中進(jìn)程運(yùn)行時(shí)間片的大小也各不相同。在優(yōu)先級(jí)越高的隊(duì)列中，每個(gè)進(jìn)程的運(yùn)行時(shí)間片就越小。當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊(duì)列的末尾，也就是優(yōu)先級(jí)最高，按先來先服務(wù)的原則排隊(duì)等待調(diào)度。當(dāng)輪到該進(jìn)程運(yùn)行時(shí)，如能在該時(shí)間片內(nèi)完成，便可準(zhǔn)備撤離系統(tǒng)。如果它在一個(gè)時(shí)間片結(jié)束時(shí)尚未完成，調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第二隊(duì)列的末尾，此時(shí)其優(yōu)先級(jí)降低了一級(jí)，再同樣地按先來先服務(wù)原則等待調(diào)度運(yùn)行。如果它在第二隊(duì)列中運(yùn)行一個(gè)時(shí)間片后仍未完成，再以同樣方法，將它轉(zhuǎn)入第三隊(duì)列。它的優(yōu)先級(jí)又降低了一級(jí)。如此下去，當(dāng)一個(gè)長作業(yè)從第一隊(duì)列降到最后一個(gè)隊(duì)列后，在最后一個(gè)隊(duì)列中，使用時(shí)間片輪轉(zhuǎn)方式運(yùn)行。此時(shí)優(yōu)先級(jí)也就再也無法降低了。僅當(dāng)?shù)谝魂?duì)列空閑時(shí)，調(diào)度程序才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行。僅當(dāng)?shù)谝恢罭隊(duì)列均為空時(shí)，才會(huì)調(diào)度第N+1隊(duì)列中的進(jìn)程運(yùn)行。如果處理機(jī)正在第J隊(duì)列中為某進(jìn)程服務(wù)時(shí)，又有新進(jìn)程進(jìn)入優(yōu)先級(jí)較高的隊(duì)列，那么要考慮是否是可搶先式調(diào)度算法，若是，則新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)，而由調(diào)度程序把正在運(yùn)行的進(jìn)程放回到第J隊(duì)列，將處理機(jī)分配給新進(jìn)程。若不是，則需要等待直到當(dāng)前的進(jìn)程完成它的時(shí)間片再調(diào)度，此時(shí)會(huì)產(chǎn)生優(yōu)先級(jí)翻轉(zhuǎn)的情形，亦即在處理機(jī)上運(yùn)行的進(jìn)程其優(yōu)先級(jí)低于就緒隊(duì)列中的某個(gè)進(jìn)程。這種情形非常糟糕，極易引起死鎖。一般應(yīng)該避免。32、CSMA／CD以太網(wǎng)中，發(fā)生沖突后，重發(fā)前的退避時(shí)間最大是()。A、65536個(gè)時(shí)間片B、65535個(gè)時(shí)間片C、1024個(gè)時(shí)間片D、1023個(gè)時(shí)間片標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：考查CSMA／CD的退避算法，這里的時(shí)間片就是基本退避時(shí)間，確定基本退避時(shí)間，一般是取為爭用期2τ。定義重傳次數(shù)k，k≤10，即k=Min[重傳次數(shù)，10]從整數(shù)集合[0，1，…，(2k-1)]中隨機(jī)地取出一個(gè)數(shù)，記為r。重傳所需的時(shí)延就是r倍的基本退避時(shí)間。當(dāng)重傳達(dá)16次仍不能成功時(shí)即丟棄該幀，并向高層報(bào)告。本題中重傳次數(shù)的最大值為10，退避時(shí)間最大就是210-1=1023個(gè)時(shí)間片，因此答案是D。33、某操作系統(tǒng)的文件管理采用直接索引和多級(jí)索弓I混合方式，文件索引表共有10項(xiàng)，其中前8項(xiàng)是直接索引項(xiàng)，第9項(xiàng)是一次間接索引項(xiàng)，第10項(xiàng)是二次間接索引項(xiàng)，假定物理塊的大小是1K，每個(gè)索引項(xiàng)占用4個(gè)字節(jié)，則該文件系統(tǒng)中最大的文件可以達(dá)到()。A、65800KB、32768KC、651793KD、32904K標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：多級(jí)索引的邏輯并不復(fù)雜，二級(jí)間接索引表最多有256張，但是并沒有用滿。只用了255張，而且第255張中也沒有全部用足256條表項(xiàng)。計(jì)算時(shí)加以仔細(xì)小心，一般不會(huì)有太多變化，但是對(duì)多級(jí)索引的方法一定要掌握。(1)直接索引為8*1K=8K，一級(jí)間接索引為(1K／4B)*1K=256K；二級(jí)間接索引為(1K／4B)*(1K／4B)*1K=65536K。(2)最大的文件將所有存儲(chǔ)塊占用，則需要65536K+256K+8K=65800K。34、某機(jī)采用計(jì)數(shù)器定時(shí)查詢方式來進(jìn)行總線判優(yōu)控制，共有4個(gè)主設(shè)備競爭總線使用權(quán)，當(dāng)計(jì)數(shù)器初值恒為102時(shí)，4個(gè)主設(shè)備的優(yōu)先級(jí)順序?yàn)?)。A、設(shè)備0＞設(shè)備1＞設(shè)備2＞設(shè)備3B、設(shè)備2＞設(shè)備1＞設(shè)備0＞設(shè)備3C、設(shè)備2＞設(shè)備3＞設(shè)備0＞設(shè)備1D、設(shè)備2=設(shè)備3=設(shè)備0=設(shè)備1標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：計(jì)數(shù)器初值為10z，故設(shè)備2的優(yōu)先級(jí)最高，計(jì)數(shù)器值會(huì)遞增然后返回到O，故優(yōu)先級(jí)順序?yàn)樵O(shè)備2>設(shè)備3>設(shè)備0>設(shè)備1。35、1、2、3、4順序入棧(起始為空棧)，只要棧不空即可出棧，不可能的序列是()。A、4、3、2、1B、2、1、3、4C、1、2、3、4D、4，3，1，2標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：D錯(cuò)，首先出棧的是4，故1、2、3必然已入過棧，出棧序列必為4、3、2、1。36、在機(jī)器數(shù)中，正數(shù)的符號(hào)位用“1”表示的是()。A、原碼B、補(bǔ)碼C、反碼D、移碼標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：只有移碼表示法中正數(shù)的符號(hào)位為“1”，原碼、反碼和補(bǔ)碼中正數(shù)的符號(hào)位均為“0”。37、下列AOE網(wǎng)表示一項(xiàng)包含8個(gè)活動(dòng)的工程。通過同時(shí)加快若干活動(dòng)的進(jìn)度可以縮短整個(gè)工程的工期。下列選項(xiàng)中，加快其進(jìn)度就可以縮短工程工期的是A、c和eB、d和cC、f和dD、f和h標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：根據(jù)AOE網(wǎng)的定義可知，關(guān)鍵路徑上的活動(dòng)時(shí)間同時(shí)減少，可以縮短工期。38、下列選項(xiàng)中，不可能在用戶態(tài)發(fā)生的事件是A、系統(tǒng)調(diào)用B、外部中斷C、進(jìn)程切換D、缺頁標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：進(jìn)程切換是在核心態(tài)完成的，不能夠在用戶態(tài)下發(fā)生。39、A、

B、

C、

D、

標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：暫無解析40、文件系統(tǒng)中，文件訪問控制信息存儲(chǔ)的合理位置是____。A、文件控制塊B、文件分配表C、用戶口令表D、系統(tǒng)注冊表標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：考查文件控制塊的內(nèi)容。在文件控制塊中，通常含有以下三類信息，即基本信息、存取控制信息及使用信息。二、綜合應(yīng)用題(本題共15題，每題1.0分，共15分。)41、已知L為沒有頭結(jié)點(diǎn)的單鏈表中第一個(gè)結(jié)點(diǎn)的指針，每個(gè)結(jié)點(diǎn)數(shù)據(jù)域存放一個(gè)字符，該字符可能是英文字母字符或數(shù)字字符或其它字符，編寫算法構(gòu)造三個(gè)以帶頭結(jié)點(diǎn)的單循環(huán)鏈表表示的線性表，使每個(gè)表中只含同一類字符。(要求用最少的時(shí)間和最少的空間)。標(biāo)準(zhǔn)答案：voidOneToThree(LinkList＆L，&la，&ld，＆lo){／*L是無頭結(jié)點(diǎn)的單鏈表第一個(gè)結(jié)點(diǎn)的指針，鏈表中的數(shù)據(jù)域存放字符。本算法將鏈表L分解成含有英文字母字符、數(shù)字字符和其它字符的帶頭結(jié)點(diǎn)的三個(gè)循環(huán)鏈表*／la=(LinkList)malloc(sizeof(LNode))；／／建立三個(gè)鏈表的頭結(jié)點(diǎn)ld=(LinkList)malloc(sizeof(LNode))；lo=(LinkList)malloc(sizeof(LNode))；la一>next=la；／／置三個(gè)循環(huán)鏈表為空表ld一>next=ld；lo一>rlext=lo；while(L!=NULL){／／分解原鏈表r=L；L=L一>next；／／L指向待處理結(jié)點(diǎn)的后繼if(r一>data>=‘a(chǎn)’&&r一>data<=‘z’∣∣r一>data>=‘A’&&r一>data<=‘z’){r一>next=la一>next；／／處理字母字符la一>next=r；}elseif(r一>data>=‘0’&&r一>data<=‘9’){r一>next=ld一>next；／／處理數(shù)字字符ld一>next=r；}else{r一>next=lo一>next；／／處理其它符號(hào)lo一>next=r；}}}知識(shí)點(diǎn)解析：將一個(gè)結(jié)點(diǎn)數(shù)據(jù)域?yàn)樽址膯捂湵?，分解成含有字母字符、?shù)字字符和其它字符的三個(gè)循環(huán)鏈表，首先要構(gòu)造分別含有這三類字符的表頭結(jié)點(diǎn)。然后從原鏈表第一個(gè)結(jié)點(diǎn)開始，根據(jù)結(jié)點(diǎn)數(shù)據(jù)域是字母字符、數(shù)字字符和其它字符而分別插入到三個(gè)鏈表之一的鏈表。注意：不要因結(jié)點(diǎn)插入新建鏈表而使原鏈表斷鏈。另外，題目并未要求鏈表有序，插入采用“頭插法”，每次插入的結(jié)點(diǎn)均成為所插入鏈表的第一元素的結(jié)點(diǎn)即可。某操作系統(tǒng)的文件管理采用直接索引和多級(jí)索引混合方式，文件索引表共有10項(xiàng)，其中前8項(xiàng)是直接索引項(xiàng)，第9項(xiàng)是一次間接索引項(xiàng)，第10項(xiàng)是二次間接索引項(xiàng)，假定物理塊的大小是2KB，每個(gè)索引項(xiàng)占用4B，試問：42、該文件系統(tǒng)中最大的文件可以達(dá)到多大?標(biāo)準(zhǔn)答案：物理塊大小為2KB，每個(gè)索引項(xiàng)占4B，所以一塊物理塊可容納2KB／4B=512個(gè)索引項(xiàng)。由此可知，一次間接索引項(xiàng)可以指向512個(gè)物理塊，二次間接索引項(xiàng)可以指向512×512個(gè)物理塊。最大文件的文件物理塊個(gè)數(shù)可以達(dá)到：8+512+512x512塊，每塊2KB，所以最大文件大小可達(dá)：(8+512+512×512)×2KB=513MB+16KB。知識(shí)點(diǎn)解析：暫無解析43、假定一個(gè)文件的實(shí)際大小是128MB，該文件實(shí)際占用磁盤空間多大(包括間接索引塊，不計(jì)索引表所占空間)?標(biāo)準(zhǔn)答案：文件的實(shí)際大小為128MB，即128MB／2KB=64K個(gè)物理塊。8個(gè)直接索引項(xiàng)可以表示8個(gè)物理塊，一個(gè)間接索引項(xiàng)可以表示512個(gè)物理塊，所以還剩下(64K-512-8)塊需要二級(jí)索引來表示，故需要二級(jí)索引塊的個(gè)數(shù)為1+(64K-512-8)／512=128。其中前面加1的意思是，二級(jí)索引塊是建立在一級(jí)索引塊之上的，所以需要加一個(gè)一級(jí)索引塊。(64K一512—8)／512這里的除法運(yùn)算需要向上取整。一共需要的間接索引塊為1+128=129塊。所占空問為129×2KB=258KB。因此，該文件實(shí)際占用磁盤空間大小為：128MB+258KB。知識(shí)點(diǎn)解析：暫無解析44、設(shè)某計(jì)算機(jī)有四個(gè)中斷源，優(yōu)先順序按1→2→3→4降序排列，若1、2、3、4中斷源的服務(wù)程序中對(duì)應(yīng)的屏蔽字分別為1110、0100、0110、1111，試寫出這四個(gè)中斷源的中斷處理次序(按降序排列)。若四個(gè)中斷源同時(shí)有中斷請(qǐng)求，畫出CPU執(zhí)行程序的軌跡。標(biāo)準(zhǔn)答案：中斷處理次序(按降序排列)為：4-1-3-2，CPU執(zhí)行程序的軌跡如下圖8-5所示。1、2、3、4級(jí)中斷源的中斷請(qǐng)求同時(shí)出現(xiàn)，根據(jù)中斷響應(yīng)次序，首先響應(yīng)第1級(jí)中斷，但進(jìn)入中斷服務(wù)程序1之后，發(fā)現(xiàn)其屏蔽字為1110，即對(duì)第4級(jí)中斷開放，所以應(yīng)先執(zhí)行中斷服務(wù)程序4，當(dāng)中斷服務(wù)程序4執(zhí)行完畢，再返回執(zhí)行中斷服務(wù)程序1。接下來還剩下第2和3級(jí)中斷，仍然先響應(yīng)第2級(jí)中斷，但進(jìn)入中斷服務(wù)程序2之后，發(fā)現(xiàn)其屏蔽字為0100，對(duì)第3級(jí)中斷開放，所以應(yīng)先執(zhí)行中斷服務(wù)程序3，當(dāng)中斷服務(wù)程序3執(zhí)行完畢，再返回執(zhí)行中斷服務(wù)程序2。知識(shí)點(diǎn)解析：暫無解析45、設(shè)有一系統(tǒng)在某時(shí)刻的資源分配情況如下：請(qǐng)回答：(1)系統(tǒng)中各進(jìn)程尚需資源數(shù)各是多少?(2)當(dāng)前系統(tǒng)安全嗎?為什么?(3)如果此時(shí)進(jìn)程P1提出資源請(qǐng)求(0，4，2，0)，系統(tǒng)能分配給它嗎?若不能則寫出原因，若能則寫出安全序列。標(biāo)準(zhǔn)答案：(1)系統(tǒng)中各進(jìn)程尚需資源數(shù)如下表(2)此時(shí)安全，因?yàn)榇嬖谝粋€(gè)安全序列{P0，P3，P4，P1，P2)，故該狀態(tài)是安全的。(3)當(dāng)進(jìn)程P1提出請(qǐng)求(0，4，2，0)時(shí)，可以判斷該請(qǐng)求是合理的，因?yàn)镻1尚可以申請(qǐng)的最大請(qǐng)求為(1，7，5，0)，而且，剩余資源(1，6，2，2)也是可以滿足其要求的。但是，一旦分配以后，修改請(qǐng)求資源表如下剩余資源A’vailable(1，2，0，2)已不能滿足上述任何進(jìn)程的需要。進(jìn)入不安全狀態(tài)，所以P1請(qǐng)求(0，4，2，0)不能分配。知識(shí)點(diǎn)解析：本題是典型的銀行家算法的題目。銀行家算法的題目相對(duì)比較固定，復(fù)雜度也不高，只要思路正確，一般不會(huì)有太大困難。設(shè)有4臺(tái)主機(jī)A、B、C和D都處在同一物理網(wǎng)絡(luò)中，它們的IP地址分別為192．155．28．112、192．155．28．120、192．155．28．135和192．155．28．202，子網(wǎng)掩碼都是255．255．255．224，請(qǐng)回答：46、該網(wǎng)絡(luò)的4臺(tái)主機(jī)中哪些可以直接通信?哪些需要通過設(shè)置路由器才能通信?請(qǐng)畫出網(wǎng)絡(luò)連接示意圖，并注明各個(gè)主機(jī)的子網(wǎng)地址和主機(jī)地址。標(biāo)準(zhǔn)答案：思路分析：子網(wǎng)掩碼為255．255．255．224，僅和第四節(jié)節(jié)有關(guān)，轉(zhuǎn)換為二進(jìn)制255．255．255．11100000。把主機(jī)的地址轉(zhuǎn)換為二進(jìn)制，并和子網(wǎng)掩碼進(jìn)行與運(yùn)算，就可求出其網(wǎng)絡(luò)地址。主機(jī)地址網(wǎng)絡(luò)地址A192．155．28．112192．155．28．01110000192．155．28．96B192．155．28．120192．155．28．01111000192．155．28．96C192．155．28．135192．155．28．10000111192．155．28．128D192．155．28．202192．155．28．11001010192．155．28．192只有處于同一個(gè)網(wǎng)絡(luò)的主機(jī)之間才能直接通信。因此，只有A和B之間才可以直接通信。C和D以及它們同A和B的通信必須經(jīng)過路由器。若要加入第5臺(tái)主機(jī)E，使它能與D直接通信，那么主機(jī)E必須位于和D相同的網(wǎng)絡(luò)中，即192．155．28．192，這樣地址范圍是192．155．28．193～192．155．28．222，且除去D主機(jī)的IP地址192．155．28．202。主機(jī)A地址改為192．155．28．168，那么它所處的網(wǎng)絡(luò)為192．155．28．160。由定義知，直接廣播地址是主機(jī)號(hào)各位為全“1”，用于任何網(wǎng)絡(luò)向該網(wǎng)絡(luò)上的所有主機(jī)發(fā)送報(bào)文，每個(gè)子網(wǎng)的廣播地址則是直接廣播地址。本地廣播地址又稱為有限廣播地址，它的32位為全“1”，用于該網(wǎng)絡(luò)不知道網(wǎng)絡(luò)號(hào)時(shí)的內(nèi)部廣播。因此，主機(jī)A的直接廣播地址為192．155．28．191，本地廣播地址是255．255．255．255，若使用本地廣播地址發(fā)送信息，則所有主機(jī)都能夠收到。若希望4臺(tái)主機(jī)直接通信，則可以修改掩碼為255．255．255．0，這樣4臺(tái)主機(jī)就處于同一個(gè)網(wǎng)絡(luò)中。(1)只有主機(jī)A和主機(jī)B之間可以直接通信，主機(jī)C和主機(jī)D以及它們同A和B的通信都必須經(jīng)過路由器。網(wǎng)絡(luò)連接示意圖如圖8—1所示。各個(gè)主機(jī)的子網(wǎng)地址和主機(jī)地址見思路分析。知識(shí)點(diǎn)解析：暫無解析47、若要加入第5臺(tái)主機(jī)E，使它能與主機(jī)D直接通信，則其IP地址的范圍是多少?標(biāo)準(zhǔn)答案：IP地址的范圍是192．155．28．193～192．155．28．222，且除去D主機(jī)的IP地址192．155．28．202。知識(shí)點(diǎn)解析：暫無解析48、若不改變主機(jī)A的物理位置，而將其IP改為192．155．28．168，則它的直接廣播地址和本地廣播地址各是多少?若使用本地廣播地址發(fā)送信息，請(qǐng)問哪些主機(jī)能夠收到?標(biāo)準(zhǔn)答案：主機(jī)A的直接廣播地址是192．155．28．19l，本地廣播地址是255．255．255．255，若使用本地廣播地址發(fā)送信息，則所有主機(jī)都能夠收到。知識(shí)點(diǎn)解析：暫無解析49、若要使該網(wǎng)絡(luò)中的4臺(tái)主機(jī)都能夠直接通信，可采取什么辦法?標(biāo)準(zhǔn)答案：若要使4臺(tái)主機(jī)都能夠直接通信，則可以修改子網(wǎng)掩碼為255．255．255．0，這樣4臺(tái)主機(jī)就處于一個(gè)網(wǎng)絡(luò)中，可以直接通信。知識(shí)點(diǎn)解析：暫無解析一個(gè)客戶機(jī)利用FTP協(xié)議從服務(wù)器上下載文件，如下圖所示為整個(gè)過程中協(xié)議交換的過程，請(qǐng)回答如下問題：50、該協(xié)議層圖中第四層協(xié)議是什么?標(biāo)準(zhǔn)答案：FTP協(xié)議使用了TCP作為傳輸層協(xié)議，所以第四層協(xié)議應(yīng)該為TCP。知識(shí)點(diǎn)解析：暫無解析51、如果FTP客戶端采用了LIST命令來獲得FTP服務(wù)器上的文件列表，該列表采用什么端口傳輸?標(biāo)準(zhǔn)答案：FTP協(xié)議的控制連接端口是21，數(shù)據(jù)連接端口是20。而列表信息是通過數(shù)據(jù)傳輸端口傳送的，所以通過了20端口傳送。知識(shí)點(diǎn)解析：暫無解析52、如果一個(gè)TCP數(shù)據(jù)包的數(shù)據(jù)部分長度為5000字節(jié)，那么在IP層需要分片嗎?標(biāo)準(zhǔn)答案：以太網(wǎng)的最大數(shù)據(jù)長度是1500，而該，TCP包的長度為5000，再加上20字節(jié)的TCP頭和20字節(jié)的IP頭，最后成幀的長度為5040字節(jié)，不能通過以太網(wǎng)直接發(fā)送，必須要在IP層分片。知識(shí)點(diǎn)解析：暫無解析53、如果需要分片請(qǐng)說明需要分成幾片，每片長度為多少?如果不需要分片，請(qǐng)說明原因。標(biāo)準(zhǔn)答案：每片都帶有一個(gè)IP頭，還有1480字節(jié)可以用來傳輸數(shù)據(jù)，計(jì)算得需要分4片傳送，前3片的長度為1500字節(jié)，最后一片長度為600字節(jié)。知識(shí)點(diǎn)解析：暫無解析請(qǐng)求分頁管理系統(tǒng)中，假設(shè)某進(jìn)程的頁表內(nèi)容如下表所示。頁面大小為4KB，一次內(nèi)存的訪問時(shí)間是100ns，一次快表(TLB)的訪問時(shí)間是10ns，處理一次缺頁的平均時(shí)間為108ns(已含更新TLB和頁表的時(shí)間)，進(jìn)程的駐留集大小固定為2，采用最近最少使用置換算法(LRU)和局部淘汰策略。假設(shè)：①TLB初始為空；②地址轉(zhuǎn)換時(shí)先訪問TLB，若TLB未命中，再訪問頁表(忽略訪問頁表之后的TLB更新時(shí)間)；③有效位為0表示頁面不在內(nèi)存，產(chǎn)生缺頁中斷，缺頁中斷處理后，返回到產(chǎn)生缺頁中斷的指令處重新執(zhí)行。設(shè)有虛地址訪問序列2362H、1565H、25A5H，請(qǐng)問：54、依次訪問上述三個(gè)虛地址，各需多少時(shí)間?給出計(jì)算過程。標(biāo)準(zhǔn)答案：根據(jù)頁式管理的工作原理，應(yīng)先考慮頁面大小，以便將頁號(hào)和頁內(nèi)位移分解出來。頁面大小為4KB，即212，則得到頁內(nèi)位移占虛地址的低12位，頁號(hào)占剩余高位?？傻萌齻€(gè)虛地址的頁號(hào)P如下(十六進(jìn)制的一位數(shù)字轉(zhuǎn)換成4位二進(jìn)制，因此，十六進(jìn)制的低三位正好為頁內(nèi)位移，最高位為頁號(hào))：2362H：P=2，訪問快表10ns，因初始為空，訪問頁表100ns得到頁框號(hào)，合成物理地址后訪問主存100ns，共計(jì)10ns+100ns+100ns=210ns。1565H：P=1，訪問快表10ns，落空，訪問頁表100ns落空，進(jìn)行缺頁中知識(shí)點(diǎn)解析：暫無解析55、基于上述訪問序列，虛地址1565H的物理地址是多少?請(qǐng)說明理由。標(biāo)準(zhǔn)答案：當(dāng)訪問虛地址1565H時(shí)，產(chǎn)生缺頁中斷，合法駐留集為2，必須從頁表中淘汰一個(gè)頁面，根據(jù)題目的置換算法，應(yīng)淘汰0號(hào)頁面，因此1565H的對(duì)應(yīng)頁框號(hào)為101H。由此可得1565H的物理地址為101565H。知識(shí)點(diǎn)解析：暫無解析計(jì)算機(jī)專業(yè)（基礎(chǔ)綜合）模擬試卷第2套一、單選題(本題共40題，每題1.0分，共40分。)1、設(shè)數(shù)據(jù)碼字為10010011，采用海明碼進(jìn)行校驗(yàn)，若僅考慮糾正一位錯(cuò)，則必須加入的(冗余)位數(shù)是()。A、2B、3C、4D、5標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：如果僅考慮糾正1位錯(cuò)的情況，只要滿足2k≥n+k+1就可以了(設(shè)校驗(yàn)位的位數(shù)為k，信息位的位數(shù)為n)。此題中因?yàn)閚=8，所以k≥4。如果在糾正1位錯(cuò)的同時(shí)還要能發(fā)現(xiàn)2位錯(cuò)，則滿足2k-1≥n+k+1。2、一個(gè)交叉存放信息的磁盤，信息存放方式如圖1—3所示。每個(gè)磁道有8個(gè)扇區(qū)，每個(gè)扇區(qū)512B，旋轉(zhuǎn)速度為3000r／min。假定磁頭已在讀取信息的磁道上，0扇區(qū)轉(zhuǎn)到磁頭下需要1／2r，且設(shè)備對(duì)應(yīng)的控制器不能同時(shí)進(jìn)行輸入／輸出，在數(shù)據(jù)從控制器傳送至內(nèi)存的這段時(shí)間內(nèi)，從磁頭下通過的扇區(qū)數(shù)為2，問依次讀取一個(gè)磁道上所有的扇區(qū)的數(shù)據(jù)到內(nèi)存平均傳輸速度為()。A、57．1KB／sB、67．1KB／sC、77．1KB／sD、87．1KB／s標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：在數(shù)據(jù)從控制器傳送至內(nèi)存的這段時(shí)間內(nèi)，從磁頭下通過的扇區(qū)數(shù)為2。當(dāng)數(shù)據(jù)從控制器傳送至內(nèi)存后，磁頭開始讀數(shù)據(jù)時(shí)，剛好轉(zhuǎn)到目標(biāo)扇區(qū)。所以總時(shí)間的計(jì)算公式為總時(shí)間=初始尋找0扇區(qū)的時(shí)間+讀扇區(qū)總時(shí)間+將扇區(qū)數(shù)據(jù)送入內(nèi)存的總時(shí)間由題中條件可知，旋轉(zhuǎn)速度為3000r／min=50r／s，即20ms／r。讀一個(gè)扇區(qū)需要的時(shí)間為20／8ms=2．5ms讀一個(gè)扇區(qū)并將扇區(qū)數(shù)據(jù)送入內(nèi)存需要的時(shí)間為2．5×3ms=7.5ms讀出一個(gè)磁道上的所有扇區(qū)需要的時(shí)間為20／2ms+8×7．5ms=70ms=0．07s每磁道數(shù)據(jù)量為8×512B=4KB數(shù)據(jù)傳輸速度為4KB／0．07s=57．1KB／s所以，依次讀出一個(gè)磁道上的所有扇區(qū)需要0．07s，其數(shù)據(jù)傳輸速度為57．1KB／s。3、MIPS(每秒百萬次指令數(shù))和MFLOPS(每秒百萬次浮點(diǎn)運(yùn)算數(shù))是衡量CPU性能的兩個(gè)指標(biāo)，其中()。A、MIPS適合衡量向量處理機(jī)的性能，MFLOPS適合衡量標(biāo)量處理機(jī)的性能B、MIPS適合衡量標(biāo)量處理機(jī)的性能，MFLOPS適合衡量向量處理機(jī)的性能C、MIPS反映計(jì)算機(jī)系統(tǒng)的峰值性能，MFLOPS反映計(jì)算機(jī)系統(tǒng)的持續(xù)性能D、MIPS反映計(jì)算機(jī)系統(tǒng)的持續(xù)性能，MFLOPS反映計(jì)算機(jī)系統(tǒng)的峰值性能標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：MIPS反映的是單位時(shí)間內(nèi)執(zhí)行定點(diǎn)指令的條數(shù)，MLOPS是基于所完成的浮點(diǎn)操作次數(shù)而不是指令數(shù)。同一個(gè)程序，不同計(jì)算機(jī)運(yùn)行所需的指令數(shù)會(huì)不同，但所用到的浮點(diǎn)運(yùn)算次數(shù)卻是相同的。[歸納總結(jié)]以MIPS和MFLOPS作為計(jì)量單位來衡量運(yùn)算速度。MIPS表示每秒執(zhí)行多少百萬條指令，這里所說的指令一般是指加、減運(yùn)算這類短指令，適合于衡量標(biāo)量機(jī)的性能。MFLOPS表示每秒執(zhí)行多少百萬次浮點(diǎn)運(yùn)算，MFLOPS適用于衡量向量機(jī)的性能。4、下列有關(guān)I／O編址方式的描述中，正確的是()。A、統(tǒng)一編址是將I／O地址看作是存儲(chǔ)器地址的一部分，可用專門的I／O指令對(duì)設(shè)備進(jìn)行訪問B、獨(dú)立編址是指I／O地址和存儲(chǔ)器地址是分開的，所以對(duì)I／O訪問必須有專門的I／O指令C、統(tǒng)一編址是指I／O地址和存儲(chǔ)器地址是分開的，所以可用訪存指令實(shí)現(xiàn)CPU對(duì)設(shè)備的訪問D、獨(dú)立編址是將I／O地址看作是存儲(chǔ)器地址的一部分，所以對(duì)I／0訪問必須有專門的I／O指令標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：統(tǒng)一編址是將I／O地址看作是存儲(chǔ)器地址的一部分，不需要專門的I／O指令。5、計(jì)算機(jī)的外圍設(shè)備是指()。A、主存儲(chǔ)器B、外存儲(chǔ)器C、除主機(jī)外的其他設(shè)備D、除CPU外的其他設(shè)備標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：外圍設(shè)備是相對(duì)主機(jī)而言，即除CPU和主存儲(chǔ)器外的其他設(shè)備。6、TCP協(xié)議規(guī)定HTTP端口號(hào)為80的進(jìn)程是()。A、客戶B、分布C、服務(wù)器D、主機(jī)標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：本題考查網(wǎng)絡(luò)應(yīng)用模式，HTTP協(xié)議是萬維網(wǎng)所應(yīng)用的協(xié)議，萬維網(wǎng)是以客戶服務(wù)器方式工作。這里瀏覽器就是在用戶計(jì)算機(jī)上的萬維網(wǎng)客戶程序。萬維網(wǎng)文檔所駐留的計(jì)算機(jī)則運(yùn)行服務(wù)器程序，因此這個(gè)計(jì)算機(jī)也稱為萬維網(wǎng)服務(wù)器。客戶程序向服務(wù)器程序發(fā)出請(qǐng)求，服務(wù)器程序向客戶程序送回客戶所要的萬維網(wǎng)文檔，而80端口是服務(wù)器偵聽的端口號(hào)，因此答案為C。7、某8位機(jī)的地址碼為16位，主存按字節(jié)編址，其中最高8KB主存空間為系統(tǒng)BIOS程序一區(qū)，其余為用戶程序區(qū)?，F(xiàn)有4K×4的ROM芯片和18K×4的SRAM芯片。構(gòu)建該機(jī)所允許的最大空間的主存，需用上述規(guī)格的ROM芯片和SRAM芯片各為()。A、4，4B、14，14C、14，4D、4，14標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：內(nèi)存空間為：216×8=64KB。去掉主存空間里的前8K，還有56K的用戶空間。使用4K×4的ROM芯片數(shù)為：8K／4K×8／4=4。使用8K×4位的SRAM芯片為56．K／8K×8／4=14。8、虛擬頁式存儲(chǔ)管理中，CPU須具備必要的物理硬件的支持，而不是必需的單元是()。A、缺頁中斷機(jī)構(gòu)B、地址加法器C、cacheD、地址寄存器標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：在虛擬頁式存儲(chǔ)管理中，除了有主存和輔存以外，為滿足虛擬技術(shù)，CPU還需要有缺頁中斷機(jī)制；為滿足頁式存儲(chǔ)管理，CPU中需要有地址加法器和地址寄存器來計(jì)算頁表到頁框的映射，而cache并不是必需的，因?yàn)閏ache的存在只是提高了CPU尋址的效率，并不是虛擬頁式存儲(chǔ)技術(shù)的重要單元，缺少cache，CPU每次執(zhí)行一個(gè)雙字的指令(以32位為例)或取一個(gè)數(shù)據(jù)均需要二次訪問內(nèi)存，當(dāng)然這是很不利的，可能會(huì)實(shí)際上造成虛擬頁式的使用障礙。增加了cache，使得虛擬頁式存儲(chǔ)技術(shù)的實(shí)際使用提供了方便。9、下列說法正確的是()。Ⅰ．用鏈?zhǔn)椒绞酱鎯?chǔ)的隊(duì)列，在進(jìn)行出隊(duì)操作時(shí)，隊(duì)頭、隊(duì)尾指針都必須修改Ⅱ．將遞歸算法轉(zhuǎn)換成等價(jià)的非遞歸算法應(yīng)使用棧Ⅲ．圖的廣度優(yōu)先搜索使用了棧來實(shí)現(xiàn)A、ⅠB、Ⅰ、ⅡC、ⅡD、Ⅱ、Ⅲ標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：Ⅰ：隊(duì)列以鏈表方式存儲(chǔ)時(shí)，如果隊(duì)列中只有一個(gè)元素，則出隊(duì)操作需要修改隊(duì)頭、隊(duì)尾指針；反之，只需要修改隊(duì)頭指針，所以Ⅰ錯(cuò)誤。Ⅱ：考查棧的基本應(yīng)用，在二叉樹遍歷的非遞歸算法中可以得到認(rèn)證，所以Ⅱ正確。Ⅲ：隊(duì)列具有先進(jìn)先出的特性，在廣度優(yōu)先搜索算法中，訪問完每一個(gè)結(jié)點(diǎn)，可將其子結(jié)點(diǎn)全部加入隊(duì)列中，這樣可實(shí)現(xiàn)結(jié)點(diǎn)的按層次優(yōu)先的訪問，故廣度優(yōu)先搜索使用了隊(duì)列來實(shí)現(xiàn)，所以Ⅲ錯(cuò)誤。10、假設(shè)有k個(gè)關(guān)鍵字互為同義詞，若用線性探查法把這k個(gè)關(guān)鍵字存入，至少要進(jìn)行的探查次數(shù)是()。A、k－1B、kC、k＋1D、k(k＋1)／2標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：假設(shè)有k個(gè)關(guān)鍵字互為同義詞，若用線性探查法把這k個(gè)關(guān)鍵字存入，探查次數(shù)最少的情況是第1個(gè)關(guān)鍵字通過1次比較后插入，第2個(gè)關(guān)鍵字通過2次比較后插入，……，第k個(gè)關(guān)鍵字通過k次比較后插入?？偟谋容^次數(shù)＝1＋2＋……＋k＝k(k＋1)／2。11、下列的網(wǎng)絡(luò)協(xié)議中，()的運(yùn)輸層協(xié)議是使用TCP的。A、TFTPB、DNSC、RIPD、TELNET標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：其他三項(xiàng)都是使用UDP來傳輸?shù)?，只有TELNET是使用TCP的。12、關(guān)于以太網(wǎng)交換機(jī)，下面的論述中不正確的是()。A、交換機(jī)工作在數(shù)據(jù)鏈路層B、交換機(jī)的每個(gè)端口形成一個(gè)沖突域C、交換機(jī)支持多端口同時(shí)收發(fā)數(shù)據(jù)D、交換機(jī)是一種多端口中繼器標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：本題考查交換機(jī)的工作原理和特性，交換機(jī)是工作與數(shù)據(jù)鏈路層的網(wǎng)絡(luò)設(shè)備，每個(gè)端口是獨(dú)立的沖突域，交換機(jī)的交換結(jié)構(gòu)保證了多端口同時(shí)進(jìn)行數(shù)據(jù)交換，多端口的中繼器可以認(rèn)為是集線器，其所有端口處于同一個(gè)沖突域內(nèi)，因此答案為D。13、下列敘述中，不符合m階B-樹定義要求的是()。A、根節(jié)點(diǎn)最多有m棵子樹B、所有葉結(jié)點(diǎn)都在同一層上C、各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列D、葉結(jié)點(diǎn)之間通過指針鏈接標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：暫無解析14、下面的敘述中，屬于分段式虛擬存儲(chǔ)管理的優(yōu)點(diǎn)的是()。A、沒有內(nèi)零頭B、便于處理在進(jìn)程執(zhí)行過程中堆棧尺寸的增長問題C、便于共享內(nèi)存中數(shù)據(jù)D、只需將進(jìn)程的一部分調(diào)入內(nèi)存，進(jìn)程即可運(yùn)行標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：如果系統(tǒng)正在向非易失性存儲(chǔ)器件硬盤寫數(shù)據(jù)，此時(shí)，系統(tǒng)崩潰，寫的數(shù)據(jù)可能會(huì)丟失，或者存儲(chǔ)信息不完整。15、有一個(gè)長度為12的有序表，按折半查找法對(duì)該表進(jìn)行查找，在表內(nèi)各元素等概率情況下，查找成功所需的平均比較次數(shù)是()。A、37/12B、35/12C、39/12D、43/12標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：長度為12的折半查找判定樹如下圖所示，判定樹中有12個(gè)內(nèi)結(jié)點(diǎn)。對(duì)于長度為12的有序表，折半查找成功時(shí)的平均查找長度為：16、計(jì)算機(jī)系統(tǒng)中，不屬于DMA控制器的是()。A、命令／狀態(tài)寄存器B、內(nèi)存地址寄存器C、數(shù)據(jù)寄存器D、堆棧指針寄存器標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：本題考查IO設(shè)備中DMA設(shè)備的組成。DMA設(shè)備與CPU有三類信號(hào)線：數(shù)據(jù)線、地址線和控制線。一般要DMA設(shè)備工作，必須有命令／狀態(tài)寄存器，這個(gè)寄存器控制DMA的工作模式并反映給CPU它當(dāng)前的狀態(tài)，地址寄存器存放DMA作業(yè)時(shí)的源地址和目標(biāo)地址，數(shù)據(jù)寄存器存放要DMA轉(zhuǎn)移的數(shù)據(jù)，只有堆棧指針寄存器不需要在DMA控制器中存放。堆棧一般在計(jì)算機(jī)內(nèi)存中開辟有統(tǒng)一的區(qū)域。17、要發(fā)送的數(shù)據(jù)是1101011011，采用CRC校驗(yàn)，生成多項(xiàng)式是10011，那么最終發(fā)送的數(shù)據(jù)應(yīng)該是()。A、11010110111010B、11010110110110C、11010110111110D、11110011011100標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：根據(jù)給出的除數(shù)，用11010110110000除以10011，得到的冗余碼為1110，添加在原來數(shù)據(jù)的最后發(fā)送出去。18、若某完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)為100，則第60個(gè)結(jié)點(diǎn)的度為()。A、0B、1C、2D、不確定標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)，說明有1個(gè)度為1的結(jié)點(diǎn)。設(shè)ni為度是i的結(jié)點(diǎn)的個(gè)數(shù)，那么就有：n0+n2+1=100，n0=n2-1，解得：n0=55，n2=54；又因?yàn)橥耆鏄涞木幪?hào)是先度為2的結(jié)點(diǎn)，然后度為1的結(jié)點(diǎn)，最后才是葉子結(jié)點(diǎn)，即1～54是度為2的結(jié)點(diǎn)，55是度為1的結(jié)點(diǎn)，56～100是度為0的結(jié)點(diǎn)。因此，第60個(gè)結(jié)點(diǎn)為度為0的結(jié)點(diǎn)。19、若某線性表中最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)，則下面最合適的存儲(chǔ)方式是()。A、單鏈表B、循環(huán)雙鏈表C、單循環(huán)鏈表D、帶有尾指針的單循環(huán)鏈表標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：在鏈表中的最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)要知道終端結(jié)點(diǎn)的地址，單鏈表、單循環(huán)鏈表都不合適；刪除最后一個(gè)結(jié)點(diǎn)要知道終端結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的地址，帶有尾指針的單循環(huán)鏈表不合適；而循環(huán)雙鏈表滿足這兩個(gè)條件。20、如果二叉樹T2是由有序樹T1轉(zhuǎn)換而來的二叉樹，那么T1中結(jié)點(diǎn)的先序就是T2中結(jié)點(diǎn)的()。A、先序B、中序C、后序D、層次序標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：一般樹中一個(gè)結(jié)點(diǎn)的孩子是無序的，所謂有序樹是指樹中任一結(jié)點(diǎn)的孩子是有序的。由樹轉(zhuǎn)換成二叉樹的過程可知本題答案為A。21、RS-232-C的電氣特性規(guī)定邏輯“1”的電平范圍為()。A、+5～+15VB、-5～-15VC、0～+5VD、0～-5V標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：RS-232-C關(guān)于電氣信號(hào)特性的要求，規(guī)定邏輯“1”的電平為低于-3V，為了表示一個(gè)邏輯1或MARK條件，驅(qū)動(dòng)器必須提供-5V～-15V之間的電壓；為了表示一個(gè)邏輯0或SPACE條件，驅(qū)動(dòng)器必須給出+5V～+15V之間韻電壓。22、要發(fā)送的數(shù)據(jù)是1101011011，采用CRC校驗(yàn)，生成多項(xiàng)式是：10011，那么最終發(fā)送的數(shù)據(jù)應(yīng)該是()。A、11010110111010B、11010110110110C、11010110111110D、11110011011100標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：根據(jù)給出的除數(shù)，用11010110110000除以10011，得到的冗余碼為1110，添加在原來數(shù)據(jù)的最后發(fā)送出去。23、采用段式存儲(chǔ)管理時(shí)，一個(gè)程序分段的時(shí)機(jī)是()。A、程序編譯時(shí)B、用戶編程時(shí)C、程序裝入時(shí)D、程序執(zhí)行時(shí)標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：本題考查段式存儲(chǔ)管理的段的確定形式。分段是信息單位，當(dāng)用戶在編寫程序時(shí)并不分段，一旦編譯時(shí)，編譯系統(tǒng)會(huì)將指令代碼和數(shù)據(jù)歸類分開存放，為將來的運(yùn)行做好前期工作。運(yùn)行時(shí)，操作系統(tǒng)將編譯好的代碼和數(shù)據(jù)按段申請(qǐng)內(nèi)存，并將對(duì)應(yīng)的段裝入內(nèi)存。至于段的類型和大小在編譯完以后就已經(jīng)確定了，鏈接過程中只是將系統(tǒng)提供的系統(tǒng)調(diào)用或API的代碼按段的種類鏈接到程序中，運(yùn)行時(shí)操作系統(tǒng)不再調(diào)整或改變。24、建立一個(gè)文件系統(tǒng)時(shí)，不是文件系統(tǒng)必須建立的是()。A、磁盤空間管理B、根目錄C、啟動(dòng)信息塊D、文件查找表標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：本題考查對(duì)文件系統(tǒng)結(jié)構(gòu)的理解。文件系統(tǒng)存放在磁盤上，多數(shù)磁盤劃分為一個(gè)或多個(gè)分區(qū)，每個(gè)分區(qū)中有一個(gè)獨(dú)立的文件系統(tǒng)，在該分區(qū)的起始是啟動(dòng)的基本代碼和信息，稱為啟動(dòng)塊或自舉塊、引導(dǎo)塊等，其中包括：確定文件系統(tǒng)位置、文件系統(tǒng)中數(shù)據(jù)塊的組織以及其他重要的管理信息。從啟動(dòng)塊開始，后面的布局是隨著文件系統(tǒng)的不同而變化的。至少會(huì)建立磁盤空間管理信息，例如空閑塊的信息，已分配磁盤塊信息等。接著是根目錄。它存放文件系統(tǒng)目錄樹的根部。其余即是用戶所用的文件和子目錄的空間。一個(gè)文件系統(tǒng)建立起來以后(通常是格式化以后)，除了文件和子目錄的空間為空外，其余的部分均已經(jīng)分配完畢，所以，最小的可用文件系統(tǒng)應(yīng)該包含根目錄及以上層面的各個(gè)部分。而所謂文件查找表在文件系統(tǒng)中并不存在。25、已知某磁盤的平均轉(zhuǎn)速為r秒／轉(zhuǎn)，平均尋道時(shí)間為T秒，每個(gè)磁道可以存儲(chǔ)的字節(jié)數(shù)為N，現(xiàn)向該磁盤讀寫b字節(jié)的數(shù)據(jù)，采用隨機(jī)尋道的方法，每道的所有扇區(qū)組成一個(gè)簇，請(qǐng)問：平均訪問時(shí)間是()。A、b／N*(r＋T)B、b／N*2C、(b／N＋T)*rD、b*T／N＋r標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：本題考查磁盤結(jié)構(gòu)和磁盤讀寫的概念。磁盤是旋轉(zhuǎn)盤式存儲(chǔ)設(shè)備，每個(gè)盤面劃分有若干存儲(chǔ)信息的同心圓稱為磁道，每個(gè)磁道又劃分成多個(gè)扇區(qū)。本題中，將每道的所有扇區(qū)組成一個(gè)簇，意味著可以將一個(gè)磁道的所有存儲(chǔ)空間組織成一個(gè)數(shù)據(jù)塊組，這樣有利于提高存儲(chǔ)速度。讀寫磁盤時(shí)，磁頭首先要找到磁道，稱為尋道，然后才可以將信息從磁道里讀出來或?qū)戇M(jìn)去。讀寫完一個(gè)磁道以后磁頭會(huì)繼續(xù)尋找下一個(gè)磁道，完成剩余的工作，所以，在隨機(jī)尋道的情況下，讀寫一個(gè)磁道的時(shí)間要包含尋道時(shí)間和讀寫磁道時(shí)間，即T＋r秒。由于總的數(shù)據(jù)量是b字節(jié)，它要占用的磁道數(shù)為b／N個(gè)，所以總的平均讀寫時(shí)間為b／N*(T＋r)秒。如果不采用隨機(jī)尋道，而是采用連續(xù)讀寫的方式，那么磁盤的存儲(chǔ)方式是這樣的，首先也是尋道，找到一組連續(xù)的磁道(用于連續(xù)讀或?qū)?，寫入的話磁道總?cè)萘勘囟ù笥谝獙懭氲男畔⒖倲?shù))，花費(fèi)時(shí)間T秒，然后再花費(fèi)r秒將N個(gè)字節(jié)的信息寫入(或讀出)，然后磁頭移動(dòng)到下一道(此時(shí)，這個(gè)磁道與上一個(gè)磁道是緊緊挨著的，幾乎可以不花費(fèi)時(shí)間)，繼續(xù)寫入(或讀出)N字節(jié)，循環(huán)往復(fù)，直到全部信息寫入(或讀出)完成。這樣的話，總時(shí)間可以縮短為b／N*r＋T。因?yàn)槠洳恍枰看味既さ溃恍枰淮螌さ兰纯?。所以，考生要注意題目的條件，找出符合題意的正確答案。26、OSI模型中完成路徑選擇功能的層次是()。A、物理層B、數(shù)據(jù)鏈路層C、網(wǎng)絡(luò)層D、傳輸層標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：本題考查OSI模型中各個(gè)層次功能，完成路徑選擇，也就是路由功能的是網(wǎng)絡(luò)層，答案是C。27、下列說法中，正確的是()。A、所有指令的取指操作的時(shí)間都是相同的B、中斷周期是在指令執(zhí)行完成后出現(xiàn)的C、微命令發(fā)生器的作用是產(chǎn)生控制時(shí)序D、所有指令的間址操作都是一樣的標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：A：不同長度的指令，其取指操作的時(shí)間可能是不同的。例如雙字長指令和三字長指令與單字長指令的取指操作訪問主存的次數(shù)是不同的，故A選項(xiàng)錯(cuò)誤。B：取指周期→間址周期→執(zhí)行周期→中斷周期，故B選項(xiàng)正確。C：微命令發(fā)生器也稱為控制單元(CU)，用于產(chǎn)生計(jì)算機(jī)所需的各種微操作命令，故C選項(xiàng)錯(cuò)誤。D：指令間址有一次間址、兩次間址、多次間址，它們的操作是不同的，故D選項(xiàng)錯(cuò)誤。28、浮點(diǎn)加減中的對(duì)階是()。A、將較小的一個(gè)階碼調(diào)整到與較大的一個(gè)階碼相同B、將較大的一個(gè)階碼調(diào)整到與較小的一個(gè)階碼相同C、將被加數(shù)的階碼調(diào)整到與加數(shù)的階碼相同D、將加數(shù)的階碼調(diào)整到與被加數(shù)的階碼相同標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：對(duì)階的原則是小階向大階看齊。29、操作系統(tǒng)為用戶提供了多種接口，它們是()。I．計(jì)算機(jī)高級(jí)指令；Ⅱ．終端命令；Ⅲ．圖標(biāo)菜單；Ⅳ．匯編語言；V．C語言；Ⅵ．系統(tǒng)調(diào)用；A、I；Ⅱ；VB、Ⅱ；Ⅲ；ⅥC、Ⅲ；Ⅳ；VD、Ⅱ；Ⅳ；Ⅵ標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：本題考查操作系統(tǒng)的接口，操作系統(tǒng)有二種接口，命令輸入和系統(tǒng)調(diào)用，而命令輸入又可以分為命令行和圖形用戶界面。命令行是在終端或命令輸入窗口中輸入操作和控制計(jì)算機(jī)的規(guī)定的命令，既可以一條一條輸入，也可以組織成一批命令，逐條自動(dòng)執(zhí)行，稱為批處理命令。圖形用戶接口是我們熟知的圖標(biāo)和菜單形式。系統(tǒng)調(diào)用是我們編寫程序過程中，需要計(jì)算機(jī)所做的操作，一般要按固定格式來調(diào)用。30、有A，B，C，D，E5個(gè)元素按次序入棧，在各種可能的出棧次序中，以元素C，D最先出棧的序列中，下列正確的一組是()。A、CDBAECDABEB、CDEBACDBEAC、CDEABCDABED、CEBAECDAEB標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：要使得CD作為第一、二個(gè)元素出棧，應(yīng)是A、B、C先入棧，C出棧，D入棧，D出棧；接著就剩下A、B在棧中，E未入棧，共3個(gè)元素，此三者序列為BAE，BEA，EBA。31、下列哪個(gè)選項(xiàng)不是RISC的特點(diǎn)()。A、只有取數(shù)和存數(shù)指令訪問存儲(chǔ)器，其余指令都在寄存器之間進(jìn)行B、由使用頻率高的簡單指令和很有用且不復(fù)雜的指令組成C、使用RISC技術(shù)后，指令系統(tǒng)又回到了計(jì)算機(jī)發(fā)展早期的比較簡單的情況D、使用優(yōu)化的編譯程序標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：早期的指令系統(tǒng)簡單是由設(shè)計(jì)水平和器件水平?jīng)Q定的，而且RIS(二技術(shù)不是簡單地精簡了指令系統(tǒng)，而是在合理選擇簡單指令的基礎(chǔ)上采取了很多優(yōu)化措施，如縮短機(jī)器周期，采用流水線技術(shù)，使用優(yōu)化的編譯程序等等，兩者不可等同。32、一個(gè)使用CSMA／CA的網(wǎng)絡(luò)上，計(jì)算機(jī)A的幀際間隔是2時(shí)槽，計(jì)算機(jī)B的幀際間隔是6時(shí)槽，如果計(jì)算機(jī)C使用()幀際間隔可以獲得最高優(yōu)先級(jí)。A、8時(shí)槽B、5時(shí)槽C、3時(shí)槽D、1時(shí)槽標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：在CSMA／CA中，幀際間隔值可以用來分配發(fā)送方的優(yōu)先級(jí)，如果一個(gè)設(shè)備被分配一個(gè)較小的幀際優(yōu)先級(jí)，那么它就會(huì)有更多的機(jī)會(huì)得到對(duì)傳輸介質(zhì)訪問的機(jī)會(huì)。33、A、115200bpsB、57600bpsC、28800bpsD、230400bps標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：暫無解析34、網(wǎng)絡(luò)協(xié)議的三要素是()。A、數(shù)據(jù)格式、編碼、信號(hào)電平B、數(shù)據(jù)格式、控制信息、速度匹配C、語法、語義、時(shí)序D、編碼、控制信息、同步標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：網(wǎng)絡(luò)協(xié)議三要素：語法，用來規(guī)定信息格式；語義，用來說明通信雙方應(yīng)當(dāng)怎么做；時(shí)序，詳細(xì)說明事件的先后順序。35、()進(jìn)程調(diào)度算法綜合考慮到了CPU密集型進(jìn)程和I／O密集型進(jìn)程。A、時(shí)間片輪轉(zhuǎn)B、優(yōu)先級(jí)C、多重隊(duì)列D、彩票標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：多級(jí)反饋隊(duì)列調(diào)度算法描述：(1)進(jìn)程在進(jìn)人待調(diào)度的隊(duì)列等待時(shí)，首先進(jìn)入優(yōu)先級(jí)最高的Q1等待。(2)首先調(diào)度優(yōu)先級(jí)高的隊(duì)列中的進(jìn)程。若高優(yōu)先級(jí)中隊(duì)列中已沒有調(diào)度的進(jìn)程，則調(diào)度次優(yōu)先級(jí)隊(duì)列中的進(jìn)程。例如：Q1，Q2，Q3三個(gè)隊(duì)列，只有在Q1中沒有進(jìn)程等待時(shí)才去調(diào)度Q2，同理，只有Q1，Q2都為空時(shí)才會(huì)去調(diào)度Q3。(3)對(duì)于同一個(gè)隊(duì)列中的各個(gè)進(jìn)程，按照時(shí)間片輪轉(zhuǎn)法調(diào)度。比如Q1隊(duì)列的時(shí)間片為N，那么Q1中的作業(yè)在經(jīng)歷了N個(gè)時(shí)間片后若還沒有完成，則進(jìn)入Q2隊(duì)列等待，若Q2的時(shí)間片用完后作業(yè)還不能完成，一直進(jìn)入下一級(jí)隊(duì)列，直至完成。(4)在低優(yōu)先級(jí)的隊(duì)列中的進(jìn)程在運(yùn)行時(shí)，又有新到達(dá)的作業(yè)，那么在運(yùn)行完這個(gè)時(shí)間片后，CPU馬上分配給新到達(dá)的作業(yè)(搶占式)。故多級(jí)反饋隊(duì)列調(diào)度算法綜合考慮了CPU密集型和I／O密集型進(jìn)程。36、下列描述中，屬于馮.諾依曼體系結(jié)構(gòu)的特點(diǎn)是()。①采用流水線技術(shù)；②指令和數(shù)據(jù)均以二進(jìn)制表示；③存儲(chǔ)程序并且存儲(chǔ)時(shí)不區(qū)別數(shù)據(jù)和指令。A、①和②B、①和③C、②和③D、①，②和③標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：暫無解析37、某系統(tǒng)中n個(gè)相互獨(dú)立的生產(chǎn)者進(jìn)程為一個(gè)消費(fèi)者進(jìn)程提供數(shù)據(jù)，假設(shè)每個(gè)生產(chǎn)者提的數(shù)據(jù)寫入各不相同的緩沖區(qū)，且生產(chǎn)者寫緩沖區(qū)的速度比消費(fèi)者讀緩沖區(qū)的速度快，則緩沖區(qū)個(gè)數(shù)的最優(yōu)值應(yīng)為()。A、n一1B、nC、n+1D、2n標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：由于生產(chǎn)者寫緩沖區(qū)的速度比消費(fèi)者讀緩沖區(qū)的速度快，所以為使生產(chǎn)者寫入的數(shù)據(jù)不至丟失最少需n個(gè)緩沖區(qū)供生產(chǎn)者寫入外加1個(gè)單獨(dú)的緩沖區(qū)供消費(fèi)者讀出。故緩沖區(qū)個(gè)數(shù)最優(yōu)值為n+1。選C。38、若用鄰接矩陣存儲(chǔ)有向圖，矩陣中主對(duì)角線以下的元素均為零，則關(guān)于該圖拓?fù)湫蛄械慕Y(jié)論是A、存在，且唯一B、存在，且不唯一C、存在，可能不唯一D、無法確定是否存在標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：鄰接矩陣存儲(chǔ)有向圖且主對(duì)角線以下的元素均為零，說明在此有向圖中，l為起點(diǎn)，n為終點(diǎn)。任何一個(gè)頂點(diǎn)都不能到達(dá)比其號(hào)碼小的頂點(diǎn)。在這種有向圖中拓?fù)湫蛄惺谴嬖诘?，但是可能唯一，也可能不唯一。例如，只有兩個(gè)頂點(diǎn)的有向圖，其拓?fù)湫蛄芯臀ㄒ?。但是，三個(gè)頂點(diǎn)的有向圖中拓?fù)湫蛄芯涂赡懿晃ㄒ涣恕?9、下列關(guān)于無向連通圖特性的敘述中，正確的是____。I．所有頂點(diǎn)的度之和為偶數(shù)Ⅱ．邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1Ⅲ．至少有一個(gè)頂點(diǎn)的度為1A、只有IB、只有ⅡC、I和ⅡD、I和Ⅲ標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：考查無向連通圖的特性。每條邊都連接了兩個(gè)結(jié)點(diǎn)，則在計(jì)算頂點(diǎn)的度之和時(shí)，這條邊都被計(jì)算了兩次，故所有頂點(diǎn)的度之和為邊數(shù)的兩倍，顯然必為偶數(shù)。而Ⅱ和Ⅲ則不一定正確，如對(duì)頂點(diǎn)數(shù)N≥1無向完全圖不存在一個(gè)頂點(diǎn)的度為1，并且邊數(shù)與頂點(diǎn)數(shù)的差要大于1。40、在OSI參考模型中，自下而上第一個(gè)提供端到端服務(wù)的層次是____。A、數(shù)據(jù)鏈路層B、傳輸層C、會(huì)話層D、應(yīng)用層標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：考查OSI模型中傳輸層的功能。傳輸層提供應(yīng)用進(jìn)程間的邏輯通信，即端到端的通信。而網(wǎng)絡(luò)層提供點(diǎn)到點(diǎn)的邏輯通信。因此選B。二、綜合應(yīng)用題(本題共13題，每題1.0分，共13分。)已知某32位二進(jìn)制機(jī)器數(shù)為11000000000000000000000000000000，試計(jì)算在下列各種編碼方式下其代表的真值。41、原碼定點(diǎn)小數(shù)；標(biāo)準(zhǔn)答案：該32位二進(jìn)制機(jī)器數(shù)為原碼定點(diǎn)小數(shù)時(shí)，其真值為一1×2-1=一0．5；知識(shí)點(diǎn)解析：暫無解析42、補(bǔ)碼定點(diǎn)小數(shù)；標(biāo)準(zhǔn)答案：該32位二進(jìn)制機(jī)器數(shù)為補(bǔ)碼定點(diǎn)小數(shù)時(shí)，根據(jù)其符號(hào)位為1可知其為負(fù)數(shù)，為方便計(jì)算，將其連符號(hào)位在內(nèi)取反加1，得其相反數(shù)的補(bǔ)碼機(jī)器數(shù)為0．1000000000000000000000000000000相反數(shù)真值為1×2-1=0．5，故原機(jī)器數(shù)真值為一0．5；知識(shí)點(diǎn)解析：暫無解析43、反碼定點(diǎn)小數(shù)；標(biāo)準(zhǔn)答案：該32位二進(jìn)制機(jī)器數(shù)為反碼定點(diǎn)小數(shù)時(shí)，根據(jù)其符號(hào)位為1可知其為負(fù)數(shù)，故將其數(shù)值位取反即可得其真值對(duì)應(yīng)的原碼機(jī)器數(shù)為1．0111111111111111111111111111111其真值為一(0×2-1+1×2-2+…+1×2-31)=一(2-1一2-31)；知識(shí)點(diǎn)解析：暫無解析44、IEEE754標(biāo)準(zhǔn)短實(shí)數(shù)?！咀ⅰ款}中機(jī)器數(shù)中間加空格是為了讀寫方便，并非機(jī)器數(shù)的一部分，答題時(shí)如有需要可類似表示。標(biāo)準(zhǔn)答案：該32位二進(jìn)制機(jī)器數(shù)表示IEEE754標(biāo)準(zhǔn)短實(shí)數(shù)時(shí)，根據(jù)IEEE754標(biāo)準(zhǔn)的格式，知其為負(fù)數(shù)，寫出隱藏位，得其尾數(shù)的形式如下一1．00000000000000000000000尾數(shù)真值為一1，又IEEE754標(biāo)準(zhǔn)短實(shí)數(shù)階碼采用偏移量為7FH的移碼，故其階碼真值為100000002—011111112=000000012=110，又基數(shù)為2，故題目所求真值為一1×21=一2。知識(shí)點(diǎn)解析：暫無解析45、大部分文件系統(tǒng)以硬盤作為文件存儲(chǔ)器。某一個(gè)文件系統(tǒng)中，其磁盤物理塊的大小為512B，有一個(gè)文件，包含了590個(gè)邏輯記錄，每個(gè)記錄占255B；其中，為檢索方便，采用成組法存儲(chǔ)，在每個(gè)物理塊上只存放2個(gè)記錄。文件A在該文件目錄中的位置如下圖5—2所示。此樹形文件目錄結(jié)構(gòu)由根目錄結(jié)點(diǎn)和作為文件中間的目錄結(jié)點(diǎn)以及作為信息文件的葉結(jié)點(diǎn)組成，每個(gè)目錄項(xiàng)占127B，每個(gè)物理塊存放4個(gè)目錄項(xiàng)。根目錄的內(nèi)容常駐內(nèi)存。(1)若文件采用隱式鏈接文件結(jié)構(gòu)，設(shè)每塊的連接字占4B，存放在每個(gè)物理塊的尾部。如果要將文件A讀人內(nèi)存，至少要讀取幾次硬盤?為什么?(2)若文件采用連續(xù)文件結(jié)構(gòu)，如果要將文件A的邏輯記錄號(hào)為480的記錄讀入內(nèi)存，至少要讀取幾次硬盤?為什么?標(biāo)準(zhǔn)答案：(1)當(dāng)文件采用隱式鏈接文件結(jié)構(gòu)時(shí)，首先計(jì)算找到文件A的讀盤次數(shù)。從根目錄root起，第一次讀硬盤得到bin，dev，home等的信息和目錄mary的盤塊地址。第二次讀硬盤得到doc的地址，第三次讀硬盤得到文件A的地址，第四次開始讀文件A的內(nèi)容。再計(jì)算把文件A讀入內(nèi)存的次數(shù)，所需讀盤次數(shù)為590／2=295次。所以，為把文件A讀入內(nèi)存需讀盤次數(shù)=295+3=298次。(2)當(dāng)文件為連續(xù)結(jié)構(gòu)時(shí)，第三次就能讀硬盤得到文件A的地址，而知道了文件A的地址，通過計(jì)算，只需要1次讀盤就可讀出第480個(gè)邏輯記錄。即共需要讀取4次硬盤，就能將文件A的邏輯記錄號(hào)為480的記錄讀入內(nèi)存。知識(shí)點(diǎn)解析：暫無解析46、在windows操作系統(tǒng)中支持FAT32文件系統(tǒng)，一個(gè)文件的物理結(jié)構(gòu)是用文件分配表FAT來表示的，在FAT32中，文件分配表每個(gè)表項(xiàng)占32位。如果某分區(qū)為FAT32磁盤文件系統(tǒng)，每簇8扇區(qū)，扇區(qū)的大小為512字節(jié)，則該分區(qū)最大可為多少字節(jié)?每個(gè)FAT表占用的存儲(chǔ)空間是多少字節(jié)?標(biāo)準(zhǔn)答案：512B×8×232＝16TB。4B(32位)×232＝16GB。知識(shí)點(diǎn)解析：本題考查FAT文件系統(tǒng)的基本原理。當(dāng)一個(gè)程序?qū)ξ募到y(tǒng)要求提供某一個(gè)文件的內(nèi)容時(shí)，會(huì)到此文件的目錄記錄表去尋找它的第一個(gè)簇號(hào)碼，然后再到FAT記錄表里去找在此鏈表(Chain)里的下一個(gè)簇。此動(dòng)作不斷地重復(fù)直到找到文件的最后一個(gè)簇為止，文件系統(tǒng)可以精確地計(jì)算哪些簇屬于這個(gè)文件及其先后順序。由此方式，文件系統(tǒng)可提供程序所要求之文件的任何部分。這種組織文件的方式稱為FAT鏈(FATChain)，在FAT文件系統(tǒng)下，文件永遠(yuǎn)被分配到整數(shù)單位的簇。例如，在一個(gè)每一簇大小為32K的11GB磁盤中，一個(gè)只包含“Hello，world”這幾個(gè)字符的大小為12字節(jié)文件仍要在磁盤中占32KB的空間。在簇中沒有用到的部分稱為耗損(Slack)，文件的耗損平均為半個(gè)簇。在一個(gè)每簇為16KB的850MB硬盤中其中平均文件大小為50KB的話，每4個(gè)簇約64K只用到50K，浪費(fèi)約14K，大概有21．9％分配給文件的硬盤空間實(shí)際上浪費(fèi)掉了。FAT文件系統(tǒng)將數(shù)個(gè)扇區(qū)合并成一個(gè)簇(Cluster)，作為為文件分配存儲(chǔ)空間時(shí)的基本單位，簇里的扇區(qū)數(shù)目必須是2的n次方。FAT32文件系統(tǒng)中，用32位來表示磁盤簇號(hào)的位數(shù)，每個(gè)分區(qū)最大可存放232＝4294967296個(gè)簇，每個(gè)簇為8X512字節(jié)＝4096字節(jié)，則該分區(qū)最大可存放17592186044416＝16TB。4294967296個(gè)簇號(hào)，每個(gè)簇要1個(gè)FAT表，則FAT表所占的存儲(chǔ)空間是16GB。每簇4096字節(jié)，需要占用4294967296×4÷4096＝4194304個(gè)簇。這里請(qǐng)注意，文件的格式在FATl6到FAT32的過程中有一些變化，F(xiàn)AT32格式會(huì)將扇區(qū)號(hào)在啟動(dòng)區(qū)里注明，并在磁盤上連續(xù)分配，因此在FAT表中只需要存放簇號(hào)即可。事實(shí)上，16TB是理論計(jì)算值，實(shí)際操作系統(tǒng)遠(yuǎn)低于16TB。47、已知在二叉樹中，T為根結(jié)點(diǎn)，*p和*q為二叉樹中兩個(gè)結(jié)點(diǎn)，試編寫求距離它們最近的共同祖先的算法。標(biāo)準(zhǔn)答案：intfound：FALSE；Bitree*Find_Near_Ancient(BitreeT，BitreeP，Bitreeq){／／求二叉樹T中結(jié)點(diǎn)P和q的最近共同祖先Bitreepathp[i00]，pathq[i00]；／／設(shè)立兩個(gè)輔助數(shù)組暫存從根到p，q的路徑Findpath(T，p，pathp，0)；found=FALSE；Findpath(T，q，pathq，0)；／／求從根到p，q的路徑放在pathp和pathq中for(i=0；pathp[i]==pathq[i]&&pathp[i]；i++)；／／查找兩條路徑上最后一個(gè)相同結(jié)點(diǎn)returnpathp[--i]；}voidFindpath(BitreeT，Bitreep，Bitreepath[]，inti){／／求從T到P路徑的遞歸算法if(T==p){found=TRUE；／／找到return：}path[i]=T；／／當(dāng)前結(jié)點(diǎn)存入路徑if(T-＞ichild)Findpath(T-＞ichild，p，path，i+1)；／／在左子樹中繼續(xù)尋找if(T-＞rchild&&!found)Findpath(T-＞rchild，p，path，i+1)；／／在右子樹中繼續(xù)尋找if(!found)path[i]=NULL；／／回溯}知識(shí)點(diǎn)解析：暫無解析48、帶權(quán)圖(權(quán)值非負(fù)，表示邊連接的兩頂點(diǎn)間的距離)的最短路徑問題是找出從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間的一條最短路徑。若最短路徑不止一條，在找到一條最短路徑的同時(shí)，還需要輸出不同最短路徑的條數(shù)?，F(xiàn)有一種解決該問題的方法：(1)初始化結(jié)點(diǎn)集合S為僅包含源結(jié)點(diǎn)s；用一個(gè)整型數(shù)組Counter[v]來記錄從結(jié)點(diǎn)s到結(jié)點(diǎn)v的最短路徑的條數(shù)；各結(jié)點(diǎn)Counter的初始值為0。(2)從未加入S的結(jié)點(diǎn)中選擇當(dāng)前距離最小的結(jié)點(diǎn)v(“當(dāng)前距離”是指從s到v且僅經(jīng)過S中結(jié)點(diǎn)的最短距離)，將其加入S。(3)對(duì)每個(gè)與v相鄰的結(jié)點(diǎn)w，若w不在S內(nèi)，檢查：①若v的加入使得w的當(dāng)前距離變小，則更新w的當(dāng)前距離為(v，w)的邊長與v的當(dāng)前距離之和，并日．令Counter[w]=1。②若v的加入是s到w的長度相同的另一條最短路徑，則Counter[w]++；(4)重復(fù)步驟(2)和(3)，直到所有結(jié)點(diǎn)都被收錄到集合S中。若該方法可行，請(qǐng)證明之；否則，請(qǐng)舉例說明。標(biāo)準(zhǔn)答案：首先，該算法是錯(cuò)誤的。圖8一10給出了反例：設(shè)圖中各邊長為1，則從s到w有3條長度棚同的路徑，而使用此算法得到的結(jié)果為2。問題出現(xiàn)在以下3個(gè)地辦：(1)當(dāng)v的加入產(chǎn)生新的最短路徑時(shí)，從s到v再到w的最短路徑條數(shù)等于v的最短路徑條數(shù)，而不是僅等于1。所以步驟(3)中①的Counter[w]=1應(yīng)改為等于Counter[w]=Counter[v]。(2)若v的加入是s到w的長度相同的另一條最短路徑，則w的最短路徑條數(shù)并不是僅增加了1，而是v帶過來的所有最短路徑。