計(jì)算機(jī)二級(jí)考試共公基礎(chǔ)講義教學(xué)課件

全國(guó)計(jì)算機(jī)二級(jí)公共基礎(chǔ)講義2020/12/121目錄第一章數(shù)據(jù)結(jié)構(gòu)與算法第二章程序設(shè)計(jì)基礎(chǔ)第三章軟件工程基礎(chǔ)第四章數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)2020/12/122第一章數(shù)據(jù)結(jié)構(gòu)與算法

本章應(yīng)考點(diǎn)撥：本章內(nèi)容在筆試中會(huì)出現(xiàn)5-6個(gè)題目，是公共基礎(chǔ)知識(shí)部分出題量比較多的一章，所占分值也比較大，約10分。2020/12/123第一章數(shù)據(jù)結(jié)構(gòu)與算法1.1算法

1、算法是指解題方案的準(zhǔn)確而完整的描述。換句話說(shuō)，算法是對(duì)特定問(wèn)題求解步驟的一種描述。*：算法不等于程序，也不等于計(jì)算方法。程序的編制不可能優(yōu)于算法的設(shè)計(jì)[wx1]

。

[wx1]這是因?yàn)椋涸诰帉?xiě)程序時(shí)要受到計(jì)算機(jī)系統(tǒng)運(yùn)行環(huán)境的限制，程序通常還要考慮很多與方法和分析無(wú)關(guān)的細(xì)節(jié)問(wèn)題。2020/12/1242、算法的基本特征

（1）可行性。針對(duì)實(shí)際問(wèn)題而設(shè)計(jì)的算法，執(zhí)行后能夠得到滿意的結(jié)果。

（2）確定性。每一條指令的含義明確，無(wú)二義性。并且在任何條件下，算法只有唯一的一條執(zhí)行路徑，即相同的輸入只能得出相同的輸出。（3）有窮性。算法必須在有限的時(shí)間內(nèi)完成。有兩重含義，一是算法中的操作步驟為有限個(gè)，二是每個(gè)步驟都能在有限時(shí)間內(nèi)完成。（4）擁有足夠的情報(bào)。一個(gè)算法執(zhí)行的結(jié)果總是與輸入的初始數(shù)據(jù)有關(guān)，不同的輸入將會(huì)有不同的結(jié)果輸出。當(dāng)輸入不夠或輸入錯(cuò)誤時(shí)，算法將無(wú)法執(zhí)行或執(zhí)行有錯(cuò)。一般說(shuō)來(lái)，當(dāng)算法擁有足夠的情報(bào)時(shí)，此算法才是有效的；而當(dāng)提供的情報(bào)不夠時(shí)，算法可能無(wú)效。2020/12/125什么叫算法呢?綜上所述，所謂算法，是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個(gè)規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。2020/12/1263、算法復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度。

（1）算法時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量，可以用執(zhí)行算法的過(guò)程中所需基本運(yùn)算的執(zhí)行次數(shù)來(lái)度量。

（2）算法空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。2020/12/1271.2數(shù)據(jù)結(jié)構(gòu)的基本概念

1、數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。2、數(shù)據(jù)結(jié)構(gòu)主要研究和討論以下三個(gè)方面的問(wèn)題：（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)包含：1）表示數(shù)據(jù)元素的信息；2）表示各數(shù)據(jù)元素之間的前后件關(guān)系[wx1]

。

（2）在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。

[wx1]前后件關(guān)系：一般情況下，在具有相同特征的數(shù)據(jù)元素集合中，各個(gè)數(shù)據(jù)元素之間存在某種關(guān)系（即聯(lián)系），這種關(guān)系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)。在數(shù)據(jù)處理領(lǐng)域中，通常把數(shù)據(jù)元素之間這種固有的關(guān)系簡(jiǎn)單地用前后件關(guān)系（即直接前驅(qū)與直接后繼關(guān)系）來(lái)描述。2020/12/128數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等。1）順序存儲(chǔ)。它是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。2）鏈接存儲(chǔ)。它不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3）索引存儲(chǔ)：除建立存儲(chǔ)結(jié)點(diǎn)信息外，還建立附加的索引表來(lái)標(biāo)識(shí)結(jié)點(diǎn)的地址。*：數(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ǔ)空間中的存放形式。同一種邏輯結(jié)構(gòu)的數(shù)據(jù)可以采用不同的存儲(chǔ)結(jié)構(gòu)，但影響數(shù)據(jù)處理效率。2020/12/1293、數(shù)據(jù)結(jié)構(gòu)的圖形表示一個(gè)數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外，還可以直觀地用圖形表示。在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，對(duì)于數(shù)據(jù)集合D中的每一個(gè)數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示，一般稱之為數(shù)據(jù)結(jié)點(diǎn)，并簡(jiǎn)稱為結(jié)點(diǎn)；為了進(jìn)一步表示各數(shù)據(jù)元素之間的前后件關(guān)系，對(duì)于關(guān)系R中的每一個(gè)二元組，用一條有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)。2020/12/12104、數(shù)據(jù)結(jié)構(gòu)分為兩大類型線性結(jié)構(gòu)和非線性結(jié)構(gòu)。（1）線性結(jié)構(gòu)（非空的數(shù)據(jù)結(jié)構(gòu)）條件：1）有且只有一個(gè)根結(jié)點(diǎn)[wx1]

