二級(jí)公共基礎(chǔ)- ppt課件

1、二級(jí)公共根底知識(shí)二級(jí)公共根底知識(shí)第一章第一章 數(shù)據(jù)構(gòu)造根底數(shù)據(jù)構(gòu)造根底內(nèi)容提要內(nèi)容提要 n算法算法: :算法的根本概念、算法復(fù)雜度算法的根本概念、算法復(fù)雜度n數(shù)據(jù)構(gòu)造的根本概念：什么是數(shù)據(jù)構(gòu)造、數(shù)據(jù)構(gòu)造的根本概念：什么是數(shù)據(jù)構(gòu)造、 數(shù)據(jù)構(gòu)造的圖數(shù)據(jù)構(gòu)造的圖形表示、形表示、 線性構(gòu)造與非線性構(gòu)造線性構(gòu)造與非線性構(gòu)造n線性表及其順序存儲(chǔ)構(gòu)造：線性表的根本概念、線性表及其順序存儲(chǔ)構(gòu)造：線性表的根本概念、 順序存順序存儲(chǔ)構(gòu)造、插入運(yùn)算、刪除運(yùn)算儲(chǔ)構(gòu)造、插入運(yùn)算、刪除運(yùn)算n棧和隊(duì)列：棧及其根本運(yùn)算、隊(duì)列及其根本運(yùn)算棧和隊(duì)列：棧及其根本運(yùn)算、隊(duì)列及其根本運(yùn)算n線性鏈表：根本概念、根本運(yùn)算、循環(huán)鏈表及其根本

2、運(yùn)算線性鏈表：根本概念、根本運(yùn)算、循環(huán)鏈表及其根本運(yùn)算n樹(shù)與二叉樹(shù)：樹(shù)的根本概念、二叉樹(shù)及其根本性質(zhì)、樹(shù)與二叉樹(shù)：樹(shù)的根本概念、二叉樹(shù)及其根本性質(zhì)、 二二叉樹(shù)的存儲(chǔ)構(gòu)造、二叉樹(shù)的遍歷叉樹(shù)的存儲(chǔ)構(gòu)造、二叉樹(shù)的遍歷n查找技術(shù)：查找技術(shù)： 順序查找、二分法查找順序查找、二分法查找n排序技術(shù)：交換類排序法、排序技術(shù)：交換類排序法、 插入類排序法、選擇類排序插入類排序法、選擇類排序法法1.1 1.1 算法算法1.1.1 1.1.1 算法的根本概念算法的根本概念n算法是解題方案的準(zhǔn)確而完好的描畫(huà)，它不等于程序，也算法是解題方案的準(zhǔn)確而完好的描畫(huà)，它不等于程序，也不等計(jì)算方法。不等計(jì)算方法。n1 1算法的根

3、本特征算法的根本特征n可行性可行性(effectiveness)(effectiveness)n確定性確定性(definiteness)(definiteness)n有窮性有窮性(finiteness)(finiteness)n擁有足夠的情報(bào)擁有足夠的情報(bào)n2 2算法的根本要素算法的根本要素n算法中對(duì)數(shù)據(jù)的運(yùn)算和操作算法中對(duì)數(shù)據(jù)的運(yùn)算和操作n算術(shù)運(yùn)算算術(shù)運(yùn)算: :包括加、減、乘、除等包括加、減、乘、除等n邏輯運(yùn)算邏輯運(yùn)算: :包括包括“與、與、“或、或、“非等運(yùn)算非等運(yùn)算n關(guān)系運(yùn)算關(guān)系運(yùn)算: :包括包括“大于、大于、“小于、小于、“等于、等于、“不等于不等于等等n數(shù)據(jù)傳輸數(shù)據(jù)傳輸: :包括賦值

4、、輸入、輸出等操作包括賦值、輸入、輸出等操作n算法的控制構(gòu)造算法的控制構(gòu)造1.1.1 1.1.1 算法的根本概念算法的根本概念n3 3算法設(shè)計(jì)的根本方法算法設(shè)計(jì)的根本方法n列舉法列舉法n歸納法歸納法n遞推遞推n遞歸遞歸n減半遞推技術(shù)減半遞推技術(shù)n回溯法回溯法1.1.2 1.1.2 算法復(fù)雜度算法復(fù)雜度n算法復(fù)雜度：時(shí)間復(fù)雜度、空間復(fù)雜度算法復(fù)雜度：時(shí)間復(fù)雜度、空間復(fù)雜度n1 1算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度n執(zhí)行算法所需求的計(jì)算任務(wù)量執(zhí)行算法所需求的計(jì)算任務(wù)量n與以下要素有關(guān)：與以下要素有關(guān)：n書(shū)寫(xiě)算法的程序設(shè)計(jì)言語(yǔ)書(shū)寫(xiě)算法的程序設(shè)計(jì)言語(yǔ)n編譯產(chǎn)生的機(jī)器言語(yǔ)，代碼質(zhì)量編譯產(chǎn)生的機(jī)器言語(yǔ)，代碼

5、質(zhì)量n機(jī)器執(zhí)行指令的速度機(jī)器執(zhí)行指令的速度n問(wèn)題的規(guī)模問(wèn)題的規(guī)模1.1.2 1.1.2 算法復(fù)雜度算法復(fù)雜度n問(wèn)題的規(guī)模函數(shù)問(wèn)題的規(guī)模函數(shù)n算法的任務(wù)量算法的任務(wù)量=f(n)=f(n)n算法中根本操作反復(fù)執(zhí)行的頻率算法中根本操作反復(fù)執(zhí)行的頻率T(n)T(n)，是問(wèn)題規(guī)，是問(wèn)題規(guī)模模n n的某個(gè)函數(shù)的某個(gè)函數(shù)f(n)f(n)，記作：，記作：nT(n)=O(f(n)T(n)=O(f(n)n記號(hào)記號(hào)“O O讀作讀作“大大O O。表示隨問(wèn)題規(guī)模。表示隨問(wèn)題規(guī)模n n的添加，的添加，算法執(zhí)行時(shí)間的增長(zhǎng)率和算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)f(n)相應(yīng)添加。相應(yīng)添加。n常見(jiàn)算法復(fù)雜度：常見(jiàn)算法復(fù)雜度：nO(1

6、)O(1)：常數(shù)階：常數(shù)階 O(n) O(n)：作線性階：作線性階 O(n2) O(n2)：平方階平方階nO(n3)O(n3)：立方階：立方階 O(logn) O(logn)：對(duì)數(shù)階：對(duì)數(shù)階 O(2n) O(2n)：指數(shù)階指數(shù)階1.1.2 1.1.2 算法復(fù)雜度算法復(fù)雜度nn nn n矩陣相乘算法：矩陣相乘算法：n時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(n3)O(n3)。1.1.2 1.1.2 算法復(fù)雜度算法復(fù)雜度n分析算法的任務(wù)量?jī)煞N方法：分析算法的任務(wù)量?jī)煞N方法：n平均性態(tài)平均性態(tài)n最壞情況復(fù)雜性最壞情況復(fù)雜性1.1.2 1.1.2 算法復(fù)雜度算法復(fù)雜度n2算法的空間復(fù)雜度n算法執(zhí)行過(guò)程中所需的最大存

