軍隊文職計算機類計算機類數據結構與算法知識點總結

1、數據結構知識點總結內容概要：基本概念線性表棧與隊列樹與二叉樹圖查找算法排序算法一、 基本概念1、數據元素是數據的基本單位。2、數據項是數據不可分割的最小單位。3、數據結構的邏輯結構（抽象的，與實現無關）物理結構（存儲結構）順序映像（順序存儲結構）位置“相鄰”非順序映像（鏈式存儲結構）指針表示關系4、算法特性：算法具有正確性、有窮性，確定性，（可行性）、輸入，輸出正確性：能按設計要求解決具體問題，并得到正確的結果。有窮性：任何一條指令都只能執(zhí)行有限次，即算法必須在執(zhí)行有限步后結束。確定性：算法中每條指令的含義必須明確，不允許由二義性可行性：算法中待執(zhí)行的操作都十分基本，算法應該在有限時間內執(zhí)行完

2、畢。輸入：一個算法的輸入可以包含零個或多個數據。輸出：算法有一個或多個輸出5、算法設計的要求：（1）正確性：算法應能滿足設定的功能和要求。（2）可讀性：思路清晰、層次分明、易讀易懂。（3）健壯性：輸入非法數據時應能作適當的反應和處理。（4）高效性（時間復雜度）：解決問題時間越短，算法的效率就越高。（5）低存儲量（空間復雜度）：完成同一功能，占用存儲空間應盡可能少。二、 線性表1、線性表 List：最常用且最簡單的數據結構。含有大量記錄的線性表稱為文件。2、線性表是n個數據元素的有限序列。線性結構的特點：“第一個”“最后一個”前驅后繼。3、順序表線性表的順序存儲結構特點a) 邏輯上相鄰的元素在物

3、理位置上相鄰。b) 隨機訪問。01MAXSIZE-1.L.elemL.elemL.elemL.length=0L.length=MAXSIZE0<L.length<MAXSIZE1) typedefstructDataType elemMAXSIZE;int length; SqList;2) 表長為n時，線性表進行插入和刪除操作的時間復雜度為O（n）插入一個元素時大約移動表中的一半元素。刪除一個元素時大約移動表中的（n-1）24、線性表的鏈式存儲結構1) 類型定義簡而言之，“數據 + 指針”。datanexttypedefstruct LNode DataType data;st

4、ruct LNode *next; LNode, *LinkList;2) 不帶頭結點的空表判定為 L= =null帶頭結點的空表判定為 L->next= =null循環(huán)單鏈表為空的判定條件為 L.next= =L線性鏈表的最后一個結點的指針為NULL頭結點的數據域為空，指針域指向第一個元素的指針。5、順序表和單鏈表的比較順序表單鏈表以地址相鄰表示關系用指針表示關系隨機訪問，取元素O(1)順序訪問，取元素O(n)插入、刪除需要移動元素O(n)插入、刪除不用移動元素O(n)(用于查找位置)6、順序存儲：優(yōu)點：存儲密度大，可隨機存儲缺點：大小固定；不利于增減節(jié)點;存儲空間不能充分利用；容量難

5、擴充鏈式存儲：優(yōu)點：易于插入刪除；可動態(tài)申請空間；表容量僅受內存空間限制缺點：增加了存儲空間的開銷；不可以隨機存儲元素三、 棧與隊列1、棧棧：限定僅在表尾進行插入或刪除操作的線性表。棧頂：表尾端棧底：表頭棧是先進后出的線性表。插入棧頂元素稱為入棧，刪除棧頂元素稱為出棧。2、棧分為鏈棧和順序棧·鏈棧a1/anS.an-1用不帶頭結點的單鏈表實現。·順序棧類似于順序表，插入和刪除操作固定于表尾。3、隊列先進先出的線性表。隊尾入隊對頭出隊允許插入的一端叫做隊尾允許刪除的一端叫做對頭4、鏈隊列·5、循環(huán)隊列typedefstruct DataType elemMAXSIZ

