事業(yè)單位考試計(jì)算機(jī)專業(yè)課復(fù)習(xí)資料全集　最新

1、本復(fù)習(xí)資料是根據(jù)武漢市事業(yè)單位招考筆試計(jì)算機(jī)崗位考試大綱要求編寫，涉及知識(shí)涵蓋了計(jì)算機(jī)專業(yè)知識(shí)包括：數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)網(wǎng)絡(luò)、計(jì)算機(jī)組成原理、操作系統(tǒng)、數(shù)據(jù)庫(kù)原理等知識(shí)，本稿分為五個(gè)部分。第一部分 數(shù)據(jù)結(jié)構(gòu)要點(diǎn)第一章 概 論*數(shù)據(jù)就是指能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的信息的載體。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位。*數(shù)據(jù)結(jié)構(gòu)的定義：邏輯結(jié)構(gòu)：從邏輯結(jié)構(gòu)上描述數(shù)據(jù)，獨(dú)立于計(jì)算機(jī)。線性結(jié)構(gòu)：一對(duì)一關(guān)系，是數(shù)據(jù)元素之間定義了次序關(guān)系的集合（全序集合）。圖狀結(jié)構(gòu)：多對(duì)多關(guān)系，是數(shù)據(jù)元素之間定義了網(wǎng)狀關(guān)系的集合。存儲(chǔ)結(jié)構(gòu)：是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)。順序

2、存儲(chǔ)結(jié)構(gòu)：如數(shù)組。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：如鏈表。索引存儲(chǔ)結(jié)構(gòu)：稠密索引：每個(gè)結(jié)點(diǎn)都有索引項(xiàng)。稀疏索引：每組結(jié)點(diǎn)都有索引項(xiàng)。散列存儲(chǔ)結(jié)構(gòu)：如散列表。數(shù)據(jù)運(yùn)算。對(duì)數(shù)據(jù)的操作。定義在邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算集合。常用的有：檢索、插入、刪除、更新、排序。*數(shù)據(jù)類型：是一個(gè)值的集合以及在這些值上定義的一組操作的總稱。原子類型：由語(yǔ)言提供。結(jié)構(gòu)類型：由用戶借助于描述機(jī)制定義，是導(dǎo)出類型。抽象數(shù)據(jù)類型adt：是抽象數(shù)據(jù)的組織和與之的操作。相當(dāng)于在概念層上描述問題。優(yōu)點(diǎn)是將數(shù)據(jù)和操作封裝在一起實(shí)現(xiàn)了信息隱藏。*程序設(shè)計(jì)的實(shí)質(zhì)是對(duì)實(shí)際問題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)一個(gè)好的算法。算法取決于數(shù)據(jù)結(jié)構(gòu)。*算法是指

3、的是解決問題的步驟序列，它必須具備可執(zhí)行性、確定性、有窮性這三個(gè)特性，以一個(gè)或多個(gè)值輸入，并以一個(gè)或多個(gè)值輸出。評(píng)價(jià)算法的好壞的因素：算法是正確的；執(zhí)行算法的時(shí)間；執(zhí)行算法的存儲(chǔ)空間（主要是輔助存儲(chǔ)空間）；算法易于理解、編碼、調(diào)試。*時(shí)間復(fù)雜度：是某個(gè)算法的時(shí)間耗費(fèi)，它是該算法所求解問題規(guī)模n的函數(shù)?！締栴}】時(shí)間復(fù)雜度的計(jì)算。方法：先求頻度，再求時(shí)間復(fù)雜度。習(xí)題一 分析以下程序的時(shí)間復(fù)雜度f(wàn)or (i=1;in;i+)y=y+1; for (j=0;j=(2*n);j+)x+; 分析：語(yǔ)句的頻度是f1(n)=n-1 語(yǔ)句的頻度是f2n)=(n-1)(2n-1)語(yǔ)句和語(yǔ)句得時(shí)間復(fù)雜度分別是：o1

