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

第x章（名稱）

專題（名稱）

知識與技能考核點

第1章

程序設計和C語言概述

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

第2章

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

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

第3章

選擇結構程序設計

熟練掌握關系運算、條件運算和邏輯運算。

第4章

循環(huán)結構程序設計

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

第5章

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

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

第6章

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

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

第7章

指針

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

第x章（名稱）

專題（名稱）

知識與技能考核點

第一章 緒論

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

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

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

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

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

第二章 線性表

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

（1）了解線性表的定義和線性結構的特點。

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

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

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

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

第三章 棧和隊列

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

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

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

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

第四章 樹和二叉樹

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

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

（2）理解二叉樹的性質、二叉樹的存儲結構。

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

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

第五章 圖

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

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

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

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

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

第六章 查找

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

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

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

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

第七章 內部排序

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

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

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

（3）會寫出排序執(zhí)行過程，能夠對各種排序算法進行分析比較。