大學計算機基礎-07數(shù)據(jù)結構與算法

1、大學計算機基礎-07數(shù)據(jù)結構與算法第一頁，共90頁。7.1 算 法7.1.1 算法的基本概念1算法的基本特征 （1）可行性 （2）確定性 （3）有窮性 （4）有零個或多個輸入 （5）有一個或多個輸出一個算法，就是一組定義了運算順序的規(guī)則，并且每個規(guī)則都是有效的、明確的，此運算順序?qū)⒃谟邢薜牟襟E后終止。10/8/20222第二頁，共90頁。對數(shù)據(jù)對象的運算和操作，算法的控制結構。2算法的基本要素10/8/20223第三頁，共90頁。（1）算法中對數(shù)據(jù)的運算和操作 算術運算：主要包括加、減、乘、除等運算。 邏輯運算：主要包括“邏輯與”、“邏輯或”、“邏輯非”等運算。 關系運算：主要包括“大于”、“

2、大于或等于”、“小于”、“小于或等于”、“等于”、“不等于”等運算。 數(shù)據(jù)傳輸：主要包括賦值、輸入、輸出等操作。10/8/20224第四頁，共90頁。（2）算法的控制結構算法中各種操作之間的執(zhí)行順序稱為算法的控制結構。一個算法一般都可以用順序結構、選擇結構、和循環(huán)結構這三種基本控制結構組合而成。10/8/20225第五頁，共90頁。3算法設計基本方法 （1） 列舉法 列舉法就是根據(jù)所要解決的問題，把所有可能的情況都一一列舉出來，并用問題中給定的條件來檢驗哪些是需要的，哪些是不需要的。例如：設x,y為非負整數(shù)，求滿足方程 2x+3y=10的x,y。10/8/20226第六頁，共90頁。（2）歸納

3、法 歸納法的基本思想是通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關系。 可以看出，歸納法可以解決列舉量為無限的問題。 10/8/20227第七頁，共90頁。（3）遞推 遞推是指從已知的初始條件出發(fā)，逐步推出所要求的結果。例如：求 x2=a 的遞推公式：10/8/20228第八頁，共90頁。（4）遞歸 在解決某些復雜問題時，為了降低問題的復雜程度（如問題的規(guī)模等），可以將問題逐層分解，最后歸結為一些最簡單的問題。10/8/20229第九頁，共90頁。例7.2 有5個人坐在一起，問第5個人的歲數(shù)，他說比第4個人大2歲。問第4個人的歲數(shù)，他說比第3個人大2歲。問第3個人的歲數(shù)，他說比第2個人大

4、2歲。問第2個人的歲數(shù)，他說比第1個人大2歲。問第1個人的歲數(shù)，他說是10歲。請問第5個人多大。 10/8/202210第十頁，共90頁。這個問題可以用遞歸方法解決。遞歸過程如下： age（5）age（4）十2 age（4）age（3）十2 age（3）age（2）十2 age（2）age（1）十2 age（ l）1010/8/202211第十一頁，共90頁。（5）減半遞推技術 “減半”是指將問題的規(guī)模減半，而問題的性質(zhì)不變；“遞推”是指重復“減半”的過程。10/8/202212第十二頁，共90頁。 7.1.2 算法的復雜度 可分為時間復雜度和空間復雜度。 1算法的時間復雜度 算法的時間復雜度

5、是指執(zhí)行算法所需要的計算工作量。 例如：兩個n階方陣的乘積的乘法次數(shù)為n3。 兩種常用方法：（1） 平均性態(tài)（2）最壞情況復雜性10/8/202213第十三頁，共90頁。2算法的空間復雜度算法的空間復雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。類似算法的時間復雜度，空間復雜度作為算法所需存儲空間的度量。 10/8/202214第十四頁，共90頁。7.2 數(shù)據(jù)結構的基本概念數(shù)據(jù)結構主要研究三個問題： （1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關系，即數(shù)據(jù)的邏輯結構； （2）在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲關系，即數(shù)據(jù)的存儲結構； （3）對各種數(shù)據(jù)結構進行的運算。10/8/202215第十

