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