怎么让别人看到自己做的网站,张店学校网站建设定制,常州网站建设哪儿好薇,网站建设项目环境影响评价目录复试经验分享
三、计算机学科专业基础综合
3.1 数据结构
3.1.1 概念 时间复杂度 时间复杂度是指执行算法所需要的计算工作量一般情况下#xff0c;按照基本操作次数最多的输入来计算时间复杂度#xff0c;并且多数情况下我们去最深层循环内的语句所描述的操作作为基本操作…复试经验分享
三、计算机学科专业基础综合
3.1 数据结构
3.1.1 概念 时间复杂度 时间复杂度是指执行算法所需要的计算工作量一般情况下按照基本操作次数最多的输入来计算时间复杂度并且多数情况下我们去最深层循环内的语句所描述的操作作为基本操作。一般时间复杂度常对幂指阶算法原地工作是指算法所需辅助空间是常量即 O1 算法设计原则 正确性可读性健壮性高效率和低存储性
3.1.2 链表
单链表的逆置
class Solution {
public:ListNode* ReverseList(ListNode* pHead) {ListNode *pre nullptr;//前驱ListNode *cur pHead;//当前指针ListNode *nex nullptr; // 后继这里可以指向nullptr循环里面要重新指向while (cur) {nex cur-next;cur-next pre;//当前的后继指向前驱pre cur;//当前即为前驱cur nex;//移动指针到下一个}return pre;}
};头指针 : 指向链表第一个节点的指针具有标识作用。必须有否则就找不到链表内存泄漏) 头节点第一个节点之前的空节点方便操作可有可无
3.1.3 栈
先进后出
3.1.4 队列
先进先出
循环队列解决假溢出问题空留一个位置用来判断队空队满。 队满条件Q.rear1)%MaxSizeQ.front 队空条件 Q.frontQ.rear
3.1.5 矩阵串
3.1.5.1 矩阵的压缩存储
对称矩阵只存放主对角线和下三角区的元素计算得位置三角矩阵空的不存三对角矩阵行列优先稀疏矩阵三元组法十字链表法
3.1.5.2 KMP 模式匹配算法
改进自简单模式算法在暴力匹配中每趟匹配失败都是模式后移一位再从头开始比较。而某趟已匹配相等的字符序列是模式的某个前缀这种频繁的重复比较相当于模式串在不断地进行自我比较这就是其低效率的根源。因此可以从分析模式本身的结构着手如果已匹配相等的前缀序列中有某个后缀正好是模式的前缀那么就可以将模式向后滑动到与这些相等字符对齐的位置主串 i 指针无须回溯并继续从该位置开始进行比较。而模式向后滑动位数的计算仅与模式本身的结构有关与主串无关。
3.1.6 树
3.1.6.1 基本概念
满二叉树每一层结点数都达到最大值
完全二叉树相比满二叉树少了最底层最右侧的一些节点 常用性质 结点总数 总度数 1路径树中两个结点之间所经过的结点序列 遍历方式先序遍历中序遍历、后序遍历层序遍历 层序遍历操作先将根结点入队左右子树根结点入队根出队。每次出队前将其左右子树根结点入队。
3.1.6.2 二叉排序树 二叉排序树又称二叉查找树它或者是一颗空树或者满足一下性质的二叉树 : ①若左子树不空则左子树上所有结点的值均小于根节点的值 ; ②若右子树不空则右子树上所有结点的值均大于根节点的值 ; ③左右子树也分别是二叉排序树。 二叉查找原理步骤 :
若根结点的关键字值等于查找的关键字成功。否则若小于根结点的关键字值递归查左子树。若大于根结点的关键字值递归查右子树。若子树为空查找不成功。 二叉排序树的删除 若为叶子结点直接删除 找到前驱或者后继替代转换前驱左子树的最右下后继右子树的最左下
3.1.6.3 平衡二叉树与红黑树 将二叉树的高度控制在一个合理的高度内减小递归深度增加查找效率 平衡二叉树的左右子树高度差的绝对值不超过 1且左右子树都为平衡二叉树 红黑树降低要求平衡二叉树插入新结点后需要调整过多红黑树随规模增大调整较小规模即可根叶黑不红红黑路同 性质 1. 结点是红色或黑色。 性质 2. 根结点是黑色。 性质 3. 所有叶子都是黑色。叶子是 NIL 结点 性质 4. 每个红色结点的两个子结点都是黑色。从每个叶子到根的所有路径上不能有两个连续的红色结点 性质 5. 从任一节结点到其每个叶子的所有路径都包含相同数目的黑色结点。 性质 6. 根结点到叶子结点的最长路径不超过最短路径的两倍
3.1.6.4 哈夫曼树
哈夫曼树给定 N 个权值作为 N 个叶子结点构造一棵二叉树若该树的带权路径长度达到最小称这样的二叉树为最优二叉树也称为哈夫曼树(Huffman Tree)。哈夫曼树是带 权路径长度最短的树权值较大的结点离根较近。
哈夫曼树定义 : 给定 n 个权值作为 n 个叶子结点构造一棵二叉树若带权路径长度达到最 小的二叉树. 构造方法 : 假设有 n 个权值则构造出的哈夫曼树有 n 个叶子结点。n 个权值分 别设为 w1w2、…、wn,则哈夫曼树的构造规则为 : (1)将 w1、w2、…,wn 看成是有 n 棵树的森林(每棵树仅有一个结点); (2)在森林中选出两个根结点的权值最小的树合并作为一棵新树的左、右子树且新树的 根结点权值为其左、右子树根结点权值之和 ; (3)从森林中删除选取的两棵树并将新树加入森林 ; (4)重复(2)、(3)步直到森林中只剩一棵树为止该树即为所求得的哈夫曼树。特点 : 权值越大的结点距离根节点越近 ; 树中没有度为一的结点。
应用: 哈夫曼编码减少编码的长度。哈夫曼编码就是长度最短的前缀编码。
3.1.7 图
3.1.7.1 基本概念 无向图度连通连通分量 有向图入度出度强连通图强连通分量 拓扑排序有向无环图的一个顶点组成的序列称为拓扑序列。路径 关键路径顶点表示事件有向边便是活动边上的权值表示开销称为 AOE 网。AOE 网中从源点到汇点的最大路径长度的路径叫做关键路径。
3.1.7.2 图的存储 邻接矩阵 : 是图的顺序存储结构用两个数组分别存储数据元素顶点)信息和数据元素之间的关系(边 / 弧的信息。图的邻接矩阵表示是唯一的无向图的邻接矩阵是对称的。 邻接表 : 是图的链式存储结构由单链表的表头形成的顶点表和单链表其余结点所形成的边表两部分组成。多用于无向图 十字链表 : 有向图的另一种链式存储结构。 邻接多重表 : 无向图的链式存储结构。
3.1.7.3 最小生成树 : 普里姆算法和克鲁斯卡尔算法
prim 其基本思想为 : 从联通网络 NV.E)中某一顶点 u0 出发选择与他关联的最小权值的 边将其顶点加入到顶点集 S 中此后就从一个顶点在 S 集中另一个顶点不在 S 集中的所 有顶点中选择出权值最小的边把对应顶点加入到 S 集中直到所有的顶点都加入到 S 集中 为止。kruskal 其基本思想为 : 设有一个有 N 个顶点的联通网络 NV.E, 初试时建立一个只有 N 个顶 点没有边的非连通图 TT 中每个顶点都看作是一个联通分支从边集 E 中选择出权值最 小的边且该边的两个端点不在一个联通分支中则把该边加入到 T 中否则就再从新选择一 条权值最小的边直到所有的顶点都在一个联通分支中为止。最小生成树一个有 n 个结点的连通图的生成树是原图的极小连通子图且包含原图中的所 有 n 个结点并且有保持图联通的最少的边。如果在最小生成树添加一条边必定成一个 环。
3.1.7.4 DFS 与 BFS 深度优先搜索相当与树的先序遍历一直访问当前结点的邻接结点当没有邻接结点的时候退回继续访问。 广度优先搜索相当与树的层序遍历访问当前结点的所有邻接结点再往邻接结点的邻接结点去访问
3.1.8 排序
3.1.8.1 快速排序
算法实现
Paritition1(int A[], int low, int high) {int pivot A[low];//默认选择第一个元素为枢轴元素while (low high) {while (low high A[high] pivot) {--high;}A[low] A[high];while (low high A[low] pivot) {low;}A[high] A[low];}A[low] pivot;return low;
}void QuickSort(int A[], int low, int high) //快排母函数
{if (low high) {int pivot Paritition1(A, low, high);QuickSort(A, low, pivot - 1 );QuickSort(A, pivot 1 , high);}
}算法步骤
a. 从数列中挑出一个元素称为 “基准”pivot; b. 重新排序数列所有元素比基准值小的摆放在基准前面所有元素比基准值大的摆在基准的后面相同的数可以到任一边。在这个分区退出之后该基准就处于数列的中间位置。这个称为分区partition操作 c. 递归地recursive把小于基准值元素的子数列和大于基准值元素的子数列排序
算法实现
快排相关问题 时间复杂度最好 n ∗ l o g 2 n n*log_2n n∗log2n 最差 n 2 n^2 n2 平均 n ∗ l o g 2 n n*log_2n n∗log2n 空间复杂度 l o g 2 n log_2n log2n ~ n时间复杂度与两侧平衡差值有关与处理顺序无关。递归深度不稳定算法适用于顺序表特征每完成一轮都会有至少一个元素出现在正确的位置上。上一个枢轴元素不在两端的话则下一趟至少有两个出现在正确位置。
3.1.8.2 希尔排序
希尔排序就是先将整个待排序列分割成若干子序列在子序列内分别进行直接插入排序待整个序列的元素基本有序时再将全体元素进行一次直接插入排序。
每趟排序增量递减增量的初始值是 1通过 3*h1 循环计算
3.1.8.3 内部排序与外部排序
• 内部排序是排序期间元素全部存放在内存的排序 ; 外部排序是指在排序期间元素无法全部同
时存放在内存中必须在排序的过程中根据要求不断的在内外存之间移动的排序。
3.1.9 查找
3.1.9.1 哈希查找 哈希查找是通过计算数据元素的存储地址进行查找的一种方法。 哈希查找步骤 (1)用给定的哈希函数构造哈希表 (2)根据选择的冲突处理方法解决地址冲突 (3)在哈希表的基础上执行哈希查找。 哈希函数 直接定址法线性函数一一对应 数学分析法选出若干位 平方取中法平方后取中间位 除留余数法除质数看余数 哈希冲突 开放定址法线性探测聚集二次探测法 拉链法散列地址相同的记录存储在同一个线性表中 再哈希法 建立公共溢出区基本表 溢出表 装填因子填入表中的元素个数 / 散列表的长度。 冲突是无法避免的与装填因子无关
3.1.9.2 折半查找 条件 : 有序数组 操作 :
1)查找过程从数组的中间元素开始如果中间元素正好是要查找的元素则搜素过程结束 ;
2)如果某一特定元素大于或者小于中间元素则在数组大于或小于中间元素的那一半中查找而且跟开始一样从中间元素开始比较。
3)如果在某一步骤数组为空则代表找不到。
4)这种搜索算法每一次比较都使搜索范围缩小一半。
时间复杂度 (log(n))
3.1.9.3 B 树
B 树和平衡二叉树稍有不同的是 B 树属于多叉树又名平衡多路查找树查找路径不只两个数据库索引技术里大量使用者 B 树和 B 树的数据结构。所有节点关键字是按递增次序排列并遵循左小右大原则所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为 null 对应下图最后一层节点的空格子 ;B 树相对于平衡二叉树的不同是每个节点包含的关键字增多了特别是在 B 树应用到数据库中的时候数据库充分利用了磁盘块的原理磁盘数据存储是采用块的形式存储的每个块的大小为 4K每次 IO 进行数据读取时同一个磁盘块的数据可以一次性读取出来把节点大小限制和充分使用在磁盘快大小范围把树的节点关键字增多后树的层级比原来的二叉树少了减少数据查找的次数和复杂度 ;
3.1.9.4 B 树 B 树是 B 树的一个升级版相对于 B 树来说 B 树更充分的利用了节点的空间让查询速度更加稳定其速度完全接近于二分法查找。为什么说 B 树查找的效率要比 B 树更高、更稳定 对比 1、B 树的层级更少相较于 B 树 B 每个非叶子节点存储的关键字数更多树的层级更少所以查询数据更快 2、B 树查询速度更稳定B 所有关键字数据地址都存在叶子节点上所以每次查找的次数都相同所以查询速度要比 B 树更稳定 ; 3、B 树天然具备排序功能B 树所有的叶子节点数据构成了一个有序链表在查询大小区间的数据时候更方便数据紧密性很高缓存的命中率也会比 B 树高。 4、B 树全节点遍历更快B 树遍历整棵树只需要遍历所有的叶子节点即可而不需要像 B 树一样需要对每一层进行遍历这有利于数据库做全表扫描。
B 树相对于 B 树的优点是如果经常访问的数据离根节点很近而 B 树的非叶子节点本身存有关键字其数据的地址所以这种数据检索的时候会要比 B 树快。
3.1.10 算法
3.1.10.1 贪心算法 贪心算法(又称贪婪算法是指在对问题求解时总是做出在当前看来是最好的选择。也就是说不从整体最优上加以考虑算法得到的是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解关键是贪心策略的选择。 贪心算法的一般步骤 :
1)将复杂问题分解为多个子问题 ;
2)子问题的解是当前所有解中的最优解 ;
3将所有子问题的解合并为原问题的解。
③说明 :
贪心问题和动态规划较为相似其中一个较为关键的区别是贪心算法是不可取消的自顶向下
求出子问题的当前最优解。而动态规划是每步做出的选择都依赖于子问题的解。
3.1.10.2 动态规划 动态规划和之前的贪心算法有点类似都是将一个规模大的问题分解为几个小的问题通过解决小的问题来得到整体的解。 动态规划的核心问题是问题的状态的定义和状态转移方程的求解。 动态规划的关键在于将重复出现的子问题在第一次求解之后就将其保存起来以后再遇到时不用重复求解。动态规划是按照自底向上的方式计算最优解。 算法应用的常用问题 : 当题目求解的是最大值、最小值可行与否或者方案总数时考虑使用动态规划问题。算法的一般步骤 : 将问题分解为不同的子问题 ; 定义状态找出初始状态 ; 状态转移方程的求解 ; 求出问题最终的答案。 贪心问题和动态规划较为相似其中一个较为关键的区别是贪心算法是不可取消的自顶向下求出子问题的当前最优解。而动态规划是每步做出的选择都依赖于子问题的解。
