考研数据结构参考书数据结构考研分数线

从今天开始，我会为大家总结一下考研中，数据结构每章的考点总结，如果有考研的网友，希望能够为你们带来帮助，没有考研的，也希望能够为大家在数据结构方面有一些帮助，大家多多点赞支持。
考点
1.1 数据结构的基本概念；
1.2 抽象数据类型；
1.3 算法和算法的时间复杂度。
1.1 数据结构的基本概念；
数据元是数据的基本单位，一个数据元素可由若干个数据项完成，数据项是构成数据元素的不可分割的最小单位。例如，学生记录就是一个数据元素，它由学号、姓名、性别等数据项组成。
数据对象是具有相同性质的数据元素的**，是数据的一个子集。
数据类型是一个值的**和定义在此**上一组*作的总称。
· 原子类型：其值不可再分的数据类型· 结构类型：其值可以再分解为若干成分（分量）的数据类型· 抽象数据类型：抽象数据组织和与之相关的*作1.2 抽象数据类型；
抽象数据类型（adt）是指一个数学模型以及定义在该模型上的一组*作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。通常用（数据对象、数据关系、基本*作集）这样的三元组来表示。
数据结构的三要素：
1. 逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据，独立于计算机。分为线性结构和非线性结构，线性表、栈、队列属于线性结构，树、图、**属于非线性结构。
2. 存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构，包括数据元素的表示和关系的表示，依赖于计算机语言，分为顺序存储（随机存取）、链式存储（无碎片）、索引存储（检索速度快）、散列存储（检索、增加、删除快）。
数据的运算：包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体*作步骤。
1.3 算法和算法的时间复杂度。
要明确一点：时间复杂度并不是直接对时间进行计算，而是通过计算算法中的基本*作的执行次数，来侧面对运行时间进行估算。
计算方法：
找到一个基本*作（最深层循环）分析该基本*作的执行次数x和问题规模n的关系x=f(n)x的数量级o(x)就是算法时间复杂度t(n)
常用技巧：
加法规则：o(f(n))+o(g(n))=o(max(f(n),g(n)))乘法规则：o(f(n))*o(g(n))=o(f(n)*g(n))o(1)所以，时间复杂度：o(1) ，因为程序的执行次数为常数阶。
例题2：
for (i = 0; i < n; i++)for (j = 0; j < m; j++) a[i][j] = 0;解：语句 a[i][j] = 0; 执行次数有
可推出执行次数为 m * n 次，所以时间复杂度为 o(m*n)。
例题3：
s = 0;for(i = 0; i < n; i++)for(j = 0; j < n; j++) s += b[i][j];sum = s;解：语句 s += b[i][j]; 的执行次数为 n * n 。所以，时间复杂度为o(n^2)。
例题4：
i = 1;while(i <= n)i = i*3; /* //推导可知：i = 1;while(i <= n)i = i*2;//时间复杂度为o(logn)，底数为2。*/解： i 的值为：1，3，9， 27，…用 i(x) 表示第 x 次循环时i的值，则i(x)=3^x, x初始值为0。
语句 i = i*3; 的执行次数为3^x<=n，有x<=log3n（3为底），所以，时间复杂度为o(log3n)。
例题5：
x = 2;while(x < n/2)x = x * 2; 解：x 的取值是首项为4，公比为2的等比数列，设执行次数为 t，则有2^(t+1)例题6：
x = 0;for(i = 1; i < n; i++)for (j = 1; j <= n-i; j++)x++;解：解：语句x++; 的执行次数为
所以，时间复杂度为o(n^2)。
例题7：
x = 0;for(k = 1; k <= n; k*=2)for (j = 1; j <= n; j++)x++;解：此题不同于（6）小题，内层循环条件 j <= n 与外层循环变量无关。
每执行一次 j 自增一，每次内层循环都执行 n 次，所以内层的时间复杂度为 o(n)。
对于外层，设循环次数 t 满足k=2^t<=n ，所以t=(y+1) * (y+1)，有 y<=n^1/2-1，所以，时间复杂度为o(n^1/2)。
例题10：
int func(int n){int i = 0, sum = 0;while(sum 1; i--)for (int j = 1; j a[j+1])a[j]与a[j+1]对换;解：最后一行语句频度在最坏情况下是o(n^2)。
当所有相邻元素都为逆序时，则最后一行的语句每次都会执行。则有
所以，时间复杂度为o(n^2)。
例题12：
已知两个长度分别为 m 和 n 的升序链表，若将它们合并为长度为 m + n 的一个降序链表，则最坏情况下的时间复杂度是 o(max(m,n))。
解：两个升序链表合并，两两比较表中元素，每比较一次，确定一个元素的链接位置（取较小元素）。当一个链表比较结束后，将另一个链表的剩余元素**即可。
最坏的情况是两个链表中的元素依次进行比较，因为2 max(m,n) >= m + n，所以时间复杂度为o(max(m,n))。
今天第一章就给大家分享到这里，希望给大家一些帮助，也希望大家多多点赞支持。
考研数据结构(考研数据结构参考)

资阳市雁江区丹山职业技术学校

考研数据结构参考书 数据结构考研分数线

考研数据结构参考书数据结构考研分数线