全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)教程

1、全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)第 1頁(yè)全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí) C+語(yǔ)言程序設(shè)計(jì)考試大綱(2013 年版)基本要求1.掌握 C+語(yǔ)言的基本語(yǔ)法規(guī)則。2.熟練掌握有關(guān)類(lèi)與對(duì)象的相關(guān)知識(shí)。3.能夠閱讀和分析 C+程序。4.能夠采用面向?qū)ο蟮木幊趟悸泛头椒ň帉?xiě)應(yīng)用程序。5.能熟練使用 VisualC+6.0 集成開(kāi)發(fā)環(huán)境編寫(xiě)和調(diào)試程序。考試內(nèi)容一、C+語(yǔ)言概述1.了解 C+語(yǔ)言的基本符號(hào)。2.了解 C+語(yǔ)言的詞匯(關(guān)鍵字、 標(biāo)識(shí)符、常量、運(yùn)算符、標(biāo)點(diǎn)符號(hào)等)。3.掌握 C+程序的基本框架。4.能夠使用 VisualC+6.0 集成開(kāi)發(fā)環(huán)境編輯、編譯、運(yùn)行與調(diào)試程序。二、數(shù)據(jù)類(lèi)型、表達(dá)式和基本運(yùn)算1

2、.掌握 C+數(shù)據(jù)類(lèi)型(基本類(lèi)型,指針類(lèi)型)及其定義方法。2.了解 C+的常量定義(整型常量,字符常量,邏輯常量,實(shí)型常量,地址常量,符號(hào)常量)。3.掌握變量的定義與使用方法(變量的定義及初始化,全局變量,局部變量)。4.掌握 C+運(yùn)算符的種類(lèi)、運(yùn)算優(yōu)先級(jí)和結(jié)合性。5.熟練掌握 C+表達(dá)式類(lèi)型及求值規(guī)則(賦值運(yùn)算,算術(shù)運(yùn)算符和算術(shù)表達(dá)式,關(guān)系運(yùn)算符和關(guān)系表達(dá)式,邏輯運(yùn)算符和邏輯表達(dá)式,條件運(yùn)算,指針運(yùn)算,逗號(hào)表達(dá)式)。二級(jí)各科目考試的公共基礎(chǔ)知識(shí)考試大綱及樣題見(jiàn)高等教育出版社出版的 全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)教程公共基礎(chǔ)知識(shí)(2013 年版)附錄部分。三、C+的基本語(yǔ)句1.掌握 C+的基本語(yǔ)句,例如

3、賦值語(yǔ)句、表達(dá)式語(yǔ)句、復(fù)合語(yǔ)句、輸入、輸出語(yǔ)句和空語(yǔ)句等。2.用 if語(yǔ)句實(shí)現(xiàn)分支結(jié)構(gòu)。3.用 switch 語(yǔ)句實(shí)現(xiàn)多分支選擇結(jié)構(gòu)。4.用 for語(yǔ)句實(shí)現(xiàn)循環(huán)結(jié)構(gòu)。5.用 while 語(yǔ)句實(shí)現(xiàn)循環(huán)結(jié)構(gòu)。6.用 do.while 語(yǔ)句實(shí)現(xiàn)循環(huán)結(jié)構(gòu)。7.轉(zhuǎn)向語(yǔ)句(goto,continue,break和 return)。8.掌握分支語(yǔ)句和循環(huán)語(yǔ)句的各種嵌套使用。四、數(shù)組、指針與引用1.掌握一維數(shù)組的定義、 初始化和訪(fǎng)問(wèn),了解多維數(shù)組的定義、初始化和訪(fǎng)問(wèn)。2.了解字符串與字符數(shù)組。3.熟練掌握常用字符串函數(shù)(strlen,strcpy,strcat,strcmp,strstr等)。4.指針與指針變

4、量的概念,指針與地址運(yùn)算符,指針與數(shù)組。5.引用的基本概念,引用的定義與使用。五、掌握函數(shù)的有關(guān)使用1.函數(shù)的定義方法和調(diào)用方法。2.函數(shù)的類(lèi)型和返回值。3.形式參數(shù)與實(shí)際參數(shù),參數(shù)值的傳遞。4.變量的作用域和生存周期。5.遞歸函數(shù)。6.函數(shù)重載。7.內(nèi)聯(lián)函數(shù)。8.帶有默認(rèn)參數(shù)值的函數(shù)。六、熟練掌握類(lèi)與對(duì)象的相關(guān)知識(shí)1.類(lèi)的定義方式、數(shù)據(jù)成員、成員函數(shù)及訪(fǎng)問(wèn)權(quán)限(public,private,protected)。2.對(duì)象和對(duì)象指針的定義與使用。3.構(gòu)造函數(shù)與析構(gòu)函數(shù)。4.靜態(tài)數(shù)據(jù)成員與靜態(tài)成員函數(shù)的定義與使用方式。5.常數(shù)據(jù)成員與常成員函數(shù)。6.this 指針的使用。7.友元函數(shù)和友元類(lèi)。8

5、.對(duì)象數(shù)組與成員對(duì)象。七、掌握類(lèi)的繼承與派生知識(shí)1.派生類(lèi)的定義和訪(fǎng)問(wèn)權(quán)限。全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)第 2頁(yè)2.繼承基類(lèi)的數(shù)據(jù)成員與成員函數(shù)。3.基類(lèi)指針與派生類(lèi)指針的使用。4.虛基類(lèi)。5.子類(lèi)型關(guān)系。八、了解多態(tài)性概念1.虛函數(shù)機(jī)制的要點(diǎn)。2.純虛函數(shù)與抽象基類(lèi),虛函數(shù)。3.了解運(yùn)算符重載。九、模板1.簡(jiǎn)單了解函數(shù)模板的定義和使用方式。2.簡(jiǎn)單了解類(lèi)模板的定義和使用方式。十、輸入輸出流1.掌握 C+流的概念。2.能夠使用格式控制數(shù)據(jù)的輸入輸出。3.掌握文件的 I/O 操作?？荚嚪绞缴蠙C(jī)考試,考試時(shí)長(zhǎng) 120 分鐘,滿(mǎn)分 100分。1.題型及分值單項(xiàng)選擇題40分(含公共基礎(chǔ)知識(shí)部分1

6、0 分)、操作題 60 分(包括基本操作題、簡(jiǎn)單應(yīng)用題及綜合應(yīng)用題)。2.考試環(huán)境VisualC+6.0。全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)第 3頁(yè)目錄目錄二 級(jí) 公 共 基 礎(chǔ) 知 識(shí) 考綱 1第 一 章數(shù) 據(jù) 結(jié) 構(gòu) 與 算法2第 二 章程 序 設(shè) 計(jì) 基礎(chǔ)19第 三 章軟 件 工 程 基礎(chǔ)23第 四 章數(shù) 據(jù) 庫(kù) 設(shè) 計(jì) 基礎(chǔ)32全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)考綱考試內(nèi)容一、 基本數(shù)據(jù)結(jié)構(gòu)與算法1.算法的基本概念；算法復(fù)雜度的概念和意義（時(shí)間復(fù)雜度與空間復(fù)雜度） 。2.數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)； 數(shù)據(jù)結(jié)構(gòu)的圖形表示；線(xiàn)性結(jié)構(gòu)與非線(xiàn)性結(jié)構(gòu)的概念。3.線(xiàn)性表的定義；線(xiàn)性表

7、的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除運(yùn)算。4.棧和隊(duì)列的定義；棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算。5.線(xiàn)性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。6.樹(shù)的基本概念；二叉樹(shù)的定義及其存儲(chǔ)結(jié)構(gòu)；二叉樹(shù)的前序、中序和后序遍歷。7.順序查找與二分法查找算法；基本排序算法（交換類(lèi)排序，選擇類(lèi)排序，插入類(lèi)排序） 。二、 程序設(shè)計(jì)基礎(chǔ)1.程序設(shè)計(jì)方法與風(fēng)格。2.結(jié)構(gòu)化程序設(shè)計(jì)。3.面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，對(duì)象，方法，屬性及繼承與多態(tài)性。三、 軟件工程基礎(chǔ)1.軟件工程基本概念，軟件生命周戎概念，軟件工具與軟件開(kāi)發(fā)環(huán)境。2.結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說(shuō)明書(shū)。3.結(jié)構(gòu)化設(shè)計(jì)方法，總體設(shè)計(jì)與詳細(xì)

8、設(shè)計(jì)。4.軟件測(cè)試的方法，白盒測(cè)試與黑盒測(cè)試，測(cè)試用例設(shè)計(jì)，軟件測(cè)試的實(shí)施，單元測(cè)試、集成測(cè)試和系統(tǒng)測(cè)試。5.程序的調(diào)試， 靜態(tài)調(diào)試與動(dòng)態(tài)調(diào)試。四、 數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)1.數(shù)據(jù)庫(kù)的基本概念：數(shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)管理系統(tǒng)，數(shù)據(jù)庫(kù)系統(tǒng)。2.數(shù)據(jù)模型， 實(shí)體聯(lián)系模型及 E-R 圖，從 E-R 圖導(dǎo)出關(guān)系數(shù)據(jù)模型。3.關(guān)系代數(shù)運(yùn)算，包括集合運(yùn)算及選擇、投影、連接運(yùn)算，數(shù)據(jù)庫(kù)規(guī)范化理論。4.數(shù)據(jù)庫(kù)設(shè)計(jì)方法和步驟： 需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)策略。考試方式公共基礎(chǔ)的考試方式為筆試，與 C語(yǔ)言 （VisualBASIC、 Visual FoxPro、Java、Access、Visual C+）的筆試

