2015年天津大学在职研究生软件工程复试考试大纲

　　考试科目：数据结构与程序设计

　　一、基本内容：

　　数据结构部分

　　【考查目标】

　　1、理解数据结构的概念；掌握各种常用数据结构及其基本操作的实现。

　　2、掌握基本的数据处理原理和方法；掌握使用基本数据结构的常用算法并能够对算法进行时间复杂度与空间复杂度分析。

　　3、能够选择合适的数据结构和方法进行问题求解，具备采用C或C++语言设计与实现算法的能力。

　　【考查内容】

　　（一）线性表

　　1、线性表的定义和基本操作

　　2、线性表的实现（1）顺序存储（2）链式存储

　　3、线性表的应用

　　（二）栈、队列

　　1、栈和队列的基本概念

　　2、栈和队列的顺序存储结构

　　3、栈和队列的链式存储结构

　　4、栈和队列的应用

　　5、递归的概念及应用

　　（三）字符串与数组

　　1、字符串的概念

　　2、字符串的模式匹配算法

　　3、数组的概念

　　4、特殊矩阵的压缩存储

　　5、稀疏矩阵的压缩存储

　　6、稀疏矩阵的转置

　　7、广义表的概念

　　（四）树与二叉树

　　1、树的基本概念

　　2、二叉树

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

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

　　（3）二叉树的遍历

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

　　3、树、森林

　　（1）树的存储结构

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

　　（3）树和森林的遍历

　　4、树与二叉树的应用

　　（1）哈夫曼（Huffman）树和哈夫曼编码

　　（五）图

　　1、图的基本概念

　　2、图的存储结构及基本操作（1）邻接矩阵法（2）邻接表法

　　3、图的遍历

　　（1）深度优先遍历（2）广度优先遍历

　　4、图的基本应用

　　（1）最小（代价）生成树（2）最短路径（3）拓扑排序（4）关键路径

　　（六）查找

　　1、查找的基本概念

　　2、顺序查找法

　　3、折半查找法

　　4、二叉排序树

　　5、平衡二叉树

　　6、B-树及其基本操作、B+树的基本概念

　　7、散列（哈希）表及其查找

　　8、查找算法的分析及应用

　　（七）排序

　　1、排序的基本概念

　　2、插入排序

　　（1）直接插入排序（2）折半插入排序

　　3、起泡排序

　　4、简单选择排序

　　5、希尔排序

　　6、快速排序

　　7、堆排序

　　8、二路归并排序

　　9、基数排序

　　10、各种内部排序算法的比较

　　11、内部排序算法的应用

　　程序设计部分

　　【考查目标】

　　1、掌握C++语言的基本语法规则。

　　2、掌握有关类与对象的相关知识。

　　3、能够阅读和分析C++程序。

　　4、能够采用面向对象的编程思路和方法编写应用程序。

　　【考查内容】

　　（一）C++语言概念

　　1、了解C++语言的基本符号。

　　2、了解C++语言的关键字、标识符、常量、运算符、标点符号等。

　　3、掌握C++程序的基本框架。

　　（二）数据类型、表达式和基本运算

　　1、掌握C++数据类型及其定义方法。

　　2、了解C++的常量定义。

　　3、掌握变量的定义与使用方法。

　　4、掌握C++运算符的种类、运算优先级和结合性。

　　5、熟练掌握C++表达式类型及求值规则。

　　（三）C++的基本语句

　　1、掌握C++的基本语句。

　　2、掌握分支结构、多分支选择结构、循环结构、转向及分支语句和循环语句的各种嵌套使用。

　　（四）数组、指针与引用

　　1、掌握数组的定义、初始化和访问。

　　2、了解字符串与字符数组。

　　3、掌握常用字符串函数。

　　4、指针与指针变量的概念,指针与地址运算符,指针与数组。

　　5、引用的基本概念,引用的定义与使用。

　　（五）掌握函数的有关使用

　　1、函数的定义方法和调用方法。

　　2、函数的类型和返回值。

　　3、形式参数与实际参数,参数值的传递。

　　4、变量的作用域和生存周期。

　　5、递归函数。

　　6、函数重载。

　　7、内联函数。

　　8、带有默认参数值的函数。

　　（六）熟练掌握类与对象的相关知识

　　1、类的定义方式、数据成员、成员函数及访问权限。

　　2、对象和对象指针的定义与使用。

　　3、构造函数与析构函数。

　　4、静态数据成员与静态成员函数的定义与使用方式。

　　5、常数据成员与常成员函数。

　　6、this指针的使用。

　　7、友元函数和友元类。

　　8、对象数组与成员对象。

　　（七）掌握类的继承与派生知识

　　1、派生类的定义和访问权限。

　　2、继承基类的数据成员与成员函数。

　　3、基类指针与派生类指针的使用。

　　4、虚基类。

　　5、子类型关系。

　　（八）了解多态性概念（九）模板

　　1、了解函数模板的定义和使用方式。

　　2、了解类模板的定义和使用方式。（十）输入输出流

　　1、掌握C++流的概念。

　　2、能够使用格式控制数据的输入输出。

　　3、掌握文件的I/O操作。

　　二、考试题型：

　　数据结构部分

　　1、选择题

　　2、实做题

　　3、算法设计题

　　程序设计部分

　　1、读程序写结果

　　2、程序填空

　　三、参考教材

　　[1]《数据结构（C语言版）》，严蔚敏，清华大学出版社，2011年[2]《C++程序设计（第2版）》，谭浩强，清华大学出版社，2011年