招生学院：计算机科学与技术 招生专业：计算机技术
科目名称：数据结构与C++
一、考试形式与试卷结构
(一)试卷满分值及考试时间
本试卷满分为150分，考试时间为180分钟。
(二)答题方式
答题方式为闭卷、笔试。试卷由试题和答题纸组成;答案必须写在答题纸(由考点提供)相应的位置上。
(三)试卷内容结构
考试内容主要包括数据结构(50%)，C++(50%)。
(四)试卷题型结构
第一部分 数据结构
1. 单项选择题(12分)，共8道;
2. 问答题(40分)，共5道;
3. 算法设计题(23分)，共2道。
第二部分 C++
1. 单项选择题(15分)，共10道;
2. 程序阅读题(30分)，共3-5道;
3. 编程题(30分)，共2道。
二、考查目标
第一部分数据结构课程考试的目的在于测试考生对于数据结构的基本概念、基本理论、基础知识的掌握情况，以及分析研究计算机加工的对象特性、选择适当的数据结构和存储结构、设计与之相适应的算法、和运用算法的时间和空间分析方法的能力。
第二部分C++课程考试的目的在于测试考生对于C++语言的基本语法成分及其语法/语义、程序设计逻辑和基本算法的掌握情况以及综合运用语言分析和解决实际问题的的能力。
三、考查范围或考试内容概要
第一部分 数据结构
1. 数据结构基础知识
数据结构、算法的基本概念;抽象数据类型;算法的描述和算法分析
2. 线性表
线性表的逻辑结构;线性表的顺序存贮结构;线性表的链式存储结构和线性链表;循环链表和双向链表
3. 栈和队列
栈的抽象数据类型;栈的表示与实现;栈的应用;队列的抽象数据类型;链式队列;循环队列
4. 串
串类型的定义;串的表示和实现;串的模式区配;串操作应用
5. 数组和广义表
数组的定义和运算;数组的顺序存储结构;矩阵的压缩存储;广义表表示
6. 树和二叉树
树和二叉树的定义和基本操作;二叉树的性质;二叉树的存储结构;二叉树遍历算法和应用;线索二叉树;树和森林;哈夫曼树及其应用
7. 图
图的定义和术语;图的存储结构;图的遍历;图的连通性;有向无环图及其应用;最短路径
8. 查找
静态查找表;动态查找表;哈希表
9. 内部排序
排序的定义，排序方法的稳定性，内部排序与外部排序，排序方法的分类;插入排序;快速排序;选择排序;归并排序;基数排序;各种内部排序方法的比较讨论
第二部分 C++
1. C++程序设计的基本概念
C++程序的概念、C++程序结构、C++程序的运行方法与过程
2. 基本数据类型、常量、变量、运算符和表达式
基本数据类型的概念;常量和变量的概念及其使用方法;常见的运算符(算术、赋值、逻辑、关系、逗号、条件、位运算符等)及其构成的表达式计算;运算符的优先级及结合性。
3. 顺序结构的程序设计
基本输入/输出操作及其使用;顺序结构程序设计的基本方法。
4. 选择和循环结构的程序设计
选择结构的程序设计方法(if语句和switch语句及其使用);循环结构的程序设计方法(while循环、do-while循环、for循环、break和continue语言);选择和循环结构程序设计的具体应用。
5. 数组及其使用
一维和二维数组的基本概念;一维和二维数组的基本使用方法;一维和二维数组的应用;字符数组与字符串的概念及其使用;字符串的处理;向量的基本概念及其简单使用方法。
6. 函数及其使用
函数的概念及其定义;函数的调用;递归函数的定义和使用;变量的存储类型;函数与数组、指针等的关系;
7. 指针及其使用
指针的基本概念;指针的使用;指针与数组;指针与函数;指针与字符串;命令行参数。
8. 编译预处理
简单的编译预处理指令及其使用方法。
9. 结构体与共用体类型
结构体/共用体类型的定义和使用方法;枚举类型的定义和使用方法;链表的简单构造和操作。
10. 类与对象
类的定义方法;对象的基本概念及其使用;构造函数的定义、作用和重载;析构函数的定义、作用;拷贝构造函数的定义和作用;类的静态成员及其使用;常对象和常成员函数;运算符重载。
11. 继承与派生
继承的基本概念;派生类的构造函数与析构函数;多重继承;多重继承方式下的二义性解决方法。
12. 多态性
多态的概念及其实现机制;抽象类的概念;静态联编与动态联编。
四、参考教材或主要参考书：
1. 严蔚敏、吴伟民，《数据结构(C语言版)》，清华大学出版社，2011年
2. 严蔚敏、吴伟民、米宁，《数据结构习题集(C语言版)》，清华大学出版社，2011年
3. 钱能，《C++程序设计教程》(第二版)，清华大学出版社，2005.
