大學(xué)計算機基礎(chǔ)_07數(shù)據(jù)結(jié)構(gòu)與算法

1、第第7 7章章數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法7.1 算 法7.2 數(shù)據(jù)結(jié)構(gòu)的基本概念7.3 線性表及其順序存儲結(jié)構(gòu)7.4 棧和隊列7.5 線性鏈表7.6 樹與二叉樹7.7 查找與排序技術(shù)習(xí)題第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1827.1 算算 法法7.1.1 算法的基本概念算法的基本概念1算法的基本特征算法的基本特征 （1）可行性）可行性 （2）確定性）確定性 （3）有窮性）有窮性 （4）有零個或多個輸入）有零個或多個輸入 （5）有一個或多個輸出）有一個或多個輸出一個算法，就是一組定義了運算順序的規(guī)則，并且每一個算法，就是一組定義了運算順序的規(guī)則，并且每個規(guī)則都是有效的、明確的，此運算順序?qū)?/p>

2、在有限個規(guī)則都是有效的、明確的，此運算順序?qū)⒃谟邢薜牟襟E后終止。的步驟后終止。第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-183l 對數(shù)據(jù)對象的對數(shù)據(jù)對象的運算和操作運算和操作，l 算法的算法的控制結(jié)構(gòu)控制結(jié)構(gòu)。2算法的基本要素算法的基本要素第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-184（1 1）算法中對數(shù)據(jù)的運算和操作）算法中對數(shù)據(jù)的運算和操作 算術(shù)運算算術(shù)運算：主要包括加、減、乘、除等運算。：主要包括加、減、乘、除等運算。 邏輯運算邏輯運算：主要包括：主要包括“邏輯與邏輯與”、“邏輯或邏輯或”、“邏輯非邏輯非”等運算。等運算。 關(guān)系運算關(guān)系運算：主要包括：主要包括“大于大于”、“大于或等于大于或等

3、于”、“小于小于”、“小于或等于小于或等于”、“等于等于”、“不等于不等于”等運算。等運算。 數(shù)據(jù)傳輸數(shù)據(jù)傳輸：主要包括賦值、輸入、輸出等操作。：主要包括賦值、輸入、輸出等操作。第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-185（2 2）算法的控制結(jié)構(gòu)）算法的控制結(jié)構(gòu)算法中各種操作之間的執(zhí)行順序稱為算法的控制結(jié)構(gòu)。算法中各種操作之間的執(zhí)行順序稱為算法的控制結(jié)構(gòu)。一個算法一般都可以用一個算法一般都可以用順序結(jié)構(gòu)、選擇結(jié)構(gòu)、和循環(huán)結(jié)構(gòu)順序結(jié)構(gòu)、選擇結(jié)構(gòu)、和循環(huán)結(jié)構(gòu)這三這三種基本控制結(jié)構(gòu)組合而成。種基本控制結(jié)構(gòu)組合而成。第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1863算法設(shè)計基本方法算法設(shè)計基本方法 （1）

4、 列舉法列舉法 列舉法列舉法就是根據(jù)所要解決的問題，把所有可能就是根據(jù)所要解決的問題，把所有可能的情況都一一列舉出來，并用問題中給定的條件來的情況都一一列舉出來，并用問題中給定的條件來檢驗?zāi)男┦切枰?，哪些是不需要的。檢驗?zāi)男┦切枰?，哪些是不需要的。例如：設(shè)例如：設(shè)x,y為非負整數(shù)，求滿足方程為非負整數(shù)，求滿足方程 2x+3y=10的的x,y。第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-187（2）歸納法）歸納法 歸納法歸納法的基本思想是通過列舉少量的特殊情況，經(jīng)過分的基本思想是通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關(guān)系。析，最后找出一般的關(guān)系。 可以看出，歸納法可以解決列舉量為無限的問

