北华航天工业学院
硕士研究生招生初试科目考试大纲
—————————————————————————————
科目代码、名称： 804《C语言程序设计与数据结构》
编制单位： 计算机学院
—————————————————————————————
一、考试总体要求
本考试大纲适用于报考我校计算机学院电子信息专业的硕士研究生入学考试。主要涵盖《C语言程序设计》和《数据结构》两门课程的内容，所占的比例为40%和60%。
《C语言程序设计》课程的考试目标是要求学生掌握C语言基本知识;熟练掌握结构化程序设计的方法，形成良好的程序设计风格;掌握程序设计中基本的数据结构和算法，达到训练学生的逻辑思维能力的目的。
《数据结构》课程的考试目标是要求考生比较系统地理解数据结构的基本概念、基本原理和方法，掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。能够对算法进行设计与分析，能够选择合适的数据结构和方法进行问题求解。
二、考试形式与试卷结构
1.考试形式：闭卷、笔试，答题时间180分钟，满分150分。
2.试卷结构与题型：选择题、填空题、阅读程序题、应用题、算法设计题、程序设计题;除此之外还可能有简答题、改错题等。
三、考试内容及要求
《C语言程序设计》课程考试内容与要求
(一)C语言概述
1.了解C语言的特点及发展。
2.掌握程序的基本结构与书写格式。
3.掌握头文件、数据说明、函数的开始和结束标志。
(二)数据类型、运算符与表达式
1.掌握各种数据类型及其定义方法。
2.理解运算符的种类、运算优先级、结合性。
3.掌握不同类型数据间的转换与运算。
4.掌握表达式类型(赋值表达式、算术表达式、关系表达式、逻辑表达式、条件表达式、逗号表达式)和求值规则。
(三)顺序程序设计
1.理解表达式语句、空语句、复合语句以及赋值语句。
2.掌握数据的输入/输出和输入/输出函数。
(四)选择结构程序设计
1.熟练掌握if语句实现选择结构。
2.熟练掌握switch语句实现多分支选择结构。
(五)循环控制
1.熟练掌握for循环结构。
2.熟练掌握while和do-while循环结构。
3.掌握continue、break、return语句。
4.熟练掌握循环的嵌套。
(六)数组
1.掌握数组的定义和数组元素的引用方法及数组的初始化方法。
2.熟练掌握一维和二维数组的基本操作和基本算法。
3.熟练掌握字符数组的存储结构，字符串的输入/输出，对字符串进行处理的基本函数和对字符串进行处理的基本算法。
(七)函数
1.理解库函数的正确调用。
2.熟练掌握函数的定义方法。
3.掌握函数的类型和返回值。
4.掌握形式参数与实在参数的区别，参数值的传递。
5.理解函数的一般调用和嵌套调用，学会递归调用。
6.掌握局部变量和全局变量。
7.理解变量的存储类型(自动、静态、寄存器、外部)，变量的作用域和生存期。
8.了解内部函数和外部函数。
(八)预处理命令
1.理解编译预处理的概念和特点。
2.了解带参数的宏定义及其使用，了解不带参数的宏定义及其使用。
3.理解“文件包含”的概念和使用。
(九)指针
1.掌握指针的概念及指针的定义。
2.掌握指针运算。
3.掌握指向变量、数组、字符串、函数的指针变量。
4.熟练掌握用指针作函数参数。
5.掌握指针数组和指向指针数据的指针的概念及其定义方法。
6.掌握动态内存分配与指向它的指针变量。
(十)结构体与共用体
1.理解结构体类型和结构体变量。
2.掌握结构体数组和结构体指针。
3.了解运用指针处理链表。
4.理解共用体类型。
5.理解枚举类型。
(十一)文件
1.理解文件类型指针(file类型指针)。
2.掌握文件的打开与关闭(fopen和fclose函数)。
3.掌握文件的读与写(fprintf和fscanf函数)。
《数据结构》课程考试内容与要求
(一)概述
1.理解数据的逻辑结构与存储结构的基本概念。
2.理解算法定义、基本性质以及算法分析，包括时间复杂度和空间复杂度的计算。
(二)线性表
1.理解线性关系、线性表的定义，线性表的基本操作。
2.掌握线性表的顺序存储结构与链式存储结构(包括单链表、循环链表和双向链表)的构造原理。
3.熟练掌握在以上两种存储结构的基础上对线性表实施的基本操作，包括顺序表的插入与删除、链表的建立、插入与删除、查找等操作对应的算法设计。
4.掌握链表的常用应用。
(三)栈和队列
1.理解栈与队列的基本概念与基本操作。
2.掌握栈与队列的顺序存储结构与链式存储结构的构造原理。
3.熟练掌握在不同存储结构的基础上对栈与队列实施插入与删除等基本操作的算法设计。
4.掌握栈和队列在解决实际问题中应用。例如：递归过程、表达式求值、数制转换、迷宫、排队问题等。
(四)串、数组和广义表
1.理解串的基本概念及顺序和链式存储结构。
2.掌握串的模式匹配过程及算法设计。
3.掌握数组的顺序存储结构及地址计算。
4.理解特殊矩阵的压缩存储方法。
5.理解广义表的基本概念、存储结构。
(五)树与二叉树
1.理解树与二叉树的基本概念，名词术语。
2.掌握二叉树的基本性质和存储结构。
3.掌握二叉树与树、树林之间的转换。
4.熟悉掌握二叉树的遍历，包括递归和非递归算法。
5.掌握以二叉链表形式存储的二叉树遍历算法的应用。
6.掌握哈夫曼树的基本概念，哈夫曼树和哈夫曼编码的构造和算法设计。
(六)图
1.理解图的基本概念、名词术语。
2.掌握图的邻接矩阵存储方法和邻接表(含逆邻接表)存储方法的构造原理及特点。
3.熟练掌握图的深度优先搜索与广度优先搜索过程和算法设计。
4.掌握最小生成树和最短路径的构造和算法设计。
5.掌握AOV网与拓扑排序基本概念与求解过程。
(七)查找
1.掌握顺序查找、折半查找和分块查找的查找算法的设计与算法复杂性的分析过程。
2.掌握二叉排序树的概念、构造、基本操作及实现算法的设计。
3.掌握平衡二叉树的概念、构造、插入和删除过程。
4.掌握散列(Hash)表的构造、散列函数的构造、处理散列冲突的基本方法以及散列表的查找和平均查找长度的计算。
(八)内部排序
1.理解排序的基本概念，各种内排序方法的基本原理和特点，包括排序过程中进行的元素之间的比较次数，排序总趟数、排序稳定性以及时间复杂度与空间复杂度计算。
2.掌握直接插入排序、折半插入排序、选择排序;起泡排序、希尔排序法、快速排序、堆排序、二路归并排序、基数排序;
3.了解各种内部排序算法的应用。
四、参考书目
《C语言程序设计》 谭浩强 编 清华大学出版社
《数据结构(C语言版)》 严蔚敏 吴伟民主编 清华大学出版社