9、部分合為一張?jiān)嚲怼?公共基礎(chǔ)部分占全卷的 30 分。公共基礎(chǔ)知識(shí)有10 道選擇題和 5 道填空題。第一章 數(shù)據(jù)結(jié)構(gòu)與算法一、內(nèi)容要點(diǎn)（一）算法1算法的基本概念算法是指解題方案的準(zhǔn)確而完整的描述。即是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)第 4頁(yè)并且每一個(gè)規(guī)則都是有效的，且是明確的，沒(méi)有二義性， 同時(shí)該規(guī)則將在有限次運(yùn)算后可終止。1）算法的基本特征（1）可行性由于算法的設(shè)計(jì)是為了在某一個(gè)特定的計(jì)算工具上解決某一個(gè)實(shí)際的問(wèn)題而設(shè)計(jì)的，因此，它總是受到計(jì)算工具的限制，使執(zhí)行產(chǎn)生偏差。如：計(jì)算機(jī)的數(shù)值有效位是有限的，當(dāng)大數(shù)和小數(shù)進(jìn)行運(yùn)算時(shí)， 往往會(huì)因?yàn)橛行粩?shù)的影響而使小數(shù)丟

10、失，因此，在算法設(shè)計(jì)時(shí)，應(yīng)該考慮到這一點(diǎn)。（2）確定性算法的設(shè)計(jì)必須是每一個(gè)步驟都有明確的定義，不允許有模糊的解釋?zhuān)膊荒苡卸嗔x性。例如，一個(gè)實(shí)際的問(wèn)題，小寶和萍萍共有 12 個(gè)蘋(píng)果，小寶比萍萍多 4 個(gè)，請(qǐng)問(wèn)小寶和萍萍各有幾個(gè)蘋(píng)果？這個(gè)問(wèn)題， 我們可以立一個(gè)方程412yxyx來(lái)求解， 要求x 和 y 的值，公式是正確的，但如何讓計(jì)算能夠進(jìn)行計(jì)算， 我們的算法不能把公式直接輸進(jìn)去，而應(yīng)該設(shè)計(jì)出解題的步驟和過(guò)程。即設(shè)計(jì)的算法是計(jì)算工具所能夠正常解決問(wèn)題的過(guò)程。（3）有窮性算法的有窮性， 即在一定的時(shí)間是能夠完成的， 即算法應(yīng)該在計(jì)算有限個(gè)步驟后能夠正常結(jié)束。例如，在數(shù)學(xué)中的無(wú)窮級(jí)數(shù)，在計(jì)算機(jī)中只

11、能求有限項(xiàng)，即計(jì)算的過(guò)程是有窮的。（4）擁有足夠的情報(bào)算法的執(zhí)行與輸入的數(shù)據(jù)和提供的初始條件相關(guān)， 不同的輸入或初始條件會(huì)有不同的輸出結(jié)果，提供準(zhǔn)確的初始條件和數(shù)據(jù)，才能使算法正確執(zhí)行。2）算法的基本要素一是數(shù)據(jù)對(duì)象的運(yùn)算和操作， 二是算法的控制結(jié)構(gòu)。（1）算法中對(duì)數(shù)據(jù)的運(yùn)算和操作算法實(shí)際上是按解題要求從環(huán)境能進(jìn)行的所有操作中選擇合適的操作所組成的一組指令序列。 即算法是計(jì)算機(jī)所能夠處理的操作所組成的指令序列。（2）算法的控制結(jié)構(gòu)算法的功能不僅取決于所選用的操作，而且還與各操作之間的順序有關(guān)。在算法中， 操作的執(zhí)行順序又稱(chēng)算法的控制結(jié)構(gòu)，一般的算法控制結(jié)構(gòu)有三種：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。

12、在算法描述是， 有相關(guān)的工具對(duì)這三種結(jié)構(gòu)進(jìn)行描述， 常用的描述工具有： 流程圖、N-S 結(jié)構(gòu)圖和算法描述語(yǔ)言等。3）算法設(shè)計(jì)的基本方法為用計(jì)算機(jī)解決實(shí)際問(wèn)題而設(shè)計(jì)的算法，即是計(jì)算機(jī)算法。通常的算法設(shè)計(jì)有如下幾種：（1）列舉法列舉法的基本思想是，根據(jù)提出的問(wèn)題，列舉出所有可能的情況，并用問(wèn)題中給定的條件檢驗(yàn)?zāi)男┦菨M(mǎn)足條件的， 哪些是不滿(mǎn)足條件的。列舉法通常用于解決“是否存在”或“有哪些可能”等問(wèn)題。例如，我國(guó)古代的趣味數(shù)學(xué)題： “百錢(qián)買(mǎi)百雞” 、 “雞兔同籠”等，均可采用列舉法進(jìn)行解決。使用列舉法時(shí)， 要對(duì)問(wèn)題進(jìn)行詳細(xì)的分析，將與問(wèn)題有關(guān)的知識(shí)條理化、完備化、系統(tǒng)化，從中找出規(guī)律。（2）歸納法歸

13、納法的基本思想是， 通過(guò)列舉少量的特殊情況， 經(jīng)過(guò)分析， 最后找出一般的關(guān)系。歸納是一種抽象， 即從特殊現(xiàn)象中找出一般規(guī)律。 但由于在歸納法中不可能對(duì)所有的情況進(jìn)行列舉，因此，該方法得到的結(jié)論只是一種猜測(cè)，還需要進(jìn)行證明。（3）遞推遞推，即是從已知的初始條件出發(fā)，逐次推出所要求的各個(gè)中間環(huán)節(jié)和最后結(jié)果。其中初始條件或問(wèn)題本身已經(jīng)給定， 或是通過(guò)對(duì)問(wèn)題的分析與化簡(jiǎn)而確定。遞推的本質(zhì)也是一種歸納， 遞推關(guān)系式全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)第 5頁(yè)通常是歸納的結(jié)果。例如，裴波那契數(shù)列，是采用遞推的方法解決問(wèn)題的。（4）遞歸在解決一些復(fù)雜問(wèn)題時(shí)， 為了降低問(wèn)題的復(fù)雜程序，通常是將問(wèn)題逐層分解，最后

14、歸結(jié)為一些最簡(jiǎn)單的問(wèn)題。 這種將問(wèn)題逐層分解的過(guò)程，并沒(méi)有對(duì)問(wèn)題進(jìn)行求解，而只是當(dāng)解決了最后的問(wèn)題那些最簡(jiǎn)單的問(wèn)題后，再沿著原來(lái)分解的逆過(guò)程逐步進(jìn)行綜合，這就是遞歸的方法。遞歸分為直接遞歸和間接遞歸兩種方法。如果一個(gè)算法直接調(diào)用自己，稱(chēng)為直接遞歸調(diào)用； 如果一個(gè)算法 A 調(diào)用另一個(gè)算法B， 而算法 B 又調(diào)用算法 A， 則此種遞歸稱(chēng)為間接遞歸調(diào)用。（5）減半遞推技術(shù)減半遞推即將問(wèn)題的規(guī)模減半，然后，重復(fù)相同的遞推操作。例如，一元二次方程的求解。（6）回溯法有些實(shí)際的問(wèn)題很難歸納出一組簡(jiǎn)單的遞推公式或直觀的求解步驟， 也不能使用無(wú)限的列舉。對(duì)于這類(lèi)問(wèn)題，只能采用試探的方法，通過(guò)對(duì)問(wèn)題的分析，找出

15、解決問(wèn)題的線(xiàn)索，然后沿著這個(gè)線(xiàn)索進(jìn)行試探，如果試探成功，就得到問(wèn)題的解，如果不成功，再逐步回退，換別的路線(xiàn)進(jìn)行試探。這種方法，即稱(chēng)為回溯法。如人工智能中的機(jī)器人下棋。2算法復(fù)雜度算法的復(fù)雜度包括時(shí)間復(fù)雜度和空間復(fù)雜度。1）時(shí)間復(fù)雜度即實(shí)現(xiàn)該算法需要的計(jì)算工作量。 算法的工作量用算法所執(zhí)行的基本運(yùn)算次數(shù)來(lái)計(jì)算。同一個(gè)問(wèn)題規(guī)模下， 如果算法執(zhí)行所需要的基本次數(shù)取決于某一特定輸入時(shí)， 可以用以下兩種方法來(lái)分析算法的工作量：算法工作量=f(n)（1）平均性態(tài)用各種特定輸入下的基本運(yùn)算次數(shù)的加權(quán)平均值來(lái)度量算法的工作量。設(shè) x 是某個(gè)可能輸入中的某個(gè)特定輸入，p(x)是 x 出現(xiàn)的概率，t(x)是算法在

