五數(shù)據(jù)結(jié)構(gòu)與算法

1、數(shù)據(jù)結(jié)構(gòu)與算法第一節(jié)數(shù)據(jù)結(jié)構(gòu)及算法概述一、數(shù)據(jù)結(jié)構(gòu)【要點】1.數(shù)據(jù)元素是數(shù)據(jù)的基本。2.數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。3.4 類基本的邏輯結(jié)構(gòu):集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和網(wǎng)狀結(jié)構(gòu)。4.4 種數(shù)據(jù)方式：順序、鏈式、索引和散列?！纠}單選題】（2009 年省招聘）下列說法不正確的是（）。A.數(shù)據(jù)元素是數(shù)據(jù)的基本B.數(shù)據(jù)項是數(shù)據(jù)中不可分割的最小標志單位C.數(shù)據(jù)可由若干個數(shù)據(jù)元素D.數(shù)據(jù)項可由若干個數(shù)據(jù)元素正確D數(shù)據(jù)元素是數(shù)據(jù)的基本，在計算機程序中通常被作為一個整體進行考慮和處理。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是不可分割的、含有獨立意義的最小數(shù)據(jù)。因此D 選項不正

2、確。二、算法算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每條指令表示一個或多個操作。算法的特性：有窮性、確定性、可行性、輸入和輸出?！疽c】評價算法優(yōu)劣標準：正確性、可讀性、健壯性、高效率與低量需求。第二節(jié)線性表線性表是n（n0）個數(shù)據(jù)元素 a1，a2，an 組成的有限序列，n=0 時稱為空表。非空的線性表，有以下特征:1.有且僅有一個開始結(jié)點 a1，沒有直接前趨，有且僅有一個直接后繼 a2。2.有且僅有一個終結(jié)結(jié)點 an，沒有直接后繼，有且僅有一個直接前趨 an-1。3.其余的結(jié)點 ai（2in-1）都有且僅有一個直接前趨 ai-1 和一個直接后繼ai+1。線性表的鏈式包括單

3、鏈表、循環(huán)鏈表和雙鏈表?！咀⒁狻颗c單鏈表的和刪除操作不同的是，在雙鏈表中和刪除須同時修改兩個方向上的指針。第三節(jié)棧和隊列一、棧棧是一種“特殊的”線性表，這種線性表中的和刪除運算限定在表的某一端進行。不含任何數(shù)據(jù)元素的棧稱為空棧。棧的基本運算：構(gòu)造一個空棧 InitStack（S）、判?？?StackEmpty（S）、判棧滿 StackFull（S）、進棧 Push（S，x）、退棧 Pop（S）、取棧頂元素 StackTop（S）?！疽c】棧的修改是按后進先出的原則進行。二、隊列隊列是只允許在一端進行，而在另一端進行刪除的運算受限的線性表。當隊列中沒有元素時稱為空隊列。棧和隊列一般有兩種結(jié)構(gòu)：順

4、序結(jié)構(gòu)和鏈式結(jié)構(gòu)?！疽c】隊列的修改是按照先進先出的原則進行的?！纠}單選題】（2007 年省招聘）以下（）不是棧的基本運算？A.刪除棧頂元素B.刪除棧底元素C.判斷棧是否為空D.將棧置為空棧正確B棧是一種特殊的線性表，這種線性表上的和刪除運算限定在表的某一端進行。允許進行和刪除的這一端稱為棧頂，另一端稱為棧底。處于棧頂位置的數(shù)據(jù)元素稱為棧頂元素。棧的修改是按后進先出的原則進行。棧的運算在棧頂進行。因此，刪除棧底元素不屬于棧的基本運算。第四節(jié)數(shù)組數(shù)組：把具有相同類型的若干變量按有序的形式組織起來的同類數(shù)據(jù)元素的集合。第五節(jié)樹一、樹（一）基本概念樹是n（n0）個結(jié)點的有窮集合，滿足以下條件：（1

5、）有且僅有一個稱為根的結(jié)點。（2）其余結(jié)點分為m（m0）個互不相交的非空集合T1,T2,Tm,這些集合中的每一個都是一棵樹，稱為根的。森林是m（m0）棵互不相交的樹的集合。樹中的一個結(jié)點擁有的數(shù)稱為該結(jié)點的度。一棵樹的度是指該樹中結(jié)點的最大度數(shù)。樹中某個結(jié)點的的根稱為該結(jié)點的孩子或兒子。樹中結(jié)點的最大層數(shù)稱為樹的高度或深度。（二）樹和森林的遍歷1.樹的遍歷先序遍歷：若樹不空，則先根結(jié)點，然后依次先序遍歷各棵。ABCDE后序遍歷：若樹不空，則先依次后序遍歷各棵，然后根結(jié)點。BDCEA層次遍歷：若樹不空，則自上而下自左至右樹中每個結(jié)點。ABCED2.森林的遍歷前序遍歷森林：若森林非空，則：森林中第

