数据结构考试内容总结（2020版）1
需积分: 0 80 浏览量
2022-08-03
19:29:58
上传
评论
收藏 180KB PDF 举报
小结
第一章 绪论
一、基本概念
数据、数据元素、数据项（数据元素的某一个属性，结构体中某一处成员）、
数据对象（特性相同）、数据结构（关系）。
数据结构：逻辑结构和存储结构。逻辑结构是数据元素间内在的、本质的关
系，与计算机无关（线性表、队列）。存储结构强调的是数据元素之间的关系在
计算机中的存储与表示（顺序表、线索二叉树、哈希表）。
存储结构：顺序存储和链式存储。顺序存储借助存储数据元素的位置来表示
数据元素之间的逻辑关系（逻辑相邻，物理相邻；连续的存储单元；随机的存取）；
链式存储借助存储数据元素地址的指针来表示数据元素之间的关系（存储单元不
一定是连续的，逻辑相邻，物理上不一定相邻，随机的存储单元、顺序存取）。
逻辑结构：线性结构和非线性结构；线性结构、树形结构、图状（网状）结
构、集合。
二、抽象数据类型的定义
数据对象、数据关系、基本操作
三、算法及算法分析
1、算法的特性：输入、输出、有穷性、确定性、可行性。
2、算法评价：正确性、可读性、键状性、高效性（时间复杂度和空间复杂度）。
时间复杂度：算法中基本语句重复执行的次数是问题规模 n 的某个函数 f(n).
O(n) = O(f(n))
例 1、分析以下算法的时间复杂度
Void fun(int n)
{
int y=0;
while(y*y <= n)
y++;
}
设 while 语句的执行频度为 T(n)，每循环一次 y 值增大 1，即 y=T(n)，有以下关
系：
T(n)*T(n) <= n 即 T(n)
2
<=n T(n)=O(n
1/2
)
剩余21页未读，继续阅读
评论0
最新资源