4、(1)=o(n) o2(n)=o(n2)習(xí)題二 分析下列程序段的時(shí)間復(fù)雜度i=1; while (i=1)i=i*2 分析： i=1 i=1*2 i=2 i=2*2 i=22 i=23 i=2f(n) i=2f(n)+1即：f(n)=log2n語(yǔ)句的時(shí)間復(fù)雜度是f(n)=log2n。習(xí)題三 求下列程序段的頻度f(wàn)or (i=1;i=n;i+) for (j=1;j=i;j+)for (k=1;k=j;kelem=(elemtype*)malloc(list_max_length *sizeof(elemtype); /分配空間 if (l-elem=null) return error; /若分

5、配空間不成功，返回error l-length=0; /將當(dāng)前線性表長(zhǎng)度置0 return ok; /成功返回ok *順序表是按線性表的邏輯結(jié)構(gòu)次序依次存放在一組地址連續(xù)的存儲(chǔ)單元中。在存儲(chǔ)單元中的各元素的物理位置和邏輯結(jié)構(gòu)中各結(jié)點(diǎn)相鄰關(guān)系是一致的。地址計(jì)算：loc(a(i)=loca(1)+(i-1)*d；（首地址為1）在順序表中實(shí)現(xiàn)的基本運(yùn)算： 插入：平均移動(dòng)結(jié)點(diǎn)次數(shù)為n/2；平均時(shí)間復(fù)雜度均為o(n)。刪除：平均移動(dòng)結(jié)點(diǎn)次數(shù)為（n-1）/2；平均時(shí)間復(fù)雜度均為o(n)。*線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同，為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還存

6、儲(chǔ)了其后繼結(jié)點(diǎn)的地址信息(即指針或鏈)。這兩部分信息組成鏈表中的結(jié)點(diǎn)結(jié)構(gòu)。 一個(gè)單鏈表由頭指針的名字來(lái)命名。*單鏈表運(yùn)算：建立單鏈表頭插法：s-next=head；head=s；生成的順序與輸入順序相反。平均時(shí)間復(fù)雜度均為o(n)。尾插法：head=rear=null；if(head=null) head=s;else r-next=s;r=s; 平均時(shí)間復(fù)雜度均為o(n)加頭結(jié)點(diǎn)的算法：對(duì)開始結(jié)點(diǎn)的操作無(wú)需特殊處理，統(tǒng)一了空表和非空表。查找按序號(hào)：與查找位置有關(guān)，平均時(shí)間復(fù)雜度均為o(n)。按值：與輸入實(shí)例有關(guān)，平均時(shí)間復(fù)雜度均為o(n)。插入運(yùn)算：p=getnode(l,i-1)；s-ne

7、xt=p-next；p-next=s；平均時(shí)間復(fù)雜度均為o(n)刪除運(yùn)算：p=getnode(l,i-1)；r=p-next；p-next=r-next；free(r)；平均時(shí)間復(fù)雜度均為o(n)*單循環(huán)鏈表是一種首尾相接的單鏈表，終端結(jié)點(diǎn)的指針域指向開始結(jié)點(diǎn)或頭結(jié)點(diǎn)。鏈表終止條件是以指針等于頭指針或尾指針。 采用單循環(huán)鏈表在實(shí)用中多采用尾指針表示單循環(huán)鏈表。優(yōu)點(diǎn)是查找頭指針和尾指針的時(shí)間都是o(1)，不用遍歷整個(gè)鏈表。雙鏈表就是雙向鏈表，就是在單鏈表的每個(gè)結(jié)點(diǎn)里再增加一個(gè)指向其直接前趨的指針域prior,形成兩條不同方向的鏈。由頭指針head惟一確定。雙鏈表也可以頭尾相鏈接構(gòu)成雙(向)循環(huán)鏈

8、表。雙鏈表上的插入和刪除時(shí)間復(fù)雜度均為o (1)。*順序表和鏈表的比較：基于空間：順序表的存儲(chǔ)空間是靜態(tài)分配，存儲(chǔ)密度為1；適于線性表事先確定其大小時(shí)采用。鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配，存儲(chǔ)密度1；適于線性表長(zhǎng)度變化大時(shí)采用。 基于時(shí)間：順序表是隨機(jī)存儲(chǔ)結(jié)構(gòu)，當(dāng)線性表的操作主要是查找時(shí)，宜采用。以插入和刪除操作為主的線性表宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。若插入和刪除主要發(fā)生在表的首尾兩端，則宜采用尾指針表示的單循環(huán)鏈表。第三章 棧和隊(duì)列*棧(stack)是僅限制在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，稱插入、刪除這一端為棧頂，另一端稱為棧底。表中無(wú)元素時(shí)為空棧。棧的修改是按后進(jìn)先出的原則進(jìn)行的，我們又稱棧為l

9、ifo表(last in first out)。通常棧有順序棧和鏈棧兩種存儲(chǔ)結(jié)構(gòu)。*棧的基本運(yùn)算有六種： 構(gòu)造空棧：initstack(s)判?？眨簊tackempty(s)判棧滿：stackfull(s)進(jìn)棧： push(s,x)退棧： pop(s)取棧頂元素：stacktop(s) *隊(duì)列(queue)是一種運(yùn)算受限的線性表，插入在表的一端進(jìn)行，而刪除在表的另一端進(jìn)行，允許刪除的一端稱為隊(duì)頭(front)，允許插入的一端稱為隊(duì)尾(rear) ,隊(duì)列的操作原則是先進(jìn)先出的，又稱作fifo表(first in first out) 。隊(duì)列也有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種存儲(chǔ)結(jié)構(gòu)。*隊(duì)列的基本運(yùn)算有六

10、種： 置空隊(duì)：initqueue(q)判隊(duì)空：queueempty(q)判隊(duì)滿：queuefull(q)入隊(duì)：enqueue(q,x)出隊(duì)：dequeue(q)取隊(duì)頭元素：queuefront(q)*順序隊(duì)列的假上溢現(xiàn)象：由于頭尾指針不斷前移，超出向量空間。這時(shí)整個(gè)向量空間及隊(duì)列是空的卻產(chǎn)生了“上溢”現(xiàn)象。為了克服假上溢現(xiàn)象引入循環(huán)向量的概念，是把向量空間形成一個(gè)頭尾相接的環(huán)形，這時(shí)隊(duì)列稱循環(huán)隊(duì)列。判定循環(huán)隊(duì)列是空還是滿，方法有三種： 第一種是另設(shè)一個(gè)布爾變量來(lái)判斷；第二種是少用一個(gè)元素空間，入隊(duì)時(shí)先測(cè)試（(rear+1)%m = front）? 滿：空； 第三種就是用一個(gè)計(jì)數(shù)器記錄隊(duì)列中的元

11、素的總數(shù)。*隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈隊(duì)列，一個(gè)鏈隊(duì)列就是一個(gè)操作受限的單鏈表。為了便于在表尾進(jìn)行插入(入隊(duì))的操作，在表尾增加一個(gè)尾指針，一個(gè)鏈隊(duì)列就由一個(gè)頭指針和一個(gè)尾指針唯一地確定。鏈隊(duì)列不存在隊(duì)滿和上溢的問題。在鏈隊(duì)列的出隊(duì)算法中，要注意當(dāng)原隊(duì)中只有一個(gè)結(jié)點(diǎn)時(shí)，出隊(duì)后要同進(jìn)修改頭尾指針并使隊(duì)列變空。第四章 串*串的基本運(yùn)算有： 求串長(zhǎng)strlen(char*s)串復(fù)制strcpy(char*to,char*from)串聯(lián)接strcat(char*to,char*from)串比較charcmp(char*s1,char*s2)字符定位strchr(char*s,charc)*串是特殊的線性

12、表(結(jié)點(diǎn)是字符)，所以串的存儲(chǔ)結(jié)構(gòu)與線性表的存儲(chǔ)結(jié)構(gòu)類似。串的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序串。順序串又可按存儲(chǔ)分配的不同分為： 靜態(tài)存儲(chǔ)分配：直接用定長(zhǎng)的字符數(shù)組來(lái)定義。優(yōu)點(diǎn)是涉及串長(zhǎng)的操作速度快，但不適合插入、鏈接操作。動(dòng)態(tài)存儲(chǔ)分配：是在定義串時(shí)不分配存儲(chǔ)空間，需要使用時(shí)按所需串的長(zhǎng)度分配存儲(chǔ)單元。*串的鏈?zhǔn)酱鎯?chǔ)就是用單鏈表的方式存儲(chǔ)串值，串的這種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈串。鏈串與單鏈表的差異只是它的結(jié)點(diǎn)數(shù)據(jù)域?yàn)閱蝹€(gè)字符。為了解決存儲(chǔ)密度低的狀況，可以讓一個(gè)結(jié)點(diǎn)存儲(chǔ)多個(gè)字符，即結(jié)點(diǎn)的大小。 *第五章多維數(shù)組和廣義表數(shù)組一般用順序存儲(chǔ)的方式表示。存儲(chǔ)的方式有： 行優(yōu)先順序，也就是把數(shù)組逐行依次排列。pa

