考研 数据结构(考研数据结构参考)
考研 数据结构，考研数据结构真题
从今天开始，我会为大家总结一下考研中，数据结构每章的考点总结，如果有考研的网友，希望能够为你们带来帮助，没有考研的，也希望能够为大家在数据结构方面有一些帮助，大家多多点赞支持。
考点
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(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(2!)<O(nn)，即常数<对数<线性<幂函数<指数函数
三种复杂度：
最坏时间复杂度：考虑输入数据最坏的情况。平均时间复杂度：考虑所有输入数据都等概率的情况最好时间复杂度：考虑输入数据最好的情况
例题1：
x = 90; y = 100;while(y > 0){ if(x > 100){ x = x - 10; y--; }else{ x++; }}
解：运行程序，有 x < 100, x = 91 …… x = 101时，有 x = 91, y = 99，每循环11次y的值减1，所以总循环次数有11 * 100 = 1100。
所以，时间复杂度：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)<n/2，即t<log2n/2，即t<log2n/2-1，所以，时间复杂度为O(log2n)。
例题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<=log2n。
所以，内层的时间复杂度*外层的时间复杂度即为O(n)*O(log2n)=O(nlog2n)。
所以，时间复杂度为 O(nlog2n)。
例题8：
int fact(int n){ if(n <= 1) return 1; return n*fact(n-1);}
解：本题是求 n 的阶乘，即 n(n-1)(n-2)*…*2*1，每次递归调用时 fact() 的参数减一，递归出口为 fact(1)，一共执行 n 次递归调用 fact()，所以，时间复杂度为 O(n) 。
例题9：
//（9）x = n; //n>1y = 0;while(x ≥ (y+1) * (y+1)) y++;
解：语句 y++; 的执行次数为 n>=(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 < n) sum += ++i; return i;}
解：i 与 sum 的取值变化如下：
|
i |
sum |
|
1 |
0+1 |
|
2 |
0+1+2 |
|
3 |
0+1+3 |
|
… |
… |
|
ｔ |
所以，有
所以，时间复杂度为O(n^1/2)。
例题11：
for(int i= n-1; i > 1; i--)for (int j = 1; j < i; j++) if(A[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))。
今天第一章就给大家分享到这里，希望给大家一些帮助，也希望大家多多点赞支持。
考研 数据结构(考研数据结构参考)