全国计算机等级考试《二级公共基础知识》【教材精讲+真题解析】讲义

内容简介

为了帮助考生顺利通过全国计算机等级考试，我们根据全国计算机等级考试最新公告、考试大纲以及相关考

试用书，精心编写制作了全国计算机等级考试“二级公共基础知识”辅导系列：

1.全国计算机等级考试《二级公共基础知识》【教材精讲+真题解析】讲义与视频课程112小时高清视频】

2.全国计算机等级考试《二级公共基础知识》题库【历年真题+章节题库+模拟试题】

3.全国计算机等级考试《二级公共基础知识》专用教材【考纲分析+考点精讲+真题演练+强化习题】

本书主要包括以下两部分内容：

I.教材精讲【含12小时视频讲解】。遵循“二级公共基础知识考试大纲（2018版）”的考察要求及指定

参考教材和相关法律法规，名师高清视频深入剖析考试大纲，全面讲解教材重点难点内容，帮助学员巩固知识,

梳理逻辑，轻松应考。

2.真题解析。精选历年考试真题，每道真题均提供详尽答案解析。学员可以熟悉真题的考试特点，巩固知

识点并测试自己的水平。

视频讲解教师简介

全国计算机等级考试辅导（二级）

公共基础知识

网授精讲班

主讲教师：赵亮

赵痉，毕业于中科院研究生院的计算机科学与技术专业。常年从事计算机学科的研究和教学，有较强的专业

知识和教学能力，能够根据学科特点，深入浅出的讲解课程内容，使学生快速理解掌握，达到教学目标。

授课挣点：亲和力强，课堂氛围轻松，授课思路明朗，能够让枯燥的知识形象生动，帮助学员轻松掌握核心

知识点，深受广大学员喜爱。

教材精讲部分［视频讲解I

考试形式

1.公共基础知识不单独考试，与其他二级科目组合在一起，作为二级科目考核内容的一部分。

2.考试方式为上机考试，10道选择题，占10分。

知识点分布

I.数据结构与算法

2.程序设计基础

3.软件工程基础

4.数据库设计基础

大纲基本要求

1.掌握算法的基本概念。

2.掌握基本数据结构及其操作，

3.掌握基本排序和查找算法。

4.掌握逐步求精的结构化程序设计方法。

5.掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。

6.掌握数据库的基本知识，了解关系数据库的设计。

第1章数据结构与算法［视频讲解］

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

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

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

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

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

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

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

1.1算法

一、算法的基本概念

1.算法的定义

算法是指解题方案的准确而完整的描述，即算法是对特定问题求解步骤的一种描述。

【注意】算法不等于程序，也不等于计算方法。

2.算法的基本特征

(1)可行性(Effectiveness)：算法中的每一个步骤必须能够实现，执行的结果要能够达到预期的目的。

(2)确定性(Definiteness)：算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释或多义

性。

(3)有穷性(Fineness)：算法必须能在有限的时间(合理的时间)内做完，即算法必须能在执行有限个步

骤之后终止。

(4)拥有足够的情报：输入是否足够并正确，输出是否合理,初始状态是否正确。

二、算法设计基本方法

I.列举法

(1)基本思想

根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。

(2)特点

简单，方便用计算机进行大量列举；情况较多时，工作量将会很大。

<3)使用

将与问题有关的知识条理化、完备化、系统化，从中找出规律，进行分类，减少列举量。

【例1】今有鸡母一，值钱三；鸡翁一，值钱二；鸡雏一，值钱半。凡百钱买百鸡，问鸡母、鸡翁、鸡雏各

几何？

假设买母鸡I只、公鸡J只、小鸡KN。根据题意，粗略的列举算法描述如下：

FOR1=0TO100STEP1DO

FORJ=0TO100STEP1DO

FORK=0TO100STEP1DO

【卜((l+J+K==100)AND(3*l+2勾+U.5*K==1UU.U))THEN

PRINTI,J,K

)

END

共有三层循环，每层循环各需要循环101次，大约为100万次。

优化后的算法

FOR1=0TO33STEPIDO

