二級計算機等級考試公共基礎(chǔ)知識大綱要求
基本要求
掌握算法基本概念
掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作
掌握基本排序和查找算法
掌握逐步求精的結(jié)構(gòu)化程序設(shè)計算法
掌握工程的基本算法,具有初步應(yīng)用相關(guān)技術(shù)進行軟件開發(fā)能力
考試內(nèi)容
一 基本數(shù)據(jù)結(jié)構(gòu)與算法
1 算法的基本概念,算法復雜度概念和意義(時間復雜度和空間復雜度)
2 數(shù)據(jù)結(jié)構(gòu)的定義,數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的圖形表示,線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念
3 線性表的定義,線性表的順序存儲結(jié)構(gòu)極其插入與刪除的運算
4 棧和隊列的定義:棧和隊列的順序存儲結(jié)構(gòu)及其基本運算
5 線性單鏈表多向鏈表與循環(huán)鏈表及其基本運算
6 樹的基本概念,二叉樹的定義及其存儲結(jié)構(gòu),二叉樹的前序,中序,后序遍歷
7 順序查找與二分法查找,基本排序算法(交換類,選擇類,插入類)
二 程序設(shè)計基礎(chǔ)
1 程序設(shè)計方法與風格
2 結(jié)構(gòu)化程序設(shè)計
3 面向?qū)ο蟮某绦蛟O(shè)計方法,對象,方法,屬性及繼承與多態(tài)性
三 軟件的工程基礎(chǔ)
1 軟件工程基本概念,軟件聲明周期概念,軟件工具與軟件開發(fā)環(huán)境
2 結(jié)構(gòu)化分析方法,數(shù)據(jù)流圖,數(shù)據(jù)字典,軟件需求規(guī)格說明書
3 結(jié)構(gòu)化程序設(shè)計方法總體設(shè)計與詳細設(shè)計
4 軟件測試方法:白盒測試與黑盒測試,測試用例設(shè)計,軟件測試的實施,單元測試,集成測試和系統(tǒng)測試
5 程序的調(diào)試;靜態(tài)調(diào)試與動態(tài)調(diào)試
四 數(shù)據(jù)庫設(shè)計基礎(chǔ)
1 數(shù)據(jù)庫的基本概念;數(shù)據(jù)庫,數(shù)據(jù)庫管理系統(tǒng),數(shù)據(jù)庫系統(tǒng),數(shù)據(jù)模型,E-R圖,從導出關(guān)系數(shù)據(jù)模型
2 關(guān)系代數(shù)運算包括集合運算及選擇,投影,連接運算,數(shù)據(jù)庫規(guī)范化理論
3 數(shù)據(jù)設(shè)計方法和步驟;需求分析,概念設(shè)計,邏輯設(shè)計,和物理設(shè)計的相關(guān)策略
公共基礎(chǔ)知識各章掌握重點歸納
一 數(shù)據(jù)結(jié)構(gòu)與算法
算法定義：所謂算法是解題方案的準確而完整的描述
算法的特征：可行性、確定性、有窮性、擁有足夠的情報
算法的二要素；一是對數(shù)據(jù)對象的控制和操作，二是算法的控制結(jié)構(gòu)
算法的三種基本控制結(jié)構(gòu)：順序，選擇，循環(huán)
算法復雜度包括時間復雜度和空間復雜度
時間復雜度是指執(zhí)行算法所需要的計算工作量
------可以用算法在執(zhí)行過程中所需基本運算的執(zhí)行次數(shù)來度量算法的工作量
算法的空間復雜度是指執(zhí)行這個算法所需要的內(nèi)存空間
數(shù)據(jù)結(jié)構(gòu)是指相互關(guān)聯(lián)的數(shù)據(jù)元素的集合
------數(shù)據(jù)元素之間的前后件關(guān)系是指他們的邏輯關(guān)系，而與他們在計算機中的存儲位置無關(guān)
數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)的嘸峁乖詡撲慊媧⒖占渲械拇娣判問匠莆蕕拇媧⒔峁?BR>數(shù)據(jù)結(jié)構(gòu)的兩大類型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)
線性結(jié)構(gòu)與非線性結(jié)構(gòu)都可以是空的數(shù)據(jù)結(jié)構(gòu)
在計算機中存放線性表一種最簡單的方法是順序存儲
棧是先進后出的線性表（棧頂top 棧底bottom）
隊列是先進先出的線性（表排頭指針front 尾指針rear）
鏈式存儲方式中每個結(jié)點由兩部分組成：數(shù)據(jù)域和指針域
當從線性鏈表中刪除一個元素后該元素存儲結(jié)點就變?yōu)榭臻e，應(yīng)將該空閑結(jié)點送回到可利用棧
循環(huán)鏈表增加了一個表頭結(jié)點
基本要求
掌握算法基本概念
掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作
掌握基本排序和查找算法
掌握逐步求精的結(jié)構(gòu)化程序設(shè)計算法
掌握工程的基本算法,具有初步應(yīng)用相關(guān)技術(shù)進行軟件開發(fā)能力
考試內(nèi)容
一 基本數(shù)據(jù)結(jié)構(gòu)與算法
1 算法的基本概念,算法復雜度概念和意義(時間復雜度和空間復雜度)
2 數(shù)據(jù)結(jié)構(gòu)的定義,數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的圖形表示,線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念
3 線性表的定義,線性表的順序存儲結(jié)構(gòu)極其插入與刪除的運算
4 棧和隊列的定義:棧和隊列的順序存儲結(jié)構(gòu)及其基本運算
5 線性單鏈表多向鏈表與循環(huán)鏈表及其基本運算
6 樹的基本概念,二叉樹的定義及其存儲結(jié)構(gòu),二叉樹的前序,中序,后序遍歷
7 順序查找與二分法查找,基本排序算法(交換類,選擇類,插入類)
二 程序設(shè)計基礎(chǔ)
1 程序設(shè)計方法與風格
2 結(jié)構(gòu)化程序設(shè)計
3 面向?qū)ο蟮某绦蛟O(shè)計方法,對象,方法,屬性及繼承與多態(tài)性
三 軟件的工程基礎(chǔ)
1 軟件工程基本概念,軟件聲明周期概念,軟件工具與軟件開發(fā)環(huán)境
2 結(jié)構(gòu)化分析方法,數(shù)據(jù)流圖,數(shù)據(jù)字典,軟件需求規(guī)格說明書
3 結(jié)構(gòu)化程序設(shè)計方法總體設(shè)計與詳細設(shè)計
4 軟件測試方法:白盒測試與黑盒測試,測試用例設(shè)計,軟件測試的實施,單元測試,集成測試和系統(tǒng)測試
5 程序的調(diào)試;靜態(tài)調(diào)試與動態(tài)調(diào)試
四 數(shù)據(jù)庫設(shè)計基礎(chǔ)
1 數(shù)據(jù)庫的基本概念;數(shù)據(jù)庫,數(shù)據(jù)庫管理系統(tǒng),數(shù)據(jù)庫系統(tǒng),數(shù)據(jù)模型,E-R圖,從導出關(guān)系數(shù)據(jù)模型
2 關(guān)系代數(shù)運算包括集合運算及選擇,投影,連接運算,數(shù)據(jù)庫規(guī)范化理論
3 數(shù)據(jù)設(shè)計方法和步驟;需求分析,概念設(shè)計,邏輯設(shè)計,和物理設(shè)計的相關(guān)策略
公共基礎(chǔ)知識各章掌握重點歸納
一 數(shù)據(jù)結(jié)構(gòu)與算法
算法定義：所謂算法是解題方案的準確而完整的描述
算法的特征：可行性、確定性、有窮性、擁有足夠的情報
算法的二要素；一是對數(shù)據(jù)對象的控制和操作，二是算法的控制結(jié)構(gòu)
算法的三種基本控制結(jié)構(gòu)：順序，選擇，循環(huán)
算法復雜度包括時間復雜度和空間復雜度
時間復雜度是指執(zhí)行算法所需要的計算工作量
------可以用算法在執(zhí)行過程中所需基本運算的執(zhí)行次數(shù)來度量算法的工作量
算法的空間復雜度是指執(zhí)行這個算法所需要的內(nèi)存空間
數(shù)據(jù)結(jié)構(gòu)是指相互關(guān)聯(lián)的數(shù)據(jù)元素的集合
------數(shù)據(jù)元素之間的前后件關(guān)系是指他們的邏輯關(guān)系，而與他們在計算機中的存儲位置無關(guān)
數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)的嘸峁乖詡撲慊媧⒖占渲械拇娣判問匠莆蕕拇媧⒔峁?BR>數(shù)據(jù)結(jié)構(gòu)的兩大類型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)
線性結(jié)構(gòu)與非線性結(jié)構(gòu)都可以是空的數(shù)據(jù)結(jié)構(gòu)
在計算機中存放線性表一種最簡單的方法是順序存儲
棧是先進后出的線性表（棧頂top 棧底bottom）
隊列是先進先出的線性（表排頭指針front 尾指針rear）
鏈式存儲方式中每個結(jié)點由兩部分組成：數(shù)據(jù)域和指針域
當從線性鏈表中刪除一個元素后該元素存儲結(jié)點就變?yōu)榭臻e，應(yīng)將該空閑結(jié)點送回到可利用棧
循環(huán)鏈表增加了一個表頭結(jié)點