xianligongdaxue——————863数据结构
需积分: 9 3 浏览量
2020-12-17
10:27:26
上传
评论 1
收藏 8.36MB DOCX 举报
第一章 绪论
考试大纲
1）了解数据元素、数据结构、抽象数据类型、存储结构等概念；了解算法概念及算法设计的基本要求 ；
2）掌握算法分析方法、语句的频度和估算时间复杂度、空间复杂度分析方法。
考查要点
1．数据结构的研究内容
包括 数据的逻辑结构、数据的存储结构 和 对数据元素施加的操作（即数据的运算）三方面。
2．算法概念及其评价
五大特性：有穷性、确定性、可行性、输入性、输出性;
算法评价：正确性、可读性、健壮性、高效性、低存储性;
要特别弄清诸如语句频度、时间复杂度、空间复杂度等的概念，评价一个算法好坏的两个主要标准--时间复杂度和空间复杂度。
3．算法和程序的区别
a. 程序不一定满足有穷性(如操作系统)；
b. 程序中的指令必须是机器可执行的，算法中的指令则无此限制；
c. 算法代表了对问题的解，程序则是算法在计算机上的特定的实现(一个算法若用程序设计语言来描述，它才是一个程序);
d. 数据结构+算法=程序。
4．数据结构的相关概念
数据结构包括 数据的逻辑结构 和 数据的存储结构。
数据元素 是组成数据的基本单位。
数据项 是数据不可分割的最小单位。
数据逻辑结构的两大类型（线性结构、非线性结构）、抽象数据类型（是指一个数学模型以及定义在该模型上的一组操作）。
数据的四种逻辑结构（集合、线性、树形、图形）
数据的四种存储结构（顺序、链式、索引、散列）
不管是顺序存储结构还是链式存储结构，都要存储数据元素本身和数据元素之间的关系
顺序存储结构、链式存储结构都可存各种逻辑结构
5．数据逻辑结构、存储结构的区别和联系
区别：数据的逻辑结构是一个数学模型；数据的存储结构是数据的逻辑结构在计算机内部的存储方式。
联系：一种逻辑结构可以用多种存储结构来存储；一种存储结构可以用来存多种逻辑结构。
课后习题
1. 数据结构包括 数据的逻辑结构、数据的存储结构 和 数据的运算。
2. 数据的逻辑结构可以分为 线性 和 非线性 两大类型。
3. 在算法正确的前提下，评价一个算法好坏的两个主要标准是 时间复杂度 和 空间复杂度。
4. 对于给定的 n 个元素,可以构造出的逻辑结构有线性、树形、图形 和 集合 四种。
5. 数据的存储结构不仅有顺序存储结构、链式存储结构，还有 索引存储结构 和 散列存储结构。
6. 组成数据的基本单位是 数据元素。
7. 数据结构的两个要素是 数据元素 和 数据元素之间的关系。
8. 语句频度是 语句重复执行的次数。
9. 算法是 对特定问题求解步骤的一种描述，是指令的有限序列。
10. 数值计算问题是 操作对象之间的关系可以用数学方程加以描述的问题 ；非数值计算问题是 操作对象之间的关系不能用数
学方程加以描述的问题。
1
剩余63页未读，继续阅读
评论0