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

1、二級公共根底知識二級公共根底知識第一章第一章 數(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線性表及其順序存儲構(gòu)造：線性表的根本概念、線性表及其順序存儲構(gòu)造：線性表的根本概念、 順序存順序存儲構(gòu)造、插入運算、刪除運算儲構(gòu)造、插入運算、刪除運算n棧和隊列：棧及其根本運算、隊列及其根本運算棧和隊列：棧及其根本運算、隊列及其根本運算n線性鏈表：根本概念、根本運算、循環(huán)鏈表及其根本

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

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

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

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

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

7、儲空間n存儲量包括以下三部分n算法程序所占的空間n輸入的初始數(shù)據(jù)所占的存儲空間n算法執(zhí)行過程中所要的額外空間n算法空間復(fù)雜度可定義為：nS(n)=O(f(n)n原地任務(wù)(in place)的算法：記作O(1)n緊縮存儲技術(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ù)的存儲構(gòu)造數(shù)據(jù)的存儲構(gòu)造n對各種數(shù)據(jù)構(gòu)造進展的運算對各種數(shù)據(jù)構(gòu)造進展的運算n2 2研討數(shù)據(jù)構(gòu)造目的研討數(shù)據(jù)構(gòu)造目的n提高數(shù)據(jù)處置的速度提高數(shù)據(jù)處置的速度n盡量節(jié)省在數(shù)據(jù)處置過程中所占用的

8、計算盡量節(jié)省在數(shù)據(jù)處置過程中所占用的計算機存儲空間機存儲空間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ù)的存儲構(gòu)造數(shù)據(jù)的存儲構(gòu)造n對各種數(shù)據(jù)構(gòu)造進展的運算對各種數(shù)據(jù)構(gòu)造進展的運算n2 2研討數(shù)據(jù)構(gòu)造目的研討數(shù)據(jù)構(gòu)造目的n提高數(shù)據(jù)處置的速度提高數(shù)據(jù)處置的速度n盡量節(jié)省在數(shù)據(jù)處置過程中所占用的計算盡量節(jié)省在數(shù)據(jù)處置過程中所占用的計算機存儲空間機存儲空間1.2.1 1.2.1 什么是數(shù)據(jù)構(gòu)造什么是數(shù)據(jù)構(gòu)造 1數(shù)據(jù)的邏輯構(gòu)造 2、數(shù)據(jù)的存儲構(gòu)造 3、數(shù)據(jù)的運算：檢索、排序、插入、刪除、修正等。 A線性構(gòu)造

9、B非線性構(gòu)造A 順序存儲 B 鏈式存儲 線性表棧隊樹形構(gòu)造圖形構(gòu)造數(shù)據(jù)構(gòu)造的三個方面 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)系來描畫n一個數(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對數(shù)據(jù)元素之間的邏輯關(guān)系的描畫對數(shù)據(jù)元素之間的邏輯關(guān)系的描畫n只籠統(tǒng)地反映數(shù)據(jù)元素之間的邏輯關(guān)系，只籠統(tǒng)地反映數(shù)據(jù)元素之間的邏輯關(guān)系，與計算機中的存儲無關(guān)與計算機中的存儲無關(guān)n兩個要素：兩個要素

10、：n數(shù)據(jù)元素的集合，通常記為數(shù)據(jù)元素的集合，通常記為D D；n前后件關(guān)系，通常記為前后件關(guān)系，通常記為R Rn一個數(shù)據(jù)構(gòu)造一個數(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ù)的存儲構(gòu)造數(shù)據(jù)的存儲構(gòu)造n數(shù)據(jù)的邏輯構(gòu)造在計算機存儲空間中的存數(shù)據(jù)的邏輯構(gòu)造在計算機存儲空間中的存放方式放方式n常用的存儲構(gòu)造：常用的存儲構(gòu)造：n順序順序n鏈式鏈式n索引索引n一種數(shù)據(jù)構(gòu)造可根據(jù)需求采用不同的存儲一種數(shù)據(jù)構(gòu)造可根據(jù)需求采用不同的存儲構(gòu)造。采用不同的存儲構(gòu)造，其數(shù)據(jù)處置構(gòu)造。采用不同的存儲構(gòu)造，其數(shù)據(jù)處置的效率是不同的效率是不同1.

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

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

13、=0 時的線性表被稱為空時的線性表被稱為空表。稱表。稱i i為在線性表中的位序。為在線性表中的位序。n例如：例如：n英文大寫字母表英文大寫字母表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ù)元素在表中的位置由序號決議，數(shù)據(jù)數(shù)據(jù)元素在表中的位置由序號決議，數(shù)據(jù)元素之間的相對位置是線性的；元素之間的相

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

