“数据结构”专接本复习纲要(1)

《“数据结构”专接本复习纲要(1)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、“数据结构”专接本复习纲要第一章数据结构概论一、数据与信息1、什么是数据数据是对人类各种活动内容的详细记录。（只是事实的记录，没有特定的目的）2、什么是信息信息是指对某一特定目的而言，具有意义的事实与知识。（信息由数据处理而得）3、数据类型数据类型可以认为是对具有相同构造特征和操作特性的数据集合的一种抽象描述。对考试来说，重要的是了解和掌握C语言所提供的各种数据类型的使用。二、数据处理1、什么是数据处理数据处理是通过人力或机器，将收集到的数据加以系统的处理，归纳出有价值的信息。2、常用的数据处理方式(1)编辑（2）排序（3）归并（4

2、）分配（5）建档（6）更新（7）计算（8）链表（9）查找（10）查询（11）其它（如分类、摘要、变换等）三、程序和算法1、程序产生的五个阶段（1）需求（了解、分析）“数据结构“专接本复习纲要第1章第50页共6页（2）设计（算法）（3）分析（哪种方案最佳）（4）细化与编码（5）验证2、什么是算法、算法的描述、算法的时间复杂度算法是对解决所处理问题的方法和步骤的一种描述，是一个有限的指令序列。算法的描述方法可以是自然语言、形式化的图表（流程图、N-S图、PAD图等）、伪代码语言、程序设计语言等。算法的时间复杂度是指实现算法所需要花费的时

3、间。3、影响程序执行时间的因素（1）程序所输入的数据量多少（2）程序所使用的算法（3）编译器所产生机器代码的优劣（4）指令在机器中的执行速度显然，（3）和（4）与所使用的具体机器和编译工具有关，而与算法本身的好坏没有直接的联系。所以，在分析算法的时间性能时，不考虑所使用的机器和编译器。4、算法时间复杂度的分析在程序中，算法的实现是通过一个个语句的执行来体现的。而影响语句执行所需要的时间由语句执行的次数和执行一次语句所需要的时间这两个因素确定的。语句执行的时间是以上两者的乘积。显然，语句执行一次的时间与具体使用的编译器和机器硬件有关。

4、由于我们在分析算法的时间复杂度时，不考虑编译器和硬件的因素，所以，在分析算法的时间复杂度时，依据的是语句执行的次数，尤其是嵌套在最内层的基本语句。“数据结构“专接本复习纲要第1章第50页共6页算法中语句执行的次数又往往是和所处理问题的规模有关，所谓算法的问题规模指的是输入的数据量。所以，算法的时间复杂度往往是算法问题规模的函数。例，求两个N阶方阵的乘积C=A*B，算法如下：#defineN100/*假设N的值是100*//*这里的N就是下列算法的问题规模*/voidmat_mul(intA[N][N],intB[N][N],intC

5、[N][N]){inti,j,k;(1)for(i=0;i

6、见的算法时间复杂度函数表示按时间性能从优到劣有O(1)O(log2N)O(N)O(Nlog2N)O(N2)…O(2N)O(N!)练习，分析下列程序段的时间复杂度x=0;for(i=1;i<=n;i++)for(j=1;j<=i;j++)“数据结构“专接本复习纲要第1章第50页共6页x+=2*i+3*j;四、数据结构概念1、什么是数据结构数据结构是相互之间存在一种或多种特定关系的数据元素的集合。（摘自严蔚敏著的《数据结构》）我们目前学习的数据结构涉及的是有限集合。这告诉我们，数据结构所研究的诸元素之间是存在一定的关系的。2、什么是数据

7、的逻辑结构数据的逻辑结构指的是数据结构所研究的数据元素之间的逻辑关系，有时也叫数据结构的逻辑结构。数据的逻辑结构与具体的计算机无关。数据的逻辑结构可以分为线性结构和非线性结构两大类。线性结构体现了元素之间一个挨一个的次序关系。我们所学习的线性结构主要有线性表、栈、队列、一维数组等。我们所学习的非线性结构主要有树型结构、图（网）状结构。树型结构体现了元素之间一对多的层次关系。图（网）状结构体现了元素之间多对多的网状关系。3、什么是数据的物理结构（存储结构）数据的物理结构（又叫存储结构）是指数据结构在计算机中的表示。这里的表示可理解为存

8、储的意思，而这个存储包含了两个方面的含义，一个是存储数据元素的值本身，另一个是这种存储要能体现数据元素之间的逻辑关系。顺序存储结构和链式存储结构是两种常见的存储结构。它们表示数据元素之间逻辑关系的方法是不同的。“数据结构“专接本复习纲