第一堂复试

1.数据结构的基本概念

数据元素 相当于一个类
数据对象是数据元素的集合
数据项：具体的属性

2.数据结构三要素

1.一般线性表相当于数组，2.栈先进后出，3.队列先进先出
非线性结构一般是一对多
线性结构一般是一对一

3.数据的存储结构

4.算法特性

五个特性：

5.时间复杂度

在大多数情况下，时间复杂度为 O(log n) 的算法效率更高于时间复杂度为 O(n) 的算法。这是因为 O(log n) 表示算法的运行时间随着输入规模的增加以对数速度增长，而 O(n) 表示算法的运行时间直接与输入规模成线性关系。
![](https://img-blog.csdnimg.cn/direct/b93e12e35cdb4bd5b576eeafdb42c989.png

2.线性表

2.1线性表的定义

表示的是一种关系（逻辑结构）——>栈，队列（栈队列是线性结构，一对一），树，图等（树图是非线性结构->一对多）

存储结构：顺序表
优点： 访问速度快，随机访问，0(1)，索引访问，存储密度大
缺点： 删除，插入速度较慢，因为抽一发而动全身，其余元素的内存地址需要重新分配

2.2 插入时间复杂度：
平均移动次数为 n/2次

2.3 删除时间复杂度：
删除的平均运动次数n-1/2，删除第i个，需要移动n-i

3.单链表

3.1头插法：

4.双链表

静态链表``存储空间是连续的，而单链表是不连续的