大學(xué)數(shù)據(jù)結(jié)構(gòu)演示文檔

《大學(xué)數(shù)據(jù)結(jié)構(gòu)演示文檔》由會員分享，可在線閱讀，更多相關(guān)《大學(xué)數(shù)據(jù)結(jié)構(gòu)演示文檔（64頁珍藏版）》請在裝配圖網(wǎng)上搜索。

.,第一章數(shù)據(jù)結(jié)構(gòu)與算法,1.1算法 1.2數(shù)據(jù)結(jié)構(gòu)的基本概念 1.3線性表及其順序存儲結(jié)構(gòu) 1.4棧和隊列 1.5線性鏈表 1.6樹與二叉樹 1.7查找技術(shù) 1.8排序技術(shù),.,1.1算法,1.1.1 算法的基本概念 算法：是指解題方案的準確而完整的描述。 算法不等于程序，也不等于計算機方法，程序的編制不可能優(yōu)于算法的設(shè)計。1、算法的基本特征：是一組嚴謹?shù)囟x運算順序的規(guī)則，每一個規(guī)則都是有效的，是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。,.,1.1算法,特征包括：（1）可行性；（2）確定性，算法中每一步驟都必須有明確定義，不允許有模棱兩可的解釋，不允許有多義性；（3）有窮性，算法必須能在有限的時間內(nèi)做完，取能在執(zhí)行有限個步驟后終止，包括合理的執(zhí)行時間的含義；（4）擁有足夠的情報。,.,1.1算法,2、算法的基本要素： 一是對數(shù)據(jù)對象的運算和操作； 二是算法的控制結(jié)構(gòu)。 基本運算和操作包括：算術(shù)運算、邏輯運算、關(guān)系運算、數(shù)據(jù)傳輸。 一個算法一般都可以用順序、選擇、循環(huán)三種基本控制結(jié)構(gòu)組合而成。,.,1.1算法,1.1.2算法的復(fù)雜度 算法時間復(fù)雜度和算法空間復(fù)雜度。,,.,1.1算法,1.算法的時間復(fù)雜度 算法時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量。算法的工作量用算法所執(zhí)行的基本運算次數(shù)來度量，而算法所執(zhí)行的基本運算次數(shù)是問題規(guī)模的函數(shù)，即 算法的工作量=f(n) 最壞情況復(fù)雜性：是指在規(guī)模為n時，算法所執(zhí)行的基本運算的最大次數(shù)。（例：O（n2）) 常見的時間復(fù)雜度，按數(shù)量級比較排列關(guān)系為：,,,.,1.1算法,2.算法空間復(fù)雜度 算法空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。 一個算法所占用的存儲空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲空間以及算法執(zhí)行過程中所需要的額外空間。,.,1.2數(shù)據(jù)結(jié)構(gòu)的基本概念,數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。 數(shù)據(jù)結(jié)構(gòu)研究的三個方面：（1）數(shù)據(jù)集合中和數(shù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；（2）在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)；（3）對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。 討論以上問題的主要目的是為了提高數(shù)據(jù)的效率。所謂提高數(shù)據(jù)處理的效率，主要包括兩個方面：一是提高數(shù)據(jù)處理的速度，二是盡量節(jié)省在數(shù)據(jù)處理過程中所占用的計算機存儲空間。,.,數(shù)據(jù)的邏輯結(jié)構(gòu)包含： （1）表示數(shù)據(jù)元素的信息； （2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。 數(shù)據(jù)的邏輯結(jié)構(gòu)分為：線性結(jié)構(gòu)與非線性結(jié)構(gòu) 線性結(jié)構(gòu)條件： （1）有且只有一個根結(jié)點； （2）每一個結(jié)點最多有一個前件，也最多有一個后件。 非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。,數(shù)據(jù)的邏輯結(jié)構(gòu),.,數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）。 數(shù)據(jù)的存儲結(jié)構(gòu)有順序、鏈接、索引等。,數(shù)據(jù)的存儲結(jié)構(gòu),.,1.3 線性表及其存儲結(jié)構(gòu),1.3.1 線性表的基本概念線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號，元素之間的相對位置是線性的。 　　　　　　　學(xué)生情登記表,.,在復(fù)雜線性表中，由若干項數(shù)據(jù)元素組成的數(shù)據(jù)元素稱為記錄，而由多個記錄構(gòu)成的線性表又稱為文件。 非空線性表的結(jié)構(gòu)特征： （1）有且只有一個根結(jié)點a1，它無前件； （2）有且只有一個終端結(jié)點an，它無后件； （3）除根結(jié)點與終端結(jié)點外，其他所有結(jié)點有且只有一個前件，也有且只有一個后件。結(jié)點個數(shù)n稱為線性表的長度，當n=0時，稱為空表。,.,線性表的順序存儲結(jié)構(gòu)具有以下兩個基本特點： （1）線性表中所有元素的所占的存儲空間是連續(xù)的； （2）線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。 ai的存儲地址為：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)為第一個元素的地址，k代表每個元素占的字節(jié)數(shù)。,線性表的順序存儲結(jié)構(gòu),.,順序表的基礎(chǔ)要點,1、線性表是具有n個數(shù)據(jù)元素的有限序列。 2、線性表的順序存儲結(jié)構(gòu)具有三個弱點： ①在插入和刪除時，需移動大量元素 ②由于難以估計，必須預(yù)先分配較大的空間 ③表的容量難以擴充 (如何解決？） 3、順序存儲結(jié)構(gòu)通過元素的相對存儲地址來表示元素之間的關(guān)系 4、線性表順序存儲的優(yōu)點是可隨機存取元素。 5、順序表中邏輯上相鄰的元素的物理位置必定緊鄰。 6、順序表是一種隨機存取的存儲結(jié)構(gòu)。 7、在順序表中插入或刪除一個元素時，需要平均移動表的一半元素，具有移動的元素個數(shù)與該元素的位置有關(guān)。 8、在長度為n的順序表中插入一個元素的時間復(fù)雜度為O(n)，刪除一個元素的時間復(fù)雜度為O(n)。,.,線性表的鏈式存儲結(jié)構(gòu)是指用一組任意的存儲單元（可以連續(xù)，也可以不連續(xù)）存儲線性表中的數(shù)據(jù)元素。因此，鏈表中結(jié)點的邏輯次序和物理次序不一定相同。為了能正確表示數(shù)據(jù)元素間的邏輯關(guān)系，對于每個數(shù)據(jù)元素不僅要表示它的具體內(nèi)容，還要附加一個表示它的直接后繼元素存儲位置的信息。這個信息稱為指針(pointer)或鏈(link)。這兩部分組成了鏈表中的結(jié)點結(jié)構(gòu)：,指針域，用來存放結(jié)點的直接后繼的地址,數(shù)據(jù)域，用來存放結(jié)點的值,1.4 線性表的鏈式存儲結(jié)構(gòu)--鏈表,.,術(shù)語 表示每個數(shù)據(jù)元素的兩部分信息組合在一起被稱為結(jié)點； 其中表示數(shù)據(jù)元素內(nèi)容的部分被稱為數(shù)據(jù)域（data）； 表示直接后繼元素存儲地址的部分被稱為指針或指針域（next）。,單聯(lián)表結(jié)構(gòu)示意圖,.,數(shù)據(jù)結(jié)構(gòu)中的每一個結(jié)點對應(yīng)于一個存儲單元，這種存儲單元稱為存儲結(jié)點，簡稱結(jié)點。 結(jié)點由兩部分組成：（1）用于存儲數(shù)據(jù)元素值，稱為數(shù)據(jù)域；（2）用于存放指針，稱為指針域，用于指向前一個或后一個結(jié)點。 在鏈式存儲結(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。 鏈式存儲方式即可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。,.,鏈式存儲結(jié)構(gòu)的特點 （1）線性表中的數(shù)據(jù)元素在存儲單元中的存放順序與邏輯順序不一定一致； （2）在對線性表操作時，只能通過頭指針進入鏈表，并通過每個結(jié)點的指針域向后掃描其余結(jié)點，這樣就會造成尋找第一個結(jié)點和尋找最后一個結(jié)點所花費的時間不等，具有這種特點的存取方式被稱為順序存取方式。,.,循環(huán)鏈表(circular linked list) 循環(huán)鏈表是表中最后一個結(jié)點的指針指向頭結(jié)點，使鏈表構(gòu)成環(huán)狀 特點：從表中任一結(jié)點出發(fā)均可找到表中其他結(jié)點，提高查找效率,.,例題講解,.,鏈表不具有的特點是 A) 不必事先估計存儲空間 B) 可隨機訪問任一元素 C) 插入刪除不需要移動元素 D) 所需空間與線性表長度成正比 用鏈表表示線性表的優(yōu)點是 A) 便于隨機存取 B) 花費的存儲空間較順序存儲少 C) 便于插入和刪除操作 D) 數(shù)據(jù)元素的物理順序與邏輯順序相同 長度為n的順序存儲線性表中，當在任何位置上插入一個元素概率都相等時，插入一個元素所需移動元素的平均個數(shù)為 【1】 。,.,線性表L=(a1,a2,a3,…ai，…an)，下列說法正確的是 A) 每個元素都有一個直接前件和直接后件 B) 線性表中至少要有一個元素 C) 表中諸元素的排列順序必須是由小到大或由大到小 D) 除第一個元素和最后一個元素外，其余每個元素都有一個且只有一個直接前件和直接后件 在單鏈表中，增加頭結(jié)點的目的是 A) 方便運算的實現(xiàn) B) 使單鏈表至少有一個結(jié)點 C) 標識表結(jié)點中首結(jié)點的位置 D) 說明單鏈表是線性表的鏈式存儲實現(xiàn),.,循環(huán)鏈表的主要優(yōu)點是 A) 不再需要頭指針了 B) 從表中任一結(jié)點出發(fā)都能訪問到整個鏈表 C) 在進行插入、刪除運算時，能更好保證鏈表不斷開 D) 已知某個結(jié)點的位置能容易的找到它的直接前件 線性表的順序存儲結(jié)構(gòu)和線性表的鏈式存儲結(jié)構(gòu)分別是 A) 順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) B) 隨機存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) C) 隨機存取的存儲結(jié)構(gòu)、隨機存取的存儲結(jié)構(gòu) D) 任意存取的存儲結(jié)構(gòu)、任意存取的存儲結(jié)構(gòu),.,下列對于線性鏈表的描述中正確的是_______。 A）存儲空間不一定是連續(xù)，且各元素的存儲順序是任意的 B）存儲空間不一定是連續(xù)，且前件元素一定存儲在后件元素的前面 C）存儲空間必須連續(xù)，且前件元素一定存儲在后件元素的前面 D）存儲空間必須連續(xù)，且各元素的存儲順序是任意的 下列敘述中正確的是_______。 A）一個邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲結(jié)構(gòu) B）數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，存儲結(jié)構(gòu)屬于非線性結(jié)構(gòu) C）一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)不影響數(shù)據(jù)處理的效率 D）一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)影響數(shù)據(jù)處理的效率,.,棧,是一種特殊的線性表。其特殊性在于限定插入和刪除數(shù)據(jù)元素的操作只能在線性表的表尾端進行。如下所示： 進行插入和刪除的表尾端是浮動端，通常被稱為棧頂， an 為棧頂元素， 并用一個“棧頂指針”指示；而表頭端是固定端，通常被稱為棧底， a1 為棧底元素，。我們經(jīng)常將棧用下圖的形式描述：,a1, a2, a3, ..., an 插入和刪除端,,.,.,結(jié)論：后進先出（Last In First Out），簡稱為LIFO線性表。 舉例1：家里吃飯的碗，通常在洗干凈后一個一個地落在一起存放，在使用時，若一個一個地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。 舉例2：在建筑工地上，使用的磚塊從底往上一層一層地碼放，在使用時，將從最上面一層一層地拿取。,.,棧的基本運算,棧的基本運算： （1）插入元素稱為入棧運算； （2）刪除元素稱為退棧運算； （3）讀棧頂元素是將棧頂元素賦給一個指定的變量，此時指針無變化,.,,棧頂指針和棧中元素之間的關(guān)系,A,B,C,D,E,top 指向棧頂元素,棧的順序存儲及運算,.,棧的鏈式存儲 若是棧中元素的數(shù)目變化范圍較大或不清楚棧元素的數(shù)目，就應(yīng)該考慮使用鏈式存儲結(jié)構(gòu)。人們將用鏈式存儲結(jié)構(gòu)表示的棧稱作“鏈?！薄ｆ湕ＭǔＳ靡粋€無頭結(jié)點的單鏈表表示。如圖所示。 由于棧的插入刪除操作只能在一端進行，而對于單鏈表來說，在首端插入刪除結(jié)點要比尾端相對地容易一些，所以，我們將單鏈表的首端作為棧頂端，即將單鏈表的頭指針作為棧頂指針。,.,隊列及其基本運算,隊列(Queue)也是一種運算受限的線性表。它只允許在表的一端進行插入，而在另一端進行刪除。允許刪除的一端稱為隊頭(front)，允許插入的一端稱為隊尾(rear)。 例如：排隊購物。操作系統(tǒng)中的作業(yè)排隊。先進入隊列的成員總是先離開隊列。因此隊列亦稱作先進先出(First In First Out)的線性表，簡稱FIFO表。,.,下圖是隊列的示意圖： 　　　　　 　　　　　　 a1　a2　…　an 　　 　　　　　 插入端和刪除端都是浮動的。通常我們將插入端稱為隊尾，用一個“隊尾指針”指示；而刪除端被稱為隊頭，用一個“隊頭指針”指示。 結(jié)論：先進先出（First In First Out），簡稱為FIFO線性表。,出隊,入隊,.,隊列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。Rear指針指向隊尾，front指針指向隊頭。 隊列是“先進行出”（FIFO）或“后進后出”（LILO）的線性表。 隊列運算包括（1）入隊運算：從隊尾插入一個元素；（2）退隊運算：從隊頭刪除一個元素。,隊列基本運算,.,隊列的順序存儲結(jié)構(gòu) 實現(xiàn)：用一維數(shù)組實現(xiàn)sq[M],J1,J2,J3,設(shè)兩個指針front,rear,約定： rear指示隊尾元素； front指示隊頭元素前一位置 初值front=rear=-1,空隊列條件：front==rear 入隊列：sq[++rear]=x; 出隊列：x=sq[++front];,,,,.,存在問題 設(shè)數(shù)組維數(shù)為M，則： 當front=-1,rear=M-1時，再有元素入隊發(fā)生溢出——真溢出 當front?-1,rear=M-1時，再有元素入隊發(fā)生溢出——假溢出 解決方案：循環(huán)隊列（掌握計算隊列元素個數(shù)的方法） 基本思想：把隊列設(shè)想成環(huán)形，讓sq[0]接在sq[M-1]之后，若rear+1==M,則令rear=0;,實現(xiàn)：利用“?！边\算 入隊： rear=(rear+1)%M; sq[rear]=x; 出隊： front=(front+1)%M; x=sq[front]; 隊滿、隊空判定條件 解決方案： 1.另外設(shè)一個標志以區(qū)別隊空、隊滿 2.少用一個元素空間： 隊空：front==rear 隊滿：(rear+1)%M==front,.,隊列的鏈式存儲結(jié)構(gòu) 隊列的鏈式存儲結(jié)構(gòu)簡稱為鏈隊列，它是限制僅在表頭刪除和表尾插入的單鏈表。顯然僅有單鏈表的頭指針不便于在表尾做插入操作，為此再增加一個尾指針，指向鏈表的最后一個結(jié)點。于是，一個鏈隊列由一個頭指針和一個尾指針唯一確定。添加頭節(jié)點。和順序隊列類似，我們也是將這兩個指針封裝在一起，,.,例題講解,.,按照“后進先出”原則組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是______。 A）隊列 　　B）棧 　　C）雙向鏈表 D）二叉樹 下列敘述中正確的是______。 A）循環(huán)隊列有隊頭和隊尾兩個指針，因此，循環(huán)隊列是非線性結(jié)構(gòu) B）在循環(huán)隊列中，只需要隊頭指針就能反映隊列中元素的動態(tài)變化情況 C）在循環(huán)隊列中，只需要隊尾指針就能反映隊列中元素的動態(tài)變化情況 D）循環(huán)隊列中元素的個數(shù)是由隊頭指針和隊尾指針共同決定,.,設(shè)某循環(huán)隊列的容量為50，頭指針Front=5 (指向隊頭元素的前一位置)，尾指針rear=29（指向隊尾元素），則該循環(huán)隊列中共有 個元素。 設(shè)某循環(huán)隊列的容量為50，如果頭指針Front＝45（指向隊頭元素的前一位置），尾指針rear=10 (指向隊尾元素) 則該循環(huán)隊列中共有 個元素。 當循環(huán)隊列非空且隊尾指針等于隊頭指針時，說明循環(huán)隊列已滿，不能進行入隊運算。這種情況稱為 。,.,1．6 樹與二叉樹,樹是一種簡單的非線性結(jié)構(gòu)，所有元素之間具有明顯的層次特性。 在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為父結(jié)點，沒有前件的結(jié)點只有一個，稱為樹的根結(jié)點，簡稱樹的根。每一個結(jié)點可以有多個后件，稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)點稱為葉子結(jié)點。 在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件的個數(shù)稱為該結(jié)點的度，所有結(jié)點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。,.,(C)是有13個結(jié)點的樹，其中A是根，其余結(jié)點分成3個子集： T1 、T2 、T3 。都是根A的子樹，且本身也是一棵樹。例如： T1 其根為B，兩棵子樹為 T11 ={ F } T12 = { E, K, L }， T12 又是一棵子樹，樹根為F，{K} 和 {L}是E的兩個互不相交的子集。,4,.,A,?,,(a),(b),(c),.,1.6.2二叉樹及其基本性質(zhì),二叉樹的特點： （1）非空二叉樹只有一個根結(jié)點； （2）每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。,.,G H,D E F,B C,A,,,,,,,,,.,二叉樹的基本性質(zhì)：,（1）在二叉樹的第k層上，最多有2k-1(k≥1)個結(jié)點； （2）深度為m的二叉樹最多有2m-1個結(jié)點； （3）度為0的結(jié)點（即葉子結(jié)點）總是比度為2的結(jié)點多一個； （4）具有n個結(jié)點的二叉樹，其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數(shù)部分； （5）具有n個結(jié)點的完全二叉樹的深度為[log2n]+1；,.,滿二叉樹是指除最后一層外，每一層上的所有結(jié)點有兩個子結(jié)點，則k層上有2k-1個結(jié)點深度為m的滿二叉樹有2m-1個結(jié)點。 完全二叉樹是指除最后一層外，每一層上的結(jié)點數(shù)均達到最大值，在最后一層上只缺少右邊的若干結(jié)點。,滿二叉樹和完全二叉樹,.,.,一棵滿二叉樹一定是一棵完全二叉樹，而一棵完全二叉樹不一定是滿二叉樹。,.,1.6.3二叉樹的存儲結(jié)構(gòu) 二叉樹也可以采用兩種存儲方式：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。 1. 順序存儲結(jié)構(gòu) 這種存儲結(jié)構(gòu)適用于完全二叉樹。其存儲形式為：用一組連續(xù)的存儲單元依次自上而下、自左至右存儲完全二叉樹的結(jié)點元素，即 ：按照完全二叉樹的每個結(jié)點編號的順序存放結(jié)點內(nèi)容。下面是一棵二叉樹及其相應(yīng)的存儲結(jié)構(gòu)。,.,,,a,b,c,d,e,f,g,h,i,j,k,l,,,,,,,,,,,完全二叉樹,1 2 3 4 5 6 7 8 9 10 11 12,.,2 鏈式存儲結(jié)構(gòu) 在順序存儲結(jié)構(gòu)中，利用編號表示元素的位置及元素之間孩子或雙親的關(guān)系，因此對于非完全二叉樹，需要將空缺的位置用特定的符號填補，若空缺結(jié)點較多，勢必造成空間利用率的下降。在這種情況下，就應(yīng)該考慮使用鏈式存儲結(jié)構(gòu)。 常見的二叉樹結(jié)點結(jié)構(gòu)如下所示：,.,1.6.4二叉樹的遍歷 所謂遍歷二叉樹就是按某種順序訪問二叉樹中的每個結(jié)點一次且僅一次的過程。這里的訪問可以是輸出、比較、更新、查看元素內(nèi)容等等各種操作。 二叉樹的遍歷方式分為：前序遍歷、中序遍歷、后序遍歷,.,（1）先序遍歷 若二叉樹為空，則結(jié)束遍歷操作；否則 訪問根結(jié)點； 先序遍歷左子樹； 先序遍歷右子樹。 （2）中序遍歷 若二叉樹為空，則結(jié)束遍歷操作；否則 中序遍歷左子樹； 訪問根結(jié)點； 中序遍歷右子樹。,.,（3）后序遍歷 若二叉樹為空，則結(jié)束遍歷操作；否則 后序遍歷左子樹； 后序遍歷右子樹； 訪問根結(jié)點。 下面是一棵二叉樹及其經(jīng)過三種遍歷得到的相應(yīng)序列。,.,G H,B C,A,,,,,,先序序列： ABDGCEFH 中序序列： DGBAECHF 后序序列： GDBEHFCA,.,1．7 查找技術(shù),1.7.1順序查找 順序查找是一種最簡單的查找方法。 順序查找的使用情況： （1）線性表為無序表； （2）表采用鏈式存儲結(jié)構(gòu)。,.,1.7.2二分法查找 二分法查找只適用于順序存儲的有序表。 對于長度為n的有序線性表，最壞情況只需比較log2n次。,.,1.8排序技術(shù),排序是指將一個無序序列整理成按值非遞減順序排列的有序序列。 1.8.1交換排序 所謂交換類排序法是指借助數(shù)據(jù)元素之間的互相交換進行的排序的一種方法。,.,1.冒泡排序 冒泡排序是一種最簡單的交換類排序方法,它是通過相鄰數(shù)據(jù)元素的交換逐步將線性表變成有序。 冒泡排序法，需要比較的次數(shù)為n(n-1)/2； ２.快速排序 最壞情況下，需要比較的次數(shù)為n(n-1)/2,.,１.8.2插入排序 １．簡單插入排序法 最壞情況需要n(n-1)/2次比較； ２.希爾排序法 最壞情況需要O(n1.5)次比較。,.,１.８.３ 選擇類排序法,（1）簡單選擇排序法最壞情況需要n(n-1)/2次比較； （2）堆排序法 最壞情況需要O(nlog2n)次比較。,.,在深度為7的滿二叉樹中，葉子結(jié)點的個數(shù)為______。 A）32 　　B）31 　　C）64 　　D）63 對下列二叉樹： 進行中序遍歷的結(jié)果是______。 A）ACBDFEG 　　 B）ACBDFGE 　　 C）ABDCGEF 　　 D）FCADBEG,.,某二叉樹中有n個度為2的結(jié)點,則該二叉樹中的葉子結(jié)點數(shù)為_______。 A）n+1 B）n-1 C）2n 　D）n/2 一棵二叉樹中共有70個葉子結(jié)點與80個度為1的結(jié)點，則該二叉樹中的總結(jié)點數(shù)為_______。 A）219 B）221 C）229 D）231 一棵二叉樹的中序遍歷結(jié)果為DBEAFC，前序遍歷結(jié)果為ABDECF，則后序遍歷結(jié)果為 。 設(shè)一棵完全二叉樹共有839個結(jié)點，則該二叉樹中有 個葉子結(jié)點。,.,對于長度為n的線性表進行順序查找，在最壞情況下所需要的比較次數(shù)為_______。 A）log2n B） n/2 C） n D） n+1 下列敘述中正確的是______。 A）對長度為n的有序鏈表進行查找，最壞的情況需要比較次數(shù)為n。 B）對長度為n的有序鏈序表進行對分查找，最壞的情況需要比較次數(shù)為（n/2）。 C）對長度為n的有序鏈序表進行對分查找，最壞的情況需要比較次數(shù)為（log2n）。 D）對長度為n的有序鏈序表進行對分查找，最壞的情況需要比較次數(shù)為（nlog2n）。 對長度為10的線性表進行冒泡排序，最壞情況下需要比較的次數(shù)為 。,