大學計算機基礎_07數據結構與算法

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

2、在有限個規(guī)則都是有效的、明確的，此運算順序將在有限的步驟后終止。的步驟后終止。第7章 數據結構與算法2021-11-183l 對數據對象的對數據對象的運算和操作運算和操作，l 算法的算法的控制結構控制結構。2算法的基本要素算法的基本要素第7章 數據結構與算法2021-11-184（1 1）算法中對數據的運算和操作）算法中對數據的運算和操作 算術運算算術運算：主要包括加、減、乘、除等運算。：主要包括加、減、乘、除等運算。 邏輯運算邏輯運算：主要包括：主要包括“邏輯與邏輯與”、“邏輯或邏輯或”、“邏輯非邏輯非”等運算。等運算。 關系運算關系運算：主要包括：主要包括“大于大于”、“大于或等于大于或等

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

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

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

6、據結構與算法2021-11-1810例例7.2 有有5個人坐在一起，個人坐在一起，問第問第5個人的歲數，他說比第個人的歲數，他說比第4個人大個人大2歲。歲。問第問第4個人的歲數，他說比第個人的歲數，他說比第3個人大個人大2歲。歲。問第問第3個人的歲數，他說比第個人的歲數，他說比第2個人大個人大2歲。歲。問第問第2個人的歲數，他說比第個人的歲數，他說比第1個人大個人大2歲。歲。問第問第1個人的歲數，他說是個人的歲數，他說是10歲。歲。請問第請問第5個人多大。個人多大。 第7章 數據結構與算法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章 數據結構與算法2021-11-1812（5）減半遞推技術）減半遞推技術 “減半減半”是指將問題的規(guī)模減半，而問題的性質不變；是指將問題的規(guī)模減半，而問題的性質不變；“遞推遞推”是指重復是指重復“減半減半”的過程。的過程。第7章 數據結構與算法2021-11-1813 7.1.2 算法的復雜度算法的復雜度 可分為可分為時間復雜度時間復雜度和和空間復雜度空間復雜度。 1算法的時間復雜度算法的時間復雜度 算法的時間復雜度算法的時間復雜度

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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