2019陇东学院专升本计算机科学与技术专业考试大纲历年真题录取分数线(三)

的连通图，根据Prim和Kruskal算法构造出最小生成树。

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、掌握直接选择排序和堆排序的