天津理工大学2017年硕士初试《数据结构与C++程序设计》考试大纲.pdf

天津理工大学2017年硕士初试 《数据结构与C++程序设计》考试大 纲 一、考试科目：数据结构与C++程序设计 （817） 二、考试方式： 考试采用笔试形式，考试时间为180分钟，试卷满分为150分。 三、试卷结构与分数比重： 题型包括填空题 （20%）、选择题 （20%）、算法或数据结构的设计与分析题 （30%）、程序分析题 （15%） 与编程题 （15%）等。 四、考查的知识范围： 《数据结构与C++程序设计》入学考试包括两部分内容：其中数据结构考试主要涉及线性结构、树、 图、查找表和排序，占75分；C++程序设计考试主要涉及支持面向对象程序设计的内容，同时兼顾C++支 持结构化程序设计的特征，占75分。本试卷总共150分，具体考试内容主要包括： 数据结构部分 一、绪论 （5%） 1．数据结构相关基本概念 2．逻辑结构和物理结构 3．算法效率的度量 （O－表示法） 二、线性表、栈和队列 （25%） （以下各点要求掌握算法的程序实现） 1．顺序表的表示和基本操作的实现算法 2．单链表、循环链表、双向链表的表示和和基本操作的实现算法 3．栈的表示和和基本操作的实现算法 4．循环队列、链队列的表示和和基本操作的实现算法 三、数组、递归 （5%） 1．数组的存储方式 2．特殊矩阵的压缩存储 3．递归思想的特点 4．递归算法和递归函数 四、树和二叉树 （20%） 1．树的定义和基本术语 2．二叉树的定义、性质，二叉链表存储结构 3．完全二叉树的性质 4．二叉树的深度优先 （先序、中序、后序）和广度优先 （层序）遍历算法和程序实现 5．树的存储结构 6．树、森林与二叉树的转换 7．霍夫曼树的定义、性质、构造方法 五、图 （10%） 1．图的定义和术语 2．图的邻接矩阵、邻接表存储结构 3．图的深度优先搜索、广度优先搜索及其算法实现 4．生成树的定义，图的最小生成树定义与构造方法 （不要求算法实现） 5．拓扑排序 六、查找 （25%） 1．平均搜索长度 （ASL）的定义 2．顺序表的查找算法、程序实现和ASL分析 3．二分查找法的算法描述、程序实现和ASL分析 4．索引顺序表的查找 （分块查找）方法和和ASL分析 5．二叉排序树的定义，插入、删除操作 6．平衡二叉树的定义，建立过程 （掌握4种旋转方法），计算等概率下查找成功的ASL和查找不成功 的ASL 7．B-树的定义 8．散列表的概念，几种常用散列函数的构造方法 9．散列表处理冲突的方法 （线性探查法、二次探查法、再散列法、链地址法），计算等概率下查找成 功的ASL和查找不成功的ASL 10．散列表负载因子 （装填因子）α的定义 七、排序 （10%） （以下每种排序算法要求掌握排序过程和程序实现） 1．直接插入排序、希尔排序 2．冒泡排序、快速排序 3．简单选择排序、堆排序 4．归并排序 5．基数排序 （箱排序） 6．以上各种排序算法的时间复杂度分析，各自的特征及其比较 C++程序设计部分 一、C++基础语法 （15%） 1．C++的字符集与词法规则 2．常见的数据类型 3．变量与常量 4．运算符的优先级和结合性 5．表达式的类型与计算顺序 6．语句：包括操作运算语句和流程控制语句 7．C++中的编译预处理 二、函数、指针、结构与联合 （15%） 1．函数定义/说明的格式 2．函数的参数和返回值 3．函数的调用机制 4．函数的参数传递方式 5．重载函数以及函数重载的原则 6．标识符的作用域与变量的存储类别 7．指针、引用与数组的概念和应用 三、类的封装性 （20%） 1．类的定义 2．构造函数与析构函数 3．隐含的this指针 4．类的静态成员 5．类的友元 6．指向类成员的指针 7．复杂对象与成分对象 8．类的常量成员 四、类的继承性 （15%） 1．基类与派生类 单继承与多继承 继承方式：public protected p