数据结构期末复习-2014

数据结构期末复习与习题课

第一章绪论

1．什么是数据结构、逻辑结构、存储结构、运算？数据结构三方面的含义？数据结构的定义定义1----P1

数据元素之间的关系（逻辑关系）称为结构，带有结构的数据元素的集合称为数据结构。定义2----

按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。数据结构的三个方面的含义：（1）逻辑结构---

数据元素间抽象化的相互关系（简称为数据结构）。

与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。（2）存储结构（物理结构）----

数据元素及其关系在计算机存储器中的存储方式。

是逻辑结构用计算机语言的实现，它依赖于计算机语言。（3）运算（算法）

2、算法的概念，算法必须满足的准则

所谓算法（Algorithm)是描述计算机解决给定问题的操作过程（解题方法），即为解决某一特定问题而由若干条指令组成的有穷序列。一个算法必须满足以下五个准则：

（1）有穷性---执行了有限条指令后一定要终止。

（2）确定性（无二义）---算法的每一步操作都必须有确切定义，不得有任何歧义性。（3）可（能）行性---算法的每一步操作都必须是可行的，即每步操作均能在有限时间内完成。

（4）输入数据---一个算法有n（n>=0)个初始数据的输入。

（5）输出数据---一个算法有一个或多个与输入有某种关系的有效信息的输出。思考：算法与程序有何区别？

3、对算法进行简单分析的评价准则算法的评价准则

首先，算法必须是“正确”的，其次：

（1）执行算法所耗费的时间（效率要高）。

（2）执行算法所耗费的存储空间（主要考虑辅存空间；低存储要求）。（3）算法的可读性、易维护性要好（易于理解，易于编码，易于调试）。

4、什么是问题的规模？时间复杂度？渐近时间复杂度？

（1）问题的规模（size)---算法求解问题的输入量（或初始数据量）。不考虑机器软硬件环境时算法的时间耗费：设：执行每条语句所需时间为单位时间，则：一个算法耗费的时间=所有语句的频度之和。

TOP相关主题