；2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。

*：常見(jiàn)的線性結(jié)構(gòu)有線性表、棧、隊(duì)列和線性鏈表等。（2）非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。*：常見(jiàn)的非線性結(jié)構(gòu)有樹(shù)、二叉樹(shù)和圖等。

[wx1]在數(shù)據(jù)結(jié)構(gòu)中，沒(méi)有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)。2020/12/12111.3線性表及其順序存儲(chǔ)結(jié)構(gòu)

1、線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號(hào)，元素之間的相對(duì)位置是線性的。線性表是由n(n≥0)個(gè)數(shù)據(jù)元素組成的一個(gè)有限序列，表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)外，有且只有一個(gè)前件，除了最后一個(gè)外，有且只有一個(gè)后件。線性表中數(shù)據(jù)元素的個(gè)數(shù)稱為線性表的長(zhǎng)度。線性表可以為空表。*：線性表是一種存儲(chǔ)結(jié)構(gòu)，它的存儲(chǔ)方式：順序和鏈?zhǔn)健?020/12/12122、線性表的順序存儲(chǔ)結(jié)構(gòu)具有兩個(gè)基本特點(diǎn)：（1）線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。*：由此可以看出，在線性表的順序存儲(chǔ)結(jié)構(gòu)中，其前后件兩個(gè)元素在存儲(chǔ)空間中是緊鄰的，且前件元素一定存儲(chǔ)在后件元素的前面，可以通過(guò)計(jì)算機(jī)直接確定第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址。

2020/12/12133、順序表的插入、刪除運(yùn)算（1）順序表的插入運(yùn)算：在一般情況下，要在第i（1≤i≤n）個(gè)元素之前插入一個(gè)新元素時(shí)，首先要從最后一個(gè)（即第n個(gè)）元素開(kāi)始，直到第i個(gè)元素之間共n-i+1個(gè)元素依次向后移動(dòng)一個(gè)位置，移動(dòng)結(jié)束后，第i個(gè)位置就被空出，然后將新元素插入到第i項(xiàng)。插入結(jié)束后，線性表的長(zhǎng)度就增加了1。*：順性表的插入運(yùn)算時(shí)需要移動(dòng)元素，在等概率情況下，平均需要移動(dòng)n/2個(gè)元素。2020/12/1214（2）順序表的刪除運(yùn)算：在一般情況下，要?jiǎng)h除第i（1≤i≤n）個(gè)元素時(shí)，則要從第i+1個(gè)元素開(kāi)始，直到第n個(gè)元素之間共n-i個(gè)元素依次向前移動(dòng)一個(gè)位置。刪除結(jié)束后，線性表的長(zhǎng)度就減小了1。*：進(jìn)行順性表的刪除運(yùn)算時(shí)也需要移動(dòng)元素，在等概率情況下，平均需要移動(dòng)（n-1）/2個(gè)元素。插入、刪除運(yùn)算不方便。2020/12/12151.4棧和隊(duì)列