6、五頁，共90頁。例7.5 無序表的順序查找與有序表的對分查找。7.2 數(shù)據(jù)結構的基本概念7.2.1 什么是數(shù)據(jù)結構10/8/202216第十六頁，共90頁。現(xiàn)實世界中存在的一切個體都可以是數(shù)據(jù)元素（簡稱元素）。例如： 春、夏、秋、冬； 26、56、65、 73、26、； 父親、兒子、女兒。數(shù)據(jù)元素之間的關系可用前后件關系例如， “春”是“夏”前件，“夏”是“春”的后件。10/8/202217第十七頁，共90頁。1數(shù)據(jù)的邏輯結構指數(shù)據(jù)之間的邏輯關系，與它們在計算機中的存儲位置無關。有兩個基本要素： 表示數(shù)據(jù)元素的信息，通常記為D； 表示各數(shù)據(jù)元素之間的前后件關系，通常記為R。例7.2 一年四季的

7、數(shù)據(jù)結構可以表示成 B=（D，R） D=春，夏，秋，冬 R=（春，夏），（夏，秋），（秋，冬）10/8/202218第十八頁，共90頁。例7.3 家庭成員數(shù)據(jù)結構可以表示成 B=（D， R） D=父親，兒子，女兒 R=（父親，兒子），（父親，女兒）10/8/202219第十九頁，共90頁。2數(shù)據(jù)的存儲結構 數(shù)據(jù)的邏輯結構在計算機存儲空間中的存放形式稱為數(shù)據(jù)的存儲結構（也稱數(shù)據(jù)的物理結構）。 一種數(shù)據(jù)的邏輯結構可以表示成多種存儲結構。 常用的存儲結構有順序、鏈接、索引等存儲結構。10/8/202220第二十頁，共90頁。7.2.2 數(shù)據(jù)結構的圖形表示10/8/202221第二十一頁，共90頁。7

8、.2.3 線性結構與非線性結構如果一個數(shù)據(jù)結構滿足：（1）有且只有一個根結點；（2）每個結點最多有一個前件，也最多有一個后件。則稱該數(shù)據(jù)結構為線性結構。線性結構又稱線性表。10/8/202222第二十二頁，共90頁。7.3 線性表及其順序存儲結構7.3.1 線性表的基本概念線性表是指n個數(shù)據(jù)元素的有限序列。線性表可以表示為 （a1，a2，ai，an），當n=0時，稱為空表。 10/8/202223第二十三頁，共90頁。7.3.2 線性表的順序存儲結構順序存儲的特點如下：（1）線性表中所有元素所占的存儲空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。10/8/20222

9、4第二十四頁，共90頁。7.3.3 順序表的插入運算10/8/202225第二十五頁，共90頁。7.3.4 線性表的刪除運算10/8/202226第二十六頁，共90頁。7.4 棧和隊列7.4.1 棧及其基本運算 1棧的基本概念棧（stack）是限定僅在一端進行插入和刪除運算的線性表。在棧中，允許插入與刪除的一端稱為棧頂，而不允許插入與刪除的另一端稱為棧底。10/8/202227第二十七頁，共90頁。棧的順序存儲結構如圖所示。10/8/202228第二十八頁，共90頁。2棧的基本運算 有三種：入棧、退棧與讀棧頂元素。（1） 入棧運算首先將棧頂指針進一，然后將新元素插入到棧頂指針指向的位置；10/

10、8/202229第二十九頁，共90頁。（2） 退棧運算首先將棧頂元素賦給一個指定的變量，然后將棧頂指針退一。（3） 讀棧頂元素是指將棧頂元素賦給一個指定的變量。棧頂指針不會改變。10/8/202230第三十頁，共90頁。7.4.2 隊列及其基本運算1隊列的基本概念隊列（queue）是在表的一端進行插入，在表的另一端進行刪除的線性表。在隊列中，允許插入的一端稱為隊尾， 允許刪除的一端稱為隊頭。隊列又稱為“先進先出”或“后進后出”的線性表。在隊列中，常用指針front 指向隊頭，用rear指向隊尾，如圖所示。10/8/202231第三十一頁，共90頁。圖7.11是在隊列中進行插入與刪除的示意圖。

