数据结构第一章 绪论

程序设计的关键是什么？

数据表示：从问题抽象出数据模型，从机外表示转换为机内表示

数据表示

数据处理：设计算法，再将算法转换为程序设计语言对应的程序

数据处理

计算机不能分析问题并产生问题的解决方案，必须由人来分析问题、确定解决方案、编写程序，再让计算机执行程序最终获得问题的解

利用计算机求解问题的一般过程？

计算机解决问题的过程

本课程主要讨论非数值问题的数据组织和处理

（1）数据的逻辑结构：线性表、树、图等数据结构，其核心是如何组织待处理的数据以及数据之间的关系；

（2）数据的存储结构：如何将表、树、图等数据结构存储到计算机的存储器中，其核心是如何有效地存储数据以及数据之间的逻辑关系

（3）算法：如何基于数据的某种存储结构实现插入、删除、查找等基本操作，其核心是如何有效地处理数据；

（4）常用数据处理技术：查找技术、排序技术等。

### 数据结构的基础概念

数据：所有能输入到计算机中并能被程序识别和处理的符号集合

数据

数据元素：数据的基本单位，在程序中作为一个整体进行考虑和处理，通常情况下，数据元素具有相同个数和类型的数据项。

数据项：构成数据元素的最小单位

数据结构：相互之间存在一定关系的数据元素的集合

数据的逻辑结构：数据元素之间逻辑关系的整体

数据结构的分类

数据的存储结构

数据的存储（物理）结构：数据及其逻辑结构在计算机中的表示

（1）顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置表示

（2）链接存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示

抽象数据类型

抽象数据类型：一个数据模型以及定义在该模型上的一组操作

实现抽象数据类型 ## 算法及算法的特性

算法 : 是对特定问题求解步骤的一种描述，是指令的有限序列

算法的基本要求

（1）有穷性：总是在执行有穷步之后结束，且每一步都在有穷时间内完成

（2）确定性：每一条指令必须有确切的含义，相同的输入得到相同的输出

（3）可行性：操作步骤可以通过已经实现的基本操作执行有限次来实现

算法分析

算法分析：对已设计的算法，如何评价或判断其优劣

事后统计（定量分析）：将算法实现，测算其时间和空间开销

事前分析（定性分析）：对算法所消耗资源的一种估算方法

基本语句：执行次数与整个算法的执行次数成正比的操作指令

问题规模：输入量的多少

算法的时间复杂度

时间复杂度：当问题规模充分大时，算法中基本语句的执行次数在渐近意义下的阶——关注的是增长趋势

定义1-1 若存在两个正的常数 c 和 n0，对于任意 n ≥ n0，都有T(n) ≤ c × f(n)，则称T(n) = O(f(n))。

T(n)和f(n)具有相同的增长趋势，T(n)的增长至多趋同于函数f(n)的增长

Ο(1)＜(log2n)＜(n)＜(nlog2n)＜(n2)＜(n3)＜…＜(2n)＜(n!)

时间复杂度是在不同数量级的层面上比较算法

算法的空间复杂度

空间复杂度：算法在执行过程中需要的辅助空间数量

除算法本身和输入输出数据所占用的空间外，算法临时开辟的存储空间

空间复杂度也是问题规模的函数，通常记作：S(n) = O(f(n))

就地（原地）算法：空间复杂度为O(1)，辅助空间是常数

定理1-1：若T(n) = amnm + am-1nm-1 +  + a1n + a0是一个m次多项式，则T(n) = O(nm)

分析的策略是从内部（或最深层部分）向外展开，分析的策略是设其执行次数为T(n)，则有2T(n) ≤ n，即T(n) ≤ log2n

如果算法的时间代价与输入数据有关，则需要分析最好情况、最坏情况、平均情况

1. 最好情况：不能代表算法的效率，当出现概率较大时分析
2. 最坏情况：最坏能坏到什么程度，实时系统需要分析
3. 平均情况：已知输入数据分布情况，通常假设等概率分布

数据结构 第一章 绪论题目

判断题

1. 数据元素是数据的最小单位。 (F)
2. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。 (F)
3. 数据结构概念包括数据之间的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面。 (T)
4. 数据结构的抽象操作的定义与具体实现有关。 (F)
5. 算法和程序没有区别，在数据结构中二者是通用的。 (F)
6. 数据结构包括数据对象集以及它们的逻辑结构和物理结构，还包括与数据对象相关联的操作集，以及实现这些操作的高效的算法。 (T)

单选题

1. 在 Data_Structure = (D，R)中，D 是（ ）的有限集合。 (A)

A 数据元素 B 算法 C 数据操作 D数据对象

1. 以下关于数据结构的说法中错误的是（ ） (A)

A.数据结构相同，对应的存储结构也相同 B.数据结构涉及数据的逻辑结构存储结构和施加其上的操作3个方面

C.数据结构操作的实现与存储结构有关 D.定义逻辑结构时可不考虑存储结构

1. 算法分析的目的是( ) (C)

A.找出数据结构的合理性 B.研究算法中的输入和输出的关系

C.分析算法的效率以求改进 D.分析算法的易读性和文档性

1. 算法分析的两个主要方面是( ) (A)

A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性

1. 采用链结构存储线性表时，其地址（ ）。
2. 一个正确的算法应该具有 5 个特性，除输入、输出特性外，另外 3 个特性是（ ）。