文章

7

粉丝

7

获赞

13

访问

35743

头像
计算机考研复试笔记——算法篇
数据结构
发布于2021年4月8日 23:23
阅读数 5076

1. 两个有序链表的合并:设两个有序链表分别为L1和L2,先用两个指针分别遍历这两个链表,并且每次读取两个链表中元素的值,将较小的值插入到新的链表L中,如果其中一个链表遍历完毕,则另一个链表中剩下的元素就可以直接接在L的表尾。

2. 求链表中倒数第k个结点:①可以使用栈,将链表中全部元素入栈,在出栈时选择第k个结点。②设置快慢指针,其中快指针比慢指针多走k-1步,那么当快指针走到终点的时候,慢指针就指向了倒数第k个结点。

3. 括号匹配:括号匹配算法用栈来实现,给定一组括号,如果是左括号就直接入栈,如果是右括号就从栈顶弹出一个元素,如果匹配则继续,如果不匹配则直接返回false,最后括号都遍历完毕后再检查栈中是否还有元素,如果没有则说明匹配成功,否则说明匹配失败。

4. 哈夫曼树:先从所有的结点中选出两个值最小的结点,构成一棵树,然后再将这两个结点值之和与其他结点进行比较,直到所有的结点都连接在一棵树上为止。

5. 二分查找:二分查找只适用于排好序的情况,先用两个指针分别指向数组的首部和尾部,然后执行循环的条件是首部指针的位置小于尾部指针的位置,每次找到首尾指针的中心位置然后与要查找的元素(设为x)比较,如果比x要大,则从数组的前一半中继续寻找,如果比x要小,则从数组的后一半中寻找。如果循环结束后还没有找到说明数组中没有这个元素,时间复杂度为O(logn)。

6. 冒泡排序:设排序序列记录的元素为n,进行n-1次遍历,每次遍历从开始位置依次往后比较前后相邻元素,这样较大的元素后移,n-1次遍历结束后,序列有序,平均时间复杂度为O(n^2)。

7. 简单选择排序:设排序序列的记录个数为n,进行n-1次选择,每次在n-i+1个记录中选择关键字最小的记录作为有效序列中的第i个记录,平均时间复杂度为O(n^2)。

8. 直接插入排序:将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数加1的有序表,第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从后向前扫描,把第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。平均时间复杂度为O(n^2)。

9. 归并排序:归并排序是分治法的一个典型应用,主要思想是将待排序列分为两部分,对每部分递归的应用归并排序,在两部分都排好序后进行合并,平均时间复杂度为O(nlogn)。

10. 快速排序:快速排序的主要思想是在待排序的序列中选择一个称为主元的元素,将数组分为两部分,使得第一部分中的所有元素都小于或等于主元,而第二部分的元素都大于主元,然后对两部分递归的应用快速排序算法。快速排序算法在数组基本有序时效率最低,可以使用随机主元的方式来解决。

11. 快速排序为什么是最快的排序算法:快速排序交换和比较的大部分都是相邻元素,并且使用频率高,所以对cache友好。

12. 堆排序:给定一个待排序序列,首先经过一次调整,将序列构建成一个大顶堆,此时第一个元素是最大的元素,将其和序列的最后一个元素交换,然后将前n-1个元素调整为大顶堆,再将其第一个元素和末尾元素交换,这样最后就可以得到有序序列,时间复杂度为O(nlogn)。

13. Prim算法:prim算法是最小生成树算法,思想为以某一个点为开始,寻找当前该点可以访问到的所有的边;在已经寻找的边中发现最小边,这个边必须有一个点还没有被访问过,将还没有访问过的点加入到我们的集合中,记录添加的边;寻找当前集合可以访问的所有边,重复上述过程,直到没有新的点可以加入,此时由所有的边构成的树即为最小生成树。

14. Kruskal算法:kruskal算法是最小生成树算法,假设图中有m个顶点和n条边,首先把m个结点看作m个独立的生成树,并且把n条边按照从小到大的顺序进行排列,在n条边中,我们依次取出其中的每一条边,如果发现边的两个结点分别位于两棵树上,那么把这两棵树合并成一棵树,如果边的两个结点位于同一棵树上,则忽略这条边。等到所有的边都遍历结束后,如果所有的生成树可以合并成一棵树,那么它就是我们要找的最小生成树,反之则没有最小生成树。

15. 拓扑排序:依次选择一个入度为0的顶点并输出,从网中删除此顶点并且与这个点连接的边。循环结束后,若输出的顶点数小于网中的顶点数,则有回路,否则输出的顶点序列就是一种拓扑排序序列。

16. 深度优先搜索:深度优先搜索是对连通图进行遍历的算法,它的思想是从一个顶点V0开始,沿着一条路一直走到底,如果发现不能到达目标解,那就返回到上一个结点,然后从另一条路开始走到底,所以使用递归来实现。

17. 广度优先搜索:需要结合队列来实现,每次都是先遍历同一个层次的所有结点,然后根据顺序依次入队列,每次循环的时候,判断队列是否为空,如果不为空再把队列的第一个结点取出,然后再把这个结点对应的所有子结点按照顺序依次加入队列,然后重复上述过程,一直到所有的结点都入队。

18. Dijkstra算法:这是一种基于贪心算法的单源最短路算法,维护两个点集A,B,其中A点集代表已经求出源点到终点的最短路的点的集合,B点集代表未求出源点到终点的最短路的点的集合。然后维护一个向量d,d[i]表示源点到点i的最短路径长度,不断重复以下操作:找出B中d[i]最小的点,这个点为进入A中的候选结点,然后通过点松弛B中其他的点,更新向量d,然后将该候选点放入A中,直到B为空,一般时间复杂度为O(n^2)。

19. Floyd算法:这是一种基于动态规划的多源最短路算法,假如求A到B的最短距离,无非两种情况,一种是直接从A到B,另一种是A经过几个结点后再到B,分别算出这两种情况下的距离长度,选择最小的。算法的时间复杂度为O(n^3),比较适合于数据量较小的时候。



登录后发布评论

暂无评论,来抢沙发