硕士研究生入学考试《数据结构与算法》考试概要电子信息专业硕士

说明：数据结构与算法使用C语言进行考察，考试将分别考察C语言程序设计能力和数据结构两部分内容。

1、C语言程序设计

1、报考条件：

（1） 学会C语言语法及其特征；

（2） 学会顺序结构、选择结构、循环结构程序设计的基本办法，能运用结构化程序设计办法撰写程序；

（3） 学会C语言常用库函数（包含文件操作函数）的用法，与用户函数的概念，调用参数传递的办法；

（4） 可以运用指针、递归和结构体等达成基本数据结构和常用算法；

（5） 学会阅读和剖析程序的办法和方法与程序开发与调试技术。

2、考试内容：

（1） 概述

C程序的特征、算法性能剖析与度量。

（2） 算法

算法概述、算法的表示办法、结构化程序设计办法。

（3） 数据种类、运算符与表达式

C语言数据种类、常量与变量、整型数据、实型数据、字符型数据、变量赋初值、变量种类转换、算术运算符和算术表达式、赋值运算符和赋值表达式、逗号运算符和逗号表达式。

（4） 顺序结构

数据输入、数据输出、顺序程序设计。

（5） 选择结构

关系运算与关系表达式、逻辑运算与逻辑表达式、if语句、switch语句。

（6） 循环结构

while语句达成循环、do-while语句达成循环、for语句达成循环、循环的嵌套、几种循环形式的关系和比较、break语句和continue语句。

（7） 数组

一维数组的概念和应用、二维数组的概念和应用、字符数组的概念和应用。

（8） 函数

函数的概念、函数的调用、函数的嵌套调用、函数的递归调用、数组作为函数参数、局部变量与全局变量、变量的存储方法和存活期等。

（9） 指针

地址和指针的定义、变量的指针和指向变量的指针变量、数组的指针和指向数组的指针变量、字符串的指针和指向字符串的指针变量、函数的指针和指向函数的指针变量、返回指针值的函数、指针数组、指向指针的指针、动态内存分配与指向它的指针变量等。

（10） 结构体及应用

概念和用结构体变量、结构体数组及应用、结构体指针及应用、用指针处置链表、共用体种类、枚举种类、用typedef声明新种类名。

（11） 文件

文件的定义、文件种类指针、文件的打开与关闭、文件的读写。

2、数据结构

1、报考条件：

（1） 学会各类型型的数据结构（包含线性表、栈、队列、串、数组、树和二叉树、图等）的概念、表示和达成；

（2） 学会设计算法的步骤和剖析办法；

（3） 学会排序、查找、遍历、创建、插入、删除等常用算法的应用。

2、考试内容：

（1） 绪论

数据结构的定义、基本术语；算法描述及算法剖析。

（2） 线性表

线性表的概念及基本运算；线性表的顺序存储结构；线性表的链式存储结构。

（3） 栈和队列

栈的概念、表示和达成，栈的应用（表达式计算、递归算法设计）；队列的概念、表示和达成，队列的应用。

（4） 串

串的概念、表示与达成；串的模式匹配算法。

（5） 数组

数组的概念和运算；数组的顺序存储结构；矩阵的压缩存储。

（6） 树和二叉树

树的基本定义；二叉树的概念、性质及存储结构；遍历二叉树和线索二叉树；树和森林（树的存储结构，树、森林与二叉树的相互转换，树和森林的遍历）；哈夫曼树及其应用。

（7） 图

图的基本定义；图的存储结构（邻接矩阵、邻接表）；图的遍历；图的应用（最小生成树、最短路径、拓扑排序、重点路径）。

（8） 查找

查找的基本定义；静态查找表的查找（顺序、折半、索引顺序查找）；动态查找表的查找（二叉排序树、平衡二叉树、B-树和B+树）；哈希表的架构及查找；查找算法的效率剖析。

（9） 排序

排序的基本定义；插入排序（直接插入、折半插入、希尔排序）、选择排序（直接选择、堆排序）、交换排序（冒泡排序、迅速排序）、归并排序、基数排序；各种内部排序算法的比较；外部排序的办法。

参考资料： 《数据结构（C语言版）》，严蔚敏 吴伟民 著，清华大学出版社