2014年黄冈师范学院普通专升本计算机科学与技术（专业综合）考试大纲
考试科目：C语言、数据结构
课程一：《C程序设计》考试大纲
一、总体要求：
1．了解高级程序设计语言的结构，掌握C语言的基本语法、基本的程序设计过程和技巧。
2．掌握基本的分析问题和利用计算机求解问题的能力，具备初步的高级语言程序设计能力。
二、考核知识点
1、数据定义
数据定义包括数据类型和存储类别
(1)基本类型
基本类型指整型、实型和字符型
① 常量
熟练掌握各种表示形式的整数、实数、字符常量和字符串常量，符号常量的定义和使用。
包括整数的十进制、八进制和十六进制的表示形式、长整型常量和无符号型常量的表示形式，实数的浮点表示法和科学记数法，字符的转义序列，常用符号常量的含义（如NULL、EOF等）
② 变量
熟练掌握变量的定义和初始化
(2)构造类型
构造类型包括数组和结构
① 数组
熟练掌握一维和二维数组的定义和初始化，数组元素的引用。
包括一维字符数组和字符串，二维字符数组和字符串数组
② 结构
熟练掌握结构类型的定义，结构变量的定义和初始化，结构变量成员的引用。
(3) 指针
① 熟练掌握指针和地址的概念
② 熟练掌握指针变量的定义和初始化
③ 熟练掌握通过指针引用指向实体
(4) 构造类型和指针类型的混合定义及应用
① 熟练掌握指针、数组和地址间的关系
② 熟练掌握指针数组
③ 熟练掌握结构数组
④ 熟练掌握结构指针
⑤ 掌握结构中含指针或数组
⑥ 掌握嵌套结构
⑦ 掌握指向指针的指针（二级）
⑧ 单向链表:掌握单向链表的建立和遍历,了解插入和删除单向链表中的一个节点
(5) 空类型
掌握空类型的定义和使用
(6) 变量的存储类别、作用域和生存期
① 掌握变量的存储类别
auto 自动型、static 静态型
② 掌握全局变量和局部变量
注意区分：自动局部变量和静态局部变量
2、运算及流程控制
(1)基本运算
包括算术运算（含自增、自减操作）、关系运算、逻辑运算、条件运算、赋值运算。
熟练掌握运算符的功能
熟练掌握运算符的优先级和结合方向
熟练掌握隐式类型转换和强制类型转换
(2)表达式
熟练掌握各类表达式的组成规则和计算过程
(3)语句
① 熟练掌握表达式语句、空语句、复合语句；
② 熟练掌握简单控制语句（break、continue、return）；
③ 熟练掌握选择控制语句(if、switch)
④ 熟练掌握重复控制语句(for、while、do—while);
3、程序结构和函数
(1)程序结构
熟练掌握main函数与其他函数之间的关系
包括标准库函数和自定义函数
(2)函数的定义
① 熟练掌握函数定义的ANSI C格式
② 熟练掌握函数的参数（形式参数和实在参数）及参数传递
包括指针作为函数的参数
③ 熟练掌握函数的返回值
(3)函数的调用
① 函数调用的一般格式
熟练掌握通过函数名调用函数
② 掌握函数的嵌套调用和递归调用
③ 熟练掌握标准库函数的调用
常用数学函数：cos、sqrt、pow、exp、fabs、log、log10等
常用字符函数：isalnum、isalpha、isdigit、islower、toupper等
常用字符串函数：strcpy、strcmp、strcat、strlen等
4、编译预处理和命令行参数
(1)熟练掌握编译预处理的基本概念
(2)掌握宏定义
(3)掌握文件包含
5、常用算法
以下算法针对本大纲中列出的各种数据结构
(1)分类（排序）算法
冒泡、选择、插入
(2)检索（查找）算法
① 无序数据序列的查找（见遍历算法）
② 有序数据序列的查找：二分法
(3)遍历算法
① 一维数组和二维数组的遍历
② 单向链表的遍历
(4)简单的数值计算方法：如多项式函数的计算
(5)其它基本算法：如进制转换
教材：C程序设计，谭浩强，清华大学出版社
试卷结构（C语言部分，100分）
试卷题型比例：
选择题 约40%
填空题 约30%
程序理解题 约30%
课程二：《数据结构》考试大纲
一、总体要求：
1、基本理论知识
(l)什么是数据结构、基本概念和基本术语，算法的描述和算法分析。
(2)什么是线性表、在线性表上常进行的基本操作以及这些操作分别在顺序存储和链式存储结构下的实现及复杂度分析。
(3)栈和队列的定义、表示方法和实现。
(4)串的定义及其基本操作。
(5)数组的定义、运算和存储、稀疏矩阵的压缩存储。
(6)树的定义、基本术语和存储结构，二叉树的定义和性质、二叉树的存储结构及其各种操作，哈夫曼树。
(7)图的定义和术语、图的存储结构及其各种操作。
(8)各种查找方法的算法、适用范围及时间复杂度的分析。
(9)多种内排算法的基本思想和算法的时间复杂度分析，不同排序方法的比较。
2、基本技能
(1)能阅读用类C语言编写的算法。
(2)能分析算法所完成的功能、运行结果和时间复杂度。
(3)能根据要求用类C语言编写算法。
二、考核知识点
1、绪论
(1)数据、数据元素、数据项、数据对象、数据结构、逻辑结构、物理结构、元素、结点等基本概念。抽象数据类型的定义、表示和实现方法。
(2)算法、算法的特性、如何用类C语言来描述算法。
(3)算法设计的基本要求以及计算语句频度和估算算法时间复杂度的方法。
2、线性表
(1)线性表的定义和操作。
(2)顺序存储线性表的实现和运算。
(3)链式存储线性表，带有附加表头结点和不带附加表头结点的单链表、循环链表和双向链表的实现和查找对插入、删除等基本操作。
3、栈和队列
(1)栈和队列的定义及其存储结构、循环队列。
(2)栈和队列的主要运算。
(3)栈的应用举例，如：数制转换、表达式求值等。
4、串
(1)串的定义、空串、空格串。
(2)串的基本操作。
(3)串的顺序存储结构及在顺序存储结构下基本操作的实现。
(4)串的模式匹配算法。
5、树和二叉树
(1)树的定义和术语。
(2)二叉树(完全二叉树、满二叉树)的定义和性质、二叉树的存储结构（顺序表示法和二叉链表表示法）。
(3)二叉树遍历的递归算法。
(4)树和森林转换为二叉树的方法。
6、图
(1)图的定义。
(2)图的基本术语。
①图及无向图、有向图、网、子图、连通图、强连通图。
②顶点的度、入度、出度。
③顶点间路径、路径长度、环。
(3)图的存储结构
①邻接矩阵
②邻接表(含逆邻接表)
(4)遍历图
①深度优先搜索遍历图的算法及其时间复杂度。
②广度优先搜索遍历图的思想及其时间复杂度。
(5)生成树
①生成树、最小生成树的概念。
②最小生成树的构造过程(Prim算法和Kruskal算法)及其时间复杂度。
(6)两类求最短路径问题的解法。
8、排序
(1)排序的目的、分类和排序方法的稳定性的定义。
(2)插入排序
①直接插入排序的算法。
②希尔排序的思想。
(3)选择排序
①简单的选择排序的算法。
③堆的定义、堆排序的思想。
(4)归并排序的思想。
(5)基数排序的思想及特点。
(6)各种内部排序方法的比较。
9、查找
(1)查找、关键字、平均查找长度等概念。
(2)静态查找表的查找算法及其效率(最坏和平均查找长度)。
①顺序查找
②分块查找
(3)动态查找表
①二叉排序树定义、构造过程及其查找算法和效率。
(4)哈希表
①哈希表的特点。
②构造哈希函数的方法（除留余数法等）。
③处理冲突的方法。
教材：《数据结构》（C语言版） 朱站立编著 西安交通大学出版社
试卷结构（数据结构部分，100分）
试卷题型比例：
选择题 约50%
填空题 约30%
计算分析算法题 约20%
