演算法知識點匯總

㈠ 人教版高二數學必修三第一章知識點：演算法與程序框圖

1.演算法的概念
(1)演算法的定義：廣義的演算法是指完成某項工作的方法和步驟，那麼我們可以說洗衣機的使用說明書是操作洗衣機的演算法，菜譜是做菜的演算法等等。
在數學中，現代意義的演算法是指可以用計算機來解決的某一類問題的程序和步驟，這些程序或步驟必須是明確和有效的，而且能夠在有限步之內完成。
(2)演算法的特徵：①確定性：演算法的每一步都應當做到准確無誤、「不重不漏」。「不重」是指不是可有可無的、甚至無用的步塵顫驟，「不漏」 是指缺少哪一步都無法完成任務。②邏輯性：演算法從開始的「第一步」直到「最後一步」之間做到環環相扣。分工明確，「前一步」是「後一步」的前提， 「後一步」是「前一步」的繼續。③有窮性：演算法要有明確的開始和結束，當到達終止步驟時所要解決的問題必須有明確的結果，也就是說必須在有限步內完成任務，不能無限制的持續進行。
(3)演算法的描述：自然語言、程序框圖、程序語言。
2.高中二年級數學必修三演算法與程序框圖程序框圖
(1)程序框圖的概念：程序框圖又稱流程圖，是一種用規定的圖形、指向線及文字說明來准確、直觀地表示演算法的圖形;
(2)構成程序框的圖形符號及其作用
(3)程序框圖的構成
一個程序框圖包括以下幾部分：實困兄伏現不同演算法功能的相對應的程序框;帶箭頭的流程線;程序框內必要的說明文字。
3.高中二年級數學必修三演算法與程序框圖幾種重要的結構
(1)順序結構
順序結構是最簡單的演算法結構，語句與語句之間，框與框之間是按從上到下的順序進行的。它是由若干個依次執行的步驟組成的，它是任何一個演算法都離不開的一種基本演算法結構。
見示意圖和實例：
順序結構在程序框圖中的體現就是用流程線將程序框自上而下地連接起來，按順序執行演算法步驟。如在示意圖中，A框和B框是依次執行的，只有在執行汪攜完A框指定的操作後，才能接著執行B框所指定的操作。
(2)條件結構
如下面圖示中虛線框內是一個條件結構，此結構中含有一個判斷框，演算法執行到此判斷給定的條件P是否成立，選擇不同的執行框(A框、B框)。無論P條件是否成立，只能執行A框或B框之一，不可能既執行A框又執行B框，也不可能A框、B框都不執行。A框或B框中可以有一個是空的，即不執行任何操作。
見示意圖
(3)循環結構
在一些演算法中要求重復執行同一操作的結構稱為循環結構。即從演算法某處開始，按照一定條件重復執行某一處理過程。重復執行的處理步驟稱為循環體。
循環結構有兩種形式：當型循環結構和直到型循環結構。
①當型循環結構，如左下圖所示，它的功能是當給定的條件P成立時，執行A框，A框執行完畢後，返回來再判斷條件P是否成立，如果仍然成立，返回來再執行A框，如此反復執行A框，直到某一次返回來判斷條件P不成立時為止，此時不再執行A框，離開循環結構。繼續執行下面的框圖。
②直到型循環結構，如右下圖所示，它的功能是先執行重復執行的A框，然後判斷給定的條件P是否成立，如果P仍然不成立，則返回來繼續執行A框，再判斷條件P是否成立。以次重復操作，直到某一次給定的判斷條件P時成立為止，此時不再返回來執行A框，離開循環結構。繼續執行下面的框圖。

㈡ 計算機考研：數據結構常用演算法解析(2)