6、E;int front, rear; / 隊頭、隊尾位置 SqQueue;·循環(huán)隊列判斷隊空的條件為 front=rear循環(huán)隊列判斷隊滿的條件為（rear+1）%m=front在一個循環(huán)隊列中刪除元素時，首先需要后移隊首指針。6、棧與隊列比較：都是線形結構，棧的操作LIFO（后進先出），隊列操作FIFO（先進先出）。四、 樹和二叉樹1. 樹的定義樹（Tree）：是 n（n0）個有限數據元素的集合。在任意一棵非空樹T中：（1）有且僅有一個特定的稱為樹根（Root）的結點，根結點無前趨結點；（2）當n>1時，除根結點之外的其余結點被分成m(m>0)個互不相交的集合T1，T2

7、，Tm，其中每一個集合Ti（1 i m）本身又是一棵樹，并且稱為根的子樹。2. 基本術語：結點的度數：結點的非空子樹（即后綴）個數叫作結點的度數樹葉、分支結點：左（右）子樹均為空二叉樹的結點稱作樹葉否則稱作分支結點。結點的層數：規(guī)定根的層數是0，其余結點的層數等于其父結點的層數加1孩子和雙親：樹的深度：樹的度數：樹中度數最大的結點度數叫作樹的度數樹林：是由零個或多個不相交的樹所組成的集合。3. 二叉樹性質：1) 二叉樹的第i層上至多有2i-1個結點。2) 深度為k的二叉樹至多有2k-1個結點。滿二叉樹：深度為k，有2k-1個結點。完全二叉樹：給滿二叉樹的結點編號，從上至下，從左至右，n個結點的

8、完全二叉樹中結點在對應滿二叉樹中的編號正好是從1到n。3) 葉子結點n0，度為2的結點為n2，則n0 = n2+1。考慮結點個數：n = n0 + n1 + n2考慮分支個數：n-1 = 2n2 + n1可得n0 = n2+14) n個結點的完全二叉樹深度為。5) n個結點的完全二叉樹，結點按層次編號有： i的雙親是，如果i = 1時為根（無雙親）； i的左孩子是2i，如果2i>n，則無左孩子； i的右孩子是2i + 1，如果2i + 1>n則無右孩子。4. 二叉樹的存儲結構·順序存儲結構用數組、編號i的結點存放在i-1處。適合于存儲完全二叉樹。·鏈式存儲結構二

9、叉鏈表：typedefstruct BTNode DataType data;struct BTNode *lchild, *rchild; BTNode, *BinTree;三叉鏈表：typedefstruct BTNode DataType data;struct BTNode *lchild, *rchild, *parent; BTNode, *BinTree;dataparentlchildrchilddatarchildlchild在鏈式存儲結構中，含有n個結點的二叉鏈表有n+1個空鏈域。5. 遍歷二叉樹（先序DLR、中序LDR、后序LRD）方法與C語言描述由二叉樹的遞歸定義可知，

10、一棵二叉樹由根結點（D）、根結點的左子樹（L）和根結點的右子樹（R）三部分組成。因此，只要依次遍歷這三部分，就可以遍歷整個二叉樹。一般有三種方法：先序(前序)遍歷DLR（根左右）、中序遍歷LDR（左根右）、后序遍歷LRD（左右根）。6. 線索二叉樹n個結點的二叉鏈表中有n+1個空指針，可以利用其指向前驅或后繼結點，叫線索，同時需附加一個標志，區(qū)分是子樹還是線索。lchildltagdatartagrchild0/10/1lchild有左子樹，則指向左子樹，標志ltag = 0；沒有左子樹，可作為前驅線索，標志ltag = 1。rchild有右子樹，則指向右子樹，標志rtag = 0；沒有右子樹

11、，可作為后繼線索，標志rtag = 1。7. 樹和森林樹的存儲結構雙親表示法，孩子表示法，孩子兄弟表示法。特點：雙親表示法容易求得雙親，但不容易求得孩子；孩子表示法容易求得孩子，但求雙親麻煩；兩者可以結合起來使用。孩子兄弟表示法，容易求得孩子和兄弟，求雙親麻煩，也可以增加指向雙親的指針來解決。樹與二叉樹的轉換表Error! No text of specified style in document.1樹和二叉樹的對應關系樹對應的二叉樹根根第一個孩子左孩子下一個兄弟右孩子樹的遍歷樹的結構：根，根的子樹。先根遍歷：。例：ABCDEFGHIJK。后根遍歷：。例：CEDFBHGJKIA。遍歷森林森林

