2020井岡山大學專升本《計算機科學與技術(shù)》專業(yè)考試大綱

第x章（名稱）

專題（名稱）

知識與技能考核點

第1章

程序設計和C語言概述

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

第2章

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

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

第3章

選擇結(jié)構(gòu)程序設計

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

第4章

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

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

第5章

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

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

第6章

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

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

第7章

指針

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

第x章（名稱）

專題（名稱）

知識與技能考核點

第一章 緒論

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

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

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

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

（4）會根據(jù)語句的最大頻度計算算法的時間復雜度。

第二章 線性表

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

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

（2）理解線性表的順序存儲和鏈式存儲，理解數(shù)組與單鏈表表示表的優(yōu)缺點。

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

（4）會用單鏈表編寫簡單操作算法。

（5）能夠從時間和空間復雜度的角度綜合比較兩種存儲結(jié)構(gòu)的特點及適用場合。

第三章 棧和隊列

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

（1）了解棧和隊列的定義。

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

（3）掌握順序棧、鏈棧的入棧和出棧操作，順序隊列、鏈隊列的入隊和出隊操作，棧和隊列的空和滿的判斷。

第四章 樹和二叉樹

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

（1）了解樹的定義和二叉樹的定義。

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

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

（4）會利用二叉樹的先根、中根和后根遍歷解決有關(guān)二叉樹的應用問題，會采用二叉鏈表存儲結(jié)構(gòu)編寫與二叉樹簡單遞歸的算法。

第五章 圖

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

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

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

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

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

第六章 查找

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

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

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

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

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

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

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

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

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