13、scal、c列優(yōu)先順序，就是把數(shù)組逐列依次排列。fortran*地址的計(jì)算方法：按行優(yōu)先順序排列的數(shù)組：loca(ij)=loca(11)+(i-1)*n+(j-1)*d。按列優(yōu)先順序排列的數(shù)組：loca(ij)=loca(11)+(j-1)*n+(i-1)*d。*矩陣的壓縮存儲(chǔ)：為多個(gè)相同的非零元素分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配空間。特殊矩陣的概念：所謂特殊矩陣是指非零元素或零元素分布有一定規(guī)律的矩陣。稀疏矩陣的概念：一個(gè)矩陣中若其非零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于零元素的個(gè)數(shù)，則該矩陣稱為稀疏矩陣。*稀疏矩陣的壓縮存儲(chǔ)方式用三元組表把非零元素的值和它所在的行號(hào)列號(hào)做為一個(gè)結(jié)點(diǎn)存放在一起，用這些結(jié)點(diǎn)組

14、成的一個(gè)線性表來(lái)表示。但這種壓縮存儲(chǔ)方式將失去隨機(jī)存儲(chǔ)功能。加入行表記錄每行的非零元素在三元組表中的起始位置，即帶行表的三元組表。*廣義表是n(n0)個(gè)元素的有限序列，其中的元素是原子或者是一個(gè)廣義表。 第六章樹*樹是n個(gè)結(jié)點(diǎn)的有限集合，非空時(shí)必須滿足：只有一個(gè)稱為根的結(jié)點(diǎn)；其余結(jié)點(diǎn)形成m個(gè)不相交的子集，并稱根的子樹。根是開始結(jié)點(diǎn)；結(jié)點(diǎn)的子樹數(shù)稱度；度為0的結(jié)點(diǎn)稱葉子(終端結(jié)點(diǎn))；度不為0的結(jié)點(diǎn)稱分支結(jié)點(diǎn)(非終端結(jié)點(diǎn))；除根外的分支結(jié)點(diǎn)稱內(nèi)部結(jié)點(diǎn)；有序樹是子樹有左，右之分的樹；無(wú)序樹是子樹沒有左，右之分的樹；森林是m個(gè)互不相交的樹的集合；樹的四種不同表示方法：樹形表示法；嵌套集合表示法；凹入表

15、示法；廣義表表示法。*二叉樹的定義：是n0個(gè)結(jié)點(diǎn)的有限集，它是空集(n=0)或由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的分別稱作這個(gè)根的左子樹和右子樹的二叉樹組成。二叉樹不是樹的特殊情形，與度數(shù)為2的有序樹不同。二叉樹的4個(gè)重要性質(zhì)：.二叉樹上第i層上的結(jié)點(diǎn)數(shù)目最多為2(i-1)(i1)；深度為k的二叉樹至多有(2k)-1個(gè)結(jié)點(diǎn)(k1)；在任意一棵二叉樹中，若終端結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1；具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為int(log2n)+1。滿二叉樹是一棵深度為k，結(jié)點(diǎn)數(shù)為(2k)-1的二叉樹；完全二叉樹是滿二叉樹在最下層自右向左去處部分結(jié)點(diǎn)；*二叉樹的順序存儲(chǔ)結(jié)構(gòu)就是把

16、二叉樹的所有結(jié)點(diǎn)按照層次順序存儲(chǔ)到連續(xù)的存儲(chǔ)單元中。（存儲(chǔ)前先將其畫成完全二叉樹）樹的存儲(chǔ)結(jié)構(gòu)多用的是鏈?zhǔn)酱鎯?chǔ)。bintnode的結(jié)構(gòu)為lchild|data|rchild，把所有bintnode類型的結(jié)點(diǎn)，加上一個(gè)指向根結(jié)點(diǎn)的bintree型頭指針就構(gòu)成了二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，稱為二叉鏈表。它就是由根指針root唯一確定的。共有2n個(gè)指針域，n+1個(gè)空指針。*根據(jù)訪問結(jié)點(diǎn)的次序不同可得三種遍歷：先序遍歷(前序遍歷或先根遍歷)，中序遍歷(或中根遍歷)、后序遍歷(或后根遍歷)。時(shí)間復(fù)雜度為o(n)。*利用二叉鏈表中的n+1個(gè)空指針域來(lái)存放指向某種遍歷次序下的前趨結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針，這些附加的指

17、針就稱為線索，加上線索的二叉鏈表就稱為線索鏈表。線索使得查找中序前趨和中序后繼變得簡(jiǎn)單有效，但對(duì)于查找指定結(jié)點(diǎn)的前序前趨和后序后繼并沒有什么作用。*樹和森林及二叉樹的轉(zhuǎn)換是唯一對(duì)應(yīng)的。轉(zhuǎn)換方法： 樹變二叉樹：兄弟相連，保留長(zhǎng)子的連線。二叉樹變樹：結(jié)點(diǎn)的右孩子與其雙親連。森林變二叉樹：樹變二叉樹，各個(gè)樹的根相連。*樹的存儲(chǔ)結(jié)構(gòu)：有雙親鏈表表示法：結(jié)點(diǎn)data | parent，對(duì)于求指定結(jié)點(diǎn)的雙親或祖先十分方便，但不適于求指定結(jié)點(diǎn)的孩子及后代。孩子鏈表表示法：為樹中每個(gè)結(jié)點(diǎn)data | next設(shè)置一個(gè)孩子鏈表firstchild，并將data | firstchild存放在一個(gè)向量中。雙親孩子