7、儲(chǔ)空間n存儲(chǔ)量包括以下三部分n算法程序所占的空間n輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間n算法執(zhí)行過(guò)程中所要的額外空間n算法空間復(fù)雜度可定義為：nS(n)=O(f(n)n原地任務(wù)(in place)的算法：記作O(1)n緊縮存儲(chǔ)技術(shù)1.2 1.2 數(shù)據(jù)構(gòu)造的根本概念數(shù)據(jù)構(gòu)造的根本概念1.2.1 1.2.1 什么是數(shù)據(jù)構(gòu)造什么是數(shù)據(jù)構(gòu)造n1 1數(shù)據(jù)構(gòu)造研討的主要內(nèi)容數(shù)據(jù)構(gòu)造研討的主要內(nèi)容n數(shù)據(jù)的邏輯構(gòu)造數(shù)據(jù)的邏輯構(gòu)造n數(shù)據(jù)的存儲(chǔ)構(gòu)造數(shù)據(jù)的存儲(chǔ)構(gòu)造n對(duì)各種數(shù)據(jù)構(gòu)造進(jìn)展的運(yùn)算對(duì)各種數(shù)據(jù)構(gòu)造進(jìn)展的運(yùn)算n2 2研討數(shù)據(jù)構(gòu)造目的研討數(shù)據(jù)構(gòu)造目的n提高數(shù)據(jù)處置的速度提高數(shù)據(jù)處置的速度n盡量節(jié)省在數(shù)據(jù)處置過(guò)程中所占用的

8、計(jì)算盡量節(jié)省在數(shù)據(jù)處置過(guò)程中所占用的計(jì)算機(jī)存儲(chǔ)空間機(jī)存儲(chǔ)空間1.2.1 1.2.1 什么是數(shù)據(jù)構(gòu)造什么是數(shù)據(jù)構(gòu)造n1 1數(shù)據(jù)構(gòu)造研討的主要內(nèi)容數(shù)據(jù)構(gòu)造研討的主要內(nèi)容n數(shù)據(jù)的邏輯構(gòu)造數(shù)據(jù)的邏輯構(gòu)造n數(shù)據(jù)的存儲(chǔ)構(gòu)造數(shù)據(jù)的存儲(chǔ)構(gòu)造n對(duì)各種數(shù)據(jù)構(gòu)造進(jìn)展的運(yùn)算對(duì)各種數(shù)據(jù)構(gòu)造進(jìn)展的運(yùn)算n2 2研討數(shù)據(jù)構(gòu)造目的研討數(shù)據(jù)構(gòu)造目的n提高數(shù)據(jù)處置的速度提高數(shù)據(jù)處置的速度n盡量節(jié)省在數(shù)據(jù)處置過(guò)程中所占用的計(jì)算盡量節(jié)省在數(shù)據(jù)處置過(guò)程中所占用的計(jì)算機(jī)存儲(chǔ)空間機(jī)存儲(chǔ)空間1.2.1 1.2.1 什么是數(shù)據(jù)構(gòu)造什么是數(shù)據(jù)構(gòu)造 1數(shù)據(jù)的邏輯構(gòu)造 2、數(shù)據(jù)的存儲(chǔ)構(gòu)造 3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修正等。 A線性構(gòu)造

9、B非線性構(gòu)造A 順序存儲(chǔ) B 鏈?zhǔn)酱鎯?chǔ) 線性表?xiàng)ｊ?duì)樹(shù)形構(gòu)造圖形構(gòu)造數(shù)據(jù)構(gòu)造的三個(gè)方面 1.2.1 1.2.1 什么是數(shù)據(jù)構(gòu)造什么是數(shù)據(jù)構(gòu)造n3數(shù)據(jù)構(gòu)造的定義n相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合n數(shù)據(jù)元素之間的關(guān)系可以用前后件關(guān)系來(lái)描畫(huà)n一個(gè)數(shù)據(jù)構(gòu)造應(yīng)包含以下兩方面信息：n表示數(shù)據(jù)元素的信息 n表示各數(shù)據(jù)元素之間的前后件關(guān)系1.2.1 1.2.1 什么是數(shù)據(jù)構(gòu)造什么是數(shù)據(jù)構(gòu)造n4 4數(shù)據(jù)的邏輯構(gòu)造數(shù)據(jù)的邏輯構(gòu)造n對(duì)數(shù)據(jù)元素之間的邏輯關(guān)系的描畫(huà)對(duì)數(shù)據(jù)元素之間的邏輯關(guān)系的描畫(huà)n只籠統(tǒng)地反映數(shù)據(jù)元素之間的邏輯關(guān)系，只籠統(tǒng)地反映數(shù)據(jù)元素之間的邏輯關(guān)系，與計(jì)算機(jī)中的存儲(chǔ)無(wú)關(guān)與計(jì)算機(jī)中的存儲(chǔ)無(wú)關(guān)n兩個(gè)要素：兩個(gè)要素

10、：n數(shù)據(jù)元素的集合，通常記為數(shù)據(jù)元素的集合，通常記為D D；n前后件關(guān)系，通常記為前后件關(guān)系，通常記為R Rn一個(gè)數(shù)據(jù)構(gòu)造一個(gè)數(shù)據(jù)構(gòu)造B B可以表示為：可以表示為：nB=B=D D，R R1.2.1 1.2.1 什么是數(shù)據(jù)構(gòu)造什么是數(shù)據(jù)構(gòu)造n5 5數(shù)據(jù)的存儲(chǔ)構(gòu)造數(shù)據(jù)的存儲(chǔ)構(gòu)造n數(shù)據(jù)的邏輯構(gòu)造在計(jì)算機(jī)存儲(chǔ)空間中的存數(shù)據(jù)的邏輯構(gòu)造在計(jì)算機(jī)存儲(chǔ)空間中的存放方式放方式n常用的存儲(chǔ)構(gòu)造：常用的存儲(chǔ)構(gòu)造：n順序順序n鏈?zhǔn)芥準(zhǔn)絥索引索引n一種數(shù)據(jù)構(gòu)造可根據(jù)需求采用不同的存儲(chǔ)一種數(shù)據(jù)構(gòu)造可根據(jù)需求采用不同的存儲(chǔ)構(gòu)造。采用不同的存儲(chǔ)構(gòu)造，其數(shù)據(jù)處置構(gòu)造。采用不同的存儲(chǔ)構(gòu)造，其數(shù)據(jù)處置的效率是不同的效率是不同1.

11、2.2 1.2.2 數(shù)據(jù)構(gòu)造的圖形表示數(shù)據(jù)構(gòu)造的圖形表示n數(shù)據(jù)結(jié)點(diǎn)：用方框表示數(shù)據(jù)結(jié)點(diǎn)：用方框表示n根結(jié)點(diǎn)、終端結(jié)點(diǎn)根結(jié)點(diǎn)、終端結(jié)點(diǎn)n前后件關(guān)系：用有向線段表示前后件關(guān)系：用有向線段表示n根本運(yùn)算：根本運(yùn)算：n插入運(yùn)算插入運(yùn)算n刪除運(yùn)算刪除運(yùn)算n查找、分類、合并、分解、復(fù)制、修正、查找、分類、合并、分解、復(fù)制、修正、1.2.3 1.2.3 線性構(gòu)造與非線性構(gòu)造線性構(gòu)造與非線性構(gòu)造n空的數(shù)據(jù)構(gòu)造：一個(gè)數(shù)據(jù)元素都沒(méi)有空的數(shù)據(jù)構(gòu)造：一個(gè)數(shù)據(jù)元素都沒(méi)有n線性構(gòu)造線性構(gòu)造n假設(shè)一個(gè)非空數(shù)據(jù)構(gòu)造滿足以下兩個(gè)條件：假設(shè)一個(gè)非空數(shù)據(jù)構(gòu)造滿足以下兩個(gè)條件：n有且只需一個(gè)根結(jié)點(diǎn)；有且只需一個(gè)根結(jié)點(diǎn)；n每一個(gè)結(jié)點(diǎn)最

12、多有一個(gè)前件，也最多有一每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。個(gè)后件。n常見(jiàn)的線性構(gòu)造有：線性表、棧與隊(duì)列、常見(jiàn)的線性構(gòu)造有：線性表、棧與隊(duì)列、線性鏈表線性鏈表n非線性構(gòu)造非線性構(gòu)造n假設(shè)一個(gè)數(shù)據(jù)構(gòu)造不是線性構(gòu)造假設(shè)一個(gè)數(shù)據(jù)構(gòu)造不是線性構(gòu)造n常見(jiàn)的非線性構(gòu)造有：樹(shù)、二叉樹(shù)、圖常見(jiàn)的非線性構(gòu)造有：樹(shù)、二叉樹(shù)、圖1.3 1.3 線性表及其順序存儲(chǔ)構(gòu)造線性表及其順序存儲(chǔ)構(gòu)造1.3.1 1.3.1 線性表的根本概念線性表的根本概念n線性表：由線性表：由n(n0)n(n0)個(gè)一樣類型數(shù)據(jù)元素構(gòu)成的有個(gè)一樣類型數(shù)據(jù)元素構(gòu)成的有限序列：限序列：nn n定義為線性表的表長(zhǎng)；定義為線性表的表長(zhǎng)；n=0 n

13、=0 時(shí)的線性表被稱為空時(shí)的線性表被稱為空表。稱表。稱i i為在線性表中的位序。為在線性表中的位序。n例如：例如：n英文大寫(xiě)字母表英文大寫(xiě)字母表nA A，B B，C C，D D，E E，F(xiàn) F，XX，Y Y，Z Zn同一花樣的同一花樣的1313張撲克牌張撲克牌 n(2,3,4,5,6,7,8,9,10,J,Q,K,A)(2,3,4,5,6,7,8,9,10,J,Q,K,A),(21niaaaa1.3.1 1.3.1 線性表的根本概念線性表的根本概念n線性表的構(gòu)造特征線性表的構(gòu)造特征n數(shù)據(jù)元素在表中的位置由序號(hào)決議，數(shù)據(jù)數(shù)據(jù)元素在表中的位置由序號(hào)決議，數(shù)據(jù)元素之間的相對(duì)位置是線性的；元素之間的相

14、對(duì)位置是線性的；n對(duì)于一個(gè)非空線性表，有且只需一個(gè)根結(jié)對(duì)于一個(gè)非空線性表，有且只需一個(gè)根結(jié)點(diǎn)點(diǎn)a1a1，它無(wú)前件，有且只需一個(gè)終端結(jié)點(diǎn)，它無(wú)前件，有且只需一個(gè)終端結(jié)點(diǎn)anan，它無(wú)后件，除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，它無(wú)后件，除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他一切結(jié)點(diǎn)有且只需一個(gè)前件，也有且其他一切結(jié)點(diǎn)有且只需一個(gè)前件，也有且只需一個(gè)后件。只需一個(gè)后件。n線性表的存儲(chǔ)構(gòu)造線性表的存儲(chǔ)構(gòu)造n順序存儲(chǔ)順序存儲(chǔ)n鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)1.3.2 1.3.2 線性表的順序存儲(chǔ)構(gòu)造線性表的順序存儲(chǔ)構(gòu)造n兩個(gè)根本特點(diǎn)：兩個(gè)根本特點(diǎn)：n線性表中一切元素所占的存儲(chǔ)空間是延續(xù)的。線性表中一切元素所占的存儲(chǔ)空間是延續(xù)的。n線性表中各數(shù)

