知识点
1.数据结构的基本概念和术语
1.1、数据、数据元素、数据项和数据对象
数据（Data）是客观事物的符号表示，是所有能输入计算机中并被计算机程序处理的符号的总称。
数据元素（Data Element）是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。
数据项（Data Item）是组成数据元素的、有独立含义的、不可分割的最小单位。
数据对象（Data Object）是性质相同的数据元素的集合，是数据的一个子集。
| 姓名 | 性别 | 身高 | 课程代号 |
| 小明 | 男 | 180 | A |
| 小红 | 女 | 180 | A |
| 小绿 | 男 | 180 | B |
| 课程代号 | 课程名 |
| A | 语文 |
| B | 数学 |
这两张表就是数据
而单独的一张表就称为数据对象，即人员表是一个数据对象，课程表也是一个数据对象
而每张表中的每一行就称为数据元素
而姓名，性别，身高，课程代号，课程名就称为数据项
1.2数据结构
数据结构（Data Structure）是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构包括逻辑结构和存储结构两个层次。
(1).逻辑结构
数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的.
数据的逻辑结构有两个要素：一是数据元素；二是关系。
逻辑结构分为四种类型：集合结构，线性结构，树形结构，图形结构。
- 集合结构：数据元素同属一个集合，单个数据元素之间没有任何关系。
- 线性结构：类似于线性关系，线性结构中的数据元素之间是一对一的关系。
- 树形结构：树形结构中的数据元素之间存在一对多的关系。
- 图形结构：数据元素之间是多对多的关系
(2).存储结构（物理结构）
数据对象在计算机中的存储表示称为数据的存储结构，也称为物理结构
数据元素在计算机中有两种基本的存储结构，分别是顺序存储结构和链式存储结构
- 顺序存储结构:是把数据元素放到地址连续的存储单元里面，其数据间的逻辑关系和物理关系是一致的。
- 链式存储结构：是把数据元素存放在任意的存储单元里面，这组存储单元可以是连续的也可以是不连续的。
1.3数据类型和抽象数据类型
数据类型
一般包括整型、实型、字符型等原子类型外，还有数组、结构体和指针等结构类型。
抽象数据类型
抽象数据类型（Abstract Data Type,ADT），类似C语言中的结构体以及C++、java语言中的类。
通俗的讲，抽象数据类型，泛指除基本数据类型以外的数据类型。
2.算法和算法分析
算法 + 数据结构 = 程序
2.1、算法的定义及特性
算法是为了解决某类问题而规定的一个有限长的操作序列。
一个算法必须满足以下五个重要特性：
- 有穷性。一个算法必须总是在执行有穷步后结束，且每一步都必须在有穷时间内完成。
- 确定性。对于每种情况下所应执行的操作，在算法中都有确切的规定，不会产生二义性，算法的执行者或阅读者都能明确其含义及如何执行。
- 可行性。算法中的所有操作都可以通过将已经实现的基本操作运算执行有限次来实现。
- 输入。一个算法有0个或多个输入。当用函数描述算法时，输入往往是通过形参表示的，在它们被调用时，从主调函数获得输入值。
- 输出。一个算法有一个或多个输出，它们是算法进行信息加工后得到的结果，无输出的算法没有任何意义。当用函数描述算法时，输出多用返回值或引用类型的形参表示。
2.2、评价算法优劣的基本标准
正确性 、 可读性 、 健壮性 、 高效性
2.3.算法的时间复杂度
根据循环的嵌套层数，依次递增。
最好、最坏和平均时间复杂度
- 最好时间复杂度，指的是算法计算量可能达到的最小值。
- 最坏时间复杂度，指的是算法计算量可能达到的最大值。
- 平均时间复杂度，是指算法在所有可能情况下，按照输入实例以等概率出现时，算法计算量的加权平均值。
2.4、算法的空间复杂度
空间复杂度只需要分析辅助变量所占的额外空间。
空间复杂度：S(n) = O(f(n))
习题
一、单选题
1.在数据结构中，与所使用的计算机无关的是数据的（ ）结构。
A. 逻辑
B. 存储
C. 逻辑和存储
D. 物理
2.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（ ）。
A. 数据的处理方法
B. 数据的存储方法
C. 数据元素的类型
D. 数据元素之间的关系
3.关于数据结构以下说法正确的是（ ）。
A. 数据元素是数据的最小单位
B. 数据项是数据的基本单位
C. 数据结构是带有结构的各数据项的集合
D. 数据对象是带结构的数据元素的子集
4.在数据结构中，从逻辑上可以把数据结构分成（）。
A. 动态结构和静态结构
B. 紧凑结构和非紧凑结构
C. 线性结构和非线性结构
D. 内部结构和外部结构
5.数据结构在计算机内存中的表示是指( )
A. 数据的存储结构
B. 数据结构
C. 数据的逻辑结构
D. 数据元素之间的关系
6.数据结构的定义是( )。
A. 一种数据类型
B. 数据的存储结构
C. 一组性质相同的数据元素的集合
D. 相互之间存在一种或多种特定关系的数据元素的集合
7.可以用( )定义一个完整的数据结构。
A. 数据元素
B. 数据对象
C. 数据关系
D. 抽象数据类型
8.算法的时间复杂度取决于（ ）。
A. 问题的规模
B. 待处理数据的初态
C. 算法执行的实际时间
D. 问题的规模和待处理数据的初态
9.计算机算法指的是解决问题的步骤序列，它必须具备（ ） 这五个特性。
A. 可执行性、可移植性、可扩充性、输入、输出
B. 可执行性、确定性、有穷性、输入、输出
C. 确定性、有穷性、稳定性、输入、输出
D. 易读性、稳定性、安全性、输入、输出
10.在下面的程序段中，对x的赋值的语句频度为（ ）
for(i=0;i<n;i++)
for(j=0;j<n;j++)
x=x+1;
A. O(2n)
B. O(n)
C. O(n²)
D. O(log₂n)
11.算法分析的目的是( )
A. 找出数据结构的合理性
B. 研究算法中的输入和输出的关系
C. 分析算法的效率以求改进
D. 分析算法的易懂性和文档性
12.某算法的时间复杂度为O(n²)，表明该算法的( )
A. 问题规模是 n²
B. 执行时间等于 n²
C. 执行时间与 n² 成正比
D. 问题规模与 n² 成正比
13.试分析下面各程序段的时间复杂度为( )
x=90; y=100;
while(y>0)
if(x>100)
{x=x-10;y–;}
else x++;
A. O(n)
B. O(n²)
C. O(1)
D. O(0)
二. 填空题
1.数据元素是数据的（ 1 ）单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。
2.数据对象是性质相同的数据元素的集合，是数据的一个（ 1 ）。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’， ‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。
3.逻辑结构是从逻辑关系上描述数据，它与数据的（ 1 ）无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题（ 2 ）出来的数学模型。
答案解析
一、选择题解析
1.A
答案解析：数据的逻辑结构是数据本身的特点，与计算机无关。
2.D
答案解析：数据元素的值和数据元素直接的关系都要存储，顺序存储中物理上的相邻表示关系，链式存储中指针（地址）表示关系。
3.D
答案解析：数据元素是数据的基本单位，数据项是数据的最小单位，数据结构是带有结构的各数据元素的集合。
4.C
答案解析：线性表属于线性结构，树和图属于非线性结构。5.
5.A
答案解析：存储结构是指在计算机中的存储。
6.D
答案解析：数据结构是带有结构的各数据元素的集合。结构又是关系。
7.D
答案解析：抽象数据类型描述数据、关系和操作。
8.D
答案解析：算法的时间复杂度不仅与问题的规模有关，还与问题的其他因素有关。如某些排序的算法，其执行时间与待排序记录的初始状态有关。为此，有时会对算法有最好、最坏以及平均时间复杂度的评价。
9.B
答案解析：一个算法具备的5个重要特性是：有穷性，确定性，可行性，有零个或多个的输入，有1个或多个的输出。
10.C
答案解析：语句频度=基本语句执行时间*执行次数。
11.C
答案解析：算法分析的目的是分析算法的效率以求改进。
12.C
答案解析：算法的时间复杂度是算法执行时间的预估，代表随着规模n增长的趋势。
13.C
答案解析：程序段的执行与规模n无关，不能体现随着规模n的增加，呈现的趋势，所以是常量级的。
二、填空题解析
1.(1) 基本
答案解析：数据元素是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。
2.(1) 子集
答案解析：数据对象是性质相同的数据元素的集合，是数据的一个子集。
3.(1) 存储;在计算机中的存储
(2) 抽象;归纳
答案解析：逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。