第15章 算法与数据结构(讲稿)

第十五章数据结构与算法

大纲要求：

1.算法的基本概念；算法复杂麦的概念和意义（时间复杂度与空间复杂度）。

2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性

结构的概念。

3.线性表的定义；线性表的顺序存储结构及其插入与删除运算。

4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。

5.线性单链表、双向链表与循环链表的结构及其基本运算。

6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。

7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。

重要考点：

L算法复杂度.

2.数据结构、栈、队列、线性链表的基本概念。

3.二叉树和存储结构

4.线性表、树的节点计算和遍历。

5.冒泡排序的最坏次数计算。

15.1算法

知识点1算法的基本概念

所谓算法是对■特定问题求解步骤的一种描述。

基本特征如下：

（I）可行性：算法的每一步操作都可通过已有的基本操作执行有限次实现。

（2）有穷性：算法必须在执行有穷步之后结束，包括合理的执行时间的含义。

（3）确定性：算法中每一步骤都必须有明确定义，他人理解时不可产生二义性。

（4）输出：一个算法应该有一个或多个输出。

【经典题解】

I、算法的有穷性是指

A）算法程序的运行时间是有限的

B）算法程序所处理的数据量是有限的

C）算法程序的长度是有限的

D）算法只能被有限的用户使用

【答案】A

【解析】此题主要考查有穷性的概念：算法必须在执行有穷步之后结束，包括合理的执行

时间的含义。

知识点2算法的时间复杂度

所谓算法的时间复杂度是指执行算法所需要的计算工作量,算法的工作量用算法所执行

的基本运算次数来度量。

例如，有如下两个程序段：

（1）s=s+i

（2）fori=0ton

s=s+i

nexti

这两个程序段的时间复杂度分别为0（1）和0（2。

算法所执行的基本运算次数与问题的规模有关，还可能与特定的输入有关。在同一个问

题的规模下，如果算法执行所需的基本运算次数取决于某一特定输入时，可以用两种方法来

分析算法的工作量：一种是平均性态分析，另一种是讨论算法在最坏情况下的时间复杂度。

后者比前者更具有实用价值。

【经典题解】

1、算法的时间复杂度是指

A）算法的执行时间

B）算法所处理的数据量

C）算法程序中的语句或指令条数

D）算法在执行过程中所需要的基本运算次数

【答案】D

【解析】此题主要考查算法时间复杂度的概念：是指执行算法所需要的基本运算次数。

知识点3算法的空间复杂度

所谓算法的空间复杂度是指执行这个算法所需要的存储空间。B寸间复杂度与空间复杂度

之间无必然联系。

【经典题解】

1、©法的空间复杂度是指

A）算法在执行过程中所需要的计算机存储空间

B）算法所处理的数据量

C）和法程序中的语句或指令条数

D）算法在执行过程中所需要的临时工作单元数

【答案】A

【解析】此题主要考查算法空间复杂度的概念：所谓算法的空间复杂度是指执行这个算法

所需要的内存空间。

15.2数据结构的基本概念

知识点4数据结构

（1）数据结构是指相互之间存在一种或多种特性关系的数据元素的集合。

（2）数据结构可以分为逻辑结构和存储结构两种。一般来说，一种数据的逻辑结构根

据需要可以表示成多种存储结构。而采用不同的存储结构，其数据处理效率是不同的。

图15-1为数据结构所涵盖的三个方面：

'线性表

'线性结构«栈

r数据的逻辑结构J队列

（树形结构

I非线性结构’

图形结构

]顺序存储结构

数据的存储结构•

链式存储结构

I数据的运算：查找、排序

图15-1数据结构涵盖的三方面

知识点5数据的逻辑结构

（I）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。

（2）数据的逻辑结构分为线性结构和非线性结构两种。

（3）满足条件：有且只有一个根结点；每一个结点最多有一个前件•，也最多有一个后

件，则该数据结构称为线性结构。

（4）不满足线性结构条件的数据结构称为非线性结构。

知识点6数据的存储结构

（1）各数据元素在计算机中的存储关系，即数据的存储结构。

（2）数据的存储结构主要包括顺序存储结构和链式存储结构等。

（3）所谓顺序存储结构，是指在计算机中用一组地址连续的存储单元依次存储数据。

（4）所谓链式存储结构，是指在计算机中用一组任意的存储单元依次存储数据。

图15-2是顺序存储结构和链式存储结构的示意图:

地址编号内存

15-2顺序存储结构和俄式存储结构模型

【经典题解】

1.下列叙述中正确的是

A）顺序存储结构的存储空间一定是连续的，链式存储结构的存储空间不一定是连续的

B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构

o顺序存储结构能存储力.序表，链式存储结构不能存储有序表

D）链式存储结构比顺序存储结构节省存偌空间

