數(shù)據(jù)結(jié)構(gòu)要點第一章概論************************************************************************數(shù)據(jù)就是指能夠被計算機識別、存儲和加工處理的信息的載體。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，可以由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是具有獨立含義的最小標識單位。數(shù)據(jù)結(jié)構(gòu)的定義：?邏輯結(jié)構(gòu)：從邏輯結(jié)構(gòu)上描述數(shù)據(jù)，獨立于計算機。?線性結(jié)構(gòu)：一對一關(guān)系。線性結(jié)構(gòu)：多對多關(guān)系。存儲結(jié)構(gòu)：是邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)。?順序存儲結(jié)構(gòu)：如數(shù)組。鏈式存儲結(jié)構(gòu)：如鏈表。索引存儲結(jié)構(gòu)：?稠密索引：每個結(jié)點都有索引項。稀疏索引：每組結(jié)點都有索引項。散列存儲結(jié)構(gòu)：如散列表。數(shù)據(jù)運算。?對數(shù)據(jù)的操作。定義在邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有?個運算集合。常用的有：檢索、插入、刪除、更新、排序。************************************************************************數(shù)據(jù)類型：是一個值的集合以及在這些值匕定義的一組操作的總稱。?原子類型：由語言提供。結(jié)構(gòu)類型：由用戶借助于描述機制定義，是導(dǎo)出類型。抽象數(shù)據(jù)類型ADT：?是抽象數(shù)據(jù)的組織和與之的操作。相當于在概念層上描述問題。優(yōu)點是將數(shù)據(jù)和操作封裝在一起實現(xiàn)了信息險藏。程序設(shè)計的實質(zhì)是對實際問題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，設(shè)計一個好的算法。算法取決了數(shù)據(jù)結(jié)構(gòu)。************************************************************************算法是一個良定義的計算過程，以一個或多個值輸入，并以一個或多個值輸出。評價算法的好壞的因素：-算法是正確的：執(zhí)行算法的時間；執(zhí)行算法的存儲空間(主要是輔助存儲空間)；算法易于理解、編碼、調(diào)試。************************************************************************時間復(fù)雜度：是某個算法的時間耗費，它是該算法所求解問題規(guī)模n的函數(shù)。漸近時間復(fù)雜度：是指當問題規(guī)模趨向無窮大時，該算法時間復(fù)雜度的數(shù)量級。空間復(fù)雜度：是某個算法的空間耗費，它是該算法所求解問題規(guī)模n的函數(shù)。算法的時間復(fù)雜度和空間復(fù)雜度合稱算法復(fù)雜度。第二章線性表線性表是由n'O個數(shù)據(jù)元素組成的有限序列。n=0是空表：非空表，只能仃一個開始結(jié)點，仃且只能有一個終端結(jié)點。線性表上定義的基本運算：?構(gòu)造空表：Initlist(L)*************************************************順序表是按線性表的邏輯結(jié)構(gòu)次序依次存放在一組地址連續(xù)的存儲單元中。在存儲單元中的各元素的物理位置和邏輯結(jié)構(gòu)中各結(jié)點相鄰關(guān)系是?致的。地址計算：LOCa(i尸LOCa(l)+(i?l)*d；(首地址為1)在順序表中實現(xiàn)的基本運算：?插入：平均移動結(jié)點次數(shù)為n/2：平均時間復(fù)雜度均為O(n)。刪除：平均移動結(jié)點次數(shù)為(n-l)/2；平均時間更雜度均為O(n)。************************************************************************線性表的鏈式存儲結(jié)構(gòu)中結(jié)點的邏輯次序和物理次序不一定相同，為了能正確表示結(jié)點間的邏輯關(guān)系，在存儲每個結(jié)點值的同時，還存儲了其后繼結(jié)點的地址信息(即指針或鏈)。這兩部分信息組成鏈表中的結(jié)點結(jié)構(gòu)。一個單鏈表由頭指針的名字來命名。************************************************************************單鏈表運算：?建立單鏈表?頭插法：s->next=hcad；hcad=s；生成的順序與輸入順序相反。平均時間復(fù)雜度均為O(n)。尾插法：head=rear=null：if(head=null)head=s;elser->next=s;r=s;平均時間復(fù)雜度均為O(n)加頭結(jié)點的算法：對開始結(jié)點的操作無需特殊處理，統(tǒng)一了空表和非空表。杳我?按序號：與查找位置有關(guān)，平均時間復(fù)雜度均為O(n)。按值：與輸入實例有關(guān)，平均時間復(fù)雜度均為O(n)。插入運算：p=GetNode(L,i-l)：s->next=p->next；p->next=s：平均時間復(fù)雜度均為O(n)刪除運算：p=GetNode(L,i-l);r=p->next；p->next=r->next；free(r)；平均時間復(fù)雜度均為O(n)單循環(huán)鏈表是一種首尾相接的單鏈表，終端結(jié)點的指針域指向開始結(jié)點或頭結(jié)點。鏈表終止條件是以指針等于頭指針或尾指針。采用單循環(huán)鏈表在實用中多采用尾指針表示單循環(huán)鏈表。優(yōu)點是查找頭指針和尾指針的時間都是0(1),不用遍歷整個鏈表。雙鏈表就是雙向鏈表，就是在單鏈表的每個結(jié)點里再增加一個指向其直接前趨的指針域prior,形成兩條不同方向的鏈。由頭指針head惟-確定。雙鏈表也可以頭尾相鏈接構(gòu)成雙(向)循環(huán)鏈衣。雙鏈表上的插入和刪除時間或雜度均為0(l)o************************************************************************順序表和鏈表的比較：?基于空間：?順序表的存儲空間是靜態(tài)分配，存儲密度為1;適于線性表事先確定其大小時采用。鏈表的存儲空間是動態(tài)分配，存儲密度＜1:適于線性去長度變化大時采用。?基于時間：?順序表是隨機存儲結(jié)構(gòu)，當線性表的操作主要是查找時，宜采用。以插入和刪除操作為主的線性表宜采用鏈表做存儲結(jié)構(gòu)。若插入和刪除主要發(fā)生在表的首尾兩端，則宜采用尾指針衣示的單循環(huán)鏈表。第三章棧和隊列************************************************************************棧(Stack)是僅限制在表的端進行插入和刪除運算的線性表，稱插入、刪除這?端為棧頂，另端稱為棧底。表中無元素時為空棧。棧的修改是按后進先出的原則進行的，我們又稱枝為LIFO表(LastInFirstOut)。通常棧有順序棧和鏈棧兩種存儲結(jié)構(gòu)。棧的基本運算有六種：-構(gòu)造空棧：InitStack(S),判棧空：StackEmpty(S)判棧滿：StackFull(S),進棧：Push(S,x)退棧：Pop(S)取棧頂元親:StackTop(S)隊列(Queue)是一種運算受限的線性表，插入在表的一端進行，而刪除在表的另一端進行，允許刪除的一端稱為隊頭(front),允許插入的一端稱為隊尾(rear),隊列的操作原則是先進先出的，又稱作FIFO表(FirstInFirslOut)。隊列也仃順序存儲和鏈式存儲兩種存儲結(jié)構(gòu)。************************************************************************隊列的基本運算有六種：?置空隊：InitQueue(Q)?制隊空：QueueEmpty(Q)?判隊滿：QueueFull(Q)?入隊：EnQucuc(Q,x)?出隊：DeQucuc(Q)?取隊頭元素：QucucFront(Q)順序隊列的“假上溢”現(xiàn)象：由于頭尾指針不斷前移，超出向量空間。這時整個向量空間及隊列是空的卻產(chǎn)生了“上溢”現(xiàn)象。為了克服“假上溢”現(xiàn)象引入循環(huán)向量的概念，是把向量空間形成個頭尾相接的環(huán)形，這時隊列稱循環(huán)隊列。判定循環(huán)隊列是空還是滿，方法有三種：-?種是另設(shè)?個布爾變量來判斷；第二種是少用一個元素空間，入隊時先測試((rear+l)%m=front)?滿：空：第三種就是用一個計數(shù)器記錄隊列中的元素的總數(shù)。************************************************************************隊列的鏈式存儲結(jié)構(gòu)稱為鏈隊列，一個鏈隊列就是一個操作受限的單鏈表。為了便于在表尾進行插入(入隊)的操作，在表尾增加一個尾指針，一個鏈隊列就由一個頭指針和一個尾指針唯一地確定。鏈隊列不存在隊滿和上溢的問題。在鏈隊列的出隊算法中，要注意當原隊中只有一個結(jié)點時，出隊后要同進修改頭尾指針并使隊列變空。第四章串串的基本運算有：?求申長strlen(char*s)strcpy(char*to,char*from),串聯(lián)接strcat(char*to,char*from),串比較charcmp(char*sl,char*s2),字符定位strchr(char*s,charc).串是特殊的線性表(結(jié)點是字符)，所以串的存儲結(jié)構(gòu)與線性表的存儲結(jié)構(gòu)類似。串的順序存儲結(jié)構(gòu)簡稱為順序申。順序串又可按存儲分配的不同分為：?靜態(tài)存儲分配：直接用定長的字符數(shù)組來定義。優(yōu)點是涉及串長的操作速度快，但不適合插入、鏈接操作。?動態(tài)存儲分配：是在定義串時不分配存儲空間，需要使用時按所需串的長度分配存儲單元。************************************************************************串的鏈式存儲就是用單鏈表的方式存儲串值，串的這種鏈式存儲結(jié)構(gòu)簡稱為鏈串。鏈串與單鏈表的差異只是它的結(jié)點數(shù)據(jù)域為單個字符。為了解決“存儲密度”低的狀況，可以讓一個結(jié)點存儲多個字符，即結(jié)點的大小。************************************************************************第五章多維數(shù)組和廣義表數(shù)組一般用順序存儲的方式表示。存儲的方式有：-行優(yōu)先順序，也就是把數(shù)組逐行依次排列。PASCAL.C?列優(yōu)先順序，就是把數(shù)組逐列依次排列。FORTRAN************************************************************************地址的計算方法：?按行優(yōu)先順序排列的數(shù)組：LOCa(ij尸LOCa(U)+((i-l)*n+(H))*d。按列優(yōu)先順序排列的數(shù)組:LOCa(ij)=LOCa(ll)+((j-l)*n+(i-l))*d.************************************************************************矩陣的壓縮存儲：為多個相同的非零元素分配?個存儲空間；對零元素不分配空間。特殊矩陣的概念：所謂特殊矩陣是指非零元素或零元素分布有一定規(guī)律的矩陣。稀疏矩陣的概念：一個矩陣中若其非零元素的個數(shù)遠遠小于零元素的個數(shù)，則該矩陣稱為稀疏矩陣。************************************************************************稀疏矩陣的壓縮存儲方式用三元組表把非零元素的值和它所在的行號列號做為一個結(jié)點存放在一起，用這些結(jié)點組成的一個線性表來表示O但這種壓縮存儲方式將失去隨機存儲功能。加入行表記錄每行的非零元素在三元組表中的起始位置，即帶行表的三元組表。************************************************************************廣義表是n(n20)個元素的有限序列，其中的元素是原/或者是?個廣義表。第六章樹************************************************************************樹是n個結(jié)點的有限集合，非空時必須滿足：只有一個稱為根的結(jié)點；其余結(jié)點形成m個不相交的子集，并稱根的子樹。根是開始結(jié)點：結(jié)點的子樹數(shù)稱度；度為0的結(jié)點稱葉子(終端結(jié)點)；度不為0的結(jié)點稱分支結(jié)點(非終端結(jié)點)：除根外的分支結(jié)點稱內(nèi)部結(jié)點；有南對是子樹仃左，右之分的樹：無序樹是子樹沒有左，右之分的樹；森林是m個互不相交的樹的集合；樹的四種不同表示方法：-樹形表示法；-嵌套集合表示法；-凹入表示法-廣義表表示法。************************************************************************二叉樹的定義：是n20個結(jié)點的有限集，它是空集(n=0)或由一個根結(jié)點及兩棵互不相交的分別稱作這個根的左子樹和右子樹的二叉樹組成。二叉樹不是樹的特殊情形，與度數(shù)為2的有序樹不同。二叉樹的4個重要性質(zhì)：?.二叉樹上第i層上的結(jié)點數(shù)目最多為2人(i?l)(i21).；深度為k的二叉樹至多有(2”)-1個結(jié)點(k2l)；.在任意一棵二叉樹中，若終端結(jié)點的個數(shù)為nO,度為2的結(jié)點數(shù)為n2,則n0=n2+l；.具有n個結(jié)點的完全二叉樹的深度為int(log2n)+lo滿二叉樹是一棵深度為k,結(jié)點數(shù)為(2”)?1的二叉樹；完全二叉樹是滿二叉樹在最下層自右向左去處部分結(jié)點：二叉樹的順序存儲結(jié)構(gòu)就是把二叉樹的所有結(jié)點按照層次順序存儲到連續(xù)的存儲單元中。(存儲前先將其畫成完全二叉樹)樹的存儲結(jié)構(gòu)多用的是鏈式存儲。BinTNodc的結(jié)構(gòu)為lchild|data|rchild,把所有BinTNode類型的結(jié)點，加上一個指向根結(jié)點的BinTree型頭指針就構(gòu)成了二叉樹的鏈式存儲結(jié)構(gòu)，稱為二叉鏈表。它就是由根指針root唯一確定的。共有2n個指針域，n+1個空指針。************************************************************************根據(jù)訪問結(jié)點的次序不同可得三種遍歷：先序遍歷（前序遍歷或先根遍歷），中序遍歷（或中根遍歷）、后序遍歷（或后根遍歷）。時間復(fù)雜度為O（n）.利用二叉鏈表中的n+1個空指針域來存放指向某種遍歷次序下的前趨結(jié)點和后繼結(jié)點的指針，這些附加的指針就稱為“線索”，加上線索的二叉鏈表就稱為線索鏈表。線索使得查找中序前趨和中序后繼變得簡單有效，但對于查找指定結(jié)點的前序前趨和后序后繼并沒有什么作用************************************************************************樹和森林及二叉樹的轉(zhuǎn)換是唯一對應(yīng)的。轉(zhuǎn)換方法：?樹變二叉樹：兄弟相連，保留長子的連線。?二叉樹變樹：結(jié)點的右孩子與其雙親連。?森林變二叉樹：樹變二叉樹，各個樹的根相連。樹的存儲結(jié)構(gòu)：?有雙親鏈表表示法：結(jié)點data|parent,對于求指定結(jié)點的雙親或祖先十分方便，但不適于求指定結(jié)點的孩子及后代,孩/鏈表表示法：為樹中每個結(jié)點data|next設(shè)置個孩子鏈表firstchild,并將data|firstchild存放在一個向量中。雙親孩子鏈表表示法：將雙親鏈表和孩子鏈表結(jié)合。孩子兄弟鏈表表示法：結(jié)點結(jié)構(gòu)leftmostchild|data|rightsibing,附加兩個分別指向該結(jié)點的坡左孩子和右鄰兄弟的指針域。************************************************************************樹的前序遍歷與相對應(yīng)的二叉樹的前序遍歷一致：樹的后序遍歷與相對應(yīng)的二叉樹的中序遍歷一致。************************************************************************樹的帶權(quán)路徑長度是樹中所有葉結(jié)點的帶權(quán)路徑長度之和。樹的帶權(quán)路徑長度最小的二叉樹就稱為最優(yōu)二義樹（即哈夫曼樹）。在葉子的權(quán)值相同的二叉樹中，完全二叉樹的路徑長度最短。哈夫曼樹有n個葉結(jié)點，共有2n.i個結(jié)點，沒有度為1的結(jié)點，這類樹又稱為嚴格二叉樹。************************************************************************變長編碼技術(shù)可以使頻度高的字符編碼短，而頻度低的字符編碼長，但是變長編碼可能使解碼產(chǎn)生二義性。如00、01、0001這三個碼無法在解碼時確定是哪一個，所以要求在字符編碼時任-字符的編碼都不是其他字符編碼的前綴，這種碼稱為前綴碼（其實是非前綴碼）。哈夫曼樹的應(yīng)用最廣泛地是在編碼技術(shù)E,它能夠容易地求出給定字符集及其概率分布的最優(yōu)前綴碼。哈夫曼編碼的構(gòu)造很容易，只要同好了哈夫曼樹，按分支情況在左路徑上寫代碼0,右路徑上寫代碼1,然后從上到下到葉結(jié)點的相應(yīng)路徑上的代碼的序列就是該結(jié)點的最優(yōu)前綴碼。第七章圖************************************************************************圖的邏輯結(jié)構(gòu)特征就是其結(jié)點（頂點）的前趨和后繼的個數(shù)都是沒有限制的，即任意兩個結(jié)點之間之間都可能相關(guān)。圖GraphG=（V,E）,V是頂點的有窮非空集合，E是頂點偶對的有窮集。有向圖Digr叩h：每條邊有方向；無向圖Undigmph：每條邊沒有方向。有向完全圖：具有n*（n?l）條邊的有向圖；無向完全圖：具有n*（n?l）/2條邊的無向圖；有根圖：有一個頂點有路徑到達其它頂點的有向圖：簡單路徑：是經(jīng)過頂點不同的路徑；簡單回路是開始和終端重合的簡單路徑；網(wǎng)絡(luò)：是帶權(quán)的圖。************************************************************************圖的存儲結(jié)構(gòu)：?鄰接矩陣表示法：用一個n階方陣來表示圖的結(jié)構(gòu)是唯一的，適合稠密圖。?無向圖：鄰接矩陣是對稱的。有向圖：行是出度，列是入度。建立鄰接矩陣算法的時間是O(n+M2+e),其時間復(fù)雜度為0(22)鄰接表表示法：用頂點表和鄰接表構(gòu)成不是唯一的，適合稀疏圖。?頂點表結(jié)構(gòu)vertex|firstedge,指針域存放鄰接表頭指針。鄰接表：用頭指針確定。?無向圖稱邊表；有向圖又分出邊表和逆鄰接表：鄰接表結(jié)點結(jié)構(gòu)為adjvcx|next,時間復(fù)雜度為O(n+e).,空間復(fù)雜度為O(n+e).°圖的遍歷：?深度優(yōu)先遍歷：借助于鄰接矩陣的列。使用棧保存已訪問結(jié)點。廣度優(yōu)先遍歷：借助于鄰接矩陣的行。使用隊列保存已訪問結(jié)點。生成樹的定義：若從圖的某個頂點出發(fā)，可以系統(tǒng)地訪問到圖中所有頂點，則遍歷時經(jīng)過的邊和圖的所有頂點所構(gòu)成的子圖稱作該圖的生成樹。坡小生成樹：圖的生成樹不唯一，從不同的頂點出發(fā)可得到不同的生成樹，把權(quán)值最小的生成樹稱為最小生成樹(MST)。構(gòu)造最小生成樹的算法：-Prim算法的時間復(fù)雜度為0(22)與邊數(shù)無關(guān)適于稠密圖。Kruskal算法的時間復(fù)雜度為O(lge),主要取決于邊數(shù)，較適合于稀疏圖。************************************************************************垃短路徑的算法：-Dijkstra算法，時間復(fù)雜度為0(22).?類似于prim算法。拓撲排序：是將有向無環(huán)圖G中所有頂點排成一個線性序列，若vu,v>￡E(G),則在線性序列u在v之前，這種線性序列稱為拓撲序列。拓撲排序也有兩種方法：?無前趨的頂點優(yōu)先，每次輸出一個無前趨的結(jié)點并刪去此結(jié)點及其出邊，最后得到的序列即拓撲序列。?無后繼的結(jié)點優(yōu)先：每次輸出一個無后繼的結(jié)點并刪去此結(jié)點及其入邊，最后得到的序列是逆拓撲序列。第八章排序************************************************************************記錄中可用某一項來標識一個記錄，則稱為關(guān)鍵字項，該數(shù)據(jù)項的值稱為關(guān)鍵字。排序是使文件中的記錄按關(guān)鍵字遞增(或遞減)次序排列起來。?基本操作：比較關(guān)鍵字大小；改變指向記錄的指針或移動記錄.?存儲結(jié)構(gòu)：順序結(jié)構(gòu)、鏈表結(jié)構(gòu)、索引結(jié)構(gòu)。經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對次序保持不變，則稱這種排序方法是穩(wěn)定的，否則排序算法是不穩(wěn)定的。排序過程中不涉及數(shù)據(jù)的內(nèi)、外存交換則稱之為"內(nèi)部排序"(內(nèi)排序)，反之，若存在數(shù)據(jù)的內(nèi)外存交換，則稱之為外排序。內(nèi)部排序方法可分五類：插入排序、選擇排序、交換排序、歸并排序和分配排序。評價排序算法好壞的標準主要有兩條：執(zhí)行時間和所需的輔助空間，另外算法的復(fù)雜程序也是要考慮的一個因素。插入排序：?直接插入排序：?逐個向前插入到合適位置。?哨兵(監(jiān)視哨)有兩個作用：?作為臨變量存放R[i]?是在查找循環(huán)中用來監(jiān)視下標變量j是否越界。?直接插入排序是就地的穩(wěn)定排序。時間復(fù)雜度為0(22),比較次數(shù)為(n+2)(n-l)/2：移動次數(shù)為(n+4)(n-l”：?希爾排序：?等間隔的數(shù)據(jù)比較并按要求順序排列，最后間隔為1。?希爾排序是就地的不穩(wěn)定排序。時間復(fù)雜度為0(21.25),比較次數(shù)為(21.25)：移動次數(shù)為(1.621.25)；交換排序：?冒泡排序：?自下向上確定最輕的一個。?自上向下確定最重的一個。?自下向上確定最輕的一個，后自上向下確定最重的?冒泡排序是就地的穩(wěn)定排序。時間復(fù)雜度為0(22),比較次數(shù)為n(n-l)/2；移動次數(shù)為3n(n-l)/2；?快速排序：?以第一個元素為參考基準，設(shè)定、動兩個指針，發(fā)生交換后指針交換位置，直到指針重合。重復(fù)直到排序完成。?快速排序是非就地的不穩(wěn)定排序。時間復(fù)雜度為O(nk>g2n),比較次數(shù)為n(n-l)/2；選擇排序：?直接選擇排序：?選擇最小的放在比較區(qū)前。?直接選擇排序就地的不穩(wěn)定排序。時間復(fù)雜度為0(22)。比較次數(shù)為n(n-l)/2：?堆排序?建堆：按層次將數(shù)據(jù)填入完全二叉樹，從int(n/2)處向前逐個調(diào)整位置。?然后將樹根與最后一個葉子交換值并斷開與樹的連接并重建堆，直到全斷開。堆排序是就地不穩(wěn)定的排序，時間復(fù)雜度為O(nlog2n),不適宜于記錄數(shù)較少的文件。。歸并排序：?先兩個一組排序，形成(n+l)/2組，再將兩組并一組，直到剩下一組為止。歸并排序是非就地穩(wěn)定排序，時間復(fù)雜度是O(nlog2n),分配排序：-箱排序：-按關(guān)鍵字的取值范圍確定箱子數(shù)，按關(guān)鍵字投入箱子，鏈接所有非空箱。?箱排序的平均時間復(fù)雜度是線性的O(n).?基數(shù)排序：-從低位到高位依次對關(guān)鍵字進行箱排序。基數(shù)排序是非就穩(wěn)定的排序，時間復(fù)雜度是O(d*n+d*rd)。各種排序方法的比較和選擇：?.待排序的記錄數(shù)目n；n較大的要用時間復(fù)雜度為O(nlog2n)的第九章查找查找的同時對表做修改操作(如插入或刪除)則相應(yīng)的表稱之為動態(tài)查找表，否則稱之為靜態(tài)查找表。衡量查找算法效率優(yōu)劣的標準是在查找過程中對關(guān)鍵字需要執(zhí)行的平均比較次數(shù)(即平均查找長度ASL).************************************************************************線性表杳找的方法：?順序杳找：逐個查找，ASL=(n+l)/2;二分查找：取中點int(n/2)比較，若小就比左區(qū)間，大就比右區(qū)間。用二叉判定樹表示。ASL=(E(每層結(jié)點數(shù)*層數(shù)))/No分塊杏找。要求“分塊有序”，將表分成若干塊內(nèi)部不一定有序，并抽取各塊中的最大關(guān)鍵字及其位置建立有序索引表。************************************************************************二叉排序樹(BST)定義是：二叉排序樹是空樹或者滿足如下性質(zhì)的二叉樹：-若它的左子樹非空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；若它的右子樹非空，則右子樹卜.所有結(jié)點的值均大于根結(jié)點的值；左、右子樹本身又是棵二叉排序樹。二叉排序樹的插入、建立、刪除的算法平均時間性能是O(nlog2n)。二叉排序樹的刪除操作可分三種情況進行處理：?*P是葉子，則直接刪除*P，即將*P的雙親*parent中指向*P的指針域置空即可。*P只有一個孩子*child,此時只需將*child和*p的雙親直接連接就可刪去*p.*p有兩個孩子，則先將*p結(jié)點的中序后繼結(jié)點的數(shù)據(jù)到*p,刪除中序后繼結(jié)點。************************************************************************關(guān)于B-樹(多路平衡杳找樹)。它適合在磁盤等直接存取設(shè)備上組織動態(tài)的杳找表，是?種外杳找算法。建立的方式是從下向上拱起。************************************************************************散列技術(shù)：將結(jié)點按其關(guān)鍵字的散列地址存儲到散列表的過程稱為散列。散列函數(shù)的選擇有兩條標準：簡單和均勻。常見的散列函數(shù)構(gòu)的造方法：?.平方取中法：hash=int((xA2)%100).除余法：表長為m,hash=x%m.相乘取整法：hash=int(m*(x*A-int(x+A))；A=0.618.隨機數(shù)法：hash=random(x)o處理沖突的方法：?開放定址法：??般形式為hi=(h(key)+di)%mlWiWm-1,開放定址法要求散列表的裝填因子aW1。開放定址法類型：-線性探查法：address=(hash(x)+i)%m；,二次探杳法：addrcss=(hash(x)+iA2)%m；,雙重散列法：addrcss=(hash(x)+i*hash(y))%m：?拉鏈法：-是將所有關(guān)鍵字為同義詞的結(jié)點鏈接在同一個單鏈表中。拉鏈法的優(yōu)點：?拉鏈法處理沖突簡單，且無堆積現(xiàn)象；鏈表上的結(jié)點空間是動態(tài)申請的適于無法確定表長的情況；拉鏈法中a可以大于1,結(jié)點較大時其指針域可忽略，因此節(jié)省空間：拉鏈法構(gòu)造的散列表刪除結(jié)點易實現(xiàn)。拉鏈法也有缺點：當結(jié)點規(guī)模較小時，用拉鏈法中的指針域也要占用額外空間，還是開放定址法省空間。第十章文件文件是性質(zhì)相同的記錄的集合。記錄是文件中存取的基本單位，數(shù)據(jù)項是文件可使用的最小單位，數(shù)據(jù)項有時稱字段或者屬性。文件-邏輯結(jié)構(gòu)是一種線性結(jié)構(gòu)。操作有：檢索和維護。并有實時和批量處理兩種處理方式。文件?存儲結(jié)構(gòu)是指文件在外存上的組織方式。基本的組織方式有：順序組織、索引組織、散列組織和鏈組織。常用的文件組織方式：順序文件、索引文件、散列文件和多關(guān)鍵字文件。評價?個文件組織的效率，是執(zhí)行文件操作所花費的時間和文件組織所需的存儲空間。檢索功能的多寡和速度的快慢，是衡量文件操作質(zhì)量的重要標志。************************************************************************順序文件是指按記錄進入文件的先后順序存放、其邏輯順序和物理順序一致的文件。主關(guān)鍵字有序稱順序有序文件，否則稱順序無序文件。一切存儲在順序存儲器（如磁帶）上的文件都只能順序文件，只能按順序查找法存取。順序文件的插入、刪除和修改只能通過復(fù)制整個文件實現(xiàn)。************************************************************************索引文件的組織方式：通常是在主文件之外建立?張索引表指明邏輯記錄和物理記錄之間--對應(yīng)的關(guān)系，它和主文件一起構(gòu)成索引文件。索引非順序文件中的索引表為稠密索引。索引順序文件中的索引表為稀疏索引。若記錄很大使得索引表也很大時，可對索引表再建立索引，稱為杏找表。是?種靜態(tài)索引。索引順序文件常用的有兩種：-ISAM索引順序存取方法：是專為磁盤存取文件設(shè)計的，采用靜態(tài)索引結(jié)構(gòu)。?VSAM虛擬存儲存取方法：采用B+樹作為動態(tài)索引結(jié)構(gòu)，由索引集、順序集、數(shù)據(jù)集組成。************************************************************************散列文件是利用散列存儲方式組織的文件，亦稱為直接存取文件。散列文件?優(yōu)點是：文件隨機存放，記錄不需要排序：插入刪除方便；存取速度快：不需要索引區(qū)，節(jié)省存儲空間。?缺點是：不能進行順序存取，只能按關(guān)鍵字隨機存取，且詢問方式限地簡單詢問，需要重新組織文件。多重表文件：對需要查詢的次關(guān)鍵字建立相應(yīng)的索引，對相同次關(guān)鍵字的記錄建一個鏈表并將鏈表頭指針、長度、次關(guān)鍵字作為索引表的索引項。倒排表：次關(guān)鍵字索引表稱倒排表，主文件和倒排表構(gòu)成倒排文件。計算機組成原理第1章概論一、名詞解釋：歷年真題：名詞解釋題：（2002年）1.主機：由CPU、存儲器與I/O接口合在一起構(gòu)成的處理系統(tǒng)稱為主機。（2003年）16.主機：由CPU、存儲器與I/O接口合在--起構(gòu)成的處理系統(tǒng)稱為主機。（2004年）18.ALU算術(shù)邏輯運算單元，負責執(zhí)行各種算術(shù)運算和邏輯運算。（2005年）21.應(yīng)用軟件：完成應(yīng)用功能的軟件，專門為解決某個應(yīng)用領(lǐng)域中的具體任務(wù)而編寫。近4年都考「名稱解釋，所以第?章的名稱解釋是考試的重點，這里給大家列出了名詞解釋大家要熟悉下，這都是本章的基本概念，也有利于做選擇題及填空題。.主機：由CPU、存儲器與I/O接口合在一起構(gòu)成的處理系統(tǒng)稱為主機。.CPU：中央處理器，是計算機的核心部件，由運算器和控制器構(gòu)成。.運算器：計算機中完成運算功能的部件，由ALU和寄存器構(gòu)成。.ALU：算術(shù)邏輯運算單元，負責執(zhí)行各種算術(shù)運算和邏輯運算。.外圍設(shè)備：計算機的輸入輸出設(shè)備，包括輸入設(shè)備，輸出設(shè)備和外存儲設(shè)備。.數(shù)據(jù)：編碼形式的各種信息，在計算機中作為程序的操作對象。.指令：是一種經(jīng)過編碼的操作命令，它指定需要進行的操作，支配計算機中的信息傳遞以及主機與輸入輸出設(shè)備之間的信息傳遞，是構(gòu)成計算機軟件的基本元素。.透明：在計算機中，從某個角度看不到的特性稱該特性是透明的。.位：計算機中的一個二進制數(shù)據(jù)代碼，計算機中數(shù)據(jù)的最小表示單位。.字：數(shù)據(jù)運算和存儲的單位，其位數(shù)取決于具體的計算機。.字節(jié)：衡量數(shù)據(jù)量以及存儲容量的基本單位。1字節(jié)等于8位二進制信息。.字長：一個數(shù)據(jù)字中包含的位數(shù)，反應(yīng)了計算機并行計算的能力。一般為8位、16位、32位或64位。.地址：給主存器中不同的存儲位置指定的一個二進制編號。.存儲器：計算機中存儲程序和數(shù)據(jù)的部件，分為內(nèi)存和外存。.總線：計算機中連接功能單元的公共線路，是一束信號線的集合，包括數(shù)據(jù)總線.地址總線和控制總線。.硬件：由物理元器件構(gòu)成的系統(tǒng)，計算機硬件是一個能夠執(zhí)行指令的設(shè)備。.軟件：由程序構(gòu)成的系統(tǒng)，分為系統(tǒng)軟件和應(yīng)用軟件。.兼容：計算機部件的通用性。.軟件兼容：一個計算機系統(tǒng)上的軟件能在另一個計算機系統(tǒng)上運行，并得到相同的結(jié)果，則稱這兩個計算機系統(tǒng)是軟件兼容的。.程序：完成某種功能的指令序列。.寄存器：是運算器中若干個臨時存放數(shù)據(jù)的部件，由觸發(fā)器構(gòu)成，用于存儲最頻繁使用的數(shù)據(jù)。.容量：是衡量容納信息能力的指標。.主存：一般采用半導(dǎo)體存儲器件實現(xiàn)，速度較高.成本高且當電源斷開時存儲器的內(nèi)容會丟失。.輔存：一般通過輸入輸出部件連接到主存儲器的外圍設(shè)備，成本低，存儲時間長。.操作系統(tǒng)：主要的系統(tǒng)軟件，控制其它程序的運行，管理系統(tǒng)資源并且為用戶提供操作界面。.匯編程序：將匯編語言程序翻譯成機器語言程序的計算機軟件。.匯編語言：采用文字方式（助記符）表示的程序設(shè)計語言，其中大部分指令和機器語言中的指令一一對應(yīng)，但不能被計算機的硬件直接識別。.編譯程序：將高級語言程序轉(zhuǎn)換成機器語言程序的計算機軟件。.解釋程序：解釋執(zhí)行高級語言程序的計算機軟件，解釋并立即執(zhí)行源程序的語句。.系統(tǒng)軟件：計算機系統(tǒng)的?部分，進行命令解釋、操作管理、系統(tǒng)維護、網(wǎng)絡(luò)通信、軟件開發(fā)和輸入輸出管理的軟件，與具體的應(yīng)用領(lǐng)域無關(guān)。.應(yīng)用軟件：完成應(yīng)用功能的軟件，專門為解決某個應(yīng)用領(lǐng)域中的具體任務(wù)而編寫。.指令流：在計算機的存儲器與CPU之間形成的不斷傳遞的指令序列。從存儲器流向控制器。.數(shù)據(jù)流：在計算機的存儲器與CPU之間形成的不斷傳遞的數(shù)據(jù)序列。存在于運算器與存儲器以及輸入輸出設(shè)備之間。.接口：計算機主機與外圍設(shè)備之間傳遞數(shù)據(jù)與控制信息的電路。計算機可以與多種不同的外圍設(shè)備連接，因而需要有多種不同的輸入輸出接口。選擇題沒仃考過二、填空題：（2000年）系統(tǒng)軟件主要包括：和及診斷程序等°操作系統(tǒng)語言處理程序（2005年）18.構(gòu)成中央處理器的兩大部件是和。運算器控制器三、改錯題：（2000年）I.運算器的功能就是執(zhí)行加、減、乘、除四則運算。運算器的功能就是算術(shù)運算和邏輯運算（2005年）18.構(gòu)成中央處理器的兩大部件是和o硬盤的存儲容量常用GB表示，1GB=1O24MB三、數(shù)據(jù)編碼：定點數(shù)編碼：（2000年）2.如果X為負數(shù),由［X］補求［-X］補是將（）o［X］補各值保持不變［X］補符號位變反，其它各位不變［X］補除符號位外，各位變反，未位加1［X］補連同符號位一起各位變反，未位加1【分析】：不論X是正數(shù)還是負數(shù)，由［X］補求［.X］補的方法是對［X］補求補，即連同符號位?起按位取反，末位加1。【答案】：D（2001年）2.若x補=0.1101010,則x原=（）。A.1.0010101B.1.0010110C.0.0010110D.0.1101010【分析】：正數(shù)的補碼與原碼相同，負數(shù)的補碼是用正數(shù)的補碼按位取反，末位加1求得。此題中X補為正數(shù)，則X原與X補相同。【答案】：D（2002年）2.若x=1011,則［x］補=（）oA.01011B.1011 C.0101 D.10101【分析】：x為正數(shù)，符號位為0,數(shù)值位與原碼相同，結(jié)果為01011。【答案】：A（2003年）8.若［X］補=10011,則真值X是（）?A.-0.1011B.-0.0101C.0.1011D.0.0101【分析】：［X］補=1.1011,其符號位為1,真值為負；真值絕對值可由其補碼經(jīng)求補運算得到，即按位取后得。0100再末位加1得0.0101,故其真值為-0.0101。【答案】：B（2004年）13.設(shè)有二進制數(shù)x=-1101110,若采用8位二進制數(shù)表示，則［X］補（）。A.11101101B.10010011C.00010011D.10010010【分析】：x=-noiiio為負數(shù),負數(shù)的補碼是將二進制位按位取反后在最低位上加I,故M補=iooiooi0o【答案】：D（2005年）1.若［X］補=0.1011,則真值X=（）oA.0.1011B.0.0101 C.1.1011D.1.0101【分析】：［X］補=0.101L其符號位為0,真值為正；真值就是0.1011。［答案］:a由上可見，有關(guān)補碼每年都考。同學(xué)也要注意一下移碼。（2001）3.若定點整數(shù)64位，含1位符號位，補碼表示，則所能表示的絕對值最大負數(shù)為（）oA.-264B.-（264-1）C.-263D.-（263-1）【分析】：字長為64位,符號位為1位，則數(shù)值位為63位。當表示負數(shù)時，數(shù)值位全0為負絕對值最大，為?263。【答案】：C（2002年）3.某機字長8位，含一位數(shù)符，采用原碼表示，則定點小數(shù)所能表示的非零鼓小正數(shù)為（）A.2-9B.2-8 C.1- D.2-7【分析】：求最小的非零正數(shù)，符號位為0,數(shù)值位取非。中的原碼最小值，此8位數(shù)據(jù)編碼為：00000001,表示的值是：2?7。【答案】：D第3章存儲系統(tǒng)一、名詞解釋：歷年真題：（2001年）2.DRAM：動態(tài)隨機訪問存儲器，利用電容電荷存儲信息。（2001年）6.邏輯地址：程序員編程所用的地址以及CPU通過指令訪問主存時所產(chǎn)生的地址。（2001年）10.隨機存取方式：可按地址訪問存儲器任編址單元，其訪問時間相同且與地址無關(guān)。六年以來就考了這3個名稱解釋，而且近4年都沒有考，所以第三章的名稱解釋不是考試的重點，這里給大家列出了名詞解釋大家要熟悉一下，這都是本章的基本概念，有利于做選擇題及填空題。.RAM：隨機訪問存儲器，能夠快速方便的訪問地址中的內(nèi)容，訪問的速度與存儲位置無關(guān)。.ROM：只讀存儲器，一種只能讀取數(shù)據(jù)不能寫入數(shù)據(jù)的存儲器。.SRAM：靜態(tài)隨機訪問存儲器，采用雙穩(wěn)態(tài)電路存儲信息。.DRAM：動態(tài)隨機訪問存儲器，利用電容電荷存儲信息。.EDODRAM：增強數(shù)據(jù)輸出動態(tài)隨機訪問存儲，采用快速頁面訪問模式并增加了一個數(shù)據(jù)鎖存器以提高數(shù)據(jù)傳輸速率。.PROM：可編程的ROM,可以被用戶編程次。.EPROM：可擦寫可編程的ROM,可以被用戶編程多次。靠紫外線激發(fā)浮置柵上的電荷以達到擦除的目的。.EEPROM：電可擦寫可編程的ROM,能夠用電子的方法擦除其中的內(nèi)容。.SDRAM：同步型動態(tài)隨機訪問存儲器，在系統(tǒng)時鐘控制下進行數(shù)據(jù)的讀寫。.快閃存儲器：一種非揮發(fā)性存儲器，與EEPROM類似，能夠用電子的方法擦除其中的內(nèi)容。.相聯(lián)存儲器：一種按內(nèi)容訪問的存儲器，每個存儲單元有匹配電路，可用于是cache中查找數(shù)據(jù)。.多體交叉存儲器：由多個相互獨立、容量相同的存儲體構(gòu)成的存儲器，每個存儲體獨立工作，讀寫操作重疊進行。.訪存局部性：CPU的一種存取特性，對存儲空間的90%的訪問局限于存儲空間的10%的區(qū)域中，而另外10%的訪問則分布在90%的區(qū)域中。.直接映象：cache的一種地址映象方式，一個主存塊只能映象到cache中的唯一一個指定塊。.全相聯(lián)映象：cache的一種地址映象方式，一個主存塊可映象到任何cache塊。.組相聯(lián)映象：cache的一種地址映象方式，將存儲空間分成若干組，各組之間用直接映象，組內(nèi)各塊之間用全相聯(lián)映象。.全寫法（寫直達法）：cache命中時的一種更新策略，寫操作時將數(shù)據(jù)既寫入cache又寫入主存，但塊變更時不需要將調(diào)出的塊寫回主存。.寫回法：cache命中時的一種更新策略，寫cache時不寫主存，而當cache數(shù)據(jù)被替換出去時才寫回主存。.按寫分配：cache不命中時的一種更新策略，寫操作時把對應(yīng)的數(shù)據(jù)塊從主存調(diào)入cache。.不按寫分配：cache不命中時的一種更新策略，寫操作時該地址的數(shù)據(jù)塊不從主存調(diào)入cache。一般寫回法采用按寫分配法，寫直達法則采用不按寫分配法。.虛擬存儲器：為了擴大容量，把輔存當作主存使用，所需要的程序和數(shù)據(jù)由輔助的軟件和硬件自動地調(diào)入主存，對用戶來說，好像機器有一個容量很大的內(nèi)存，這個擴大了的存儲空間稱為虛擬存儲器.層次化存儲體系：把各種不同存儲容量、不同訪問速度、不同成本的存儲器件按層次構(gòu)成多層的存儲器，并通過軟硬件的管理將其組成統(tǒng)?的整體，使所存儲的程序和數(shù)據(jù)按層次分布在各種存儲器件中。.訪問時間：從啟動訪問存儲器操作到操作完成的時間。.訪問周期時間：從一次訪問存儲的操作到操作完成后可啟動下一次操作的時間。.帶寬：存儲器在連續(xù)訪問時的數(shù)據(jù)吞吐率。.段式管理：一種虛擬存儲器的管理方式，把虛擬存儲空間分成段，段的長度可以任意設(shè)定，并可以放大或縮小。.頁式管理：一種虛擬存儲器的管理方式，把虛擬存儲空間和實際存儲空間等分成固定容量的頁，需要時裝入內(nèi)存，各頁可裝入主存中不同的實際頁面位置。.段頁式管理：一種虛擬存儲器的管理方式，將存儲空間邏輯模塊分成段，每段又分成若干頁。.固件：固化在硬件中的固定不變的常用軟件。.邏輯地址：程序員編程所用的地址以及CPU通過指令訪問主存時所產(chǎn)生的地址。.物理地址：實際的主存儲器的地址稱為“真實地址”。二、選擇填空題：歷年真題評析：2000年：5.動態(tài)半導(dǎo)體存儲器的特點是（）。A.在工作中存儲器內(nèi)容會產(chǎn)生變化B.每次讀出后，需要根據(jù)原存內(nèi)容重新寫入一遍C.每隔一定時間，需要根據(jù)原存內(nèi)容重新寫入一遍D.在工作中需要動態(tài)地改變訪存地址【分析】：動態(tài)半導(dǎo)體存儲器是利用電容存儲電荷的特性記錄信息，由于電容會放電，必須在電荷流失前對電容充電，即刷新。方法是每隔?定時間，根據(jù)原存內(nèi)容重新寫入?遍。【答案】：C.地址線A15?A0（低），若選取用16Kxi存儲芯片構(gòu)成64KB存儲器則應(yīng)由地址碼 譯碼產(chǎn)生片選信號。【分析】：用16Kxi芯片構(gòu)成64KB的存儲器，需要的芯片數(shù)量為：（64KX8）/（16KX1）=32,每8片一組分成4組，每組按位擴展方式組成一個16Kx8位的模塊，4個模塊按字擴展方式構(gòu)成64KB的存儲器。存儲器的容量為64K=216,需要16位地址,選用A15-A0為地址線：每個模塊的容量為16K=214需要14位地址,選用A13-A0為每個模塊提供地址：A15、A14通過24譯碼器對4個模塊進行片選。【答案】：AI5,A14.有靜態(tài)RAM與動態(tài)RAM可供選擇，在構(gòu)成大容量主存時，?般就選擇（ ）。【分析】：靜態(tài)RAM特點是存取速度快，單位價格（每字節(jié)存儲空間的價格）較高；動態(tài)RAM則是存取速度稍慢，單位價格較低。所以考慮價格因素，在構(gòu)成大容量的存儲器時?般選擇動態(tài)存儲器。【答案】：動態(tài)RAM2001年：11.高速緩沖存儲器Cache一般采取（）oA.隨機存取方式B.順序存取方式C.半順序存取方式D.只讀不寫方式【分析】：Cache是為提高存儲器帶寬而在主存儲器和CPU之間增加的存儲器，目的是用來存儲使用頻繁的數(shù)據(jù)和指令，存取方式應(yīng)與主存儲器相同，均為隨機存取方式。【答案】：A.若存儲周期250ns,每次讀出16位，則該存儲器的數(shù)據(jù)傳送率為（