16、輸入為 x 時(shí)所執(zhí)行的基本運(yùn)算次數(shù)， 則算法的平均性態(tài)定義為：nDxxtxpnA)()()(Dn表示當(dāng)規(guī)模為 n 時(shí)，算法執(zhí)行時(shí)所有可能輸入的集合。（2）最壞情況復(fù)雜度指在規(guī)模為 n 時(shí)， 算法所執(zhí)行的基本運(yùn)算的最大次數(shù)。它定義為：)(max)(xtnWnDx例如， 在具有 n 個(gè)元素的數(shù)列中搜索一個(gè)數(shù) x。平均性態(tài)：nqqnnqinqtpnAniinii)1 (2) 1()1 ()(111即該數(shù)在數(shù)列中任何位置出現(xiàn)的數(shù)列是相同的，也有可能不存在，存在的概率為q。如果有一半的機(jī)會(huì)存在，則概率 q 為1/2，平均性態(tài)：nnnnA43)211 (221) 1()(如果查找的元素一定在數(shù)列中， 則每

17、個(gè)數(shù)存在的概率即為 1，則平均性態(tài)為：221)(nnnA最壞情況分析： 即要查找的元素 X 在數(shù)列的最后或不在數(shù)列中，顯然，它的最壞情況復(fù)雜度為：nnitnWi11 |max)(全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)第 6頁(yè)2）算法的空間復(fù)雜度指要執(zhí)行該算法所需要的內(nèi)存空間。 算法所占用的內(nèi)存空間包括算法程序所占的空間、 輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及算法執(zhí)行過(guò)程中所需要的額外空間， 如執(zhí)行過(guò)程中工作單元以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲(chǔ)空間等。（二）數(shù)據(jù)結(jié)構(gòu)的基本概念1概念數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。它包括以下兩個(gè)方面：表示數(shù)據(jù)元素的信息表示各數(shù)據(jù)之間的前后件關(guān)系1）數(shù)據(jù)的邏輯結(jié)構(gòu)是

18、指反映數(shù)據(jù)元素之間的邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個(gè)要素：數(shù)據(jù)元素的集合，記作 D數(shù)據(jù)之間的前后件關(guān)系，記作 R則數(shù)據(jù)結(jié)構(gòu) B=（D，R）2）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱(chēng)為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)， 或數(shù)據(jù)的物理結(jié)構(gòu)。即數(shù)據(jù)存儲(chǔ)時(shí)， 不僅要存放數(shù)據(jù)元素的信息， 而且要存儲(chǔ)數(shù)據(jù)元素之間的前后件關(guān)系的信息。通常的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等存儲(chǔ)結(jié)構(gòu)。2數(shù)據(jù)結(jié)構(gòu)的圖形表示數(shù)據(jù)結(jié)構(gòu)的圖形表示有兩個(gè)元素：中間標(biāo)有元素值的方框表示數(shù)據(jù)元素，稱(chēng)為數(shù)據(jù)結(jié)點(diǎn)用有向線(xiàn)段表示數(shù)據(jù)元素之間的前后件關(guān)系， 即有向線(xiàn)段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)注意：在結(jié)構(gòu)圖中，沒(méi)有前件的結(jié)點(diǎn)稱(chēng)為根結(jié)點(diǎn)，沒(méi)有后

19、件的結(jié)點(diǎn)稱(chēng)為終端結(jié)點(diǎn)，也稱(chēng)葉子結(jié)點(diǎn)。3線(xiàn)性結(jié)構(gòu)與非線(xiàn)性結(jié)構(gòu)如果一個(gè)數(shù)據(jù)元素都沒(méi)有， 該數(shù)據(jù)結(jié)構(gòu)稱(chēng)為空數(shù)據(jù)結(jié)構(gòu)； 在空數(shù)據(jù)結(jié)構(gòu)中插入一個(gè)新的元素后數(shù)據(jù)結(jié)構(gòu)變?yōu)榉强諗?shù)據(jù)結(jié)構(gòu)； 將數(shù)據(jù)結(jié)構(gòu)中的所有元素均刪除， 則該數(shù)據(jù)結(jié)構(gòu)變成空數(shù)據(jù)結(jié)構(gòu)。如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿(mǎn)足如下條件，則該數(shù)據(jù)結(jié)構(gòu)為線(xiàn)性結(jié)構(gòu)：有且只有一個(gè)根結(jié)點(diǎn)每一個(gè)結(jié)點(diǎn)最多只有一個(gè)前件， 也最多只有一個(gè)后件線(xiàn)性結(jié)構(gòu)又稱(chēng)線(xiàn)性表。注意：在線(xiàn)性結(jié)構(gòu)表中插入或刪除元素，該線(xiàn)性表仍然應(yīng)滿(mǎn)足線(xiàn)性結(jié)構(gòu)。如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不滿(mǎn)足線(xiàn)性結(jié)構(gòu)， 則稱(chēng)為非線(xiàn)性結(jié)構(gòu)。（三）線(xiàn)性表及其順序存儲(chǔ)結(jié)構(gòu)1基本概念線(xiàn)性表是最常用的數(shù)據(jù)結(jié)構(gòu)， 它由一組數(shù)據(jù)元素組成。注意： 這里的數(shù)據(jù)

20、元素是一個(gè)廣義的數(shù)據(jù)元素， 并不僅僅是指一個(gè)數(shù)據(jù)。 如， 矩陣、學(xué)生記錄表等。非空線(xiàn)性表的結(jié)構(gòu)特征：有且只有一個(gè)根結(jié)點(diǎn)，它無(wú)前件有且只有一個(gè)終端結(jié)點(diǎn)， 它無(wú)后件除根結(jié)點(diǎn)和終端結(jié)點(diǎn)之外， 所有的結(jié)點(diǎn)有且只有一個(gè)前件和一個(gè)后件。 線(xiàn)性表中結(jié)點(diǎn)的個(gè)數(shù)稱(chēng)為結(jié)點(diǎn)的長(zhǎng)度 n。當(dāng) n=0 時(shí)，稱(chēng)為空表。2順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)：線(xiàn)性表中所有的元素所占的存儲(chǔ)空間是連續(xù)的線(xiàn)性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的通常，順序存儲(chǔ)結(jié)構(gòu)中，線(xiàn)性表中每一個(gè)數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的存儲(chǔ)地址由該元素在線(xiàn)性表中的位置序號(hào)唯一確定。線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)下的基本運(yùn)算：全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)第 7

21、頁(yè)在指定位置插入一個(gè)元素刪除線(xiàn)性表中的指定元素查找某個(gè)或某些特定的元素線(xiàn)性表的排序按要求將一個(gè)線(xiàn)性表拆分為多個(gè)線(xiàn)性表將多個(gè)線(xiàn)性表合并為一個(gè)線(xiàn)性表復(fù)制線(xiàn)性表逆轉(zhuǎn)一個(gè)線(xiàn)性表3線(xiàn)性表的基本操作1）順序表的插入運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表中插入一個(gè)元素。注意：找到插入位置后，將插入位置開(kāi)始的所有元素從最后一個(gè)元素開(kāi)始順序后移。另外，在定義線(xiàn)性表時(shí)，一定要定義足夠的空間，否則，將不允許插入元素。2）順序表的刪除運(yùn)算在順序在存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表中刪除一個(gè)元素。注意：找到刪除的數(shù)據(jù)元素后，從該元素位置開(kāi)始，將后面的元素一一向前移動(dòng)，在移動(dòng)完成后，線(xiàn)性表的長(zhǎng)度減 1（四）棧和隊(duì)列1棧及其基本運(yùn)算1）棧棧是一種特殊的

22、線(xiàn)性表， 它是限定在一端進(jìn)行插入和刪除的線(xiàn)性表。 它的插入和刪除只能在表的一端進(jìn)行，而另一端是封閉的，不允許進(jìn)行插入和刪除操作。在棧中， 允許插入和刪除操作一端稱(chēng)為棧頂， 不允許插入和刪除操作的一端則稱(chēng)為棧底。棧頂?shù)脑乜偸亲詈蟊徊迦氲脑?，也是最先被刪除的元素。它遵循的原則是：先進(jìn)后出或后進(jìn)先出。堆棧指針總是指向棧頂元素的。2）棧的順序存儲(chǔ)及其運(yùn)算在棧的順序存儲(chǔ)空間 S（1：m）中，S（bottom）通常為棧底元素，S（top）為棧頂元素。Top=0 表示?？眨籺op=m 表示棧滿(mǎn)。1）入棧運(yùn)算即在棧的頂部插入一個(gè)新元素。 操作方式是：將棧頂指針加 1，再將元素插入至指針?biāo)傅奈恢谩?）退棧