【答案】A

【解析】此题主要考查逻辑结构与存储结构之间的关系：数据的逻辑结构与存储结构无必

然联系；不论哪种存储结构，均不能节省空间，故A项正确。

15.3线性表及其顺序存储结构

知识点7线性表的基本概念

线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号。简言之，一个线

性表是n个元素的有限序列。线性表中每一个数据称为一个节点。结点个数n称为线性表

的长度，当n=0时，称为空表。

知识点8线性表的顺序存储结构

线性表的顺序存储结构具有以下二个基本特点：

（1）线性表中所有元素所占的存储空间是连续的。

（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

线性表的长度在处理过程中是动态变化的，在开辟线性表的存储空间时要考虑到线性表

在动态变化过程中可能达到的最大长度。

【经典题解】

1、下列叙述中正确的是

A）线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的

B）线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构

C）线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构

D）上述三种说法都不对

【答案】B

【解析】此题主要考查线性表的链式存储结构和线性存储结构：当线性表的长度确定，采

用顺序存储结构一般只需要存储线性表中的元素；采用链式存储结构，除了要存储元素本

身的信息外，还要存储指向下一个元素位置的指针，因此B选项正确。

15.4栈和队列

知识点9栈及其基本运算

图15-3为栈数据结构的模型：

（I）栈是限定在一端进行插入与删除的线性表。允许插入与删除的一端称为栈顶，不

允许插入与删除的另一端称为栈底。

（2）栈按照“先进后出"（FILO）或“后进先出"（LIFO）组织数据：用top表示栈顶位

置，用bottom表示栈底。

（3）插入元素称为入栈运算；删除元素称为退栈运算。

（4）在栈的运算过程中，栈底的位置始终保持不变，而栈顶的位置却随着入栈、退栈

操作不断变化。

【经典题解】

1、下列叙述中正确的是

A）在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化

B）在栈中，栈顶指针不变，或中元素随栈底指针的变化而动态变化

C）在栈中，栈底指针不变，戌中元素随栈顶指针的变化而动态变化

D）上述三种说法都不对

【答案】C

【解析】此题主要考查栈的特性。

栈中栈底的指针永远不会变化，栈顶指针随着栈中元素的变化而变化，因此C选项正确。

2、一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后

再依次出栈，则元素出栈的顺序是

A）123456ABCDE

B）EDCBA54321

C）ABCDE12345

D）54321EDCBA

【答案】B

【解析】此题主要考查栈的工作特性。

栈是“先进后出”，因此B选项正确。

3、下列关于栈的叙述正确的是

A）栈按“先进先出”组织数据

B）栈按“先进后出”组织数据

C）只能在栈底插入数据

D）不能删除数据

【答案】B

【解析】此题主要考查栈的特性：栈是“先进后出”，因此B选项正确。

4、一个栈的初始状态为空。首先将元素5,4,3,2,1依次入栈，然后退栈一次，再将元

素A,B,C,D依次入栈，之后将所有元素全部退栈，则所有元素退栈（包括中间退栈的元素）

的顺序为一o

【答案】1DCBA2345

【解析】此题主要考查栈的特性：栈是“先进后出”。

5、假设用一个长度为50的数组（数组元素的下标从0到49）作为栈的存储空间，栈底指

针bottom指向栈底元素，栈顶指针lop指向栈顶元素，如果boilom=49.lop=30（数组下标），

则栈中具有个元素。

【答案】|

【解析】此题主要考查栈的特性：栈从31（数组下标）开始存放数据，到49结束存放，故

元素个数为19。

知识点10队列及其基本运算

图15-4为队列数据结构的模型：

出队列入队列

队头（front）队尾（rear）

图15-4队列的模型

（1）队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。

（2）队列是“先进先出"（FIFO）或“后进后出"（LILO）的线性表：Rear指针指向队尾,

front指针指向队头。

（3）入队运算：从队尾插入一个元素：退队运算：从队头删除一个元素。

（4）在队列运算中，队尾（rear）的位置随着入队运算而不断发生变化，对头（front）

的位置随着退队运算而不断发生变化。

（5）在队列中队尾指针一定大于对头指针。所谓指针，是指对应存储单元在内存中的

编号或者地址。

【经典题解】

1、一个队列的初始状态为空。现将元素A,B,C,D,E,F,5,4,321依次入队，然后再依次退队,

则元素退队的顺序为0

【答案】ABCDEF54321

【解析】此题主要考查队列的特性，队列的特性为“先进先出”。

知识点11循环队列及其基本运算

（1）循环队列是一种特殊的队列，逻辑上它是首尾相接的环形区域。

（2）循环队列中，对头指针可能大于队尾指针，也可能小于队尾指针。

