- 1 -
第 1章 引论
1.1 数据结构课程的地位和考试要求
1.1.1 数据结构课程的地位
数据结构是计算机科学与技术专业本科生的专业基础课程之一，是程序设计系列课程中
一个不可或缺的环节，对于信息系统的研究和开发起到重要的支撑作用。因此，国内外大专
院校计算机和软件
工程
路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理
专业都把《数据结构》列为考研的必考科目。2009 年教育部更是把
这门课程列为全国硕士研究生入学考试计算机专业基础综合考试的考试科目之一，在满分
150 分中占了 45 分。复习好数据结构，对于通过联考有着至关重要的作用。
1.1.2 考试要求
2010 年教育部指定《考试大纲》明确提出，对于数据结构部分，主要考查：
(1) 理解数据结构的基本概念；掌握数据的逻辑结构，存储结构及其差异，以及各种基
本操作的实现。
(2) 在掌握基本的数据处理原理和方法的基础上，能够对算法进行时间复杂度和空间复
杂度分析。
(3) 能够选择合适的数据结构和方法进行问题求解。具备采用 C 或 C++或 JAVA 语言设
计与实现算法的能力。
换句话说，考查的目标有两个：知识和技能。
1．知识方面
从数据结构的结构定义和使用，以及存储表示和操作的实现两个层次，系统地考查：
(1) 掌握常用的基本数据结构（包括顺序表、链接表、栈与队列、数组、二叉树、堆、
树与森林、图、查找结构、索引结构、散列结构）及其不同的实现
(2) 掌握分析、比较和选择不同数据结构、不同存储结构、不同算法的原则和方法
2. 能力方面
从解决问题的角度出发，系统地考查：
(1) 掌握运用基本数据结构来设计算法方法的能力
(2) 掌握算法设计和分析的思考方式及技巧，提高分析问题和解决问题的能力。
前者在全国联考的试卷中占 20 分，主要通过选择填空题方式考查；后者在全国联考的
试卷中占 25 分，主要通过综合应用题方式考查。
1.1.3 考查的知识点
分析 2010 年《考试大纲》，对其主要条目做了细化和整理，总结出数据结构部分主要考
查的知识点有 45 个，分布在 6 章内
1．线性表
包括 4 个知识点：
(1) 线性表的定义、特点和基本操作（已考）
(2) 线性表的存储表示，包括顺序存储和链式存储（已考）
(3) 特殊链表的定义和基本运算的实现，包括循环链表和双向链表
(4) 线性表的应用，包括基于一维数组的一些算法、一元多项式的组织和操作等
2．栈、队列和数组
包括 7 个知识点：
- 2 -
(1) 栈与队列的定义、特点和基本操作（已考）
(2) 栈的存储表示及其操作的实现，包括顺序栈和链式栈
(3) 队列的存储表示及其操作的实现，包括循环队列和链式队列
(4) 特殊队列的定义和存储表示，包括双端队列（已考）和优先队列
(5) 栈与队列的应用，包括递归改非递归（分治与回溯）、表达式计算、括号配对、数
值转换、分层处理
(6) 多维数组的定义和特点，包括二维数组计算、基于矩阵的算法实现
(7) 特殊矩阵的定义和特点，包括对称矩阵、三对角矩阵、稀疏矩阵
3．树与二叉树
包括 9 个知识点：
(1) 树与二叉树的定义、性质（已考）
(2) 二叉树的存储表示，包括顺序存储和链接存储
(3) 二叉树的遍历及其应用，包括前序、中序、后序（已考）和层次序遍历
(4) 线索二叉树的定义（已考）、存储表示和寻找前驱、后继
(5) 树与森林的存储表示（已考）和遍历（已考）
(6) 二叉排序树的定义、存储表示、基于二叉排序树的算法实现
(7) 平衡二叉树的定义（已考）、存储表示、基本操作和平衡旋转（已考）
(8) 哈夫曼（Huffman）树的定义（已考）、存储表示和应用
(9) 堆的定义（已考）、存储表示和基本操作的实现（已考）
4．图
包括 8 个知识点：
(1) 图的基本概念，包括顶点的度、路径、回路、连通图（已考）等
(2) 图的存储表示，包括邻接矩阵、邻接表
(3) 图的遍历，包括深度优先搜索和广度优先搜索的实现
(4) 最小生成树的定义（已考）、构成方法，包括 Kruskal 算法和 Prim 算法
(6) 最短路径的概念（已考）和求解方法，包括 Dijkstra 算法和 Floyd 算法
(7) 拓扑排序的定义、实现方法（已考）
(8) 关键路径的定义、求解方法
5．查找
包括 6 个知识点：
(1) 查找的概念和性能评价
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
(2) 顺序查找算法和性能分析
(3) 折半查找算法和性能分析（已考）
(4) m 阶 B 树的定义和存储结构（已考）、查找、插入与删除的平衡化
(5) m 阶 B+树的定义和存储结构、搀着、插入与删除的平衡化
(6) 散列法的概念、散列函数的选择、解决冲突的线性探测法（已考）、二叉探测法、
双散列法和链地址法、散列法的性能分析
6．内排序
包括 10 个知识点：
(1) 排序的概念和性能评价标准，包括排序码比较次数、元素移动次数、附加存储数、
稳定性
(2) 直接插入排序的思路、算法和性能分析（已考）、稳定性
(3) 折半插入排序的思路、算法和性能分析、稳定性
(4) 起泡排序的思路、算法和性能分析（已考）、稳定性
(5) 简单选择排序的思路、算法和性能分析（已考）、稳定性
(6) 快速排序的思路、算法和性能分析（已考）、稳定性
- 3 -
(7) 堆排序的思路、算法和性能分析、稳定性
(8) 二路归并排序的思路、算法和性能分析（已考）、稳定性
(9) 基数排序的思路、算法和性能分析
(10) 排序方法的性能比较（已考）
(11) 排序方法的应用
在复习过程要切实掌握这些知识点，才能够对考试应付自如。复习方法参看第 8 章。
1.2 数据结构和算法的预备知识
这些知识是《考试大纲》没有明确要求，但贯穿于所有各章的必备知识。对于理解和掌
握各章的内容起到了支持作用。
1.2.1 数据结构的主要概念
1．什么是数据
数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算
机程序识别和处理的符号的集合。
数据主要分两大类：数值性数据和非数值性数据。数据结构主要研究的是非数值型数据。
2．什么是数据元素
数据的基本单位就是数据元素。例如，在学校的学籍管理系统中学生文件是由一系列学
生记录组成，每个学生记录就是一个数据元素。在计算机程序中数据元素常作为一个整
体进行考虑和处理。数据元素又可称为元素、结点、记录。
有时一个数据元素可以由若干数据项组成。数据项是具有独立含义的最小标识单位。例
如，每个学生记录又可由学号、姓名、性别等数据项组成。
数据元素的集合构成一个数据对象，它是针对某种特定的应用。
3．什么是数据结构
数据结构指某一数据元素集合中的所有数据成员之间的关系。完整的定义为：
数据结构 = { D, R, M }
其中，D 是某一数据元素的集合；R 是该集合中所有数据成员之间的关系的有限集合；
M 是作用在该集合所有数据成员之上的方法（或操作）。
4．数据结构的三个要素
数据结构是指数据元素间的逻辑关系，即数据的逻辑结构。数据逻辑结构的要点是：
数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关；
数据的逻辑结构可以看作是从具体问题抽象出来的数据模型（面向应用的）；
数据的逻辑结构与数据元素本身的形式、内容无关；
数据的逻辑结构与数据元素的相对存储位置无关。
数据的物理结构是数据元素及其关系在计算机存储内的表示，也称为数据的存储结构。
作用于数据结构上的运算是讨论数据结构的另一个重要方面。讨论数据结构必须讨论相
关的操作。操作的实现依赖于相应的存储结构。图 1.1 是它们之间的关系。
图 1.1 数据结构三个要素的关系
5．数据逻辑结构的分类
数据的逻辑结构通常划分为线性结构、树形结构、图结构和集合结构。如图 1.2 所示。
- 4 -
图 1.2 数据逻辑结构的分类
线性结构中元素之间的关系是一对一的关系，集合结构中元素之间的关系为空，树形结
构中元素之间的关系是分层的一对多的关系，图结构中元素之间的关系是多对多的关系。
这 4 种关系中集合结构的实现往往采用其他逻辑结构的存储表示。
6．数据存储结构的分类
数据存储结构分为 4 类：顺序存储表示、链接存储表示、索引存储表示、散列存储表示。
7．数据类型与抽象数据类型
数据类型是一组性质相同的值的集合, 以及定义于这个值集合上的一组操作的总称。数
据类型可分为两大类：基本数据类型和构造数据类型。
基本数据类型可以看作是计算机中已实现的数据结构。例如，C 语言中的基本数据类型
有字符型（char）、整型（int）、浮点型（float）、双精度型（double）和无值（void），可直
接使用由它们定义的变量和相应的操作。
构造数据类型由基本数据类型或构造数据类型组成，在应用中可视为一种数据模型。构
造数据类型由不同成分类型构成，在 C 语言中用 typedef struct 来定义。
数据类型和数据结构的共同点在于它们都有其抽象性，它们并不特指适用于何处，就像
利用半径求圆周的公式一样，想用到哪里就可放到哪里。
数据类型与数据结构之间的区别在于数据结构本身是一种数据的组织形式和使用形式，
通过把它定义成数据类型才能在计算机上使用。从这个意义上来看，数据类型是从编程者使
用的角度可由计算机实现的数据结构。注意，数据类型本身不能参加运算，必须定义属于某
种数据类型的变量，使用这些变量才能参与运算。
抽象数据类型由用户定义，用以表示应用问题的数据模型。抽象数据类型由构造数据类
型组成, 包括数据的组成和一组相关的服务（或称操作）。
抽象数据类型的三大特征是信息隐蔽、数据封装、使用与实现相分离。面向对象方法中
的类（class）完美地实现了抽象数据类型。
1.2.2 算法及算法分析
1．算法的概念
所谓算法，就是基于特定的计算模型在信息处理过程中为了解决某一类问题而设计的一
个指令序列。算法的 5 个要素是
有输入：待处理的信息，即用数据对具体问题的描述；
有输出：经过处理后得到的信息，即问题的答案；
确定性：对于相同的输入数据，算法执行确定的预设路线，得到确定的结果；
可行性：算法的每一基本操作都可以实施，并能够在常数时间内完成；
有穷性：对于任何输入，算法都能经过有穷次基本操作得到正确的结果。
2．设计算法的三个阶段
设计算法通常经过三个主要阶段
(1) 从问题出发，寻找可能的解决
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
，结合计算机选择合适的算法；
(2) 建立解决问题的数据模型和程序框架，并用伪代码描述一系列
步骤
新产品开发流程的步骤课题研究的五个步骤成本核算步骤微型课题研究步骤数控铣床操作步骤
；
a b c d e f g h
1 2
4
3
6
5
d
e
b g
a c h
f
a1 a2 a3 a4
(a) 线性结构 (b) 集合结构
(c) 树形结构 (d) 图结构
- 5 -
(3) 细化程序框架，用程序设计语言写出完整的数据结构和程序代码。
3．算法的性能分析
设计算法就是为了求解问题。算法的效率是衡量是否具有可计算性的关键。性能分析的
目的就是要了解算法的效率。性能，指算法功能实际执行的功效或表现如何。主要从算法执
行的时间和空间效率进行分析。
(1) 时间复杂度
算法的时间复杂度度量是通过统计算法的每一条指令的执行次数和执行时间得到的。因
此，算法的时间代价的计算公式为：
算法的执行时间 = 算法中每条语句执行时间之和；
每条语句的执行时间 = 该语句的执行次数（或频度）×该语句执行一次所需时间；
语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量，很难确
定，因此设每条语句执行一次所需时间为单位时间。则一个算法的运行时间 = 该算法中所
有语句的执行次数（或频度）之和。
例如，有一个求两个 n 阶方阵的乘积 C = A×B 的算法，其执行次数如表 1.1 所列。
表 1.1
程 序 语 句 语句执行次数
void MatrixMultiply ( int A[][], int B[][], int C[][], int n )
{
int i, j, k;
for ( i = 0; i < n; i++ ) … n+1
for ( j = 0; j < n; j++ ) … n(n+1)
{
C[i][j] = 0; … n2
for ( k = 0; k < n; k++ ) … n2(n+1)
C[i][j] = C[i][j] + A[i][k] * B[k][j]; … n3
}
};
总 计 ...2n3+3n2+2n+1
(2) 渐进时间复杂度：大 O 表示法
算法中所有语句的频度之和是矩阵阶数 n 的函数
T(n) = 2n3 + 3n2 + 2n +1
称 n 是问题的规模。则时间复杂度 T(n)是问题规模 n 的函数。当 n 趋于无穷大时，称时
间复杂度的数量级为算法的渐进时间复杂度
T(n) = O(n3) ⎯ 算法的大 O 表示
大 O 表示表明当 n→∞时，T(n)的变化趋势。教科书上对大 O 表示的较严格的定义是：
如果存在正常数 a、N 和一个函数 f (n)，使得对于任何 n＞N，都有
T(n)＜a×f (n)
则可以认为在 n 足够大之后，f (n)给出了 T(n)的一个上界，记为
T(n) = O(f (n))
事实上，大 O 表示给出了算法执行效率的一个保守的估计，即对于规模为 n 的任意输
入，算法的执行时间都不会超过 O(f (n))。对于表 1.1 所示的例子，其大 O 表示为
T(n) = O(n3)
在分析一个程序的渐进时间复杂性时，我们需要抓关键操作，为此需要分解程序结构。
在程序的许多并列的程序段中找出最复杂的程序段，特别是包括多层嵌套循环的程序段，其
最内层循环中的执行语句即为关键操作。分析关键操作的执行次数，就可直接得到大 O 表
- 6 -
示的结果。例如，表 1.1 所示程序最内层循环中执行语句 C[i][j] = C[i][j] + A[i][k] * B[k][j]
就是关键操作，它的执行次数为 n3，则整个程序的大 O 表示为 O(n3)，这样不必再一条语句
一条语句做繁琐的计算。
(3) 空间复杂度
空间复杂度是对算法的存储效率的度量。算法所用存储存储空间可分为两大部分：固定
部分和可变部分。
存储空间的固定部分主要包括程序指令代码所占用的空间，常数、简单变量、定长成分
（如数组元素、结构成分、对象的数据成员等）变量所占用的空间等。这部分空间可以通过
程序分析很容易地统计出来。存储空间的可变部分主要包括尺寸与问题规模有关的成分变量
所占用的存储空间、递归栈所占用的存储空间、通过 malloc 和 free 命令动态使用的存储空
间等。这部分存储空间需要分析程序的执行过程才能统计出来。
通常，空间复杂度的度量只是在相同功能的不同算法之间比较优劣时才使用。在这种情
况下，一般比较它们完成功能时所需的附加存储空间即可。
(4) 不同大 O 表示的比较
表 1.2 显示了不同的函数（= f (n)）当 n 增大时的增长趋势。如果一个算法的时间复杂度
达到O(log2n)，就说明这个算法具有很高的时间效率，如果一个算法的时间复杂度达到O(n!)，
一旦 n 变大，算法的运行时间将达到不可计算的程度。因此，如果用“<”表示优于，则有
c < log2n < n < nlog2n < n2 < n3 < 2n < 3n < n!
表 1.2
n log2n n*log2n n2 n3 2n n!
4 2 8 16 64 16 24
8 3 24 64 512 256 80320
10 3.32 33.2 100 1000 1024 3628800
16 4 64 256 4096 65536 2.1*1013
32 5 160 1024 32768 4.3*109 2.6*1035
128 7 896 16384 2097152 3.4*1038 ∞
1024 10 10240 1048576 1.07*109 ∞ ∞
10000 13.29 132877 108 1012 ∞ ∞
1.2.3 选择填空题解析
题 1.2.1 顺序存储表示中数据元素之间的逻辑关系是由（ 1 ）表示的，链接存储表
示中数据元素之间的逻辑关系是由（ 2 ）表示的。
(1)、(2) A．指针 B．逻辑顺序 C．存储位置 D．问题上下文
【解析】(1) 选 C，(2) 选 A。顺序存储的存储位置与逻辑结构中的逻辑顺序是对应的；
链接存储用指针把元素按照其逻辑关系链接起来，不要求数据元素的逻辑顺序与存储顺序有
对应关系。选哪种存储结构是由问题的上下文确定的。
题 1.2.2 计算机所处理的数据一般具有某种关系，这是指（ ）。
A．数据与数据之间存在的某种关系
B．数据元素与数据元素之间存在的某种关系
C．元素内数据项与数据项之间存在的某种关系
D．数据文件内记录与记录之间存在的某种关系
【解析】选 B。数据由数据元素构成，特定上下文环境下数据元素构成的集合即为数据
对象。一般数据处理考虑的是数据对象内各元素之间的关系。数据元素是数据的基本标识单
位，数据项是数据的最小处理单位。
题 1.2.3 以下关于数据结构的说法中错误的是（ ）。
- 7 -
A．数据结构相同，对应的存储结构也相同
B．数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面
C．数据结构操作的实现与存储结构有关
D．定义逻辑结构时可不考虑存储结构
【解析】选 A。数据结构通常指的是逻辑结构。同一逻辑结构可对应不同的存储结构。
例如字典，可用顺序表、链表、散列表、索引表来实现。数据结构的操作在不同存储下有不
同的实现。
题 1.2.4 以下关于数据结构的说法正确的是（ ）。
A．数据结构的逻辑结构独立于其存储结构
B．数据结构的存储结构独立于该数据结构的逻辑结构
C．数据结构的逻辑结构唯一地决定了该数据结构的存储结构
D．数据结构仅由其逻辑结构和存储结构决定
【解析】选 A。数据的逻辑结构是面向问题的，是从应用的需求出发而建立的，至于如
何在计算机上存储，这是设计时再考虑的内容，所以数据的逻辑结构可独立于存储结构来组
织。反之，数据的存储结构是逻辑结构在计算机中的映像，它不能独立于逻辑结构存在；此
外，同一逻辑结构在计算机上如何存储，要看是否易于访问，是否易于修改或增删，是否利
于安全保密等，相应地可有不同存储结构可以选用；数据结构不是孤立的，不但要考虑数据
的组织，还要考虑作用在数据结构上的操作，即数据对象的行为，因此数据结构不是仅由其
逻辑结构和存储结构决定的。
题 1.2.5 下面关于抽象数据类型的描述，不正确的是（ ）。
A．数据封装 B．使用与实现分离
C．信息隐藏 D．用例驱动
【解析】选 D。抽象数据类型（ADT）的三个特点是数据封装、信息隐藏、使用与实现
分离，即把数据结构的实现封装在模块内部，使用者只能通过模块接口的操作来访问模块内
存储的数据。其作用是使将来的变更局部化。目前 ADT 已成为系统实现的核心技术。用例
是系统分析时描述功能的图示，与 ADT 无关。
题 1.2.6 算法的时间复杂度与（ ）有关。
A．问题规模 B．计算机硬件的运行速度
C．源程序的长度 D．编译后执行程序的质量
【解析】选 A。算法的具体执行时间与计算机硬件的运行速度、编译产生的目标程序的
质量有关，但这属于事后测量。算法的时间复杂度的度量属于事前估计，与问题的规模有关。
题 1.2.7 某算法的时间复杂度是 O(n2)，表明该算法（ ）。
A．问题规模是 n2 B．问题规模与 n2 成正比
C．执行时间等于 n2 D．执行时间与 n2 成正比
【解析】选 D。算法的的时间复杂度是 O(n2)，这是设定问题规模为 n 的分析结果，所
以 A、B 都不对；它也不表明执行时间等于 n2，它只表明算法的执行时间 T(n)≤c×n2（c 为
比例常数）。有的算法，如 n×n 矩阵的转置，时间复杂度为 O(n2)，不表明问题规模是 n2。
题 1.2.8 下面说法中错误的是（ ）。
① 算法原地工作的含义是指不需要任何额外的辅助空间
② 在相同问题规模 n 下时间复杂度为 O(n)的算法总是优于时间复杂度为 O(2n)的算法
③ 所谓时间复杂度是指在最坏情形下估算算法执行时间的一个上界
④ 同一个算法，实现语言的级别越高，执行效率越低
A．① B．① ② C．① ④ D． ③
【解析】选 A。算法原地工作的含义指空间复杂度 O(1)。
题 1.2.9 在下列程序中：
- 8 -
void calc( int pl, int p2 ) {
p2 = p2*p2; pl = p1-p2; p2 = p2-p1;
} //calc
void main {
int i = 2, j = 3;
calc(i, j); cout << j << endl;
} //main
当参数传递改用引用方式（Call by reference）时，所得结果 j =（ 1 ）；
A．2 B．16 C．20 D．28
当参数传递采用赋值方式 ( Call by value) 时，所得结果 j =（ 2 ）。
A．0 B．3 C．5 D．6
【解析】(1) 选 B，(2) 选 B。引用方式传递参数的实质是传送作为实际参数的变量的
地址，这样函数体内的运算将会直接对该变量进行操作，改变变量本身的内容。赋值方式传
递参数只是将变量的内容赋给参数，函数体内只是对该变量的副本进行操作，这样不能改变
作为实际参数的变量本身的内容。
题 1.2.10 设有以下三个函数：
f(n) = 100n3+n2+1000, g(n) = 25n3+4000n2， h(n) = n2.01+1000nlog2n
以下关系式中有错误的是（ ）。
A．f(n) = O(g(n)) B．g(n) = O(f(n)) C．h(n) = O(n2.01) D．h(n) = O(nlog2n)
【解析】选 D。因为 f(n) = O(n3)，g(n) = O(n3)，当 n→∞时，显然 n2.01比 nlog2n 增长得
快，h(n) = O(n2.01)，所以，f(n) = O(g(n))，g(n) = O(f(n))，而 h(n) = O(nlog2n)不对。
题 1.2.11 下列函数中渐进时间复杂性最小的是（ ）。
A．T1(n) = nlog2n + 1000log2n B．T2(n) =
C．T3(n) = n2 – 1000log2n D．T4(n) = 2nlog2n – 1000log2n
【解析】选 A。因为 T1(n) = O(nlog2n)，T2(n) = O( )，T3(n) = O(n2 )，T4(n) = O(nlog2n)。
虽然 T1(n) = O(T4(n))，但 T4(n)中 nlog2n 是 T1(n)的 2 倍，所以 T1(n)的渐进时间复杂性最低。
题 1.2.12 判断下列各对函数 f(n)和 g(n)，当 n→∞时，增长最快的函数是（ ）。
A.
B.
C.
D.
【解析】选 D。一般情况下，指数级和阶乘级比多项式级的增长速度快得多。
1.2.4 综合应用题选讲
题 1.2.13 用归纳法证明：
(1)
(2)
(3)
【参考答案】证明过程如下。
(1) 当 n = 1， 成立。设当 n = k 时公式成立，即 ，
3log2n
7n2n)n(g)10!n(ln10)n(f 4n2
3 ++=++=
5.22 13n)n(g)5)!n(ln()n(f =+=
n))!n(ln()n(g1nn)n(f 241.2 +=++=
5)n(2n)n( nn)n(g)2(2)n(f
23 +=+=
nlog1000n 2
3log2 −
1n ,
2
1)n(ni
n
1i
≥+=∑
=
1n ,
6
1)1)(2nn(ni
n
1i
2 ≥++=∑
=
0n 1, x,
1x
1xx
1nn
0i
i ≥≠−
−=
+
=
∑
2
)11(*11i
1
1i
+==∑
= 2
)1k(*ki
k
1i
+=∑
=
- 9 -
当 n = k+1 时， ，结论成立。
(2) 当 n = 1， 成立，
设当 n = k 时公式成立，即
当 n = k+1 时，
结论成立。
(3) 当 n = 0， 成立，设当 n = k 时 成立，
当 n = k+1 时，
结论成立，这实际上就是求等比级数的和。
证毕
题 1.2.14 设 n 为正整数, 分析下列各程序段中加下划线的语句的执行次数。
(1) int i, j, k;
for ( i = 1; i <= n; i++ )
for ( j = 1; j <= n; j++ ) {
c[i][j] = 0.0;
for ( k = 1; k <= n; k++ )
c[i][j] = c[i][j] + a[i][k] * b[k][j];
}
(2) int i, j, k, x = 0, y = 0;
for ( i = 1; i <= n; i++ )
for ( j = 1; j <= i; j++ )
for ( k = 1; k <= j; k++ )
x = x + y;
【参考答案】当 n 给定后，各小题中加下划线的语句的执行次数如下。
(1)
(2)
题 1.2.15 有实现同一功能的两个算法 A1 和 A2，其中 A1 的渐进时间复杂度是 T1(n) =
O(2n)，A2 的渐进时间复杂度是 T2(n) = O(n2)。仅就时间复杂度而言，具体分析这两个算法
哪个好。
【参考答案】比较算法好坏需比较两个函数 2n和 n2。
当 n = 1 时，21 > 12，算法 A2 好于 A1
当 n = 2 时，22 = 22，算法 A1 与 A2 相当
6
2)1)(nn(n
2
1)n(n
2
1
6
1)1)(2nn(n
2
1
i
2
1i
2
1
2
1)i(ij1
n
1i
n
1i
n
1i
2
n
1i
i
1j
n
1i
i
1j
j
1k
++=++++=
=+=⎟⎠
⎞⎜⎝
⎛ +== ∑ ∑∑∑ ∑ ∑ ∑∑
= === = = ==
∑∑∑
= = =
=
n
1i
n
1j
3
n
1k
n1
2
)2k)(1k(1k
2
)1k(k)1k(ii
k
1i
1k
1i
++=+++=++=∑∑
=
+
=
6
)11*2(*)11(*11i
1
1i
2 ++==∑
=
6
)1k*2(*)1k(*ki
k
1i
2 ++=∑
=
22
k
1i
2
1k
1i
2 )1k(
6
)1k*2(*)1k(*k)1k(ii ++++=++=∑∑
=
+
=
6
)6k7k2)(1k(
6
)6k6kk2(1)k 22 +++=++++=（
6
)1)1k(2)(1)1k)((1k(
6
)3k2)(2k)(1k( +++++=+++=
1x
1x1x
100
0i
i
−
−==
+
=
∑ 1x 1xx
1kk
0i
i
−
−=
+
=
∑
1x
1x
1x
)1x(x1xx
1x
1xxxx
2k1k1k
1k
1kk
0i
1ki
1k
0i
i
−
−=−
−+−=+−
−=+=
+++
+
+
=
+
+
=
∑∑
- 10 -
当 n = 3 时，23 < 32，算法 A1好于 A2
当 n = 4 时，24 > 42，算法 A2好于 A1
当 n > 4 时，2n > n2，算法 A2好于 A1
当 n→∞时，算法 A2在时间上显然优于 A1。
另一种解法是对算法 A1和 A2的时间复杂度 T1(n)和 T2(n)取对数，得 nlog2 和 2logn，用
大 O 表示，有 T1(n) = O(n)，T2(n) = O(logn)。显然，算法 A2好于 A1。
题 1.2.16 按增长率由小至大的顺序排列下列各函数：
2100，(3/2)n，(2/3)n，(4/3)n，nn，n3/2，n2/3， ，n!，n，log2n，n/log2n，
(log2n)2，log2(log2n)，nlog2n， 。
【参考答案】各函数的排列次序如下：
(2/3)n，2100，log2(log2n)，log2n，(log2n)2， ，n2/3，n／log2n，n，nlog2n，n3/2，
(4/3)n，(3/2)n， ，n!，nn。
题 1.2.17 已知有实现同一功能的两个算法，其时间复杂度分别为 0(2n)和 0(n10)，假设
计算机可连续运算的时间为 l07秒（100 多天），又每秒可执行基本操作（根据这些操作来估
算算法时间复杂度）105次。试问在此条件下，这两个算法可解问题的规模（即 n 值的范围）
各为多少？哪个算法更适宜？请说明理由。
【参考答案】根据假设，计算机可连续运行 107 秒，每秒可执行基本操作 105，那么计
算机可连续执行基本操作 107*105 = 1012次。在此能力限制下，算法 1 的时间复杂性为 O(2n)，
则可求得问题规模 n≤log2(1012) = 12log210；算法 2 的时间复杂性为 O(n10)，则其问题规模
n≤(1012)0.1。显然，算法 1 适用的问题规模范围更大些，更适宜些。由此得到一个结论：虽
然在一般情况下，多项式阶的算法比指数阶的算法能更快解决问题，但高次多项式的算法在
n 的范围上还不如指数阶的算法。
题 1.2.18 试举一个例子，说明对相同的逻辑结构，同一种运算在不同的存储方式下实
现，其运算效率不同。
【参考答案】例如，线性表中的插入和删除操作，在顺序存储方式下平均移动近一半的
元素，时间复杂度为 O(n)；而在链式存储方式下，插入和删除时间复杂度都是 O(1)。
题 1.2.19 运算是数据结构要讨论的一个重要方面。试举一个例子，说明两个数据结构
的逻辑结构和存储方式完全相同，只是对于运算的定义不同。因而两个结构具有显著不同的
特性，是两个不同的结构。
【参考答案】例如，栈和队列的逻辑结构相同，其存储表示也可相同，无论是顺序存储
表示还是链接存储表示，但由于其运算集合不同而成为不同的数据结构。
题 1.2.20 指出下列各算法的功能并求出其时间复杂度。
(1) int Prime ( int n ) {
int i = 2, x = (int) sqrt (n); //sqrt(n)为求 n 的平方根
while ( i <= x ) {
if ( n % i == 0 ) break;
i++;
}
if ( i > x ) return 1;
else return 0;
};
(2) int sum1( int n ) {
int p = 1, s = 0;
for ( int i = 1; i <= n; i++ )
n
nlog2n
n
nlog2n
- 11 -
{ p *= i; s += p; }
return s;
};
(3) int sum2 ( int n ) {
int s = 0;
for ( int i = 1; i <= n; i++ ) {
int p = 1;
for ( int j = 1; j <= i; j++ ) p *= j;
s += p;
}
return s;
};
(4) int fun ( int n ) {
int i = 1, s = 1;
while ( s < n ) s += ++i;
return i;
};
(5) void mtable ( int n ) {
for ( int i = 1; i <= n; i++) {
for ( int j = i; j <= n; j++ )
cout << i << "*" << j << "=" << setw(2) << i*j << " ";
cout << endl;
}
};
【参考答案】
(1) 判断整数 n 是否素数，如果是则函数返回 1，否则返回 0。算法时间复杂性 T(n) =
O( )。
(2) 计算 ，即 1, 1*2, 1*2*3, !*2*3*4, ..., 1*2*3*…*n 的和。算法时间复杂性 T(n) =
O(n)。
(3) 同样计算 。算法时间复杂性 T(n) = O(n2)。这是因为没有像上题那样保留计算
的中间结果，每次都重新计算 1*2*…*i，程序步数达到
(4) 求出满足不等式 1+2+3+L+i≥n 的最小 i 值。例如，n = 100，当 i = 14 时，满足
1+2+…+13 = 91＜100，1+2+…+14 = 105≥100。
从 i(i-1)/2＜n 可得，i2-i-2n＜0，用代数法求解得
因此可知，算法时间复杂性为 O( )。
(5) 打印 n 以内整数的乘法口诀表。第 i 行（1≤i≤n）中有 n-i 个乘法项，每个乘法项
为 i 与 j（i≤j≤n）的乘积。算法时间复杂性
∑∑ ∑
= = −
=+==
n
1i
i
1j
2
n
1i
)n(O
2
)1n(ni1
2
n811i +±<
)n(O
2
)1n(n)in(1)n(T 2
n
1i
n
1i
n
1ij
=−=−== ∑∑∑
== +=
n
∑
=
n
1i
!i
∑
=
n
1i
!i
n
- 12 -
1.3 使用 C/C++的几个规则
在程序或算法描述中，使用 C/C++语言，主要涉及算法结构、函数参数、指针、条件、
动态存储分配等主要问题，常用的规则如下所述。
1.3.1 算法结构
算法结构的
规范
编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载
描述为
<返回类型> 算法名 ( <参数表> ) {
//算法功能说明（用文字描述）
变量说明语句；
算法执行语句；
};
其中，<返回类型>可以是无值（void）或其他类型，如果返回类型不是 void，算法最后
要用 return ×××返回需要返回的结果。<参数表>给出算法所需输入数据或输出结果。
1.3.2 函数参数
对于参数表内的构造型参数，如作为操作主体，可定义为引用型（&），目的是可直接
操作实际实体对象，不必在函数内建立副本。
对于算法需要输出的数据，可在参数表内声明为引用型参数（&），目的是将该参数当
作实际变量的别名，函数内对它操作就是对实际变量操作，操作结果可直接送给实际变量。
对于指针型参数，如果操作后指针保存的地址有变化，也应定义为引用型（*&），目的
是在函数返回时带回变化后指针的值，且在函数内可像操作普通变量那样操作指针变量。
除此以外，如果想把值直接输入，或函数对输入的数据不需要改变，或改变后的值不需
要返回，这样的参数都可定义为传值参数。
注意，出现在参数表中的数组，如 int A[ ]，不可写 int& A[ ]。因为数组本来在参数表
中就是传地址的。而且在参数表内不能写成 int A[n]，而是分开写 int A[ ], int n。
1.3.3 条件运算
条件运算分关系运算和逻辑运算。比较运算符有<、<=、==、!=、>=、>，运算结果为
false（0）和 true（1）。逻辑运算法有！（非）、&&（与）、||（或）。逻辑运算的优先级低于
比较运算符（限于 C/C++，因为 Pascal 正好相反）。在逻辑运算内，各逻辑运算符的优先级
从高到低为!、&&、||。
对于复合条件运算，运算顺序需要特别说明。
例如，对于表达式 A && B，当 A 为 true 时，还要看 B，当 B 也为 true 时表达式为 true，
当 B 为 false 时表达式为 false；当 A 为 false 时表达式为 false，不需要再看 B。
例如，对于表达式 A || B，当 A 为 true 时，表达式为 true，不需要再看 B；当 A 为 false
时，还要看 B，当 B 为 true 时表达式为 true，当 B 为 false 时表达式为 false。
1.3.4 动态存储分配
在 C 中动态存储分配的函数用 malloc，动态回收的函数用 free。例如，动态分配一个整
数数组的存储的语句和动态回收这个数组所占用存储的语句分别为
int *visited = (int *) malloc ( maxSize*sizeof (int) );
free (visited);
malloc 做了三件事：首先按 int 计算待分配字节数，然后动态分配存储空间，最后把首
- 13 -
地址用类型转换强制转换为指向 int 的指针返回；如果存储分配失败，返回 NULL。
在 C++中动态存储分配函数用 new，动态回收的函数为 delete。同样动态分配一个整数
数组的存储的语句和动态回收这个数组所占用存储的语句分别为
int *visited = new int[maxSize];
delete [] vosited;
显然后者简洁，它与 Pascal 语言和 JAVA 语言相通。本书采用后者作为动态存储分配和
回收的语句。
1.3.5 标准输入/输出
C 语言中的标准输入/输出语句为 stdin、stdout 和 stderr。在 C++中用 cin，cout 和 cerr。
使用 C++中的标准输入/输出的优点是简单，许多输出数据类型和输出格式问题都由系统代
劳了。所以本书中输入数据一律用 cin >> a 或 cin >> a >> b 形式输入数据或输入多个数据；
输出数据一律用 cout << n << endl 或 cout << ”a : " << n << "f : " << f << endl 形式。其中的
“endl”是换行。
1.3.6 指针
所谓指针，就意味着“地址”。C/C++的指针使用一定要理解和掌握。
如果指针 p 保持的是一个数据的存放地址，p 本身是该数据的存储地址，*p 是该数据的
内容。如果*p 在赋值符“=”的右边，表明取出 P 指示地址中保存的数据值；如果*p 在赋
值符“=”的左边，表示向 p 所指示的地址内存放数据值。
如果指针 p 保持的是一个数组中某一元素的地址，与上述情况相同。但可以用 p++把指
针 p 所保持的地址加 1，以指示下一数组元素的地址；用 p—-把指针 p 所保持的地址减 1，
以指示前一数组元素的地址。
如果指针 p 指示的是一个链表结点，则用*p 表示结点本身，但不能用*p 得到结点内保
存的数据值。必须使用 p->data 得到该结点的数据值，用 p->link 或 p->next 得到该结点所
保存的链表下一结点的地址。用 p++可以让指针 p 指向物理上的下一结点，但 p++与 p->link
可能不相等，因为 p->link 指示的是 p 所指示结点的逻辑上的下一结点，而一个链表结点的
逻辑上的下一个结点不一定是物理上的下一个结点。
如果有两个指针 p 和 q 都是链表结点指针，它们的初始状态如图 1.3(a)所示。
语句 p = q 的执行结果如图 1.3(b)所示，由于地址的传送，p 也指向 q 所指向的结点。
语句 q = p->link 的执行结果如图 1.3(c)所示，把 p 所指示结点的 link 域内保存的结点地
址赋给指针 q，使得指针 q 指向 p 的下一结点。
最后，语句 p = p->link 就是链表操作中常用的让指针 p 进到链表下一结点的语句，如
图 1.3(d)所示。
图 1.3 指针操作
p
q
p
q
(a) (b) p = q
p
q
(c) q = p->link
p
p
(d) p = p->link
浙公网安备 33021202002483