计算机考研之终极笔记-数据结构篇

《计算机考研之终极笔记-数据结构篇》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、考试点：www.kaoshidian.com第一章绪论1.1时间复杂度的求法（一）循环主体中的变量参与循环条件的判断a)找出基本操作b)设基本操作执行次数为T(n)，根据初始条件和基本操作语句确定变量与次数的关系式c)带回循环条件，求出T(n)，确定O(n)（二）循环主体中的变量与循环条件无关（1）递归程序a)确定递推关系（注意这里确定的是基本操作次数的递推关系）b)推出递推关系与执行次数的表达式c)令低级递推关系中的次数为常数（0或1），整理式子d)推导出T(n)（2）非递归程序等比、等差数列求和1.2

2、实例王道单科P8，综合第二题1）归类：循环主体中的变量参与循环条件的判断基本操作：i++(注意不是k参与循环条件的判断)初始条件i=1,执行一次i加一，值为2;执行第二次，i再加一，值为3；…；执行T(n)次，i的值为T(n)+1;考试点：www.kaoshidian.com考试点：www.kaoshidian.com带回循环变量：i

3、0;执行一次y加一,执行T(n)次后值y=T(n);带回循环变量：(T(n)+1)*(T(n)+1)>n推出：T(n)=n½-1所以T(n)=O(n½)3）归类：循环主体中的变量与循环条件无关,非递归程序T(n)=∑∑∑1=O(n^3)4）归类：循环主体中的变量与循环条件无关,非递归程序T(n)=M*N=O(M*N)综合题第一题归类：循环主体中的变量与循环条件无关,递归程序递推关系已给，题中没给的要自己推出来T(n)=2T(n/2)+n————①（注意：这里的n,2等都是执行次数，不是变量的值）T(n/2

4、)=2T(n/2*2)+n/2————②考试点：www.kaoshidian.com考试点：www.kaoshidian.com把②带回①得到T(n)=2*2*T(n/2*2)+2*n令T(n/2*2)中令n/2*2=1，解出n=2*2,2=Log2nT(n)=n*T(1)+n*Log2n=n+n*Log2n=O(n*Log2n)P7第4题归类：循环主体中的变量参与循环条件的判断基本操作：x=x*2初始条件：x=2,执行一次后x=2*2,执行两次后x=2*2*2,…,执行T(n)次后，x=2^T(n)带回

5、循环变量:2^T(n)=n/2T(n)=Log2(n)–1=O(Log2(n))第5题归类：循环主体中的变量与循环条件无关,递归程序基本操作：n*fact(n-1)递推关系：T(n)=1+T(n-1)（这里1为上面的基本操作执行了一次）T(n-1)=1+T(n-2)，代入上式得到：T(n)=1+1+T(n-2)令T(n-2)中n-2=0,则2=n考试点：www.kaoshidian.com考试点：www.kaoshidian.com原式整理为：T(n)=n+T(0)（这里表示的是次数的变化，即我每次减一，

6、前面就加一，减到n时，前面也加到n）T(n)=n=O(n)第二章线性表、栈、队列2.1各种链表特殊操作的时间复杂度DS复杂度操作删除最后删除第一个元素在最后插入在最前插入元素元素元素单链表O(n)O(1)O(n)O(1)循环单链表（头指针）O(n)O(1)O(n)O(1)循环单链表（尾指针）O(n)O(1)O(1)O(1)双链表（头指针）O(n)O(1)O(n)O(1)双链表（尾指针）O(1)O(n)O(1)O(n)双链表（头、尾指针）O(1)O(1)O(1)O(1)循环双链表O(1)O(1)O(1)O(

7、1)注意：若题中选项出现多个时间复杂度合适选项，选择修改指针最少的。2.2链表的指针修改原则——不断链原则先定义一下指针（个人定义）主链接性指针——通过已知指针（头指针或尾指针）和该指针可以链接操作所有参与元素，即该指针一断，元素失去控制（断链）；考试点：www.kaoshidian.com考试点：www.kaoshidian.com非主链接性指针——断开后不影响元素链接操作；（1）对只有主链接性指针的链表操作步骤a)建立新的主链接性指针b)修改旧主链接性指针（2）既有主链接性指针又有非主连接性指针a)修

8、改非主链接性指针b)建立新的主链接性指针c)修改旧主链接性指针2.3链表算法设计常用方法：头插法；尾插法；双指针；多指针（1）删除删除一个链表元素时，能同步找到它的直接前驱是最高效的，而如何实现同步直接影响算法的复杂程度（2）建表头插法；尾插法；双指针，各有各的特点，自己总结吧（3）查找这几次考的都是通过双指针的距离查找元素位置（4）排序考试点：www.kaoshidian.com考试点：www.kaoshidian.com对