甘肃民族师范学院2020年普通高职(专科)升本科考试计算机科学与技术专业考试大纲

一、考试目的

计算机科学与技术专业考试内容包括两部分：《C语言程序设计》与《数据结构》。考试目的是测试考生对于《C语言程序设计》和《数据结构》两门课程的基本知识掌握程度是否达到教学大纲所规定的要求。是否具有应用计算机解决和处理实际问题的思维方法与基本能力。

二、考试内容

(一)C语言程序设计

第一章 C语言基础知识

1.知识点：C语言基本结构、常量与变量、基本数据类型、运算符及其表达式、C语句、标准格式化输入输出函数、宏定义

2.考核要求：了解C语言发展史;理解程序代码执行过程及编写格式规范化要求;掌握符号常量的定义与应用;掌握不同数据类型常量取值范围、变量定义与应用;掌握运算符优先级和结合方向及其对应表达式的应用;掌握格式化输入输出函数的应用。

第二章 程序设计三大结构

1.知识点：顺序结构、选择结构(if/switch语句)、循环结构(for/while/do-while语句)、break语句、continue语句、复合语句。

2.考核要求：了解三大程序设计结构特点和应用;掌握常用算术库函数的应用;掌握if语句中单分支和双分支及复合语句的应用;掌握switch语句语法及多分支结构的编程方法;掌握三种循环语句语法及嵌套循环结构的应用;掌握break和continue语句的应用。

第三章 数组及其应用

1.知识点：　一维数组、二维数组、顺序查找、排序(冒泡、选择)、统计

2.考核要求：掌握一维数组定义、初始化和输入输出操作;掌握一维数组应用(查找、统计、排序);掌握二维数组定义、初始化和输入输出操作;掌握二维数组应用(矩阵基本操作);

第四章 字符串操作

1.知识点：字符串、字符数组、字符串库函数

2.考核要求：理解字符串与字符数组区别与联系;掌握字符串读写操作(gets/puts函数，%s格式控制符);掌握处理字符串操作库函数的实现与应用;掌握有关字符串特殊应用。

第五章 函数及其应用

1.知识点：函数、局部变量、全局变量、变量的存储类别

2.考核要求：深层次了解C语言基本结构和执行过程;了解函数递归调用;理解形参、实参定义与应用;理解局部变量和全局变量的使用;掌握程序调试简单操作;理解变量的存储类别;掌握自定义函数申明、实现和调用。

第六章 结构体、共用体和枚举类型

1.知识点：结构体、共用体、枚举类型

2.考核要求：了解共用体和枚举类型定义和简单操作;掌握结构体类型申明;掌握结构体变量定义、初始化、赋值和读写操作;掌握结构体数组的应用。

第七章 指针及其应用

1.知识点：指针变量、指向变量的指针、指向数组的指针、指向字符串的指针

2.考核要求：了解指针与地址的概念;理解指针变量与指向变量的指针之间区别与联系;掌握运用指向一维数组的指针对一维数组进行操作;掌握运用指向字符串的指针对字符串进行操作。

第八章 文件读写操作

1.知识点：文件类型、文件的指针、文件的读写、文件基本操作库函数

2.考核要求：了解文件类型定义;理解文件指针概念;掌握文件的打开与关闭操作;掌握文件简单的读写操作(fread/fwrite);掌握文件操作常用库函数(如feof()等)的应用。

(二)数据结构

第一章 绪论

1.知识点：数据结构基本概念和术语、算法、算法的描述和算法分析。

2.考核要求：了解非数值问题的数学模型;理解数据、数据元素、数据对象、数据结构和数据类型等的定义;掌握数据的逻辑结构和存储结构及其种类、算法的重要特征等;会根据语句的最大频度计算算法的时间复杂度的方法。

第二章 线性表

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

2.考核要求：了解线性表的定义和线性结构的特点;理解线性表的顺序存储和链式存储，理解数组与单链表表示表的优缺点;掌握线性顺序表中数据元素的存储位置的计算，顺序表、单向链表、循环链表和双向链表的插入、删除等有关操作;)会用单链表编写插入、删除等有关算法;能够从时间和空间复杂度的角度综合比较两存储结构的特点及适用场合。

