計算機二級考試是以程式設計為主的計算機等級考試，目的是促進考生學習程式設計的熱情，提高考生的程式設計水平。而程式設計離不開演算法、軟體工程等知識的。本課程作為計算機二級考試的公共基礎課程，從理論的角度對資料結構、軟體工程、結構化程式設計與物件導向的程式設計、資料庫基礎知識進行了簡單的介紹，擴充套件考生的知識面，並對程式設計知識有乙個系統的了解。
本課程一共有四個部分。第一部分，主要介紹演算法的基本概念，資料結構的基本概念和定義，線性表及其基本運算，二叉樹的基本概念、儲存結構及其應用，並介紹了一些常用的演算法；第二部分，主要介紹程式設計的方法與風格，結構化程式設計，物件導向的程式設計方法，物件，方法，屬性及繼承與多型性；第三部分，主要介紹軟體工程的基本概念，結構化分析方法，結構化設計方法，軟體測試的基本方法和程式的除錯方法，從工程的角度對軟體開發進行了介紹；第四部分，主要介紹資料庫，資料庫管理系統，資料庫系統的基本概念，資料模型，實體聯絡模型及e-r圖等基本概念，關係代數理論中的基本運算，資料庫設計的基本方法和步驟。
本課程作為公共基礎課，在有限的篇幅和學時的情況下，當然不能將所涉及到的相關知識都講透，如果對這些知識感興趣，可去查閱相關主題的書籍，深入學習。
第一章的參考書：各類《資料結構》教程
第二章的參考書：各類介紹程式設計與演算法、物件導向程式設計的教程
第三章的參考書：各類《軟體工程》教程
第四章的參考書：各類《資料庫原理與應用》教程的基礎部分
本課程的學習，要求認真看書，對書中的內容進行歸納和總結，將所有的知識穿成一條線。
在看書的過程中，要仔細閱讀，對書中重要的內容、概念要記住，因為本課程的考試是採用標準化的考試方式，單選和填空兩種題型，因此要求考生對知識的掌握要準確，不能模稜兩可。
反覆地看書，做題，因為本課程主要是一些理論的知識，要求記憶的內容很多，因此，必須多做題，多看書，在做題的過程中檢驗自己對知識的理解和掌握情況是否到位、正確。自己總結課程的內容，也是幫助理解和記憶的好方法。
1．了解演算法的基本概念和一些常用的演算法，學會計算演算法的時間複雜度；
2．掌握資料結構的基本概念，並了解資料的邏輯結構和儲存結構，學會利用圖形的方式表示資料結構；
3．了解線性表的基本概念，並掌握線性表的順序儲存結構以及順序儲存的線性表的基本運算；
4．了解棧和佇列的基本概念，並掌握它們的基本運算；
5．了解線性鍊錶的基本概念，並掌握線性鍊錶的基本運算，同時，了解迴圈鍊錶的基本概念和基本操作；
6．理解樹的概念，尤其是二叉樹的基本概念和相關性質，掌握二叉樹的儲存結構和遍歷技術；
7．掌握查詢技術，學會利用順序查詢和二分查詢在數列中查詢指定的資料；
8．學會利用相關的排序技術實現無序數列的排序操作。
演算法是指解題方****而完整的描述。即是一組嚴謹地定義運算順序的規則，並且每乙個規則都是有效的，且是明確的，沒有二義性，同時該規則將在有限次運算後可終止。
（1）可行性
由於演算法的設計是為了在某乙個特定的計算工具上解決某乙個實際的問題而設計的，因此，它總是受到計算工具的限制，使執行產生偏差。
如：計算機的數值有效位是有限的，當大數和小數進行運算時，往往會因為有效位數的影響而使小數丟失，因此，在演算法設計時，應該考慮到這一點。
（2）確定性
演算法的設計必須是每乙個步驟都有明確的定義，不允許有模糊的解釋，也不能有多義性。
例如，乙個實際的問題，小寶和萍萍共有12個蘋果，小寶比萍萍多4個，請問小寶和萍萍各有幾個蘋果？這個問題，我們可以立乙個方程來求解，要求x和y的值，公式是正確的，但如何讓計算能夠進行計算，我們的演算法不能把公式直接輸進去，而應該設計出解題的步驟和過程。
即設計的演算法是計算工具所能夠正常解決問題的過程。
（3）有窮性
演算法的有窮性，即在一定的時間是能夠完成的，即演算法應該在計算有限個步驟後能夠正常結束。
例如，在數學中的無窮級數，在計算機中只能求有限項，即計算的過程是有窮的。
（4）擁有足夠的情報
演算法的執行與輸入的資料和提供的初始條件相關，不同的輸入或初始條件會有不同的輸出結果，提供準確的初始條件和資料，才能使演算法正確執行。
一是資料物件的運算和操作，二是演算法的控制結構。
（1）演算法中對資料的運算和操作
演算法實際上是按解題要求從環境能進行的所有操作中選擇合適的操作所組成的一組指令序列。即演算法是計算機所能夠處理的操作所組成的指令序列。
（2）演算法的控制結構
演算法的功能不僅取決於所選用的操作，而且還與各操作之間的順序有關。
在演算法中，操作的執行順序又稱演算法的控制結構，一般的演算法控制結構有三種：順序結構、選擇結構和迴圈結構。
在演算法描述是，有相關的工具對這三種結構進行描述，常用的描述工具有：流程圖、n-s結構圖和演算法描述語言等。
為用計算機解決實際問題而設計的演算法，即是計算機演算法。
通常的演算法設計有如下幾種：
（1）列舉法
列舉法的基本思想是，根據提出的問題，列舉出所有可能的情況，並用問題中給定的條件檢驗哪些是滿足條件的，哪些是不滿足條件的。列舉法通常用於解決「是否存在」或「有哪些可能」等問題。
例如，我國古代的趣味數學題：「百錢買百雞」、「雞兔同籠」等，均可採用列舉法進行解決。
使用列舉法時，要對問題進行詳細的分析，將與問題有關的知識條理化、完備化、系統化，從中找出規律。
（2）歸納法
歸納法的基本思想是，通過列舉少量的特殊情況，經過分析，最後找出一般的關係。歸納是一種抽象，即從特殊現象中找出一般規律。但由於在歸納法中不可能對所有的情況進行列舉，因此，該方法得到的結論只是一種猜測，還需要進行證明。
（3）遞推
遞推，即是從已知的初始條件出發，逐次推出所要求的各個中間環節和最後結果。其中初始條件或問題本身已經給定，或是通過對問題的分析與化簡而確定。
遞推的本質也是一種歸納，遞推關係式通常是歸納的結果。
例如，裴波那契數列，是採用遞推的方法解決問題的。
（4）遞迴
在解決一些複雜問題時，為了降低問題的複雜程式，通常是將問題逐層分解，最後歸結為一些最簡單的問題。這種將問題逐層分解的過程，並沒有對問題進行求解，而只是當解決了最後的問題那些最簡單的問題後，再沿著原來分解的逆過程逐步進行綜合，這就是遞迴的方法。
遞迴分為直接遞迴和間接遞迴兩種方法。如果乙個演算法直接呼叫自己，稱為直接遞迴呼叫；如果乙個演算法a呼叫另乙個演算法b，而演算法b又呼叫演算法a，則此種遞迴稱為間接遞迴呼叫。
（5）減半遞推技術
減半遞推即將問題的規模減半，然後，重複相同的遞推操作。
例如，一元二次方程的求解。
（6）回溯法
有些實際的問題很難歸納出一組簡單的遞推公式或直觀的求解步驟，也不能使用無限的列舉。對於這類問題，只能採用試探的方法，通過對問題的分析，找出解決問題的線索，然後沿著這個線索進行試探，如果試探成功，就得到問題的解，如果不成功，再逐步回退，換別的路線進行試探。這種方法，即稱為回溯法。
如人工智慧中的機械人下棋。
演算法的複雜度包括時間複雜度和空間複雜度。
即實現該演算法需要的計算工作量。演算法的工作量用演算法所執行的基本運算次數來計算。
同乙個問題規模下，如果演算法執行所需要的基本次數取決於某一特定輸入時，可以用以下兩種方法來分析演算法的工作量：
演算法工作量=f(n)
（1）平均性態
用各種特定輸入下的基本運算次數的加權平均值來度量演算法的工作量。
設x是某個可能輸入中的某個特定輸入，p(x)是x出現的概率，t(x)是演算法在輸入為x時所執行的基本運算次數，則演算法的平均性態定義為：
dn表示當規模為n時，演算法執行時所有可能輸入的集合。
（2）最壞情況複雜度
指在規模為n時，演算法所執行的基本運算的最大次數。它定義為：
例如，在具有n個元素的數列中搜尋乙個數x。
平均性態：
即該數在數列中任何位置出現的數列是相同的，也有可能不存在，存在的概率為q。
如果有一半的機會存在，則概率q為1/2，平均性態：
如果查詢的元素一定在數列中，則每個數存在的概率即為1，則平均性態為：
最壞情況分析：即要查詢的元素x在數列的最後或不在數列中，顯然，它的最壞情況複雜度為：
指要執行該演算法所需要的記憶體空間。演算法所占用的記憶體空間包括演算法程式所佔的空間、輸入的初始資料所佔的儲存空間以及演算法執行過程中所需要的額外空間，如執行過程中工作單元以及某種資料結構所需要的附加儲存空間等。
資料結構是指相互有關聯的資料元素的集合。它包括以下兩個方面：
● 表示資料元素的資訊
● 表示各資料之間的前後件關係
是指反映資料元素之間的邏輯關係的資料結構。
資料的邏輯結構有兩個要素：
● 資料元素的集合，記作d
● 資料之間的前後件關係，記作r
則資料結構b=（d，r）
資料的邏輯結構在計算機儲存空間中的存放形式稱為資料的儲存結構，或資料的物理結構。
即資料儲存時，不僅要存放資料元素的資訊，而且要儲存資料元素之間的前後件關係的資訊。
通常的資料儲存結構有順序、鏈結、索引等儲存結構。
資料結構的圖形表示有兩個元素：
● 中間標有元素值的方框表示資料元素，稱為資料結點
● 用有向線段表示資料元素之間的前後件關係，即有向線段從前件結點指向後件結點
注意：在結構圖中，沒有前件的結點稱為根結點，沒有後件的結點稱為終端結點，也稱葉子結點。
如果乙個資料元素都沒有，該資料結構稱為空資料結構；在空資料結構中插入乙個新的元素後資料結構變為非空資料結構；將資料結構中的所有元素均刪除，則該資料結構變成空資料結構。
如果乙個非空的資料結構滿足如下條件，則該資料結構為線性結構：
● 有且只有乙個根結點
● 每乙個結點最多只有乙個前件，也最多只有乙個後件
線性結構又稱線性表。
注意：**性結構表中插入或刪除元素，該線性表仍然應滿足線性結構。
如果乙個資料結構不滿足線性結構，則稱為非線性結構。
二級基礎知識公共
第一章資料結構與演算法 經過對部分考生的調查以及對近年真題的總結分析，筆試部分經常考查的是演算法複雜度 資料結構的概念 棧 二叉樹的遍歷 二分法查詢，讀者應對此部分進行重點學習。詳細重點學習知識點 1 演算法的概念 演算法時間複雜度及空間複雜度的概念 2 資料結構的定義 資料邏輯結構及物理結構的定義...
二級公共基礎知識
第一章資料結構與演算法 經過對部分考生的調查以及對近年真題的總結分析，筆試部分經常考查的是演算法複雜度 資料結構的概念 棧 二叉樹的遍歷 二分法查詢，讀者應對此部分進行重點學習。詳細重點學習知識點 1 演算法的概念 演算法時間複雜度及空間複雜度的概念 2 資料結構的定義 資料邏輯結構及物理結構的定義...
二級公共基礎知識總結
第一章資料結構與演算法 1.1 演算法 演算法 是一組有窮指令集，是解題方 而完整的描述。通俗地說，演算法就是計算機解題的過程。演算法不等於程式，也不等於計算方法，程式的編制不可能優於演算法的設計。演算法是一組嚴謹地定義運算順序的規則，每乙個規則都是有效的，且是明確的，此順序將在有限的次數下終止。所...