数据结构计算题
题源来自《王道数据结构》
一、概论
1. 时间复杂度题型
1.1 循环主体中变量参与循环条件的判断
-
方法：找出主体语句中与T(n)成正比的循环变量，将其代入条件中进行计算
-
例题1：
int i = 1; while(i<=n) i = i*2;i * 2的次数正是主体语句的执行次数 t ， 因此有 2 ^ t <= n，取对数后 t <= log2n， 则T(n) = O( log2n )
-
例题2：
int y = 5; while((y+1)*(y+1) < n) y = y+1;y + 1 的次数恰好与T(n)成正比，记 t 为该程序的执行次数并令 t = y-5，有y = t + 5 ，则（t+5+1) * ( t+5+1) < n，得 t < n^(1/2) - 6，故T(n) = O( n^(1/2) )
1.2 循环主体中的变量与循环条件无关
-
方法：采用数学归纳法或直接累计循环次数，多层循环从内到外分析，只关注主体语句的执行次数。
-
题型1：递归程序，一般使用公式进行递推
int fact(int n){ if(n<=1){ return 1; } return n*fact(n-1); }本题是求阶乘的递归代码，即n * (n-1) * .... * 1。每次递归调用 fact() 的参数减1，递归出口为 fact(1) , 一共执行n次递归调用 fact() ，故T(n) = 1 + T(n-1) = 1+1+T(n-2) = 1+1+1+...+T(1) = n-1 + T(1)。 即T(n) = O(n)
-
题型2：非递归程序，直接累计次数
void fun(int n){ int i = 0; while(i*i*i<=n) i++; }基本运算为 i++ ，设执行次数为 t ，有 t * t * t <= n， 即 t^3 <= n， 故有 t <= n^(1/3) 。即T(n) = O( n^(1/3) )
1.3 级数工具
-
常用级数
-
常函数级数
-
算数级数
-
幂方级数
-
几何级数
-
二、线性表
1. 链表插入删除题型
- 此种题型选择题方法：画图按照选项进行分析；大题方法：画图分析逐步写出代码
- 代表题型：《王道》page36 - 6 \ 13 \ 14 \ 15 题
1.1 单链表插入删除
1.2 双链表插入删除
2. 判断空表条件
- 此种题型要深入了解头结点的作用，对单链表和双链表的判空条件进行理解
- 代表题型：《王道》page36 - 11 \ 18 题
2.1 单链表判空条件
2.2 双链表判空条件
3. 头指针、尾指针、循环链表
- 此种题型通常给出操作，如末尾插入结点和删除结点，问选用哪种结构最节省时间
- 解题技巧：明确各项操作中需要用到哪些，如末尾插入结点，需要找到前驱结点；删除结点，则需要尾指针。然后看选项哪一个结构全符合O(1)的
- 代表题型：《王道》page37 - 19 \ 20 \ 21 题
4. 概念题
- 此种题型考察概念与特点，常规题型，把线性表部分掌握熟练即可应付