15、據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。放的。n存儲(chǔ)表示圖存儲(chǔ)表示圖kiaLocaLoci*) 1()()(11.3.3 1.3.3 順序表的插入運(yùn)算順序表的插入運(yùn)算1.3.4 1.3.4 順序表的刪除運(yùn)算順序表的刪除運(yùn)算順序表的插入和刪除分析順序表的插入和刪除分析n插入算法的分析插入算法的分析n假設(shè)線性表中含有假設(shè)線性表中含有n n個(gè)數(shù)據(jù)元素，在進(jìn)展插入操作時(shí)，假設(shè)假定在個(gè)數(shù)據(jù)元素，在進(jìn)展插入操作時(shí)，假設(shè)假定在n+1n+1個(gè)位置上插入元素的能夠性均等，那么平均挪動(dòng)元素的個(gè)數(shù)為：個(gè)位置上插入元素的能夠性均等，那么平均挪動(dòng)元素的個(gè)數(shù)為：n刪除算法

16、的分析刪除算法的分析n在進(jìn)展刪除操作時(shí)，假設(shè)假定刪除每個(gè)元素的能夠性均等，那么平均在進(jìn)展刪除操作時(shí)，假設(shè)假定刪除每個(gè)元素的能夠性均等，那么平均挪動(dòng)元素的個(gè)數(shù)為：挪動(dòng)元素的個(gè)數(shù)為：n分析結(jié)論分析結(jié)論n順序存儲(chǔ)構(gòu)造表示的線性表，在做插入或刪除操作時(shí)，平均需求挪動(dòng)順序存儲(chǔ)構(gòu)造表示的線性表，在做插入或刪除操作時(shí)，平均需求挪動(dòng)大約一半的數(shù)據(jù)元素。當(dāng)線性表的數(shù)據(jù)元素量較大，并且經(jīng)常要對(duì)其大約一半的數(shù)據(jù)元素。當(dāng)線性表的數(shù)據(jù)元素量較大，并且經(jīng)常要對(duì)其做插入或刪除操作時(shí)，這一點(diǎn)需求值得思索做插入或刪除操作時(shí)，這一點(diǎn)需求值得思索niidlninpnE121)(1112) 1(11niiisninpnE1.4 1.

17、4 棧和隊(duì)列棧和隊(duì)列1.4.1 1.4.1 棧及其根本運(yùn)算棧及其根本運(yùn)算n1 1棧的定義棧的定義n棧棧stackstack：一種只允許在表的一端進(jìn)展插入或：一種只允許在表的一端進(jìn)展插入或刪除操作的特殊的線性表刪除操作的特殊的線性表n棧頂棧頂(top) (top) ：允許進(jìn)展插入與刪除操作的一端：允許進(jìn)展插入與刪除操作的一端n棧底棧底(bottom)(bottom)：不允許插入與刪除操作的另一端：不允許插入與刪除操作的另一端n先進(jìn)后出先進(jìn)后出FILOFILO或后進(jìn)先出或后進(jìn)先出(LIFO)(LIFO)的線性表的線性表1.4.1 1.4.1 棧及其根本運(yùn)算棧及其根本運(yùn)算n2棧的順序存儲(chǔ)及其運(yùn)算nt

18、op=0：?？?top=m：棧滿n棧的根本運(yùn)算 n入棧運(yùn)算n退棧運(yùn)算n讀棧頂元素1.4.2 1.4.2 隊(duì)列及其根本運(yùn)算隊(duì)列及其根本運(yùn)算n1 1隊(duì)列的定義隊(duì)列的定義n限定只能在表的一端進(jìn)展插入和在另一端進(jìn)展刪除操作的限定只能在表的一端進(jìn)展插入和在另一端進(jìn)展刪除操作的線性表線性表n隊(duì)尾隊(duì)尾(rear)(rear)：允許插入的一端：允許插入的一端n隊(duì)頭隊(duì)頭(front)(front)：允許刪除的另一端：允許刪除的另一端n先進(jìn)先出先進(jìn)先出FIFOFIFO表或后進(jìn)后出表或后進(jìn)后出LILOLILO線性表線性表n根本操作根本操作n入隊(duì)運(yùn)算：往隊(duì)列的隊(duì)尾插入一個(gè)元素，隊(duì)尾指針入隊(duì)運(yùn)算：往隊(duì)列的隊(duì)尾插入一個(gè)元

19、素，隊(duì)尾指針rearrear的的變化變化n退隊(duì)運(yùn)算：從隊(duì)列的排頭刪除一個(gè)元素，隊(duì)頭指針退隊(duì)運(yùn)算：從隊(duì)列的排頭刪除一個(gè)元素，隊(duì)頭指針frontfront的變化的變化1.4.2 1.4.2 隊(duì)列及其根本運(yùn)算隊(duì)列及其根本運(yùn)算n2 2循環(huán)隊(duì)列及其運(yùn)算循環(huán)隊(duì)列及其運(yùn)算n隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，構(gòu)成邏輯隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，構(gòu)成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)運(yùn)用上的環(huán)狀空間，供隊(duì)列循環(huán)運(yùn)用 n入隊(duì)運(yùn)算入隊(duì)運(yùn)算 ：隊(duì)尾指針加：隊(duì)尾指針加1 1，并當(dāng)，并當(dāng)rear=m+1rear=m+1時(shí)置時(shí)置rear=1rear=1n出隊(duì)運(yùn)算：隊(duì)頭指針加出隊(duì)運(yùn)算：隊(duì)頭指針加1 1，并當(dāng)，

20、并當(dāng)front=m+1front=m+1時(shí)置時(shí)置front=1front=11.5 1.5 線性鏈表線性鏈表1.5.1 1.5.1 線性鏈表的根本概念線性鏈表的根本概念n1 1線性表順序存儲(chǔ)的缺陷線性表順序存儲(chǔ)的缺陷n插入或刪除的運(yùn)算效率很低。在順序存儲(chǔ)插入或刪除的運(yùn)算效率很低。在順序存儲(chǔ)的線性表中，插入或刪除數(shù)據(jù)元素時(shí)需求的線性表中，插入或刪除數(shù)據(jù)元素時(shí)需求挪動(dòng)大量的數(shù)據(jù)元素。挪動(dòng)大量的數(shù)據(jù)元素。n線性表的順序存儲(chǔ)構(gòu)造下，線性表的存儲(chǔ)線性表的順序存儲(chǔ)構(gòu)造下，線性表的存儲(chǔ)空間不便于擴(kuò)展?？臻g不便于擴(kuò)展。n線性表的順序存儲(chǔ)構(gòu)造不便于對(duì)存儲(chǔ)空間線性表的順序存儲(chǔ)構(gòu)造不便于對(duì)存儲(chǔ)空間的動(dòng)態(tài)分配。的動(dòng)態(tài)

21、分配。1.5.1 1.5.1 線性鏈表的根本概念線性鏈表的根本概念n2 2線性鏈表線性鏈表n線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造n物理存儲(chǔ)單元上非延續(xù)、非順序的存儲(chǔ)構(gòu)物理存儲(chǔ)單元上非延續(xù)、非順序的存儲(chǔ)構(gòu)造，數(shù)據(jù)元素的邏輯順序是經(jīng)過(guò)鏈表中的造，數(shù)據(jù)元素的邏輯順序是經(jīng)過(guò)鏈表中的指針鏈接來(lái)實(shí)現(xiàn)的指針鏈接來(lái)實(shí)現(xiàn)的n每個(gè)結(jié)點(diǎn)由兩部分組成：數(shù)據(jù)域和指針域每個(gè)結(jié)點(diǎn)由兩部分組成：數(shù)據(jù)域和指針域1.5.1 1.5.1 線性鏈表的根本概念線性鏈表的根本概念n雙向鏈表：每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針雙向鏈表：每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針n左指針：指向其前件結(jié)點(diǎn)左指針：指向其前件結(jié)點(diǎn)n右指針：指向其后件結(jié)點(diǎn)右指針：指向其后件結(jié)點(diǎn)1