1、棧及其基本運(yùn)算棧是限定在一端進(jìn)行插入與刪除運(yùn)算的線性表。在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧頂元素總是最后被插入的元素，棧底元素總是最先被插入的元素。即棧是按照“先進(jìn)后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的。棧具有記憶作用。2020/12/1216棧的基本運(yùn)算：1）插入元素稱為入棧運(yùn)算；2）刪除元素稱為退棧運(yùn)算；3）讀棧頂元素是將棧頂元素賦給一個(gè)指定的變量，此時(shí)指針無(wú)變化。棧的存儲(chǔ)方式和線性表類似，也有兩種，即順序棧和鏈?zhǔn)綏！?020/12/12172、隊(duì)列及其基本運(yùn)算隊(duì)列是指允許在一端（隊(duì)尾）進(jìn)入插入，而在另一端（隊(duì)頭）進(jìn)行刪除的線性表。尾指針（Rear）指向隊(duì)尾元素，頭指針（front）指向排頭元素的前一個(gè)位置（隊(duì)頭）。隊(duì)列是“先進(jìn)先出”或“后進(jìn)后出”的線性表。2020/12/1218隊(duì)列運(yùn)算包括：1）入隊(duì)運(yùn)算：從隊(duì)尾插入一個(gè)元素；2）退隊(duì)運(yùn)算：從隊(duì)頭刪除一個(gè)元素。循環(huán)隊(duì)列及其運(yùn)算：所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用。在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用排頭指針front指向排頭元素的前一個(gè)位置，因此，從頭指針front指向的后一個(gè)位置直到隊(duì)尾指針rear指向的位置之間，所有的元素均為隊(duì)列中的元素。*：循環(huán)隊(duì)列中元素的個(gè)數(shù)=rear-front。2020/12/12191.5線性鏈表1、線性表順序存儲(chǔ)的缺點(diǎn)（1）插入或刪除的運(yùn)算效率很低。在順序存儲(chǔ)的線性表中，插入或刪除數(shù)據(jù)元素時(shí)需要移動(dòng)大量的數(shù)據(jù)元素；（2）線性表的順序存儲(chǔ)結(jié)構(gòu)下，線性表的存儲(chǔ)空間不便于擴(kuò)充；（3）線性表的順序存儲(chǔ)結(jié)構(gòu)不便于對(duì)存儲(chǔ)空間的動(dòng)態(tài)分配。2020/12/12202、線性鏈表：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表，是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接來(lái)實(shí)現(xiàn)的。因此，在鏈?zhǔn)酱鎯?chǔ)方式中，每個(gè)結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存放指針，稱為指針域，用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)（即前件或后件），如下圖所示：2020/12/1221線性鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表三種類型。在單鏈表中，每一個(gè)結(jié)點(diǎn)只有一個(gè)指針域，由這個(gè)指針只能找到其后件結(jié)點(diǎn)，而不能找到其前件結(jié)點(diǎn)。因此，在某些應(yīng)用中，對(duì)于線性鏈表中的每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針，一個(gè)稱為左指針，指向其前件結(jié)點(diǎn)；另一個(gè)稱為右指針，指向其后件結(jié)點(diǎn)，這種鏈表稱為雙向鏈表，如下圖所示：2020/12/12223、線性鏈表的基本運(yùn)算（1）在線性鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個(gè)新元素。*：在線性鏈表中插入元素時(shí)，不需要移動(dòng)數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點(diǎn)指針即可，也不會(huì)出現(xiàn)“上溢[wx1]

”現(xiàn)象（2）在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)。*：在線性鏈表中刪除元素時(shí)，也不需要移動(dòng)數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點(diǎn)指針即可。

[wx1]當(dāng)為一個(gè)線性表分配順序存儲(chǔ)結(jié)構(gòu)后，如果出現(xiàn)線性表的存儲(chǔ)空間已滿，但還需要插入新的元素時(shí)，就會(huì)發(fā)生“上溢”現(xiàn)象。2020/12/12233、線性鏈表的基本運(yùn)算（1）在線性鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個(gè)新元素。*：在線性鏈表中插入元素時(shí)，不需要移動(dòng)數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點(diǎn)指針即可，也不會(huì)出現(xiàn)“上溢[wx1]

”現(xiàn)象。（2）在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)。*：在線性鏈表中刪除元素時(shí)，也不需要移動(dòng)數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點(diǎn)指針即可。