23、運(yùn)算退棧運(yùn)算即將棧頂元素取出并賦給一個(gè)指定的變量。操作方式是：先將棧頂元素賦給指定的變量，再將棧頂指針減 1。3）讀棧頂元素將棧頂元素賦給某一指定變量， 但棧頂指針不變。2隊(duì)列及其基本運(yùn)算1）隊(duì)列隊(duì)列即是允許在一端進(jìn)行插入， 而在另一端進(jìn)行刪除的線(xiàn)性表。 允許插入的一端稱(chēng)為隊(duì)尾，通常用一個(gè)尾指針指向隊(duì)尾；允許刪除的一端稱(chēng)為隊(duì)首， 通常用一個(gè)隊(duì)首指針指向排隊(duì)元素的前一個(gè)位置。隊(duì)列遵循的規(guī)則是： 先進(jìn)先出或后進(jìn)后出2）循環(huán)隊(duì)列及其運(yùn)算隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)一般采用循環(huán)隊(duì)列的形式。循環(huán)隊(duì)列， 即是次隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置， 形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用。在循環(huán)隊(duì)列中，用隊(duì)尾指針

24、 rear 指向隊(duì)列中的隊(duì)尾元素， 用排頭指針 front 指向排頭元素的前一個(gè)位置，因此，從排頭指針front 指向的后一個(gè)位置到隊(duì)尾指針 rear指向的位置之間所有的元素均為隊(duì)列中的元素。循 環(huán) 隊(duì) 列 的 初 始 狀 態(tài) 為 空 ， 即rear=front=m。 這里m即為隊(duì)列的存儲(chǔ)空間。循環(huán)隊(duì)列的基本運(yùn)算： 入隊(duì)運(yùn)算和退隊(duì)運(yùn)算。入隊(duì)運(yùn)算：每進(jìn)行一次入隊(duì)運(yùn)算，隊(duì)尾指針加 1。 當(dāng)隊(duì)尾指針 rear=m+1 時(shí)， 即表示隊(duì)列空間的尾部已經(jīng)放置了元素， 則下一個(gè)元素應(yīng)該旋轉(zhuǎn)到隊(duì)列空間的首部， 即 rear=1全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)第 8頁(yè)退隊(duì)運(yùn)算：每退隊(duì)一個(gè)元素，排頭指針加 1。

25、當(dāng)排頭指針 front=m+1 時(shí)，即排頭指針指向隊(duì)列空間的尾部，退隊(duì)后，排頭指針指向隊(duì)列空間的開(kāi)始，即 front=1。在 隊(duì) 列 操 作 時(shí) ， 循 環(huán) 隊(duì) 列 滿(mǎn) 時(shí) ，front=rear，隊(duì)列空時(shí)，也有 rear=front，即在隊(duì)列空或滿(mǎn)時(shí)， 排頭指針和隊(duì)尾指針均指向同一個(gè)位置。要判斷隊(duì)列空或滿(mǎn)時(shí)，還應(yīng)增加一個(gè)標(biāo)志，s 值的定義：表示隊(duì)列滿(mǎn)表示隊(duì)列滿(mǎn)表示隊(duì)列空表示隊(duì)列空10s判斷隊(duì)列空與隊(duì)列滿(mǎn)的條件下：隊(duì)列空的條件：s=0隊(duì)列滿(mǎn)的條件：s=1、front=rear（1）入隊(duì)運(yùn)算即在隊(duì)尾加入一個(gè)新元素。 這個(gè)運(yùn)算有兩個(gè)基本操作：首先，將隊(duì)尾指針加 1，即rear=rear+1，當(dāng) r

26、ear=m+1 時(shí)，置 rear=1，然后，將新元素插入到隊(duì)尾指針指向的位置。當(dāng)循環(huán)隊(duì)列非空 （s=1） ， 且 front=rear時(shí)，隊(duì)列滿(mǎn)，不能進(jìn)行入隊(duì)操作。此情況稱(chēng)“上溢” 。（2）退隊(duì)操作即將隊(duì)首的元素賦給一個(gè)指定的變量。該運(yùn)算也有兩個(gè)基本操作：首先，將排頭指針加 1，即 front=front+1，當(dāng) front=m+1時(shí)，置 front=1，然后，將排頭指針指向的元素賦給指定的變量。當(dāng)循環(huán)隊(duì)列為空（s=0）時(shí)，不能進(jìn)行退隊(duì)運(yùn)算。此種情況稱(chēng)為“下溢” 。（五）線(xiàn)性鏈表1基本概念前面的線(xiàn)性表均是采用順序存儲(chǔ)結(jié)構(gòu)及在順序存儲(chǔ)結(jié)構(gòu)下的運(yùn)算。1）順序存儲(chǔ)的優(yōu)點(diǎn)：結(jié)構(gòu)簡(jiǎn)單運(yùn)算方便2）順序存儲(chǔ)

27、結(jié)構(gòu)的缺點(diǎn)：要在順序存儲(chǔ)的線(xiàn)性表中插入一個(gè)新元素或刪除一個(gè)元素時(shí)， 為了保證插入或刪除后的線(xiàn)性表仍然為順序存儲(chǔ)。在插入或刪除元素時(shí)，需要移動(dòng)大量的數(shù)據(jù)元素，因此運(yùn)算效率較低。如果一個(gè)線(xiàn)性表分配順序存儲(chǔ)空間后， 如果出現(xiàn)線(xiàn)性表的存儲(chǔ)空間已滿(mǎn)，但還需要插入元素時(shí)，會(huì)發(fā)生“上溢”錯(cuò)誤。在實(shí)際應(yīng)用時(shí)， 可能有多個(gè)線(xiàn)性表同時(shí)使用存儲(chǔ)空間， 這樣給存儲(chǔ)空間的分配帶來(lái)問(wèn)題， 有可能使有的隊(duì)列空間不夠或過(guò)多造成浪費(fèi)?；谏鲜銮闆r， 對(duì)于大的線(xiàn)性表或元素變動(dòng)頻繁的大線(xiàn)性表不宜采用順序存儲(chǔ)結(jié)構(gòu)，而應(yīng)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)假設(shè)每一個(gè)數(shù)據(jù)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)存儲(chǔ)單元，該存儲(chǔ)單元稱(chēng)為存儲(chǔ)結(jié)點(diǎn)，簡(jiǎn)稱(chēng)結(jié)點(diǎn)。在鏈?zhǔn)酱鎯?chǔ)方

28、式中， 要求每一個(gè)結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素，你為數(shù)據(jù)域；另一部分用于存放指針，稱(chēng)為指針域。 該指針用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中， 存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)， 各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系不一致， 而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來(lái)確定的。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)既可以用于線(xiàn)性結(jié)構(gòu)， 也可用于非線(xiàn)性結(jié)構(gòu)。4）線(xiàn)性鏈表線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)為線(xiàn)性鏈表。將存儲(chǔ)空間劃分成若干的小塊， 每塊占用若干個(gè)字節(jié)，這些小塊稱(chēng)為存儲(chǔ)結(jié)點(diǎn)。將存儲(chǔ)結(jié)點(diǎn)分為兩個(gè)部分， 一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱(chēng)為數(shù)據(jù)域；另一部分用于存儲(chǔ)元素之間的前后件關(guān)系， 即存放下一個(gè)元素在

29、存儲(chǔ)序號(hào)（即存儲(chǔ)地址） ，即指向后件結(jié)點(diǎn)，稱(chēng)為指針域。在線(xiàn)性鏈表中用一個(gè)專(zhuān)門(mén)的指針 HEAD全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)第 9頁(yè)指向線(xiàn)性鏈表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn) （即存放第一個(gè)元素的地址） 。線(xiàn)性表中最后一個(gè)元素沒(méi)有后件，因此，線(xiàn)性鏈表中的最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭?（用Null 或0表示） ，表示鏈終結(jié)。在線(xiàn)性鏈表中， 各元素的存儲(chǔ)序號(hào)是不連續(xù)的， 元素間的前后件關(guān)系與位置關(guān)系也是不一致的。在線(xiàn)性鏈表中，前后件的關(guān)系依靠各結(jié)點(diǎn)的指針來(lái)指示， 指向表的第一個(gè)元素的指針 HEAD 稱(chēng)為頭指針， 當(dāng) HEAD=NULL時(shí)，表示該鏈表為空。對(duì)于線(xiàn)性鏈表，可以從頭指針開(kāi)始，沿著各結(jié)點(diǎn)的指針掃描到

30、鏈表中的所有結(jié)點(diǎn)。這種線(xiàn)性鏈表稱(chēng)為線(xiàn)性單鏈表， 即可以從表頭開(kāi)始向后掃描鏈表中的所有結(jié)點(diǎn)， 而不能從中間或表尾結(jié)點(diǎn)向前掃描位于該結(jié)點(diǎn)之前的元素。這種鏈表結(jié)構(gòu)的缺點(diǎn)是不能任意地對(duì)鏈表中的元素按下同的方向進(jìn)行掃描。 在某些應(yīng)用時(shí)， 如果對(duì)鏈表中的元素設(shè)置兩個(gè)指針域，一個(gè)為指向前件的指針域，稱(chēng)為左指針（LLink） ，一個(gè)為指向后件的指針域，稱(chēng)為右指針 （RLink） 。 則這種鏈表是雙向鏈表。5）帶鏈的棧帶鏈的棧即是用來(lái)收集計(jì)算機(jī)存儲(chǔ)空間中的所有空閑的存儲(chǔ)結(jié)點(diǎn)， 這種帶鏈的棧稱(chēng)為可利用棧。當(dāng)需要存儲(chǔ)結(jié)點(diǎn)時(shí)， 即從可利用的棧的頂部取出棧頂結(jié)點(diǎn)； 當(dāng)系統(tǒng)要釋放一個(gè)存儲(chǔ)結(jié)點(diǎn)時(shí)， 將該結(jié)點(diǎn)空間放回到可利用