（3）循环队列解决了队列的“假满”问题。

在循环队列中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所

有的结点，而线性单链表做不到这一点。

图15-5是循环队列的数据模型：

【经典题解】

1、下列数据结构中，能够按照“先进后出”原则存取数据的是

A）循环队列

B）栈

C）队列

D）二叉树

【答案】B

【解析】此题主要考查栈的特性。

栈的基本特性是“先进后出”，因此B选项正确。

2、对于循环队列，下列叙述中正确的是

A）队头指针是固定不变的

B）队头指针一定大于队尾指曾

C）队头指针一定小于队尾指升

D）队头指针可以大于队尾指针，也可以小于队尾指针

【答案】D

【解析】此题主要考查循环队列的特性：队头指针可能大于队尾指针，也可能小于队尾指

针。

3、下列叙述中正确的是

A）栈是“先进先出''的线性表

B）队列是“后进先出”的线性表

C）循环队列是非线性结构

D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构

【答案】D

【解析】此题主要考查栈和队列的特性。

栈是“先进后出”，队列是“先进先出”，栈和队列都是一种特殊的线性结构，因此D选项

正确。

4、下列叙述中正确的是

A）循环队列有队头和队尾两个指针，因此，循环队列是非线性结构

B）在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况

C）在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况

D）循环队列中元素的个数是方队头指针和队尾指针共同决定

【答案】D

【解析】此题主要考查循环队列的特性：循环队列是一种特殊的队列，它同样属于线性结

构，循环队列中元素的个数由对头指针和队尾指针共同决定。

5、设某循环队列的容量为50,如果头指针front=45（指向队头元素的前一位置），尾指针

rear=10（指向队尾元素），则该循环队列中共有个元素

【答案】15

【解析】此题主要考查循环队列的特性：循环队列都是从队头开始、队尾结束，故元素个

数为50-45+10=15

6、设某循环队列的容量为50：头指针froni=5（指向队头元素的前一位置），尾指针rear=29

（指向队尾元素），则该循环队列中共有个元素。

【答案】24

【解析】此题主要考查循环队列的特性，做法同第5题。

15.5线性链表

知识点12线性链表的基本概念

（1）在线性表的捱式存储结构中，各数据结点的存储单元可以是不连续的。

（2）各数据结点的存储顺序与数据元素之间的逻辑关系正以不一致。

（3）数据元素之间的逻辑关系是由指针域来确定的。

（4）链式存储方式既可用于表示线性结构，也可用于表示非线性结构。

15.6树与二叉树

知识点13树的基本概念

（1）树是一种简单的非线性结构，所有元素之间具有明显的层次特性。

（2）在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个,

称为树的根结点，简称树的根。

（3）每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结

点。

（4）在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的

度称为树的度。

（5）树的最大层次称为树的深度。

【经典题解】

1、支持了程序调用的数据结构是

A）栈B）树C）队列D）二叉树

【答案】A

知识点14二叉树及其基本性质

二叉树具有两个特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵

子树，且分别称为该结点的左子树与右子树。

二叉树有以下几个性质：

（I）在二叉树的第k层上,最多有2k人心1）个结点。

（2）深度为m的二叉树最多有2m-1个结点。

（3）度为0的结点（即叶子结点）总是比度为2的结点多一个。

满二叉树是指除最后一层外.每一层卜的所有结点有两个子结点.满二叉树的第k层卜

有2kl个结点，且深度为m的满二叉树有2m.i个结点。

完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少

右边的若干结点。

在计算机中，二叉树通常采用链式存储结构。

【经典题解】

1、某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是

A）10B）8C）6D）4

【答案】C

【解析】此题主要考查二叉树的特性：度为0的结点（即叶子结点）总是比度为2的结点

多一个，因此C选项正确。

2、一棵二叉树有10个度为I的结点，7个度为2的结点，则该二叉树共有个结点。

【答案】25

【解析】此题主要考查二叉树的特性：二叉树由度为0的节点、度为1的节点和度为2的

节点共同组成，已知度为1的节点和度为2的节点，而度为0的结点（即叶子结点）总是

比度为2的结点多一个，因此节点总数为10+7+8=25o

3、某二叉树有5个度为2的结点以及3个度为I的结点，则该二义树共有个结点。

【答案】14

【解析】此题主要考查二叉树的特性：二叉树由度为0的节点、度为1的节点和度为2的

节点共同组成，己知度为1的节点和度为2的节点，而度为0的结点（即叶子结点）总是

比度为2的结点多一个，因此节点总数为5+3+6=14。

4、深度为5的满二叉树有个叶子结点

【答案】16

【解析】此题主要考查二叉树的特性：满二叉树只可能最后一层上有叶子节点，而在二叉

树的第k层上，最多有2k”化”)个结点，故答案为2§」=16。

