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