公共基礎(chǔ)知識(shí)PPT課件

1、二、數(shù)據(jù)結(jié)構(gòu)：1、數(shù)據(jù)結(jié)構(gòu)：相互之間存在一種或多種特定關(guān)系和數(shù)據(jù)元素的集合，即數(shù)據(jù)的組織形式，它主要研究三個(gè)方面：邏輯結(jié)構(gòu)：數(shù)據(jù)集合中各數(shù)據(jù)元素之間固有的邏輯關(guān)系數(shù)據(jù)結(jié)構(gòu)主要分為線性結(jié)構(gòu)與非線性結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)：各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行運(yùn)算2、線性結(jié)構(gòu)：非空數(shù)據(jù)結(jié)構(gòu)滿足有且只有一個(gè)根結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)至少有一個(gè)前件，也最多有一個(gè)后件第1頁(yè)/共24頁(yè) 3、線性表的順序存儲(chǔ) 線性表是最簡(jiǎn)單、最常用的一種數(shù)據(jù)結(jié)構(gòu)。 （1）線性表的所有元素所占的存儲(chǔ)空間是連續(xù)的。 （2）各數(shù)據(jù)元素在存儲(chǔ)空間是按邏輯順序存放的。 它是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)第2頁(yè)/共24頁(yè) 4、棧：只能在表的一端進(jìn)行插入

2、和刪除運(yùn)算的線性表，能進(jìn)行插入和刪除操作的為棧頂，另一端為棧底，表中沒有元素為空棧。 特點(diǎn)：先進(jìn)后出 棧的操作：入棧、退棧、讀取棧的元素 -入棧運(yùn)算是指在棧頂位置插入一個(gè)新的元素 -退棧運(yùn)算是指取出棧頂元素并賦給一個(gè)指定變量 -讀棧頂元素是指將棧頂元素賦給一個(gè)指定的變量。 當(dāng)棧頂指針為0時(shí)，說明?？?，不可能進(jìn)行退棧操作。稱為“下溢”錯(cuò)誤。第3頁(yè)/共24頁(yè)例1：ABCD依次入棧又依次出棧，出棧順序是_例2：若進(jìn)棧序列為1、2、3、4，進(jìn)棧過程可以出棧，則（ ）不可能是一個(gè)出棧序列。A、1、4、3、2 B、2、3、4、1 C、3、1、4、2 D、3、4、2、1第4頁(yè)/共24頁(yè)21第5頁(yè)/共24頁(yè)

3、5、隊(duì)列：只允許在一端刪除，另一端插入的順序表，允許刪除的一端叫隊(duì)頭(front頭指針)，允許插入的一端叫隊(duì)尾(rear尾指針)，隊(duì)中沒有元素叫空隊(duì)。 特點(diǎn)：先進(jìn)先出 操作：進(jìn)隊(duì)，退隊(duì)第6頁(yè)/共24頁(yè) 循環(huán)隊(duì)列及其計(jì)算 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)一般采用循環(huán)隊(duì)列的形式。所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞道第一個(gè)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用。-入隊(duì)運(yùn)算（rear=rear+1）-退隊(duì)運(yùn)算（front=front+1）當(dāng)循環(huán)隊(duì)列為空（s=0）時(shí)，不能進(jìn)行退隊(duì)運(yùn)算，稱為“下溢”*計(jì)算公式：*（非循環(huán)隊(duì)列）元素的個(gè)數(shù)尾指針頭指針（循環(huán)隊(duì)列）元素的個(gè)數(shù)（尾指針頭指針 + 容量）除以

4、容量 所得的余數(shù)第7頁(yè)/共24頁(yè) 6、線性鏈表：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。在存儲(chǔ)時(shí)，每個(gè)結(jié)點(diǎn)有兩部分組成，一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域，另一部分用來存放指針，稱為指針域，其中指針用來指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)。（即前件或后件） 分為線性單鏈表與線性雙向鏈表 操作：插入、刪除 7、循環(huán)鏈表：最后一個(gè)結(jié)點(diǎn)的指針域不是空而是指向表頭結(jié)點(diǎn)，即在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成了一個(gè)環(huán)狀鏈。 第8頁(yè)/共24頁(yè) 8、樹與二叉樹 （1）樹：是一種簡(jiǎn)單的非線性結(jié)構(gòu) 根結(jié)點(diǎn)，只有直接后件沒有直接前件 除根結(jié)點(diǎn)以外的其它結(jié)點(diǎn)可以劃分為M（M=0）個(gè)互不相交的有限集合，每個(gè)集合又是一棵樹，稱為根的