5、題?？梢钥闯觯瑲w納法可以解決列舉量為無限的問題。 第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-188（3）遞推）遞推 遞推遞推是指從已知的初始條件出發(fā)，逐步推出所要求是指從已知的初始條件出發(fā)，逐步推出所要求的結(jié)果。的結(jié)果。例如：求例如：求 x2=a 的遞推公式：的遞推公式：0 , )(0211xxxnxann第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-189（4）遞歸）遞歸 在解決某些復(fù)雜問題時，為了降低問題的復(fù)雜程度（如在解決某些復(fù)雜問題時，為了降低問題的復(fù)雜程度（如問題的規(guī)模等），可以將問題逐層分解，最后歸結(jié)為一問題的規(guī)模等），可以將問題逐層分解，最后歸結(jié)為一些最簡單的問題。些最簡單的問題。第7章 數(shù)

6、據(jù)結(jié)構(gòu)與算法2021-11-1810例例7.2 有有5個人坐在一起，個人坐在一起，問第問第5個人的歲數(shù)，他說比第個人的歲數(shù)，他說比第4個人大個人大2歲。歲。問第問第4個人的歲數(shù)，他說比第個人的歲數(shù)，他說比第3個人大個人大2歲。歲。問第問第3個人的歲數(shù)，他說比第個人的歲數(shù)，他說比第2個人大個人大2歲。歲。問第問第2個人的歲數(shù)，他說比第個人的歲數(shù)，他說比第1個人大個人大2歲。歲。問第問第1個人的歲數(shù)，他說是個人的歲數(shù)，他說是10歲。歲。請問第請問第5個人多大。個人多大。 第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1811這個問題可以用遞歸方法解決。遞歸過程如下：這個問題可以用遞歸方法解決。遞歸過程如下

7、： age（5）age（4）十）十2 age（4）age（3）十）十2 age（3）age（2）十）十2 age（2）age（1）十）十2 age（ l）10第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1812（5）減半遞推技術(shù)）減半遞推技術(shù) “減半減半”是指將問題的規(guī)模減半，而問題的性質(zhì)不變；是指將問題的規(guī)模減半，而問題的性質(zhì)不變；“遞推遞推”是指重復(fù)是指重復(fù)“減半減半”的過程。的過程。第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1813 7.1.2 算法的復(fù)雜度算法的復(fù)雜度 可分為可分為時間復(fù)雜度時間復(fù)雜度和和空間復(fù)雜度空間復(fù)雜度。 1算法的時間復(fù)雜度算法的時間復(fù)雜度 算法的時間復(fù)雜度算法的時間復(fù)雜度

8、是指執(zhí)行算法所需要的計算工作量是指執(zhí)行算法所需要的計算工作量。 例如：兩個例如：兩個n階方陣的乘積的乘法次數(shù)為階方陣的乘積的乘法次數(shù)為n3。 兩種常用方法：兩種常用方法：（1） 平均性態(tài)平均性態(tài)（2）最壞情況復(fù)雜性）最壞情況復(fù)雜性第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-18142算法的空間復(fù)雜度算法的空間復(fù)雜度算法的空間復(fù)雜度算法的空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。是指執(zhí)行這個算法所需要的內(nèi)存空間。類似算法的時間復(fù)雜度，空間復(fù)雜度作為算法所需存儲空類似算法的時間復(fù)雜度，空間復(fù)雜度作為算法所需存儲空間的度量。間的度量。 第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-18157.2 數(shù)據(jù)結(jié)構(gòu)的基本

9、概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)主要研究三個問題：數(shù)據(jù)結(jié)構(gòu)主要研究三個問題： （1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即系，即數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)； （2）在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機）在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲關(guān)系，即中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)； （3）對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。）對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1816例例7.5 7.5 無序表的順序查找與有序表的對分查找。無序表的順序查找與有序表的對分查找。7.2 7.2 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概

10、念7.2.1 7.2.1 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1817現(xiàn)實世界中存在的一切個體都可以是現(xiàn)實世界中存在的一切個體都可以是數(shù)據(jù)元素（數(shù)據(jù)元素（簡稱簡稱元元素素）。）。例如：例如： 春、夏、秋、冬；春、夏、秋、冬； 26、56、65、 73、26、； 父親、兒子、女兒。父親、兒子、女兒。數(shù)據(jù)元素之間的關(guān)系可用前后件關(guān)系數(shù)據(jù)元素之間的關(guān)系可用前后件關(guān)系例如，例如， “春春”是是“夏夏”前件前件，“夏夏”是是“春春”的的后件。后件。第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-18181數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)指數(shù)據(jù)之間的邏輯關(guān)系，與它們在計算機中的存儲位置指數(shù)