11、10/8/202232第三十二頁，共90頁。7.5 線性鏈表7.5.1 線性鏈表的基本概念1線性鏈表其鏈表結構如圖（a）所示。實際上，常用圖（b）來表示它們的邏輯關系。10/8/202233第三十三頁，共90頁。雙向鏈表：一個指向其前件結點，稱為前件指針或左指針；另一指向其后件結點，稱為后件指針或右指針。10/8/202234第三十四頁，共90頁。7.6 樹與二叉樹7.6.1 樹的基本概念樹（tree）是一種非線性結構，其所有數(shù)據(jù)元素之間的關系具有明顯的層次特點。10/8/202235第三十五頁，共90頁。實際上，能用樹結構表示的例子有許多。10/8/202236第三十六頁，共90頁。樹的基本

12、特征和基本術語：每一個結點只有一個前件，稱為父結點。沒有前件的結點只有一個，稱為根結點（簡稱根）。每一個結點可以有多個后件，稱為該結點的子結點。沒有后件的結點稱為葉子結點。個結點所擁有的后件的個數(shù)稱為該結點的度。所有結點中的最大的度稱為樹的度。樹的最大層數(shù)稱為樹的深度。以某結點的一個子結點為根構成的樹稱為該結點的一棵 子樹。10/8/202237第三十七頁，共90頁。7.6.2 二叉樹及其基本運算1二叉樹的基本概念兩個特點： 非空二叉樹只有一個根結點； 每個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。10/8/202238第三十八頁，共90頁。圖中所示的是4顆不同的二叉樹，但如果作為

13、樹，它們就相同了。10/8/202239第三十九頁，共90頁。2滿二叉樹與完全二叉樹（1） 滿二叉樹在一顆二叉樹中，如果所有分支結點都存在左子樹和右子樹，并且所有葉子結點都在同一層上，這樣的二叉樹稱為滿二叉樹。10/8/202240第四十頁，共90頁。（2） 完全二叉樹完全二叉樹是指除最后一層外，每一層上的結點數(shù)均達到最大值，而在最后一層上只缺少右邊的若干結點。10/8/202241第四十一頁，共90頁。3二叉樹的基本性質(zhì)二叉樹具有下列重要性質(zhì)：性質(zhì)1 在二叉樹中，第i層的結點數(shù)最多為2i-1個（i1）。性質(zhì)2 在深度為k的二叉樹中，結點總數(shù)最多為2k-1個（k1）。10/8/202242第四

14、十二頁，共90頁。例如，在圖7.25所示的二叉樹中，有5個葉子結點，有4個度為2的結點，度為0的結點比度為2的結點多一個。性質(zhì)3 對任意一棵二叉樹，度為0的結點（即葉子結點）總是比度為2的結點多一個。10/8/202243第四十三頁，共90頁。性質(zhì)4 （1）具有n個結點的二叉樹，其深度至少為log2n+1，其中l(wèi)og2n表示取log2n的整數(shù)部分。（2）具有n個結點的完全二叉樹的深度為log2n+1。10/8/202244第四十四頁，共90頁。性質(zhì)5 如果對一棵有n個結點的完全二叉樹的結點從1到n按層序編號，則對任一結點i（1in），有（1）如果i=1，則結點i是二叉樹的根，它沒有父結點；如果

15、i1，則其父結點編號為i/2。（2）如果2in，則結點i無左子結點（結點i為葉子結點）；否則，其左子結點是結點2i。（3）如果2i+1n，則結點i無右子結點；否則，其右子結點是結點2i+1。根據(jù)完全二叉樹的這個性質(zhì)，如果按從上到下、從左到右順序存儲完全二叉樹的各結點，則很容易確定每一個結點的父結點、左子結點和右子結點的位置。 10/8/202245第四十五頁，共90頁。7.6.3 二叉樹的存儲結構二叉樹通常采用鏈式存儲結構。用于存儲二叉樹中各元素的存儲結點由兩部分組成：數(shù)據(jù)域與指針域。10/8/202246第四十六頁，共90頁。7.6.4 二叉樹的遍歷分為三種：前序遍歷、中序遍歷、后序遍歷。下

