1.1数据结构与算法
考点1算法
1.算法的基本概念
算法是指对解题方案准确而完整的描述。
(1)算法的基本特征
考核概率为45%。该知识点属于熟记内容,考生要熟记算法的概念,以及时间复杂度和空间复杂度的概念。可行性:针对实际问题而设计的算法,执行后能够得到满意的结果,即必须有一个或多个输出。注意：即使某一算法在数学理论上是正确的,但如果在实际的计算工具上不能执行,则该算法也是不具有可行性的。
确定性:指算法中每一步骤都必须是有明确定义的。
有穷性:指算法必须能在有限的时间内做完。
拥有足够的情报:一个算法是否有效,还取决于为算法所提供的情报是否足够。
(2)算法的基本要素
算法一般由两种基本要素构成:
对数据对象的运算和操作;
算法的控制结构,即运算和操作时间的顺序。
算法中对数据的运算和操作:算法就是按解题要求从指令系统中选择合适的指令组成的指令序列。因此，计算机算法就是计算机能执行的操作所组成的指令序列。不同的计算机系统,其指令系统是有差异的,但一般的计算机系统中都包括的运算和操作有4类,即算术运算、逻辑运算、关系运算和数据传输。
算法的控制结构:算法中各操作之间的执行顺序称为算法的控制结构。算法的功能不仅取决于所选用的操作,还与各操作之间的执行顺序有关。基本的控制结构包括顺序结构、选择结构和循环结构。
(3)算法设计的基本方法
算法设计的基本方法有列举法、归纳法、递推法、递归法、减半递推技术和回溯法。
2.算法复杂度
算法复杂度主要包括时间复杂度和空间复杂度。
(1)算法的时间复杂度
所谓算法的时间复杂度,是指执行算法所需要的计算工作量。
一般情况下,算法的工作量用算法所执行的基本运算次数来度量,而算法所执行的基本运算次数是问题规模的函数,即
算法的工作量=f（n）
其中n是问题的规模。这个表达式表示随着问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同。
在同一个问题规模下,如果算法执行所需的基本运算次数取决于某一特定输入,可以用两种方法来分析算法的工作量:平均性态分析和最坏情况分析。
(2)算法的空间复杂度
一个算法的空间复杂度,一般是指执行这个算法所需要的内存空间。算法执行期间所需要的存储空间包括以下3个部分。
算法程序所占的空间;
输入的初始数据所占的存储空间;
算法执行过程中所需要的额外空间。
在许多实际问题中,为了减少算法所占的存储空间,通常采用压缩存储技术。
考点2数据结构的基本概念1.数据结构的定义
数据结构是指相互有关联的数据元素的集合,即数据的组织形式。
考核概率为45%。该知识点属于熟记内容，考生要熟记数据结构的定义、分类,能区分线性结构与非线性结构。(1)数据的逻辑结构
所谓数据的逻辑结构,是指反映数据元素之间逻辑关系（即前、后件关系）的数据结构。它包括数据元素的集合和数据元素之间的关系。
(2)数据的存储结构
数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称为数据的物理结构）。数据结构的存储方式有顺序存储方法、链式存储方法、索引存储方法和散列存储方法。而采用不同的存储结构,其数据处理的效率是不同的。因此,在进行数据处理时,选择合适的存储结构是很重要的。
数据结构研究的内容主要包括3个方面：
数据集合中各数据元素之间的逻辑关系,即数据的逻辑结构;
在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;
对各种数据结构进行的运算。
2.数据结构的图形表示
数据元素之间最基本的关系是前、后件关系。前、后件关系即每一个二元组,都可以用图形来表示。用中间标有元素值的方框表示数据元素,一般称之为数据节点,简称为节点。对于每一个二元组,用一条有向线段从前件指向后件。
用图形表示数据结构具有直观、易懂的特点，在不引起歧义的情况下,前件节点到后件节点连线上的箭头可以省去。例如,树形结构中,通常是用无向线段来表示前、后件关系的。
3.线性结构与非线性结构
根据数据结构中各数据元素之间前、后关系的复杂程度,一般将数据结构分为两大类型,即线性结构和非线性结构。
如果一个非空的数据结构有且只有一个根节点,并且每个节点最多有一个直接前驱或直接后继,则称该数据结构为线性结构,又称线性表。不满足上述条件的数据结构称为非线性结构。
小提示需要注意的是,在一个线性结构中插入或删除任何一个节点后还应该是线性结构;否则,不能称之为线性结构。
下列叙述中正确的是()。
A.程序执行的效率与数据的存储结构密切相关
B.程序执行的效率只取决于程序的控制结构
C.程序执行的效率只取决于所处理的数据量
D.以上3种说法都不对
【答案】 A
【解析】在计算机中,数据的存储结构对数据的执行效率有较大影响,如在有序存储的表中查找某个数值比在无序存储的表中查找的效率高很多。
书单推荐