6、一棵樹的根結(jié)點。前序遍歷第一棵樹中根結(jié)點的各所的森林。前序遍歷除第一棵樹外其他樹的森林。右圖前序遍歷序列為 ABCDEFIGJH。后序遍歷森林：若森林非空，則:后序遍歷森林中第一棵樹的根結(jié)點的各所的森林。第一棵樹的根結(jié)點。后序遍歷除第一棵樹外其他樹的森林。右圖后序遍歷序列為 BDCAIFJGHE。二、二叉樹（一）基本概念二叉樹是n（n0）個結(jié)點的有限集，它可以是空集（n=0），或者由一個根結(jié)點及兩棵互不相交的、分別稱作這個根的樹和右的二叉樹組成。二叉樹的性質(zhì)二叉樹的第 i 層上至多含有 2i-1 個結(jié)點（i1）。深度為 k 的二叉樹上至多含有 2k-1 個結(jié)點（k1）。3.對任何一棵二叉樹，若

7、它含有 n0 個葉子結(jié)點、n2 個度為 2 的結(jié)點，則必存在關(guān)系式：n0=n2+1。深度為k（k1）且有 2k-1 個結(jié)點的二叉樹稱為滿二叉樹。如果在一棵深度為k（k1）的滿二叉樹上刪去第k 層上最右邊的連續(xù)j（0j2k-1）個結(jié)點，就得到一棵深度為k 的完全二叉樹。滿二叉樹也是完全二叉樹。（二）二叉樹的遍歷1.先根遍歷若需遍歷的二叉樹為空，執(zhí)行空操作；否則，依次執(zhí)行下列操作：（1）根結(jié)點。（2）先根遍歷樹。（3）先根遍歷右。右圖的遍歷序列為：ABDGCEF2.中根遍歷若需遍歷的二叉樹為空,執(zhí)行空操作；否則，依次執(zhí)行下列操作：（1）中根遍歷樹。（2）根結(jié)點。（3）中根遍歷右。右圖的遍歷序列為：

8、DGBAECF3.后根遍歷若需遍歷的二叉樹為空，執(zhí)行空操作；否則，依次執(zhí)行下列操作：（1）后根遍歷樹。（2）后根遍歷右。（3）根結(jié)點。右圖的遍歷序列為：GDBEFCA【要點】樹和二叉樹的概念和他們的各種遍歷方法。第六節(jié) 圖一、圖的基本概念在樹形結(jié)構(gòu)點間具有分支層次關(guān)系，每一層上的節(jié)點只能和上一層中的至多一個節(jié)點相關(guān)，但可能和下一層的多個節(jié)點相關(guān)。在圖狀結(jié)構(gòu)中，任意兩個節(jié)點之間都可能相關(guān)。有序偶對用尖括號括起來；無序偶對用圓括號括起來。（x,y）與（y,x）被認為是同一條邊，但與則是不同的兩條弧。圖的邊或弧附帶數(shù)值，這種數(shù)值叫權(quán)?！疽c】一個具有n 個頂點的無向完全圖的邊數(shù)為 n（n-1）/2。

9、一個具有 n 個頂點的有向完全圖的弧數(shù)為n（n-1）。二、圖的結(jié)構(gòu)圖的兩種結(jié)構(gòu)：鄰接矩陣表示法和鄰接表表示法。圖的遍歷包括深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種方法。第七節(jié) 查找一、查找的基本概念查找表是由同一類型的數(shù)據(jù)元素（或）的集合。分為兩類：靜態(tài)查找表和動態(tài)查找表。二、線性表的查找順序查找：從表的一端開始，順序掃描線性表，依次將掃描到的結(jié)點關(guān)鍵字和給定值K 相比較。若當前掃描到的結(jié)點關(guān)鍵字與K 相等，則查找成功；若掃描結(jié)束后，仍未找到關(guān)鍵字等于K 的結(jié)點，則查找失敗。二分查找：要求線性表是有序表，每次將查找區(qū)間中間位置上的數(shù)據(jù)元素的鍵值與給定值K 比較，若不等則縮小查找區(qū)間，并在新的區(qū)間內(nèi)重復(fù)上