12、的結構：第一棵樹的根，第一棵樹的根的子樹森林，其余樹(除第一棵外)組成的森林。先序遍歷：。例：ABCDEFGHIJ。中序遍歷：。例：BDCEAGFIJH。注：先序遍歷森林，相當于依次先根遍歷每一棵樹；中根遍歷森林相當于后根遍歷每一棵樹。ABICDFHGJKEAHBCEGFIJD樹的結構劃分森林的結構劃分遍歷樹、森林與遍歷二叉樹的關系遍歷樹、森林和二叉樹的關系樹森林二叉樹先根遍歷先序遍歷先序遍歷后根遍歷中序遍歷中序遍歷8. 哈夫曼樹：葉子結點帶有權值的最小帶權路徑長度的最優(yōu)二叉樹構造赫夫曼樹每次取兩個最小的樹組成二叉樹赫夫曼編碼(前綴碼)向左分支為0，向右分支為1，從根到葉子的路徑構成葉子的前綴

13、編碼。五、 圖1完全圖：有12 n(n-1)條變得無向圖有向完全圖：具有n（n-1）條弧的有向圖。權：與圖的邊或弧相關的數。頂點v的度：和v相關聯的邊的數目。入度：以頂點v為頭的弧的數目出度：以頂點v為尾的弧的數目回路或環(huán)：第一個頂點和最后一個頂點相同的路徑。簡單路徑：序列中頂點不重復出現的路徑。2.圖的存儲結構·鄰接矩陣：0110000110000101000010010ABCDE·鄰接表：typedefstruct ArcNode / 弧結點int adjvex;/ 鄰接點struct ArcNode *nextarc;/ 下一個鄰接點 ArcNode;typedefs

14、truct VexNode / 頂點結點 VertexType data;/ 頂點信息 ArcNode *firstarc;/ 第一個鄰接點 VexNode;constint MAX_VERTEX = 最大頂點個數;typedefstruct Graph / 圖 VexNode vexsMAX_VERTEX;/ 頂點向量int vexnum, arcnum;/ 頂點和弧的個數 Graph;邊(弧)多則需要存儲空間多。ABCDE12/0123423/3/0/03/·十字鏈表：十字鏈表是有向圖的另一種鏈式存儲結構?？梢钥闯墒菍⒂邢驁D的鄰接表和逆鄰接表結合起來的一種鏈表。在十字鏈表中，對應

15、于有向圖中每一條弧有一個結點，對應于每個頂點有一個結點。·鄰接多重表3. 圖的遍歷1) 深度優(yōu)先（DFS）搜索訪問方式：從圖中某頂點v出發(fā)：a）訪問頂點v；b）從v的未被訪問的鄰接點出發(fā)，繼續(xù)對圖進行深度優(yōu)先遍歷，若從某點出發(fā)所有鄰接點都已訪問過，退回前一個點繼續(xù)上述過程，若退回開始點，結束。2) 廣度（寬度，BFS）優(yōu)先搜索a）訪問頂點v ；b）訪問同v相鄰的所有未被訪問的鄰接點w1,w2, wk；c）依次從這些鄰接點出發(fā)，訪問它們的所有未被訪問的鄰接點; 依此類推，直到圖中所有訪問過的頂點的鄰接點都被訪問；4. 生成樹和最小生成樹每次遍歷一個連通圖將圖的邊分成遍歷所經過的邊和沒有

16、經過的邊兩部分，將遍歷經過的邊同圖的頂點構成一個子圖，該子圖稱為生成樹。因此有DFS生成樹和BFS生成樹。1) 最小生成樹·Kruskal算法一句話，“不構成環(huán)的情況下，每次選取最小邊”。ABCDE25331763ABCDE25331763ABCDE25331763(a)(b)(c)ABCDE25331763ABCDE25331763ABCDE25331763(d)(e)(f)·普里姆算法記V是連通網的頂點集，U是求得生成樹的頂點集，TE是求得生成樹的邊集。普里姆算法：(a) 開始時，U=v0，TE=；(b) 計算U到其余頂點V-U的最小代價，將該頂點納入U，邊納入TE；(

17、c) 重復(b)直到U=V。普里姆算法和克魯斯卡爾算法的比較算法普里姆算法克魯斯卡爾算法時間復雜度O(n2)O(e loge)特點只與頂點個數n有關與邊的數目e無關適用于稠密圖只與邊的數目e有關與頂點個數n無關適用于稀疏圖5.AOV-網用頂點表示活動，邊表示活動的優(yōu)先關系的有向圖稱為AOV網。拓撲排序：對AOV網絡中頂點構造拓撲有序序列的過程。拓撲排序的方法(1)在有向圖中選一個沒有前驅的頂點且輸出之(2)從圖中刪除該頂點和所有以它為尾的弧6. 關鍵路徑AOE網，關鍵路徑AOE網(Activity On Edge)帶權的有向無環(huán)圖，其中頂點表示事件，弧表示活動，權表示活動持續(xù)時間。在工程上常用