5、子樹。 度：一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中的最大度稱為樹的度。 樹的深度：指最大層次數(shù)。 （2）二叉樹：樹的每個(gè)結(jié)點(diǎn)最多只能有兩棵子樹，并且分別稱為該結(jié)點(diǎn)的左子樹與右子樹第9頁(yè)/共24頁(yè) 滿二叉樹：除最后一層外，每一層所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn) 完全二叉樹：除最后一層外，每一層的結(jié)點(diǎn)都達(dá)到最大值，在最后的一層上只缺少右邊的若干個(gè)結(jié)點(diǎn)。 (圖36頁(yè))第10頁(yè)/共24頁(yè) 二叉樹的性質(zhì)： 1、在二叉樹的第k層上，最多有2k-1（k1）個(gè)結(jié)點(diǎn)。 2、深度為m的二叉樹最多有2m-1個(gè)結(jié)點(diǎn)。 3、在任意一棵二叉樹中，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)。 4、具有n個(gè)結(jié)點(diǎn)的二

6、叉樹，其深度至少為log2n+1,其中l(wèi)og2n表示取log2n的整數(shù)部分。第11頁(yè)/共24頁(yè) （3）二叉樹的遍歷： 前序：根左右 中序：左根右 后序：左右根 二叉樹的存儲(chǔ)： 二叉樹通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ABDEGCF DBGEACF DGEBFCA第12頁(yè)/共24頁(yè) 例 前序遍歷：abdgcefh 中序遍歷：dgbaecfh 后序遍歷：gdbehfcaDBEAFC ABDECF A B C D E F第13頁(yè)/共24頁(yè)第14頁(yè)/共24頁(yè) 題：1.設(shè)樹T的度為4，其中度為1、2、3、4的結(jié)點(diǎn)個(gè)數(shù)分別為4,2,1,1,則T中的葉子結(jié)點(diǎn)數(shù)為 A:8 B:7 C:6 D:5 2.設(shè)一棵完全二叉樹共有

7、700個(gè)結(jié)點(diǎn)，則在該二叉樹中有 個(gè)葉子結(jié)點(diǎn)。 3.設(shè)一棵二叉樹的中序遍歷結(jié)果為DBEAFC,前序?yàn)锳BDECF,后續(xù) 4.在一個(gè)容量為15的循環(huán)隊(duì)列中，若頭指針FRONT=6，尾指針REAR=9，則該循環(huán)隊(duì)列中共有 元素。 5.深度為5的滿二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為 A.32 B.31 C.16 D.15第15頁(yè)/共24頁(yè) 9、查找 （1）、順序查找，在最壞情況下，順序查找需要比較n次 例：A B C D E F39頁(yè) （2）、二分查找，在最壞情況下，二分查找需要比較log2n次 計(jì)算規(guī)則：39頁(yè) 例：已知一個(gè)有序表為（13，18，24，35，47，50，62，83，90，115，134），當(dāng)

8、使用二分法查找值為90的元素時(shí)，查找成功的比較次數(shù)為 B 。 A.1 B.2 C.3 D.4第16頁(yè)/共24頁(yè)51 7 3 1 6 9 4 2 8 615 3 1 6 7 4 2 8 6 91 1 5 3 2 6 7 4 6 8 9第17頁(yè)/共24頁(yè) 10、排序 （1）交換類排序 1）冒泡排序 n(n-1)/2例41頁(yè)第18頁(yè)/共24頁(yè) 2）快速排序 n(n-1)/2 例：對(duì)序列15、9、7、8、20、-1、4用快速排序方法進(jìn)行排序（按遞增序），以第一個(gè)元素作為劃分的基準(zhǔn)，在第一次劃分后數(shù)據(jù)的排列是（ ）。 A、9，7，8，4，-1，15，20 B、20，15，8，9，、-1，4，7 C、-1，4，7，8，9，15，20 D、4，9，7，8，-1，15，20第19頁(yè)/共24頁(yè) （2）插入類排序 1）簡(jiǎn)單插入排序n(n-1)/2 例：初始為 5 | 1 7 3 1 6一次插入排序，把第一個(gè)1插入前邊已排序部分，得1 5 | 7 3 1 6后邊依次是1 5 7 | 3 1 61 3 5 7 | 1 61 1 3 5 7 | 61 1 3 5 6 7 | 例：5 1 7 3 1 6 9 4 2 8 6 43頁(yè) 2）希爾排序 O(n1.5)第20頁(yè)/共24頁(yè) （3）選擇類排序 1）簡(jiǎn)單的選擇排序 n(n-1)/2 掃描整個(gè)線性表，從中選出最小