第一部分 数据结构与算法（总分：60分）
知识点：21
考试题型
问答、分析、编程
考试大纲
栈（Stack）、队列（Queue）和向量（Vector）
内容：
- 单链表,双向链表,环形链表,带哨兵节点的链表;
- 栈的基本概念和性质,栈ADT及其顺序,链接实现;
- 栈的应用;
- 栈与递归;
- 队列的基本概念和性质,队列ADT及其顺序,链接实现;
- 队列的应用;
- 向量基本概念和性质;
- 向量ADT及其数组、链接实现;
树
内容：
- 树的基本概念和术语;
- 树的前序,中序,后序,层次序遍历;
- 二叉树及其性质;
- 普通树与二叉树的转换;
- 树的存储结构,标准形式;
- 完全树(complete tree)的数组形式存储;
- 树的应用,Huffman树的定义与应用;
查找(search)
内容：
- 查找的基本概念;对线性关系结构的查找,顺序查找,二分查找;
- Hash查找法,常见的Hash函数(直接定址法,随机数法),hash冲突的概念,解决冲突的方法(开散列方法/拉链法,闭散列方法/开址定址法),二次聚集现象;
- BST树定义,性质,ADT及其实现,BST树查找,插入,删除算法;
- 平衡树(AVL)的定义,性质,ADT及其实现,平衡树查找,插入算法,平衡因子的概念;
- 优先队列与堆,堆的定义,堆的生成,调整算法;
- 范围查询;
参考书目
| 作者 | 书名 | 出版社 | 出版时间 | 版次 | 备注 |
|---|---|---|---|---|---|
| Mark Allen Weiss | 数据结构与算法分析—Java语言描述（英文版·第3版） | 机械工业出版社 | 2013年3月 | 第三版 |