10、述過程，直到查找成功或查找區(qū)間長度為 0（查找不成功）為止。【要點】二分查找法要求線性表是有序表，掌握其查找方法?！纠}單選題】（2010 年省招聘）在順序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找關(guān)鍵碼值 11 所需的關(guān)鍵碼比較次數(shù)為（）。A.2B.3C.4D.5正確D根據(jù)二分法查找方法，各數(shù)值比較次數(shù)如下（用圓圈里的數(shù)來表示：3，6，8，10，12，15，16，18，21，25，30），對于 11 來說，是查找不成功，所以應(yīng)該比較 5 次。第八節(jié) 排序一、排序概述排序，就是使文件中的按關(guān)鍵字遞增（或遞減）次序排列起來。按是否外存，可將排序方法分為排序和

11、外部排序。對于排序，根據(jù)設(shè)置有序序列的方式的不同，又可以劃分為排序、交換排序、選擇排序、歸并排序和其他排序方法。二、常用排序方法簡介（一）排序每步將一個待排序的按其關(guān)鍵字的大小插到前面已經(jīng)排序的序列中的適當位置，直到全部完畢為止。1.直接排序依次將每個到一個有序序列中去。2.排序先取一個小于n 的整數(shù)d1 作為第一個增量，把文件的全部分成 d1 個組。所有距離為 d1 的倍數(shù)的放在同一個組中。先在各組內(nèi)進行直接排序；然后，取第二個增量 d2d1 重復(fù)上述的分組和排序，直至所取的增量 dt=1（dtdt-1d2d1），即所有放在同一組中進行直接排序為止。（二）交換排序兩兩比較待排序的關(guān)鍵字，發(fā)現(xiàn)

12、兩個的次序相反時即進行交換，直到?jīng)]有反序的為止。1.冒泡排序?qū)τ?1n 個，先將第 n 個和第 n-1 個的鍵值進行比較，如 rn.keyrn-1.key,則將兩個交換。然后比較第 n-1 個和第 n-2 個的關(guān)鍵字。依此類推，直到第 2 個和第 1 個進行比較交換，這稱為一趟冒泡。這一趟最明顯的效果是：將鍵值最小的傳到了第 1 位。然后對 2n 個進行同樣操作，則具有次小鍵值的被安置在第 2 位上。重復(fù)以上過程，每次的移動都向最終排序的目標前進，直至沒有需要交換為止。2.快速排序在待排序的n 個中任取一個（例如就取第 1 個）,以該的鍵值為標準，將所有分為兩組（一般都是無序的），使得第 1

13、組中各的鍵值均小于或等于該鍵值，第 2 組中各的鍵值均大于該鍵值。然后把該排在這兩組的中間（這也是該最終的位置）。此稱為一趟快速排序（或一次劃分），對所分成的兩組再分別重復(fù)上述方法，直到所有都排在適當位置為止?！疽c】冒泡排序和快速排序方法?！纠}單選題】（2010 年省招聘）用某種排序方法對序列（25，84，21，47，15，27，68，35，20）進行排序，序列的變化情況如下：原始序列：第一趟排序結(jié)果：第二趟排序結(jié)果：第三趟排序結(jié)果：則采用的排序方法是（）。A.直接選擇排序B.冒泡排序C.快速排序D.二路歸并排序正確C直接選擇排序第一趟就應(yīng)該選出一個最小的在第一個位置；冒泡排序法是兩兩比較，25 與 84 比較，25 要小，位置不變；快速排序法使比基準數(shù)（第一趟是25）小的數(shù)在基準數(shù)左邊，比基準數(shù)大的數(shù)在基準數(shù)右邊；二路歸并排序是分組比較，第一趟應(yīng)該是“2584”、“2147”、“1527”、“6835”、“20”這幾組進行排序。（三）選擇排序每一趟從待排序的中選出關(guān)鍵字最小的，順序放在已排好序的子文件的最后，直到全部排序完畢。常用的選擇排序方法有直接選擇排序和堆排序。1.直接選擇排序先在所有的中選出鍵值最小的，把它與第 1 個交換；然后在其余的中再選出鍵值最小的與第 2 個交換；依此類推，直至所有排序完成。2.堆排序?qū)σ唤M待排序的鍵值，先將它