第三章 栈和队列

1.知识点：栈的定义、栈的表示和实现;队列的定义、队列的表示和实现，链队列、循环队列。

2.考核要求：了解栈和队列的定义;理解线性表、栈和队列特点及区别，栈对实现递归过程的作用;掌握顺序栈、链栈的入栈和出栈操作，顺序队列、链队列的入队和出队操作，循环队列的队空和队满的判断;会编写入栈和出栈，入队和出队的有关算法。

第四章 串

1.知识点：串的有关定义、串的逻辑结构、静态存储结构、动态存储结构和串的基本操作。

2.考核要求：了解串的有关定义;理解串的逻辑结构和物理存储结构;了解串的模式匹配传统方法。

第五章 数组和广义表

1.知识点：数组的定义和运算、数组的顺序存储结构、特殊矩阵、稀疏矩阵的定义、矩阵的压缩存储、广义表的定义、广义表的存储结构。

2.考核要求：了解数组、特殊矩阵和稀疏矩阵的定义、广义表的概念和链表表示;理解矩阵的压缩存储的概念;掌握矩阵的压缩存储的有关计算方法;掌握一种广义表的链式储方法。

第六章 树和二叉树

1.知识点：树的结构定义和基本操作、二叉树的定义，性质，存储结构和遍历二叉树、线索二叉树;树和森林、树的存储结构、森林与二叉树的转换、树的遍历;最优二叉树和哈夫曼编码。

2.考核要求：了解树的定义和二叉树的定义;理解二叉树的性质、二叉树的存储结构;掌握遍历二叉树的方法、线索二叉树的构造、森林与二叉树的转换，最优二叉树和哈夫曼编码;会利用二叉树的先根、中根和后根遍历解决有关二叉树的应用问题、会编写与二叉树有关的算法。

第七章 图

1.知识点：图的定义和术语、图的存储结构：邻接矩阵和邻接表，图的遍历;深度优先搜索和广度优先搜索、无向图的连通分量和生成树、最小生成树、拓扑排序。

2.考核要求：了解图的定义和术语，生成树和最小生成树的概念;理解邻接矩阵中元素的含义和邻接表中结点的含义;理解深度优先搜索和广度优先搜索算法;会用Prim算法和Kruskal算法构造最小生成树，会找出图中顶点的拓扑序列等。

第八章 查找

1.知识点：静态查找表、顺序查找、二分查找和分块查找、动态查找表、二叉排序树和平衡二叉树、哈希查找、哈希函数的构造方法和处理冲突的方法。

2、考核要求：了解顺序查找、二分查找和分块查找、二叉排序树和平衡二叉树、哈希查找等的概念;理解顺序查找、二分查找和分块查找算法，二叉排序树的性质;掌握哈希函数的构造方法和处理冲突的方法;了解平衡二叉树的查找、插入和删除操作算法，相关查找方法的ASL;会用哈希函数、开放地址法或拉链法建立散列表。

第九章 内部排序

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

2.考核要求：了解排序算法的稳定性问题;理解直接插入排序、希尔排序、快速排序、简单选择排序、堆排序、归并排序和基数排序的基本思想;掌握直接插入排序、希尔排序、快速排序、简单选择排序、堆排序、归并排序的算法和时间分析;会用希尔排序、快速排序、堆排序、二路归并排序方法写出每趟排序的结果;会编写与直接插入排序和简单选择排序有关的算法。

三、试题难易程度

较容易题 约30%

中等难度题 约50%

较难题 约20%

四、说明

试卷满分为200分，《C语言程序设计》和《数据结构》各为100分。考试时间为120分钟。

五、参考书目

1.《C语言程序设计》(第3版)，苏小红，王宇颖，孙志岗，高等教育出版社， 2018年10月。

2. 《数据结构》(第2版)，严蔚敏，李冬梅，吴伟民，人民邮电出版社，2017年8月。