全国计算机等级考试真题(笔试+上机)详解与样题精选二级公共基础知识+VisualBasic第1章数据结构与算法第1章数据结构与算法考点1算法★★考点点拨：主要考查算法的基本概念、算法的时间复杂度和空间复杂度。【试题1】问题处理方案的正确而完整的描述称为。(2005年4月)答案：算法分析：算法给出了问题处理方案的准确而完整的描述。【试题2】算法具有4个特性，以下选项中不属于算法特性的是______。A)有穷性B)简洁性C)可行性D)确定性答案：B分析：算法的4个特性是：确定性，可行性，有穷性，拥有足够的情报。【试题3】算法的复杂度主要包括时间复杂度和_______复杂度。(2005年9月)答案：空间分析：算法复杂度主要包括时间复杂度和空间复杂度。时间复杂度用来描述执行算法所需要的计算工作量，空间复杂度用来描述执行算法所需要的内存空间。【试题4】算法的时间复杂度是指。A)执行算法程序所需要的时间B)算法程序的长度C)算法执行过程中所需要的基本运算次数D)算法程序中的指令条数答案：C分析：所谓算法的时间复杂度，是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即：算法的工作量=f(n)。其中n是问题的规模。理论链接：算法时间复杂度在具体分析一个算法的工作量时，还会存在这样的问题：对于一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关，而实际上又不可能将所有可能情况下算法所执行的基本运算次数都列举出来。例如，“在长度为n的一维数组中查找值为x的元素”，若采用顺序搜索法，即从数组的第一个元素开始，逐个与被查值x进行比较。显然，如果第一个元素恰为x，则只需要比较1次。但如果x为数组的最后一个元素，或者x不在数组中，则需要比较n次才能得到结果。因此，在这个问题的算法中，其基本运算(即比较)的次数与具体的被查值x有关。【试题5】算法的空间复杂度是指。A)算法程序的长度B)算法程序中的指令条数C)算法程序所占的存储空间D)算法执行过程中所需要的存储空间答案：D分析：一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间(例如，在链式结构中，除了要存储数据本身外，还需要存储链接信息)。如果额外空间量相对于问题规模来说是常数，则称该算法是原地(inplace)工作的。在许多实际问题中，为了减少算法所占的存储空间，通常都会采用压缩存储技术，以尽量减少不必要的额外空间。【试题6】一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是算法的。答案：控制结构分析：一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。理论链接：(1)算法中对数据的运算和操作每个算法实际上是按解题要求，从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。因此，计算机算法就是计算机能处理的操作所组成的指令序列。通常，计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列。在一般的计算机系统中，基本的运算和操作有以下4类。①算术运算：主要包括加、减、乘、除等运算。②逻辑运算：主要包括“与”、“或”、“非”等运算。③关系运算：主要包括“大于”、“小于”、“等于”、“不等于”等运算。④数据传输：主要包括赋值、输入、输出等操作。(2)算法的控制结构一个算法的功能不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序即称为算法的控制结构。算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且还直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般可以用顺序、选择、循环3种基本控制结构组合而成。【试题7】在同一个问题规模下，如果算法执行所需的基本运算次数取决于某一特定输入时，可以用平均性态和两种方法来分析算法的工作量。答案：最坏情况复杂性分析：所谓平均性态分析，是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。设x是所有可能输入中的某个特定输入，p(x)是x出现的概率(即输入为x的概率)，t(x)是算法在输入为x时所执行的基本运算次数，则算法的平均性态定义为：A(n)=其中Dn表示当