18、鏈表表示法：將雙親鏈表和孩子鏈表結(jié)合。孩子兄弟鏈表表示法：結(jié)點(diǎn)結(jié)構(gòu)leftmostchild |data | rightsibing，附加兩個(gè)分別指向該結(jié)點(diǎn)的最左孩子和右鄰兄弟的指針域。*樹的前序遍歷與相對(duì)應(yīng)的二叉樹的前序遍歷一致；樹的后序遍歷與相對(duì)應(yīng)的二叉樹的中序遍歷一致。*樹的帶權(quán)路徑長(zhǎng)度是樹中所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。樹的帶權(quán)路徑長(zhǎng)度最小的二叉樹就稱為最優(yōu)二叉樹（即哈夫曼樹）。在葉子的權(quán)值相同的二叉樹中，完全二叉樹的路徑長(zhǎng)度最短。哈夫曼樹有n個(gè)葉結(jié)點(diǎn)，共有2n-1個(gè)結(jié)點(diǎn)，沒有度為1的結(jié)點(diǎn)，這類樹又稱為嚴(yán)格二叉樹。*變長(zhǎng)編碼技術(shù)可以使頻度高的字符編碼短，而頻度低的字符編碼長(zhǎng)，但是變長(zhǎng)編

19、碼可能使解碼產(chǎn)生二義性。如00、01、0001這三個(gè)碼無(wú)法。在解碼時(shí)確定是哪一個(gè)，所以要求在字符編碼時(shí)任一字符的編碼都不是其他字符編碼的前綴，這種碼稱為前綴碼（其實(shí)是非前綴碼）。哈夫曼樹的應(yīng)用最廣泛地是在編碼技術(shù)上，它能夠容易地求出給定字符集及其概率分布的最優(yōu)前綴碼。哈夫曼編碼的構(gòu)造很容易，只要畫好了哈夫曼樹，按分支情況在左路徑上寫代碼0，右路徑上寫代碼1，然后從上到下到葉結(jié)點(diǎn)的相應(yīng)路徑上的代碼的序列就是該結(jié)點(diǎn)的最優(yōu)前綴碼。第七章 圖*圖的邏輯結(jié)構(gòu)特征就是其結(jié)點(diǎn)(頂點(diǎn))的前趨和后繼的個(gè)數(shù)都是沒有限制的，即任意兩個(gè)結(jié)點(diǎn)之間之間都可能相關(guān)。圖graphg=(v,e)，v是頂點(diǎn)的有窮非空集合，e是頂

20、點(diǎn)偶對(duì)的有窮集。有向圖digraph：每條邊有方向；無(wú)向圖undigraph：每條邊沒有方向。有向完全圖：具有n*(n-1)條邊的有向圖；無(wú)向完全圖：具有n*(n-1)/2條邊的無(wú)向圖；有根圖：有一個(gè)頂點(diǎn)有路徑到達(dá)其它頂點(diǎn)的有向圖；簡(jiǎn)單路徑：是經(jīng)過頂點(diǎn)相同的路徑；簡(jiǎn)單回路是開始和終端重合的簡(jiǎn)單路徑；網(wǎng)絡(luò)：是帶權(quán)的圖。*圖的存儲(chǔ)結(jié)構(gòu)：鄰接矩陣表示法：用一個(gè)n階方陣來(lái)表示圖的結(jié)構(gòu)是唯一的，適合稠密圖。 無(wú)向圖：鄰接矩陣是對(duì)稱的。有向圖：行是出度，列是入度。建立鄰接矩陣算法的時(shí)間是o(n+n2+e),其時(shí)間復(fù)雜度為o(n2)鄰接表表示法：用頂點(diǎn)表和鄰接表構(gòu)成不是唯一的，適合稀疏圖。頂點(diǎn)表結(jié)構(gòu) ver

21、tex | firstedge，指針域存放鄰接表頭指針。鄰接表：用頭指針確定。無(wú)向圖稱邊表；有向圖又分出邊表和逆鄰接表；鄰接表結(jié)點(diǎn)結(jié)構(gòu)為 adjvex | next，時(shí)間復(fù)雜度為o(n+e)，空間復(fù)雜度為o(n+e)。圖的遍歷： 深度優(yōu)先遍歷：借助于鄰接矩陣的列。使用棧保存已訪問結(jié)點(diǎn)。廣度優(yōu)先遍歷：借助于鄰接矩陣的行。使用隊(duì)列保存已訪問結(jié)點(diǎn)。*生成樹的定義：若從圖的某個(gè)頂點(diǎn)出發(fā)，可以系統(tǒng)地訪問到圖中所有頂點(diǎn)，則遍歷時(shí)經(jīng)過的邊和圖的所有頂點(diǎn)所構(gòu)成的子圖稱作該圖的生成樹。最小生成樹：圖的生成樹不唯一，從不同的頂點(diǎn)出發(fā)可得到不同的生成樹，把權(quán)值最小的生成樹稱為最小生成樹(mst)。構(gòu)造最小生成樹的算

22、法： prim算法的時(shí)間復(fù)雜度為o(n2)與邊數(shù)無(wú)關(guān)適于稠密圖。kruskal算法的時(shí)間復(fù)雜度為o(lge),主要取決于邊數(shù)，較適合于稀疏圖。*最短路徑的算法：dijkstra算法，時(shí)間復(fù)雜度為o(n2)。類似于prim算法。*拓?fù)渑判颍菏菍⒂邢驘o(wú)環(huán)圖g中所有頂點(diǎn)排成一個(gè)線性序列，若e(g)，則在線性序列u在v之前，這種線性序列稱為拓?fù)湫蛄小Ｍ負(fù)渑判蛞灿袃煞N方法：無(wú)前趨的頂點(diǎn)優(yōu)先，每次輸出一個(gè)無(wú)前趨的結(jié)點(diǎn)并刪去此結(jié)點(diǎn)及其出邊，最后得到的序列即拓?fù)湫蛄小o(wú)后繼的結(jié)點(diǎn)優(yōu)先：每次輸出一個(gè)無(wú)后繼的結(jié)點(diǎn)并刪去此結(jié)點(diǎn)及其入邊，最后得到的序列是逆拓?fù)湫蛄?。第八?排序*記錄中可用某一項(xiàng)來(lái)標(biāo)識(shí)一個(gè)記錄，則稱為