22、.5.2 1.5.2 線性鏈表的根本運(yùn)算線性鏈表的根本運(yùn)算n插入插入n刪除刪除n合并合并n分解分解n逆轉(zhuǎn)逆轉(zhuǎn)n復(fù)制復(fù)制n排序排序n查找查找1.5.2 1.5.2 線性鏈表的根本運(yùn)算線性鏈表的根本運(yùn)算n1 1在線性鏈表中查找指定元素在線性鏈表中查找指定元素n鏈表不是隨機(jī)存取構(gòu)造鏈表不是隨機(jī)存取構(gòu)造n從鏈表的頭指針出發(fā)，順著鏈域從鏈表的頭指針出發(fā)，順著鏈域nextnext逐個(gè)逐個(gè)結(jié)點(diǎn)往下搜索，直至搜索到第結(jié)點(diǎn)往下搜索，直至搜索到第i i個(gè)結(jié)點(diǎn)為止個(gè)結(jié)點(diǎn)為止n2 2線性鏈表的插入線性鏈表的插入1.5.2 1.5.2 線性鏈表的根本運(yùn)算線性鏈表的根本運(yùn)算n3 3線性鏈表的刪除線性鏈表的刪除n與順序存儲(chǔ)

23、相比，鏈表的優(yōu)點(diǎn)有：與順序存儲(chǔ)相比，鏈表的優(yōu)點(diǎn)有：n插入和刪除元素時(shí)，不需求挪動(dòng)數(shù)據(jù)元素，插入和刪除元素時(shí)，不需求挪動(dòng)數(shù)據(jù)元素，只需求修正指針即可只需求修正指針即可 1.5.3 1.5.3 棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)構(gòu)造棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)構(gòu)造 n1棧的鏈?zhǔn)酱鎯?chǔ)構(gòu)造鏈棧1.5.3 1.5.3 棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)構(gòu)造棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)構(gòu)造 n2隊(duì)列鏈?zhǔn)酱鎯?chǔ)構(gòu)造鏈隊(duì)列1.5.4 1.5.4 循環(huán)鏈表及其根本運(yùn)算循環(huán)鏈表及其根本運(yùn)算n循環(huán)鏈表特點(diǎn)：循環(huán)鏈表特點(diǎn)：n在鏈表中添加了一個(gè)表頭結(jié)點(diǎn)在鏈表中添加了一個(gè)表頭結(jié)點(diǎn)n最后一個(gè)結(jié)點(diǎn)的指針域指向表頭結(jié)點(diǎn)，構(gòu)成了一最后一個(gè)結(jié)點(diǎn)的指針域指向表頭結(jié)點(diǎn)，構(gòu)成了一個(gè)環(huán)狀鏈個(gè)

24、環(huán)狀鏈n循環(huán)鏈表優(yōu)點(diǎn)：循環(huán)鏈表優(yōu)點(diǎn)：n從任一結(jié)點(diǎn)出發(fā)來(lái)訪問(wèn)表中其他一切結(jié)點(diǎn)從任一結(jié)點(diǎn)出發(fā)來(lái)訪問(wèn)表中其他一切結(jié)點(diǎn)n空表與非空表的運(yùn)算的一致空表與非空表的運(yùn)算的一致 1.6 1.6 樹(shù)與二叉樹(shù)樹(shù)與二叉樹(shù)n1樹(shù)的定義n樹(shù)(Tree)是n(n0)個(gè)結(jié)點(diǎn)的有限集T，T為空時(shí)稱為空樹(shù)，否那么它滿足如下兩個(gè)條件：n1有且僅有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn)；n2其他的結(jié)點(diǎn)可分為m(m0)個(gè)互不相交的子集T1，T2，T3，Tm，其中每個(gè)子集又是一棵樹(shù)，并稱其為子樹(shù)。1.6 1.6 樹(shù)與二叉樹(shù)樹(shù)與二叉樹(shù)n2 2樹(shù)中的根本概念樹(shù)中的根本概念n父結(jié)點(diǎn)與樹(shù)的根：每個(gè)結(jié)點(diǎn)最多只允許有一個(gè)前父結(jié)點(diǎn)與樹(shù)的根：每個(gè)結(jié)點(diǎn)最多

25、只允許有一個(gè)前件，稱為該結(jié)點(diǎn)的父結(jié)點(diǎn)。沒(méi)有前件的結(jié)點(diǎn)中有件，稱為該結(jié)點(diǎn)的父結(jié)點(diǎn)。沒(méi)有前件的結(jié)點(diǎn)中有一個(gè)，稱為樹(shù)的根結(jié)點(diǎn)。一個(gè)，稱為樹(shù)的根結(jié)點(diǎn)。n子結(jié)點(diǎn)與葉子結(jié)點(diǎn)：在樹(shù)構(gòu)造中，每一個(gè)結(jié)點(diǎn)可子結(jié)點(diǎn)與葉子結(jié)點(diǎn)：在樹(shù)構(gòu)造中，每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，它們都稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒(méi)以有多個(gè)后件，它們都稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒(méi)有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。n結(jié)點(diǎn)的度和樹(shù)的度：一個(gè)結(jié)點(diǎn)所擁有后件個(gè)數(shù)稱結(jié)點(diǎn)的度和樹(shù)的度：一個(gè)結(jié)點(diǎn)所擁有后件個(gè)數(shù)稱為該結(jié)點(diǎn)的度。一棵樹(shù)中各個(gè)結(jié)點(diǎn)度數(shù)的最大值為該結(jié)點(diǎn)的度。一棵樹(shù)中各個(gè)結(jié)點(diǎn)度數(shù)的最大值叫做這棵樹(shù)的度。叫做這棵樹(shù)的度。n層和樹(shù)的深度：樹(shù)構(gòu)造是一種層次構(gòu)

26、造，根結(jié)點(diǎn)層和樹(shù)的深度：樹(shù)構(gòu)造是一種層次構(gòu)造，根結(jié)點(diǎn)為第一層，根的子結(jié)點(diǎn)為第二層，其他各結(jié)點(diǎn)的為第一層，根的子結(jié)點(diǎn)為第二層，其他各結(jié)點(diǎn)的層數(shù)逐層由上而下計(jì)算。一棵樹(shù)中結(jié)點(diǎn)的最大層層數(shù)逐層由上而下計(jì)算。一棵樹(shù)中結(jié)點(diǎn)的最大層數(shù)叫做此樹(shù)的深度。數(shù)叫做此樹(shù)的深度。1.6.1 1.6.1 樹(shù)的根本概念樹(shù)的根本概念n樹(shù)的特點(diǎn)樹(shù)的特點(diǎn)n1 1樹(shù)中只需根結(jié)點(diǎn)沒(méi)有前件；樹(shù)中只需根結(jié)點(diǎn)沒(méi)有前件；n2 2除根外，其他結(jié)點(diǎn)都有且僅一個(gè)前件；除根外，其他結(jié)點(diǎn)都有且僅一個(gè)前件；n3 3樹(shù)的結(jié)點(diǎn)，可以有零個(gè)或多個(gè)后件；樹(shù)的結(jié)點(diǎn)，可以有零個(gè)或多個(gè)后件；n4 4除根外的其他結(jié)點(diǎn)，都存在獨(dú)一條從根到該除根外的其他結(jié)點(diǎn)，都存在獨(dú)一

27、條從根到該結(jié)點(diǎn)的途徑；結(jié)點(diǎn)的途徑；n5 5樹(shù)是一種分支構(gòu)造除根的結(jié)點(diǎn)外每個(gè)元樹(shù)是一種分支構(gòu)造除根的結(jié)點(diǎn)外每個(gè)元素都有且僅有一個(gè)直接前件，有且僅有零個(gè)或多素都有且僅有一個(gè)直接前件，有且僅有零個(gè)或多個(gè)直接后件。個(gè)直接后件。n樹(shù)的存儲(chǔ)樹(shù)的存儲(chǔ)n用多重鏈表來(lái)表示用多重鏈表來(lái)表示1.6.2 1.6.2 二叉樹(shù)及其根本性質(zhì)二叉樹(shù)及其根本性質(zhì)n1 1二叉樹(shù)的定義二叉樹(shù)的定義n一個(gè)二叉樹(shù)是一個(gè)二叉樹(shù)是n n個(gè)結(jié)點(diǎn)的有限集合個(gè)結(jié)點(diǎn)的有限集合n0n0，此集合或者，此集合或者是空集是空集n=0n=0，或者是由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的、，或者是由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的、分別稱為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成，并且左

28、右子樹(shù)都分別稱為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成，并且左右子樹(shù)都是二叉樹(shù)。是二叉樹(shù)。n特點(diǎn)：特點(diǎn)：n非空二叉樹(shù)只需一個(gè)根結(jié)點(diǎn)；非空二叉樹(shù)只需一個(gè)根結(jié)點(diǎn)；n每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，且分別稱為該結(jié)點(diǎn)的左子樹(shù)每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，且分別稱為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)。與右子樹(shù)。1.6.2 1.6.2 二叉樹(shù)及其根本性質(zhì)二叉樹(shù)及其根本性質(zhì)n2 2二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì)n性質(zhì)性質(zhì)1 1 在二叉樹(shù)的第在二叉樹(shù)的第k k層上，最多有層上，最多有 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。n性質(zhì)性質(zhì)2 2 深度為深度為m m的二叉樹(shù)最多有個(gè)的二叉樹(shù)最多有個(gè) 結(jié)點(diǎn)。結(jié)點(diǎn)。n性質(zhì)性質(zhì)3 3 在恣意一棵二叉樹(shù)中，度數(shù)為在恣意一棵二叉樹(shù)中，度數(shù)