16、面分別介紹這三種遍歷的方法，并用 D 表示“訪問根結點” L 表示“遍歷根結點的左子樹 R 表示“遍歷根結點的右子樹”。10/8/202247第四十七頁，共90頁。1前序遍歷（DLR）是指首先訪問根結點，然后遍歷左子樹，最后遍歷右子樹例如，對圖7.31中的二叉樹進行前序遍歷，則為ABDGCEHIF。10/8/202248第四十八頁，共90頁。2中序遍歷（LDR）是指首先遍歷左子樹，然后訪問根結點，最后遍歷右子樹。例如，對圖7.31中的二叉樹進行中序遍歷，則為DGBAHEICF。10/8/202249第四十九頁，共90頁。3后序遍歷（LRD）是指首先遍歷左子樹，然后遍歷右子樹，最后訪問根結點。例

17、如，對圖7.31中的二叉樹進行后序遍歷，則為GDBHIEFCA。10/8/202250第五十頁，共90頁。7.7 查找與排序技術7.7.1 順序查找順序查找又稱為順序搜索。順序查找是指在線性表中查找指定的元素，例如在線性表（a1，a2，ai，an）中查找 x。10/8/202251第五十一頁，共90頁。7.7.2 二分法查找二分法查找只適用于順序存儲的有序表，即要求線性表中的元素按元素值的大小排列（遞減排列或遞增排列）。10/8/202252第五十二頁，共90頁。7.7.3 交換類排序法1冒泡排序法原序列628131957第1遍（從前往后）261318579（從后往前）126135879第2遍

18、（從前往后）121356789（從后往前）112356789第3遍（從前往后）112356789最后結果11235678910/8/202253第五十三頁，共90頁。7.7.3 插入類排序法1簡單插入排序法10/8/202254第五十四頁，共90頁。7.7.4 選擇類排序法1簡單選擇排序法 10/8/202255第五十五頁，共90頁。選擇題 1算法具有五個特性，以下選項中不屬于算法特性的是（ ）。 A) 有窮性 B) 簡潔性 C) 可行性 D)確定性 答案：B 10/8/202256第五十六頁，共90頁。選擇題 2算法的時間復雜度是指（ ）。A） 執(zhí)行算法程序所需要的時間B） 算法程序的長度C

19、） 算法執(zhí)行過程中所需要的基本運算次數(shù)D） 算法程序中的指令條數(shù)答案：C 10/8/202257第五十七頁，共90頁。選擇題 3算法的空間復雜度是指（ ）。A） 算法程序的長度B） 算法程序中的指令條數(shù)C） 算法程序所占的存儲空間D） 算法執(zhí)行過程中所需要的存儲空間答案：D10/8/202258第五十八頁，共90頁。選擇題 4數(shù)據(jù)的存儲結構是指（ ）。A） 數(shù)據(jù)所占的存儲空間量 B） 數(shù)據(jù)的邏輯結構在計算機中的表示C） 數(shù)據(jù)在計算機中的順序存儲方式 D） 存儲在外存中的數(shù)據(jù)答案：B 10/8/202259第五十九頁，共90頁。選擇題 5下列對于線性表的描述中正確的是（ ）。 A) 存儲空間不一

20、定是連續(xù)，且各元素的存儲順序是任意的 B) 存儲空間不一定是連續(xù)，且前件元素一定存儲在后件元素的前面 C) 存儲空間必須連續(xù)，且各前件元素一定存儲在后件元素的前面 D) 存儲空間必須連續(xù)，且各元素的存儲順序是任意的答案：A 10/8/202260第六十頁，共90頁。選擇題 6下列關于棧的敘述中正確的是（ ）。A） 在棧中只能插入數(shù)據(jù) B）在棧中只能刪除數(shù)據(jù)C） 棧是先進先出的線性表 D）棧是先進后出的線性表答案：D 10/8/202261第六十一頁，共90頁。選擇題 7下列關于棧的描述中錯誤的是（ ）。A) 棧是先進后出的先性表 B) 棧只能順序存儲 C) 棧具有記憶作用 D) 對棧的插入和刪