23、關(guān)鍵字項(xiàng)，該數(shù)據(jù)項(xiàng)的值稱為關(guān)鍵字。排序是使文件中的記錄按關(guān)鍵字遞增(或遞減)次序排列起來(lái)。基本操作：比較關(guān)鍵字大??；改變指向記錄的指針或移動(dòng)記錄。存儲(chǔ)結(jié)構(gòu)：順序結(jié)構(gòu)、鏈表結(jié)構(gòu)、索引結(jié)構(gòu)。經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對(duì)次序保持不變,則稱這種排序方法是穩(wěn)定的，否則排序算法是不穩(wěn)定的。排序過程中不涉及數(shù)據(jù)的內(nèi)、外存交換則稱之為內(nèi)部排序(內(nèi)排序)，反之，若存在數(shù)據(jù)的內(nèi)外存交換，則稱之為外排序。內(nèi)部排序方法可分五類：插入排序、選擇排序、交換排序、歸并排序和分配排序。評(píng)價(jià)排序算法好壞的標(biāo)準(zhǔn)主要有兩條：執(zhí)行時(shí)間和所需的輔助空間，另外算法的復(fù)雜程序也是要考慮的一個(gè)因素。*插入排序：直接插入排序：

24、 逐個(gè)向前插入到合適位置。哨兵(監(jiān)視哨)有兩個(gè)作用： 作為臨變量存放ri是在查找循環(huán)中用來(lái)監(jiān)視下標(biāo)變量j是否越界。直接插入排序是就地的穩(wěn)定排序。時(shí)間復(fù)雜度為o(n2)，比較次數(shù)為(n+2)(n-1)/2；移動(dòng)次數(shù)為(n+4)(n-1)/2；希爾排序： 等間隔的數(shù)據(jù)比較并按要求順序排列，最后間隔為1。希爾排序是就地的不穩(wěn)定排序。時(shí)間復(fù)雜度為o(n1.25)，比較次數(shù)為(n1.25)；移動(dòng)次數(shù)為(1.6n1.25)；交換排序：冒泡排序：自下向上確定最輕的一個(gè)。自上向下確定最重的一個(gè)。自下向上確定最輕的一個(gè)，后自上向下確定最重的一個(gè)。冒泡排序是就地的穩(wěn)定排序。時(shí)間復(fù)雜度為o(n2)，比較次數(shù)為n(n

25、-1)/2；移動(dòng)次數(shù)為3n(n-1)/2；快速排序：以第一個(gè)元素為參考基準(zhǔn)，設(shè)定、動(dòng)兩個(gè)指針，發(fā)生交換后指針交換位置，直到指針重合。重復(fù)直到排序完成?？焖倥判蚴欠蔷偷氐牟环€(wěn)定排序。時(shí)間復(fù)雜度為o(nlog2n)，比較次數(shù)為n(n-1)/2；選擇排序：直接選擇排序：選擇最小的放在比較區(qū)前。直接選擇排序就地的不穩(wěn)定排序。時(shí)間復(fù)雜度為o(n2)。比較次數(shù)為n(n-1)/2；堆排序：建堆：按層次將數(shù)據(jù)填入完全二叉樹，從int(n/2)處向前逐個(gè)調(diào)整位置。然后將樹根與最后一個(gè)葉子交換值并斷開與樹的連接并重建堆，直到全斷開。堆排序是就地不穩(wěn)定的排序，時(shí)間復(fù)雜度為o(nlog2n)，不適宜于記錄數(shù)較少的文件

26、。基本思路：從下往上，調(diào)小到根，遇到交換，記得檢驗(yàn)。降序 從下往上，調(diào)大到根，遇到交換，記得檢驗(yàn)。升序該思路為建堆基本思路?！玖?xí)題】49 38 65 97 76 13 27 歸并排序：先兩個(gè)一組排序，形成(n+1)/2組，再將兩組并一組，直到剩下一組為止。歸并排序是非就地穩(wěn)定排序，時(shí)間復(fù)雜度是o(nlog2n)。分配排序：箱排序：按關(guān)鍵字的取值范圍確定箱子數(shù)，按關(guān)鍵字投入箱子，鏈接所有非空箱。箱排序的平均時(shí)間復(fù)雜度是線性的o(n)?；鶖?shù)排序：從低位到高位依次對(duì)關(guān)鍵字進(jìn)行箱排序?；鶖?shù)排序是非就穩(wěn)定的排序，時(shí)間復(fù)雜度是o(d*n+d*rd)。各種排序方法的比較和選擇： 待排序的記錄數(shù)目n；n較大的

27、要用時(shí)間復(fù)雜度為o(nlog2n)的。第九章 查找*查找的同時(shí)對(duì)表做修改操作(如插入或刪除)則相應(yīng)的表稱之為動(dòng)態(tài)查找表，否則稱之為靜態(tài)查找表。衡量查找算法效率優(yōu)劣的標(biāo)準(zhǔn)是在查找過程中對(duì)關(guān)鍵字需要執(zhí)行的平均比較次數(shù)(即平均查找長(zhǎng)度asl).*線性表查找的方法： 順序查找：逐個(gè)查找，asl=(n+1)/2；二分查找：取中點(diǎn)int(n/2)比較,若小就比左區(qū)間，大就比右區(qū)間。用二叉判定樹表示。asl=（每層結(jié)點(diǎn)數(shù)*層數(shù)）/n。分塊查找。要求“分塊有序”，將表分成若干塊內(nèi)部不一定有序，并抽取各塊中的最大關(guān)鍵字及其位置建立有序索引表。*二叉排序樹(bst)定義是：二叉排序樹是空樹或者滿足如下性質(zhì)的二叉樹