數據結構是計算機考研408計算機學科專業基礎綜合的重要組成部分，考生需要認真復習，尤其是對於數據結構中一些常用的演算法問題，考生一定要弄懂弄會，理解的去掌握。獵考考研就帶大家一一梳理這些知識點。
第二章
循環鏈表是一種首尾相接的鏈表。也就是終端結點的指針域不是指向NULL空而是指向開始結點(也可設置一個頭結點)，形成一個環。採用循環鏈表在實用中多採用尾指針表示單循環鏈表。這樣做的好處是查找頭指針和尾指針的時間都是O(1)，不用遍歷整個鏈表了。
判別鏈表終止的條件也不同於單鏈表，它是以指針是否等於某一指定指針如頭指針或尾指針來確定。
何時選用順序表、何時選用鏈表作為線性表的存儲結構為宜?
答：
在實際應用中，應根據具體問題的要求和性質來選擇順序表或鏈表作為線性表的存儲結構，通常有以下幾方面的考慮：
1.基於空間的考慮。當要求存儲的線性表長度變化不大，易於事先確定其大小時，為了節約存儲空間，宜採用順序表;反之，當線性表長度變化大，難以估計其存儲規模時，採用動態鏈表作為存儲結構為好。
2.基於時間的考慮。若線性表的操作主要是進行查找，很少做插入和刪除操作時，採用順序表做存儲結構為宜;反之， 若需要對線性表進行頻繁地插入或刪除等的操作時，宜採用鏈表做存儲結構。並且，若鏈表的插入和刪除主要發生在表的首尾兩端，則採用尾指針表示的單循環鏈表為宜。
第2章節有關數據結構演算法，上文中為大家作了分析，希望考生對於這些演算法能夠熟記於心，方便考試的應用和日後的實際操作，預祝大家都能夠取得好成績，加油!

更多詳情請點擊：計算機考研：數據結構常用演算法解析匯總

考研有疑問、不知道如何總結考研考點內容、不清楚考研報名當地政策，點擊底部咨詢官網，免費領取復習資料：https://www.87dh.com/xl/

㈢ 計算機二級數據結構與演算法知識點

一、數據結構

（1）數據結構的基本概念

1、數據：數據是客觀事物的符號表示，是能輸入到計算機中並被計算程序識別和處理的符號的總稱，如文檔，聲音，視頻等。

2、數據元素：數據元素是數據的基本單位。

3、數據對象：數據對象是性質相同的數據元素的集合。

4、數據結構：是指由某一數據對象中所有數據成員之間的關系組成的集合。

（2）邏輯結構和存儲結構

1、數據結構可分為數據的邏輯結構和存儲結構。

1）數據的邏輯結構是對數據元素之間的邏輯關系的描述，與數據的存儲無關，是面向問題的，是獨立於計算機的。它包括數據對象和數據對象之間的關系。

2）數據的存儲結構也稱為數據的物理結構，是數據在計算機中的存放的方式，是面向計算機的，它包括數據元素的存儲方式和關系的存儲方式。

2、存儲結構和邏輯結構的關系：一種數據的邏輯結構可以表示成多種存儲結構即數據的邏輯結構和存儲結構不一定一一對應。

3、常見的存儲結構有：順序，鏈接，索引等。採用不同的存儲結構其數據處理的效率是不同的。

㈣ 程序框圖的高中數學演算法知識點總結

1、程序框圖基本概念：

(一)程序構圖的概念：程序框圖又稱流程圖，是一種用規定的圖形、指向線及文字說明來准確、直觀地表示演算法的圖形。

一個程序框圖包括以下幾部分：表示相應操作的程序框;帶箭頭的流程線;程序框外必要文字說明。

(二)構成程序框的圖形符號及其作用

學習這部分知識的時候，要掌握各個圖形的'形狀、作用及使用規則，畫程序框圖的規則如下：

1、使用標準的圖形符號。2、框圖一般按從上到下、從左到右的方向畫。3、除判斷框外，大多數流程圖符號只有一個進入點和一個退出點。判斷框具有超過一個退出點的唯一符號。4、判斷框分兩大類，一類判斷框「是」與「否」兩分支的判斷，而且有且僅有兩個結果;另一類是多分支判斷，有幾種不同的結果。5、在圖形符號內描述的語言要非常簡練清楚。

(三)、演算法的三種基本邏輯結構：順序結構、條件結構、循環結構。