31、棧的棧頂。即在計(jì)算機(jī)中所有空閑的空間， 均可以以結(jié)點(diǎn)的方式鏈接到可利用棧中， 隨著其他線(xiàn)性鏈表中結(jié)點(diǎn)的插入與刪除， 可利用棧處于動(dòng)態(tài)變化之中， 即可利用棧經(jīng)常要進(jìn)行退棧和入棧操作。6）帶鏈的隊(duì)列隊(duì)列也是線(xiàn)性表， 也可利用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來(lái)進(jìn)行保存。2線(xiàn)性鏈表的基本運(yùn)算線(xiàn)性鏈表包括的基本運(yùn)算：在鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個(gè)新元素在鏈表中刪除包含指定元素的結(jié)點(diǎn)將兩個(gè)線(xiàn)性鏈表按要求合并成一個(gè)線(xiàn)性鏈表將一個(gè)線(xiàn)性鏈表按要求進(jìn)行分解逆轉(zhuǎn)線(xiàn)性鏈表復(fù)制線(xiàn)性鏈表線(xiàn)性鏈表的排序線(xiàn)性鏈表的查找1）線(xiàn)性鏈表中查找指定的元素在線(xiàn)性鏈表中查找元素 X：從頭指針指向的結(jié)點(diǎn)開(kāi)始往后沿指針進(jìn)行掃描， 直到后面已沒(méi)有結(jié)點(diǎn)或下

32、一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閄為止。元素的查找， 經(jīng)常是為了進(jìn)行插入或刪除操作而進(jìn)行的，因此，在查找時(shí)，往往是需要記錄下該結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)。2）線(xiàn)性鏈表的插入線(xiàn)性鏈表的插入即在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線(xiàn)性表中插入一個(gè)新元素。在線(xiàn)性鏈表中包含元素x的結(jié)點(diǎn)之前插入新元素 b，插入過(guò)程：（1）從可利用棧中取得一個(gè)結(jié)點(diǎn)，設(shè)該結(jié)點(diǎn)號(hào)為 p，即取得的結(jié)點(diǎn)的存儲(chǔ)序號(hào)存放在變量 p 中。 并置結(jié)點(diǎn) p 的數(shù)據(jù)域?yàn)椴迦氲脑刂?b。（2）在線(xiàn)性鏈表中尋找包含元素 x 的前一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的存儲(chǔ)序號(hào)為 q。（3）將結(jié)點(diǎn) p 插入到結(jié)點(diǎn) q 之后。具體的操作：首先，使結(jié)點(diǎn) p 插入到結(jié)點(diǎn) q 之后（即結(jié)點(diǎn) q 的后件結(jié)點(diǎn)） ，然后，使

33、結(jié)點(diǎn) q的指針域 內(nèi)容改為指向結(jié)點(diǎn) p。線(xiàn)性鏈表的插入操作， 新結(jié)點(diǎn)是為來(lái)自于可利用棧，因此不會(huì)造成線(xiàn)性表的溢出。同樣，由于可利用?？杀欢鄠€(gè)線(xiàn)性表利用，因此，不會(huì)造成存儲(chǔ)空間的浪費(fèi)，大家動(dòng)態(tài)地共同使用存儲(chǔ)空間。3）線(xiàn)性鏈表的刪除線(xiàn)性鏈表的刪除， 即是在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)第 10頁(yè)下的線(xiàn)性表中刪除指定元素的結(jié)點(diǎn)。操作方式：（1）在線(xiàn)性表中找到包含指定元素 x的前一個(gè)結(jié)點(diǎn) p（2）將該結(jié)點(diǎn) p 后的包含元素 x 的結(jié)點(diǎn)從線(xiàn)性鏈表中刪除， 然后將被刪除結(jié)點(diǎn)的后一個(gè)結(jié)點(diǎn) q 的地址提供給結(jié)點(diǎn) p 的指針域，即將結(jié)點(diǎn) p 指向結(jié)點(diǎn) q。（3）將刪除的結(jié)點(diǎn)送回可利用棧。從以上的

34、刪除操作可見(jiàn)， 刪除一個(gè)指定的元素，不需要移動(dòng)其他的元素即可實(shí)現(xiàn)，這是順序存儲(chǔ)的線(xiàn)性表所不能實(shí)現(xiàn)的。同時(shí)， 此操作還可更有效地利用計(jì)算機(jī)的存儲(chǔ)空間。3循環(huán)鏈表及其基本操作在線(xiàn)性鏈表中， 雖然對(duì)數(shù)據(jù)元素的插入和刪除操作比較簡(jiǎn)單， 但由于它對(duì)第一個(gè)結(jié)點(diǎn)和空表需要單獨(dú)處理， 使得空表與非空表的處理不一致。循環(huán)鏈表，即是采用另一種鏈接方式，它的特點(diǎn)如下：（1） 在循環(huán)鏈表中增加一個(gè)表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蚋鶕?jù)需要來(lái)設(shè)置， 指針域指向線(xiàn)性表的第一個(gè)元素的結(jié)點(diǎn)。 循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)。（2）循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不是空的，而是指向表頭結(jié)點(diǎn)。在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成一個(gè)環(huán)狀鏈。在循

35、環(huán)鏈表中， 只要指出表中任何一個(gè)結(jié)點(diǎn)的位置， 均可以從它開(kāi)始掃描到所有的結(jié)點(diǎn)，而線(xiàn)性鏈表做不到，線(xiàn)性鏈表是一種單向的鏈表，只能按照指針的方向進(jìn)行掃描。循環(huán)鏈表中設(shè)置了一個(gè)表頭結(jié)點(diǎn)，因此，在任何時(shí)候都至少有一個(gè)結(jié)點(diǎn)，因此空表與非空表的運(yùn)算相統(tǒng)一。（六）樹(shù)與二叉樹(shù)1樹(shù)的基本概念樹(shù)是一種簡(jiǎn)單的非線(xiàn)性結(jié)構(gòu)。 在樹(shù)結(jié)構(gòu)中，數(shù)據(jù)元素之間有著明顯的層次結(jié)構(gòu)。在樹(shù)的圖形表示中，用直線(xiàn)連接兩端的結(jié)點(diǎn)，上端點(diǎn)為前件，下端點(diǎn)為后件。在樹(shù)結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱(chēng)為父結(jié)點(diǎn)。如 A 即為結(jié)點(diǎn) B、C、D 的父結(jié)點(diǎn)。沒(méi)有父結(jié)點(diǎn)的結(jié)點(diǎn)只有一個(gè)， 稱(chēng)為根結(jié)點(diǎn)。如上圖所示，結(jié)點(diǎn) A 即為根結(jié)點(diǎn)。每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件

36、， 它們均稱(chēng)為該結(jié)點(diǎn)的子結(jié)點(diǎn)。如結(jié)點(diǎn) G、H、I 是結(jié)點(diǎn)D 的子結(jié)點(diǎn)。沒(méi)有后件的結(jié)點(diǎn)，稱(chēng)為葉子結(jié)點(diǎn)。上圖中，葉子結(jié)點(diǎn)有：J、M、N、L、C、G、H、I。在樹(shù)結(jié)構(gòu)中， 一個(gè)結(jié)點(diǎn)所擁有的后件結(jié)點(diǎn)個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的度。例如，結(jié)點(diǎn) D 的度為 3，結(jié)點(diǎn) E 的度為 1 等，按此原則，所有葉子結(jié)點(diǎn)的度均為 0。在樹(shù)中， 所有結(jié)點(diǎn)中最大的度稱(chēng)為該樹(shù)的度。上圖所示的樹(shù)中，所有結(jié)點(diǎn)中最大的度是 3，所以該樹(shù)的度為 3。樹(shù)分層，根結(jié)點(diǎn)為第一層，往下依次類(lèi)推。同一層結(jié)點(diǎn)的所有子結(jié)點(diǎn)均在下一層。如上圖：A 結(jié)點(diǎn)在第 1 層，B、C、D 結(jié)點(diǎn)在第 2 層；E、F、G、H、I 在第 3 層；J、K、L在第 4 層；M、N