[wx1]當(dāng)為一個(gè)線性表分配順序存儲(chǔ)結(jié)構(gòu)后，如果出現(xiàn)線性表的存儲(chǔ)空間已滿，但還需要插入新的元素時(shí)，就會(huì)發(fā)生“上溢”現(xiàn)象。2020/12/12244、循環(huán)鏈表及其基本運(yùn)算在線性鏈表中，其插入與刪除的運(yùn)算雖然比較方便，但還存在一個(gè)問(wèn)題，在運(yùn)算過(guò)程中對(duì)于空表和對(duì)第一個(gè)結(jié)點(diǎn)的處理必須單獨(dú)考慮，使空表與非空表的運(yùn)算不統(tǒng)一。為了克服線性鏈表的這個(gè)缺點(diǎn)，可以采用另一種鏈接方式，即循環(huán)鏈表。循環(huán)鏈表具有以下兩個(gè)特點(diǎn)：1）在鏈表中增加了一個(gè)表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蛘吒鶕?jù)需要來(lái)設(shè)置，指針域指向線性表的第一個(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)狀鏈。2020/12/1225循環(huán)鏈表的優(yōu)點(diǎn)主要體現(xiàn)在兩個(gè)方面：一是在循環(huán)鏈表中，只要指出表中任何一個(gè)結(jié)點(diǎn)的位置，就可以從它出發(fā)訪問(wèn)到表中其他所有的結(jié)點(diǎn)，而線性單鏈表做不到這一點(diǎn)；二是由于在循環(huán)鏈表中設(shè)置了一個(gè)表頭結(jié)點(diǎn)，在任何情況下，循環(huán)鏈表中至少有一個(gè)結(jié)點(diǎn)存在，從而使空表與非空表的運(yùn)算統(tǒng)一。*：循環(huán)鏈表是在單鏈表的基礎(chǔ)上增加了一個(gè)表頭結(jié)點(diǎn)，其插入和刪除運(yùn)算與單鏈表相同。但它可以從任一結(jié)點(diǎn)出發(fā)來(lái)訪問(wèn)表中其他所有結(jié)點(diǎn)，并實(shí)現(xiàn)空表與非空表的運(yùn)算的統(tǒng)一

2020/12/1226下圖a是一個(gè)非空的循環(huán)鏈表，圖b是一個(gè)空的循環(huán)鏈表：2020/12/12271.6樹(shù)與二叉樹(shù)1、樹(shù)的基本概念樹(shù)是一種簡(jiǎn)單的非線性結(jié)構(gòu)。在樹(shù)這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性。

在樹(shù)結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)。沒(méi)有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹(shù)的根結(jié)點(diǎn)，簡(jiǎn)稱樹(shù)的根。每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒(méi)有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。

在樹(shù)結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹(shù)的度。樹(shù)的最大層次稱為樹(shù)的深度。2020/12/12282、二叉樹(shù)及其基本性質(zhì)（1）什么是二叉樹(shù)二叉樹(shù)是一種很有用的非線性結(jié)構(gòu)，它具有以下兩個(gè)特點(diǎn)：1）非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)；2）每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，且分別稱為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)。*：根據(jù)二叉樹(shù)的概念可知，二叉樹(shù)的度可以為0（葉結(jié)點(diǎn)）、1（只有一棵子樹(shù)）或2（有2棵子樹(shù)）。

2020/12/1229（2）二叉樹(shù)的基本性質(zhì)

性質(zhì)1在二叉樹(shù)的第k層上，最多有個(gè)結(jié)點(diǎn)。性質(zhì)2深度為m的二叉樹(shù)最多有個(gè)個(gè)結(jié)點(diǎn)。性質(zhì)3在任意一棵二叉樹(shù)中，度數(shù)為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總比度為2的結(jié)點(diǎn)多一個(gè)。性質(zhì)4具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其深度至少為，其中表示取的整數(shù)部分。2020/12/12303、滿二叉樹(shù)與完全二叉樹(shù)滿二叉樹(shù)：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。完全二叉樹(shù)：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。*：根據(jù)完全二叉樹(shù)的定義可得出：度為1的結(jié)點(diǎn)的個(gè)數(shù)為0或1。2020/12/1231下圖a表示的是滿二叉樹(shù)，下圖b表示的是完全二叉樹(shù)：2020/12/1232完全二叉樹(shù)還具有如下兩個(gè)特性：性質(zhì)5具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)深度為。性質(zhì)6設(shè)完全二叉樹(shù)共有n個(gè)結(jié)點(diǎn)，如果從根結(jié)點(diǎn)開(kāi)始，按層序（每一層從左到右）用自然數(shù)1，2，…，n給結(jié)點(diǎn)進(jì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)；若k>1，則該結(jié)點(diǎn)的父結(jié)點(diǎn)的編號(hào)為INT(k/2)。②若2k≤n，則編號(hào)為k的左子結(jié)點(diǎn)編號(hào)為2k；否則該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)（顯然也沒(méi)有右子結(jié)點(diǎn)）。③若2k+1≤n，則編號(hào)為k的右子結(jié)點(diǎn)編號(hào)為2k+1；否則該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)。2020/12/12334、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)