18、來表示工程進度計劃。關鍵路徑：從源點到匯點的最長的一條路徑，或者全部由關鍵活動構成的路徑。7. 最短路徑(1) 迪杰斯特拉算法求一個頂點到其他各頂點的最短路徑。算法：(a) 初始化：用起點v到該頂點w的直接邊(弧)初始化最短路徑，否則設為；(b) 從未求得最短路徑的終點中選擇路徑長度最小的終點u：即求得v到u的最短路徑；(c) 修改最短路徑：計算u的鄰接點的最短路徑，若(v,u)+(u,w)<(v,w)，則以(v,u,w)代替。(d) 重復(b)-(c)，直到求得v到其余所有頂點的最短路徑。特點：總是按照從小到大的順序求得最短路徑。(2) 弗洛伊德算法求每對頂點之間的最短路徑。依次計算A

19、(0)，A(1)，A(n)。A(0)為鄰接矩陣，計算A(k)時，A(k)(i,j)=minA(k-1)(i,j), A(k-1)(i,k)+A(k-1)(k,j)。技巧：計算A(k)的技巧。第k行、第k列、對角線的元素保持不變，對其余元素，考查A(i,j)與A(i,k)+A(k,j) （“行+列”），如果后者更小則替換A(i,j)，同時修改路徑。六、 查找1. 查找分為：靜態(tài)查找表、動態(tài)查找表、哈希查找表2. 靜態(tài)查找表：對查找表只作查找操作的查找表。動態(tài)查找表：查找過程中同時插入表中不含的元素，或者刪除查找表中已有的元素的操作的查找表。3. 順序查找：順序查找又稱線性查找，是最基本的查找方法

20、之一。順序查找既適用于順序表，也適用于鏈表。4. 二分法（折半）查找：是一種效率較高的查找方法，但前提是表中元素必須按關鍵字有序（按關鍵字遞增或遞減）排列。5. 索引順序表查找又稱分塊查找。分塊查找：塊內無序、塊間有序、如何分塊效率最高6. 動態(tài)查找表：二叉排序樹查找：二叉排序樹的生成二叉排序樹(二叉查找樹)：或者是一顆空樹?；蛘呷缦?若它的左子樹不空，則左子樹上所有的結點的值均小于他的根結點的值。2若右子樹不空，則右子樹所有結點的值均大于她得根結點的值。3 左右子樹也分別為二叉排序樹。7. 哈希表：哈希函數構造：直接定址法、除留余數法、平方取中法，隨機數法，數字分析法沖突解決方法：開放定址法

21、、拉鏈法、公共溢出區(qū)法七、 排序1.插入類排序：·直接插入排序每次將一個待排序的數據元素，插入到前面已經排好序的數列中的適當位置，使數列依然有序；直到待排序數據元素全部插入完為止。·折半插入排序·希爾排序基本思想：先將整個待排序記錄序列分成為若干個子序列分別進行直接插入排序，待整個序列中的記錄基本有序時在對全體序列進行一次直接插入排序，子序列的構成不是簡單的逐段分割，而是將像個某個增量的記錄組成一個子序列。2.交換類排序·起泡排序也稱冒泡法，每相鄰兩個記錄關鍵字比大小,大的記錄往下沉（也可以小的往上?。Ｃ恳槐榘炎詈笠粋€下沉的位置記下，下一遍只需檢查比較

22、到此為止；到所有記錄都不發(fā)生下沉時，整個過程結束（每交換一次，記錄減少一個反序數）。·快速排序在當前無序區(qū)R1.H中任取一個數據元素作為比較的"基準"(不妨記為X)，用此基準將當前無序區(qū)劃分為左右兩個較小的無序區(qū)：R1.I-1和RI+1.H，且左邊的無序子區(qū)中數據元素均小于等于基準元素，右邊的無序子區(qū)中數據元素均大于等于基準元素，而基準X則位于最終排序的位置上，即R1.I-1X.KeyRI+1.H(1IH)，當R1.I-1和RI+1.H均非空時，分別對它們進行上述的劃分過程，直至所有無序子區(qū)中的數據元素均已排序為止。3.選擇類排序·簡單選擇排序每一趟從待

