【数据结构】数据结构，算法 概念
https://i-blog.csdnimg.cn/direct/ed0fa215a8c8453789a3dca920f3b6ab.gif0.本篇题目：
[*]数据、数据元素、数据对象、数据项之间的基本关系？
[*]ADT是什么？
[*]数据结构的三要素？
[*]数据的逻辑结构有哪些？
[*]数据的存储结构有哪些？
[*]算法的五个特征？
[*]O(1) O(logn) O(n^n) O(n) O(n^2) O(n^3) O(2^n) O(n!) O(nlogn) 巨细关系？
★ 错题&范例题
1. 可以用（ ）界说一个完整的数据结构
A.数据元素 B.数据对象 C.数据关系 D.抽象数据类型
2.以部属于逻辑结构的是（ ）
A.顺序表 B.哈希表 C.有序表 D.单链表
3.以下关于数据结构的说法中，正确的是（ ）
A.数据结构的逻辑结构独立于其存储结构
B.数据结构的存储结构独立于其逻辑结构
C.数据的逻辑结构唯一决定其存储结构
D.数据结构仅由其逻辑结构和存储结构决定
4.一个算法应该是（ ）
A.步伐 B.题目求解步骤的形貌 C.要满意五个基本特性 D. A和C
5.某算法的时间复杂度为O(n^2),则体现该算法的（ ）
A.题目规模是n^2 B.实行时间便是n^2
C.实行时间与n^2成正比 D.题目规模与n^2成正比
6.【2017】 求下面步伐时间复杂度
int func(int n) {
int i = 0, sum = 0;
while (sum < n) sum += ++i;
return i;
} 7.【2019】求下面步伐时间复杂度
x = 0;
while (n >= (x + 1) * (x + 1))
x = x + 1; 8.【2022】求下面步伐时间复杂度
int sum = 0;
for (int i = 1; i < n; i *= 2)
for (int j = 0; j < i; j++)
sum++;https://i-blog.csdnimg.cn/direct/cc429030c31a49f4b0d6183b2af60b9a.gif
一、数据、数据元素、数据对象、数据项、数据结构、数据类型
1.1 概念（P1）
[*]数据结构是相互之间存在一种或多种特定关系的数据元素的聚集；它包括三方面的内容：逻辑结构，存储结构，数据的运算。
[*]数据对象是具有相同性子的数据元素的聚集，是数据的一个子集；
[*]数据是信息的载体，是形貌客观事物属性的数、字符及全部能输入到计算机中并被计算机步伐辨认和处理的符号的聚集；
[*]数据元素是数据的基本单位，通常作为一个整体举行考虑和处理；
[*]一个数据元素有若干数据项构成，数据项是构成数据元素的不可分割的最小单位。
[*]数据类型：原子类型、结构类型、抽象数据类型（ADT）：形貌了数据的逻辑结构和抽象运算，通常用（数据对象，数据关系，基本利用）如许的三元组来体现，eg.栈、队列，树...（ADT和数据密切相关，但不完全相同）
1.2 我的明确
[*]数据项是最小的，数据是最大的；
[*]数据项构成数据元素；
[*]数据元素构成数据对象；
[*]全部数据对象的总和是数据。
[*] 数据结构是相互之间存在一种或多种特定关系的数据元素的聚集。(数据元素+关系)
[*]数据对象是具有相同性子的数据元素的聚集，是数据的一个子集。(数据元素)
[*]世界上全部的信息、符号的总和是数据。
[*]这些数据有全部大学学生数据（数据对象），全部餐厅顾客数据（数据对象），XX大学学生数据（数据对象），全部动物的XX数据（数据对象）...
[*]XX大学同学ABCD...数据（数据元素），...
[*]班级学生有自己的学号（数据项），姓名（数据项），年事（数据项）...
[*]数据结构是带存储关系的同学ABCD...的数据（通过它你不但知道这些数据，还知道它们之间的关系是怎样的，怎样存储的）
[*]数据对象，数据元素，数据项根据研究内容的差异都是相对的，这项研究中的数据元素可能是下一项研究中的数据对象。
https://i-blog.csdnimg.cn/direct/cc429030c31a49f4b0d6183b2af60b9a.gif
二、数据结构的三要素
2.1 数据结构三要素
逻辑结构，存储结构，运算 知存储就知逻辑，知逻辑不愿定知存储！
2.2.1 逻辑结构
四类基本结构：线性结构、聚集(同属一个聚集无其他关系)、树形、图状结构(网状结构)。
https://i-blog.csdnimg.cn/direct/eb1d93c3bc954b4e8ed902468f18c31d.jpeg
2.2.2 存储结构
①顺序存储
②链式存储
③索引存储（索引表中每项是索引项（关键字，地点）） 优点：检索快，缺点：索引表额外占据存储空间；增删要修改索引表，时间耗费多。
④散列存储（哈希存储）
2.2.3 运算
施加在数据上的运算，包括运算的界说和实现。运算的界说是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体利用步骤。
https://i-blog.csdnimg.cn/direct/cc429030c31a49f4b0d6183b2af60b9a.gif
三、算法
3.1 算法的概念和特征
算法是对特定题目求解步骤的一种形貌，他是指令的有限数列，其中的每条指令体现一个或多个利用。
特征：①有穷性 ②确定性 ③可行性 ④输入>=0 ⑤输出>=1
3.2 时间复杂度&空间复杂度
是题目规模n的函数。
Q:算法题目规模永久是A:不是。在算法中，题目规模不愿定是n。
n通常用来体现输入规模，比如在一个排序算法中，n可能代表要排序的元素个数。但题目规模也可以用其他方式来权衡。
比方，在图算法中，除了用顶点数目n来体现题目规模，还可能会涉及边的数目m。对于一些复杂的算法，如计算两个图的同构题目，题目规模可能是由多个因素共同决定的，包括顶点数、边数、顶点和边的属性等复杂因素。
在矩阵运算相关的算法中，矩阵的行数和列数都可能影响题目规模，而不是简单地用一个n来体现。
常见的渐进时间复杂度比较：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
https://i-blog.csdnimg.cn/direct/cc429030c31a49f4b0d6183b2af60b9a.gif
答案：1.D 2.C 3.A 4.B 5.C 6.O(n^(1/2)) 7.O(n^(1/2)) 8.O(n)
-THE END-
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]