数据结构c语言版题集答案(严蔚敏)，数据结构c语言版严蔚敏考研网课

蔚敏《数据结构》笔记与习题第一章详解绪论

一.什么是数据结构

数据结构是研究非数值计算编程问题中计算机的操作对象以及它们之间的关系和操作等的学科。

二.基本概念和术语

1数据

数据是表示客观事物的符号，是计算机科学中可以输入计算机，由计算机程序处理的符号的总称。

2数据要素

数据要素是数据的基本单位。

3数据对象

数据对象是性质相同的数据元素的集合，是数据的子集。

4数据结构

数据结构是相互之间具有一个或多个特定关系的数据元素的集合。

数据结构的基本结构

根据数据元素之间关系的特性，通常有四种基本结构：

聚在一起。 数据元素属于“同一集合”，没有其他复杂的关系。

线性结构。 数据要素之间存在一对一的关系。

树形结构。 数据元素之间有多个关系。

图状结构或网状结构。 数据元素之间存在多对关系。

【注意】区分这四种基本结构取决于元素之间的对应关系。

图1-1表示上述4种基本结构的关系图。

静业学习网

图1-1类基本结构关系图

数据结构的形式定义

数据结构的格式定义如下：

Data_Structure=(D，s )

在此，d表示数据要素的有限集合，s表示d上的关系的有限集合。

在计算机中查看数据结构

数据结构包括数据元素的表示和关系，在计算机中称为数据的物理结构。

在这里，关系有顺序映射和非顺序映射两种表现方法。 这两种表示方式支持两种存储结构：顺序存储结构和链式存储结构。

a .顺序映射：用相对位置表示数据要素间的逻辑关系。

b .非顺序图像：用指针表示数据要素之间的逻辑关系。

5数据类型

数据类型是值的集合和为该值的集合定义的一组操作的总称。

6抽象数据类型

抽象数据类型由值域和为该值域定义的一组操作组成。

【注意】抽象数据类型是数据类型体系结构的全局表示，可以更清晰地看到某些数据类型。

7多形数据类型

多边形数据类型是指其值的成分不确定的数据类型。

8数据操作的类型

基本操作如下

插入

删除

更新

搜索

排序

从操作的特性来看，所有操作可以归纳为两类。

加工模具操作：改变了结构的值

引用型操作：也就是说，在不改变结构值的情况下，只需检查或求出结构的值即可。

在上述5个操作中，除了\”检索\”是引用型操作以外，都是加工型操作.

9演算法

【定义】算法是解决特定问题的过程的说明，是指令的有限序列，每个指令表示一个或多个操作。

【特性】

有穷性

确定性

可行性

输入

输出功率

【注意】在试验中这五个特性可能出现在选材或填空题上。

三.抽象数据类型的表示与实现

四.算法和算法分析

1算法说明

算法需要用语言描述，可以用程序框图、编程语言等描述算法。

【注意】在应试笔试中，在对应语法不确定的情况下，通常也可以使用伪代码。

2算法设计要求

正确性

易读性

顽强性

效率和低存储需求

3算法效率的测量

算法的执行时间是根据该算法编写的程序在计算机上执行时所消耗的时间来测量的。 通常有两种方法来测量程序的执行时间。

事后统计

事前分析估计

提前考虑消耗时间的因素

时间的复杂性

时间复杂度是有关问题规模的函数，通常用o表示。 典型的时间复杂度按如下方式逐级增加：

O&lt； O&lt； O&lt； O&lt； O&lt； O&lt； O&lt； O&lt； O&lt； o

【注意】需要对具体算法进行时间复杂度的分析和计算，尤其是在研究生院，算法的时间复杂度计算是不可避免的。

4算法的存储容量要求

算法的空间复杂性是空间在算法运行中所占的尺度。

测量时，一般只考虑算法运行所需的开销量、算法安装时定义的中间变量、数组等对存储区域的影响。

当场工作：算法运行所需的额外空间对于输入数据量是一定的。