2020井岡山大學(xué)專(zhuān)升本《軟件工程》專(zhuān)業(yè)考試大綱

第x章（名稱(chēng)）

專(zhuān)題（名稱(chēng)）

知識(shí)與技能考核點(diǎn)

第1章

程序設(shè)計(jì)和C語(yǔ)言概述

了解C語(yǔ)言的發(fā)展及特點(diǎn)，了解簡(jiǎn)單C程序的組成，了解各編譯系統(tǒng)的搭建。

第2章

數(shù)據(jù)的表現(xiàn)形式及其運(yùn)算和順序程序設(shè)計(jì)

了解順序結(jié)構(gòu)程序設(shè)計(jì)，掌握基本數(shù)據(jù)類(lèi)型的定義和表示范圍，熟練掌握數(shù)據(jù)類(lèi)型的選擇和標(biāo)準(zhǔn)輸入/輸出。

第3章

選擇結(jié)構(gòu)程序設(shè)計(jì)

熟練掌握關(guān)系運(yùn)算、條件運(yùn)算和邏輯運(yùn)算。

第4章

循環(huán)結(jié)構(gòu)程序設(shè)計(jì)

熟練掌握三種循環(huán)語(yǔ)句的實(shí)現(xiàn)方法，了解三種循環(huán)的區(qū)別和轉(zhuǎn)換。

第5章

利用數(shù)組處理批量數(shù)據(jù)

掌握一維數(shù)組的定義和數(shù)組元素的引用方法。

第6章

使用函數(shù)實(shí)現(xiàn)模塊化程序設(shè)計(jì)

掌握函數(shù)的定義方法和調(diào)用規(guī)則，掌握在C語(yǔ)言程序中數(shù)據(jù)的傳遞規(guī)則，了解函數(shù)的返回值及其類(lèi)型。

第7章

指針

掌握最基本的指針定義和引用方法。

第x章（名稱(chēng)）

專(zhuān)題（名稱(chēng)）

知識(shí)與技能考核點(diǎn)

第一章 緒論

數(shù)據(jù)結(jié)構(gòu)基本概念和術(shù)語(yǔ)，算法、算法的描述和算法分析。

（1）了解非數(shù)值問(wèn)題的數(shù)學(xué)模型是表、樹(shù)和圖之類(lèi)的數(shù)據(jù)結(jié)構(gòu)。

（2）理解數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類(lèi)型等的定義。

（3）掌握數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)及其種類(lèi)；算法的重要特征等。

（4）會(huì)根據(jù)語(yǔ)句的最大頻度計(jì)算算法的時(shí)間復(fù)雜度。

第二章 線(xiàn)性表

線(xiàn)性表的定義、線(xiàn)性表的邏輯結(jié)構(gòu)、線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，單向鏈表、循環(huán)鏈表和雙向鏈表，一元多項(xiàng)式的表示及相加。

（1）了解線(xiàn)性表的定義和線(xiàn)性結(jié)構(gòu)的特點(diǎn)。

（2）理解線(xiàn)性表的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，理解數(shù)組與單鏈表表示表的優(yōu)缺點(diǎn)。

（3）掌握順序表中數(shù)據(jù)元素的存儲(chǔ)位置的計(jì)算，順序表、單向鏈表、循環(huán)鏈表和雙向鏈表的查找、插入、刪除等有關(guān)操作。

（4）會(huì)用單鏈表編寫(xiě)簡(jiǎn)單操作算法。

（5）能夠從時(shí)間和空間復(fù)雜度的角度綜合比較兩種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用場(chǎng)合。

第三章 棧和隊(duì)列

棧的定義、棧的表示和實(shí)現(xiàn)；隊(duì)列的定義、隊(duì)列的表示和實(shí)現(xiàn)，鏈隊(duì)列、循環(huán)隊(duì)列。

（1）了解棧和隊(duì)列的定義。

（2）理解線(xiàn)性表、棧和隊(duì)列特點(diǎn)及區(qū)別，棧對(duì)實(shí)現(xiàn)遞歸過(guò)程的作用。

（3）掌握順序棧、鏈棧的入棧和出棧操作，順序隊(duì)列、鏈隊(duì)列的入隊(duì)和出隊(duì)操作，棧和隊(duì)列的空和滿(mǎn)的判斷。

第四章 樹(shù)和二叉樹(shù)

樹(shù)的結(jié)構(gòu)定義和基本操作、二叉樹(shù)的定義、二叉樹(shù)的性質(zhì)、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)、遍歷二叉樹(shù)，樹(shù)和森林、樹(shù)的存儲(chǔ)結(jié)構(gòu)、森林與二叉樹(shù)的轉(zhuǎn)換、樹(shù)的遍歷，最優(yōu)二叉樹(shù)和哈夫曼編碼。

（1）了解樹(shù)的定義和二叉樹(shù)的定義。

（2）理解二叉樹(shù)的性質(zhì)、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)。

（3）掌握遍歷二叉樹(shù)的方法、森林與二叉樹(shù)的轉(zhuǎn)換、最優(yōu)二叉樹(shù)的構(gòu)造和哈夫曼編碼。

（4）會(huì)利用二叉樹(shù)的先根、中根和后根遍歷解決有關(guān)二叉樹(shù)的應(yīng)用問(wèn)題，會(huì)采用二叉鏈表存儲(chǔ)結(jié)構(gòu)編寫(xiě)與二叉樹(shù)簡(jiǎn)單遞歸的算法。

第五章 圖

圖的定義和術(shù)語(yǔ)、圖的存儲(chǔ)結(jié)構(gòu)：鄰接矩陣和鄰接表，圖的遍歷：深度優(yōu)先搜索和廣度優(yōu)先搜索，無(wú)向網(wǎng)的最小生成樹(shù)，有向網(wǎng)的最短路徑。

（1）了解圖的定義和術(shù)語(yǔ)，生成樹(shù)和最小生成樹(shù)、最短路徑的概念。

（2）理解鄰接矩陣中元素的含義和鄰接表中結(jié)點(diǎn)的含義。

（3）掌握深度優(yōu)先搜索和廣度優(yōu)先搜索算法思想。

（4）會(huì)用Prim算法和Kruskal算法手工構(gòu)造無(wú)向網(wǎng)的最小生成樹(shù)，會(huì)找出有向網(wǎng)任意頂點(diǎn)間的最短路徑。

第六章 查找

靜態(tài)查找表：順序查找、二分查找和分塊查找；動(dòng)態(tài)查找表：二叉排序樹(shù)；哈希查找、哈希函數(shù)的構(gòu)造方法和處理沖突的方法

（1）了解順序查找、二分查找和分塊查找的概念，以及二叉排序樹(shù)、哈希查找等概念。

（2）掌握二叉排序樹(shù)的查找、插入和刪除操作算法思想。

（3）掌握哈希函數(shù)的構(gòu)造方法和處理沖突的方法，會(huì)用哈希函數(shù)、加上開(kāi)放地址法或拉鏈法建立哈希表。

第七章 內(nèi)部排序

直接插入排序、希爾排序、快速排序、簡(jiǎn)單選擇排序、堆排序、歸并排序和基數(shù)排序。各種內(nèi)部排序方法的比較。

（1）了解排序算法的穩(wěn)定性問(wèn)題。

（2）理解直接插入排序、希爾排序、冒泡排序、快速排序、簡(jiǎn)單選擇排序、堆排序、歸并排序和基數(shù)排序的基本思想。

（3）會(huì)寫(xiě)出排序執(zhí)行過(guò)程，能夠?qū)Ω鞣N排序算法進(jìn)行分析比較。