科目编号：834                               科目名称：数据结构与程序设计

一、考试的总体要求

考试内容由两部分组成，数据结构（占90分）和程序设计（占60分）。

数据结构是计算机科学与技术、软件工程和网络工程等与计算机相关专业的专业基础课。该门课程的硕士研究生入学考试要求考生能够比较系统地理解数据结构的基本概念、基本原理和方法，掌握数据的逻辑结构、存储结构以及各种基本操作的实现；要求考生能够运用所学的基本原理和基本方法分析、判断和解决相关的理论问题和实际问题；要求考生能够对算法进行设计与分析并选择适当的数据结构和方法进行问题求解。程序设计指采用C语言，应用数据结构的相关知识进行程序设计，要求考生掌握基本的程序设计方法，掌握C语言的基本概念、语法及编程方法等。

二、考试的内容及比例

1.数据结构考试的内容包括（占90分）：

 ①线性表、顺序表以及链表的定义、特点、存储结构及相关的基本算法。

 ②栈的定义、特点、顺序与链式存储表示、基本算法；栈的应用；队列的定义、特点；链队列、循环队列相关的定义、特点、基本算法；栈与递归的实现。

 ③广义表的定义及存储结构。

 ④二叉树的定义、性质及存储结构；遍历二叉树定义、过程及其算法；二叉树的应用；树、森林与二叉数之间的转换；哈夫曼树及其应用；与二叉树应用相关的递归算法。

 ⑤图的定义、存储结构；图的遍历过程及算法；最小生成树构造过程及算法；拓扑排序过程及算法；关键路径相关内容；最短路径相关内容；与图应用相关的递归算法。

 ⑥静态表查找过程及算法、动态表查找过程及算法；哈希表的构造及处理冲突方法。

 ⑦插入排序、快速排序、选择排序、归并排序、基数排序等内部排序的特点、过程及算法。

2.程序设计考试的内容包括（占60分）：

 ①熟练运用常量与变量；熟练运用各种数据类型；掌握变量赋初值、算术运算符及表达式、关系运算符及表达式和逻辑运算符和表达式求解，并能够在程序设计中正确使用；字符数据的输入与输出函数、格式输入与输出函数。

 ②基本控制结构：顺序、选择、循环语句的应用和编程。考生应能够编写简单的顺序结构程序、分支结构程序和循环结构程序；掌握计数型循环（如for循环）和条件型循环（如while、do-while循环等）的执行；要求能够编写带有循环结构的程序。

 ③基本的编程方法和程序设计技巧（穷举法、迭代法、递归法以及回溯法等）。

 ④模块化编程方法（函数的定义、调用，函数参数，函数的重载及标识符的作用域等）。 

 ⑤结构化程序设计方法的应用等。

 ⑥组织数据的能力（能够根据具体的问题设计合适的数据结构和数据类型，并能求解问题）。

 ⑦算法的描述工具（流程图、N-S图等）。

三、试卷的题型及比例

试卷分为数据结构、程序设计两部分，总分150分。

数据结构（90分）试题类型包括：填空题、选择题、判断题、综合应用题等。

程序设计（60分）试题类型包括：基本理论与概念、程序填空题、读程序写运算结果以及程序设计题等。

四、考试形式及时间

1. 考试形式：闭卷笔试。

2. 考试时间：3个小时。

五、主要参考教材

 1. 严蔚敏，《数据结构（C语言版）》，清华大学出版社，2013年。

 2. 谭浩强，《C程序设计》（第四版），清华大学出版社，2010年。

 3. 羊四清，《C语言程序设计》，中国水利水电出版社，2012年

 4. 李云清，《数据结构（C语言版）》，人民邮电出版社，2014年。