37、 在第 5 層。樹(shù)的最大層次稱(chēng)為樹(shù)的深度。 上圖樹(shù)的深度為 5。在樹(shù)中， 某結(jié)點(diǎn)的一個(gè)子結(jié)點(diǎn)為根構(gòu)成的樹(shù)稱(chēng)作該結(jié)點(diǎn)的子樹(shù)。葉子結(jié)點(diǎn)沒(méi)有子樹(shù)。在計(jì)算機(jī)中， 可以用樹(shù)來(lái)表示算術(shù)表達(dá)式。原則如下：（1）表達(dá)式中每一個(gè)運(yùn)算符在樹(shù)中對(duì)應(yīng)一個(gè)結(jié)點(diǎn)，稱(chēng)為運(yùn)算符結(jié)點(diǎn)ABCDEFGHIJKLMN全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)第 11頁(yè)（2）運(yùn)算符的每一個(gè)運(yùn)算對(duì)象在樹(shù)中為該運(yùn)算符結(jié)點(diǎn)的子樹(shù) （在樹(shù)中的順序?yàn)閺淖蟮接遥?）運(yùn)算對(duì)象中的單變量均為葉子結(jié)點(diǎn)樹(shù)在計(jì)算機(jī)中用多重鏈表表示。 多重鏈表中的每個(gè)結(jié)點(diǎn)描述了樹(shù)中對(duì)應(yīng)結(jié)點(diǎn)的信息，而每個(gè)結(jié)點(diǎn)中的鏈域（即指針域）個(gè)數(shù)將隨著樹(shù)中該結(jié)點(diǎn)的度而定義。如果在樹(shù)中， 每一個(gè)結(jié)

38、點(diǎn)的子結(jié)點(diǎn)的個(gè)數(shù)不相同， 因此在多重鏈中各結(jié)點(diǎn)的鏈域個(gè)數(shù)也不相同，會(huì)導(dǎo)致算法太復(fù)雜。因此，在樹(shù)中， 常采用定長(zhǎng)結(jié)點(diǎn)來(lái)表示樹(shù)中的每一個(gè)結(jié)點(diǎn)， 即取樹(shù)的度作為每個(gè)結(jié)點(diǎn)的鏈域的個(gè)數(shù)。這樣，管理相對(duì)簡(jiǎn)化了，但會(huì)造成空間的浪費(fèi)，因?yàn)橛性S多的結(jié)點(diǎn)存在空鏈域。2二叉樹(shù)及其基本性質(zhì)1）二叉樹(shù)的定義二叉樹(shù)的特點(diǎn)：非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)每一個(gè)結(jié)點(diǎn)最多只有兩個(gè)子結(jié)點(diǎn)，且結(jié)點(diǎn)分左右。 則一個(gè)結(jié)點(diǎn)最多可以有兩棵子樹(shù)， 分別稱(chēng)為左子樹(shù)和右子樹(shù)在二叉樹(shù)中， 每一個(gè)結(jié)點(diǎn)的度最大為 2，即二叉樹(shù)的度為 2。在二叉樹(shù)中，任何的子樹(shù)也均為二叉樹(shù)。在二叉樹(shù)中， 每一個(gè)結(jié)點(diǎn)的子樹(shù)被分為左子樹(shù)和右子樹(shù)。在二叉樹(shù)中，允許某一個(gè)結(jié)點(diǎn)只有左

39、子樹(shù)或只有右子樹(shù)。 如果一個(gè)結(jié)點(diǎn)既沒(méi)有左子樹(shù)，也沒(méi)有右子樹(shù)，則該結(jié)點(diǎn)為葉子結(jié)點(diǎn)。2）二叉樹(shù)的性質(zhì)性質(zhì) 1：在二叉樹(shù)的第 k 層上，最多有2k-1（k1）個(gè)結(jié)點(diǎn)。性質(zhì) 2：深度為 m 的二叉樹(shù)最多有 2m-1個(gè)結(jié)點(diǎn)。性質(zhì) 3：在任意一棵二叉樹(shù)中，度為 0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總比度為 2 的結(jié)點(diǎn)多一個(gè)。性質(zhì) 4：具有 n 個(gè)結(jié)點(diǎn)的二叉樹(shù)，其深度至少為log2n+1， 其中l(wèi)og2n表示 log2n的整數(shù)部分。3）滿(mǎn)二叉樹(shù)與完全二叉樹(shù)（1）滿(mǎn)二叉樹(shù)滿(mǎn)二叉樹(shù)的特點(diǎn)：除最后一層外， 每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。即在滿(mǎn)二叉樹(shù)中，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值， 即在滿(mǎn)二叉樹(shù)上的第 k 層上有 2k-1

40、個(gè)結(jié)點(diǎn)。如下即為一棵滿(mǎn)二叉樹(shù)。（2）完全二叉樹(shù)特點(diǎn)：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值， 在最后一層上只缺少右邊的若干個(gè)結(jié)點(diǎn)。即如果從根結(jié)點(diǎn)開(kāi)始， 對(duì)二叉樹(shù)的結(jié)點(diǎn)自上而下、自左而右用自然數(shù)進(jìn)行連續(xù)編號(hào)，則深度為 m、且有 n 個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為m的滿(mǎn)二叉樹(shù)中編號(hào)從 1 到 n 的結(jié)點(diǎn)一一對(duì)應(yīng)， 則是完全二叉樹(shù)。對(duì)于完全二叉樹(shù)， 葉子結(jié)點(diǎn)只能在層次最大的兩層中出現(xiàn)；對(duì)于任何一個(gè)結(jié)點(diǎn)，若其右分支下的子樹(shù)結(jié)點(diǎn)的最大層次為 p，則其分支下的子孫結(jié)點(diǎn)的最大層次為 p 或p+1。完全二叉樹(shù)具有的性質(zhì)：ABCDEFGHIJKLMNO滿(mǎn)二叉樹(shù)ABCDEFGHIJKLMNOP

41、QR完全二叉樹(shù)全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)第 12頁(yè)性質(zhì) 5：具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2n+1性質(zhì) 6：設(shè)完全二叉樹(shù)共有 n 個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開(kāi)始，按層次（每一層從左到右）用自然數(shù) 1、2、n 給結(jié)點(diǎn)編號(hào)，對(duì)于編號(hào)為 k （k=1,2,n） 的結(jié)點(diǎn)有如下結(jié)論： 若 k=1， 則該結(jié)點(diǎn)為根結(jié)點(diǎn)， 它沒(méi)有父結(jié)點(diǎn)；若 k1，則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為INT(k/2)。 若 2kn， 則編號(hào)為 k 的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為 2k； 否則該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn) （當(dāng)然也沒(méi)有右子結(jié)點(diǎn)） 若 2k+1n， 則編號(hào)為 k 的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為 2k+1；否則該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)。3二叉樹(shù)的存儲(chǔ)結(jié)

42、構(gòu)二叉樹(shù)的存儲(chǔ)常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。存儲(chǔ)二叉樹(shù)中各元素的存儲(chǔ)結(jié)點(diǎn)由兩個(gè)部分組成： 數(shù)據(jù)域和指針域。 在二叉樹(shù)中，由于每個(gè)結(jié)點(diǎn)可有兩個(gè)子結(jié)點(diǎn)， 則它的指針域有兩個(gè)： 一個(gè)用于存儲(chǔ)該結(jié)點(diǎn)的左子結(jié)點(diǎn)的存儲(chǔ)地址，即稱(chēng)為左指針域；一個(gè)用于存儲(chǔ)指向該結(jié)點(diǎn)的右子結(jié)點(diǎn)的存儲(chǔ)地址， 稱(chēng)為右指針域。存儲(chǔ)結(jié)構(gòu)如下：LchildValueRchildiL(i)V(i)R(i)即二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)中每一個(gè)存儲(chǔ)結(jié)點(diǎn)都有兩個(gè)指針域，因此，二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也稱(chēng)為二叉樹(shù)的鏈表。 在二叉樹(shù)在存儲(chǔ)中， 用一個(gè)頭指針指向二叉樹(shù)的根結(jié)點(diǎn)的存儲(chǔ)地址。如圖所示的二叉樹(shù)：如果我們將該二叉樹(shù)的所有結(jié)點(diǎn)順序編號(hào)，順序存放在存儲(chǔ)空間里，則它們?cè)趦?nèi)

43、存空間中的存放方式是：iL(i)V(i)R(i)BT12A324B536C748D9510E11612F13714G15816H17918I0100J0110K0120L0130M0140N0150O0160P0170Q0180R0當(dāng)然，對(duì)于滿(mǎn)二叉樹(shù)或完全二叉樹(shù)而言，也可采用順序存儲(chǔ)的方式，但順序存儲(chǔ)的方式不適合其他的二叉樹(shù)。4二叉樹(shù)的遍歷二叉樹(shù)的遍歷即是不重復(fù)地訪(fǎng)問(wèn)二叉樹(shù)的所有結(jié)點(diǎn)。在遍歷二叉樹(shù)時(shí)，一般先遍歷左子樹(shù)，然后再遍歷右子樹(shù)。在先左后右的原則下，二叉樹(shù)的遍歷又可分為三種：前序遍歷、中序遍歷和后序遍歷。ABCDEFGHIJKLMNOPQR全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)第 13頁(yè)1）