23、排序的數據元素中選出最?。ɑ蜃畲螅┑囊粋€元素，順序放在已排好序的數列的最后，直到全部待排序的數據元素排完。·堆排序堆排序是一樹形選擇排序，在排序過程中，將R1.N看成是一顆完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系來選擇最小的元素。4.歸并類排序·二路歸并排序5.基數類排序·基數排序主要特點不需要進行關鍵字間的比較。多關鍵字排序：最高為優(yōu)先（MSD法）從主關鍵字開始排序，再從次高位排序，一次類推，最后將所有子序列依次連接在一起成為一個有序序列。最低位優(yōu)先（LSD法）從最次位關鍵字開始排序，在對高一位的進行排序，直到成為一個有序序列。

24、排序方法穩(wěn)定性平均時間最壞情況輔助存儲直接插入排序穩(wěn)定O（n*n）O（n*n）O（1）快速排序不穩(wěn)定O（nlbn）O（n*n）O（lbn）歸并排序穩(wěn)定O(nlbn)O（nlbn）O（n）簡單選擇排序穩(wěn)定O（n*n）O（n*n）O（1）堆排序不穩(wěn)定O（nlbn）O（nlbn）O(1)基數排序穩(wěn)定O（d（n+rd）O（d（n+rd）O（rd）l 選取排序方法需要考慮的因素：(1) 待排序的元素數目n；(2) 元素本身信息量的大??；(3) 關鍵字的結構及其分布情況；(4) 語言工具的條件，輔助空間的大小等。l 小結：(1) 若n較小(n <= 50)，則可以采用直接插入排序或直接選擇排序。由于

25、直接插入排序所需的記錄移動操作較直接選擇排序多，因而當記錄本身信息量較大時，用直接選擇排序較好。(2) 若文件的初始狀態(tài)已按關鍵字基本有序，則選用直接插入或冒泡排序為宜。(3) 若n較大，則應采用時間復雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序。快速排序是目前基于比較的內部排序法中被認為是最好的方法。(4) 在基于比較排序方法中，每次比較兩個關鍵字的大小之后，僅僅出現兩種可能的轉移，因此可以用一棵二叉樹來描述比較判定過程，由此可以證明：當文件的n個關鍵字隨機分布時，任何借助于"比較"的排序算法，至少需要O(nlog2n)的時間。算法分析知識點總結算法概述