FORJ=0TO50-1.5*1STEP1DO

{

K=IOO-I-J

IF(3旬+2*J+0.5*K==100.0)THEN

PRINTI,J,K

}

END

共有两层循环，循环次数为

33

^(51-1.57)^894

/=0

2.归纳法

(I)基本思想

通过列举少量的特殊情况，经过分析最后找出一般的关系。

(2)特点

归纳是•种抽象，即从特殊现象中找出••般关系。

(3)使用

由于在归纳的过程中不可能对所有的情况进行列举。因此，最后由归纳得到的结论还只是•种猜测，还需要

对这种猜测加以必要的证明。实际上，通过精心观察而得到的猜测得不到证实或最后证明猜测是错的，也是常有

的事。

3.递推

(I)基本思想

从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。

(2)特点

本质上属于归纳法，递推关系式往往是归纳的结果。

(3)使用

递推算法在数值计算中是极为常见的。但是，对于数值型的递推算法必须要注意数值计算的稳定性问题。

4.递归

(1)基本思想

为了降低问题的复杂程度，将问题逐层分解，最后归结为一些最简单的问题，这种将问题逐层分解的过程,

实际上并没有对问题进行求解，而只是当解决r最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综

合。

(2)特点

结构清晰，可读性强。

(3)使用

递归在可计算性理论和算法设计中占有很重要的地位。

(4)分类

直接递归(自己调用自己)和间接递归(P调用Q,Q又调用P)。

【例2】编写一个过程，对于输入的参数n,依次打印输出自然数1到n。

非递归算法：

wrt(intn)

(

FORk=lTOnSTEPIDOPRINTk

RETURN

)

递归算法：

wrtl(intn)