11、據(jù)之間的邏輯關(guān)系，與它們在計算機中的存儲位置無關(guān)無關(guān)。有兩個基本要素有兩個基本要素： 表示數(shù)據(jù)元素的信息，通常記為表示數(shù)據(jù)元素的信息，通常記為D； 表示各數(shù)據(jù)元素之間的前后件關(guān)系，通常記為表示各數(shù)據(jù)元素之間的前后件關(guān)系，通常記為R。例例7.2 一年四季的數(shù)據(jù)結(jié)構(gòu)可以表示成一年四季的數(shù)據(jù)結(jié)構(gòu)可以表示成 B=（D，R） D=春，夏，秋，冬春，夏，秋，冬 R=（春，夏），（夏，秋），（秋，冬）（春，夏），（夏，秋），（秋，冬）第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1819例例7.3 家庭成員數(shù)據(jù)結(jié)構(gòu)可以表示成家庭成員數(shù)據(jù)結(jié)構(gòu)可以表示成 B=（D， R） D=父親，兒子，女兒父親，兒子，女兒 R=（父

12、親，兒子），（父親，女兒）（父親，兒子），（父親，女兒）第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-18202數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式稱為數(shù)據(jù)的數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）存儲結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）。 一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以表示成多種存儲結(jié)構(gòu)一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以表示成多種存儲結(jié)構(gòu)。 常用的存儲結(jié)構(gòu)有順序、鏈接、索引等存儲結(jié)構(gòu)。常用的存儲結(jié)構(gòu)有順序、鏈接、索引等存儲結(jié)構(gòu)。第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-18217.2.2 數(shù)據(jù)結(jié)構(gòu)的圖形表示數(shù)據(jù)結(jié)構(gòu)的圖形表示第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-

13、11-18227.2.3 線性結(jié)構(gòu)與非線性結(jié)構(gòu)線性結(jié)構(gòu)與非線性結(jié)構(gòu)如果一個數(shù)據(jù)結(jié)構(gòu)滿足：如果一個數(shù)據(jù)結(jié)構(gòu)滿足：（1）有且只有一個根結(jié)點；）有且只有一個根結(jié)點；（2）每個結(jié)點最多有一個前件，也最多有一個后件。）每個結(jié)點最多有一個前件，也最多有一個后件。則稱該數(shù)據(jù)結(jié)構(gòu)為則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)線性結(jié)構(gòu)。線性結(jié)構(gòu)又稱。線性結(jié)構(gòu)又稱線性表線性表。第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-18237.3 線性表及其順序存儲結(jié)構(gòu)線性表及其順序存儲結(jié)構(gòu)7.3.1 線性表的基本概念線性表的基本概念線性表線性表是指是指n n個數(shù)據(jù)元素的有限序列。個數(shù)據(jù)元素的有限序列。線性表可以表示為線性表可以表示為 （a a1 1

14、，a a2 2，a ai i，a an n），），當(dāng)當(dāng)n=0n=0時，稱為空表。時，稱為空表。 第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-18247.3.2 線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)順序存儲的特點如下：順序存儲的特點如下：（1） 線性表中所有元素所占的存儲空間是連續(xù)的；線性表中所有元素所占的存儲空間是連續(xù)的；（2） 線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。存放的。第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-18257.3.3 順序表的插入運算順序表的插入運算第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-18267.3.4 線性表的刪除運

15、算線性表的刪除運算第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-18277.4 棧和隊列棧和隊列7.4.1 棧及其基本運算棧及其基本運算 1棧的基本概念棧的基本概念棧棧（stack）是限定僅在一端進行插入和刪除運算的線性表。）是限定僅在一端進行插入和刪除運算的線性表。在棧中，允許插入與刪除的一端稱為在棧中，允許插入與刪除的一端稱為棧頂棧頂，而不允許插入與，而不允許插入與刪除的另一端稱為刪除的另一端稱為棧底棧底。第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1828棧的順序存儲結(jié)構(gòu)如圖所棧的順序存儲結(jié)構(gòu)如圖所示。示。第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-18292棧的基本運算棧的基本運算 有三種：有三種：入棧入

