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