天津工业大学834数据结构与程序设计2017年大纲

天津工业大学834数据结构与程序设计2016年大纲

一、考试的总体要求

考试内容由两部分组成，数据结构（占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年。

一、考试的总体要求

《数据结构》是计算机科学与技术专业、软件工程专业和网络工程专业等计算机技术领域专业的专业基础课。

该课程考试要求考生比较系统地理解数据结构的基本概念、基本原理和方法，掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。能够对算法进行设计与分析，能够选择合适的数据结构和方法进行问题求解。

二、考试的内容及比例

（一）线性表

⒈ 线性表的定义和基本操作

⒉ 线性表的实现

（1）顺序存储结构

（2）链式存储结构

（3）线性表的应用

（二）栈、队列和数组

⒈ 栈和队列的基本概念

⒉ 栈和队列的顺序存储结构

⒊ 栈和队列的链式存储结构

⒋ 栈和队列的应用

⒌ 特殊矩阵的压缩存储

（三）树与二叉树

⒈ 树的基本概念

⒉ 二叉树

（1）二叉树的定义及其主要特征

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

（3）二叉树的遍历

（4）线索二叉树的基本概念和构造

⒊ 树、森林

（1）书的存储结构

（2）森林与二叉树的转换

（3）树和森林的遍历

⒋ 树与二叉树的应用

（1）二叉排序树

（2）平衡二叉树（3）哈夫曼树和哈夫曼编码

（四）图

⒈ 图的概念⒉ 图的存储及基本操作 （1）邻接矩阵法 （2）邻接表法 ⒊ 图的遍历 （1）深度优先搜索 （2）广度优先搜索 ⒋ 图的基本应用及其复杂度分析 （1）最小（代价）生成树 （2）最短路径

    （3）拓扑排序         （4）关键路径

（五）查找

 ⒈ 查找的基本概念  ⒉ 顺序查找法  ⒊ 有序表的查找方法

 ⒋ 二叉排序树和平衡二叉树

 ⒌ B-树  ⒍ 哈希表及其查找  ⒎ 查找算法的分析及应用

（六）内部排序  ⒈ 排序的基本概念  ⒉ 插入排序 （1）直接插入排序 （2）折半插入排序  ⒊ 起泡排序  ⒋ 简单选择排序  ⒌ 希尔排序  ⒍ 快速排序  ⒎ 堆排序  ⒏ 二路归并排序  ⒐ 基数排序  10. 各种内部排序算法的比较  1⒈ 内部排序算法的应用

三、试卷的题型及比例 (待定)

考试题型包括填空题（20分）、选择题（40分）、判断题（16分）、综合应用题（74分），满分150分。

四、考试形式及时间

考试形式为笔试，时间为3个小时。

五、主要参考教材

严蔚敏, 吴伟民主编，《数据结构 (C语言版)》（第三版），清华大学出版社，2007年。

变化情况：参考教材全换、更换、新增很多考试内容，各部分分值发生变化。