2020井冈山大学专升本《计算机科学与技术》专业考试大纲

第x章（名称）

专题（名称）

知识与技能考核点

第1章

程序设计和C语言概述

了解C语言的发展及特点，了解简单C程序的组成，了解各编译系统的搭建。

第2章

数据的表现形式及其运算和顺序程序设计

了解顺序结构程序设计，掌握基本数据类型的定义和表示范围，熟练掌握数据类型的选择和标准输入/输出。

第3章

选择结构程序设计

熟练掌握关系运算、条件运算和逻辑运算。

第4章

循环结构程序设计

熟练掌握三种循环语句的实现方法，了解三种循环的区别和转换。

第5章

利用数组处理批量数据

掌握一维数组的定义和数组元素的引用方法。

第6章

使用函数实现模块化程序设计

掌握函数的定义方法和调用规则，掌握在C语言程序中数据的传递规则，了解函数的返回值及其类型。

第7章

指针

掌握最基本的指针定义和引用方法。

第x章（名称）

专题（名称）

知识与技能考核点

第一章 绪论

数据结构基本概念和术语，算法、算法的描述和算法分析。

（1）了解非数值问题的数学模型是表、树和图之类的数据结构。

（2）理解数据、数据元素、数据对象、数据结构和数据类型等的定义。

（3）掌握数据的逻辑结构和存储结构及其种类；算法的重要特征等。

（4）会根据语句的最大频度计算算法的时间复杂度。

第二章 线性表

线性表的定义、线性表的逻辑结构、线性表的顺序存储结构和链式存储结构，单向链表、循环链表和双向链表，一元多项式的表示及相加。

（1）了解线性表的定义和线性结构的特点。

（2）理解线性表的顺序存储和链式存储，理解数组与单链表表示表的优缺点。

（3）掌握顺序表中数据元素的存储位置的计算，顺序表、单向链表、循环链表和双向链表的查找、插入、删除等有关操作。

（4）会用单链表编写简单操作算法。

（5）能够从时间和空间复杂度的角度综合比较两种存储结构的特点及适用场合。

第三章 栈和队列

栈的定义、栈的表示和实现；队列的定义、队列的表示和实现，链队列、循环队列。

（1）了解栈和队列的定义。

（2）理解线性表、栈和队列特点及区别，栈对实现递归过程的作用。

（3）掌握顺序栈、链栈的入栈和出栈操作，顺序队列、链队列的入队和出队操作，栈和队列的空和满的判断。

第四章 树和二叉树

树的结构定义和基本操作、二叉树的定义、二叉树的性质、二叉树的存储结构、遍历二叉树，树和森林、树的存储结构、森林与二叉树的转换、树的遍历，最优二叉树和哈夫曼编码。

（1）了解树的定义和二叉树的定义。

（2）理解二叉树的性质、二叉树的存储结构。

（3）掌握遍历二叉树的方法、森林与二叉树的转换、最优二叉树的构造和哈夫曼编码。

（4）会利用二叉树的先根、中根和后根遍历解决有关二叉树的应用问题，会采用二叉链表存储结构编写与二叉树简单递归的算法。

第五章 图

图的定义和术语、图的存储结构：邻接矩阵和邻接表，图的遍历：深度优先搜索和广度优先搜索，无向网的最小生成树，有向网的最短路径。

（1）了解图的定义和术语，生成树和最小生成树、最短路径的概念。

（2）理解邻接矩阵中元素的含义和邻接表中结点的含义。

（3）掌握深度优先搜索和广度优先搜索算法思想。

（4）会用Prim算法和Kruskal算法手工构造无向网的最小生成树，会找出有向网任意顶点间的最短路径。

第六章 查找

静态查找表：顺序查找、二分查找和分块查找；动态查找表：二叉排序树；哈希查找、哈希函数的构造方法和处理冲突的方法

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

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

（3）掌握哈希函数的构造方法和处理冲突的方法，会用哈希函数、加上开放地址法或拉链法建立哈希表。

第七章 内部排序

直接插入排序、希尔排序、快速排序、简单选择排序、堆排序、归并排序和基数排序。各种内部排序方法的比较。

（1）了解排序算法的稳定性问题。

（2）理解直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序和基数排序的基本思想。

（3）会写出排序执行过程，能够对各种排序算法进行分析比较。