B.4M字節(jié)/秒D.8M字節(jié)/秒A.4X106B.4M字節(jié)/秒D.8M字節(jié)/秒C.8X106字節(jié)/秒【分析】：存儲周期250ns,換算為250X10-9秒；每個存儲周期可讀出16位，為兩個字節(jié)，則數(shù)據(jù)傳送率為:2字節(jié)/（250X10-9）秒，即8X106字節(jié)/秒。【答案】：C.半導(dǎo)體靜態(tài)存儲器SRAM的存儲原理是（）＜.A.依靠雙穩(wěn)態(tài)電路 B.依靠定時刷新C.依靠讀后再生 D.信息不再變化【分析】:半導(dǎo)體靜態(tài)存儲器SRAM是由雙穩(wěn)態(tài)電路構(gòu)成，并依靠其穩(wěn)態(tài)特性來保存信息;動態(tài)存儲器DRAM是利用電容器存儲電荷的特性存儲數(shù)據(jù)，依靠定時刷新和讀后再生對信息進行保存，而ROM中的信息一經(jīng)寫入就不再變化。【答案】：A2002年：.一般來講，直接映象常用在（）oA.小容量高速Cache B.大容量高速CacheC.小容量低速Cache D.大容量低速Cache【分析】：直接映象的地址轉(zhuǎn)換速度快，但塊的沖突概率較高。在大容量高速Cache系統(tǒng)中使用直接映象方式，即可以發(fā)揮Cache的高速度，又可以減少塊的沖突概率。【答案】：B.下列存儲器中，（）速度最快。A.硬盤 B.光盤 C.磁帶 D.半導(dǎo)體存儲器【分析由于存儲器原理和結(jié)構(gòu)的不同，各種存儲器的訪問速度各不相同。以上存儲器中訪問速度由快到慢的順序為：半導(dǎo)體存儲器、硬盤、光盤、磁帶。【答案】：D2003年：15.在下列Cache替換算法中，一般說來哪一種比較好（）。A.隨機法 B.先進先出法C.后進先出法 D.近期最少使用法【分析】：在Cache替換算法中，隨機法是隨機地確定替換的存儲單元，先進先出法是替換最早調(diào)入的存儲單元，它們都沒有根據(jù)程序訪存局部性原理，命中率較低；近期最少使用法比較正確地利用了程序訪存局部性原理，替換出近期用得最少的存儲塊，命中率較高，是一種比較好的替換算法。而后進先出法不是Cache所使用的替換算法，此法在堆棧存儲結(jié)構(gòu)中使用。【答案】：D2004年：8.表示主存容量的常用單位為（）。A.數(shù)據(jù)塊數(shù) B.字節(jié)數(shù) C.扇區(qū)數(shù) D.記錄項數(shù)【分析】：表示主存容量的常用單位字節(jié)B,是基本單位。此外還有KB、MB、GB、TB。【答案】：B11.存儲器的隨機訪問方式是指（）oA.可隨意訪問存儲器B.按隨機文件訪問存儲器C.可對存儲器進行讀出與寫入D.可按地址訪問存儲器任一編址單元，其訪問時間相同且與地址無關(guān)【分析】：存儲器的隨機訪問方式是指可按地址訪問存儲器任編址單元，其訪問時間相同且與地址無關(guān)。【答案】：D2005年：.動態(tài)存儲器的特點是（）。A.工作中存儲內(nèi)容會產(chǎn)生變化B.工作中需要動態(tài)改變訪存地址C.工作中需要動態(tài)地改變供電電壓D.需要定期刷新每個存儲單元中存儲的信息【分析】：此題與2000年考題基本相同。動態(tài)半導(dǎo)體存儲器是利用電容存儲電荷的特性記錄信息，由于電容會放電，必須在電荷流失前對電容充電，即刷新。方法是每隔一定時間，根據(jù)原存內(nèi)容重新寫入一遍。【答案】：D.組相聯(lián)映象和全相聯(lián)映象通常適合于（）oA.小容量Cache B.大容量CacheC.小容量ROM D.大容量ROM【分析工直接映象的地址轉(zhuǎn)換速度快，但塊的沖突概率較高。在大容量高速Cache系統(tǒng)中使用直接映象方式，即可以發(fā)揮Cache的高速度，又可以減少塊的沖突概率。組相聯(lián)映象和全相聯(lián)映象速度較低，通常適合于小容量Cacheo【答案】：A第4章指令系統(tǒng)一、名詞解釋：歷年真題：2001年.堆棧：數(shù)據(jù)的寫入寫出不需要地址，按先進后出的順序讀取數(shù)據(jù)的存儲區(qū)。.立即尋址方式：操作數(shù)直接在指令中給出。六年以來就考了這2個名稱解釋，而且近4年都沒有考，所以第四章的名稱解釋不是考試的重點，這里給大家列出了名詞解釋大家要熟悉一下，這都是本章的基本概念，有利于做選擇題、改錯題和填空題。.指令系統(tǒng)：計算機中各種指令的集合，它反映了計算機硬件具備的基本功能。.計算機指令：計算機硬件能識別并能直接執(zhí)行操作的命令，描述一個基本操作。.指令編碼：將指令分成操作碼和操作數(shù)地址碼的幾個字段來編碼。.指令格式：指定指令字段的個數(shù)，字段編碼的位數(shù)和編碼的方式。.立即數(shù)：在指令中直接給出的操作數(shù)。.指令字長度：一個指令字所占有的位數(shù)。.助記符：用容易記憶的符號來表示指令中的操作碼和操作數(shù)。.匯編語言：采用文字方式(助記符)表示的程序設(shè)計語言，其中大部分指令和機器語言中的指令一一對應(yīng)，但是不能被計算機的硬件直接識別。.偽指令：匯編語言程序所提供的裝入內(nèi)存中的位置信息，表示程序段和數(shù)據(jù)段開始信息及結(jié)束信息等。且不轉(zhuǎn)換成2進制機器指令。.大數(shù)端：當一個數(shù)據(jù)元素的位數(shù)超過一個字節(jié)或者一個字的寬度，需存儲在相鄰的多個字節(jié)的存儲位置時，將數(shù)據(jù)的最低字節(jié)存儲在最大地址位置的存儲方式。.小數(shù)端：當一個數(shù)據(jù)元素的位數(shù)超過一個字節(jié)或者一個字的寬度，需存儲在相鄰的多個字節(jié)的存儲位置時，將數(shù)據(jù)的最低字節(jié)存儲在最小地址位置的存儲方式。.操作數(shù)尋址方式：指令中地址碼的內(nèi)容及編碼方式。.系統(tǒng)指令：改變計算機系統(tǒng)的工作狀態(tài)的指令。.特權(quán)指令：改變執(zhí)行特權(quán)的指令，用于操作系統(tǒng)對系統(tǒng)資源的控制。.自陷指令：特殊的處理程序，又叫中斷指令。.尋址方式：對指令的地址碼進行編碼，以得到操作數(shù)在存儲器中的地址的方式。.相對轉(zhuǎn)移：轉(zhuǎn)移到的目標指令的地址與當前指令的地址有關(guān)，是用當前指令的PC與一個偏移量相加，和為目標指令的PC。.絕對轉(zhuǎn)移：轉(zhuǎn)移到的口標指令的地址與當前指令的地址無關(guān)，指令中給定的目標地址即為目標指令的PC。.無條件轉(zhuǎn)移：一種轉(zhuǎn)移指令類型，不管狀態(tài)如何，一律進行轉(zhuǎn)移操作。.條件轉(zhuǎn)移：一種轉(zhuǎn)移指令類型，根據(jù)計算機中的狀態(tài)決定是否轉(zhuǎn)移。.RISC：精簡指令系統(tǒng)計算機，即指令系統(tǒng)中的指令數(shù)量少，且指令功能相對簡單。.CISC：復(fù)雜指令系統(tǒng)計算機，即指令系統(tǒng)中的指令數(shù)量多，且指令功能相對較強。.堆棧：數(shù)據(jù)的寫入寫出不需要地址，按先進后出的順序讀取數(shù)據(jù)的存儲區(qū)。二、選擇填空題：歷年真題2000年：3.在堆棧尋址中，設(shè)A為累加器，SP為堆棧指示器，Msp為SP指示的棧頂單元。如果進棧操作順序是：(SP)?1一SP,(A)fMsp：那么出棧操作的順序應(yīng)是()o(Msp)-A,(SP)+1-*SP(SP)+1-SP,(Msp)f(SP)-1-*SP,(Msp)-A(Msp)-A,(SP)-1-*SP【分析】：堆棧是按特定順序進行訪問的存儲區(qū)，其訪問方式是后進先出，即先存入的數(shù)據(jù)后讀出。對堆棧的操作有入棧和出棧兩種，兩者的操作完全相反，包括功能和順序均相反。【答案】：A6.在按字節(jié)編址的存儲器中，每個編址單元中存放（）oA.1位 B.8位 C.16位 D.32位【分析】：在按字節(jié)編址在存儲器中，每個編址單元的容量為一個字節(jié)，一個字節(jié)由8位二進制數(shù)組成，個字節(jié)存儲單元可以存放8位二進制位。【答案】：B.在CPU的狀態(tài)寄存器中，常設(shè)置以下狀態(tài)位：零標志位（Z）,負標志位（N）,（ ）和（ ）。【分析】：在CPU中專門設(shè)置有一個存儲計算機狀態(tài)的寄存器，稱為狀態(tài)寄存器SR,其中通常包括如卜,標志位：零標志位（Z）、負標志位（N）、溢出標志位（V）、進位或借位標志位（C）等。【答案】：溢出標志位（V）、進位或借位標志位（C）.如指令中給出形式地址為D,則間接尋址方式獲得操作數(shù)的有效地址為 。【分析】：在存儲器間接尋址方式中，操作數(shù)的地址在主存儲器中，其存儲器地址在指令中給出。也就是說在指令中給出的既不是操作數(shù)，也不是操作數(shù)的地址，而是操作數(shù)地址的地址，則有效地址為以形式地址D為地址的存儲單元的內(nèi)容。【答案】：以D為地址的存儲單元的內(nèi)容13.如果說變址尋址方式主要是面向用戶的，那么基址尋址一般是面向（ ）的。【分析】：變址尋址方式是面向用戶的，常用于訪問字符小、向量數(shù)據(jù)結(jié)構(gòu)和循環(huán)程序設(shè)計；而基址尋址方式是面向系統(tǒng)的，對由邏輯地址空間到物理地址空間的變換提供支持，用以解決程序在存儲器中再定位和擴大尋址空間等問題。【答案】：系統(tǒng)2001年：.為了縮短指令中某個地址段的位數(shù)，有效的方法是采取（）oA.立即尋址 B.變址尋址C.間接尋址 D.寄存器尋址【分析】：由于計算機中寄存器的數(shù)量一般很少，采用寄存器尋址時可用少量的代碼來指定寄存器，這樣可以減少對應(yīng)地址段的代碼位數(shù)，也可減少整個指令的代碼長度。【答案】：D.堆棧指針SP的內(nèi)容是（）oA.棧頂單元內(nèi)容B.棧頂單元地址C.棧底單元內(nèi)容D.棧底單元地址【分析】：堆棧是按特定順序進行訪問的存儲區(qū)，其訪問方式是后進先出，即先存入的數(shù)據(jù)后讀出。對堆棧的訪問由堆棧指針寄存器SP控制，其內(nèi)容為堆棧中棧項單元的地址，即入棧時數(shù)據(jù)保存在SP指向的單元，出棧時將SP指向單元的內(nèi)容取出。【答案】：B2002年：采用直接尋址方式，則操作數(shù)在（）中。A.主存 B.寄存器 C.直接存取存儲器 D.光盤【分析】：直接尋址方式是指在指令中直接給出操作數(shù)在存儲器中的地址，操作數(shù)在主存儲器中，指令中的地址直接作為有效地址，對存儲器進行訪問即可取得操作數(shù)。【答案】：A零息I:指令的操作數(shù)一般隱含在（）中。A.磁盤 B.磁帶 C.寄存器 D.光盤【分析】：零地址指令只有操作碼，沒有操作數(shù)。這種指令有兩種情況：一是無需操作數(shù)，另一種是操作數(shù)為默認的（隱含的），默認為操作數(shù)在寄存器中，指令可直接訪問寄存器。【答案】：C2003年：3.假設(shè)寄存器R中的數(shù)值為200,主存地址為200和300的地址單元中存效的內(nèi)容分別是300和400,則什么方式下訪問到的操作數(shù)為200（）oA.直接尋址200B.寄存器間接尋址（R）C.存儲器間接尋址（200）D.寄存器尋址R【分析】：直接尋址200的操作數(shù)為300,寄存器間接尋址（R）的操作數(shù)300,存儲器間接尋址（200）的操作數(shù)為400,寄存器尋址R的操作數(shù)為200。【答案】：D5.單地址指令（）。A.只能對單操作數(shù)進行加工處理B.只能對雙操作數(shù)進行加工處理C.無處理雙操作數(shù)的功能D.既能對單操作數(shù)進行加工處理，也能在隱含約定另一操作數(shù)（或地址）時，對雙操作數(shù)進行運算【分析】：單地址指令既能對單操作數(shù)進行加工處理，也能對雙操作數(shù)進行運算。當處理雙操作數(shù)時，一個操作數(shù)在指令中給出，另一個操作數(shù)則是隱含約定的，例如堆棧操作指令中的入棧指令PUSH,指令中只給出源操作數(shù)，而目的操作數(shù)則由計算機中的堆棧指針（SP）確定，在指令中不需要指定。【答案】：D2004年：14.反映計算機基本功能的是（）oA.操作系統(tǒng) B.系統(tǒng)軟件 C.指令系統(tǒng) D.數(shù)據(jù)庫系統(tǒng)【分析】：指令系統(tǒng)：計算機中各種指令的集合，它反映了計算機硬件具備的基本功能。【答案】：C2005年：.在大多數(shù)情況下，一條機器指令中是不直接用二進制代碼來指定（）oA.下一條指令的地址B.操作的類型C.操作數(shù)地址D.結(jié)果存放地址答案：A.在存儲器堆棧中，若棧底地址為A,SP指針初值為A-1,當堆棧采用從地址小的位置向地址大的位置生成時，彈出操作應(yīng)是（）?A.先從堆棧取出數(shù)據(jù)，然后SP指針減1B.先從堆棧取出數(shù)據(jù)，然后SP指針加1SP指針先加1,然后從堆棧取出數(shù)據(jù)SP指針先減1,然后從堆棧取出數(shù)據(jù)【分析】：堆棧是按特定順序進行訪問的存儲區(qū)，其訪問方式是后進先出，即先存入的數(shù)據(jù)后讀出。對堆棧的訪問由堆棧指針寄存器SP控制，當堆棧采用從地址小的位置向地址大的位置生成時，入棧操作是SP指針先加1，然后將數(shù)據(jù)存入堆棧，從堆棧取出彈出操作是先從堆棧取出數(shù)據(jù)，然后SP指針減【答案】：A10.轉(zhuǎn)移指令執(zhí)行結(jié)束后，程序計數(shù)器PC中存放的是（）oA.該轉(zhuǎn)移指令的地址B.順序執(zhí)行的下條指令地址C.轉(zhuǎn)移的目標地址D.任意指令地址【分析】：轉(zhuǎn)移指令執(zhí)行過程中，將轉(zhuǎn)移指令所指的子程序的起始地址裝入PC,因此轉(zhuǎn)移指令執(zhí)行結(jié)束后，程序計數(shù)器PC中存放的是轉(zhuǎn)移的目標地址。【答案】：C三、改錯題：3.在寄存器尋址方式中，指定寄存器中存放的是操作數(shù)地址。（2000）【分析】：在寄存器間接尋址方式中，指定寄存器中存放的是操作數(shù)地址；而在寄存器尋址方式中，指定寄存器中存放著操作數(shù)。【答案】：在寄存器尋址方式中，指定寄存器中存放著操作數(shù)。1.在計算機中，各指令周期的時間長度是相同的。（2002）【分析】：在計算機中，由于指令的種類不同，功能不同，執(zhí)行每條指令時機器所進行的操作可能就不同，所需要的時間長短也可能不相同，所以各指令周期的時間長度不一定相同。【答案】：一般說，由于各指令功能的不同，它們的指令周期有長有短，不定相同。22.轉(zhuǎn)移指令執(zhí)行結(jié)束后，目標地址可放在任意寄存器中。（2004年）【分析】：轉(zhuǎn)移指令執(zhí)行過程中，將轉(zhuǎn)移指令所指的子程序的起始地址裝入PC,因此轉(zhuǎn)移指令執(zhí)行結(jié)束后，程序計數(shù)器PC中存放的是轉(zhuǎn)移的目標地址。【答案】：轉(zhuǎn)移指令執(zhí)行結(jié)束后，目標地址放在程序計數(shù)器PC中。第5章控制器一、名詞解釋：歷年真題：（2001年）6.邏輯地址：程序員編程所用的地址以及CPU通過指令訪問主存時所產(chǎn)生的地址。與內(nèi)存物理地址無固定對應(yīng)關(guān)系的地址。（2001年）7.微程序控制器：將執(zhí)行指令所需要的微命令以代碼形式編成微指令序列（微程序），存入一個控制存儲器，需要時從該存儲器中讀取。按這種方式工作的控制器為微程序控制器。（2002年）3.控制存儲器（CPU內(nèi)的）：CPU內(nèi)用于存放實現(xiàn)指令系統(tǒng)全部指令的微程序的只讀存儲器稱為控制存儲器。（2004年）20.垂直型微指令：一種微指令類型，設(shè)置微操作碼字段，采用微操作碼編碼法，由微操作碼規(guī)定微指令的功能。（2005年）23.微程序控制器：將執(zhí)行指令所需要的微命令以代碼形式編成微指令序列（微程序），存入一個控制存儲器，需要時從該存儲器中讀取。按這種方式工作的控制器為微程序控制器。近年以來每年考本章的名詞解釋，所以第五章的名稱解釋是考試的重點。這里給大家列出了本章的名詞解釋，大家要熟悉?下，這都是本章的基本概念，有利于做名稱解釋、選擇題、改錯題和填空題。.指令周期：從一條指令的啟動到下一條指令的啟動的間隔時間。.機器周期：指令執(zhí)行中每一步操作所需的時間。.指令仿真：通過改變微程序?qū)崿F(xiàn)不同機器指令系統(tǒng)的方式，使得在?種計算機上可以運行另種計算機上的指令代碼。.指令模擬：在一種計算機上用軟件來解釋執(zhí)行另一種計算機的指令。.硬連線邏輯：一種控制器邏輯，用一個時序電路產(chǎn)生時間控制信號，采用組合邏輯電路實現(xiàn)各種控制功能。.微程序：存儲在控制存儲中的完成指令功能的程序，由微指令組成。.微指令：控制器存儲的控制代碼，分為操作控制部分和順序控制部分。.微操作：在微程序控制器中，執(zhí)行部件接受微指令后所進行的操作。.微地址：微每時令在控制存儲器中的存儲地址。.控制存儲器：CPU內(nèi)用于存放實現(xiàn)指令系統(tǒng)全部指令的微程序的只讀存儲器稱為控制存儲器。.相容性微操作：在同時或同個CPU周期內(nèi)可以并行執(zhí)行的微操作。.相斥性微操作：不能在同時或不能在同一個CPU周期內(nèi)并行執(zhí)行的微操作。二、選擇題和填空題：2000年：.在取指周期中，是按照（）的內(nèi)容訪問主存，以讀取指令。A.指令寄存器IR B.程序狀態(tài)寄存器PSC.存儲器數(shù)據(jù)寄存器MDR D.程序計數(shù)器PC【分析】：每一條指令的執(zhí)行都是從取指令開始，需要對主存儲器進行訪問。程序計數(shù)器PC是用來存放將要讀取并執(zhí)行的指令在主存儲器中的地址，對主存儲器訪問時所需要的地址由程序計數(shù)器PC來提供，即需要按程序計數(shù)器PC的內(nèi)容來訪問主存儲器。【答案】：D.在微程序控制中，一個節(jié)拍中所需要的一組微命令，被編成?條（ 。【分析】：控制部件通過控制總線向執(zhí)行部件發(fā)出的控制命令稱為微命令，它是計算機中最基本的、不可再分的命令單元。在一個節(jié)拍中，一組實現(xiàn)一定功能的微命令的組合構(gòu)成一條微指令。【答案】：微指令2002年：.微程序存放在（）oA.主存中 B.堆棧中 C.只讀存儲器中 D.磁盤中【分析】：微程序控制的基本思想是把指令執(zhí)行所需的所有控制信號存放在存儲器中，需要時從這個存儲器中讀取。由于每一條微指令執(zhí)行時所發(fā)出的控制信號是事先設(shè)計好的，不需要改變，故此存放所有控制信號的存儲器應(yīng)為只讀存儲器，并將其集成到CPU內(nèi)，稱其為控制存儲器。【答案】：C.在微程鬲控制方式中，機器指令和微指令的關(guān)系是（）。A.每一條機器指令由一條微指令來解釋執(zhí)行B.每一條機器指令由一段（或一個）微程序來解釋執(zhí)行一段機器指令組成的工作程序可由一條微指令來解釋執(zhí)行一條微指令由若干條機器指令組成【分析】：在微程序控制方式中，控制部件通過控制總線向執(zhí)行部件發(fā)出的各種控制命令稱為微命令，在一個CPU周期中，一組實現(xiàn)一定功能的微命令的組合構(gòu)成一條微指令，有序的微指令序列構(gòu)成一段微程序。微程序的作用是實現(xiàn)一條對應(yīng)的機器指令，即每一條機器指令是由一段（或一個）微程序來解釋執(zhí)行的。【答案】：B2003年：.下列說法中，合理的是（）?A.執(zhí)行各條指令的機器周期數(shù)相同，各機器周期的長度均勻.執(zhí)行各條指令的機器周期數(shù)相同，各機器周期的長度可變C.執(zhí)行各條指令的機器周期數(shù)可變，各機器周期的長度均勻D.執(zhí)行各條指令的機器周期數(shù)可變，各機器周期的長度可變【分析】：機器周期是指令執(zhí)行中每一步操作所需要的時間，一般以CPU中完成一個運算操作所需的時間作為機器周期的基本時間，其長度是均勻的，而各種指令的功能不同，因而各指令執(zhí)行時所需的機器周期數(shù)是可變的。【答案】：C10.微地址是指微指令（）。A.在主存的存儲位置 B.在堆棧的存儲位置C.在磁盤的存儲位置 D.在控制存儲器的存儲位置【分析】：微程序控制的基本思想是：把指令執(zhí)行所需要的所仃控制信號存放在控制存儲器中，需要時從這個存儲器中讀取，即把操作控制信號編成微指令，存放在控制存儲器中。條機器指令的功能通常用許多條微指令組成的序列來實現(xiàn)，這個微指令序列稱為微程序。微指令在控制存儲器中的存儲位置稱為微地址。【答案】：D2004年：.在微程序控制中，把操作控制信號編成（）oA.微指令 B.微地址 C.操作碼 D.程序【分析】：微程序控制的基本思想是：把指令執(zhí)行所需要的所有控制信號存放在控制存儲器中，需要時從這個存儲器中讀取，即把操作控制信號編成微指令，存放在控制存儲器中。一條機器指令的功能通常用許多條微指令組成的序列來實現(xiàn)，這個微指令序列稱為微程序。微指令在控制存儲器中的存儲位置稱為微地址。【答案】：A.從一條指令的啟動到下條指令的啟動的間隔時間稱為（）oA.時鐘周期 B.機器周期 C.工作周期D.指令周期【分析】：指令周期：從一條指令的啟動到下?條指令的啟動的間隔時間。機器周期：指令執(zhí)行中每一步操作所需的時間，又稱CPU周期。時鐘周期：計算機主頻周期。【答案】：D2005年：11.通常，微指令的周期對應(yīng)一個（）oA.指令周期 B.主頻周期 C.機器周期 D.工作周期【分析工指令周期：從一條指令的啟動到下一條指令的啟動的間隔時間。機器周期：指令執(zhí)行中每一步操作所需的時間，又稱CPU周期。時鐘周期：計算機主頻周期。微指令周期等于讀出一條微指令加上執(zhí)行該微指令的所需時間。通常微指令周期與指令的機器周期相等。【答案】：C19.在微程序控制器中，控制存儲器由（ ）構(gòu)成，用于存放 。【分析】：CPU內(nèi)用于存放實現(xiàn)指令系統(tǒng)全部指令的微程序的只讀存儲器稱為控制存儲器。【答案】：只讀存儲器 微程序三、改錯題：歷年真題：（2000年）9.單總線結(jié)構(gòu)系統(tǒng)是指：各大功能部件之間用一根信號線連接。【答案】：單總線結(jié)構(gòu)系統(tǒng)是指各寄存器及ALU之間的數(shù)據(jù)通路只用一條總線構(gòu)成。（2002年）2.CPU只是計算機的控制器。【分析】：計算機硬件系統(tǒng)是由運算器、控制器、存儲器、輸入設(shè)備和輸出設(shè)備等五大部分組成，其中將運算器和控制器合在一起稱為中央處理器，簡稱為CPU。【答案】：CPU是由控制器和運算器組成的。（2003年）21.硬連線方式是用時序電路產(chǎn)生時間控制信號，用存儲邏輯電路實現(xiàn)各種控制功能。【分析】：在采用組合邏輯和時鐘信號相結(jié)合的硬連線控制器中，時間控制信號是由時序電路產(chǎn)生，而各種控制功能則是由組合邏輯電路實現(xiàn)。【答案】：硬連線方式是用時序電路產(chǎn)生時間控制信號，用組合邏輯電路實現(xiàn)各種控制功能。（2004年）21.在一條微指令中，順序控制部分的作用是發(fā)出指揮全機工作的控制信號。【分析】：在一條微指令中，控制字部分的作用是發(fā)出指揮全機工作的控制信號；順序控制部分的作用是產(chǎn)生后繼微指令的地址。【答案】：在一條微指令中，順序控制部分的作用是產(chǎn)生后繼微指令的地址。四、簡答題：歷年真題：（2000年）4.在CPU中，哪些寄存器屬于控制用的指令部件？它們各起什么作用？（5分）【答案】：（1）程序計數(shù)器PC,提供取指地址，從而控制程序執(zhí)行順序。（2）指令寄存器IR,存放現(xiàn)行指令，作為產(chǎn)生各種微操作命令的基本邏輯依據(jù)。（3）程序狀態(tài)寄存器PS,記錄程序運行結(jié)果的某些特征標志，或用來設(shè)置程序運行方式與優(yōu)先級，參與形成某些微操作命令。（2001年）1.硬連線控制器如何產(chǎn)生微命令？產(chǎn)生微命令的主要條件是哪些？【答案】：硬連線控制器依靠組合邏輯電路產(chǎn)生命令；（1分）組合邏輯電路的輸入是產(chǎn)生微命令的條件，主要有：①指令代碼；②時序信號；③程序狀態(tài)信息與標志位；④外部請求信號。（4分）（2002年）3.微程序控制器怎么產(chǎn)生操作控制信號，這種控制器有何優(yōu)缺點？【答案】：操作控制信號的產(chǎn)生：事先把操作控制信號以代碼形式構(gòu)成微指令，然后存放到控制存儲器中，取出微指令時，其代碼直接或譯碼產(chǎn)生操作控制信號。優(yōu)點：規(guī)整、易于修改和擴展。缺點：速度較慢。（2003年）26.當讀取并執(zhí)行一條指令時，控制器的主要功能是什么？【答案】：①人主存取指令，并計算下一條指令在主存中的地址；②對指令進行譯碼，產(chǎn)生相應(yīng)的操作控制信號：③控制指令執(zhí)行的步驟和數(shù)據(jù)流動的方向。（2004年）28.與硬連線控制器相比，微程序控制器有哪些優(yōu)缺點？【答案工與硬連線控制器相比，微程序控制器的優(yōu)點是設(shè)計規(guī)整、易于修改和擴展。缺點是比硬連線控制器速度慢。（2005年）28.硬連線控制器主要山哪幾部分構(gòu)成？它是如何產(chǎn)生控制信號的？【答案】：硬連線控制器主要由時鐘源、環(huán)形脈沖發(fā)生器、控制信號編碼器電路和指令譯碼器電路構(gòu)成。硬連線控制器采用組合邏輯與時鐘信號結(jié)合的方式產(chǎn)生控制信號。山上可見，每年都會考本章的簡答題。考試的兩個重點：一個是硬連線控制器的有關(guān)知識，另一個是微程序控制器有關(guān)內(nèi)容。這兩方面大家一定重點掌握。下面一些知識也要求大家了解微程序控制器的構(gòu)成：控制存儲器、微指令寄存器UIR、微地址寄存器UAR、地址轉(zhuǎn)移邏輯等。微指令控制字編碼的方式：微指令編碼的3種方式分別是：直接表示法、編碼表示法、混合表示法。直接表示法是將每個控制信號都作為微指令中的一個位。這種方法的特點是簡單直觀，其輸出直接用于控制，但編碼效率低。編碼表示法是將微指令進行分組編碼，將不同時出現(xiàn)的相斥信號分在一個組中，然后將其編碼成較短的代碼。這種方法減少了控制存儲器所需要的存儲器的代碼的數(shù)量，但是編碼的指令代碼需要譯碼器譯碼，增加了控制信號的延遲，影響CPU的工作頻率。混合表示法是把直接表示法與編碼方法相結(jié)合使用，即采用部分直接表示部分編碼的方法，將一些速度要求較高，或與其他控制信號都相容的控制信號以直接方式表示，而將剩余信號以編碼方式。混合表示法便于綜合考慮指令字長、靈活性和執(zhí)行速度方面的要素。微地址的形成方法：（微指令中順序控制字段的編碼）微地址的形成方法有三種方式：計數(shù)器方式、斷定方式和結(jié)