1 / 155
圣才电子书 十万种考研考证电子书、题库视频学习平台

③树形结构：数据元素之间存在一个对多个的关系。 ④图状结构或网状结构：数据元素之间存在多个对多个的关系。 【注意】区分这四种基本结构可以根据元素间的对应关系。 如图 1-1 所示为上述四类基本结构的关系图。
4．算法的存储空间需求 算法的空间复杂度是对算法运行所占空间的度量。 在度量时一般只考虑算法运行所需额外开销的多少，包括算法实现时定义的中间变量， 数组等对存储空间的影响。 原地工作：算法运行所需的额外空间相对输入数据量是常量。
1.2 强化习题详解
【基础知识题】
1．简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型和抽
4 / 155
圣才电子书 十万种考研考证电子书、题库视频学习平台

3．算法效率的度量 算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量，度 量一个程序的执行时间通常有两种方法： （1）事后统计 （2）事前分析估算 ①事先考虑消耗时间的因素 ②时间复杂度 时间复杂度是关于问题规模的函数，通常用 O 表示，常见时间复杂度按照数量级递增 排列为： O（1）＜O（log2n）＜O（n）＜O（nlog2n）＜O（n2）＜O（n3）＜O（nk）＜O（2n） 【注意】需能够对具体的算法进行时间复杂度的分析与计算，考研中算法时间复杂度的 计算不可避免。
5 / 155
圣才电子书 十万种考研考证电子书、题库视频学习平台

象数据类型。 答：（1）数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并 能被计算机程序处理的符号的总称。 （2）数据元素是数据的基本单位。 （3）数据对象是性质相同的数据元素的集合，是数据的一个子集。 （4）数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 （5）存储结构是数据结构在计算机中的表示（又称映象或数据的物理结构）。 （6）数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 （7）抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。
2．数据元素 数据元素是数据的基本单位。
3．数据对象 数据对象是性质相同的数据元素的集合，是数据的一个子集。
4．数据结构 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 （1）数据结构的基本结构 根据数据元素之间关系的不同特性，通常有下列四类基本结构： ①集合：数据元素属于“同一个集合”，并无其他复杂关系。 ②线性结构：数据元素之间存在一个对一个的关系。
3．设有数据结构（D，R），其中 D＝{d1，d2，d3，d4}，R＝{r}，r＝{（d1，d2），（d2， d3），（d3，d4）}，试按图论中图的画法惯例画出其逻辑结构图。
答：逻辑结构图如图 1-2 所示。
6 / 155
圣才电子书 十万种考研考证电子书、题库视频学习平台
圣才电子书 十万种考研考证电子书、题库视频学习平台

构）。 其中，关系有两种表示方法：顺序映象和非顺序映象。这两种表示方法对应两种存储结 构：顺序存储结构和链式存储结构。 a．顺序映象：用相对位置来表示数据元素之间的逻辑关系。 b．非顺序映象：用指针表示数据元素之间的逻辑关系。
三、数据结构的发展简史及它在计算机科学中所处的地位（略）
四、算法和算法分析 1．算法的描述 算法需要用一种语言来描述，程序框图，程序设计语言等都能对算法进行描述。 【注意】考研笔试中，如果在对应语法不确定的情况下，使用伪码通常也是可以的。
2．算法设计的要求 （1）正确性 （2）可读性 （3）健壮性 （4）效率与低存储量需求
3 / 155
圣才电子书 十万种考研考证电子书、题库视频学习平台

引用型操作：即不改变结构的值，只是查询或求得结构的值。 上述 5 种操作中除“查找”为引用型操作外，其余都是加工型操作。
9．算法 【定义】算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指 令表示一个或多个操作。 【特性】 （1）有穷性 （2）确定性 （3）可行性 （4）输入 （5）输出
圣才电子书 十万种考研考证电子书、题库视频学习平台

第1章 绪 论
1.1 复习笔记
一、什么是数据结构 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的 关系和操作等的学科。
二、基本概念和术语 1．数据 数据是对客观事物的符号表示，是计算机科学中所有能输入到计算机中并能被计算机程 序处理的符号的总称。
5．数据类型 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
6．抽象数据类型 抽象数据类型（ADT）由一个 多形数据类型是指其值的成分不确定的数据类型。
8．数据操作的类型 基本的操作主要有： （1）插入 （2）删除 （3）更新 （4）查找 （5）排序 从操作的特性来分，所有的操作可以归结为两类： 加工型操作：改变了（操作之前的）结构的值；
2．试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 答：数据结构：相互之间存在一种或多种特定关系的数据元素的集合； 抽象数据类型：一个数学模型以及在该模型上的一组操作。 区别： ①抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实 现无关。 ②抽象数据类型包含一般数据类型的概念，但含义比一般数据类型的范畴更广。 ③抽象数据类型可通过程序设计语言中的数据类型来表示和实现。
图 1-1 四类基本结构的关系图 （2）数据结构的形式定义 数据结构的形式定义为： Data_Structure=(D,S) 其中：D 表示数据元素的有限集，S 表示 D 上关系的有限集。 （3）数据结构在计算机中的表示 数据结构包括数据元素的表示和关系，在计算机中称为数据的物理结构（又称存储结
2 / 155