【正文】 (有2棵子樹)?！　≡跇浣Y(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹的度。每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。　　在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)。　 樹與二叉樹　　樹的基本概念　　樹是一種簡單的非線性結(jié)構(gòu)?！　∽⑨?：在鏈表中，即使知道被訪問結(jié)點(diǎn)的序號(hào)i，也不能像順序表中那樣直接按序號(hào)i訪問結(jié)點(diǎn)，而只能從鏈表的頭指針出發(fā)，順著鏈域逐個(gè)結(jié)點(diǎn)往下搜索，直至搜索到第i個(gè)結(jié)點(diǎn)為止。但它可以從任一結(jié)點(diǎn)出發(fā)來訪問表中其他所有結(jié)點(diǎn)，并實(shí)現(xiàn)空表與非空表的運(yùn)算的統(tǒng)一。二是由于在循環(huán)鏈表中設(shè)置了一個(gè)表頭結(jié)點(diǎn)，在任何情況下，循環(huán)鏈表中至少有一個(gè)結(jié)點(diǎn)存在，從而使空表與非空表的運(yùn)算統(tǒng)一。即在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成了一個(gè)環(huán)狀鏈?！　∨c前面所討論的線性鏈表相比，循環(huán)鏈表具有以下兩個(gè)特點(diǎn)：1)在鏈表中增加了一個(gè)表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蛘吒鶕?jù)需要來設(shè)置，指針域指向線性表的第一個(gè)元素的結(jié)點(diǎn)，而循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)。　　循環(huán)鏈表及其基本運(yùn)算　　在線性鏈表中，其插入與刪除的運(yùn)算雖然比較方便，但還存在一個(gè)問題，在運(yùn)算過程中對(duì)于空表和對(duì)第一個(gè)結(jié)點(diǎn)的處理必須單獨(dú)考慮，使空表與非空表的運(yùn)算不統(tǒng)一?！　?8)線性鏈表的查找。　　(6)復(fù)制線性鏈表?！　?4)將一個(gè)線性鏈表按要求進(jìn)行分解?！　?：在線性鏈表中刪除元素時(shí)，也不需要移動(dòng)數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點(diǎn)指針即可?！　?：在線性鏈表中插入元素時(shí)，不需要移動(dòng)數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點(diǎn)指針即可，也不會(huì)出現(xiàn)“上溢（注釋1）”現(xiàn)象。因此，在某些應(yīng)用中，對(duì)于線性鏈表中的每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針，一個(gè)稱為左指針，指向其前件結(jié)點(diǎn)。另一部分用于存放指針，稱為指針域，用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)(即前件或后件)，如下圖所示：　　線性鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表三種類型。　　線性鏈表：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表，是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接來實(shí)現(xiàn)的。(2)線性表的順序存儲(chǔ)結(jié)構(gòu)下，線性表的存儲(chǔ)空間不便于擴(kuò)充?！?線性鏈表　　線性表順序存儲(chǔ)的缺點(diǎn)：(1)插入或刪除的運(yùn)算效率很低。在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用排頭指針front指向排頭元素的前一個(gè)位置，因此，從頭指針front指向的后一個(gè)位置直到隊(duì)尾指針rear指向的位置之間，所有的元素均為隊(duì)列中的元素?！　￡?duì)列運(yùn)算包括：1）入隊(duì)運(yùn)算：從隊(duì)尾插入一個(gè)元素；2）退隊(duì)運(yùn)算：從隊(duì)頭刪除一個(gè)元素。尾指針（Rear）指向隊(duì)尾元素，頭指針（front）指向排頭元素的前一個(gè)位置（隊(duì)頭）?！　５拇鎯?chǔ)方式和線性表類似，也有兩種，即順序棧和鏈?zhǔn)綏??！　＞哂杏洃涀饔?。棧頂元素總是最后被插入的元素，棧底元素總是最先被插入的元素?棧和隊(duì)列　　棧及其基本運(yùn)算　　棧是限定在一端進(jìn)行插入與刪除運(yùn)算的線性表?！　?：進(jìn)行順性表的刪除運(yùn)算時(shí)也需要移動(dòng)元素，在等概率情況下，平均需要移動(dòng)（n1）/2個(gè)元素?！　。?）順序表的刪除運(yùn)算：在一般情況下，要?jiǎng)h除第i（1≤i≤n）個(gè)元素時(shí)，則要從第i+1個(gè)元素開始，直到第n個(gè)元素之間共ni個(gè)元素依次向前移動(dòng)一個(gè)位置。插入結(jié)束后，線性表的長度就增加了1?！　?：由此可以看出，在線性表的順序存儲(chǔ)結(jié)構(gòu)中，其前后件兩個(gè)元素在存儲(chǔ)空間中是緊鄰的，且前件元素一定存儲(chǔ)在后件元素的前面，可以通過計(jì)算機(jī)直接確定第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址?！　?：線性表是一種存儲(chǔ)結(jié)構(gòu)，它的存儲(chǔ)方式：順序和鏈?zhǔn)?。線性表中數(shù)據(jù)元素的個(gè)數(shù)稱為線性表的長度。 線性表及其順序存儲(chǔ)結(jié)構(gòu)　　線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號(hào)，元素之間的相對(duì)位置是線性的。在數(shù)據(jù)處理領(lǐng)域中，通常把數(shù)據(jù)元素之間這種固有的關(guān)系簡單地用前后件關(guān)系（即直接前驅(qū)與直接后繼關(guān)系）來描述。　　*：常見的非線性結(jié)構(gòu)有樹、二叉樹和圖等。　　*：常見的線性結(jié)構(gòu)有線性表、棧、隊(duì)列和線性鏈表等?！　?shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)?！　?shù)據(jù)結(jié)構(gòu)的圖形表示　　一個(gè)數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外，還可以直觀地用圖形表示。同一種邏輯結(jié)構(gòu)的數(shù)據(jù)可以采用不同的存儲(chǔ)結(jié)構(gòu)，但影響數(shù)據(jù)處理效率?！　?）索引存儲(chǔ)：除建立存儲(chǔ)結(jié)點(diǎn)信息外，還建立附加的索引表來標(biāo)識(shí)結(jié)點(diǎn)的地址。它不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。　　1）順序存儲(chǔ)。　?。?）在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)?！　?shù)據(jù)結(jié)構(gòu)主要研究和討論以下三個(gè)方面的問題：　　（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。　?。ㄗ⑨?）這是因?yàn)椋涸诰帉懗绦驎r(shí)要受到計(jì)算機(jī)系統(tǒng)運(yùn)行環(huán)境的限制，程序通常還要考慮很多與方法和分析無關(guān)的細(xì)節(jié)問題?！　。?）算法時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量，可以用執(zhí)行算法的過程中所需基本運(yùn)算的執(zhí)行次數(shù)來度量?！　?：綜上所述，所謂算法，是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個(gè)規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。當(dāng)輸入不夠或輸入錯(cuò)誤時(shí)，算法將無法執(zhí)行或執(zhí)行有錯(cuò)。算法中各種運(yùn)算總是要施加到各個(gè)運(yùn)算對(duì)象上，而這些運(yùn)算對(duì)象又可能具有某種初始狀態(tài)，這就是算法執(zhí)行的起點(diǎn)或依據(jù)。有兩重含義，一是算法中的操作步驟為有限個(gè)，二是每個(gè)步驟都能在有限時(shí)間內(nèi)完成。　?。?）有窮性。每一條指令的含義明確，無二義性。針對(duì)實(shí)際問題而設(shè)計(jì)的算法，執(zhí)行后能夠得到滿意的結(jié)果。程序的編制不可能優(yōu)于算法的設(shè)計(jì)（注釋1）。換句話說，算法是對(duì)特定問題求解步驟的一種描述?！　。盒枨蠓治?、概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)策略?！　?，實(shí)體聯(lián)系模型及ER圖，從ER圖導(dǎo)出關(guān)系數(shù)據(jù)模型?！　?，靜態(tài)調(diào)試與動(dòng)態(tài)調(diào)試?！　。傮w設(shè)計(jì)與詳細(xì)設(shè)計(jì)。　　三、軟件工程基礎(chǔ)　　，軟件生命周期概念，軟件工具與軟件開發(fā)環(huán)境?！　　！　?；基本排序算法（交換類排序，選擇類排序，插入類排序）?！　?、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算?！　?；線性表的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除運(yùn)算?！　　?考試內(nèi)容　　一、基本數(shù)據(jù)結(jié)構(gòu)與算法　??；算法復(fù)雜度的概念和意義（時(shí)間復(fù)雜度與空間復(fù)雜度）?！　?，具有初步應(yīng)用相關(guān)技術(shù)進(jìn)行軟件開發(fā)的能力?！　?。全國計(jì)算機(jī)等級(jí)考試二級(jí)教程——公共基礎(chǔ)知識(shí)考試大綱　　◆ 基本要求 　　?！　　！　　！　。私怅P(guān)系數(shù)據(jù)庫的設(shè)計(jì)?！　?；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念?！　?；棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算?！　?；二叉樹的定義及其存儲(chǔ)結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷?！　《?、程序設(shè)計(jì)基礎(chǔ)　　?！　?，對(duì)象，方法，屬性及繼承與多態(tài)性?！　?，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書?！　?，白盒測(cè)試與黑盒測(cè)試，測(cè)試用例設(shè)計(jì)，軟件測(cè)試的實(shí)施，單元測(cè)試、集成測(cè)試和系統(tǒng)測(cè)試?！　∷摹?shù)據(jù)庫設(shè)計(jì)基礎(chǔ)　　：數(shù)據(jù)庫，數(shù)據(jù)庫管理系統(tǒng)，數(shù)據(jù)庫系統(tǒng)?！　?，包括集合運(yùn)算及選擇、投影、連接運(yùn)算，數(shù)據(jù)庫規(guī)范化理論。　　◆ 考試方式　　公共基礎(chǔ)知識(shí)有10道選擇題和5道填空題共三十分　第一章 數(shù)據(jù)結(jié)構(gòu)與算法 　　 算法　　算法是指解題方案的準(zhǔn)確而完整的描述?！　?：算法不等于程序，也不等于計(jì)算方法。　　算法的基本特征　?。?）可行性?！　。?）確定性。并且在任何條件下，算法只有唯一的一條執(zhí)行路徑，即相同的輸入只能得出相同的輸出。算法必須在有限的時(shí)間內(nèi)完成?！　。?）擁有足夠的情報(bào)。因此，一個(gè)算法執(zhí)行的結(jié)果總是與輸入的初始數(shù)據(jù)有關(guān)，不同的輸入將會(huì)有不同的結(jié)果輸出。一般說來，當(dāng)算法擁有足夠的情報(bào)時(shí)，此算法才是有效的；而當(dāng)提供的情報(bào)不夠時(shí)，算法可能無效?！　∷惴◤?fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度?！　。?）算法空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間?！?數(shù)據(jù)結(jié)構(gòu)的基本概念 　　數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合?！　?shù)據(jù)的邏輯結(jié)構(gòu)包含：　　1）表示數(shù)據(jù)元素的信息；　　2）表示各數(shù)據(jù)元素之間的前后件關(guān)系（注釋1）。　　數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等。它是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。　　2）鏈接存儲(chǔ)。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)?！　?：數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式?！　。?）對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，對(duì)于數(shù)據(jù)集合D中的每一個(gè)數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示，一般稱之為數(shù)據(jù)結(jié)點(diǎn)，并簡稱為結(jié)點(diǎn)；為了進(jìn)一步表示各數(shù)據(jù)元素之間的前后件關(guān)系，對(duì)于關(guān)系R中的每一個(gè)二元組，用一條有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)?！　。?）線性結(jié)構(gòu)（非空的數(shù)據(jù)結(jié)構(gòu)）條件：1）有且只有一個(gè)根結(jié)點(diǎn)（注釋2）；2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前驅(qū)，也最多有一個(gè)后繼?！　。?）非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。　?。ㄗ⑨?）前后件關(guān)系：一般情況下，在具有相同特征的數(shù)據(jù)元素集合中，各個(gè)數(shù)據(jù)元素之間存在某種關(guān)系（即聯(lián)系），這種關(guān)系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)?！　。ㄗ⑨?）在數(shù)據(jù)結(jié)構(gòu)中，沒有前去的結(jié)點(diǎn)稱為根結(jié)點(diǎn)。線性表是由n(n≥0)個(gè)數(shù)據(jù)元素組成的一個(gè)有限序列，表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)外，有且只有一個(gè)前件，除了最后一個(gè)外，有且只有一個(gè)后件。線性表可以為空表?！　【€性表的順序存儲(chǔ)結(jié)構(gòu)具有兩個(gè)基本特點(diǎn)：（1）線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。　　順序表的插入、刪除運(yùn)算（學(xué)吧學(xué)吧獨(dú)家稿件）　?。?）順序表的插入運(yùn)算：在一般情況下，要在第i（1≤i≤n）個(gè)元素之前插入一個(gè)新元素時(shí)，首先要從最后一個(gè)（即第n個(gè)）元素開始，直到第i個(gè)元素之間共ni+1個(gè)元素依次向后移動(dòng)一個(gè)位置，移動(dòng)結(jié)束后，第i個(gè)位置就被空出，然后將新元素插入到第i項(xiàng)。　　*：順性表的插入運(yùn)算時(shí)需要移動(dòng)元素，在等概率情況下，平均需要移動(dòng)n/2個(gè)元素。刪除結(jié)束后，線性表的長度就減小了1。插入、刪除運(yùn)算不方便?！　≡跅Ｖ校试S插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。即棧是按照“先進(jìn)后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的?！　５幕具\(yùn)算：1）插入元素稱為入棧運(yùn)算；2）刪除元素稱為退棧運(yùn)算；3）讀棧頂元素是將棧頂元素賦給一個(gè)指定的變量，此時(shí)指針無變化?！　￡?duì)列及其基本運(yùn)算　　隊(duì)列是指允許在一端（隊(duì)尾）進(jìn)入插入，而在另一端（隊(duì)頭）進(jìn)行刪除的線性表?！　￡?duì)列是“先進(jìn)先出”或“后進(jìn)后出”的線性表?！　⊙h(huán)隊(duì)列及其運(yùn)算：所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用?！　?：循環(huán)隊(duì)列中元素的個(gè)數(shù)=rearfront。在順序存儲(chǔ)的線性表中，插入或刪除數(shù)據(jù)元素時(shí)需要移動(dòng)大量的數(shù)據(jù)元素。(3)線性表的順序存儲(chǔ)結(jié)構(gòu)不便于對(duì)存儲(chǔ)空間的動(dòng)態(tài)分配。因此，在鏈?zhǔn)酱鎯?chǔ)方式中，每個(gè)結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素的值，稱為數(shù)據(jù)域?！　≡趩捂湵碇?，每一個(gè)結(jié)點(diǎn)只有一個(gè)指針域，由這個(gè)指針只能找到其后件結(jié)點(diǎn)，而不能找到其前件結(jié)點(diǎn)。另一個(gè)稱為右指針，指向其后件結(jié)點(diǎn)，這種鏈表稱為雙向鏈表，如下圖所示：　　線性鏈表的基本運(yùn)算　　(1)在線性鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個(gè)新元素?！　?2)在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)?！　?3)將兩個(gè)線性鏈表按要求合并成一個(gè)線性鏈表。　　(5)逆轉(zhuǎn)線性鏈表?！　?7)線性鏈表的排序?！　?：線性鏈表不能隨機(jī)存取（注釋2）。為了克服線性鏈表的這個(gè)缺點(diǎn)，可以采用另一種鏈接方式，即循環(huán)鏈表。2)循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不是空，而是指向表頭結(jié)點(diǎn)?！　∠聢Da是一個(gè)非空的循環(huán)鏈表，圖b是一個(gè)空的循環(huán)鏈表：　　循環(huán)鏈表的優(yōu)點(diǎn)主要體現(xiàn)在兩個(gè)方面：一是在循環(huán)鏈表中，只要指出表中任何一個(gè)結(jié)點(diǎn)的位置，就可以從它出發(fā)訪問到表中其他所有的結(jié)點(diǎn)，而線性單鏈表做不到這一點(diǎn)?！　?：循環(huán)鏈表是