一、考试科目：数据结构与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 private
    2．访问特征
    派生类成员函数对基类成员的访问
    派生类对象对基类成员的访问
    派生类的派生类对基类成员的访问
    3．虚拟继承（共享继承）
    多继承时的二义性
    虚基类：在派生类对象中只有一份拷贝
    4．构造函数和析构函数的调用顺序
    Con：虚基类－非虚基类－成员对象类－派生类
    Des：以构造函数相反的顺序
    五、多态性（15%）
    1．多态性的概念
    2．多态性的分类
    编译时的多态性：采用静态联编
    运行时的多态性：采用动态联编
    3．静态联编：概念与常见形式
    4．运算符重载：“四不变”原则， 另外只能重载已有的运算符，而不能创造新的运算符；即将c++已有的运算符扩展到用户自定义类的类型上。
    ① 两种形式：成员函数与友元函数形式
    ② ++ --的重载，分前缀和后缀两种形式
    5．动态联编
    虚函数的概念与应用
    六、模板与I/O流类（20%）：
    1．模板引入的必要性
    函数模板
    类模板
    2．C++ I/O流类库
    标准I/O
    文件I/O
    字符串I/O
    参考书目：

《数据结构》 《C++面向对象程序设计教程》（第3版）

机械工业出版社 2008 清华大学出版社 2009年

戴敏 陈维兴

  购买考研专业课资料请点击：http://www.52kaoyan.com/Shop/