文档介绍：算法与数据结构
公共基础第一部分
本章考核内容约占13%,主要包括一下几个方面:
算法复杂度
栈、队列、线性链表的基本概念
树的结点计算和遍历
排序的最坏次数计算
考点1 算法的基本概念
。
对于一个问题,如果可以通过一个计算机程序,在有限的存储空间内运行有限的时间而得到正确的结果,则称这个问题是可解的。
:
1)可行性
2)确定性
3)有穷性:即算法必须能在执行有限个步骤之后终止
4)拥有足够的情报
考点1 算法的基本概念
【2008年4月】:算法的有穷性是指( )
A)算法程序的运行时间是有限的
B)算法程序所处理的数据量是有限的
C)算法程序的长度是有限的
D)算法只能被有限的用户使用
答案
A
考点1 算法的基本概念
一个算法通常由两种基本要素组成:一是对数据对象的运算和操作;二是算法的控制结构。
一般的计算机系统中,基本运算和操作包括以下4类:
①算术运算:加、减、乘、除等运算;
②逻辑运算:与、或、非等运算;
③关系运算:等于、不等于、大于、小于等运算;
④数据传输:赋值、输入、输出等操作。
考点1 算法的基本概念
算法的控制结构
算法各操作之间的执行顺序称为算法的控制结构。
算法的控制结构包括:顺序、选择(分支)和循环。
考点1 算法的基本概念
计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。
①列举法;
②归纳法;
③递推;
④递归;
⑤减半递推技术;
⑥回溯法。
考点2 算法的复杂度☆
算法的复杂度包括算法时间复杂度和算法空间复杂度。
算法时间复杂度是指执行算法所需要的计算工作量。
在度量一个算法的工作量时,用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。
分析算法工作量的方法:平均性态和最坏情况复杂性。
考点2 算法的复杂度☆
一个算法的空间复杂度,一般是指执行这个算法所需要的内存空间大小。
一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的空间以及算法执行过程中所需要的额外空间。
考点2 算法的复杂度☆
【2005年9月】:
算法复杂度主要包括时间复杂度和_______复杂度。
【2006年9月】:下列叙述中正确的是( )
A)一个算法的空间复杂度大,则其时间复杂度也必定大
B)一个算法的空间复杂度大,则其时间复杂度必定小
C)一个算法的时间复杂度大,则其空间复杂度必定小
D)上述三种说法都不对
答案
D
空间