计算机二级考试公共基础知识精讲.docxVIP

计算机二级考试公共基础知识精讲

2019年计算机二级考试公共基础知识精讲

数据结构与算法

1.算法是指对解题方案的准确而完整的描述，简单地说，就是解决问题的操作

步骤。

2.算法不等于数学上的计算方法，也不等于程序。

3.在编程时由于要受到计算机系统运行环境的限制，因此，程序的编制通常不

可能优于算法的设计。

4.算法的基本特征：

●可行性：算法在特定的执行环境中执行应当能够得出满意的结果，即必

须有一个或多个输出。

●确定性：算法中每一步的描述都是明确的，没有多义性。

●有穷性：法中的操作步骤为有限个，且每个步骤都能在有限时间内完成。

●拥有足够的情报：一般来说，算法在拥有足够的输入信息和初始化信息

时，才是有效的；当提供的情报不够时，算法可能无效。

5.一个算法通常由两种基本要素组成：

●对数据对象的运算和操作；

●算法的控制结构，即运算或操作间的顺序。

6.在计算机上，可以直接执行的基本操作通常都是用指令来描述的，每个指令

代表一种或几种操作。

7.指令系统一个计算机系统能执行的所有指令的集合，称为计算机的指令系统。

8.指令系统是软件与硬件分界的一个主要标志，是软件与硬件之间相互沟通的

桥梁。

9.算法就是按解题要求从指令系统中选择合适的指令组成的指令序列。

10.算法的控制结构是算法中各个操作之间的执行顺序。

11.算法一般是由顺序、选择（又称分支）和循环（又称重复）3种基本结构组

合而成。

12.描述算法的工具有传统的流程图、N-S结构化流程图和算法描述语言等。

13.常用的几种算法设计方法有列举法、归纳法、递推法、递归法、减半递推技

术和回溯法。

14.一个算法的复杂度高低体现在运行该算法所需要的计算机资源的多少，所需

的资源越多，就说明该算法的复杂度越高；反之，所需的资源越少，则该算法的复杂度越低。计算机的资源，最重要的是时间和空间（即存储器）资源。

15.算法复杂度包括算法的时间复杂度和算法的空间复杂度。

16.算法的时间复杂度是指执行算法所需要的计算工作量。

17.值得注意的是：算法程序执行的具体时间和算法的时间复杂度并不是一致的。

算法程序执行的具体时间受到所使用的计算机、程序设计语言以及算法实现过程中的许多细节所影响。而算法的时间复杂度与这些因素无关。

18.算法的计算工作量是用算法所执行的基本运算次数来度量的。

19.可以用以下两种方法来分析算法的工作量：

●平均性态；

●最坏情况复杂性。

20.算法的空间复杂度是指执行这个算法所需要的内存空间。

21.算法执行期间所需的存储空间包括3个部分：

●输入数据所占的存储空间；

●程序本身所占的存储空间；

●算法执行过程中所需要的额外空间。

22.额外空间包括算法程序执行过程中的工作单元，以及某种数据结构所需要的

附加存储空间。

23.数据结构研究的内容包括3个方面：

●数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；

●在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存

储结构；

●对各种数据结构进行的运算。

24.数据元素是数据的“基本单位”。

25.数据是需要处理的数据元素的集合，一般来说，这些数据元素，具有某个共

同的特征。

26.所谓“结构”，就是关系，是集合中各个数据元素之间存在的某种关系（或

联系）。

27.数据结构分为数据的逻辑结构和数据的存储结构。

28.一个数据结构应包含以下两方面的信息：

●表示数据元素的信息；

●表示各数据元素之间的前后件关系的信息。

29.数据的逻辑结构指反映数据元素之间逻辑关系（即前后件关系）的数据结构。

30.数据的存储结构又称为数据的物理结构，是数据的逻辑结构在计算机存储空

间中的存放方式。

31.顺序存储结构：这种存储方式主要用于线性的数据结构，它把逻辑上相邻的

数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。

32.链式存储结构就是在每个结点中至少包含一个指针域，用指针来体现数据元

素之间在逻辑上的联系。

33.根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构划

分为两大类型：线性结构和非线性结构。

34.线性结构：一个非空的数据结构如果满足以下两个条件：①有且只有一个根

结点；②每一个结点最多有一个前件，也最多有一个后件。

35.非线性结构：不满足以上两个条件的数据结构就称为非线性结构，非线性结

构主要是指树形结构和网状结构。

36.在线性结构插入或删除任何一个结点后还应是线性结构；线性结构和非线性

结构在删除结构中的所有结点后，都会产生空的数据结构。

37.一个空的数据结构究竟是属于线性结构还是属于非线性结构，这要根据具体

情况来确定。如果对该数据结构的算法是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。

38.线性