21、除操作中，不需要改變棧底指針答案：B 10/8/202262第六十二頁，共90頁。選擇題 8下列關于隊列的敘述中正確的是（ ）。A） 在隊列中只能插入數(shù)據(jù) B） 在隊列中只能刪除數(shù)據(jù)C） 隊列是先進先出的線性表 D） 隊列是先進后出的線性表答案：C 10/8/202263第六十三頁，共90頁。選擇題 9下列敘述中正確的是（ ）。A） 線性表是線性結構 B） 棧與隊列是非線性結構C） 線性鏈表是非線性結構 D） 二叉樹是線性結構答案：A10/8/202264第六十四頁，共90頁。選擇題 10下列數(shù)據(jù)結構具有記憶功能的是（ ）。 A）隊列 B）循環(huán)隊列 C）棧 D）順序表答案：C10/8/2022

22、65第六十五頁，共90頁。選擇題 11遞歸算法一般需要利用（ ）實現(xiàn)。 A）棧 B）隊列 C）循環(huán)鏈表 D）雙向鏈表答案：A 10/8/202266第六十六頁，共90頁。選擇題 12下列敘述中正確的是（ ）。 A）線性鏈表中的各元素在存儲空間中的位置必須是連續(xù)的 B）線性鏈表中的表頭元素一定存儲在其他算數(shù)的前面 C）線性鏈表中的各元素在存儲空間中的位置不一定是連續(xù)的，但表頭元素一定存儲在其他算數(shù)的前面 D）線性鏈表中的各元素在存儲空間中的位置不一定是連續(xù)的，且各元素的存儲順序也是任意的。答案：D 10/8/202267第六十七頁，共90頁。選擇題 13設有下列二叉樹： 二叉樹中序遍歷的結果為（

23、 ）。A） ABCDEF B） DBEAFC C） ABDECF D） DEBFCA答案：B 10/8/202268第六十八頁，共90頁。選擇題 14在深度為5的滿二叉樹中，葉子結點的個數(shù)為（ ）。A） 32 B） 31 C） 16 D） 15答案：C 10/8/202269第六十九頁，共90頁。選擇題 15設樹T的度為4，其中度為1，2，3，4的結點個數(shù)分別為4，2，1，1。則T中的葉子結點數(shù)為（ ）。A） 8 B） 7 C） 6 D） 5答案：A10/8/202270第七十頁，共90頁。選擇題 16設一棵二叉樹中有3個葉子結點，有8個度為1的結點，則該二叉樹中總的結點數(shù)為（ ）。A） 12

24、 B） 13 C） 14 D）15答案：B 10/8/202271第七十一頁，共90頁。選擇題 17對長度為n的線性表進行順序查找，在最壞情況下所需要的比較次數(shù)為（ ）。A） n+l B） n C） （n+1）/2 D） n/2答案：B 10/8/202272第七十二頁，共90頁。選擇題 18在長度為n的有序線性表中進行二分法查找，需要的比較次數(shù)為（ ）。A）log2n B） nlog2n C） n/2 D） (n+1)/2答案：A10/8/202273第七十三頁，共90頁。選擇題 19對于長度為N的線性表，在最壞的情況下，下列各排序法所對應的比較次數(shù)中正確的是（ ）。 A) 冒泡排序為N/2 B) 冒泡排序為N C) 快速排序為N D) 快速排序為N(N-1)/2答案：D 10/8/202274第七十四頁，共90頁。選擇題 20在最壞的情況下，下列排序方法中時間復雜度最小的是（ ）。A）冒泡排序 B） 快速排序 C） 插入排序 D）堆排序答案：D 10/8/202275第七十五頁，共90頁。選擇題 21希爾排序法屬于（ ）。A）選擇類排序 B）交換類排序 C）插入類排序 D）以上都不對答案：C10/8/202276第七十六頁，共90頁。填空題 1問題處理方案的正確而完整的描述稱為_。答案：算法 10/8/202277第七十七頁，共90頁。填空題 2一個算法通常