【计算机二级考试】MS Office 高级应用与设计选择题2.1 算法与数据结构基础

算法不等于数学上的计算方法，也不等于程序。算法可以用某种表达方式(如流程图）描述，也可以用具体的程序设计语言描述（编写程序）。算法设计必须考虑执行算法所需要的资源(不仅要考虑对数据对象的运算和操作，还要考虑算法的控制结构)，即降低时间与空间复杂度。算法的优劣取决于算法复杂度，与程序的环境无关，当算法被编程实现之后，程序的运行受到计算机系统运行环境的限制。

算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。一般来说，计算机算法是问题规模n的函数f(n)，即算法的复杂度与问题的规模相关。

算法优化一般是对算法结构和收敛性进行优化。

算法的评价主要用时间复杂度（计算的工作量）和空间复杂度（算法所需要的内存空间）来衡量。为了降低算法的空间复杂度，主要应减少输入数据所占的存储空间以及额外空间，通常采用压缩存储技术。

算法的基本特征

有穷性，算法的有穷性是指算法必须能在执行有限个步骤之后终止；

确定性，算法的每一步骤必须有确切的定义；

输入项，一个算法有0个或多个输入；

输出项，一个算法有一个或多个输出，没有输出的算法是毫无意义的；

可行性，算法中的每个计算步骤都可以在有限时间内完成。

算法的空间复杂度，一般是指执行这个算法所需要的内存空间。与数据的存储结构有关。算法执行期间所需的存储空间包括3个部分:

输入的初始数据所占的存储空间;

算法程序本身所占的存储空间;

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

算法的时间复杂度是指执行算法所需要的计算工作量，是用算法所执行的基本运算次数来度量的，与计算机运行速度和计算机存储空间无关。

算法的时间复杂度与空间复杂度没有直接关系。

数据的存储结构直接决定数据的输入，而这会影响算法所执行的基本运算次数，影响算法的效率。

数据的逻辑结构是指反映数据元素之间逻辑关系(即前后件关系)的数据结构；数据的存储结构是数据的逻辑结构在计算机存储空间中的存放方式。数据元素在计算机存储空间中的位置关系可能与逻辑关系不同。

数据元素是数据的“基本单位”，在计算机中通常作为一个整体进行考虑和处理，数据元素可以是另一数据结构。

点击查看微课程

1.下列叙述中正确的是（C )。

A、算法的复杂度与问题的规模无关

B、算法的优化主要通过程序的编制技巧来实现

C、对数据进行压缩存储会降低算法的空间复杂度

D、数值型算法只需考虑计算结果的可靠性

2.下列关于算法的描述中错误的是（D）。

A、算法强调动态的执行过程，不同于静态的计算公式

B、算法必须能在有限个步骤之后终止

C、算法设计必须考虑算法的复杂度

D、算法的优劣取决于运行算法程序的环境

3.算法空间复杂度的度量方法是（D )。

A、算法程序的长度

B、算法所处理的数据量

C、执行算法所需要的工作单元

D、执行算法所需要的存储空间

4.下列叙述中正确的是（D )。

A、算法复杂度是指算法控制结构的复杂程度

B、算法复杂度是指设计算法的难度

C、算法的时间复杂度是指设计算法的工作量

D、算法的复杂度包括时间复杂度与空间复杂度

5.下列叙述中正确的是（B )。

A、算法的效率只与问题的规模有关，而与数据的存储结构无关

B、算法的时间复杂度是指执行算法所需要的计算工作量

C、数据的逻辑结构与存储结构是一一对应的

D、算法的时间复杂度与空间复杂度一定相关

6.下列叙述中正确的是（D )。

A、有且只有一个根结点的数据结构一定是线性结构

B、每一个结点最多有一个前件也最多有一个后件的数据结构一定是线性结构

C、有且只有一个根结点的数据结构一定是非线性结构

D、有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构

7.下列叙述中正确的是（ A)。

A、数据的处理效率与数据的存储结构有关

B、算法时间复杂度的度量与计算机运行速度有关

C、算法空间复杂度的度量与数据的存储结构无关

D、算法时间复杂度的度量与计算机存储空间有关

8. 算法的有穷性是指（D )。

A、算法程序所处理的数据量是有限的

B、算法程序的长度是有限的

C、算法只能被有限的用户使用

D、算法程序的运行时间是有限的

9.下列叙述中正确的是（B )。

A、所谓算法就是计算方法

B、程序可以作为算法的一种描述方法

C、算法设计只需考虑得到计算结果

D、算法设计可以忽略算法的运算时间

10.下列叙述中正确的是（A )。

A、采用顺序存储的完全二叉树属于非线性结构

B、循环队列是队列的一种存储结构，它属于非线性结构

C、具有多个指针域的链表一定属于非线性结构

D、具有两个以上根结点的数据结构有可能是线性结构

11.下列叙述中错误的是（ B)。

A、数据结构中的数据元素可以是另一数据结构

B、数据结构中的数据元素不能是另一数据结构

C、空数据结构可以是线性结构也可以是非线性结构

D、非空数据结构可以没有根结点

12.下列结构中为非线性结构的是（A )。

A、树

B、向量

C、二维表

D、矩阵

13.设数据元素的集合D=，则满足下列关系R的数据结构中为线性结构的是(B）。

A、R={(1,2),(3,4),(5,1)}

B、R={(1,3),(4,1),(3,2),(5,4)}

C、R={(1,2),(2,3),(4,5)}

D、R={(1,3),(2,4),(3,5)}

二叉树属于非线性结构。循环队列属于线性结构，双向链表属于线性结构；向量、二维表、矩阵均为线性结构

不满足以上两个条件的数据结构就称为非线性结构。关系R元素，每个括号里的两个数代表的是前后件关系。选项A的R中，（1,2）表示1是2的前前件；（5,1）表示5是1的前件，由此可以画出一个线性结构，而（3,4）与它们没有前后件关系，由此可以判断出，这个关系R的数据结构中有两个根节点，分别是和，不满足线性结构条件，是非线性结构。同理，可以判断出C和D选项，均为非线性结构。选项B，关系R中的数据元素排列顺序为，满足线性结构条件属于线性结构。