数据结构第一章

考试无非考的是一下三点：概念、理解和运用。前者直接考的较少，后两者是考试的重点和难点。计算题考的就是理解，而代码题考的则是在理解的基础上进一步运用。三者相辅相成，构成了考试的主要内容，成为客观检测学生掌握相应知识的度量。

概念

1. 数据元素、数据项、数据对象、数据类型、数据结构的概念。
2. 数据结构三要素
3. 什么是数据的逻辑结构?数据的逻辑结构分为几种？
4. 什么是数据的存储结构？数据的存储结构有哪几种？这几种存储结构各有什么优缺点？
5. 什么是数据的运算？
6. 什么是算法？算法具有哪五种特性？五种特性的具体内容是什么？
7. 一个好的算法应该具有哪四个特性？
8. 算法的时间复杂度和空间复杂度是什么？
9. 常见的时间复杂度大小比较。

考点：时间复杂度

时间复杂度主要求两种，一种是循环下的时间复杂度，另一种就是递归下的时间复杂度。

错题1

过程：需要看递归调用的次数，所以选c

如果改一改递归函数的内部，时间复杂度也会发生改变：

错题2

每一次调用的都是前一个，所以是选B

错题3

既要看外层i的变化，又要看内层j的变化

可以看出，最后求出来的时间复杂度是介于n-1和2n-1的，所以本题选B。

应用——分析求解斐波那契数列用到的两种算法的时间复杂度

求解斐波那契数列
$$F(n)=\{\begin{array}{ll}0& \text{if }n=0\\ 1& \text{if }n=1\\ F(n-1)+F(n-2)& \text{if }n\ge 2\end{array}$$
有两种常用的算法：递归算法和非递归算法。试分别分析两种算法的时间复杂度。

算法一：递归算法

C语言代码如下：

//斐波那契数列 
#include <stdio.h>

int Function1(int n) { //递归算法 
	if(n == 0 || n == 1) {
		return n;
	}
	else{
		return Function1(n-1) + Function1(n-2);
	}	  
	//算法时间复杂度为O(),空间复杂度为O(1)  
}
 
int main() {
	int i;
	printf("斐波那契数列的前十个数字是：\n");
	for(i = 0; i < 10; i++) {
		printf("%d ", Function1(i));
	}
	return 0;
} 

递归算法的时间复杂度是$O(2^n)$，空间复杂度是$O(n)$

可以看出整个过程是一个递归调用树，在这个过程中有大量的重复计算：F(n-2) 的计算次数是2次，F(n-3) 的计算次数是3次，最终时间复杂度是指数级的；每个递归调用占用 O(1) 空间，最大递归深度是n，所以空间复杂度为O(n)。
可以从减少重复计算的角度来改进递归算法。如下所示：

int memo[100] = {0}; //全局备忘录数组
int Function1_optimized(int n) {
if(n == 0 || n ==1) return n;
if(memo[100]!=0) return memo[n]; //使用缓存结果
memo[n] = Function1_optimized(n-1) + Function1_optimized(n-2);
return memo[n];
}

这样时间复杂度就降为了O(n)，空间复杂度仍未O(n)。

算法二：非递归算法

C语言代码如下：

//斐波那契数列 
#include <stdio.h>
int Function2(int n) { //非递归算法
	int a[999], j;
	a[0] = 0;
	a[1] = 1;
	for(j = 2; j < n+1; j++) {
		a[j] = a[j-1] + a[j-2];
	} 
	return a[n];
	//算法时间复杂度为O(n),空间复杂度也为O(n) 
}
 
int main() {
	int i;
	printf("斐波那契数列的前十个数字是：\n");
	for(i = 0; i < 10; i++) {
		printf("%d ", Function2(i));
	}
	return 0;
} 

时间复杂度就不用说了，从2到n，时间复杂度为O(n)；辅助空间是数组显然也是O(n)。
还可以进一步改进，使得空间复杂度变为O(1)。

int Function2_optimized(int n) {
	if (n < 0) return -1;
	if (n == 0) return 0;
	int a = 0, b = 1;
	int i, temp;
	for(i = 2; i <= n; i++) {
		temp = a + b;
		a = b;
		b = temp;
	}
	return temp;
}