29、為0 0的結(jié)點(diǎn)的結(jié)點(diǎn)即葉子結(jié)點(diǎn)總比度為即葉子結(jié)點(diǎn)總比度為2 2的結(jié)點(diǎn)多一個(gè)。即：的結(jié)點(diǎn)多一個(gè)。即：n 其中，其中，n0n0表示度數(shù)為表示度數(shù)為0 0的結(jié)點(diǎn)數(shù)，的結(jié)點(diǎn)數(shù)，n2n2表示度數(shù)表示度數(shù)為為2 2的結(jié)點(diǎn)數(shù)。的結(jié)點(diǎn)數(shù)。n性質(zhì)性質(zhì)4 4 具有具有n n個(gè)結(jié)點(diǎn)的二叉樹(shù)的深度至少個(gè)結(jié)點(diǎn)的二叉樹(shù)的深度至少為為 ，其中，其中 表示取表示取 的整數(shù)部分。的整數(shù)部分。)1(21kk12 m120 nn1log2nlog2nn2log1.6.2 1.6.2 二叉樹(shù)及其根本性質(zhì)二叉樹(shù)及其根本性質(zhì)n3滿二叉樹(shù)和完全二叉樹(shù)n滿二叉樹(shù)：除最后一層外，每一層上的一切結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。n完全二叉樹(shù)：除最后一層外，每

30、一層上的結(jié)點(diǎn)數(shù)均到達(dá)最大值；在最后一層上只短少右邊的假設(shè)干結(jié)點(diǎn)。1.6.2 1.6.2 二叉樹(shù)及其根本性質(zhì)二叉樹(shù)及其根本性質(zhì)n性質(zhì)性質(zhì)5 5 具有具有n n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)深度為個(gè)結(jié)點(diǎn)的完全二叉樹(shù)深度為 。n性質(zhì)性質(zhì)6 6 設(shè)完全二叉樹(shù)共有設(shè)完全二叉樹(shù)共有n n個(gè)結(jié)點(diǎn)，假設(shè)從根結(jié)點(diǎn)開(kāi)場(chǎng)，個(gè)結(jié)點(diǎn)，假設(shè)從根結(jié)點(diǎn)開(kāi)場(chǎng)，按層序每一層從左到右用自然數(shù)按層序每一層從左到右用自然數(shù)1 1，2 2，n n給結(jié)點(diǎn)給結(jié)點(diǎn)進(jìn)展編號(hào)，那么對(duì)于編號(hào)為進(jìn)展編號(hào)，那么對(duì)于編號(hào)為k kk=1k=1，2 2，n n的結(jié)點(diǎn)有的結(jié)點(diǎn)有以下結(jié)論：以下結(jié)論：n假設(shè)假設(shè)k=1k=1，那么該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒(méi)有父結(jié)點(diǎn)；假設(shè)，那么該結(jié)點(diǎn)為

31、根結(jié)點(diǎn)，它沒(méi)有父結(jié)點(diǎn)；假設(shè)k1k1，那么該結(jié)點(diǎn)的父結(jié)點(diǎn)的編號(hào)為，那么該結(jié)點(diǎn)的父結(jié)點(diǎn)的編號(hào)為INT(k/2)INT(k/2)。n假設(shè)假設(shè)2kn2kn，那么編號(hào)為，那么編號(hào)為k k的左子結(jié)點(diǎn)編號(hào)為的左子結(jié)點(diǎn)編號(hào)為2k2k；否那么；否那么該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)顯然也沒(méi)有右子結(jié)點(diǎn)。該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)顯然也沒(méi)有右子結(jié)點(diǎn)。n假設(shè)假設(shè)2k+1n2k+1n，那么編號(hào)為，那么編號(hào)為k k的右子結(jié)點(diǎn)編號(hào)為的右子結(jié)點(diǎn)編號(hào)為2k+12k+1；否；否那么該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)。那么該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)。1log2n1.6.3 1.6.3 二叉樹(shù)的存儲(chǔ)構(gòu)造二叉樹(shù)的存儲(chǔ)構(gòu)造n普通二叉樹(shù)普通二叉樹(shù)n采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造n存儲(chǔ)結(jié)點(diǎn)由

32、兩部分組成：數(shù)據(jù)域與指針域存儲(chǔ)結(jié)點(diǎn)由兩部分組成：數(shù)據(jù)域與指針域n兩個(gè)指針域：兩個(gè)指針域：n左指針域左指針域n右指針域右指針域n滿二叉樹(shù)與完全二叉樹(shù)滿二叉樹(shù)與完全二叉樹(shù)n采用順序存儲(chǔ)構(gòu)造采用順序存儲(chǔ)構(gòu)造1.6.4 1.6.4 二叉樹(shù)的遍歷二叉樹(shù)的遍歷n二叉樹(shù)的遍歷：不反復(fù)地訪問(wèn)二叉樹(shù)中的一切結(jié)點(diǎn)二叉樹(shù)的遍歷：不反復(fù)地訪問(wèn)二叉樹(shù)中的一切結(jié)點(diǎn) n1 1前序遍歷前序遍歷DLRDLRn首先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)；并首先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)；并且，在遍歷左右子樹(shù)時(shí)，依然先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左且，在遍歷左右子樹(shù)時(shí)，依然先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)。

33、子樹(shù)，最后遍歷右子樹(shù)。n2 2中序遍歷中序遍歷LDRLDRn首先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)；并首先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)；并且，在遍歷左、右子樹(shù)時(shí)，依然先遍歷左子樹(shù)，然后訪問(wèn)且，在遍歷左、右子樹(shù)時(shí)，依然先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)根結(jié)點(diǎn)，最后遍歷右子樹(shù)n3 3后序遍歷后序遍歷LRDLRDn首先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)，并首先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)，并且，在遍歷左、右子樹(shù)時(shí)，依然先遍歷左子樹(shù)，然后遍歷且，在遍歷左、右子樹(shù)時(shí)，依然先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。1.6.4

34、 1.6.4 二叉樹(shù)的遍歷二叉樹(shù)的遍歷n前序遍歷：前序遍歷：nA A、B B、D D、G G、C C、E E、F Fn中序遍歷：中序遍歷：nD D、G G、B B、A A、E E、C C、F F n后序遍歷：后序遍歷：nG G、D D、B B、E E、F F、C C、A A 1.7 1.7 查找技術(shù)查找技術(shù)1.7 1.7 查找技術(shù)查找技術(shù)n查找查找SearchingSearching：根據(jù)給定的某個(gè)值，：根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素。的數(shù)據(jù)元素。n查找結(jié)果：查找結(jié)果：n查找勝利：找到查找勝利：找到n查找不勝利：沒(méi)找到查找不

35、勝利：沒(méi)找到n平均查找長(zhǎng)度：查找過(guò)程中關(guān)鍵字和給定平均查找長(zhǎng)度：查找過(guò)程中關(guān)鍵字和給定值比較的平均次數(shù)值比較的平均次數(shù)1.7.1 1.7.1 順序查找順序查找n根本思想：根本思想：n從表中的第一個(gè)元素開(kāi)場(chǎng)，將給定的值與表中逐從表中的第一個(gè)元素開(kāi)場(chǎng)，將給定的值與表中逐個(gè)元素的關(guān)鍵字進(jìn)展比較，直到兩者相符，查到個(gè)元素的關(guān)鍵字進(jìn)展比較，直到兩者相符，查到所要找的元素為止。否那么就是表中沒(méi)有要找的所要找的元素為止。否那么就是表中沒(méi)有要找的元素，查找不勝利。元素，查找不勝利。n平均要與表中一半以上元素進(jìn)展比較，最壞情況平均要與表中一半以上元素進(jìn)展比較，最壞情況下需求比較下需求比較n n次。次。n以下兩種

36、情況下只能采用順序查找：以下兩種情況下只能采用順序查找：n假設(shè)線性表是無(wú)序表即表中的元素是無(wú)序的，假設(shè)線性表是無(wú)序表即表中的元素是無(wú)序的，那么不論是順序存儲(chǔ)構(gòu)造還是鏈?zhǔn)酱鎯?chǔ)構(gòu)造，都那么不論是順序存儲(chǔ)構(gòu)造還是鏈?zhǔn)酱鎯?chǔ)構(gòu)造，都只能用順序查找。只能用順序查找。n即使是有序線性表，假設(shè)采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造，也即使是有序線性表，假設(shè)采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造，也只能用順序查找。只能用順序查找。1.7.2 1.7.2 二分法查找二分法查找n思想：先確定待查找記錄所在的范圍，然后逐漸減少范圍，直到找到或確認(rèn)找不到該記錄為止。n前提：必需在具有順序存儲(chǔ)構(gòu)造的有序表中進(jìn)展。n查找過(guò)程：n1假設(shè)中間項(xiàng)的值等于x,那么闡明已查到

