数据结构 考研，数据结构考研真题
今天为大家带来的是《数据结构》必会的核心考点，接下来的每一天，学长都会更新计算机考研408的四个科目的核心考点，帮助考24研的同学快速理清科目重点知识点，树立学科知识框架。
考点1：时间复杂度与空间复杂度
➤【考点笔记】时间复杂度
时间复杂度T(n)是指算法中所有语句的频度(执行次数)之和。人们关心的是当n趋于无穷时T(n)的数量级，而非T(n)的准确大小，因此以T(n)的数量级来表征时间复杂度。
例如，T(n)=n3+n2+n，可认为时间复杂度T(n)=O(n3)，这里数量级最大的一项必定是由最深层循环的语句贡献的，称之为基本运算。由于T(n)与算法中基本运算的频度f(n)同数量级，所以通常采用基本运算的频度的数量级O(f(n))来分析算法的时间复杂度，记为T(n)=O(f(n))。
最终归结为一句话：将算法中基本运算的执行次数的数量级作为时间复杂度。
时间复杂度的计算遵循两种规则：
· 加法法则：
T(n)=T1(n)+Tn(n)=O(f(n))+O(g(n))=O(max(f(n)，g(n)))
· 乘法法则：
T(n)=T1(n)×T2(n)=O(f(n))×O(g(n))=O(f(n)×g(n))
例如，设a{ }、b{ }、c{ }三个语句块的时间复杂度分别为O(1)、O(n)、O(n2)，则
1) a{
b{ }
c{ }
}的时间复杂度为O(n2)，满足加法法则；
2) a{
b{
c{ }
}的时间复杂度为O(n3)，满足乘法法则。
注意：有些情况下，算法中基本运算的执行次数还随问题的输入数据集的不同而不同。
➤ 【考点拓展】递归算法
递归是算法领域的一个重要思想。在后续的二叉树中也有递归的应用。递归算法可以通过迭代或栈改写为非递归算法。以本题为例，也可写成以下两种方式：
递归算法的特性：
①一个算法直接或间接调用自身。
②必须有一个明确的递归结束条件，称为递归出口。
由于递归算法需要反复进行函数调用与返回，运行效率较低。实现递归的关键是建立递归调用工作栈。当有多个函数构成嵌套调用时，按照后调用先返回的原则，因此递归调用需要开辟栈以存放每一层的返回点、局部变量等，栈的大小也就是递归深度和递归算法空间复杂度的大小。
➤ 【考点笔记】空间复杂度
空间复杂度S(n)指算法运行过程中所使用的辅助空间的大小，通常结合算法题考查。
若输入数据所占空间只取决于问题本身，和算法无关，则只需分析除输入数据和程序之外的临时分配的额外空间。算法原地工作是指算法所需辅助空间是常量，即O(1)。
考点2：线性表的顺序表示
➤【考点笔记】时间复杂度
顺序表是指用一组连续的存储单元，依次存储线性表中的各个元素，从而使得逻辑上相邻的元素在物理位置上也相邻，因此可以随机存取(根据首元素地址和元素序号)表中任一元素。
顺序表的缺点也很明显，如元素的插入和删除需要移动大量的元素，插入操作平均需要移动n/2个元素，删除操作平均需要移动(n-1)/2个元素，而且存储分配需要一段连续的存储空问，不够灵活。
➤ 【考点笔记】顺序表的插入操作
对于插入算法，若表长为n，则在第f位置插入元素，则从an到ai都要向后移动一个位置，共需移动n-f+1个元素，平均时间复杂度为O(n)。代码片段如下：
➤ 【考点笔记】顺序表的删除操作
对于删除算法，若表长为n，当删除第i个元素时，从ai+1到an都要向前移动一个位置，则共需移动n-i个元素，平均时间复杂度为O(n)。代码片段如下：
➤ 【考点笔记】顺序表的查找
(1)按序号查找，顺序表具有随机存取(根据首元地址和序号)的特点，时间复杂度为O(1)。
(2)按值x查找，主要运算是比较操作，比较的次数与值x在表中的位置有关，也与表长有关，平均比较次数为(n+1)/2，时间复杂度为O(n)。
数据结构 考研(数据结构考研参考)