學(xué)科專業(yè)基礎(chǔ)綜合計算機科學(xué)與技術(shù)聯(lián)考2009年答案

2009年計算機統(tǒng)考參考答12456789BCBCBADABCDCDCAADBDADCACBAABABCADDCA為解決計算機與之間速度不匹配的問題,通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（隊列）棧的定義:棧是只準(zhǔn)在表尾進行插入和刪除的線性表，稱為LIOFO（即后進先出表）。允許插入和刪除的一端叫棧頂，另一端叫棧底。隊列的定義：隊列是允許在一端進行插入而在另一端進行刪除的線性表。允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。隊列也稱為先進先出表（FIFO）樹的定義：樹是包含n個結(jié)點的有限集合圖的定義：圖（Graph）是由非空的頂點集合和一個描述頂點之間關(guān)系——邊（或者?。┑募辖M成。其形式化定義為：G=(V,E）其中G表一個圖，V是圖G中頂點的集合，E是圖G中邊的集合。設(shè)棧S和隊Q的初始狀態(tài)均為空,元素abcdefg依次進入棧S。若每個元素出棧后立即Q7bdcfeag,S的容量？？？（3）N代表二叉樹的根，L代表根結(jié)點的左子樹，R代表根結(jié)點的右子樹。平衡二叉樹定義:若一棵二叉樹中每個結(jié)點的左、右子樹的高度至多相差1，則稱此樹為平衡二叉樹。我們把二叉樹中每個結(jié)點的左子樹高度減去右子樹高度定義為該結(jié)點的平衡因子(balancefactor)。因此，平衡樹中每個結(jié)點的平衡因子只能是1、0或-1。已知一棵完全二叉樹的第6層（設(shè)根為第1層）8個葉結(jié)點，則完全二叉樹的結(jié)點個數(shù)最多是？？？（111）二叉樹：二叉樹是一種重要的樹形結(jié)構(gòu)，它是（n>=0個結(jié)點的有限集，其子樹分為互不相交的兩個集合，分別稱為左子樹和右子樹，左子樹和右子樹也是如上定義的二叉樹。左子樹和右子樹的順序不能互換。滿二叉樹：深度為k結(jié)點數(shù)為2^k-1的二叉樹完全二叉樹：若對滿二叉樹的結(jié)點從上到下從左到右進行編號，則深度為k且有n個結(jié)點的二叉樹當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹的編號從1到n一一對應(yīng)時，將森林轉(zhuǎn)換為對應(yīng)的二叉樹，若在二叉樹中，結(jié)點u是結(jié)點v的父結(jié)點的父結(jié)點，則在原來的森林中，u和v可能具有的關(guān)系是:父子關(guān)系或兄弟關(guān)系。森林轉(zhuǎn)換為對應(yīng)的二叉樹:兄弟之間連線，父只與長子連線。（左孩子右兄弟無向連通圖特性的敘述:所有頂點的度之和為偶數(shù)。頂點的度定義：與定點v相關(guān)聯(lián)的邊數(shù)(每個環(huán)計算兩次)。度為零的頂點稱為孤立頂點，度為奇數(shù)的頂點稱為奇點，度為偶數(shù)的頂點稱為偶點。一棵m階B樹（1970年，R.Bayer和E.mccreight提出了一種適用于外查找的樹，它是定義⑴樹中每個結(jié)點至多有m個孩子；⑵除根結(jié)點和葉子結(jié)點外，其它每個結(jié)點至少m/2個孩子⑶若根結(jié)點不是葉子結(jié)點，則至少有2個孩子(除非B樹只有一個結(jié)點)； 所有葉子結(jié)點都出現(xiàn)在同一層，葉子結(jié)點不包含任何關(guān)鍵字信息；⑸有k個孩子的非終端結(jié)點恰好包含有k-1個關(guān)鍵字(各節(jié)點內(nèi)關(guān)鍵字均升序或降序排堆(Heap)分為小根堆和大根堆兩種，對于一個小根堆，它是具有如下特性的一棵完全二叉樹：若樹根結(jié)點存在左孩子，則根結(jié)點的值(或某個域的值)小于等于左孩子結(jié)點的值(或某個域的值)；若樹根結(jié)點存在右孩子，則根結(jié)點的值(或某個域的值)小于等于右孩子結(jié)點的值(或某個域的值)；以左、右孩子為根的又各是一個堆大根堆的定義與上述類似，只要把小于等于改為大于等于就得到了由堆的定義可知，若一棵完全二叉樹是堆，則該樹中以每個結(jié)點為根的也都是一個堆。別為一個小根堆和一個大根堆。根據(jù)堆的定義可知堆頂結(jié)點即整個完全二叉樹的根結(jié)點，對于小根堆來說具有最小值，對于大根堆來說具有最大值。堆排序利用了大根堆(或小根堆)堆頂記錄的關(guān)鍵字最大(或最小)這一特征，使得在當(dāng)前無序區(qū)中選取最大(或最小)關(guān)鍵字的記錄變得簡單。當(dāng)向一個小根堆插入一個具有最小值的元素時,該元素需要逐層向上調(diào)整,直到被調(diào)整到堆頂位置為止。數(shù)據(jù)元素序列11，12，13，7，8，9，23，4，5是第二趟排序后的結(jié)果，則該排序算法只能是插入排序。氣泡排序基本思想：設(shè)待排序?qū)ο笮蛄兄械膶ο髠€數(shù)為n。一般地，第i趟起泡排序從1n-i+1依次比較相鄰的記錄被交換到第n-i+1的位置上，最多作n-1趟。簡單選擇排序基本思想：第一趟在R[1..n]中選最小的，與R[1]交第二趟在R[2..n]中選最小的，與R[2]交換，依次類推，進行n-1次選擇后，整個文件有序。直接插入排序基本思想:將一個記錄插入到已排序的有序表中，使插入后的表仍然有序。折半插入排序基本思想：將一個記錄插入到已排序的有序表中，使插入后的表仍然有序，但插入時利用折半搜索法尋找元素的插入位置。歸并排序基本思想：又一類不同的排序方法，將兩個或兩個以上的有序表合并成一個新的有序表?？焖倥判蚧舅枷耄喝[1..n]中任一記錄作為“樞軸”，一趟排序之后樞軸的值均小于“樞軸”左邊的值，樞軸右邊的值均大于“樞軸”的值。堆排序基本思想：如何將一個無序序列調(diào)整為堆？如何在互換堆頂之后重新調(diào)整為堆（排序(SSort)基本思想：n大，劃分成若干子序列，分別直接插入排序。待整個記錄“基本有序”時，對整體直接重排。馮·計算機中指令和數(shù)據(jù)均以二進制形式存放在器中，CPU區(qū)分它們的依據(jù)是指令周期的不同階段。十進制轉(zhuǎn)換：十進制轉(zhuǎn)任意進制的通用方法是：除x取余倒排法（x代表進制數(shù)）。如：將十進制數(shù)76轉(zhuǎn)換成任意進制轉(zhuǎn)成二進制76/2...=/2...=/2...=9/2...=4/2...=2/2...=1/2...76(10) 轉(zhuǎn)成八進制76/8...=9/8...=1/8...76(10)=轉(zhuǎn)成十六進制76/16...=4/16...B：二進制數(shù)。Q：八進制數(shù)。D：十進制數(shù)。負(fù)數(shù)用十六進制和八進制怎么表示？使用補碼（二進制），而且還要指定字長比如說一個二字節(jié)整型的-2就應(yīng)該是：八進制：177776浮點數(shù)加減運算過程一般包括對階、尾數(shù)運算、規(guī)格化、舍入和判溢出等步驟。設(shè)浮點數(shù)的階碼和尾數(shù)均采用補碼表示，且位數(shù)分別57位（均2位符號位）。若有兩個數(shù)X=2^7*29/32，Y=2^5*5/8,則用浮點加法計算X+Y的最終結(jié)果是發(fā)生溢出浮點數(shù)表示：小數(shù)點的位置可以在一定范圍內(nèi)浮動。E為階，包括階符和階碼（整數(shù)），階碼為數(shù)決定了浮點數(shù)的表示范圍。對階原則：小階對大階。雙符號位判溢：加，減后。兩個符號位出現(xiàn)“01”，表示已經(jīng)溢出，即結(jié)果大于器的分類：按介子分:(1)半導(dǎo)體器;(2)磁表面器;(3)光介子器。DAM用于存放計算機運行期間的大量程序和數(shù)據(jù)的器，CPU能直接。由MOS器構(gòu)成Cache是介于CPU和主存之間高速小容量器，用于存放最活躍的程序塊和數(shù)據(jù)。由靜MOS器構(gòu)成特點：速度快，但容量小，位價格較高主存和Cache一起構(gòu)成計算機的內(nèi)器（內(nèi)存），是CPU能直接的器存放當(dāng)前暫不參與運行的程序和數(shù)據(jù)，需要時再與主存成批交換信息的器。特點是容量大，可存放大量的程序和數(shù)據(jù)，但速度慢?？刂破髟谖⒊绦蚩刂频挠嬎銠C中，用于存放執(zhí)行指令的微程序的器。CMROM其它分類：按讀寫功能分類：只讀器(ROM):工作時只能讀出不能寫入的器。讀寫器(RAM):既能讀出又能寫入的器按信息的可保存性分類永久性器：指斷電后仍能保存信息的器，如磁表面器。非永久性器:指斷電后信息即的器，如半導(dǎo)體讀寫器。某計算機Cache16塊，采用2路組相連映射方式（即每組2）。每個主存塊大小32129Cache(4)主存容量是根據(jù)地址線的位數(shù)來確定的,在16位PC機中地址總線的寬度是20位,則主存大小為:2^20byte=1MB,PC32為:2^32,即主存最大容量為4GB某計算機主存容量為64KB，其中ROM區(qū)為4KB，其余為RAM區(qū)，按字節(jié)編址?，F(xiàn)要用2K*8位的ROM和4K*4位的RAM來設(shè)計該器，則需要上述規(guī)格的ROM數(shù)和RAM數(shù)分別是230一字節(jié)為操作碼字段，第二字節(jié)為相對位移量字段。假定取指令時，每取一字節(jié)PC自動加相對尋址:以當(dāng)前程序計數(shù)器pc的內(nèi)容為基址，加上指令給出的一字節(jié)補碼數(shù)（偏移量）形成新的pc值的尋址方式稱為相對尋址。目的地址=源地址+相對轉(zhuǎn)移指令字節(jié)數(shù)+指令中給定的偏移量RISC(精簡指令系統(tǒng))的敘述:(2).指令長度固定，指令格式及尋址方式種類少；只有取數(shù)/存數(shù)指 器，其余指令的操作都在寄存器之間進行；指令周期是取出并執(zhí)行一條指令的時間。指令周期常常有若干個CPU周期，CPU周期也稱為機器周期，由于CPU一次內(nèi)存所花費的時間較長，因此通常用內(nèi)存中一個指令字的最短時間來規(guī)定CPU周期。這就是說一條指令取出階段（通常為取指）需要一個CPU周期時間。而一個CPU周期時間又包含若干個時鐘周期(通常為節(jié)拍脈沖或Ｔ周期，它是處理操作的最基本的單位)。這些時鐘周期的總和則規(guī)定了一個CPU周期的時間寬度。某計算機的指令流水線由四個功能段組成，指令流經(jīng)各功能段的時間（忽略各功能段之間的緩沖時間）分別是90ns、80ns、70ns、60ns，則計算機的CPU時鐘周期是(90ns)。相對于微程序控制器，硬布線控制器的特點是指令執(zhí)行速度快，指令功能的修改和擴展難。假設(shè)某系統(tǒng)總線在一個總線周期中并行傳輸4字節(jié)信息，一個總線周期占用2個時鐘周期，總線時鐘頻率為10MHz，則總線帶寬是(20MB/S)時鐘周期和時鐘頻率互為倒數(shù)關(guān)系。1KHz=1000Hz；并行總線帶寬(MB/s)(MHz)*(bit/8B)*輸幾組數(shù)據(jù)(cycle)串行總線帶寬(MB/s)(MHz)*(bit/8B)*管線*編碼方式*每時鐘傳輸幾組數(shù)據(jù)(cycle)假設(shè)某計算機的系統(tǒng)由Cache和主存組成，某程序執(zhí)行過程中訪存1000次，其中Cache缺失（未命中）50次，則Cache中率是(95%)能引起外部中斷的是:鍵盤輸入(人的干預(yù))或外請求。（外中斷都是強迫中斷單處理機系統(tǒng)中，可并行的是（II、III和IIIIIIIV進程調(diào)度算法中，綜合考慮進程等待時間和世間是:(高響應(yīng)比優(yōu)先調(diào)度算法FCFS:誰先到就緒隊列,將處理機分給誰;時間片輪轉(zhuǎn)調(diào)度法:以先來后到的次序+時間片輪優(yōu)先級調(diào)度:選優(yōu)先級最高的進程占用處理機(優(yōu)先級可動態(tài)改變);短進程優(yōu)先:取所需的運行時間最短的進程(該算法能使平均等待時間最短).某計算機系統(tǒng)有8臺，有K個進程競爭使用，每個進程最多需要3臺。該系統(tǒng)可能會發(fā)生死鎖的K的最小值是(4)分區(qū)分配內(nèi)存管理方式的主要保護措施是(界地址保護)一個分段管理系統(tǒng)中，地址長度為32位，其中段號占8位，則最大段長是(2^24).分分頁:信息的物理單 大小一樣，由系統(tǒng)固 地址空間是一維分段:信息的邏輯單 文件物理結(jié)構(gòu)中，適合隨機且易于文件擴展的是(索引結(jié)構(gòu)連續(xù)結(jié)構(gòu):將一個文件中邏輯上連續(xù)的信息存放到介質(zhì)的依次相鄰的塊上便形成順序結(jié)構(gòu)，這類文件叫連續(xù)文件，又稱順序文件。優(yōu)點：簡單;支持順序存取和隨機存?。豁樞虼嫒∷俣瓤?；所需的磁盤尋道次數(shù)和尋道時間最少.缺點：建立文件前需要能預(yù)先確定文件長度，以便分配空間；修改、插入和增生文件記錄有；對直接器作連續(xù)分配，會造成少量空閑塊的浪費。結(jié)構(gòu)：一個文件的信息存放在若干不連續(xù)的物理塊中，各塊之間通過指針連接，前一個物理塊指向下一個物理塊。優(yōu)點：提高了磁盤空間利用率,不存在外部碎片問題；有利于文件插入和刪除；有利于文件動態(tài)擴充.缺點：存取速度慢，不適于隨機存取；可靠性問題，如指針出錯；的尋道次數(shù)和尋道時間；指針占用一定的空間.索引結(jié)構(gòu)：一個文件的信息存放在若干不連續(xù)物理塊中，系統(tǒng)為每個文件建立一個數(shù)據(jù)結(jié)構(gòu)----索引表。表中每一欄目文件信息所在的邏輯塊號和與之對應(yīng)的物理塊號。索引表的物理地址則由文件說明信息項給出。優(yōu)點：保持了結(jié)構(gòu)的優(yōu)點,又解決了其缺點；即能順序存取,又能隨機存?。粷M足了文件動態(tài)增長、插入刪除的要求；也能充分利用外存空間。缺點：較多的尋道次數(shù)和尋道時間；索引表本身帶來了系統(tǒng)開銷如：內(nèi)外存空間，存取時間。SCAN調(diào)度(電梯調(diào)度)算法:電梯調(diào)度算法基于日常生活中的電梯工作模式：電梯保持按一個方向移動，直到在那個方向上沒有請求為止，然后改變方向。反映在磁盤調(diào)度上，總是沿著移動臂的移動方向選擇距離磁頭當(dāng)前位置最近的I/O請求作為下一次調(diào)度的對象。如果該方向上已無I/O請求，則改變方向再做選擇。假設(shè)磁頭當(dāng)前位于第105道，正在向磁道序號增加的方向移動。現(xiàn)在一個磁道請求序列為35，45，12，68，110，180，170，195，采用SCAN調(diào)度（電梯調(diào)度）算法得到的磁道訪問序列是：110,170,180,195,68,45,35,12。文件系統(tǒng)中，文件控制信息的合理位置是(文件控制塊)硬：在磁盤上有一份內(nèi)容一樣的文件產(chǎn)生，但不改變文件的Inode,也就是與原文件共用Inode。軟：不在磁盤上有一份內(nèi)容一樣的文件產(chǎn)生，但產(chǎn)生新的Inode設(shè)文件F1的當(dāng)前計數(shù)值為1，先建立F1的符號（軟）文件F2，再建立F1的硬文件F3，然后刪除F1。此時，F(xiàn)2和F3的計數(shù)值分別是（1，1）。程序員利用系統(tǒng)調(diào)用打開I/O設(shè)備時，通常使用的設(shè)備標(biāo)識是（邏輯設(shè)備名）在OSI參考模型中，自下而上第一個提供端到端服務(wù)的層次是（傳輸層）。自下而上方法的一般從檢查物理層開始。自下而上分別稱為：物理層、數(shù)據(jù)鏈路層、網(wǎng)絡(luò)層、傳輸層、會話層、表示層和應(yīng)用層。34.1924(Nyquist)就推導(dǎo)出在理想低通信道的最高大碼元傳輸速率的:理想低通信道的最高大碼元傳輸速率C=2W.log2N (其中W是想低通信道的帶寬,N是電信道帶寬與數(shù)據(jù)傳輸速率的關(guān)系可以奈(Nyquist)準(zhǔn)則與(Shanon)定律描述。奈定理描述了有限帶寬、無噪聲信道的最大數(shù)據(jù)傳輸速率與信道帶寬的關(guān)系。定理則描述了有限帶寬、有隨機熱噪聲信道的最大傳輸速率與信道帶寬、信噪比之間的關(guān)系。奈準(zhǔn)則對于二進制數(shù)據(jù)信號的最大數(shù)據(jù)傳輸速率Rmax與通信信道帶寬B（B=f,單位Hz)的關(guān)系可以寫為：Rmax＝2*B(bps)定理：在有隨機熱噪聲的信道上傳輸數(shù)據(jù)信號時，數(shù)據(jù)傳輸速率Rmax與信道帶Rmax＝B*log2(1+S/N))[以2為底,1+S/N的對數(shù)]式中，Rmaxbps,帶寬BHzS/Nd（分貝數(shù)表示。若S/N=30(dB),那么信噪比根據(jù)：S/N(dB)=10*lg(S/N)則S/N=1000。若帶寬B=3000Hz，則Rmax≈對于帶寬為6MHz的信道，若用4種不同的狀態(tài)來表示數(shù)據(jù)，在不考慮熱噪聲的情況下，答：由無熱噪聲的奈 :C=2Hlog2N=2*6M*log24=24Mbps，即該信道的最大數(shù)據(jù)傳輸速率是24Mbps在無噪聲情況下，若某通信鏈路的帶寬為3KHz,采用4個相位，每個相位具有4種振幅的QAM調(diào)制技術(shù)，則該通信鏈路的最大數(shù)據(jù)傳輸速率是(24kbps)后退N幀ARQ就是從出錯處重發(fā)已發(fā)出過的N個幀數(shù)據(jù)鏈路層采用了后退N幀（GBN）協(xié)議，發(fā)送方已經(jīng)發(fā)送了編號為0~7的幀。當(dāng)計時器超時時，若發(fā)送收到0、2、3號幀的確認(rèn)，則發(fā)送方需要重發(fā)的幀數(shù)是(4)。以太網(wǎng)交換機進行轉(zhuǎn)發(fā)決策時使用的PDU地址是(目的物理地址)。ARP協(xié)議是“AddressResolutionProtocol”（地址解析協(xié)議）的縮寫。在局域網(wǎng)中，網(wǎng)絡(luò)中實際傳輸?shù)氖恰皫?，幀里面是有目?biāo)主機的MAC地址的。在以太網(wǎng)中，一個主機要和另一個主機進行直接通信，必須要知道目標(biāo)主機的MAC地址。但這個目標(biāo)MAC地址是如何獲得的呢？它就是通過地址解析協(xié)議獲得的。所謂“地址解析”就是主機在發(fā)送幀前將目標(biāo)IP地址轉(zhuǎn)換成目標(biāo)MACARP協(xié)議的基本功能就是通過目標(biāo)設(shè)備的IP地址，查詢目標(biāo)設(shè)備的MAC地址，以保證通信的順利進行。CSMA/CD是一種分布式介質(zhì)控制協(xié)議，網(wǎng)中的各個站（節(jié)點）都能獨立地決定數(shù)據(jù)幀的發(fā)送與接收。每個站在發(fā)送數(shù)據(jù)幀之前，首先要進行載波，只有介質(zhì)空閑時，才允許發(fā)送幀。這時，如果兩個以上的站同時到介質(zhì)空閑并發(fā)送幀，則會產(chǎn)生現(xiàn)象，這使發(fā)送的幀都成為無效幀，發(fā)送隨即失敗。每個站必須有能力隨時檢測是否發(fā)生，一旦發(fā)生，則應(yīng)停止發(fā)送，以免介質(zhì)帶寬因傳送無效幀而被白白浪費，然后隨機延時一段時間后，再重新爭用送幀。CSMA/CD協(xié)議簡單、可靠，其網(wǎng)絡(luò)系統(tǒng)（Ethernet）被廣泛使用。在一個采用CSMA/CD協(xié)議的網(wǎng)絡(luò)中，傳輸介質(zhì)是一根完整的電纜，傳輸速率為1Gbps,電纜中的信號速度是200000km/s。若最小數(shù)據(jù)幀長度減少800比特，則最遠(yuǎn)的兩個站點之間的距離至少需要(減少80)。最短幀長=2*L*10^9(b/s)÷200主機甲和主機乙之間建立一個TCP連接,主機甲向主機乙發(fā)送了兩個連續(xù)的TCP段,分別含300字節(jié)和500字節(jié)的有效載荷,第一個段的序列號為200,主機乙正確接收到兩個段后,發(fā)送給主機甲的確認(rèn)序列號是(1000)。例如，序列號等于前一個報文段的序列號與前一個報文段中數(shù)據(jù)字節(jié)的數(shù)量之和。例如，假設(shè)源主機發(fā)送3個報文段，每個報文段有100字節(jié)的數(shù)據(jù)，且第一個報文段的序列號是1000，那么接收到第一個報文段后，目的主機返回含確認(rèn)號1100的報頭。接收到第二個報文段（其序號為1100）后，目的主機返回確認(rèn)號1200。接收到第三個報文段后，目的主機返回確認(rèn)號1300。確定擁塞窗口的大小的過程：在剛建立連接時，將擁塞窗口的大小初始化為該連接所需的最大連接數(shù)據(jù)段的長度值，并發(fā)送一個最大長度的數(shù)據(jù)段（當(dāng)然必須是接收窗口允許的。如果在定時器超時前得到確認(rèn)，將擁塞窗口的大小增加一個數(shù)據(jù)段的字節(jié)數(shù)，并發(fā)送兩個數(shù)據(jù)段，如果每個數(shù)據(jù)段在定時器超時前都得到確認(rèn)，就再在原基礎(chǔ)上增加一倍，即為4個數(shù)據(jù)段的大小，如此反復(fù)，每次都一次的基礎(chǔ)上加倍。當(dāng)定時器超時或達(dá)到發(fā)送窗口設(shè)定值，停止擁塞窗口尺寸的增加。這種反復(fù)稱為慢速啟動，所有的TCP協(xié)議都支持這種方法。一個TCP接總是以1KB的最大段發(fā)TCP段，發(fā)送方有足夠多的數(shù)據(jù)要發(fā)送。當(dāng)擁塞窗口為16KB時發(fā)生了超時，如果接下來的4RTT（往返時間）時間內(nèi)的TCP段的傳輸都是成功的，那么當(dāng)?shù)?RTT時間內(nèi)發(fā)送的所有TCP段都得到肯定應(yīng)答時，擁塞窗口大小是FTP客戶和服務(wù)器間傳遞FTP時，使用的連接是(建立在TCP之上的控制連接)。該方法求得的路徑不一定是最短路徑。例如，對于下圖所示的帶權(quán)圖，如果按照題中的原則，ACA→B→C，事實上其最短路徑為A→D→C（1）算法基本思想如下：從頭至尾遍歷單鏈表，并用指針P指向當(dāng)前節(jié)點的前K個節(jié)到鏈表的最后一個節(jié)點時，指針P所指向的節(jié)點即為所查找的節(jié)點。詳細(xì)實現(xiàn)步驟：增加兩個指針變量和一個整型變量，從鏈表頭向后遍歷，其中指針P1指前遍歷的節(jié)點，指針PP1所指向節(jié)點的前K個節(jié)點，如P1之前沒有K個節(jié)點，那么P指向表頭節(jié)點。用整型變量i表示當(dāng)前遍歷了多少節(jié)點，當(dāng)i>k時，指針p隨著每次遍歷，也向前移點。當(dāng)遍歷完成時，p或者指向表頭就節(jié)點，或者指向鏈表中倒數(shù)第K個位置上的節(jié)點。算法描述：IntLocateElement(linklistlist,int P1=list- }if(p==list)return0;k{return1;}}（1）在中斷方式下，每32位（4B）被中斷一次，故每秒中斷0.5MB/4B=0.5×106/4=12.5×104要注意的是，這里是數(shù)據(jù)傳輸率，所以1MB=106B。因為中斷服務(wù)程序包含18條指令，中斷服務(wù)的其他開銷相當(dāng)于2條指令的執(zhí)行時間，且執(zhí)行每條指令平均需5個時鐘周期，所以，1秒內(nèi)的時鐘周期數(shù)為（2）在DMA方式下，每秒進行DMA操5MB/5000B=5×106/5000=1×103次因為DMA預(yù)處理和后處理的總開銷為500個時鐘周期，所以1秒鐘之內(nèi)用于DMA操作的時鐘周期數(shù)為故在DMA方式下，占整個CPU時間的百分比是（5×105）/（500×106指令執(zhí)行階段每個節(jié)拍的功能和有效控制信號如下所示時鐘功能有效控制信號C5MAR←(R1)PCout,MARinC6MDR←M(MAR)MemR,MDRinEC7A←(R0)C8AC←(MDR)+(A)MDRout,Addr,ACinC9MDR←(AC)ACout,MDRinC10M(MAR)←MDR之間的同步；mutex控制進程間互斥使用緩沖區(qū)。程序如下Vars1=0,s2=0,empty=N,mutex=1;頁內(nèi)頁內(nèi)的位，機制的位則就是頁號不命：不命中頁頁內(nèi)存地址缺內(nèi)存地 命內(nèi)存地根據(jù)頁式管理的工作原理，應(yīng)先考慮頁面大小，以便將頁號和頁內(nèi)位移分解出來。頁面大小為4KB，即212，則得到頁內(nèi)位移占虛地址的低12位，頁號占剩余。可得P（4低三位正好為頁內(nèi)位移，最為頁號：址后主存100ns，共計10ns+100ns+100ns=210ns。理地址后主存100ns，共計10ns+100ns+108ns+100ns≈108ns。25A5H：P=2，快表，因第一次已將該頁號放入快表，因此花費10ns便可合成物理地址，主存100ns，共計10ns+100ns=110ns。當(dāng)虛地址1565H時，產(chǎn)生缺頁中斷，合法駐留集為2，必須從頁表中淘汰一個頁面，根據(jù)題目的置換算法，應(yīng)淘汰0號頁面，因此1565H