语言程序设计和数据结构.docx

湖南师范大学硕士研究生入学考试自命题考试大纲考试科目代码：967 考试科目名称：C语言程序设计和数据结构一、试卷结构1) 试卷成绩及考试时间本试卷满分为150分，考试时间为180分钟。2)答题方式：闭卷、笔试3)试卷内容结构C语言程序设计部分 80% 数据结构部分 20%4)题型结构a: 单项选择题，共40分b: 程序填空题，共30分c: 程序阅读题，共25分d: 编程题，共45分e: 分析题，共10分二、考试内容与考试要求（一）C语言程序设计部分考试内容1、基本知识（1）C语言的数据类型（2）C语言中各种类型常量的表示法（3）各类数值型数据间的混合运算（4）C运算符（5）关系表达式及运算，逻辑表达式及运算2、顺序、选择与循环结构（1）赋值语句，格式输入与输出（2）if语句，switch语句（3）goto、while、do-while、for、break、continue语句3、数组（1）一维数组的定义和引用（2）二维数组的定义和引用（3）字符数组的定义和引用，字符串及其处理函数4、函数（1）函数定义与调用（2）局部变量和全局变量（3）变量的存储类型（4）内部函数与外部函数5、宏定义（1）带参数的宏定义（2）包含文件的处理6、指针（1）地址和指针的概念（2）数组的指针和指向数组的指针变量（3）字符串的指针和指向字符串的指针变量（4）函数的指针和指向函数的指针变量（5）指针数组和指向指针的数组7、结构体和共同体（1）结构体变量的定义和使用方法（2）指向结构体类型变量的指针（3）用指针处理链表（4）共同体变量的定义和使用方法（5）枚举类型8、位运算（1）位运算符和位运算（2）位段9、文件（1）文件类型指针（2）文件操作，包括打开、关闭、读写和定位等考试要求1、掌握C语言的基本数据类型、各种运算符和表达式。2、掌握C语言的基本控制结构。3、掌握数组的定义、数组元素的引用、数组的初始化，掌握与字符串相关的库函数。4、掌握函数的定义语法，掌握函数调用中参数的传递机制；掌握局部变量和全局变量的有效范围，掌握auto、static、register、extern变量的概念及特性。5、掌握无参数和有参数的宏定义，掌握文件包含的使用。6、掌握结构体类型变量的定义、结构体变量的引用、结构体变量的初始化方法，掌握结构体数组的定义、初始化和结构体数组的应用，掌握共同体变量的定义和使用方法，掌握枚举类型的一般概念、定义格式及使用方法。7、掌握地址和指针的基本概念，重点掌握如何使用指针来处理数组、字符串以及结构体， 掌握函数指针的基本概念以及使用。8、了解位运算符的使用方法，能利用它们处理具体问题；了解位段的概念及使用规则。9、掌握FILE的定义以及对文件进行的各种操作的库函数。（二）数据结构部分考试内容1、绪论（1）数据结构的基本概念，数据的逻辑结构、存储结构。（2）算法的定义、算法的基本特性以及算法分析的基本概念。2、线性表（1）线性关系、线性表的定义，线性表的基本操作。（2）线性表的顺序存储结构与链式存储结构(包括单链表、循环链表和双向链表)的构造原理。在以上两种存储结构上对线性表实施的最主要的操作(包括三种链表的建立、插入和删除、检索等)的算法设计。3、堆栈与队列（1）堆栈与队列的基本概念、基本操作。（2）堆栈与队列的顺序存储结构与链式存储结构的构造原理。（3）在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作对应的算法设计。4、串（1）串的基本概念、串的基本操作和存储结构。（2）串的模式匹配算法和改进的KMP算法5、数组和广义表（1）数组的概念、多维数组的实现（2）对称矩阵和稀疏矩阵的压缩存储（3）广义表的基本概念6、树与二叉树（1）树的定义和性质（2）二叉树的概念、性质和实现（3）遍历二叉树和线索二叉树（4）树和森林（5）赫夫曼树及其应用（6）树的计数7、图（1）图的定义，基本概念，图的分类，常用名词术语。（2）图的邻接矩阵存储方法、邻接表存储方法的构造原理。（3）图的遍历操作。（4）最小生成树，最短路径，AOV网与拓扑排序。8、文件及查找（1）数据文件的基本概念和基本术语，数据文件的基本操作。（2）顺序文件、索引文件、散列(Hash)文件。（3）顺序文件的顺序查找方法、排序连续顺序文件的折半查找方法以及其他文件的基本查找方法。9、内排序（1）排序的基本概念，排序方法的分类。（2）插入排序法(含折半插入排序法)、选择排序法、泡排序法、快速排序法、堆积排序法、归并排序、基数排序。各种排序方法排序的原理、规律和特点，各种排序算法的时空复杂度简单分析。考试要求1、掌握有关数据结构的基本概念，包括数据的逻辑结构、存储结构。2、掌握算法的基本概念以及算法分析的基本方法。3、掌握线性表的基本概念，在两种存储结构下的构造原理及相应的操作；4、掌握堆栈和队列的基本概念与特征以及在两种存储结构下如何对堆栈和队列进行插入和删除等操作，具备使用堆栈与队列解决实际问题的能力。5、掌握串的基本概念以及串的存储结构和相关的算法。6、掌握数组、广义表和稀疏矩阵的基本概念以及基本操作。7、掌握树型结构的逻辑特征以及各种存储结构的构造原理，能够熟练使用基于树的三种遍历方法。8、掌握二叉排序树的逻辑特征、建立过程，具备使用其解决实际问题的能力。9、了解图的逻辑结构的特点以及常用的两种存储方法，了解最小生成树(Prim算法和Kruskal算法)、最短路径、拓扑排序的求解过程。10、掌握各种顺序文件的结构与相应的查找方法以及各种查找算法之间时空效率的差异；了解散列文件的建立、散列函数的选择(构造)原则、处理散列冲突的方法以及了解散列文件的建立、散列函数的选择(构造)原则、处理散列冲突的方法以及基于散列的查找。11、掌握各种排序方法的排序特点和排序过程，能够对每一种排序方法在时间、空间、排序的稳定性等方面进行简单分析。三、参考书目1 谭浩强. C程序设计（第四版）. 清华大学出版社. 20102 严蔚敏, 吴伟民. 数据结构（C语言版）. 清华大学出版社. 2011