31、根結(jié)點，它沒有父結(jié)點；假設(shè)k1k1，那么該結(jié)點的父結(jié)點的編號為，那么該結(jié)點的父結(jié)點的編號為INT(k/2)INT(k/2)。n假設(shè)假設(shè)2kn2kn，那么編號為，那么編號為k k的左子結(jié)點編號為的左子結(jié)點編號為2k2k；否那么；否那么該結(jié)點無左子結(jié)點顯然也沒有右子結(jié)點。該結(jié)點無左子結(jié)點顯然也沒有右子結(jié)點。n假設(shè)假設(shè)2k+1n2k+1n，那么編號為，那么編號為k k的右子結(jié)點編號為的右子結(jié)點編號為2k+12k+1；否；否那么該結(jié)點無右子結(jié)點。那么該結(jié)點無右子結(jié)點。1log2n1.6.3 1.6.3 二叉樹的存儲構(gòu)造二叉樹的存儲構(gòu)造n普通二叉樹普通二叉樹n采用鏈式存儲構(gòu)造采用鏈式存儲構(gòu)造n存儲結(jié)點由

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

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

34、 1.6.4 二叉樹的遍歷二叉樹的遍歷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ù)給定的某個值，：根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素。的數(shù)據(jù)元素。n查找結(jié)果：查找結(jié)果：n查找勝利：找到查找勝利：找到n查找不勝利：沒找到查找不

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

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

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

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

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

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

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

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

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

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

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

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

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

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

49、線性構(gòu)造，存儲構(gòu)數(shù)據(jù)的邏輯構(gòu)造屬于線性構(gòu)造，存儲構(gòu)造屬于非線性構(gòu)造造屬于非線性構(gòu)造nC C一個邏輯數(shù)據(jù)構(gòu)造可以有多種存儲構(gòu)造，一個邏輯數(shù)據(jù)構(gòu)造可以有多種存儲構(gòu)造，且各種存儲構(gòu)造不影響數(shù)據(jù)處置的效率且各種存儲構(gòu)造不影響數(shù)據(jù)處置的效率nD D一個邏輯數(shù)據(jù)構(gòu)造可以有多種存儲構(gòu)造，一個邏輯數(shù)據(jù)構(gòu)造可以有多種存儲構(gòu)造，且各種存儲構(gòu)造影響數(shù)據(jù)處置的效率且各種存儲構(gòu)造影響數(shù)據(jù)處置的效率n答案答案 D Dn【例【例1-71-7】數(shù)據(jù)構(gòu)造分為邏輯構(gòu)造和存儲構(gòu)】數(shù)據(jù)構(gòu)造分為邏輯構(gòu)造和存儲構(gòu)造，循環(huán)隊列屬于造，循環(huán)隊列屬于 構(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)造，帶鏈的隊列屬于構(gòu)造，帶鏈的隊列屬于 。20192019年年9 9月月n答案答案 線性構(gòu)造線性構(gòu)造n【例【例1-91-9】以下表達中正確的選項是】以下表達中正確的選項是_。20192019年年4 4月月nA A線性鏈表是線性表的鏈式存儲構(gòu)造線性鏈表是線性表的鏈式存儲構(gòu)造nB B棧與隊列是非線性構(gòu)造棧與隊列是非線性構(gòu)造nC C雙向鏈表是非線性構(gòu)造雙向鏈表是非線性構(gòu)造nD D只需根結(jié)點的二叉樹是線性構(gòu)造只需根結(jié)點的二叉樹是線性構(gòu)造n答案答案 A An【例【例1-101-10】某線性表采用順序存儲構(gòu)造，】某線性表采用順序存儲構(gòu)造，每個元素占每個

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

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

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

54、n-1n-1，n n，輸出序列的第，輸出序列的第1 1個元素為個元素為n n，那么，那么第個輸出元素為第個輸出元素為_。nA An-i+1n-i+1nB Bn-1n-1nC Ci inD D哪個元素無所謂哪個元素無所謂n答案答案 A An【例【例1-171-17】一個隊列的入隊序列是】一個隊列的入隊序列是1 1、2 2、3 3、4 4，那么隊列的輸出序列是，那么隊列的輸出序列是 。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】隊列是限定只能在表

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

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

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

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

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

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