第1章数据结构与算法笔试题考点分析

计算机公共基础

1算法考试的内容：

1.1 算法的基本概念

1．算法的概念(必记)：

是指解题方案的准确而完整的描述。

分析：要用计算机实现某一任务时，先应设计出一整套解决问题的指导方案，然后具体实现。整套的指导方案称之为算法，而具体的实现称之为程序。并且在设计指导方案时，可不用过多考虑到实现程序的具体细节(即可以一点点的理想化)，但在程序实现时，必须受到具体环境的约束(现实不同于理想)。

结论：

2．算法的基本特征(必记)：

由于算法总是在某个特定的计算工具上实现并执行的，因而受到计算工具的限制，所以在设计算法时，要考虑到设计的算法是否是可性的。

b.确定性：算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。

算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。算法有相应的初始数据。

3．算法的基本要素：

一个算法通常由两个基本要素所组成：一是对数据对象的运算和操作，二是算法的控制结构。基本运算和操作分为四类：

a. 算术运算: (加、减、乘、除等运算)

b. 逻辑运算: (与、或、非等运算)

c. 关系运算: (大于、小于、等于、不等于等运算)

d. 数据传输: (赋值、输入、输出等操作) 算法的控制结构：

算法中各操作之间的执行顺序称之为算法的控制结构。循环三种基本控制结构组合而成。

注意：一个计算机系统能执行的所有指令的集合，称为该计算机系统的

4．算法设计基本方法：

列举法、归纳法、递推、递归、减半递推技术、回溯法。

1.2 算法的复杂度 (必记)

算法的复杂度

1．算法的时间复杂度：

是指执行算法所需要的计算工作量，是由算法所执行的基本运算次数来度量。

可用平均性态和最坏情况两种分析方法。其中平均性态分析是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量；而最坏情况分析是指在所有特定输入下的基本运算次数据的最大次数。

TOP相关主题