28、： 若它的左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；若它的右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；左、右子樹本身又是一棵二叉排序樹。二叉排序樹的插入、建立、刪除的算法平均時(shí)間性能是o(nlog2n)。二叉排序樹的刪除操作可分三種情況進(jìn)行處理： *p是葉子，則直接刪除*p，即將*p的雙親*parent中指向*p的指針域置空即可。*p只有一個(gè)孩子*child,此時(shí)只需將*child和*p的雙親直接連接就可刪去*p。*p有兩個(gè)孩子,則先將*p結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)的數(shù)據(jù)到*p，刪除中序后繼結(jié)點(diǎn)。*關(guān)于b-樹(多路平衡查找樹)。它適合在磁盤等直接存取設(shè)備上組織動(dòng)態(tài)的查找表，是一種外查

29、找算法。建立的方式是從下向上拱起。*散列技術(shù)：將結(jié)點(diǎn)按其關(guān)鍵字的散列地址存儲(chǔ)到散列表的過程稱為散列。散列函數(shù)的選擇有兩條標(biāo)準(zhǔn)：簡(jiǎn)單和均勻。常見的散列函數(shù)構(gòu)的造方法： .平方取中法：hash=int(x2)%100).除余法：表長(zhǎng)為m，hash=x%m.相乘取整法：hash=int(m*(x*a-int(x*a)；a=0.618.隨機(jī)數(shù)法：hash=random(x)。*處理沖突的方法：開放定址法：一般形式為hi=(h(key)+di)%m1im-1，開放定址法要求散列表的裝填因子1。開放定址法類型： 線性探查法：address=(hash(x)+i)%m；二次探查法：address=(hash

30、(x)+i2)%m；雙重散列法：address=(hash(x)+i*hash(y)%m；拉鏈法：是將所有關(guān)鍵字為同義詞的結(jié)點(diǎn)鏈接在同一個(gè)單鏈表中。拉鏈法的優(yōu)點(diǎn)： 拉鏈法處理沖突簡(jiǎn)單，且無(wú)堆積現(xiàn)象；鏈表上的結(jié)點(diǎn)空間是動(dòng)態(tài)申請(qǐng)的適于無(wú)法確定表長(zhǎng)的情況；拉鏈法中可以大于1，結(jié)點(diǎn)較大時(shí)其指針域可忽略，因此節(jié)省空間；拉鏈法構(gòu)造的散列表刪除結(jié)點(diǎn)易實(shí)現(xiàn)。拉鏈法也有缺點(diǎn)：當(dāng)結(jié)點(diǎn)規(guī)模較小時(shí)，用拉鏈法中的指針域也要占用額外空間，還是開放定址法省空間。第十章 文件*文件是性質(zhì)相同的記錄的集合。記錄是文件中存取的基本單位，數(shù)據(jù)項(xiàng)是文件可使用的最小單位，數(shù)據(jù)項(xiàng)有時(shí)稱字段或者屬性。文件邏輯結(jié)構(gòu)是一種線性結(jié)構(gòu)。操作有：檢

31、索和維護(hù)。并有實(shí)時(shí)和批量處理兩種處理方式。文件存儲(chǔ)結(jié)構(gòu)是指文件在外存上的組織方式?；镜慕M織方式有：順序組織、索引組織、散列組織和鏈組織。常用的文件組織方式：順序文件、索引文件、散列文件和多關(guān)鍵字文件。評(píng)價(jià)一個(gè)文件組織的效率，是執(zhí)行文件操作所花費(fèi)的時(shí)間和文件組織所需的存儲(chǔ)空間。檢索功能的多寡和速度的快慢，是衡量文件操作質(zhì)量的重要標(biāo)志。*順序文件是指按記錄進(jìn)入文件的先后順序存放、其邏輯順序和物理順序一致的文件。主關(guān)鍵字有序稱順序有序文件，否則稱順序無(wú)序文件。一切存儲(chǔ)在順序存儲(chǔ)器(如磁帶)上的文件都只能順序文件，只能按順序查找法存取。順序文件的插入、刪除和修改只能通過復(fù)制整個(gè)文件實(shí)現(xiàn)。*索引文件的

32、組織方式：通常是在主文件之外建立一張索引表指明邏輯記錄和物理記錄之間一一對(duì)應(yīng)的關(guān)系，它和主文件一起構(gòu)成索引文件。索引非順序文件中的索引表為稠密索引。索引順序文件中的索引表為稀疏索引。若記錄很大使得索引表也很大時(shí)，可對(duì)索引表再建立索引，稱為查找表。是一種靜態(tài)索引。索引順序文件常用的有兩種：isam索引順序存取方法：是專為磁盤存取文件設(shè)計(jì)的，采用靜態(tài)索引結(jié)構(gòu)。vsam虛擬存儲(chǔ)存取方法：采用b+樹作為動(dòng)態(tài)索引結(jié)構(gòu)，由索引集、順序集、數(shù)據(jù)集組成。*散列文件是利用散列存儲(chǔ)方式組織的文件，亦稱為直接存取文件。散列文件優(yōu)點(diǎn)是：文件隨機(jī)存放，記錄不需要排序；插入刪除方便；存取速度快；不需要索引區(qū)，節(jié)省存儲(chǔ)空間

33、。缺點(diǎn)是：不能進(jìn)行順序存取，只能按關(guān)鍵字隨機(jī)存取，且詢問方式限地簡(jiǎn)單詢問，需要重新組織文件。*多重表文件：對(duì)需要查詢的次關(guān)鍵字建立相應(yīng)的索引，對(duì)相同次關(guān)鍵字的記錄建一個(gè)鏈表并將鏈表頭指針、長(zhǎng)度、次關(guān)鍵字作為索引表的索引項(xiàng)。倒排表：次關(guān)鍵字索引表稱倒排表，主文件和倒排表構(gòu)成倒排文件。第二部分 計(jì)算機(jī)組成原理第1章 概論 一、名詞解釋：歷年真題：名詞解釋題：（2002）1.主機(jī)：由cpu、存儲(chǔ)器與i/o接口合在一起構(gòu)成的處理系統(tǒng)稱為主機(jī)。（2003）16.主機(jī)：由cpu、存儲(chǔ)器與i/o接口合在一起構(gòu)成的處理系統(tǒng)稱為主機(jī)。（2004）18.alu算術(shù)邏輯運(yùn)算單元，負(fù)責(zé)執(zhí)行各種算術(shù)運(yùn)算和邏輯運(yùn)算。（2

34、005）21.應(yīng)用軟件：完成應(yīng)用功能的軟件，專門為解決某個(gè)應(yīng)用領(lǐng)域中的具體任務(wù)而編寫。 近4年都考了名稱解釋，所以第一章的名稱解釋是考試的重點(diǎn)，這里給大家列出了名詞解釋大家要熟悉一下，這都是本章的基本概念，也有利于做選擇題及填空題。1.主機(jī)：由cpu、存儲(chǔ)器與i/o接口合在一起構(gòu)成的處理系統(tǒng)稱為主機(jī)。2.cpu：中央處理器，是計(jì)算機(jī)的核心部件，由運(yùn)算器和控制器構(gòu)成。3.運(yùn)算器：計(jì)算機(jī)中完成運(yùn)算功能的部件，由alu和寄存器構(gòu)成。4.alu：算術(shù)邏輯運(yùn)算單元，負(fù)責(zé)執(zhí)行各種算術(shù)運(yùn)算和邏輯運(yùn)算。5.外圍設(shè)備：計(jì)算機(jī)的輸入輸出設(shè)備，包括輸入設(shè)備，輸出設(shè)備和外存儲(chǔ)設(shè)備。6.數(shù)據(jù)：編碼形式的各種信息，在計(jì)算

35、機(jī)中作為程序的操作對(duì)象。7.指令：是一種經(jīng)過編碼的操作命令，它指定需要進(jìn)行的操作，支配計(jì)算機(jī)中的信息傳遞以及主機(jī)與輸入輸出設(shè)備之間的信息傳遞，是構(gòu)成計(jì)算機(jī)軟件的基本元素。8.透明：在計(jì)算機(jī)中，從某個(gè)角度看不到的特性稱該特性是透明的。9.位：計(jì)算機(jī)中的一個(gè)二進(jìn)制數(shù)據(jù)代碼，計(jì)算機(jī)中數(shù)據(jù)的最小表示單位。10.字：數(shù)據(jù)運(yùn)算和存儲(chǔ)的單位，其位數(shù)取決于具體的計(jì)算機(jī)。11.字節(jié)：衡量數(shù)據(jù)量以及存儲(chǔ)容量的基本單位。1字節(jié)等于8位二進(jìn)制信息。12.字長(zhǎng)：一個(gè)數(shù)據(jù)字中包含的位數(shù)，反應(yīng)了計(jì)算機(jī)并行計(jì)算的能力。一般為8位、16位、32位或64位。13.地址：給主存器中不同的存儲(chǔ)位置指定的一個(gè)二進(jìn)制編號(hào)。14.存儲(chǔ)器：

36、計(jì)算機(jī)中存儲(chǔ)程序和數(shù)據(jù)的部件，分為內(nèi)存和外存。15.總線：計(jì)算機(jī)中連接功能單元的公共線路，是一束信號(hào)線的集合，包括數(shù)據(jù)總線.地址總線和控制總線。16.硬件：由物理元器件構(gòu)成的系統(tǒng)，計(jì)算機(jī)硬件是一個(gè)能夠執(zhí)行指令的設(shè)備。17.軟件：由程序構(gòu)成的系統(tǒng)，分為系統(tǒng)軟件和應(yīng)用軟件。18.兼容：計(jì)算機(jī)部件的通用性。19.軟件兼容：一個(gè)計(jì)算機(jī)系統(tǒng)上的軟件能在另一個(gè)計(jì)算機(jī)系統(tǒng)上運(yùn)行，并得到相同的結(jié)果，則稱這兩個(gè)計(jì)算機(jī)系統(tǒng)是軟件兼容的。20.程序：完成某種功能的指令序列。21.寄存器：是運(yùn)算器中若干個(gè)臨時(shí)存放數(shù)據(jù)的部件，由觸發(fā)器構(gòu)成，用于存儲(chǔ)最頻繁使用的數(shù)據(jù)。22.容量：是衡量容納信息能力的指標(biāo)。23.主存：一般

37、采用半導(dǎo)體存儲(chǔ)器件實(shí)現(xiàn)，速度較高.成本高且當(dāng)電源斷開時(shí)存儲(chǔ)器的內(nèi)容會(huì)丟失。24.輔存：一般通過輸入輸出部件連接到主存儲(chǔ)器的外圍設(shè)備，成本低，存儲(chǔ)時(shí)間長(zhǎng)。25.操作系統(tǒng)：主要的系統(tǒng)軟件，控制其它程序的運(yùn)行，管理系統(tǒng)資源并且為用戶提供操作界面。26.匯編程序：將匯編語(yǔ)言程序翻譯成機(jī)器語(yǔ)言程序的計(jì)算機(jī)軟件。27.匯編語(yǔ)言：采用文字方式（助記符）表示的程序設(shè)計(jì)語(yǔ)言，其中大部分指令和機(jī)器語(yǔ)言中的指令一一對(duì)應(yīng)，但不能被計(jì)算機(jī)的硬件直接識(shí)別。28.編譯程序：將高級(jí)語(yǔ)言程序轉(zhuǎn)換成機(jī)器語(yǔ)言程序的計(jì)算機(jī)軟件。29.解釋程序：解釋執(zhí)行高級(jí)語(yǔ)言程序的計(jì)算機(jī)軟件，解釋并立即執(zhí)行源程序的語(yǔ)句。30.系統(tǒng)軟件：計(jì)算機(jī)系統(tǒng)的

38、一部分，進(jìn)行命令解釋、操作管理、系統(tǒng)維護(hù)、網(wǎng)絡(luò)通信、軟件開發(fā)和輸入輸出管理的軟件，與具體的應(yīng)用領(lǐng)域無(wú)關(guān)。31.應(yīng)用軟件：完成應(yīng)用功能的軟件，專門為解決某個(gè)應(yīng)用領(lǐng)域中的具體任務(wù)而編寫。32.指令流：在計(jì)算機(jī)的存儲(chǔ)器與cpu之間形成的不斷傳遞的指令序列。從存儲(chǔ)器流向控制器。33.數(shù)據(jù)流：在計(jì)算機(jī)的存儲(chǔ)器與cpu之間形成的不斷傳遞的數(shù)據(jù)序列。存在于運(yùn)算器與存儲(chǔ)器以及輸入輸出設(shè)備之間。34.接口：計(jì)算機(jī)主機(jī)與外圍設(shè)備之間傳遞數(shù)據(jù)與控制信息的電路。計(jì)算機(jī)可以與多種不同的外圍設(shè)備連接，因而需要有多種不同的輸入輸出接口。 【選擇題沒有考過】二、填空題：（2000年）系統(tǒng)軟件主要包括：和及診斷程序等。操作系統(tǒng)

39、語(yǔ)言處理程序 （2005年）18.構(gòu)成中央處理器的兩大部件是和。運(yùn)算器控制器 三、改錯(cuò)題：（2000年）1.運(yùn)算器的功能就是執(zhí)行加、減、乘、除四則運(yùn)算。運(yùn)算器的功能就是算術(shù)運(yùn)算和邏輯運(yùn)算 （2005年）18.構(gòu)成中央處理器的兩大部件是和。硬盤的存儲(chǔ)容量常用 gb 表示，1gb=1024mb 三、數(shù)據(jù)編碼：定點(diǎn)數(shù)編碼：（2000年）2.如果x為負(fù)數(shù)，由x補(bǔ)求-x補(bǔ)是將（）。a.x補(bǔ)各值保持不變b.x補(bǔ)符號(hào)位變反，其它各位不變c.x補(bǔ)除符號(hào)位外，各位變反，未位加1d.x補(bǔ)連同符號(hào)位一起各位變反，未位加1 【分析】：不論x是正數(shù)還是負(fù)數(shù)，由x補(bǔ)求-x補(bǔ)的方法是對(duì)x補(bǔ)求補(bǔ)，即連同符號(hào)位一起按位取反，末

40、位加1。【答案】：d （2001年）2.若x補(bǔ) =0.1101010 ，則 x 原=（ ）。 a.1.0010101b.1.0010110c.0.0010110d.0.1101010 【分析】：正數(shù)的補(bǔ)碼與原碼相同，負(fù)數(shù)的補(bǔ)碼是用正數(shù)的補(bǔ)碼按位取反，末位加1求得。此題中x補(bǔ)為正數(shù)，則x原與x補(bǔ)相同?！敬鸢浮浚篸 （2002年）2.若x=1011,則x補(bǔ)=( )。a.01011b.1011 c.0101 d.10101【分析】：x為正數(shù)，符號(hào)位為0,數(shù)值位與原碼相同，結(jié)果為01011?！敬鸢浮浚篴 （2003年）8.若x補(bǔ)=1.1011 ，則真值 x 是（）。a.-0.1011b.-0.0101

41、c.0.1011 d.0.0101 【分析】：x補(bǔ)=1.1011，其符號(hào)位為1，真值為負(fù)；真值絕對(duì)值可由其補(bǔ)碼經(jīng)求補(bǔ)運(yùn)算得到，即按位取后得0.0100再末位加1得0.0101，故其真值為-0.0101?！敬鸢浮浚篵 （2004年）13.設(shè)有二進(jìn)制數(shù) x=1101110，若采用 8 位二進(jìn)制數(shù)表示，則x補(bǔ)（）。 a.11101101b.10010011c.00010011d.10010010 【分析】：x=1101110為負(fù)數(shù)，負(fù)數(shù)的補(bǔ)碼是將二進(jìn)制位按位取反后在最低位上加1，故x 補(bǔ) =10010010?！敬鸢浮浚篸 （2005年）1.若x補(bǔ)=0.1011，則真值x=（）。a.0.1011 b.

42、0.0101 c.1.1011 d.1.0101【分析】：x補(bǔ)=0.1011，其符號(hào)位為0，真值為正；真值就是0.1011?！敬鸢浮浚篴 由上可見，有關(guān)補(bǔ)碼每年都考。同學(xué)也要注意一下移碼。（2001）3.若定點(diǎn)整數(shù) 64 位，含 1 位符號(hào)位，補(bǔ)碼表示，則所能表示的絕對(duì)值最大負(fù)數(shù)為（）。a.-264 b.-（264-1 ）c.-263 d.-（263-1）【分析】：字長(zhǎng)為64位，符號(hào)位為1位，則數(shù)值位為63位。當(dāng)表示負(fù)數(shù)時(shí)，數(shù)值位全0為負(fù)絕對(duì)值最大，為-263?！敬鸢浮浚篶（2002年）3.某機(jī)字長(zhǎng)8位，含一位數(shù)符，采用原碼表示，則定點(diǎn)小數(shù)所能表示的非零最小正數(shù)為（）a.2-9b.2-8c.1

43、- d.2-7 【分析】：求最小的非零正數(shù)，符號(hào)位為0,數(shù)值位取非0中的原碼最小值，此8位數(shù)據(jù)編碼為：00000001，表示的值是：2-7?！敬鸢浮浚篸第3章 存儲(chǔ)系統(tǒng)一、名詞解釋：歷年真題：（2001年）2.dram：動(dòng)態(tài)隨機(jī)訪問存儲(chǔ)器，利用電容電荷存儲(chǔ)信息。（2001年）6.邏輯地址：程序員編程所用的地址以及cpu通過指令訪問主存時(shí)所產(chǎn)生的地址。（2001年）10.隨機(jī)存取方式：可按地址訪問存儲(chǔ)器任一編址單元，其訪問時(shí)間相同且與地址無(wú)關(guān)。六年以來(lái)就考了這3個(gè)名稱解釋，而且近4年都沒有考，所以第三章的名稱解釋不是考試的重點(diǎn)，這里給大家列出了名詞解釋大家要熟悉一下，這都是本章的基本概念，有利于做選擇題及填空題。1.ram：隨機(jī)訪問存儲(chǔ)器，能夠快速方便的訪問地址中的內(nèi)容，訪問的速度與存儲(chǔ)位置無(wú)關(guān)。2.rom：只讀存儲(chǔ)器，一種只能讀取數(shù)據(jù)不能寫入數(shù)據(jù)的存儲(chǔ)器。3.sram：靜態(tài)隨機(jī)訪