在計(jì)算機(jī)中，二叉樹(shù)通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。與線性鏈表類似，用于存儲(chǔ)二叉樹(shù)中各元素的存儲(chǔ)結(jié)點(diǎn)也由兩部分組成：數(shù)據(jù)域和指針域。但在二叉樹(shù)中，由于每一個(gè)元素可以有兩個(gè)后件（即兩個(gè)子結(jié)點(diǎn)），因此，用于存儲(chǔ)二叉樹(shù)的存儲(chǔ)結(jié)點(diǎn)的指針域有兩個(gè)：一個(gè)用于指向該結(jié)點(diǎn)的左子結(jié)點(diǎn)的存儲(chǔ)地址，稱為左指針域；另一個(gè)用于指向該結(jié)點(diǎn)的右子結(jié)點(diǎn)的存儲(chǔ)地址，稱為右指針域。*：一般二叉樹(shù)通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，對(duì)于滿二叉樹(shù)與完全二叉樹(shù)來(lái)說(shuō)，可以按層序進(jìn)行順序存儲(chǔ)[wx1]

。

[wx1]這樣，不僅節(jié)省了存儲(chǔ)空間，又能方便地確定每一個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)與左右子結(jié)點(diǎn)的位置，但順序存儲(chǔ)結(jié)構(gòu)對(duì)于一般的二叉樹(shù)不適用。2020/12/12345、二叉樹(shù)的遍歷二叉樹(shù)的遍歷是指不重復(fù)地訪問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn)。二叉樹(shù)的遍歷可以分為以下三種：（1）前序遍歷（DLR）：若二叉樹(shù)為空，則結(jié)束返回。否則：首先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)；并且，在遍歷左右子樹(shù)時(shí)，仍然先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)。（2）中序遍歷（LDR）：若二叉樹(shù)為空，則結(jié)束返回。否則：首先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)；并且，在遍歷左、右子樹(shù)時(shí)，仍然先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)。

（3）后序遍歷（LRD）：若二叉樹(shù)為空，則結(jié)束返回。否則：首先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)，并且，在遍歷左、右子樹(shù)時(shí)，仍然先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。2020/12/1235(13)設(shè)一棵完全二叉樹(shù)共有699個(gè)結(jié)點(diǎn)，則在該二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)為_(kāi)_____。(b)a.349b.350c.255d.351(23)在深度為5的滿二叉樹(shù)中，葉子結(jié)點(diǎn)的個(gè)數(shù)為_(kāi)_____。(c)a.32b.31c.16d.152020/12/1236(3)在一棵二叉樹(shù)上第5層的結(jié)點(diǎn)數(shù)最多是______。(b)a.8b.16c.32d.15(33)設(shè)有下列二叉樹(shù)：對(duì)此二叉樹(shù)中序遍歷的結(jié)果為_(kāi)_____。(b)a.abcdefb.dbeafcc.abdecfd.debfca2020/12/1237(13)設(shè)一棵完全二叉樹(shù)共有699個(gè)結(jié)點(diǎn)，則在該二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)為_(kāi)_____。(b)a.349b.350c.255d.351(53)已知二叉樹(shù)后序遍歷序列是daBEC，中序遍歷序列是debac，它的前序遍歷序列是______。(a)a.cedbab.acbedc.decabd.deabc2020/12/1238(62)棧底至棧頂依次存放元素a、b、c、d，在第五個(gè)元素e入棧前，棧中元素可以出棧，則出棧序列可能是______。(d)a.abcedb.dbceac.cdabed.dcbea2020/12/12391.7查找技術(shù)查找：根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素。查找結(jié)果：（查找成功：找到；查找不成功：沒(méi)找到。）平均查找長(zhǎng)度：查找過(guò)程中關(guān)鍵字和給定值比較的平均次數(shù)。2020/12/12401、順序查找

基本思想：從表中的第一個(gè)元素開(kāi)始，將給定的值與表中逐個(gè)元素的關(guān)鍵字進(jìn)行比較，直到兩者相符，查到所要找的元素為止。否則就