16、棧、退棧退棧與與讀棧頂元素讀棧頂元素。（1） 入棧運算入棧運算首先將棧頂指針進一，然后將新元素插入到棧頂指針指向的首先將棧頂指針進一，然后將新元素插入到棧頂指針指向的位置；位置；第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1830（2） 退棧運算退棧運算首先將棧頂元素賦給一個指定的變量，然后將棧頂指針退一。首先將棧頂元素賦給一個指定的變量，然后將棧頂指針退一。（3） 讀棧頂元素讀棧頂元素是指將棧頂元素賦給一個指定的變量。棧頂指針不會改變。是指將棧頂元素賦給一個指定的變量。棧頂指針不會改變。第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-18317.4.2 隊列及其基本運算隊列及其基本運算1隊列的基本概念隊列的

17、基本概念隊列隊列（queue）是在表的一端進行插入，在表的另一端進行刪）是在表的一端進行插入，在表的另一端進行刪除的線性表。除的線性表。在隊列中，允許插入的一端稱為在隊列中，允許插入的一端稱為隊尾隊尾， 允許刪除的一端稱為允許刪除的一端稱為隊頭隊頭。隊列又稱為隊列又稱為“先進先出先進先出”或或“后進后出后進后出”的線性表。在隊列中，的線性表。在隊列中，常用指針常用指針front 指向隊頭，用指向隊頭，用rear指向隊尾，如圖所示。指向隊尾，如圖所示。第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1832圖圖7.11是在隊列中進行插入與刪除的示意圖。是在隊列中進行插入與刪除的示意圖。 第7章 數(shù)據(jù)結(jié)構(gòu)與

18、算法2021-11-18337.5 線性鏈表線性鏈表7.5.1 線性鏈表的基本概念線性鏈表的基本概念1線性鏈表線性鏈表其鏈表結(jié)構(gòu)如圖（其鏈表結(jié)構(gòu)如圖（a）所示。）所示。實際上，常用圖（實際上，常用圖（b b）來表示它們的邏輯關(guān)系。）來表示它們的邏輯關(guān)系。第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1834雙向鏈表：雙向鏈表：一個指向其前件結(jié)點，稱為一個指向其前件結(jié)點，稱為前件指針前件指針或或左指針左指針；另一指向其后件結(jié)點，稱為另一指向其后件結(jié)點，稱為后件指針后件指針或或右指針右指針。第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-18357.6 樹與二叉樹樹與二叉樹7.6.1 樹的基本概念樹的基本概念樹（樹

19、（tree）是一種非線性結(jié)構(gòu)，其所有數(shù)據(jù)元素之間的是一種非線性結(jié)構(gòu)，其所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特點。關(guān)系具有明顯的層次特點。ABDCEFGHIJ第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1836實際上，能用樹結(jié)構(gòu)表示的例子有許多。實際上，能用樹結(jié)構(gòu)表示的例子有許多。數(shù)理學(xué)院數(shù)學(xué)系化學(xué)系物理系基礎(chǔ)數(shù)學(xué)教研室應(yīng)用數(shù)學(xué)教研室基礎(chǔ)物理教研室電子信息教研室普通化學(xué)教研室應(yīng)用化學(xué)教研室第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1837樹的基本特征和基本術(shù)語：樹的基本特征和基本術(shù)語：每一個結(jié)點只有一個前件，稱為每一個結(jié)點只有一個前件，稱為父結(jié)點父結(jié)點。沒有前件的結(jié)點只有一個，稱為沒有前件的結(jié)點只有一個，

20、稱為根結(jié)點根結(jié)點（簡稱（簡稱根根）。）。每一個結(jié)點可以有多個后件，稱為該結(jié)點的每一個結(jié)點可以有多個后件，稱為該結(jié)點的子結(jié)點子結(jié)點。沒有后件的結(jié)點稱為沒有后件的結(jié)點稱為葉子結(jié)點葉子結(jié)點。個結(jié)點所擁有的后件的個數(shù)稱為該個結(jié)點所擁有的后件的個數(shù)稱為該結(jié)點的度結(jié)點的度。所有結(jié)點中的最大的度稱為所有結(jié)點中的最大的度稱為樹的度樹的度。樹的最大層數(shù)稱為樹的最大層數(shù)稱為樹的深度樹的深度。以某結(jié)點的一個子結(jié)點為根構(gòu)成的樹稱為該結(jié)點的一棵以某結(jié)點的一個子結(jié)點為根構(gòu)成的樹稱為該結(jié)點的一棵 子樹子樹。ABDCEFGHIJ第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-18387.6.2 二叉樹及其基本運算二叉樹及其基本運算1二