26、1、算法的五個性質：有窮性、確定性、能行性、輸入、輸出。2、算法的復雜性取決于：（1）求解問題的規(guī)模（N）,（2）具體的輸入數據（I），（3）算法本身的設計（A），C=F(N,I,A)。3、算法的時間復雜度的上界記號O，n下界記號(記為f(N) = (g(N)。即算法的實際運行時間至少需要g(n)的某個常數倍時間)，同階記號：f(N)= (g(N)表示f(N)和g(N)同階 。 即算法的實際運行時間大約為g(n)的某個常數倍時間。低階記號o：f(N)=o(g(N)表示f(N)比g(N)低階。 多項式算法時間： O(1)<O(logn)<O(n)<O(nlogn)<O(n

27、2)<O(n3)約定logn表示以2為底的對數。指數時間算法時間： O(2n)<O(n!)<O(nn)4、常用算法的設計技術：分治法、動態(tài)規(guī)劃法、貪心法、回溯法和分支界限法。5、常用的幾種數據結構：線性表、樹、圖。6、算法:是指解決某一問題的運算序列遞歸與分治1、遞歸算法的思想：將對較大規(guī)模的對象的操作歸結為對較小規(guī)模的對象實施同樣的操作。遞歸的時間復雜性可歸結為遞歸方程：其中，a是子問題的個數，b是遞減的步長， 表示遞減方式，D(n)是合成子問題的開銷。遞歸元的遞減方式有兩種：1、減法，即n b，的形式。2、除法，即n / b，的形式。2、遞減方式為減法 設D(n)為常數，

28、則有T(n) = O(an)。(這里都是針對遞減方式為除法的哦)D(n)為常數c：這時，T(n) = O(np)。D(n)為線形函數cn：D(n)為冪函數nx：考慮下列遞歸方程：T(1) = 1T(n) = 4T(n/2) +n T(n) = 4T(n/2) +n2 T(n) = 4T(n/2) +n3解：方程中均為a = 4，b = 2，其齊次解為n2。對， a > b1 (D(n) = n) T(n) = O(n2)；對， a = b2 (D(n) = n2) T(n) = O(n2log n)；對， a < b3 (D(n) = n3) T(n) = O(n3)；證明一個算法

29、的正確性需要證明兩點：1、算法的部分正確性。2、算法的終止性。3、漢諾塔問題：void Hanoi(int n, int Fr, int To, int As) if (n > 0) Hanoi(n1, A, C, B); Move(A, B);Hanoi(n1, C, B, A) 4、二分查找代碼貪心算法（旅行商問題、單源最短路徑問題）以下兩種算法都是為了查找最小生成樹問題的算法：1、Prim算法的基本思想：在保證連通的前提下依次選出權重較小的n 1條邊。（在實現中體現為n個頂點的選擇）。G=(V, E)為無向連通帶權圖，令V=1, 2, , n。設置一個集合S ，初始化S = 1，T

30、 = 。貪心策略：如果VS中的頂點j與S中的某個點i連接且(i, j) 的權重最小，于是就選擇j(將j加入S)，并將(i, j) 加入T中 。重復執(zhí)行貪心策略，直至VS為空。=證明最小生成樹必然包含最小權值邊=若G的任何最小生成樹都不包含e1。設T為G的最小生成樹，e1ÏT。于是T+e1是一個有回路的圖且該回路中包含e1。該回路中必有條不是e的邊ei。令T=T+e1ei。T也是G的生成樹。又c(T) = c(T) + c(e1) c(ei)，c(e1) c(ei)，從而 c(T)c(T)，T是G的最小生成樹且含有邊e1。矛盾。故必定有圖G的最小生成樹包含了e1。=2、Kruskal算

31、法的基本思想：基本思想：在保證無回路的前提下依次選出權重較小的n 1條邊。如果(i, j)是E中尚未被選中的邊中權重最小的，并且(i, j)不會與已經選擇的邊構成回路，于是就選擇 (i, j)。具體做法:先把所有n個點畫出來。不畫邊。然后把權值最小的那條邊畫上去。然后再把當前權值最小的邊(不算畫了的邊)畫上去。如果構成回路則舍棄這條邊。然后一直直到畫了n-1條邊3、 Prim與Kruskal兩算法的復雜性：Prim算法為兩重循環(huán)，外層循環(huán)為n次，內層循環(huán)為O(n)，因此其復雜性為O(n2)。Kruskal算法中，設邊數為e，則邊排序的時間為O(eloge)，最多對e條邊各掃描一次，每次確定邊的

32、時間為O(loge)，所以整個時間復雜性為O(eloge)。當e = (n2)時，Kruskal算法要比Prim算法差；當e = (n2)時，Kruskal算法比Prim算法好得多。4、貪心算法的基本要素是：貪心選擇性質。5、最小生成樹問題、單源最短路徑問題、旅行商問題、01背包問題，貪心算法不能夠找到最優(yōu)解。6、活動安排問題、最優(yōu)裝載問題，貪心算法可以找到最優(yōu)解。7、Dijkstra 算法Procedure Dijkstra ( 1) S:=1; /初始化S(2) for i:= 2 to n do /初始化dis(3) disi =C1, i ; /初始時為源到頂點i一步的距離。不能一步到

33、達就是無窮(4) for i :=1 to n do (5) 從V-S中選取一個頂點u使得disu最?。?6) 將u加入到S中；/將新的最近者加入S(7) for "wV-S do /依據最近者u修訂disw(8) disw := min(disw , disu+Cu ,w) 8、活動安排問題:先把活動按結束時間早晚排序。然后選取最早結束的。然后選取第一個開始時間比上一個結束時間大的再用這個原則選取?？偟臅r間復雜度為O(nlogn)=代碼=typedef struct   int   number; /活動的編號 float start;

34、60; /活動開始的時間 float end;    /活動結束的時間 Bool selected; /標記活動是否被選擇Active; int greedySelector(Active activity, int n) QuitckSort(activity,n); /將活動按結束時間排序 activity1.selected=true;  j=1;count=1;  for(i=2;i<=n;i+) if(activityi.start>=activityj.end) activityi.selected=

35、true;      j=i; count+; else  activityi.selected=false;  return count;  9、為什么貪心算法不能求得旅行商問題的最優(yōu)解：最臨近法不保證求得旅行商問題的精確解，只能得到問題地近似解。一般地，貪心選擇只依賴于前面選擇步驟地最優(yōu)性，因此是局部最優(yōu)的，所以貪心法不能夠確保求出問題的最優(yōu)解。10、最優(yōu)裝載問題：基本思想：這個題目比較簡單，可以用貪心法求解。每次采用重量最輕者優(yōu)先裝入的貪心選擇策略11、貪心算法的特點是什么？怎么樣知道一個問題是否能

36、用貪心算法呢？貪心算法每次選擇目前最優(yōu)的解，即通過一系列局部最優(yōu)來獲得整體最優(yōu)。貪心算法只有在具有貪心選擇性質時才能保證獲得整體最優(yōu)。證明貪心選擇性質：第一個選擇是對的；在作出貪心選擇后原問題轉化為同樣的子問題；由歸納法知問題具有貪心選擇性質。若原問題是求帶權擬陣的最優(yōu)獨立子集問題，則必滿足貪心選擇性質。動態(tài)規(guī)劃1、最短路徑問題: 如果是從源點往后推: 階段1: C(s,1)=w(s,1)=4， C(s,2)=w(s,2)=2,   C(s,3)=w(s,3)=3階段2: C(s,4)=minw(1,4)+C(s,1), w(2,4)+C(s,2)=min14,8

37、= 8C(s,5)=minw(1,5)+C(s,1), w(2,5)+C(s,2), w(3,5)+C(s,3) =min13,9,6= 6C(s,6)=minw(2,6)+C(s,2), w(3,6)+C(s,3)=min12,11= 11階段3: C(s,7)=minw(4,7)+C(s,4), w(5,7)+C(s,5), w(6,7)+C(s,6) =min12,15,16= 12C(s,8)=minw(4,8)+C(s,4), w(5,8)+C(s,5), w(6,8)+C(s,6) =min16,12,15= 12階段4: C(s,t)=minw(7,t)+C(s,7), w(8,

38、t)+C(s,8)=min20,16= 162、最有子結構的性質：最優(yōu)解的子結構也是最優(yōu)的。3、動態(tài)規(guī)劃的基本要素：（1）最優(yōu)子結構：問題的最優(yōu)解是由其子問題的最優(yōu)解所構成的。（2）重疊子問題：子問題之間并非相互獨立的，而是彼此有重疊的。4、動態(tài)規(guī)劃算法的步驟：1.找出最優(yōu)解的性質，并刻畫其結構特性。2.遞歸地定義最優(yōu)解。3.以自底向上的方式計算出各子結構的最優(yōu)值，并流入表格中保存。4.根據計算最優(yōu)值時得到的信息，構造最優(yōu)解。5、在有n個頂點的凸多邊形的三角剖分中，恰有n-3條弦，n-2個三角形?；厮莘?、三種搜索方法：（1）廣度優(yōu)先搜索的優(yōu)點是一定能找到解；缺點是空間復雜性和時間復雜性都大。

39、（2）深度優(yōu)先搜索的優(yōu)點是空間復雜性和時間復雜性較??；缺點是不一定能找到解。（3）啟發(fā)式搜索是最好優(yōu)先的搜索，優(yōu)點是一般來說能較快地找到解，即其時間復雜性更?。蝗秉c是需要設計一個評價函數，并且評價函數的優(yōu)劣決定了啟發(fā)式搜索的優(yōu)劣。2、 回溯法是一種通用的算法，實為深度優(yōu)先的搜索方法?；厮莘梢赃f歸實現，也可以迭代實現?；厮莘ㄍǔＧ蠼馊悊栴}：(1)求排列：時間復雜性為O(f(n)n!)；(2)求子集：時間復雜性為O(f(n)2n)；(3)求路徑：時間復雜性為O(f(n)kn)。這里f(n)為處理一個結點的時間復雜性。3、分支限界法回溯法聯系與區(qū)別：支限界法類似于回溯法，也是一種在問題的解空間樹

40、T上搜索問題解的算法。但在一般情況下，分支限界法與回溯法的求解目標不同?；厮莘ǖ那蠼饽繕耸钦页鯰中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出使某一目標函數值達到極大或極小的解，即在某種意義下的最優(yōu)解。由于求解目標不同，導致分支限界法與回溯法在解空間樹T上的搜索方式也不相同?；厮莘ㄒ陨疃葍?yōu)先的方式搜索解空間樹T，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹T。分支限界法的搜索策略是：在擴展結點處，先生成其所有的兒子結點（分支），然后再從當前的活結點表中選擇下一個擴展對點。為了有效地選擇下一擴展結點，以加速搜索的進程，在每一