44、前序遍歷前序遍歷即先訪(fǎng)問(wèn)根結(jié)點(diǎn)， 然后遍歷左子樹(shù)，最后遍歷右子樹(shù)。在遍歷左子樹(shù)和遍歷右子樹(shù)時(shí)，依然是先遍歷根結(jié)點(diǎn)，然后是左子樹(shù)，再是右子樹(shù)。操作的具體方式：若二叉樹(shù)為空，則結(jié)束返回。否則： 訪(fǎng)問(wèn)根結(jié)點(diǎn)前序遍歷左子樹(shù)前序遍歷右子樹(shù)如上圖所示的完全二叉樹(shù)， 它的前序遍歷結(jié)果是：A、B、D、H、P、Q、I、R、E、J、K、C、F、L、M、G、N、O2）中序遍歷中序遍歷，即先遍歷左子樹(shù)，然后訪(fǎng)問(wèn)根結(jié)點(diǎn)，最后是遍歷右子樹(shù)。具體的操作方式：若二叉樹(shù)為空，則結(jié)束返回。否則： 中序遍歷左子樹(shù)訪(fǎng)問(wèn)根結(jié)點(diǎn) 中序遍歷右子樹(shù)這里強(qiáng)調(diào)，在遍歷左子樹(shù)和右子樹(shù)時(shí)，仍然要采用中序遍歷的方法。如上圖所示的完全二叉樹(shù)， 它的中序

45、遍歷結(jié)果是：P、H、Q、D、R、I、B、J、E、K、A、L、F、M、C、N、G、O3）后序遍歷后序遍歷，即選遍歷左子樹(shù)，然后是遍歷右子樹(shù)，最后訪(fǎng)問(wèn)根結(jié)點(diǎn)。具體的操作方式：若二叉樹(shù)為空，則結(jié)束返回。否則： 前序遍歷左子樹(shù)前序遍歷右子樹(shù)訪(fǎng)問(wèn)根結(jié)點(diǎn)如上圖所示的完全二叉樹(shù)， 它的后序遍歷結(jié)果是：P、Q、H、R、I、D、J、K、E、B、L、M、F、N、O、G、C、A（七）查找技術(shù)查找即是指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)指定的元素。1順序查找順序查找又稱(chēng)順序搜索。 一般是在線(xiàn)性表中查找指定的元素?；静僮鞣椒ㄊ牵簭木€(xiàn)性表的第一個(gè)元素開(kāi)始， 與被查元素進(jìn)行比較，相等則查找成功，否則繼續(xù)向后查找。 如果所有的

46、元素均查找完畢后都不相等，則該元素在指定的線(xiàn)性表中不存在。順序查找的最好情況： 要查找的元素在線(xiàn)性表的第一個(gè)元素，則查找效率最高；如果要查找的元素在線(xiàn)性表的最后或根本不存在，則查找需要搜索所有的線(xiàn)性表元素，這種情況是最差情況。對(duì)于線(xiàn)性表而言，順序查找效率很低。但對(duì)于以下的線(xiàn)性表， 也只能采用順序查找的方法：線(xiàn)性表為無(wú)序表， 即表中的元素沒(méi)有排列不是按大小順序進(jìn)行排列的， 這類(lèi)線(xiàn)性表不管它的存儲(chǔ)方式是順序存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)， 都只能按順序查找方式進(jìn)行查找即使是有序線(xiàn)性表， 如果采用鏈?zhǔn)酱鎯?chǔ)，也只能采用順序查找方式例如，現(xiàn)有線(xiàn)性表：7、2、1、5、9、4，要在序列中查找元素 6，查找的過(guò)程是：整個(gè)線(xiàn)

47、性表的長(zhǎng)度為 5查找計(jì)次 n=1，將元素 6 與序列的第一個(gè) 7 元素進(jìn)行比較，不等，繼續(xù)查找n=2，將 6 與第二個(gè)元素 2 進(jìn)行比較，不等，繼續(xù)n=3，將 6 與第三個(gè)元素 1 進(jìn)行比較，不等，繼續(xù)n=4，將 6 與第四個(gè)元素 5 進(jìn)行比較，不等，繼續(xù)n=5，將 6 與第五個(gè)元素 9 進(jìn)行比較，不等，繼續(xù)n=6，將 6 與第六個(gè)元素 4 進(jìn)行比較，不等，繼續(xù)n=7，超出線(xiàn)性表的長(zhǎng)度，查找結(jié)束，則該表中不存在要查找的元素。2二分查找二分查找只適用于順序存儲(chǔ)的有序表。此處所述的有序表是指線(xiàn)性中的元素按值全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)第 14頁(yè)非遞減排列（即由小到大，但允許相鄰元素值相等）

48、。二分查找的方法如下：將要查找的元素與有序序列的中間元素進(jìn)行比較：如果該元素比中間元素大， 則繼續(xù)在線(xiàn)性表的后半部分 （中間項(xiàng)以后的部分）進(jìn)行查找如果要查找的元素的值比中間元素的值小， 則繼續(xù)在線(xiàn)性表的前半部分（中間項(xiàng)以前的部分）進(jìn)行查找這個(gè)查找過(guò)程一直按相同的順序進(jìn)行下去，一直到查找成功或子表長(zhǎng)度為 0（說(shuō)明線(xiàn)性表中沒(méi)有要查找的元素）有序線(xiàn)性表的二分法查找， 條件是必須這個(gè)有序線(xiàn)性表的存儲(chǔ)方式是順序存儲(chǔ)的。它的查找效率比順序查找要高得多， 它的最壞情況的查找次數(shù)是 log2n 次，而順序查找的最壞情況的查找次數(shù)是 n 次。當(dāng)然， 二分查找的方法也支持順序存儲(chǔ)的遞減序列的線(xiàn)性表。有非遞減有序線(xiàn)

49、性表：1、2、4、5、7、9，要查找元素 6。查找的方法是：序列長(zhǎng)度為 n=6，中間元素的序號(hào)m=(n+1)/2=3查找計(jì)次 k=1，將元素 6 與中間元素即元素 4 進(jìn)行比較，不等，64查找計(jì)次 k=2，查找繼續(xù)在后半部分進(jìn)行， 后半部分子表的長(zhǎng)度為 3，計(jì) 算 中 間 元 素 的 序 號(hào) ：m=3+(3+1)/2=5，將元素與后半部分的中間項(xiàng)進(jìn)行比較， 即第 5 個(gè)元素中的 7 進(jìn)行比較，不等，67查找計(jì)次 k=3，繼續(xù)查找在后半部分序列的前半部分子序列中查找，子表長(zhǎng)度為 1，則中間項(xiàng)序號(hào)即為m=3+(1+1)/2=4，即與第 4 個(gè)元素 5 進(jìn)行比較，不相等，繼續(xù)查找的子表長(zhǎng)度為 0，則

50、查找結(jié)束（八）排序技術(shù)排序即是將一個(gè)無(wú)序的序列整理成按值非遞減順序排列的有序序列。在這里，我們討論的是順序存儲(chǔ)的線(xiàn)性表的排序操作。1交換類(lèi)排序法交換類(lèi)排序法， 即是借助于數(shù)據(jù)元素之間的互相交換進(jìn)行排序的方法。1）冒泡排序法冒泡排序法即是利用相鄰數(shù)據(jù)元素之間的交換逐步將線(xiàn)性表變成有序序列的操作方法。操作過(guò)程如下：從表頭開(kāi)始掃描線(xiàn)性表， 在掃描過(guò)程中逐次比較相鄰兩個(gè)元素的大小， 若相鄰兩個(gè)元素中前一個(gè)元素的值比后一個(gè)元素的值大， 將兩個(gè)元素位置進(jìn)行交換， 當(dāng)掃描完成一遍時(shí)， 則序列中最大的元素被放置到序列的最后。再繼續(xù)對(duì)序列從頭進(jìn)行掃描， 這一次掃描的長(zhǎng)度是序列長(zhǎng)度減 1，因?yàn)樽畲蟮脑匾呀?jīng)就位了

51、， 采用與前相同的方法，兩兩之間進(jìn)行比較，將次大數(shù)移到子序列的末尾。按相同的方法繼續(xù)掃描， 每次掃描的子序列的長(zhǎng)度均比上一次減 1，直至子序列的長(zhǎng)度為 1 時(shí)， 排序結(jié)束。例如，有序列 5、2、9、4、1、7、6，將該序列從小到大進(jìn)行排列。采用冒泡排序法，具體操作步驟如下：序列長(zhǎng)度 n=7原序列5294176第一遍（從前往后）52941762594176254917623419762541796第一遍結(jié)2541769全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)第 15頁(yè)束后第二遍（從前往后）254176245176241576241567第二遍結(jié)束后241567第三遍（從前往后）241567214567

52、第三遍結(jié)束214567第四遍（從前往后）214567124567第四遍結(jié)束124567最后結(jié)果124567掃描的次數(shù)，最多需要掃描 n-1 次，如果序列已經(jīng)就位，則掃描結(jié)束。測(cè)試是否已經(jīng)就位，可設(shè)置一個(gè)標(biāo)志，如果該次掃描沒(méi)有數(shù)據(jù)交換，則說(shuō)明數(shù)據(jù)排序結(jié)束。2）快速排序法冒泡排序方法每次交換只能改變相鄰兩個(gè)元素之間的逆序，速度相對(duì)較慢。如果將兩個(gè)不相鄰的元素之間進(jìn)行交換， 可以消除多個(gè)逆序。快速排序的方法是：從線(xiàn)性表中選取一個(gè)元素，設(shè)為 T，將線(xiàn)性表后面小于 T 的元素移到前面， 而前面大于 T 的元素移到后面， 結(jié)果將線(xiàn)性表分成兩個(gè)部分 （稱(chēng)為兩個(gè)子表） ， T 插入到其分界線(xiàn)的位置處，這個(gè)過(guò)程