(

IF(n#))THEN

(

wrtl(n-l)PRINTn

)

RETURN

5.减半递推技术

所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”的过程。

【例3】设方程f(x)=0在区间［a,b］上有实根，且f(a)与f(b)异号。利用二分法求该方程在区间［a,

用上的一个实根。

用二分法求方程实根的减半递推过程如下：

(I)首先取给定区间的中点c=(a+b)/2o

(2)然后判断f(后是否为0：

如果f(c)=0,则说明c即为所求的根，求解过程结束；

如果f(c)#0,则根据以下原则将原区间减半：

①若f(a)f(c)<0,则取原区间的前半部分；

②若f(b)f(c)<0,则取原区间的后半部分。

(3)最后判断减半后的区间长度是否已经很小：

①若|a-b|Vg,则过程结束，取(a+b)/2为根的近似值；

②若|a-则重复上述的减半过程。

6.回溯法

(1)基本思想

通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成

功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。这种方法称为回溯法。

(2)特点

在工程上，有些实际问题很难归纳出一组简单的递推公式或直观的求解步骤，并且也不能进行无限的列举。

对于这类问题，一种有效的方法是“试工

三、算法复杂度

主要包括时间复杂度和空间复杂度。

1.算法的时间复杂度

(1)定义

执行算法所需要的计算工作量。

(2)衡量标准

通常用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。算法所执行的基本运算次数还与问

题的规模有关。

综上所述，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的

函数，即算法的工作量=t(n)。

(3)存在问题

算法所执行的基本运算次数还可能与特定的输入有关，而实际上乂不可能将所有可能情况下算法所执行的基

本运算次数都列举出来。

(4)解决方法

①平均性态(AverageBehavior)

用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量：

A⑺=£p(x»(x)

②最坏情况复杂性(Worst-CaseComplexity)

规模为n时，算法所执行的基本运算的最大次数：

W(〃)=max{/(x)}

2.算法的空间复杂度

【定义】执行这个算法所需要的内存空间。

(1)算法程序所占的空间：

(2)输入的初始数据所占的存储空间；

(3)算法执行过程中所需要的额外空间。

【注意】

①如果额外空间量相对于问题规模来说是常数，则称该算法是原地工作的。

②在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外

空间。

【考题1】算法的时间复杂度是指(

A.执行算法程序所需要的时间

B.算法程序的长度

C.算法执行过程中所需要的基本运算次数

D.算法执行过程中所需要的所有运算次数

E.算法程序中的指令条数

【答案】C

【解析】算法的时间复杂度是指算法执行过程中所需要的基本运算次数。执行算法程序所需要的时间、算法

长度、指令条数等与时间复杂度没有直接关系。

【考题2】算法的空间复杂度是指（）。

A.算法程序的长度

B.算法程序中的指令条数

C.算法程序所占的存储空间

D.算法执行过程中所需要的存储空间

E.算法所处理的数据量

【答案】D

【解析】算法的空间复杂度是指算法执行过程中所需要的存储空间。算法程序的长度、指令条数、所处理的

数据量等与空间复杂度没有直接关系。

1.2数据结构的基本概念

数据结构作为计算机的一门学科，主要研究和讨论以下三个方面的问题：

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

（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；

（3）对各种数据结构进行的运算。

讨论以上问题的目的：

（I）提高数据处理的速度；

（2）尽量节省在数据处理过程中所占用的计算机存储空间。

一、什么是数据结构

【定义】数据结构是指相互有关联的数据元素的集合。

数据元素具有广泛的含义：

描述一年四季的季节名：春、夏、秋、冬

表示数值的各个数：18、11、35、23、16…

表示家庭成员的各成员名：父亲、儿子、女儿

数据处理：对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也包括对数

据元素进行分析。

【注意】作为某种处理，其中的数据元素一般具有某种共同特征，一般情况下，在具有相同特征的数据元素

集合中，各个数据元素之间存在有某种关系，这种关系反映了该集合中的数据元素所固有的一种结构。

I.数据的逻辑结构

（1）定义

反映数据元素之间逻辑关系的数据结构。一个数据结构应包含以下两方面的信息：

①表示数据元素的信息；

②表示各数据元素之间的前后性关系。

（2）数据的逻辑结构有两个要素：

一是数据元素的集合，通常记为D；

二是D上的关系，它反映了D中各数据元素之间的前后件关系，通常记为R；

即一个数据结构可以表示成B=（D,R）。

【例4】•年四季的数据结构可以表示成

B=（D,R）

D=｛春，夏，秋，冬｝

R=｛（春，夏），（夏，秋），（秋，冬）｝

2.数据的存储结构

定义：数据的逻辑结构在计算机存储空间中的存放形式。

【注意】

①各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的，而且一般也不可能相同。

②在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。

③常用的存储结构有顺序、链接、索引等存储结构。

④采用不同的存储结构，具数据处理的效率是不同的。

二、数据结构的图形表示

一个数据结构除了用二元关系表示外，还可以直观地用图形表示。

（1）对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称为

结点；

（2）对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点，有时箭头可省去。

图M一年四季数据结构的图形表示图（线性）

图1-2家庭成员间关系数据结构的图形表示（树型结构）

【考题】下列叙述中正确的是（

A.线性表是线性结构

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

C.循环链表是非线性结构

D.二叉树是线性结构

【答案】A

【解析】选项A正确；选项B,栈和队列都是线性结构，二者区别是，栈只允许在一端插入和删除，队列

只允许在一端插入，在另一端删除；选项C,循环链表是线性表的链式存储结构；选项D,二叉树是一种典型的

非线性结构。

三、线性结构与非线性结构

根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性

结构”

如果一个非空的数据结构满足下列两个条件：

(1)有且只有一个根结点：

(2)每一个结点最多有一个前件，也最多有一个后件。

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

【注意】在一个线性结构中插入或删除任何一个结点后还应是线性结构。如果一个数据结构不是线性结构,

则称之为非线性结构。

【考题】设数据集合为D={1,3,5,7,9},D上的关系为R。下列数据结构B=(D,R)中为非线性结

构的是()。

A.R={(5,1),(7,9),(1,7),(9,3)}

B.R={(9,7),(L3),(7,I),(3,5)}

C.R={(1,9),(9,7),(7,5),(5,3)}

D.R={(I,3),(3,5),(5,9)}

【答案】D

【解析】如果一个非空的数据结构满足下列两个条件：①有且只有一个根结点；②每一个结点最多有一个前

件，也最多有一个后件。则该数据垢构为线性结构。

选项A：5是根结点，5的后件是1,1的后件是7,7的后件是9,9的后件是3,故选项A是线性结构；

选项B：9是根结点，9的后件是7,7的后件是1,1的后件是3,3的后件是5,故选项B是线性结构；

选项C：1是根结点，1的后件是9,9的后件是7,7的后件是5,5的后件是3,故选项C是线性结构：

选项D：I是根结点，1的后件是3,3的后件是5,5的后件是9,7也是根结点,没有前件也没有后件，线

性数据结构第一个条件不满足，故选项D是非线性结构，即选项D正确。

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

一、线性表的基本概念

线性表(LinearList)是最简单、最常用的一种数据结构。如：一个n维向量、矩阵，学生情况登记表。

线性表是由n(n^O)个数据元素a”a?,…，组成的一个芍限序列，表中的每一个数据元素，除了第一

个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表，或可以表示为(a,,

a2,ai，a„),其中％(i=l,2,n)是属于数据对象的元素，通常也称其为线性表中的一个结点。

车空线性表有如下一些结构特征：

(1)有且只有一个根结点山它无前件；

(2)有且只有一个终端结点加，它无后件；

(3)除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。

【说明】

①线性表中结点的个数n称为线性表的长度。

②当n=0时，称为空表。

二、线性表的顺序存储结构

1.特点

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

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

在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的

前面。

图1-3线性表的顺序存储结构

【注意】

①在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。

②在用一维数组存放线性表时，该一维数组的长度通常要定义得比线性表的实际长度大一些，以便对线性表

进行各种运算，特别是插入运算。

2.线性表的相关操作

（I）插入：在线性表的指定位置处加入一个新的元素，

（2）删除：在线性表中删除指定的元素。

（3）查找：在线性表中查找某个（或某些）特定的元素。

（4）排序：对线性表中的元素进行整序（即线性表的）。

（5）分解：按要求将一个线性表分解成多个线性表。

（6）合并：按要求将多个线性表合并成一个线性表。

（7）复制：复制一个线性表。

（8）逆转:逆转一个线性表。

三、顺序表的插入运算

【例5】长度为8的线性表顺序存储在长度为10的存储空间中。在第2个元素之前插入一个新元素87。然

后在线性表的第9个元素之前插入•个新元素14o

V（l：10）V（l：10）V（l：10）

129129129

叵］—218287287

356318318

463456456

535563563

624635635

731724724

847831831

9回一947914

10101047

（a）长度为8的线性表（b）插入元素87后的线性表（c）插入元素14后的线性表

图1-4线性表在顺序存储结构下的插入

线性表的存储空间从1到m,线性表的长度为n（nWm）,插入的位置为i（i表示在第i个元素之前插入）。

线性表的插入操作如下：

第一步首先处理以下三种异常情况：

①当存储空间已满（即n=m）时为“上溢”错误，不能进行插入，算法结束；

②当i>n时，认为在最后一个元素之后插入；

③当i<l时，认为在第I个元素之前插入。

第二步从最后一个元素开始，直到笫i个元素，每一个元素往后移动一个位置。

第三步将新元素插入到第i个位置，线性表的长度加1。

四、顺序表的删除运算

【例6］长度为8的线性表顺序存储在长度为10的存储空间中。现在要求删除线性表中的第1个元素。再

删除线性表中的第6个元素。

V（l：10）V（l:io）V（I：10）

129118118

218256256

356363363

463435435

535524524

624631647

7317477

84788

999

101010

（a）长度为8的线性表（b）删除兀素29后的线性表（c）删除元素31后的线性表

S1-5线性表在顺序存储结构下的删除

线性表的存储空间从1至Um,线性表的长度为n（n^m）,删除的位置为i（表示删除第i个元素）。线性表

的删除操作如下：

第一步首先处理以下两种异常情况：

①当线性表为空（即n=0）时错误，不能进行删除，算法结束；

②当i<l或>1!时・，错误，不能进行删除，算法结束。

第二步删除线性表中的第i个元素。

第三步从第i+1个元素开始，直到最后一个元素，其中每一个元素均依次往前移动一个位置。线性表的长

度减小1。

1.4栈和队列

一、栈及其基本运算

1.什么是栈

【定义】限定在一端进行插入与删除的线性表

【说明】

①允许插入与删除的一端称为栈顶（指针top）,而不允许插入与删除的另一端称为栈底（指针bottom）。

②栈是按照“先进后出"（FILO）的原则组织数据。

③栈具有记忆作用。

④往栈中插入一个元素称为入栈运算，从栈中删除一个元素（即删除栈顶元素）称为出栈运算.

人栈退栈

2.栈的顺序存储及其运算

图1-7（a）是容量为10的栈顺序存储空间，栈中已有6个元素；图1-7（b）与图1-7（c）分别为入栈与退

栈后的状态。

S（l：10）S（l：10）S（l：10）

101010

999

8top—►8Y8

77Xtop—>7X

top—>6F6F6F

5E5E5E

4D4D4D

3C3C3C

2B2B2B

rA

bottom—1bottom—►1Abottom—>1A

（a）有6个元素的栈（b）插入X与Y后的栈（c）退出一个元素后的栈

图1-7栈在顺序存储结构下的运算

（1）入栈运算

入栈运算是指在栈顶位置插入一个新元素。操作过程如下：

①首先判断栈顶指针是否已经指向存储空间的最后一个位置。如果是，则说明栈空间已满，不可能再进行入

栈操作（这种情况称为栈“上溢”错误），算法结束。

②然后将栈顶指针进一（即lop加1）。

③最后将新元素x插入栈顶指针指向的位置。

（2）退栈运算

退校运算是指取出栈顶元素并赋给一个指定的变量。操作过程如下：

①首先判断栈顶指针是否为0。如果是，则说明栈空，不可能进行退栈操作（这种情况称为栈“下溢”错误），

算法结束。

②然后将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量。

③最后将栈顶指针退一（即lop减1）。

（3）读栈顶元素

读栈顶元素是指将栈顶元素赋绐一个指定的变量。操作过程如下：

①首先判断栈顶指针是否为0。如果是，则说明枝空，读不到栈顶元素，算法结束。

②然后将栈顶元素赋给指定的变量y»

【注意】这个运算不删除栈顶元素，只是将它的值赋给一个变量，因此，在这个运算中栈顶指针不会改变。

【考题】下列关于栈的叙述中正确的是（）。

A.在栈中只能插入数据

B.在栈中只能删除数据

C.栈是先进先出的线性表

D.枝是先进后出的线性表

E.栈是一种非线性结构

【答案】D

【解析】在栈中，只允许在栈顶一端进行插入和删除，所以A、B错误；队列是“先进先出”的线性表，栈

是“先进后出”的线性表，所以C、E错误，D正确。

二、队列及其基本运算

1.什么是队列

加入的元素总是插入到线性表的末尾，并且乂总是从线性表的头部取出（删除）元素。这种线性表称为队列。

【说明】

①允许插入的一端称为队尾（rear）,允许删除的一端称为队头（from）。

②在队列中按照“先进先出”的原则进行操作。

退队-ABCDEF一入队

tT

frontrear

图1-8具有6个元素的队列示意图

front—*

Afront—►front-►

在

Ccc

rear—>rear—>5D

rear—>E

(a)一个队列(b)删除一个元素后的队列©插入元素E后的队列

图1-9队列运算示意图

【考题】下列关于队列的叙述中正确的是()。

A.在队列中只能插入数据

B.在队列中只能删除数据

C.队列是先进先出的线性表

D.队列是先进后出的线性表

【答案】C

【解析】在队列中，只允许在一端进行插入，在另一端进行删除，所以A、B错误；队列是“先进先出”的

线性表，枝是“先进后出”的线性表，所以D错误，选择C。

2.循环队列及其运算

【定义】循环队列是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环

使用。

rear—►

front—>

图1-10循环队列存储空间示意图

月队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。

在实际使用循环队列时，为了能区分队列满还是队列空，通常还需增加一个标志s,s值的定义如下:

J0表示队列空

11表示队列非空

由此可以得出队列空与队列满的条件如下:

队列空的条件为s=0；

队列满的条件为s=I且front=rearn

Q（l：8）Q（l：8）Q（l：8）

88X8X

rear—*7F7F7F

6E6E6E

5D5D51）

4C4C4C

3B3B3B

2A2Afront—*2

front—>1front—►1Yrear—>IY

rear—►

（a）具有6个元素的循环队列（b）加入X、Y后的循环队列（c）退出一个元素后的循环队列

图1-11循环队列运算示意图

（I）入队运算

入队运算是指在循环队列的队尾加入一个新元素。操作过程如下：

①首先判断循环队列是否满。当循环队列非空（S=l）且队尾指针等于排头指针时，说明循环队列已满，不

能进行入队运算。这种情况称为“上溢”。此时算法结束。

②然后将队尾指针进•（即rear=rear+1）,并当rear=m+1时置rear=1»

③最后将新元素x插入队尾指钎指向的位置，并且置循环队列非空标志。

（2）退队运算

退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。操作过程如下：

①首先判断循环队列是否为空。当循环队列为空（s=0）时，不能进行退队运算。这种情况称为“下溢”。

此时算法结束。

②然后将排头指针进一（即front=fronl+1）,并当front=m4-1时置front=1。

③再将排头指针指向的元素赋给指定的变量。

④最后判断退队后循环队列是否为空。当fronl=rear时置循环队列空标志（即s=0）。

【考题】设循环队列为Q（I：m）,其初始状态为front=rear=m。经过一系列入队与退队运算后，front=

30,rear=IOo现要在该循环队列中作顺序查找，最坏情况下需要比较的次数为（）。

A.19

B.20

C.m—19

D.m—20

【答案】D

【解析】在该循环队列中作顺序查找，最坏情况下需要比较的次数，实际上就是求循环队列中元素的个数。

元素的个数=（rear-front+m）modm=（10—30+m）modm=m—20,选项D正确。

1.5线性链表

一、线性链表的基本概念

【定义】线性表的链式存储结构称为线性链表。线性链表的数据结构包括两部分，一是数据元素的值，二是

数据元素之间的前后件关系。

存储序号数据域指针域

V(i)NEXT(i)

图1-12线性链表的一个存储结点

为什么用线性链表？

（I）线性表顺序存储结构存在的缺点：

①插入或删除过程中需要移动大量的数据元素。

②出现线性表的存储空间已满，但还需要插入新的元素时，就会发生“上溢”错误。

③线性表的顺序存储结构不便于存储空间的动态分配。

（2）线性表链式存储结构存在的优点：

在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关

系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。

【说明】

①在线性链表中，用一个专门的指针HEAD指向线性链表中第•个数据元素的结点（即存放线性表中第一

个数据元素的存储结点的序号）。线性表中最后一个元素没有后件，因此，线性链表中最后一个结点的指针域为

空（用NULL或0表示），表示链表终止。

HEAD->数据］数据2数据nNULL

图1-13线性链表的逻辑结构

②在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与

逻辑关系也不一致。

③当HEAD=NULL（或0）时称为空表。

V(i)NEXT(i)

9

a2

HEAD2

33%1

4

510

a4

6

7

8

95

100

a5

(a)线性域表的物理状态

(b)线性链表的逻辑状态

图1-14线性链表例

1.双向链表

对线性链表中的每个结点设置两个指针，一个称为左指针(Llink),用以指向其前件结点；另一个称为右指

针(Rlink),用以指向其后件结点。

图1-16带链的栈

在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。

(b)在从可利用栈取得一个结点p

图1-17可利用栈及其运算

3.带链的队列

队列也是线性表，也可以采用链式存储结构。

0

frontrear

(a)带链的队列

front

(b)在带链的队列中插入一个新结点

(C)在带链的队列中删除一个结点

图1-18带链的队列及其运算

二、线性链表的基本运算

线性链表的运算主要有以下几个：

①插入：在线性链表中包含指定元素的结点之前插入一个新元素。

②删除：在线性链表中删除包含指定元素的结点。

③合并：将两个线性链表按要求合并成一个线性链表。

④分解：将一个线性链表按要求进行分解。

⑤逆转

⑥复制

⑦排序

⑧查找

1.在线性链表中查找指定元素

从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为X为止。

因此，由这种方法找到的结点P有两种可能：

①当线性链表中存在包含元素X的结点时，则找到的p为第•次遇到的包含元素X的前•个结点序号;

②当线性链表中不存在包含元素X的结点时，则找到的P为线性链表中的最后一个结点号。

2.线性链表的插入

(c)p插入到q之后

图1-19线性链表的插入

3.线性链表的删除

TOP0

<O将被删除的结点p送回可利用栈后

图1-20线性链表的删除

二、循环链表

线性链表中，其插入与删除的运算虽然比较方便，但还存在•个问题，在运算过程中对于空表和对第一个结

点的处理必须单独考虑，使空表与非空表的运算不统一。

I.循环链表的特点

（1）增加了表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点。循

环链表的头指针指向表头结点。

（2）循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中，所有结点的指针构

成了一个环状链。

HEAD

表头结点

（a）非空循环涟表

HEAD-,

表头结点

（b）空循环捱表

图1-21循环链表的逻辑状态

2.循环链表与线性单链表相比主要有以下两个方面的优点：

（1）在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点。线

性单链表做不到这一点。

（2）由于在循环链表中设置了•个表头结点，因此，在任何情况下循环链表中至少有一个结点存在，从而

使空表与非空表的运算统一。

1.6树与二叉树

一、树的基本概念

【定义】树（Tree）是一种简单的非线性结构，树中所有数据元素之间的关系具有明显的层次特性。

图1-22学校行政层次结构树

【说明】

①在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树口勺根结点，简称

为树的根。

②在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。

③在树结构中，一个结点所拥有的后件个数称为该结点的度。

④在树中，所有结点中的最大的度称为树的度。

⑤树中的结点数=树中所有结点的度之和+1。

⑥根结点在第1层。同一层上所有结点的所有子结点都在下一层。树的最大层次称为树的深度。

树在计算机中的存储方式：

树在计算机中通常用多重链表表示。多重链表中的每个结点描述了树中对应结点的信息，而每个结点中的链

域（指针域）个数将随树中该结点的度而定。

・•

value(值)degree(®)link.link?♦linkn

图1-23树链表中的结点结构

二、二又树及其基本性质

1.什么是二叉树

二叉树具有以下两个特点：

①非空二叉树只有一个根结点；

②每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。

【注意】在二叉树中，每一个垢点的度最大为2。

回

（a）只有根结点的二叉树（b）深度为4的二叉树

图1-24二叉树例

2.二叉树的基本性质

【性质1］在二叉树的第k层上，最多有2广1（k21）个结点。

【性质2】深度为m的二叉树最多有方一1个结点,即21「+22「+…+2m「=2m-L

【性质3】在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。

【性质4】具有n个结点的二叉树，其深度至少为［log2n］+l,其中［logzn］表示取log2n的整数部分。

【考题1］在深度为5的满二叉树中，叶子结点的个数为（）。

A.32

B.31

C.16

D.15

【答案】C

【解析】叶子结点的个数=2<51）=16。

【考题2】设树T的度为4,其中度为1,2,3,4的结点个数分别为4,2,1,1。则树丁口的叶子结点数

为（）。

A.8

B.7

C.6

D.5

【答案】A

【解析】结点数为所有结点的度数之和加1，同时，注意到叶子结点的度数为0,则总结点数（设叶子结点

数为X）l*4+2*2+3*l+4*l+X*0+l=16,叶子结点数为X=16—4—2—1-1=8。

3.满二叉树与完全二叉树

（1）满二叉树

【定义】满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点。

【说明】在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k层上有2广1个结点，且深

度为m的满二叉树有2m-l个结点。