科目代码

831

科目类别

初 试

满分

150

命题方式

招生单位自命题

考试时间：

由全国硕士研究生招生考试初试时间统一确定

考试方式和考试总时长：

闭卷，笔试，考试时间为3个小时

试卷结构：

选择题、判断题、简答题、应用题、算法设计与分析、读程序写结果和程序设计题。

考试内容和要求：

一、考试说明

科目名称：数据结构与c语言程序设计

“数据结构与C语言程序设计”考试内容包括“数据结构”与“C语言程序设计”两门课程的内容。试卷满分为150分，“数据结构”90分，占比60%，“C语言程序设计”60分，占40%。

二、考试总体要求

“数据结构”要求掌握数据结构的基本术语，线性表、栈和队列、串、数组、树和二叉树、图等几种基本数据结构的特点、存储结构、基本操作以及在计算机科学中最基本的应用；掌握常用的排序与查找的方法；了解对算法的时间复杂度分析技术。要求考生能对给定的实际问题，建立准确的问题模型，选择合理的数据结构及其运算集，设计有效的算法。

“C语言程序设计”要求掌握C语言的基本程序结构、函数、数组、结构体、指针、文件等基本知识和程序设计方法。要求学生能对给定的实际问题，学会用计算机处理问题的思维方法，具有解决问题的编程能力。

三、考试内容

（一）数据结构

1、绪论

1）理解数据结构、逻辑结构、存储结构和抽象数据类型的基本概念；

2）掌握算法的时间复杂度和空间复杂度的概念和分析方法。

2、线性表

1）线性表的概念、逻辑结构特性以及两种存储结构特性

2）线性表的顺序存储和基本运算（查找、插入和删除）的实现

3）线性表的链式存储和基本运算（查找、插入和删除）的实现

4）线性表的应用

3、栈和队列

1）栈和队列的定义

2）栈的实现

（1）栈的顺序存储和基本操作（入栈、出栈和判栈空、栈满）的实现

（2）栈的链式存储和基本操作（入栈、出栈和判栈空）的实现

3）队列的实现

（1）队列的链式存储和基本操作（入队、出队和判队空）的实现

（2）循环队列的定义和基本操作（入队、出队和判队空、队满）的实现

4）栈和队列的应用

４、串

1）串的基本概念

2）串的顺序存储结构及各种基本运算

3）串的链式存储结构及各种基本运算

3）串的应用（串的模式匹配）

５、数组和广义表

1）数组的存储表示方法和地址计算方法

2）稀疏矩阵和特殊矩阵（对称矩阵、三角矩阵、对角矩阵）的压缩存储

3）广义表的定义和特性

6、树与二叉树

1）树的基本概念

2）二叉树

（1）二叉树的定义及性质

（2）二叉树的顺序存储和链式存储

（3）二叉树的各种遍历算法（先序、中序、后序遍历和层序遍历）

（4）线索二叉树的定义

3）二叉树与树、森林之间的转换，树和森林的遍历操作

4）二叉树的应用：哈夫曼（Huffman）树和哈夫曼编码

7、图

1）图的基本概念和性质

2）图的存储存储结构

（1）邻接矩阵表示法

（2）邻接表表示法

3）图的深度优先搜索和广度优先搜索方法及其实现

4）图的应用

（1）最小（代价）生成树求解方法（Prim算法和Kruskal算法）

（2）最短路径求解方法（Dijkstra算法）

（3）AOV-网、拓扑排序及关键路径

8、查找

1）查找的基本概念

2）顺序查找算法及平均查找长度计算

3）折半查找法、折半查找判定树的构造及平均查找长度计算

4）动态查找表

（1）二叉查找树（也称为二叉排序树）的构造及查找、插入和删除运算

（2）平衡二叉树及其构造

5）哈希表

（1）哈希表的构造及查找运算（解决冲突的开放地址法与链地址法）

（2）平均查找长度计算

9、内部排序

1）插入类排序算法（直接插入排序，希尔排序）

2）交换类排序算法（冒泡排序，快速排序）

3）选择类排序算法（简单选择排序，堆排序）

4）归并排序和基数排序算法

5）内部排序方法的比较和应用

（二）C语言程序设计

1、C语言基础及基本控制结构

（1）C语言数据类型、变量与常量、表达式等的基本知识

（2）顺序控制结构的程序设计

（2）分支控制结构的程序设计

（3）关系表达式和逻辑表达式的表示与应用

（4）FOR、WHILE、DO-WHILE等循环控制结构的程序设计，包括循环嵌套、break语句与continue语句

2、函数

（1）函数原型与函数声明，标准库函数的应用

（2）函数的定义与声明

（3）函数调用，参数传递方式，递归调用

（4）变量的作用域和生存期

3、数组和结构体

（1）一维数组和二维数组的定义、初始化和使用

（2）字符数组的定义与初始化，字符数组与字符串，字符串运算函数

（3）结构体类型的定义，结构体变量的定义和引用

（4）结构体数组的定义和使用。

4、编译预处理

（1）预处理指令的基本概念，文件包含和条件包含预处理指令

（2）宏替换，带参数的宏

5、指针

（1）指针的基本概念，包括定义、使用、指针变量作为函数参数和函数返回值以及函数指针

（2）数组与指针，包括指向数组的指针变量的定义与赋值、通过指针引用数组元素、数组名作为函数参数

（3）字符串与指针，指向字符串的指针变量

（4）指针与函数：函数参数为指针和数组，函数返回值为指针，函数指针

6、输入输出

（1）文件的基本概念，包括文件类型指针FILE与文件的使用方式

（2）文件的打开函数fopen与关闭函数fclose

（3）文件的状态，包括feof函数和ferror函数；

（4）文件的读/写，包括fread和fwrite函数、fputc和fgetc函数、fgets与fputs函数的应用；

（5）文件的输入函数fscanf和输出函数fprintf的应用；

参考书目：

①《数据结构(C 语言版)》，严蔚敏、吴伟民 ，清华大学出版社。（ISBN：9787302147510）

②《C程序设计教程（第3版）》，谭浩强，清华大学出版社。（ISBN： 9787302503828）

备注：