2021年陇东学院专升本计算机科学与技术专业课考试大纲(1)

14、了解最短路径的含义。

15、了解求单源最短路径的Dijkstra算法的基本思想和时间性能。

16、掌握对于给定的有向图，根据Dijkstra算法画出求单源最短路径的过程示意图。

17、掌握拓扑排序的基本思想和步骤。

18、理解拓扑排序不成功的原因。

19、了解对给定的有向图，若拓扑序列存在，则要求写出一个或多个拓扑序列。

第9章 查找

1、了解查找在数据处理中的重要性。

2、理解查找算法效率的评判标准。

3、掌握顺序查找、二分查找、分块查找的基本思想、算法实现和查找效率分析。

4、理解顺序查找中哨兵的作用。

5、理解二分查找对存储结构及关键字的要求。

6、理解通过比较线性表上三种查找方法的优缺点，能根据实际问题的要求和特点，选择出合适的查找方法。

7、掌握二叉查找树和B-树的定义和特点以及用途。

8、掌握二叉查找树的插入、删除、建树和查找算法及时间性能。

9、掌握建立一棵二叉查找树的过程实质上是对输入实例的排序过程，输入实例对所建立的二叉查找树形态的影响。

10、了解B－树的插入、删除及查找方法的基本思想。

11、掌握散列表、散列函数、散列地址和装填因子等有关概念。

12、掌握散列函数的选取原则及产生冲突的原因。

13、掌握几种常用的散列函数构造方法。

14、理解两类解决冲突的方法及其优缺点。

15、了解产生“堆积”现象的原因。

16、理解采用线性探测法和拉链法解决冲突时，散列表的建表方法、查找过程以及算法实现和时间分析。

17、了解散列表和其它表的本质区别。

第10章 内部排序

1、了解排序在数据处理中的重要性。

2、掌握排序方法的“稳定”性含义。

3、理解排序方法的分类及算法好坏的评判标准。

4、掌握直接插入排序的基本思想和算法实现，以及在很好、最坏和平均情况下的时间性能分析。

5、理解直接插入排序中哨兵的作用。

6、掌握针对给定的输入实例，要能写出直接插入排序的排序过程。

7、掌握冒泡排序的基本思想。

8、掌握快速排序的基本思想和算法实现，以及在最坏和平均情况下的时间性能分析，了解算法的稳定性。

9、了解基准元素（划分元）对划分是否平衡的影响。

10、掌握针对给定的输入实例，能写出快速排序的排序过程。

11、理解堆、小根堆、大根堆、堆项等有关概念和定义。

12、理解堆性质及堆与完全二叉树的关系。

13、掌握直接选择排序和堆排序的基本思想和算法实现，以及时间性能分析。

14、掌握针对给定的输入实例，写出堆排序的排序过程。

15、掌握归并排序的基本思想和算法实现，以及时间性能分析。

16、掌握针对给定的输入实例，能写出归并排序的排序过程。

17、掌握通过对被排序的记录数目、记录信息量的大小、关键字的结构及初始状态、稳定性要求、辅助空间的大小、各种时间性能等方面的比较掌握各种排序的优缺点。　　

三、参考教材：

1.《数据结构用C语言描述》（第二版），耿国华等编写，高等教育出版社，2015年；

2.《数据结构》（C语言版），严蔚敏、吴伟民编著，清华大学出版社，2020年。

小编推荐：专升本考试历年真题 | 专升本备考辅导资料

　　感谢您阅读2021年陇东学院专升本计算机科学与技术专业课考试大纲(1)，本文出自：诚为径统招专升本网，转载需带上本文链接地址：https://tzzsb.cwjedu.com/ksjc/1990/p2