37、。n2假設(shè)x小于中間項(xiàng)的值，那么在線性表的前半部分查找；n3假設(shè)x大于中間項(xiàng)的值，那么在線性表的后半部分查找。n特點(diǎn)：比順序查找方法效率高。最壞的情況下，需求比較 log2n次。1.7.2 1.7.2 二分法查找二分法查找n例：查找元素例：查找元素2222過(guò)程：過(guò)程： 1.8 1.8 排序技術(shù)排序技術(shù)1.8.1 1.8.1 交換類排序法交換類排序法n根本思想根本思想n兩兩比較待排序記錄的關(guān)鍵字，發(fā)現(xiàn)兩個(gè)兩兩比較待排序記錄的關(guān)鍵字，發(fā)現(xiàn)兩個(gè)記錄的次序相反時(shí)即進(jìn)展交換，直到?jīng)]有記錄的次序相反時(shí)即進(jìn)展交換，直到?jīng)]有反序的記錄為止。反序的記錄為止。n方法方法n冒泡排序冒泡排序n快速排序快速排序1.1.

38、冒泡排序冒泡排序 n根本思想根本思想n對(duì)存放原始數(shù)據(jù)的數(shù)組，按從后往前的方對(duì)存放原始數(shù)據(jù)的數(shù)組，按從后往前的方向進(jìn)展多次掃描，當(dāng)發(fā)現(xiàn)相鄰兩個(gè)數(shù)據(jù)的向進(jìn)展多次掃描，當(dāng)發(fā)現(xiàn)相鄰兩個(gè)數(shù)據(jù)的次序與排序要求的次序與排序要求的“遞增次序不符合時(shí)，遞增次序不符合時(shí)，即將這兩個(gè)數(shù)據(jù)進(jìn)展互換。這樣，較小的即將這兩個(gè)數(shù)據(jù)進(jìn)展互換。這樣，較小的數(shù)據(jù)就會(huì)逐單元向前挪動(dòng)，好象氣泡向上數(shù)據(jù)就會(huì)逐單元向前挪動(dòng)，好象氣泡向上浮起一樣。浮起一樣。n性能分析性能分析n假設(shè)線性表的長(zhǎng)度假設(shè)線性表的長(zhǎng)度n n，那么在最壞情況下，那么在最壞情況下，需求的比較次數(shù)為需求的比較次數(shù)為n(n-1)/2n(n-1)/2。1.1.冒泡排序冒泡排

39、序 2 2快速排序快速排序n根本思想根本思想n任取待排序序列中的某個(gè)元素作為基準(zhǔn)任取待排序序列中的某個(gè)元素作為基準(zhǔn)普通取第一個(gè)元素，經(jīng)過(guò)一趟排序，普通取第一個(gè)元素，經(jīng)過(guò)一趟排序，將待排元素分為左右兩個(gè)子序列，左子序?qū)⒋旁胤譃樽笥覂蓚€(gè)子序列，左子序列元素的排序碼均小于或等于基準(zhǔn)元素的列元素的排序碼均小于或等于基準(zhǔn)元素的排序碼，右子序列的排序碼那么大于基準(zhǔn)排序碼，右子序列的排序碼那么大于基準(zhǔn)元素的排序碼，然后分別對(duì)兩個(gè)子序列繼元素的排序碼，然后分別對(duì)兩個(gè)子序列繼續(xù)進(jìn)展排序，直至整個(gè)序列有序。續(xù)進(jìn)展排序，直至整個(gè)序列有序。n快速排序的平均時(shí)間復(fù)雜度為快速排序的平均時(shí)間復(fù)雜度為O(nlog2n)O

40、(nlog2n)。2 2快速排序快速排序1.8.2 1.8.2 插入類排序法插入類排序法n根本思想：根本思想：n每次將一個(gè)待排序的記錄，按其關(guān)鍵字大每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面曾經(jīng)排好序的子序列中的適小插入到前面曾經(jīng)排好序的子序列中的適當(dāng)位置，直到全部記錄插入完成為止。當(dāng)位置，直到全部記錄插入完成為止。n方法方法: :n簡(jiǎn)單插入排序簡(jiǎn)單插入排序n希爾排序希爾排序1 1簡(jiǎn)單插入排序法簡(jiǎn)單插入排序法n根本思想：根本思想：n把把n n個(gè)待排序的元素看成為一個(gè)有序表和一個(gè)待排序的元素看成為一個(gè)有序表和一個(gè)無(wú)序表，開(kāi)場(chǎng)時(shí)有序表中只包含一個(gè)元個(gè)無(wú)序表，開(kāi)場(chǎng)時(shí)有序表中只包含一個(gè)元素，無(wú)序

41、表中包含有素，無(wú)序表中包含有n-1n-1個(gè)元素，排序過(guò)程個(gè)元素，排序過(guò)程中每次從無(wú)序表中取出第一個(gè)元素，把它中每次從無(wú)序表中取出第一個(gè)元素，把它的排序碼依次與有序表元素的排序碼進(jìn)展的排序碼依次與有序表元素的排序碼進(jìn)展比較，將它插入到有序表中的適當(dāng)位置，比較，將它插入到有序表中的適當(dāng)位置，使之成為新的有序表。使之成為新的有序表。n在最壞的情況下，需求在最壞的情況下，需求n(n-1)/2n(n-1)/2次比較。次比較。1 1簡(jiǎn)單插入排序法簡(jiǎn)單插入排序法2 2希爾排序希爾排序n根本思想根本思想n先將整個(gè)待排元素序列分割成假設(shè)干個(gè)子序列先將整個(gè)待排元素序列分割成假設(shè)干個(gè)子序列由相隔某個(gè)增量由相隔某個(gè)增