21、叉樹的基本概念二叉樹的基本概念兩個特點：兩個特點： 非空二叉樹只有一個根結(jié)點；非空二叉樹只有一個根結(jié)點； 每個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的每個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹左子樹與與右子樹右子樹。ABCDGHEFIJ第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1839圖中所示的是圖中所示的是4顆不同的二叉樹，但如果作為樹，它們就相顆不同的二叉樹，但如果作為樹，它們就相同了。同了。ABCABCABCABC第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-18402滿二叉樹與完全二叉樹滿二叉樹與完全二叉樹（1） 滿二叉樹滿二叉樹在一顆二叉樹中，如果所有分支結(jié)點都存在左子樹和右子在一顆二叉樹中

22、，如果所有分支結(jié)點都存在左子樹和右子樹，并且所有葉子結(jié)點都在同一層上，這樣的二叉樹樹，并且所有葉子結(jié)點都在同一層上，這樣的二叉樹稱為稱為滿二叉樹滿二叉樹。第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1841（2） 完全二叉樹完全二叉樹完全二叉樹完全二叉樹是指除最后一層外，每一層上的結(jié)點數(shù)均達到最是指除最后一層外，每一層上的結(jié)點數(shù)均達到最大值，而在最后一層上只缺少右邊的若干結(jié)點。大值，而在最后一層上只缺少右邊的若干結(jié)點。第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-18423二叉樹的基本性質(zhì)二叉樹的基本性質(zhì)二叉樹具有下列重要性質(zhì)：二叉樹具有下列重要性質(zhì)：性質(zhì)性質(zhì)1 在二叉樹中，第在二叉樹中，第i層的結(jié)點數(shù)最多

23、為層的結(jié)點數(shù)最多為2i-1個（個（i1）。）。性質(zhì)性質(zhì)2 在深度為在深度為k的二叉樹中，結(jié)點總數(shù)最多為的二叉樹中，結(jié)點總數(shù)最多為2k-1個個（k1）。）。第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1843例如，在圖例如，在圖7.25所示的二叉樹中，有所示的二叉樹中，有5個葉子結(jié)點，有個葉子結(jié)點，有4個度個度為為2的結(jié)點，度為的結(jié)點，度為0的結(jié)點比度為的結(jié)點比度為2的結(jié)點多一個。的結(jié)點多一個。性質(zhì)性質(zhì)3 對任意一棵二叉樹，度為對任意一棵二叉樹，度為0的結(jié)點（即葉子結(jié)點）總的結(jié)點（即葉子結(jié)點）總是比度為是比度為2的結(jié)點多一個。的結(jié)點多一個。第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1844性質(zhì)性質(zhì)4 （1

24、）具有）具有n個結(jié)點的二叉樹，其深度至少為個結(jié)點的二叉樹，其深度至少為log2n+1，其中，其中l(wèi)og2n表示取表示取log2n的整數(shù)部分。的整數(shù)部分。（2）具有）具有n個結(jié)點的完全二叉樹的深度為個結(jié)點的完全二叉樹的深度為log2n+1。第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1845性質(zhì)性質(zhì)5 如果對一棵有如果對一棵有n個結(jié)點的完全二叉樹的結(jié)點從個結(jié)點的完全二叉樹的結(jié)點從1到到n按層序編號，按層序編號，則對任一結(jié)點則對任一結(jié)點i（1in），有），有（1）如果）如果i=1，則結(jié)點，則結(jié)點i是二叉樹的根，它沒有父結(jié)點；如果是二叉樹的根，它沒有父結(jié)點；如果i1，則其，則其父結(jié)點編號為父結(jié)點編號為i/

25、2。（2）如果）如果2in，則結(jié)點，則結(jié)點i無左子結(jié)點（結(jié)點無左子結(jié)點（結(jié)點i為葉子結(jié)點）；否則，其左為葉子結(jié)點）；否則，其左子結(jié)點是結(jié)點子結(jié)點是結(jié)點2i。（3）如果）如果2i+1n，則結(jié)點，則結(jié)點i無右子結(jié)點；否則，其右子結(jié)點是結(jié)點無右子結(jié)點；否則，其右子結(jié)點是結(jié)點2i+1。根據(jù)完全二叉樹的這個性質(zhì)，如果按從上到下、從左到右順序存儲完全根據(jù)完全二叉樹的這個性質(zhì)，如果按從上到下、從左到右順序存儲完全二叉樹的各結(jié)點，則很容易確定每一個結(jié)點的父結(jié)點、左子結(jié)點和右二叉樹的各結(jié)點，則很容易確定每一個結(jié)點的父結(jié)點、左子結(jié)點和右子結(jié)點的位置。子結(jié)點的位置。 第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-18467

