2010年计算机考研专业课知识点分析：数据结构[4]

查找

在给定的数据集合中查找某个关键值就是查找查找的基本方法主要有顺序查找法折半查找法B树散列(Hash)表及其查找考的比较多的是折半查找和散列表我们要掌握它们的基本概念和方法例如散列表的碰撞如何解决装载因子的概念等

另外我们要掌握各种查找算法的分析及应用最好能把各种查找在查找成功查找失败的情况下的最好平均最坏的平均查找次数的计算方法搞清楚

内部排序

根据考试大纲只考查内部排序所谓内部排序就是在内存中进行排序在这一部分中主要要掌握直接插入排序折半插入排序冒泡排序(bubble sort)简单选择排序希尔排序(shell sort)快速排序堆排序二路归并排序(merge sort)基数排序的基本概念和方法搞清楚这些排序方法的流程以及它们之间的区别

在这个知识点一个很重要的考查点就是各种内部排序算法的比较一般的书上都会有这样的一个表格列出了所有排序在各种情况下(最好最坏平均)的时间复杂度和空间复杂度这个表是需要我们记下来的当然如果我们能掌握复杂度的计算方法自己能推算出来那就更好了

最后就是要掌握内部排序算法的基本应用以及算法的实现

[] [] [] [] [] []