42、量h h的元素組成的分別進(jìn)展直接的元素組成的分別進(jìn)展直接插入排序，待整個(gè)序列中的元素根本有序增量插入排序，待整個(gè)序列中的元素根本有序增量足夠小時(shí)，再對(duì)全體元素進(jìn)展一次直接插入排足夠小時(shí)，再對(duì)全體元素進(jìn)展一次直接插入排序。由于直接插入排序在元素根本有序的情況下序。由于直接插入排序在元素根本有序的情況下接近最好情況，效率是很高的。接近最好情況，效率是很高的。n增量序列普通取增量序列普通取 ，其中其中n n為待排序序列的長(zhǎng)度為待排序序列的長(zhǎng)度n在最壞情況下，希爾排序的時(shí)間復(fù)雜度為在最壞情況下，希爾排序的時(shí)間復(fù)雜度為 )log, 2 , 1(2/2nknhki)(5 . 1nO2 2希爾排序希爾排序1

43、.8.3 1.8.3 選擇類排序法選擇類排序法n根本思想：根本思想：n每一趟從待排序的記錄中選出關(guān)鍵字最小每一趟從待排序的記錄中選出關(guān)鍵字最小的記錄，順序放在已排好序的子序列的最的記錄，順序放在已排好序的子序列的最后，直到全部記錄排序終了。后，直到全部記錄排序終了。n方法：方法：n簡(jiǎn)單項(xiàng)選擇擇排序簡(jiǎn)單項(xiàng)選擇擇排序n堆排序堆排序1 1簡(jiǎn)單項(xiàng)選擇擇排序法簡(jiǎn)單項(xiàng)選擇擇排序法 n根本思想：根本思想：n掃描整個(gè)線性表，從中選出最小的元素，掃描整個(gè)線性表，從中選出最小的元素，將它交換到表的最前面；然后對(duì)剩下的子將它交換到表的最前面；然后對(duì)剩下的子表采用同樣的方法，直到子表空為止。表采用同樣的方法，直到子表

44、空為止。n最壞情況下，需求比較最壞情況下，需求比較n(n-1)/2n(n-1)/2次。次。1 1簡(jiǎn)單項(xiàng)選擇擇排序法簡(jiǎn)單項(xiàng)選擇擇排序法 2 2堆排序法堆排序法n堆的定義堆的定義n具有具有n n個(gè)元素的序列，當(dāng)且僅當(dāng)滿足個(gè)元素的序列，當(dāng)且僅當(dāng)滿足n 或或 n時(shí)稱之為堆。稱為大根堆；稱為小根堆時(shí)稱之為堆。稱為大根堆；稱為小根堆 。122iiiihhhh122iiiihhhh2 2堆排序法堆排序法n建堆建堆n在建堆的過(guò)程中，總是將根結(jié)點(diǎn)值與左、右子樹(shù)的根結(jié)點(diǎn)在建堆的過(guò)程中，總是將根結(jié)點(diǎn)值與左、右子樹(shù)的根結(jié)點(diǎn)值進(jìn)展比較，假設(shè)不滿足堆的條件，那么將左、右子樹(shù)根值進(jìn)展比較，假設(shè)不滿足堆的條件，那么將左、右子

45、樹(shù)根結(jié)點(diǎn)值中的大者與根結(jié)點(diǎn)值進(jìn)展交換。這個(gè)調(diào)整過(guò)程不斷結(jié)點(diǎn)值中的大者與根結(jié)點(diǎn)值進(jìn)展交換。這個(gè)調(diào)整過(guò)程不斷做到一切子樹(shù)均為堆為止。做到一切子樹(shù)均為堆為止。n堆排序堆排序n1 1首先將一個(gè)無(wú)序序列建成堆。首先將一個(gè)無(wú)序序列建成堆。n2 2然后將堆頂元素然后將堆頂元素( (序列中的最大項(xiàng)序列中的最大項(xiàng)) )與堆中最后一個(gè)與堆中最后一個(gè)元素交換元素交換( (最大項(xiàng)應(yīng)該在序列的最后最大項(xiàng)應(yīng)該在序列的最后) )。不思索曾經(jīng)換到最。不思索曾經(jīng)換到最后的那個(gè)元素，只思索前后的那個(gè)元素，只思索前n-1n-1個(gè)元素構(gòu)成的子序列，將該個(gè)元素構(gòu)成的子序列，將該子序列調(diào)整為堆。子序列調(diào)整為堆。n反復(fù)做步驟反復(fù)做步驟2

46、2，直到剩下的子序列空為止。，直到剩下的子序列空為止。n在最壞情況下，堆排序法需求比較的次數(shù)為在最壞情況下，堆排序法需求比較的次數(shù)為O(nlog2n)O(nlog2n)。各種排序法比較各種排序法比較 典型考題分析典型考題分析 n【例【例1-11-1】問(wèn)題處置方案的正確而完好的描】問(wèn)題處置方案的正確而完好的描畫(huà)稱為畫(huà)稱為 。20192019年年4 4月月n答案答案 算法算法n【例【例1-21-2】算法復(fù)雜度主要包括時(shí)間復(fù)雜度】算法復(fù)雜度主要包括時(shí)間復(fù)雜度和和 復(fù)雜度。復(fù)雜度。20192019年年9 9月月n答案答案 空間空間n【例【例1-31-3】算法的時(shí)間復(fù)雜度是指】算法的時(shí)間復(fù)雜度是指_。n

47、A A執(zhí)行算法程序所需求的時(shí)間執(zhí)行算法程序所需求的時(shí)間nB B算法程序的長(zhǎng)度算法程序的長(zhǎng)度nC C算法執(zhí)行過(guò)程中所需求的根本運(yùn)算次數(shù)算法執(zhí)行過(guò)程中所需求的根本運(yùn)算次數(shù)nD D算法程序中的指令條數(shù)算法程序中的指令條數(shù)n答案答案C Cn【例【例1-41-4】算法的空間復(fù)雜度是指】算法的空間復(fù)雜度是指_。nA A算法程序的長(zhǎng)度算法程序的長(zhǎng)度nB B算法程序中的指令條數(shù)算法程序中的指令條數(shù)nC C算法程序所占的存儲(chǔ)空間算法程序所占的存儲(chǔ)空間nD D算法執(zhí)行過(guò)程中所需求的存儲(chǔ)空間算法執(zhí)行過(guò)程中所需求的存儲(chǔ)空間n答案答案D Dn【例【例1-51-5】以下表達(dá)中正確的選項(xiàng)】以下表達(dá)中正確的選項(xiàng)是是 。201

48、92019年年9 9月月nA A一個(gè)算法的空間復(fù)雜度大，那么其時(shí)間一個(gè)算法的空間復(fù)雜度大，那么其時(shí)間復(fù)雜度也必定大復(fù)雜度也必定大nB B一個(gè)算法的空間復(fù)雜度大，那么其時(shí)間一個(gè)算法的空間復(fù)雜度大，那么其時(shí)間復(fù)雜度必定小復(fù)雜度必定小nC C一個(gè)算法的時(shí)間復(fù)雜度大，那么其空間一個(gè)算法的時(shí)間復(fù)雜度大，那么其空間可復(fù)雜度必定小可復(fù)雜度必定小nD D上述三種說(shuō)法都不對(duì)上述三種說(shuō)法都不對(duì)n答案答案 D Dn【例【例1-61-6】以下表達(dá)中正確的選項(xiàng)】以下表達(dá)中正確的選項(xiàng)是是 。20192019年年9 9月月nA A一個(gè)邏輯數(shù)據(jù)構(gòu)造只能有一種存儲(chǔ)構(gòu)造一個(gè)邏輯數(shù)據(jù)構(gòu)造只能有一種存儲(chǔ)構(gòu)造nB B數(shù)據(jù)的邏輯構(gòu)造屬于

49、線性構(gòu)造，存儲(chǔ)構(gòu)數(shù)據(jù)的邏輯構(gòu)造屬于線性構(gòu)造，存儲(chǔ)構(gòu)造屬于非線性構(gòu)造造屬于非線性構(gòu)造nC C一個(gè)邏輯數(shù)據(jù)構(gòu)造可以有多種存儲(chǔ)構(gòu)造，一個(gè)邏輯數(shù)據(jù)構(gòu)造可以有多種存儲(chǔ)構(gòu)造，且各種存儲(chǔ)構(gòu)造不影響數(shù)據(jù)處置的效率且各種存儲(chǔ)構(gòu)造不影響數(shù)據(jù)處置的效率nD D一個(gè)邏輯數(shù)據(jù)構(gòu)造可以有多種存儲(chǔ)構(gòu)造，一個(gè)邏輯數(shù)據(jù)構(gòu)造可以有多種存儲(chǔ)構(gòu)造，且各種存儲(chǔ)構(gòu)造影響數(shù)據(jù)處置的效率且各種存儲(chǔ)構(gòu)造影響數(shù)據(jù)處置的效率n答案答案 D Dn【例【例1-71-7】數(shù)據(jù)構(gòu)造分為邏輯構(gòu)造和存儲(chǔ)構(gòu)】數(shù)據(jù)構(gòu)造分為邏輯構(gòu)造和存儲(chǔ)構(gòu)造，循環(huán)隊(duì)列屬于造，循環(huán)隊(duì)列屬于 構(gòu)造。構(gòu)造。20192019年年9 9月月n答案答案 邏輯邏輯n【例【例1-81-8】數(shù)據(jù)構(gòu)

50、造分為線性構(gòu)造和非線性】數(shù)據(jù)構(gòu)造分為線性構(gòu)造和非線性構(gòu)造，帶鏈的隊(duì)列屬于構(gòu)造，帶鏈的隊(duì)列屬于 。20192019年年9 9月月n答案答案 線性構(gòu)造線性構(gòu)造n【例【例1-91-9】以下表達(dá)中正確的選項(xiàng)是】以下表達(dá)中正確的選項(xiàng)是_。20192019年年4 4月月nA A線性鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造線性鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造nB B棧與隊(duì)列是非線性構(gòu)造棧與隊(duì)列是非線性構(gòu)造nC C雙向鏈表是非線性構(gòu)造雙向鏈表是非線性構(gòu)造nD D只需根結(jié)點(diǎn)的二叉樹(shù)是線性構(gòu)造只需根結(jié)點(diǎn)的二叉樹(shù)是線性構(gòu)造n答案答案 A An【例【例1-101-10】某線性表采用順序存儲(chǔ)構(gòu)造，】某線性表采用順序存儲(chǔ)構(gòu)造，每個(gè)元素占每個(gè)

51、元素占4 4個(gè)存儲(chǔ)單元，首地址為個(gè)存儲(chǔ)單元，首地址為200200，那么第那么第1212個(gè)元素的存儲(chǔ)地址為個(gè)元素的存儲(chǔ)地址為 。nA A248248nB B247247nC C246246nD D244244n答案答案 D Dn【例【例1-111-11】在長(zhǎng)度為】在長(zhǎng)度為n n的順序表的第的順序表的第i i1in+11in+1個(gè)位置上插入一個(gè)元素，元個(gè)位置上插入一個(gè)元素，元素的挪動(dòng)次數(shù)為素的挪動(dòng)次數(shù)為 。nA An-i+1n-i+1nB Bn-in-inC Ci inD Di-1i-1n答案答案 A An【例【例1-121-12】在一個(gè)長(zhǎng)度為】在一個(gè)長(zhǎng)度為n n的順序表中，刪的順序表中，刪除第除

52、第i i1in1in個(gè)元素時(shí)，需求挪動(dòng)的個(gè)元素時(shí)，需求挪動(dòng)的元素個(gè)數(shù)為元素個(gè)數(shù)為 。nA An-i+1n-i+1nB Bn-in-inC Ci inD Di-1i-1n答案答案 B Bn【例【例1-131-13】以下描畫(huà)的中，不是線性表的】以下描畫(huà)的中，不是線性表的順序存儲(chǔ)構(gòu)造的特征的是順序存儲(chǔ)構(gòu)造的特征的是 。nA A不便于插入和刪除不便于插入和刪除nB B需求延續(xù)的存儲(chǔ)空間需求延續(xù)的存儲(chǔ)空間nC C可隨機(jī)訪問(wèn)可隨機(jī)訪問(wèn)nD D需另外開(kāi)辟空間來(lái)保管元素之間的關(guān)系需另外開(kāi)辟空間來(lái)保管元素之間的關(guān)系n答案答案 D Dn【例【例1-141-14】以下關(guān)于棧的描畫(huà)中錯(cuò)誤的選】以下關(guān)于棧的描畫(huà)中錯(cuò)誤的

53、選項(xiàng)是項(xiàng)是_。20192019年年4 4月月nA A棧是先進(jìn)后出的線性表?xiàng)Ｊ窍冗M(jìn)后出的線性表nB B棧只能順序存儲(chǔ)棧只能順序存儲(chǔ)nC C棧具有記憶作用棧具有記憶作用nD D對(duì)棧的插入與刪除操作中，不需求改動(dòng)對(duì)棧的插入與刪除操作中，不需求改動(dòng)棧底指針棧底指針n答案答案 B Bn【例【例1-151-15】棧和隊(duì)列的共同點(diǎn)是】棧和隊(duì)列的共同點(diǎn)是_。nA A都是先進(jìn)先出都是先進(jìn)先出nB B都是先進(jìn)后出都是先進(jìn)后出nC C只允許在端點(diǎn)處插入和刪除元素只允許在端點(diǎn)處插入和刪除元素nD D沒(méi)有共同點(diǎn)沒(méi)有共同點(diǎn)n答案答案 C Cn【例【例1-161-16】棧的輸入序列為】棧的輸入序列為1 1，2 2，3 3，

