|
|
知识路径： > 计算机科学基础 > 数据结构与算法基本概念 > 数据结构与算法 >
|
被考次数：2次
被考频率：低频率
总体答错率：50%
知识难度系数： 
|
由 软考在线 用户真实做题大数据统计生成
|
|
考试要求：熟悉
相关知识点：30个
|
|
|
|
|
|
|
随着计算机技术的飞速发展，再把计算机简单地看作是进行数值计算的工具，把数据仅理解为纯数值性的信息，就显得太狭隘了。现代计算机科学的观点，是把计算机程序处理的一切数值的、非数值的信息，乃至程序统称为数据（Data），而电子计算机则是加工处理数据（信息）的工具。
|
|
|
|
由于数据的表示方法和组织形式直接关系到程序对数据的处理效率，而系统程序和许多应用程序的规模很大，结构相当复杂，处理对象又多为非数值性数据。因此，单凭程序设计人员的经验和技巧已难以设计出效率高、可靠性强的程序。于是，就要求人们对计算机程序加工的对象进行系统的研究，即研究数据的特性以及数据之间存在的关系——数据结构（Date Structure）。
|
|
|
|
计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法（Algorithm）,最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。
|
|
|
|
计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。
|
|
|
|
|
|
|
|
数据（Data）是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述。
|
|
|
|
数据元素（Data Element）简称元素，是数据的基本单位，通常作为一个整体进行考虑和处理。对于一个文件而言，每个记录就是它的数据元素；对于一个字符串而言，每个字符就是它的数据元素。数据和数据元素是相对而言的。有时，一个数据元素可以由若干个数据项（Data Item）组成。
|
|
|
|
数据记录（Data Record）简称记录，它是数据处理领域组织数据的基本单位，数据中的每个数据元素在许多应用场合被组织成记录的结构。一个数据记录由一个或多个数据项组成，每个数据项可以是简单数据项，也可以是组合数据项。
|
|
|
|
关键项（Key Item）指的是在一个表或者文件中，若所有记录的某个数据项的值都不同，也就是每个值能唯一标识一个记录时，则可以把这个数据项作为记录的关键数据项，简称关键项。其中关键项的每一个值称做所在记录的关键字（Key Word或Key）。
|
|
|
|
数据处理（Data Processing）是指对数据进行查找、插入、删除、合并、排序、统计、简单计算、转换、输入、输出等的操作过程。
|
|
|
|
数据结构（Data Structure），简单地说，指数据以及相互之间的关系。它是研究数据元素（Data Element）之间抽象化的相互关系和这种关系在计算机中的存储表示（即所谓数据的逻辑结构和物理结构），并对这种结构定义相适应的运算，设计出相应的算法，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。
|
|
|
|
数据类型（Data Type）是对数据的取值范围、每一数据的结构以及允许施加操作的一种描述。换言之，它是一个值的集合和定义在这个值集上的一组操作的总称。
|
|
|
|
数据对象（Data Object）简称对象，是性质相同的数据元素的集合，是数据的一个子集。如25为一个整形数据对象，‘A’为一个字符数据对象等。
|
|
|
|
除了上述常见概念之外，数据结构还有许多别的概念，例如算法、线性结构、集合、图、树等，这些都将在以后的章节中一一介绍。
|
|
|
|
|
|
算法（algorithm）就是解决特定问题的方法。描述一个算法可以采用文字描述，也可以采用传统流程图、N-S图或PAD图等。作为一个算法应该具备以下5个特性：
|
|
|
|
|
|
.确定性。算法的每一步都应该具有确切的含义，没有二义性。
|
|
|
|
|
|
|
|
.输出。一个算法执行结束后至少要有一个输出量，表示算法对输入量进行运算和处理的结果。
|
|
|
|
注意，算法和程序是有区别的——程序未必能满足有穷性。在本书中，只讨论满足动态有穷的程序，因此“算法”和“程序”是通用的。
|
|
|
|
算法可以借助各种工具描述出来。一个算法可以是用自然语言、数字语言或约定的符号来描述，也可以用计算机高级程序语言来描述，如流程图、Pascal语言、C语言、伪代码或决策表等。下面以从n个元素中查找最大值为例，来讲解用流程图和伪代码这两种常见方法对算法的不同描述：
|
|
|
|
|
|
从n个整数元素中查找出最大值，若用流程图描述如下图所示。
|
|
|
|
|
|
|
|
|
|
除了可以用流程图描述之外，还可以用伪代码来进行描述。
|
|
|
|
|
|
|
|
一般地说，设计一个“好”的算法应该考虑达到以下目标。
|
|
|
|
（1）正确性（correctness）。算法应该是满足具体问题的需求。
|
|
|
|
（2）可读性（readability）。算法主要是为了便于人的阅读和交流。可读性好的算法有利于人的理解。
|
|
|
|
（3）健壮性（robustness）。指的是，当输入数据非法时，算法也能适当地做出反应或对它进行处理，而不会产生莫名其妙的输出结果。
|
|
|
|
（4）效率和低存储量需求。效率指的是算法执行的时间。对于同一个问题，执行时间短的算法效率高。存储量需求指的是算法执行过程中所需要的最大存储空间。
|
|
|
|
一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上，所需资源越多，该算法的复杂性越高；反之，所需资源越少，该算法的复杂性越低。其中最重要的就是算法的时间复杂性和空间复杂性。
|
|
|
|
一般情况下，算法中的基本操作重复执行的次数是问题规模n的某个函数f（n），算法的时间量度记作
|
|
|
|
|
|
它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同，称做算法的渐进时间复杂度（Asymptotic Time Complexity），简称时间复杂度。被称为问题的基本操作的原操作应是其重复执行次数和算法的执行时间成正比的原操作。语句的频度（Frequency Count）指的是该语句重复执行的次数。
|
|
|
|
和算法的时间复杂度类似的，空间复杂度（Space Complexity）指的是算法所需存储空间的量度，记作：
|
|
|
|
|
|
其中，n为问题的规模或大小。根据算法的时间复杂度和空间复杂度，可以对算法进行评价。
|
|
|
|
|
|
在计算机领域，一个算法实质上是针对所处理的问题的需要，在数据的逻辑结构和存储结构的基础上施加的一种运算。由于数据的逻辑结构和存储结构不是唯一的，在很大程度上可以由用户自行选择和设计，所以处理同一问题的算法也并不是唯一的。况且，即使是相同的逻辑结构和存储结构，算法的设计思想和技巧也不一定相同，编写出来的算法也大不相同。
|
|
|
|
学习数据结构就是要学会根据数据处理问题的需要，为待处理的数据选择合适的逻辑结构和存储结构，进而按照结构化、模块化以及面向对象的程序设计方法设计出比较满意的算法。
|
|
|
