科目名称：数据结构与C程序设计 编号：831
一、考试性质
数据结构与C程序设计考试是招收硕士研究生的入学考试科目，目的是公平、有效地测试本专业和跨专业学生的基本知识、基本理论，以及运用数据结构基本原理与程序设计方法分析解决实际控制工程问题的能力，评价的标准是本科毕业生能达到的及格或及格以上水平，以保证被录取者具有基本的控制工程知识和素养，并有利于我校在硕士研究生录取中能进行择优选拔。
二、评价目标
数据结构与C程序设计课程考试包括数据结构基本概念、线性表、栈与队列、数组与广义表、树、图、查找、排序以及相关结构算法的C程序实现等内容。要求考生：
1.准确、恰当地使用本学科的专业术语，正确理解和掌握学科的有关原理、方法和工具。
2.能够运用有关原理、方法和工具，分析和设计数据结构。
3.能够运用所学的C程序设计方法实现数据结构及相关算法。
三、考试形式和试卷结构
1.试卷满分及考试时间
本试卷满分为150 分，考试时间为 180 分钟
2.答题方式
答题方式为闭卷，笔试。
3.试卷题型结构
选择题 10分(共5题，每题2分)
名词解释 40分(共10 题，每题4分)
简答题 50分(共5题，每题10分)
综合设计题 50分(共2题，每题25分)
4.试卷内容结构
数据结构基本概念、算法特点与分析:约10分
线性表表示与实现：约15分
栈和队列的表示与实现：约20分
数组与广义表的表示与实现：约15分
树和二叉树的表示与实现：约20分
图的表示与实现：约20分
查找算法分析：约25分
内部排序算法分析：约25分
四、考试内容
一、数据结构基本概念、算法特点与分析
1. 数据、数据结构概念，数据结构分类。
2. 算法定义及特性、算法效率的度量。
二、线性表表示与实现
1. 线性表概念。
2. 线性表的顺序表示和实现。
3. 线性表的链式表示和实现
三、栈和队列的表示与实现
1. 栈、队列概念。
2. 栈的表示和实现。
3. 队列表示和实现
4. 栈和队列的应用
四、数组与广义表的表示与实现
1. 数组、广义表的定义。
2. 数组的顺序表示与实现。
3. 矩阵的压缩存储。
4. 广义表的存储结构。
五、树与二叉树
1. 树与二叉树的定义。
2. 二叉树性质与存储结构。
3. 二叉树的遍历。
4. 树和森林存储结构与遍历。
5. 赫夫曼树及其应用。
六、图
1. 图的定义与基本概念。
2. 图的存储结构。
3. 图的遍历方法。
4. 拓扑排序与关键路径。
七、查找
1. 静态表查找(顺序表、有序表)。
2. 动态表查找(二叉排序树、平衡二叉树、B-树)
3. 哈希表查找(哈希函数构造、冲突处理方法，哈希表查找分析)
八、排序(内部排序)
1. 插入排序方法分析。
2. 快速排序方法分析。
3. 选择排序方法分析。
4. 归并排序方法分析
5. 各种排序方法比较
