数据结构基础知识（一）

1. 什么是数据结构？

数据：描述客观事物的数和字符的集合

数据项：具有独立含义的数据最小单位

数据对象：数据的一个子集

数据结构：数据 + 结构，即存在某种特定关系的数据元素的集合

2. 数据结构包括什么？

逻辑结构 logical structure （数据和元素逻辑关系）

存储结构 storage structure （数据的物理结构，存储表示）

运算 operation （施加在数据上的操作）

3. 逻辑结构是什么？如何表示？有哪些类型？

逻辑结构即数据和元素的逻辑关系

图表表示：图形表示时，一个结点对应一个数据元素，两结点之间带箭头连接表示相邻关系

二元组表示：B = （D，R）；R中序偶集合r中任意序偶 <x,y> 表示相邻关系，x 为 y 的前驱元素，y 为 x 的后继元素。若某个元素没有前驱元素，则称该元素为开始元素，若无后继元素，则称为终端元素。对称序偶在用图形表示逻辑关系时，用不带箭头连线表示

逻辑结构的类型有 集合 、线性结构 、树形结构 、图形结构 。

集合：除了同属于一个集合，别无其他关系

线性结构：数据元素存在一对一的关系，开始元素和终端元素都是唯一的，其余元素有且仅有一个前驱元素和后继元素，如线性表

树形结构：每个元素仅有一个前驱元素，除了终端元素，每个元素有一个或多个后继元素，如二叉树

图形结构：数据元素之间多对多关系，可能无开始元素和终端元素也可能有多个

4. 存储结构是什么？有哪些存储结构？

存储结构即数据的物理结构，存储表示

顺序存储结构：将数据的逻辑结构直接映射到存储结构。

优点：存储效率高，可实现随机存取，由序号直接计算元素的存储地址

缺点：不便于数据修改，插入或删除需要移动一系列元素

Stud用于唯一标识顺序存储结构，作为数组的起始地址，Stud [i] 放在 Stud [i+1] 之前

链式存储结构：给每个结点附加指针域用于存放相邻结点的存储地址，也就是通过指针域将所有结点链接起来。

优点：便于数据修改，对元素插入删除仅需修改相应结点指针域，不必移动结点

缺点：存储空间利用率较低，不可随机存取

首结点指针为 head，尾结点指针域为空，一个结点的 next 指向 后继结点，每个结点采用 StudType 类型单独存储。

索引存储结构：存储数据元素信息的同时，建立附加的索引表

优点：查找效率高

缺点：需要建立索引表，增加空间开销

哈希存储结构：根据元素的关键字通过哈希函数直接计算一个值，并将这个值作为元素的存储地址（只适合要求对数据能够快速查找和插入的场合）

优点：查找速度快，根据关键字计算存储地址

5. 什么是数据运算？数据运算怎样实现？

数据运算包括：检索、插入、删除、更新、排序

运算定义 ， 逻辑结构 ， 存储结构 ， 运算实现

6. 什么是数据类型？C/C++数据类型有哪些？

（1）基本数据类型：cha、int、bool、float、double

（2）C/C++指针类型：如 int i，*p

（3）C/C++数组类型：int a[10] 包含 a[0]~a[9]

（4）C/C++结构体类型

（5）C/C++共用体类型

（6）C/C++自定义类型：如 typedef char Elem Type

存储空间的分配

静态存储空间的分配 int a[10]

动态存储空间的分配

char  *p；

p = （char *）malloc （10 * sizeof（char））；// 动态分配10个连续字符的空间

7. 什么是抽象数据类型？

ATD 抽象数据类型

{ 数据对象：数据对象的声明

数据关系：数据关系的声明

基本运算：基本运算的声明

}

基本运算声明格式：

基本运算名（参数表）：运算功能描述

8. 什么是算法？

算法具有五个重要特性：有穷性、确定性、可行性、有输入、有输出

算法设计目标包含：正确性、可使用性、可读性、健壮性、高效率与低存储量需求

算法描述的一般格式与步骤：（1）分析算法功能；（2）确定输入输出；（3）设计函数体

9. 什么是时间复杂度？

问题规模：算法求解问题输入量的多少，是问题大小的本质表示

语句频度：一条语句重复执行的次数

时间复杂度：算法中的所有语句频度之和，是矩阵阶数n的函数，忽略低阶，忽略系数

一般情况下，算法中的基本语句中，重复执行的次数，是问题规模 n 的某个函数 f（n），算法的时间度量记为：T（n） = O（f（n）），它表示问题规模 n 的增大，算法执行时间的增长率和 f（n）的增长率相同，成为算法的渐进时间复杂度，简称为时间复杂度。

如果算法执行时间不随问题规模 n 的增加而增长，算法中的语句频度就是个常数，即使这个常数再大，算法的时间复杂度都是O（1）

常见的时间复杂度按数量级递增排列依次为：常量阶O（1），对数阶O（log2n），线性阶O（n），线性对数阶O（nlog2n），平方阶O（n2）等等

最坏时间复杂度：算法计算量可能达到的最大值

说明：一般情况下人们关系最坏情况下的时间复杂度，一般的时间复杂度，指的就是最坏时间复杂度

10. 什么是空间复杂度？

算法存储空间需求，类似于算法的时间复杂度，一般采用渐进空间复杂度作为算法所需存储空间的度量称为空间复杂度，它是问题规模n的函数，记为： S（n） = O（f（n））