26、.6.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。用于存儲二叉樹中各元素的存儲結(jié)點由兩部分組成：用于存儲二叉樹中各元素的存儲結(jié)點由兩部分組成：數(shù)據(jù)數(shù)據(jù)域域與與指針域指針域。第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-18477.6.4 二叉樹的遍歷二叉樹的遍歷分為三種：分為三種：前序遍歷前序遍歷、中序遍歷中序遍歷、后序遍歷后序遍歷。下面分別介紹這三種遍歷的方法，并用下面分別介紹這三種遍歷的方法，并用 D 表示表示“訪問根結(jié)點訪問根結(jié)點” L 表示表示“遍歷根結(jié)點的左子樹遍歷根結(jié)點的左子樹 R 表示表示“遍歷根結(jié)點的右子樹遍歷根結(jié)點的右子樹”。第7章 數(shù)

27、據(jù)結(jié)構(gòu)與算法2021-11-18481前序遍歷（前序遍歷（DLR）是指首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹是指首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹例如，對圖例如，對圖7.31中的二叉樹進行中的二叉樹進行前序遍歷前序遍歷，則為，則為ABDGCEHIF。ABDGCEFHI第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-18492中序遍歷（中序遍歷（LDR）是指首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。是指首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。例如，對圖例如，對圖7.31中的二叉樹進行中的二叉樹進行中序遍歷中序遍歷，則為，則為DGBAHEICF。ABDGCEFHI第7章 數(shù)

28、據(jù)結(jié)構(gòu)與算法2021-11-18503后序遍歷（后序遍歷（LRD）是指首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。是指首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。例如，對圖例如，對圖7.31中的二叉樹進行中的二叉樹進行后序遍歷后序遍歷，則為，則為GDBHIEFCA。ABDGCEFHI第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-18517.7 查找與排序技術(shù)查找與排序技術(shù)7.7.1 順序查找順序查找順序查找又稱為順序搜索。順序查找又稱為順序搜索。順序查找是指在線性表中查找指定的元素，例如在線性表順序查找是指在線性表中查找指定的元素，例如在線性表（a a1 1，a a2 2，a ai i，a a

29、n n）中查找中查找 x x。第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-18527.7.2 二分法查找二分法查找二分法查找只適用于順序存儲的有序表，即要求線性表中的二分法查找只適用于順序存儲的有序表，即要求線性表中的元素按元素值的大小排列（遞減排列或遞增排列）。元素按元素值的大小排列（遞減排列或遞增排列）。第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-18537.7.3 交換類排序法交換類排序法1冒泡排序法冒泡排序法原序列原序列628131957第第1遍（從前往后）遍（從前往后）261318579（從后往前）（從后往前）126135879第第2遍（從前往后）遍（從前往后）121356789（從后往前）（從

30、后往前）112356789第第3遍（從前往后）遍（從前往后）112356789最后結(jié)果最后結(jié)果112356789第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-18547.7.3 插入類排序法插入類排序法1簡單插入排序法簡單插入排序法第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-18557.7.4 選擇類排序法選擇類排序法1簡單選擇排序法簡單選擇排序法 第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1856選擇題 1算法具有五個特性，以下選項中不屬于算法特性的是（ ）。 A) 有窮性 B) 簡潔性 C) 可行性 D)確定性 答案：B 第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1857選擇題 2算法的時間復(fù)雜度是指（ ）。A

31、） 執(zhí)行算法程序所需要的時間B） 算法程序的長度C） 算法執(zhí)行過程中所需要的基本運算次數(shù)D） 算法程序中的指令條數(shù)答案：C 第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1858選擇題 3算法的空間復(fù)雜度是指（ ）。A） 算法程序的長度B） 算法程序中的指令條數(shù)C） 算法程序所占的存儲空間D） 算法執(zhí)行過程中所需要的存儲空間答案：D第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1859選擇題 4數(shù)據(jù)的存儲結(jié)構(gòu)是指（ ）。A） 數(shù)據(jù)所占的存儲空間量 B） 數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示C） 數(shù)據(jù)在計算機中的順序存儲方式 D） 存儲在外存中的數(shù)據(jù)答案：B 第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1860選擇題 5下