知识点15二叉树的遍历

二叉树的遍历是指不重复地访问二叉树中所有节点。

二叉树的遍历可以分为三种：前序遍历、中序遍历和后序遍历。

(1)前序遍历

若二叉树为空，则结束返回。

否则：①访问根结点：②前序遍历左子树：③前序遍历右子树。

(2)中序遍历

若二叉树为空，则结束返回。

否则：①中序遍历左子树：②访问根结点：③中序遍历右子树。

(3)后序遍历

若二叉树为空，则结束返回。

否则：①后序遍历左子树：②后序遍历右子树：③访问根结点。

【经典题解】

1、设二叉树如下：

对该二叉树进行后序遍历的结果为°

【答案】EDBGHFCA

【解析】此题主要考查二叉树遍历的方法：后序遍历(LRD)首先遍历左子树，然后访问

遍历右子树，最后访问根结点。

2、对下列二叉树进行中序遍历的结果。

DEF

XYZ

【答案】DBXEAYFZC

【解析】此题主要考查二叉树遍历的方法。

中序遍历(LDR),首先遍历左子树，然后访问根结点，最后遍历右子树。

15.7查找技术

知识点16顺序查找法

顺序查找是从线性表开始位置的元素往后逐一进行比较，直到找到或找不到该元素为

止。

(I)在平均情况下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中一

半的元素进行比较。在最坏情况下，需要比较的次数为n次。

(2)适用干顺序存储结构和链式存储结构.

知识点17二分查找法

二分查找是先确定待查元素所在范围(区段)，然后逐步缩小范围直到找到或找不到该

元素为止。

(1)二分查找法只适用干顺序存储的有序表。

(2)对于长度为n的有序线性表，二分查找最坏情况只需比较log2n次。

【经典题解】

1、下列叙述中正确的是

A)对长度为n的有序链表进行查找，最坏情况卜.需要的比较次数为n

B)对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(n/2)

C)对长度为n的有序锥表进行对分查找，最坏情况下需要的比较次数为(k)g2n)

D)对长度为n的有序链表进行对分查找，最坏情况卜.需要的比较次数为(nlogzn)

【答案】A

【解析】对于长度为n的有序线性表，二分查找最坏情况只需比较log2n次。

2、在长度为n的有序线性表中进行二分查找，最坏情况卜需要比较的次数是

A)0(11)

B)0(n2)

C)O(log2n)

D)O(nlog2n)

【答案】C

【解析】此题主要考查二分查找法算法：对于长度为n的有序线性表，二分查找最坏情况

只需比较log2n次。

15.8排序技术

知识点18排序技术

排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。

（I）日泡排序法：在最坏的情况下，需要比较n（n-1）/2次。

（2）直接插入排序法:在最坏的情况下，需要比较n（n-1j/2次。

（3）简单选择排序法：在最坏的情况卜.，需要比较n（n-1）/2次。

（4）堆排序法：在最坏情况下，需要比较nlog2n次。堆排序是上述几种排序中比较次

数最少的排序方法。

【经典题解】

1、下列排序方法中，最坏情况下比较次数最少的是

A）日泡排序B）简单选择排序C）直接插入排序D）堆排序

【答案】D

【解析】此题主要考查各种排序方法的特性。

综合自测

一、选择题

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,下列关于栈的描述中错误的是

A）栈是先进后出的线性表

B）栈只能顺序存储

C）栈具有记忆作用

D）对栈的插入与删除操作中.不需要改变栈底指针

II.下列叙述中正确的是

A）线性链表是线性表的链式存储结构

B）栈与队列是非线性结构

C）双向链表是非线性结构

D）只有根结点的二叉树是线性结构

12.下列对于线性链表的描述中正确的是

A）存储空间不•定是连续，且各元素的存储顺序是任意的

B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面

C）存储空间必须连续，且前冲元素一定存储在后件元素的前面

D）存储空间必须连续，且各元素的存储顺序是任意的

13.一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为

A）219B）221C）229D）231

14.对下列二叉树

进行前序遍历的结果为

A)DYBEAFCZXB)YDEBFZXCA

C)ABDYECFXZD)ABCDEFXYZ

15.某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为

A)n+1B)n-1C)2nD;n/2

16.对下列二叉树进行中序遍历的结果是o

A)ACBDFEGB)ACBDFGEC)ABDCGEFD)FCADBEG

17.对如下二叉树

进行后序遍历的结果为

A)ABCDEFB)DBEAFCC)ABDECFD)DEBFCA

18.在深度为7的满二叉树中，叶子结点的个数为

A)32B)31C)64D)63

19.在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为。

A)63B)64C)6D)7

20.下列数据结构中，能用二分法进行查找的是

A)顺序存储的有序线性表