41、活結點處，計算一個函數值（限界），并根據這些已計算出的函數值，從當前活結點表中選擇一個最有利的結點作為擴展結點，使搜索朝著解空間樹上有最優(yōu)解的分支推進，以便盡快地找出一個最優(yōu)解。分支界限法1、分支界限法德兩個要點：（1）評價函數的構造。（2）搜索路徑的構造。2、所謂分支限界法就是通過評價函數及其上下界函數的計算，將狀態(tài)空間中不可能產生最佳解的子樹剪去，減少搜索的范圍，提高效率。因而更準確的稱呼應是“界限剪支法”字符串1、幾個名詞的定義：串的長度，子串，位置，串相等，模式匹配。簡單模式匹配算法在正文設置一個指針指向第一個然后跟模式串匹配。不行就指針加一直到匹配成功或者正文結束。時間復雜度為O(m

42、+n)最壞為O(mn)2、KMP算法：時間復雜度為O(m+n)。next(j)函數的計算(計算到第j個就是從1到j-1這個子串首位分別截取盡可能長的相同子串。從尾巴那里截取的子串不用倒過來。得到的最長相同子串長+1就是next(j)的值啦。Next(1)固定等于0。恒有next(2) = 1)，int KMP_StrMatch(SString S, SString P)n int i = 1, j = 1, m = 0;n while(i <= S0 && j <= P0)n if (j = 0 | Si = Pj)i+; j+;n else j = nextj;