53、稱(chēng)為線(xiàn)性表的分割。對(duì)過(guò)對(duì)線(xiàn)性表的一次分割， 就以T為分界線(xiàn)，將線(xiàn)性表分成前后兩個(gè)子表， 且前面子表中的所有元素均不大于 T，而后面的所有元素均不小于 T。再將前后兩個(gè)子表再進(jìn)行相同的快速排序，將子表再進(jìn)行分割，直到所有的子表均為空，則完成快速排序操作。在快速排序過(guò)程中， 隨著對(duì)各子表不斷的進(jìn)行分割，劃分出的子表會(huì)越來(lái)越多，但一次又只能對(duì)一個(gè)子表進(jìn)行分割處理， 需要將暫時(shí)不用的子表記憶起來(lái)， 這里可用棧來(lái)實(shí)現(xiàn)。對(duì)某個(gè)子表進(jìn)行分割后， 可以將分割出的后一個(gè)子表的第一個(gè)元素與最后一個(gè)元素的位置壓入棧中， 而繼續(xù)對(duì)前一個(gè)子表進(jìn)行再分割；當(dāng)分割出的子表為空時(shí)，可以從棧中退出一個(gè)子表進(jìn)行分割。這個(gè)過(guò)程直到

54、棧為空為止， 說(shuō)明所有子表為空，沒(méi)有子表再需分割，排序就完成。2插入類(lèi)排序法1）簡(jiǎn)單插入排序插入排序， 是指將無(wú)序序列中的各元素依次插入到已經(jīng)有序的線(xiàn)性表中。插入排序操作的思路：在線(xiàn)性表中，只包含第 1 個(gè)元素的子表，作為該有序表。從線(xiàn)性表的第 2 個(gè)元素開(kāi)始直到最后一個(gè)元素， 逐次將其中的每一個(gè)元素插入到前面的有序的子表中。該方法與冒泡排序方法的效率相同， 最壞的情況下需要 n(n-1)/2 次比較。例如，有序列 5、2、9、4、1、7、6，將該序列從小到大進(jìn)行排列。采用簡(jiǎn)單插入排序法， 具體操作步驟如下：序列長(zhǎng)度 n=75294176j=22594176j=3全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)

55、知識(shí)第 16頁(yè)2594176j=42459176j=51245976j=61245796j=7插入排序后的結(jié)果12456792）希爾排序法希爾排序法的基本思想：將整個(gè)無(wú)序序列分割成若干小的子序列分別進(jìn)行插入排序。子序列的分割方法：將相隔某個(gè)增量 h的元素構(gòu)成一個(gè)子序列，在排序的過(guò)程中，逐次減小這個(gè)增量，最后當(dāng) h 減小到 1 時(shí)，再進(jìn)行一次插入排序操作，即完成排序。增量序列一般取ht=n/2k(k=1,2,log2n)，其中 n 為待排序序列的長(zhǎng)度。3選擇類(lèi)排序法1）簡(jiǎn)單選擇排序法基本思路：掃描整個(gè)線(xiàn)性表，從中選出最小的元素，將它交換到表的最前面，然后對(duì)后面的子表采用相同的方法， 直到子表為空

56、為止。對(duì)于長(zhǎng)度為n 的序列， 需要掃描n-1次，每一次掃描均找出剩余的子表中最小的元素， 然后將該最小元素與子表的第一個(gè)元素進(jìn)行交換。例如，有序列 5、2、9、4、1、7、6，將該序列從小到大進(jìn)行排列。采用簡(jiǎn)單選擇排序法， 具體操作步驟如下：原序列5294176第一遍掃描1294576第二遍掃描1294576第三遍掃描1249576第四遍掃描1245976第五遍掃描1245679第六遍掃描1245679排序結(jié)果12456792）堆排序法堆排序法屬于選擇類(lèi)排序方法。堆 的 定 義 ： 具 有 n 個(gè) 元 素 的 序 列（ h1,h2,hn）， 當(dāng) 且 僅 當(dāng) 滿(mǎn) 足122122iiiiiiiih

57、hhhhhhh或或（I=1,2,n/2）時(shí)稱(chēng)之為堆。本節(jié)只討論滿(mǎn)足前者條件的堆。由堆的定義看，堆頂元素（即第一個(gè)元素）必為最大項(xiàng)?？梢杂靡痪S數(shù)組或完全二叉樹(shù)來(lái)表示堆的結(jié)構(gòu)。用完全二叉樹(shù)表示堆時(shí)， 樹(shù)中所有非葉子結(jié)點(diǎn)值均不小于其左右子樹(shù)的根結(jié)點(diǎn)的值，因此堆頂（完全二叉樹(shù)的根結(jié)點(diǎn)）元素必須為序列的 n 個(gè)元素中的最大項(xiàng)。例如，有序列 5、2、9、4、1、7、6，將該序列從小到大進(jìn)行排列。全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)第 17頁(yè)利用堆排序法將該序列進(jìn)行排序。操作方式即： 先將無(wú)序堆的根結(jié)點(diǎn) 5 與左右子樹(shù)的根結(jié)點(diǎn) 2、9 進(jìn)行比較，59，將5 與 9 進(jìn)行交換；整后，對(duì)左右子樹(shù)進(jìn)行堆調(diào)整， 左子

58、樹(shù)的根結(jié)點(diǎn) 2 小于其左葉子結(jié)點(diǎn)5，調(diào)整；右子樹(shù)的根結(jié)點(diǎn) 5 小于其左右子結(jié)點(diǎn) 7 和 6，根據(jù)堆的要求，將 5 與 7 進(jìn)行調(diào)整。根據(jù)堆的定義，可以得到堆排序的方法：（1）首先將一個(gè)無(wú)序序列建成堆（2）然后將堆頂元素（序列中的最大項(xiàng)）與堆中最后一個(gè)元素交換（最大項(xiàng)應(yīng)該在序列的最后） 。三、本章應(yīng)考點(diǎn)撥本章內(nèi)容在筆試中會(huì)出現(xiàn) 5-6 個(gè)題目，是公共基礎(chǔ)知識(shí)部分出題量比較多的一章，所占分值也比較大，約 10 分。第二章第二章 程序設(shè)計(jì)基礎(chǔ)程序設(shè)計(jì)基礎(chǔ)一、內(nèi)容要點(diǎn)一、內(nèi)容要點(diǎn)（一）程序設(shè)計(jì)方法與風(fēng)格程序設(shè)計(jì)方法： 主要經(jīng)過(guò)了面向過(guò)程的結(jié)構(gòu)化程序設(shè)計(jì)和面向?qū)ο蟮某绦蛟O(shè)計(jì)方法。程序設(shè)計(jì)風(fēng)格， 是指編寫(xiě)

59、程序時(shí)所表現(xiàn)出來(lái)的特點(diǎn)、習(xí)慣和邏輯思路。通常，要求程序設(shè)計(jì)的風(fēng)格應(yīng)強(qiáng)調(diào)簡(jiǎn)單和清晰， 必須是可以讀的，可以理解的。要形成良好的程序設(shè)計(jì)的風(fēng)格， 應(yīng)考慮如下因素：1源程序文檔化（1）符號(hào)名的命名：符號(hào)名的命名要具有一定的實(shí)際含義，便于對(duì)程序的理解，即通常說(shuō)的見(jiàn)名思義；（2）程序注釋?zhuān)赫_的程序注釋能夠幫助他人理解程序。 注釋一般包括序言性注釋和功能性注釋?zhuān)唬?）視覺(jué)組織：為了使程序一目了然，可以對(duì)程序的格式進(jìn)行設(shè)置， 適當(dāng)?shù)赝ㄟ^(guò)空格、空行、縮進(jìn)等使程序?qū)哟吻逦?數(shù)據(jù)說(shuō)明方法（1）數(shù)據(jù)說(shuō)明的次序規(guī)范化；（2）說(shuō)明語(yǔ)句中變量安排有序化；（3） 使用注釋來(lái)說(shuō)明復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。3語(yǔ)句的結(jié)構(gòu)（1）在一行內(nèi)

60、只寫(xiě)一條語(yǔ)句；（2） 程序的編寫(xiě)應(yīng)該優(yōu)先考慮清晰性；（3）除非對(duì)效率有特殊的要求，否則，應(yīng)做到清晰第一，效率第二；（4）首先保證程序的正確，然后再要求速度；（5）避免使用臨時(shí)變量使程序的可讀性下降；（7）盡量使用庫(kù)函數(shù)，即盡量使用系統(tǒng)提供的資源；（8）避免采用復(fù)雜的條件語(yǔ)句；（9）盡量減少使用“否定”條件的條件語(yǔ)句；（10）數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡(jiǎn)化；（11）要模塊化，使模塊功能盡可能單一化；（12）利用信息隱蔽，確保每一個(gè)模塊652941769254176947215無(wú)序堆調(diào)整根結(jié)點(diǎn)調(diào)整子樹(shù)的根結(jié)點(diǎn)建堆的過(guò)程全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)第 18頁(yè)的獨(dú)立性；（13）從數(shù)據(jù)出發(fā)去構(gòu)造程序；