32、列對于線性表的描述中正確的是（ ）。 A) 存儲空間不一定是連續(xù)，且各元素的存儲順序是任意的 B) 存儲空間不一定是連續(xù)，且前件元素一定存儲在后件元素的前面 C) 存儲空間必須連續(xù)，且各前件元素一定存儲在后件元素的前面 D) 存儲空間必須連續(xù)，且各元素的存儲順序是任意的答案：A 第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1861選擇題 6下列關(guān)于棧的敘述中正確的是（ ）。A） 在棧中只能插入數(shù)據(jù) B）在棧中只能刪除數(shù)據(jù)C） 棧是先進先出的線性表 D）棧是先進后出的線性表答案：D 第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1862選擇題 7下列關(guān)于棧的描述中錯誤的是（ ）。A) 棧是先進后出的先性表 B

33、) 棧只能順序存儲 C) 棧具有記憶作用 D) 對棧的插入和刪除操作中，不需要改變棧底指針答案：B 第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1863選擇題 8下列關(guān)于隊列的敘述中正確的是（ ）。A） 在隊列中只能插入數(shù)據(jù) B） 在隊列中只能刪除數(shù)據(jù)C） 隊列是先進先出的線性表 D） 隊列是先進后出的線性表答案：C 第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1864選擇題 9下列敘述中正確的是（ ）。A） 線性表是線性結(jié)構(gòu) B） 棧與隊列是非線性結(jié)構(gòu)C） 線性鏈表是非線性結(jié)構(gòu) D） 二叉樹是線性結(jié)構(gòu)答案：A第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1865選擇題 10下列數(shù)據(jù)結(jié)構(gòu)具有記憶功能的是（ ）。

34、A）隊列 B）循環(huán)隊列 C）棧 D）順序表答案：C第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1866選擇題 11遞歸算法一般需要利用（ ）實現(xiàn)。 A）棧 B）隊列 C）循環(huán)鏈表 D）雙向鏈表答案：A 第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1867選擇題 12下列敘述中正確的是（ ）。 A）線性鏈表中的各元素在存儲空間中的位置必須是連續(xù)的 B）線性鏈表中的表頭元素一定存儲在其他算數(shù)的前面 C）線性鏈表中的各元素在存儲空間中的位置不一定是連續(xù)的，但表頭元素一定存儲在其他算數(shù)的前面 D）線性鏈表中的各元素在存儲空間中的位置不一定是連續(xù)的，且各元素的存儲順序也是任意的。答案：D 第7章 數(shù)據(jù)結(jié)構(gòu)與算法20

35、21-11-1868選擇題 13設(shè)有下列二叉樹： 二叉樹中序遍歷的結(jié)果為（ ）。A） ABCDEF B） DBEAFC C） ABDECF D） DEBFCA答案：B 第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1869選擇題 14在深度為5的滿二叉樹中，葉子結(jié)點的個數(shù)為（ ）。A） 32 B） 31 C） 16 D） 15答案：C 第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1870選擇題 15設(shè)樹T的度為4，其中度為1，2，3，4的結(jié)點個數(shù)分別為4，2，1，1。則T中的葉子結(jié)點數(shù)為（ ）。A） 8 B） 7 C） 6 D） 5答案：A第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1871選擇題 16設(shè)一棵二叉

36、樹中有3個葉子結(jié)點，有8個度為1的結(jié)點，則該二叉樹中總的結(jié)點數(shù)為（ ）。A） 12 B） 13 C） 14 D）15答案：B 第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1872選擇題 17對長度為n的線性表進行順序查找，在最壞情況下所需要的比較次數(shù)為（ ）。A） n+l B） n C） （n+1）/2 D） n/2答案：B 第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1873選擇題 18在長度為n的有序線性表中進行二分法查找，需要的比較次數(shù)為（ ）。A）log2n B） nlog2n C） n/2 D） (n+1)/2答案：A第7章 數(shù)據(jù)結(jié)構(gòu)與算法2021-11-1874選擇題 19對于長度為N的線性表，在最壞的情況下，下列各排序法所對應(yīng)的比較次數(shù)中正確的是（ ）。 A) 冒泡