43、/失配時從nextj重新比較n if(j > P0) m = i j + 1;n return(m); =Newnext函數的計算=void get_newnext()int k,j;newnext1=0; j=2;while(j<=P0) k=nextj;if(k=0|pk!=pj) newnextj=k;else newnextj=newnextk;j=j+1; 3、BM算法：Boyer-Moore串匹配算法(簡稱BM算法)。最壞時間復雜度O(mn)其思想是在匹配過程中，一旦發(fā)現在正文中出現模式中沒有的字符時就可以將模式、正文大幅度地“滑過”一段距離。同時考慮到多數不匹配的情形

44、是發(fā)生在最后的若干個字符，采用從左到右的方式掃描將浪費很多時間，因此改自右到左的方式掃描模式和正文=dist函數的計算= m cÏP, 或c= pm且c¹ pj(0<j<m) n dist(c) = m j 否則 (j=maxc= pj, 0<j<m)4、KR算法：指印函數的要求：（1）速度快。（2）沖突概率小。（3）相鄰兩個字符串的HASH值必須有相關性。5、KR算法的基本思想：首先計算模式串和正文串所有長度為m的子串的指印函數；然后匹配與模式串指印函數相等的正文串中的子串，找到匹配串。6、KMP算法，BM算法，KR算法的優(yōu)缺點：三者中KMP算法的

45、最壞情形下的時間復雜度最低，而平均情形則三者差不多。KMP算法最早提出，應用也最廣泛，而且它的優(yōu)勢在于無需對正文回溯，當正文不能一次性讀入內存時，這種優(yōu)勢是顯而易見的。BM算法的平均性能也很出色，但它需要對正文進行回溯，所以當正文不能一次性讀入內存時，可能會出現“抖動”，需要用雙緩沖區(qū)技術來處理這一問題。KR算法的優(yōu)勢在于可以推廣到二維模型，而且可以并行地處理，所以較多地運用于圖形圖像領域。NP完全問題1、NP類問題定義：由非確定性圖靈機再多項式時間內可以計算的判定問題2、NP困難問題與NPC問題是一類問題么？就旅行商問題和判定問題談談你的看法。 不一定：對于問題Q，若滿足QNP且Q是NP困難的，則稱Q是NP完全的。旅行商問題不屬于NP問題。