《算法与数据结构》考试大纲

　　(适用于计算机科学与技术专业考生)

　　1.基本概念和术语

　　掌握数据结构中数据、数据元素、数据逻辑结构、数据存储结构、数据类型、算法等基本概念，掌握算法的时间复杂度和空间复杂度的分析方法，了解抽象数据类型的定义和使用，了解算法的描述方法。

　　2.线性表

　　掌握线性表的基本概念和类型定义，熟练掌握对顺序表和单链表的常用操作方法及其程序实现，掌握循环链表和双向链表的定义和它的插入、删除等操作方法。

　　3.稀疏矩阵

　　掌握稀疏矩阵的定义和各种存储结构，掌握稀疏矩阵的转置和相加的方法并了解其算法。

　　4.栈和队列

　　掌握栈和队列的定义，熟练掌握顺序和链接存储的栈和队列的各种运算的方法及其程序实现，掌握表达式求值和迷宫求解的方法并了解其算法。

　　6.树和二叉树

　　掌握树的定义、性质、存储结构及遍历算法，熟练掌握二叉树的各种遍历方法及其实现，掌握二叉树的其他操作方法及实现，了解树和二叉树的转换方法。

　　掌握二叉搜索树的定义、熟练掌握对二叉搜索树进行插入和查找的方法和实现、熟练掌握对堆进行查找和删除的方法和实现，掌握哈夫曼树的定义和构造哈夫曼树的方法，了解二叉搜索树的删除方法，了解哈夫曼树编码的方法。

　　7.图

　　掌握图的定义和术语;熟练掌握图的存储结构及深度和广度优先搜索方法及其实现;掌握图的生成树的概念，掌握求图的最小生成树的普里姆算法和克鲁斯卡尔算法并了解其实现算法;掌握求最短路径的算法并了解其实现方法;掌握扑排序的方法并了解其实现算法;了解关键路径的算法和实现方法。

　　8.查找

　　熟练掌握顺序查找和二分查找的方法及实现;掌握索引表的定义、索引查找的方法及实现，掌握分块查找的方法及实现;掌握散列表的定义，利用除留余数法构造散列函数的方法，利用线性探查法和链接法处理冲突的方法;了解构造散列函数的其他方法，了解进行散列表查找、插入和删除的算法描述。

　　9.排序

　　掌握直接插入排序、直接选择排序、冒泡排序的方法及其实现，熟练掌握希尔排序、快速排序、堆排序、二路归并排序的方法及其实现，掌握各种排序方法的稳定性、时间复杂度和空间复杂度。

　　10.文件

　　了解顺序文件、索引文件的组织方式。

　　参考书：

　　1.《数据结构(C语言版)》王桂芝，中国铁道出版社(2011.8)

　　2.《数据结构》(第四版)安训国，大连理工大学出版社(2009.7)