54、n-1n-1，n n，輸出序列的第，輸出序列的第1 1個(gè)元素為個(gè)元素為n n，那么，那么第個(gè)輸出元素為第個(gè)輸出元素為_(kāi)。nA An-i+1n-i+1nB Bn-1n-1nC Ci inD D哪個(gè)元素?zé)o所謂哪個(gè)元素?zé)o所謂n答案答案 A An【例【例1-171-17】一個(gè)隊(duì)列的入隊(duì)序列是】一個(gè)隊(duì)列的入隊(duì)序列是1 1、2 2、3 3、4 4，那么隊(duì)列的輸出序列是，那么隊(duì)列的輸出序列是 。nA A4 4、3 3、2 2、1 1nB B1 1、2 2、3 3、4 4nC C1 1、4 4、3 3、2 2nD D3 3、2 2、4 4、1 1n答案答案 A An【例【例1-181-18】隊(duì)列是限定只能在表

55、的一端進(jìn)】隊(duì)列是限定只能在表的一端進(jìn)展插入和在另一端進(jìn)展刪除操作的線性表。展插入和在另一端進(jìn)展刪除操作的線性表。允許插入的一端稱作允許插入的一端稱作_。n答案答案 隊(duì)尾隊(duì)尾n【例【例1-191-19】以下對(duì)于線性鏈表的描畫(huà)中正】以下對(duì)于線性鏈表的描畫(huà)中正確的選項(xiàng)是確的選項(xiàng)是 。20192019年年4 4月月nA A存儲(chǔ)空間不一定是延續(xù)，且各元素的存存儲(chǔ)空間不一定是延續(xù)，且各元素的存儲(chǔ)順序是恣意的儲(chǔ)順序是恣意的 nB B存儲(chǔ)空間不一定是延續(xù)，且前件元素一存儲(chǔ)空間不一定是延續(xù)，且前件元素一定存儲(chǔ)在后件元素的前面定存儲(chǔ)在后件元素的前面 nC C存儲(chǔ)空間必需延續(xù)，且各前件元素一定存儲(chǔ)空間必需延續(xù)，且各

56、前件元素一定存儲(chǔ)在后件元素的前面存儲(chǔ)在后件元素的前面 nD D存儲(chǔ)空間必需延續(xù)，且各元素的存儲(chǔ)順存儲(chǔ)空間必需延續(xù)，且各元素的存儲(chǔ)順序是恣意的序是恣意的 n答案答案 A An【例【例1-201-20】以下表達(dá)中，錯(cuò)誤的選項(xiàng)】以下表達(dá)中，錯(cuò)誤的選項(xiàng)是是 。nA A線性表是由線性表是由n n個(gè)數(shù)據(jù)元素組成的一個(gè)有個(gè)數(shù)據(jù)元素組成的一個(gè)有限序列限序列nB B線性表是一種線性構(gòu)造。線性表是一種線性構(gòu)造。nC C線性表的一切結(jié)點(diǎn)有且只需一個(gè)前件和線性表的一切結(jié)點(diǎn)有且只需一個(gè)前件和一個(gè)后件一個(gè)后件nD D線性表可以是空表。線性表可以是空表。n答案答案 C Cn【例【例1-211-21】以下描畫(huà)的不是鏈表的優(yōu)點(diǎn)

57、是】以下描畫(huà)的不是鏈表的優(yōu)點(diǎn)是_。nA A邏輯上相鄰的結(jié)點(diǎn)物理上不用鄰接邏輯上相鄰的結(jié)點(diǎn)物理上不用鄰接nB B插入、刪除運(yùn)算操作方便，不用挪動(dòng)結(jié)插入、刪除運(yùn)算操作方便，不用挪動(dòng)結(jié)點(diǎn)點(diǎn)nC C所需存儲(chǔ)空間比線性表節(jié)省所需存儲(chǔ)空間比線性表節(jié)省nD D無(wú)需事先估計(jì)存儲(chǔ)空間的大小無(wú)需事先估計(jì)存儲(chǔ)空間的大小n答案答案 C Cn【例【例1-221-22】某線性表最常用的運(yùn)算是插入】某線性表最常用的運(yùn)算是插入和刪除，插入運(yùn)算是指在表尾插入一個(gè)新和刪除，插入運(yùn)算是指在表尾插入一個(gè)新元素。刪除運(yùn)算是指刪除表頭第一個(gè)元素，元素。刪除運(yùn)算是指刪除表頭第一個(gè)元素，那么采用那么采用 存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。存儲(chǔ)方式最節(jié)

58、省運(yùn)算時(shí)間。nA A僅有尾指針的單向循環(huán)鏈表僅有尾指針的單向循環(huán)鏈表nB B僅有頭指針的單向循環(huán)鏈表僅有頭指針的單向循環(huán)鏈表nC C單向鏈表單向鏈表nD D順序存儲(chǔ)順序存儲(chǔ)n答案答案 A An【例【例1-231-23】一棵二叉樹(shù)第六層根結(jié)點(diǎn)為】一棵二叉樹(shù)第六層根結(jié)點(diǎn)為第一層的結(jié)點(diǎn)數(shù)最多為第一層的結(jié)點(diǎn)數(shù)最多為 個(gè)。個(gè)。20192019年年9 9月月n答案答案 32 32n【例【例1-241-24】深度為】深度為5 5的二叉樹(shù)至多有的二叉樹(shù)至多有_個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。nA A1616nB B3232nC C3131nD D1010n答案答案 C Cn【例【例1-251-25】設(shè)樹(shù)】設(shè)樹(shù)T T的度為的度

59、為4 4，其中度為，其中度為1 1，2 2，3 3，4 4的結(jié)點(diǎn)個(gè)數(shù)分別為的結(jié)點(diǎn)個(gè)數(shù)分別為4 4，2 2，1 1，1 1。那么。那么T T中的葉子結(jié)點(diǎn)為中的葉子結(jié)點(diǎn)為_(kāi)。nA A8 8nB B7 7nC C6 6nD D5 5n答案答案 A An【例【例1-261-26】某二叉樹(shù)中度為】某二叉樹(shù)中度為2 2的結(jié)點(diǎn)有的結(jié)點(diǎn)有1818個(gè)，個(gè)，那么該二叉樹(shù)中有那么該二叉樹(shù)中有 個(gè)葉子結(jié)點(diǎn)。個(gè)葉子結(jié)點(diǎn)。20192019年年4 4月月n答案答案 19 19n【例【例1-271-27】具有】具有8888個(gè)結(jié)點(diǎn)的二叉樹(shù)，其深個(gè)結(jié)點(diǎn)的二叉樹(shù)，其深度至少為度至少為_(kāi)。n答案答案 7 7n【例【例1-281-28

60、】在深度為】在深度為7 7的滿二叉樹(shù)中，葉子的滿二叉樹(shù)中，葉子結(jié)點(diǎn)的個(gè)數(shù)為結(jié)點(diǎn)的個(gè)數(shù)為20192019年年4 4月月nA A3232nB B3131nC C6464nD D6363n答案答案 C Cn【例【例1-291-29】設(shè)一棵完全二叉樹(shù)共有】設(shè)一棵完全二叉樹(shù)共有700700個(gè)結(jié)點(diǎn)，個(gè)結(jié)點(diǎn)，那么在該二叉樹(shù)中有那么在該二叉樹(shù)中有_個(gè)葉子結(jié)點(diǎn)。個(gè)葉子結(jié)點(diǎn)。n答案答案 350350n【例【例1-301-30】對(duì)如圖】對(duì)如圖1-301-30所示的二叉樹(shù)，進(jìn)所示的二叉樹(shù)，進(jìn)展后序遍歷的結(jié)果為展后序遍歷的結(jié)果為 。20192019年年4 4月月nA AABCDEFABCDEFnB BDBEAFCDBE