第一次牛客模考总结

文章目录[隐藏]

• 分数详情
• 选择题详解
• 编程题详解
• 写在最后

分数详情

单选16，编程0分，意料之中。。但是排序57%让我感到意外。牛客的模考评估报告也就是成绩单真的是爱了爱了，每个题目都有详细的步骤，以及知识点等等。真的爱了。

选择题详解

顺序表查找一个数的算法复杂度：（n-1）/ 2 ； 快速排序的过程：选定某个基数（通常是第一个），然后i，j分别指定数组的第一个和最后一个元素，先从j开始，当j遇到比基数k小的数就和i交换位置，然后从i开始，当i遇到比基数k大的数就和j交换位置，直到i和j碰面。碰面后给基数k放在这个位置。这样得到的结果：基数k前面的数都比基数k小，基数k后面的数都比基数k大。 递归思想：把基数k前后的所有数当成两个数组，那就是数组1，基数k，数组2，从某种意义上他们就是从小到大排序的，这样只需再别分递归去调用快排解决剩下两个数组就可以了，一直递归？临界条件就是当数组的数只有一个的时候，return。 算法复杂度：Olog(n)

图的拓扑序列：若一个由图中所有点构成的序列A满足：对于图中的每条边(x, y)，x在A中都出现在y之前，则称A是该图的一个拓扑序列。 拓扑序列是针对有向图而言，并且存在环就一定没有拓扑序列。因为其不存在一个入度为0的点。 计算一个拓扑序列的方法：选一个读入为0的点，删除其关联的边，然后继续重复此操作。得到一个拓扑序列就是选择的点的顺序。