1、順序結構：順序結構是最簡單的演算法結構，語句與語句之間，框與框之間是按從上到下的順序進行的，它是由若干個依次執行的處理步驟組成的，它是任何一個演算法都離不開的一種基本演算法結構。

順序結構在程序框圖中的體現就是用流程線將程序框自上而下地連接起來，按順序執行演算法步驟。如在示意圖中，A框和B框是依次執行的，只有在執行完A框指定的操作後，才能接著執行B框所指定的操作。

2、條件結構：

條件結構是指在演算法中通過對條件的判斷

根據條件是否成立而選擇不同流向的演算法結構。

條件P是否成立而選擇執行A框或B框。無論P條件是否成立，只能執行A框或B框之一，不可能同時執行A框和B框，也不可能A框、B框都不執行。一個判斷結構可以有多個判斷框。

3、循環結構：

在一些演算法中，經常會出現從某處開始，按照一定條件，反復執行某一處理步驟的情況，這就是循環結構，反復執行的處理步驟為循環體，顯然，循環結構中一定包含條件結構。循環結構又稱重復結構，循環結構可細分為兩類：

(1)、一類是當型循環結構，如下左圖所示，它的功能是當給定的條件P成立時，執行A框，A框執行完畢後，再判斷條件P是否成立，如果仍然成立，再執行A框，如此反復執行A框，直到某一次條件P不成立為止，此時不再執行A框，離開循環結構。

(2)、另一類是直到型循環結構，如下右圖所示，它的功能是先執行，然後判斷給定的條件P是否成立，如果P仍然不成立，則繼續執行A框，直到某一次給定的條件P成立為止，此時不再執行A框，離開循環結構。

當型循環結構 直到型循環結構

注意：1循環結構要在某個條件下終止循環，這就需要條件結構來判斷。因此，循環結構中一定包含條件結構，但不允許「死循環」。2在循環結構中都有一個計數變數和累加變數。計數變數用於記錄循環次數，累加變數用於輸出結果。計數變數和累加變數一般是同步執行的，累加一次，計數一次。

㈤ 數據結構與演算法基礎知識

1.數據結構的邏輯結構

(1)集合結構

(2)線性結構(存在唯一的第一個元素與唯一的最後一個元素)(eg: 線性表、隊列、棧、字元串、數組、鏈表)

(3)樹形結構(一對多)

(4)圖形結構(多對多)

2.數據結構的物理(存儲)結構

(1).順序存儲結構(插入與刪除低效因為要挪動其他元素的位置。但是遍歷簡單)

(2).鏈式存儲結構(插入與刪除高效，但是遍歷低效)

3.大O表示法(注意大O表示法表達的是最壞的情況)

規則：

(1)用常數1取代其他所有的常數(注意常數0也當1算)(3 -> 1, O(1))

(2) 只保留最高階項(n^3+2n^2+5 ->n^3, O(n^3))

(3) 若存在最高階，省略與其想成的常數(2n^3 -> n^3, O(n^3))

4. 時間復雜度類型

(1)常數階

(2)線性階

(3)平方階

(4)對數階

(5)立方階

(6)nlog階

(7)指數階(O(2^n)或O(n!), 往往會造成噩夢般的時間消耗)

5. 空間復雜度(用大O表示法求解改演算法的輔助空間即可，例如用於交換變數用的臨時變數的數量)

六. 順序存儲的線性表

線性表結構特點：

(1) 存在唯一一個的被稱作」第一個」的數據元素；

(2) 存在唯一一個的被稱作」第二個」的數據元素；

(3) 除了第一個元素以外，結構中的每個數據元素均有一個前驅；

(4) 除了最後一個元素以外，結構中的每個數據元素均有一個後繼。

七. 鏈式存儲的線性表(單鏈表)

首元結點是鏈表中第一個值域不為空的結點。

頭結點是一個值域為空且處於首位的結點。

首指針可指向首元結點也可指向頭結點，但是如果指向頭結點可以更加方便的處理單鏈表的插入和刪除問題，不用再對首位做額外判斷，並且指向頭節點的指針永遠不用變化。

*注意一下單鏈表的前插法和尾插法。尾插法更符合邏輯