全国计算机等级考试考点解析、例题精解与应试模拟-三级数据库

全国计算机等级考试考点解析、例题精解与应试模拟一一三

级数据库

第2章数据结构与算法

※本章大纲要求：

(1)基本概念

(2)线性表

(3)多维数组、稀疏矩阵和广义表

(4)树形结构

(5)查找

(6)排序

※重要考点提示：

根据对历年真题的分析可知，本章考核内容约占15%,主要包括

以下几个方面：

(1)数据结构和算法的基本概念

(2)数据的逻辑结构、存储结构

(3)顺序表和一维数组

(4)链表、栈、队列、串的概念与操作

(5)稀疏矩阵的存储、广义表的定义与存储

(6)二叉树的定义、存储与表示、线索二叉树

(7)树与二叉树的转换、二叉树的周游算法

(8)霍夫曼算法及其应用

(9)静态表、动态表的查找

(10)各种排序算法，插入排序、选择排序、交换排序、归并排

序

2.1基本概念

考点1：数据结构的基本概念★

(1)数据

数据就是采用计算机能够识别、存储和处理的方式，对现实世界

的事物进行的描述，简而言之，数据就是计算机化的信息。

数据元素是数据的基本单位。一个数据元素可由一个或多个数据

项组成，数据项是有独立含义的数据最小单位。

(2)数据结构

数据结构一般包括3个方面的内容：数据之间的逻辑关系、数据

在计算机中的存储方式以及在这些数据上定义的运算的集合。

a.数据的逻辑结构是数据间关系的描述，它只抽象地反映数据

元素间的逻辑关系，而不管其在计算机中的存储方式。数据的逻辑结

构分为线性结构和非线性结构。

b.数据的存储结构是逻辑结构在计算机存储器里的实现。

c.数据的运算定义在数据的逻辑结构上，而实现是在存储结构

±0主要的运算包括插入、删

除、排序、查找等。

考点2：主要的数据存储方式★

实现数据的逻辑结构到计算机存储器的映像有多种不同的方式。

最主要的存储方式有顺序存储储结构和链式存储方式。

(1)顺序存储结构

顺序存储结构是将逻辑上相邻的数据元素存储在物理上相邻的

存储单元中，结点之间的关系由存储单元的邻接关系来体现，其主要

特点是：

a.结构中只有自身信息域，没有链接信息域，因此，存储密度

大，存储空间利用率高；

b.可以通过计算直接确定数据结构中第i个结构的存储地址；

c.插入、删除运算会引起大量结构的移动。

(2)链式存储结构

链式存储结构是在每个结点中至少包括一个指针域，用指针来体

现数据元素之间逻辑上的联系。其主要特点是：

a.存储密度小，存储空间利用率低；

b.逻辑上相邻的结点物理上不必邻接，可用于线性表、树、图

等多种逻辑结构的存储表示；c.插入、删除操作灵活方便，不必移

动结点。

考点3：算法的设计与分析

算法的设计采用由粗到细、由抽象到具体的逐步求精的方法。

算法分析主要是分析算法所要占用的计算机资源，即时间代价和

空间代价两个方面。

a.时间代价是当问题的规模以某种单位由1增至n时解决该问

题的算法运行时所耗费的时间，也以某种单位由f(l)增至f(n),则称

该算法的时间代价为f(n)

b.空间代价是当问题的规模由1增至n时-，解决该问题的算法

实现时所占用的空间也以某种单位由g(l)增至g(n),则称该算法的空

间代价为g(n)o

2.2线性表

考点4：顺序表和一维数组

线性表的逻辑结构是n个数据元素的有限序列(al,a2,…,an)。

按存储方式不同线性表可以分为：顺序存储的顺序表、链式存储的链

表、散列存储的散列。

顺序表是用一组地址连续的存储单元依次存储数据元素的线性

表，其逻辑相邻的数据元素具有相邻的物理(存储)位置。对数据元

素进行插入、删除操作时需要移动数据元素，存储空间被分配后难以

再被扩充。

各种高级语言中的一维数组就是用顺序方式存储的线性表，因此

也常用一维数组来称呼顺序表。

考点5：链表★

链表的特点是可以用一组任意的存储单元来存储线性表的各个

数据元素，不要求逻辑上相邻的元素物理上也相邻。链表的优点是插

入、删除等操作不需要移动元素，只需要修改指针，比较灵活，缺点

是不能随机存取。

链表可以分为线性链表和双向链表两种，前者也称为单链表，每

个结点中只有一个指向后一个结点的指针；后者每个结点有两个指针,

一个指向直接前驱结点，一个指向直接后继结点。・18・

考点6：栈与队列十

栈与队列都是对操作位置加以限制的线性表。可以使用顺序存储

也可以采用链式存储。

栈的插入和删除只能发生在线性表的一端，允许插入、删除的这

一端称为栈顶，另一个固定端称为栈底。当表中没有元素时称为空栈。

栈是按“后进先出”的规则进行操作的。栈的常用运算主要包括入栈

（push）、出栈（pop）和取栈顶元素（top）。

栈是使用最为广泛的数据结构之一，表达式求值、递归过程实现

都是栈应用的典型例子。队列的插入只能在线性表的一端进行，而

删除在线性表的另一端进行，允许插入的一端叫队尾（rear）,允许删

除的一端叫队头（）队列是按“先进先出”的规则进行操作的。

front0

队列常用的运算有入队（）、出队（）和取队首元素（）

enqdeqfront0

队列在计算机中应用也十分广泛，硬件设备中的各种排队器、缓

冲区的循环使用技术、操作系统中的作业队列等都是队列应用的例子。

考点7：串

串（或字符串）是由零个或多个字符组成的有限序列，零个字符

的串是空串。串的存储方式有：顺序存储和链式存储。顺序存储时可

以采用非紧缩方式，也可以采用紧缩方式。

串的基本运算有连接、赋值、求长度、全等比较、求子串、求子

串位置以及替换等。其中找子串位置（也称模式匹配）是非常重要的

一种运算。

2.3多维数组、稀疏矩阵和广义表

考点8：多维数组的线性存储★

多维数组是一维数组的推广，其特点是结构中的元素本身可以是

具有某种结构的数据，但属于同一数据类型。多维数组中最常用的是

二维数组。

多维数组的存储方式一般是多维数组中的元素放在一个线性序

列中，排列方式可以是行优先顺序或列优先顺序。二维数组第i行、

第j列元素aij存储地址的计算公式为：

行优先顺序:LOC(aij)=LOC(all)+((i?l)*n+(j?D)*?

列优先顺序:LOC(aij)=LOC(all)+((j?l)*m+(i?l))*?

式中m和n分别为数组中每列和每行的元素个数，？为每个数组

元素占用的存储单元个数。考点9：稀疏矩阵的存储

具有大量0元素的矩阵称为稀疏矩阵。对稀疏矩阵进行压缩存储,

即只存储非0元素。

对非0元素的分布有规律的矩阵，如下三角矩阵，按行优先顺序

存储，非零元素的存储地址用下式计算：

LOC(aij)=LOC(all)+(i*(i?l)/2+(j?l))*?

对一般的稀疏矩阵，可以采用三元组方法或十字链表方法存储。

前者是按行优先顺序存储非零元素所在的行、列以及它的值构成的三

元组，后者则采用十字链表。

考点10：广义表的定义和存储

广义表是线性表的推广，也称为列表，是由零个或多个单元素或

子表所组成的有限序列。广义表与线性表的区别在于：线性表的成分

都是结构上不可分的单元素，而广义表的成分既可以是单元素，又可

以是有结构的表。

广义表的特征：

广义表的元素可以是子表，而子表的元素还可以是子表。

-19-

广义表可被其他广义表所共享。

广义表可以是递归的表，即广义表也可以是本身的一个子表。

2.4树形结构

考点11:树及二叉树的定义及表示★

树是一个或多个结点组成的有限集合T,有一个特定的结点称为

根，其余结点分为m(m2。)个不相交的集合Tl,T2,?,Tm。每

个集合又是一棵树，被称为这个根的子树。这是树的递归定义。

树的性质有以下4条：

(1)树中的结点数等于所有结点的度数加1。

(2)度为k的树中第i层上至多有ki?l个结点021)。

(3)深度为h的k叉树至多有(kh?l)/(k?l)个结点。

(4)具有n个结点的k叉树的最小深度为?logk(n(k?l)+l)?

二叉树是树形结构的一个重要类型。二叉树是结点的有限集合,

这个有限集合或者为空集，或者由一个根结点及两棵不相交的分别称

做这个根的左子树和右子树的二叉树组成。

二叉树不是树的特殊情况，树与二叉树之间最主要的区别是：二

叉树的子树有左右之分，其次序不能颠倒，即使是在只有一棵子树的

情况下也要明确指出该子树是左子树还是右子树。

在一棵二叉树中，如果最多只有最下面两层结点度数可以小于2,

并且最下面一层结点都集中在最左边的位置上，这样的一棵二叉树称

为完全二叉树。

树与二叉树可以互相转化，树（树林）转换为二叉树的算法：在

一棵树中，凡是兄弟结点就用线连起来，然后去掉父结点到子结点的

连线，只保留父结点到第一个子结点的连线。如果把森林中第二棵树

的根结点看成是第一棵树的根结点的兄弟结点，则同样可以导出森林

与二叉树的对应关系。

把二叉树转换为树的算法：若某结点是其双亲的左孩子，则把该

结点的右孩子，右孩子的右孩子??，都与该结点双亲用线连起来，最

后去掉所有的双亲到右孩子的连线。

考点12：二叉树与树的周游★

遍历一个树形结构就是按一定的次序系统地访问树上的所有结

点，使每个结点恰好被访问一次。

由二叉树的定义可知，一棵二叉树由3部分组成：根、左子树和

右子树。因此对二叉树的遍历也可相应地分为3类先序（根）遍历、

中序（对称序）遍历、后序（根）遍历。

先序遍历：访问根结点；先序遍历左子树；先序遍历右子树。

中序（对称序）遍历：中序遍历左子树；访问根结点；中序遍历

右子树。

后序遍历：后序遍历左子树；后序遍历右子树；访问根结点。

由于树也是一种层次结构，所以对树有时也进行按层遍历，所谓

按层遍历，就是从树根结点开始，依次访问每一层，对同一层结点,

由左至右进行访问。

树和森林的遍历也主要有三种：先根次序、后根次序和层次次序。

其中，前两种是按深度优先方式进行的，后一种是按广度优先方式进

行的。

根据树和二叉树的对应关系，可以看出，按先序遍历树正好等同

于按先序遍历对应的二叉树；按后序遍历树正好等同于按对称序法遍

历对应的二叉树。

-20-

考点13：二叉树的存储与线索二叉树

(1)二叉树的Llink?Hink法存储

二叉树通常的存储方式是链式存储，每个链结点除了数据域外,

还可以增加两个指针域llink和rlink,分别指向左右两个子结点。当

某个结点的子结点不存在时，相应的指针值为空(nil)。

(2)线索二叉树

一个具有n个结点的二叉树若采用二叉链表存储结构，在2n个

指针域中只有n?l个指针域是用来存储结点孩子的地址的，而另外

n+1个指针域存放的都是niL为了保留结点在某种遍历序列中直接前

驱和直接后继的位置信息、，可以利用二叉树的二叉链表存储结构中的

这n+1个空指针域来记录这些信息。这些指向直接前驱结点和指向直

接后继结点的指针被称为线索（thread）,加了线索的二叉树称为线

索二叉树。

（3）完全二叉树的顺序存储

二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的

结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。完全

二叉树或者满二叉树比较适合于顺序存储。

考点14：霍夫曼算法及其应用★

霍夫曼（Huffman）树，也称为最优二叉树，是指对于一组带有

确定权值的叶结点，构造的具有最小带权路径长度的二叉树。

设二叉树具有n个带权值的叶结点，那么从根结点到各个叶结点

的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度,

记为：

WPL??Wk?Lk

k?ln

其中Wk为第k个叶结点的权值,Lk为第k个叶结点的路径长度。

最优二叉树算法为：对于n个权为wl,w2,w3,…,wn的结点，

首选找出两个最小的wi值，不妨设为wl和w2,然后对m?l个权

wl+w2,w3,…,,wn来解这个问题，并且将解中的代替，如此进行

下去，直到所有的w构成一棵二叉树。

给定一组权值，构造出来的霍夫曼树不是唯一的。在霍夫曼树中，

权值大的结点离根最近。另外，在霍夫曼树中，没有度为1的结点。

2.5查找

考点15：线性表的查找

查找是确定一个元素在表或树中的位置，衡量一个查找算法的标

准是对关键码平均比较的次数，或称为平均检索长度ASL。对于线性

表的查找主要分下面几种：

(1)顺序查找

顺序查找是线性表的最简单的查找方法，其具体步骤是：用待查

关键码从头开始逐个与表中元素比较，直到找出相等的元素，则查找

成功；或者找遍所有元素，则查找失败。

顺序查找的优点：对线性表的结点的逻辑次序无要求，对线性表

的存储结构无要求。

顺序查找的缺点：平均检索长度长，与表中结点个数n成正比,

若检索关键码的概率相等，则

-21-

查找成功时平均比较次数为(n+l)/2。查找不成功时；关键码的比

较次数总是n+1次。

(2)二分查找

二分查找法是一种效率较高的线性表查找方法，要求线性表结点

必须是按关键码值排好序的，且线性表以顺序方式存储。其具体步骤

是：首选用要查找的关键码值与线性表中间位置结点的关键码值相比

较，这个中间结点把线性表分成两个子表，比较相等则查找完成，不

等则根据比较结果确定下一步的查找应该在哪一个子表中进行，如此

进行下去，直到找到满足要求的点。

二分查找的优点：平均查找长度小，为??Iog2n??

二分查找的缺点：线性表排序需要花费时间，顺序方式存储的插

入、删除不便。

（3）分块查找

分块查找要求把线性表分成若干块，每一块中的结点不必有序,

但块与块之间必须有序，还要求将各块中的最大关键码值组成一个有

序的索引表。其具体步骤是：首选在索引表中用顺序查找或二分查找

法确定所求记录所在的块，然后再从该块中用顺序查找方法找出所求

的记录。

（4）散列表查找

散列法的基本思想是：由结点的关键码决定结点的存储地址，即

以关键码k为自变量，通过散列函数计算出对应的函数值h（k）,将这

个值解释为结点的存储地址。检索时再根据要检索的关键码值用同样

的方法计算出结点位置。

散列法需要解决以下两个问题：

a.构造好的散列函数，能够将一组关键码值尽可能均匀地安排

在事先确定的范围里，并且使得发生碰撞的可能性最小。常见的散列

函数有直接定址法除余法、数字分析法、折叠法、平方取中法等。

b.制定解决碰撞的方案。处理碰撞的方法主要有拉链法和开放

定址法。

影响产生冲突多少有以下三个因素：哈希函数是否均匀；处理冲

突的方法；哈希表的负载因子。散列表的负载因子公式:

??散列表中结点的数目基本区域能容纳的结点数

负载因子的大小体现散列表的装满程度，？越大，则散列表装得

越满，发生碰撞的机会越大，一般取??1。

考点16：树形结构与查找山

（1）二叉排序树

二叉排序树是一类特殊的二叉树，其特点是：若左子树不空，则

左子树上所有结点的值均小于根结点的值；若右子树不空，则右子树

上所有结点的值均大于根结点的值；所有的子树也遵守相同的规则。

对二叉排序树中序遍历（周游）可以得到关键字从小到大的有序

序列。对无序序列可以通过构造一棵二叉排序树而变成一个有序序列,

构造二叉排序树的过程就是对无序序列进行排序的过程。

对二叉排序树的操作主要的插入和删除操作。

平衡二叉树是对二叉排序树的一种“平衡化”处理。结点的平衡

因子定义为其右子树高度减去左子树高度。若任一结点的平衡因子均

取一1,0或+1,则此二叉排序树为平衡的二叉排序树（AVL树）。平

衡二叉排序树的查找方法与一般的二叉排序树完全一样，优点是总能

保持检索长度为O（log2n）量级。

往平衡二叉树插入新结点时，需要对树的结构进行必要调整，以

动态地保持平衡二叉树的特点。・22・

（2）B树和B+树

B树和B+树是一种平衡的多路查找树形结构，用于组织外存储器

中文件的动态索引结构。这样可以使得每个结点包含多个关键码值，

有多个孩子，使得树的层次降低，查找时访问外存的次数减少。

由B树定义可以知：

a.m阶B树每一个结点最多有m个子树。

b.m阶B树根结点或为叶结点，或至少有两棵子树；中间结点

至少有?m/2?棵子树。

c.m阶B树任一结点的左右子树的高度都相等。

B树的主要操作是：查找、插入、删除。

在m阶B树上插入关健码的过程为：

a.B树是从空树开始，逐个插入关键码而生成的。

b.在B树中，每个非叶结点的关键码个数都在[?m/2??l,m?l]

之间。

c.B树中关键码的插入不是在叶结点上进行的，而是在最底层

的某个非终端结点中添加一个关键码。若插入结点上关键码个数不超

过m?l个，则可直接插入到该结点上；否则，要进行调整，即结点

的“分裂”。

根据B+树的定义可知：

a.有n棵子树的结点中含有n个关键码。

b.所有关键码均出现在叶结点中，上层关键码均是下层相应结

点中最大关键码的重复，且叶子结点所有关键码是有序的。

c.对B+树进行两种查找运算:一种是从最小关键码起顺序查找，

另一种是从根结点开始，进行随机查找。

2.6排序

考点17：插入排序

插入排序的基本思想是每次将一个待排序记录按其关键码值大

小插入到前面已排序的文件中的合适位置上，直到记录插入完为止。

a.直接插入排序：在已排好序的序列中查找插入位置时用顺序

法查找，找到插入位置后将该位置原来的记录及其后面所有的记录顺

序后移一个位置，空出该位置来插入记录。

b.二分法插入排序：在已排好的序列中找插入的位置时，用二

分法查找，找到插入位置后和直接插入排序法同样处理。

c.shell排序：又称缩小增量法，是按增量将文件分组。首先取

增量dl<n,把全部记录分成dl个组，所有距离为dl倍数的记录

放在一组中，各组内用插入法排序，然后取d2<dl,重复上述分组

和排序工作，直至取d=l,即所有记录放在一个组中为止。

考点18：选择排序支

选择排序的基本思想是每次从待排序的记录中选出关键码值最

小（或最大）的记录，顺序放在已排记录序列的最后，直到全部排完，

这里主要讲堆排序

堆排序是对一组待排序的关键码，首先把它们按堆的定义排成一

个序列（称为建堆），这就找到了最小的关键码，然后将最小的关键

码取出，用剩下的关键码再建堆，便得到次最小的关键码，如此反复

进行，直至将全部关键码排好序为止。

堆排序的两个主要问题：

-23-

（1）如何将n个元素的序列按关键码建成堆。

（2）输出堆顶元素后，如何调整剩余元素使之成为一个新堆。

考点19：交换排序十

交换排序主要是起泡排序和快速排序。

a.起泡排序是将排序的记录顺次两两比较，若为逆序则进行交

换，将序列照此方法从头到尾处理一遍称做一趟起泡。第二趟起泡再

将次最大关键码交换到倒数第二个位置，即它的最终位置，如此进行

下去，若某一趟起泡过程中没有发生任何交换，或排序已经进行了

n?l趟，则排序过程结束。

b.快速排序是在待排序序列中任取一个记录，以它为基准用交

换的方法将所有的记录分成两部分，关键码值比它小的一个部分，关

键码值比它大的在另一部分，再分别对两个部分实施上述过程，一直

重复到排序完成。

考点20：归并排序归并排序的基本思想是对两个或两个以上的

表组合成一个新的有序表。排序方法为先将原始序列中的每个关键字

都看作一个序列，两两有序归并，逐步扩大于序列尺寸，直到全部排

序完成。

2.7经典题解

一、选择题

1.下列哪一个术语与数据的存储结构有关。（2007.09）

A）栈

C）链表B）队列D）线性表

解析：数据的存储结构是逻辑结构在计算机存储器里的实现，如

链表。数据的逻辑结构是数据间关系的描述，它只抽象地反映数据元

素间的逻辑关系，而不管其在计算机中的存储方式。逻辑结构分为线

性结构（如线性表、栈、队列）和非线性结构（如树）。

答案：c

2.下列关于数据的逻辑结构的叙述中，哪一条是不正确的。

（2007.09）

A）数据的逻辑结构是数据间关系的描述

B）数据的逻辑结构不仅反映数据间的逻辑关系，而且包括其在

计算机中的存储方式

C）数据的逻辑结构分为线性结构和非线性结构

D）线性表是典型的线性结构

解析：数据的逻辑结构是数据间关系的描述，它只抽象地反映数

据元素间的逻辑关系，而不管其在计算机中的存储方式，在计算机中

的存储是由存储结构决定的。逻辑结构分为线性结构（如线性表、栈、

队列）和非线性结构（如树）。

答案：B

3.下列关于数据运算的叙述中，哪一条是不正确的o（2007.09）

A）数据运算是数据结构的一个重要方面

B）数据运算的具体实现在数据的逻辑结构上进行

C）检索是一种常用的运算

D）插入是一种常用的运算

解析：数据的运算定义在数据的逻辑结构上，而实现是在存储结

构上。主要的运算包括插入、删除、排序、查・24・

找等。

答案：B

4.栈结构不适用于下列哪一种运用。（2007.09）

A）表达式求值

B）快速排序算法的实现

C）树的层次次序周游算法的实现

D）二叉树对称序周游算法的实现

解析：树的层次次序周游算法需要先存储每一层的结点，然后按

照先进后出的顺序依次访问结点信息、，需要用先进先出的队列来实现,

而不是用先进后出的栈来实现；表达式求值，需要设置操作数和操作

符两个栈；快速排序需要用栈实现递归；二叉树对称序周游算法即中

序周游算法，也需要用栈结构实现。

答案：C

5.双链表的每个结点包括两个指针域。其中Hink指向结点的后

继，llink指向结点的前驱。如果要在p所指结点后插入q所指的新结

点，下列哪一个操作序列是正确的。（2007.09）

A）pf.rlinkf.llink:=q;pt.rlink:=q;qt.llink:=p;qf.rlink:=p

t.rlink;

B）pt.llinkf.rlink:=q;pt.llink:=q;qt.rlink:=p;qt.llink:=p

t.llink;

C)qf.llink:=p;qt.rlink:=pt.rlink;pt.rlinkt.llink:=q;p

t.rlink:=q;

D)qf.rlinkf:=p;qt.llink:=pf.llink;pf.llinkf.rlink:=q;p

f.llink:=q;

解析：需要先将待插入结点q的左指针更新为p，然后将q右指

针的信息更新为p的右指针所指向结点，再将p的右指针所指结点的

左指针信息更新为q，最后将p的右指针信息更新为q。

答案：C

6.在包含1000个元素的线性表中实现如下运算，哪一个所需执

行时间最长。(2007.09)

A)线性表按顺序方式存储，在线性表的第100个结点后面插入

一个新结点

B)线性表按链接方式存储，在线性表的第100个结点后面插入

一个新结点

C)线性表按顺序方式存储，删除线性表的第900个结点

D)线性表按链接方式存储，删除指针P所指向的结点

解析：线性表按顺序方式存储，执行插入操作时要将插入点后的

所有元素平移一个单位，在1000个元素的线性表的第100个结点后

插入新结点需要移动900个元素。链接方式存储插入新结点需要查找

100次找到结点再插入。线性表按顺序方式存储，删除第900个元素

要将第900?1000个元素向前移动一个单位。按链接方式存储，删除

指针P指向结点，其平均查找长度为500.5。查找开销比移动开销要

答案：B

7.设某散列表的当前状态如下：

该散列表的负载因子约为。(2007.09)

A)0.37B)0.42C)0.58D)0.73

解析：散列表的负载因子公式：

pqnewnode-25-

??散列表中结点的数目

基本区域能容纳的结点数

由题可知负载因子为7/19=0.37

答案：A

8.设有关键码序列(Q、G、M、Z、A、N、B、P、X、H、Y、S、

T、L、K、E),采用堆排序法进行排序，经过初始建堆后关键码值A

在序列中的序号是。(2007.09)

A)1

C)8B)4D)12

解析：堆排序是将待排序的关键码先按堆的定义排成一个序列

(称为建堆)，找到最小的关键码，然后将最小的关键码取出，用剩

下的关键码再建堆，便得到次最小的关键码，如此反复进行，直至将

全部关键码排好序为止。所以初始建堆关键码A即为堆顶,序号为lo

答案：A

9.对n个记录的文件进行起泡排序，所需要的辅助存储空间

为。(2007.09)

A)0(1)

C)O(n).B)O(log2n)D)O(n)2

解析：起泡排序仅需一个辅助存储空间作为记录在交换位置时的

缓存空间。

答案：A

10.下列关于数据结构基本概念的叙述中，哪一条是不正确的。

(2007.04)

A)数据是采用计算机能够识别、存储和处理的方式，对现实世

界的事物进行的描述

B)数据元素(或称结点、记录等)是数据的基本单位

C)一个数据元素至少由两个数据项组成

D)数据项是有独立含义的数据最小单位

解析：一个数据元素可由一个或若干个数据项组成。数据项是有

独立含义的不可分割的数据的最小单位。数据是所有能输入到计算机

中并被计算机程序识别、存储和处理的符号的总称。

答案：C

11.下列关于链式存储结构的叙述中，哪些是正确的。

(2007.04)

I.逻辑上相邻的结点物理上不必邻接

II.每个结点都包含恰好一个指针域

III.用指针来体现数据元素之间逻辑上的联系

IV.可以通过计算机直接确定第i个结点的存储地址

V.存储密度小于顺序存储结构

A)I、II和II

B)I、II、III和IVD)I、山和VC)II、IV和V

解析：链式存储结构中除了包含保存数据元素自身信息的信息域

外，还有表示数据元素之间的链接信息的指针域，因此比顺序存储结

构的存储密度低；链式存储结构中逻辑上相邻的数据元素在物理上不

一定相邻；不是所有节点都包含指针域，如单向链表中最后一个节点

的指针为空。

答案：D

12和13基于以下描述：有一个初始为空的栈和输入序列A、B、

C、E、F、G：现发过如下操作：

push,push,top,pop,push,push,top,push,pop,pop,pop.

12.下列哪一个是正确的从栈中删除元素的序列。(2007.04)

A)BEB)BD

-26-

C)BEDCD)BDEC

解析：栈的操作遵循后进先出的原则。题中的操作依次为：A进

栈、B进栈、B读取、B删除、C进栈、D进栈、E进栈、E删除、D

删除、C删除。由此可见删除的序列为BEDC。

答案：C

13.下列哪一个是上述操作序列完成后栈中的元素列表(从底到

顶)。(2007.04)

A)A

B)BDC)ABCE

答案：A

14—15基于如下所示的二叉树。

D)ABCDE解析：通过上题的分析可知，在操作过程中进栈的有

ABCDE,删除的有BEDC,因此最后栈中的元素只有A。14.该二叉

树对应的树林包括几棵树。(2007.04)

A)1B)2C)3D)4

解析：二叉树转换为树林时，二叉树的根就是树林第一棵树的根；

二叉树的左子树转换为树林的第一棵树，二叉树的右子树对应于树林

中其余的树；二叉树右子树的根节点作为余下树中第一棵树的根节点,

其余以此类推。本题中的二叉树应该包含2棵树。

答案：B

15.按后根次序周游该二叉树对应的树林，所得到的结点序列为

(2007.04)

A)DBAFEGC

C)DBFGECAB)ABCDEFGD)ACBEGDF

解析：后序遍历二叉树的次序是：后序遍历左子树，后序遍历右

子树，访问根节点。因此后序遍历此二叉树对应的树林所得的节点序

列为选项Co

答案：C

16.按层次次序周游该二叉对应的树林，所得到的结点序列为。

(2007.04)

A)DBAFEGC

C)DBFGECAB)ABCDEFGD)ACBEGDF

解析：按层次次序遍历二叉树的次序是：从树的根节点开始，依

次访问每一层，对同一层节点，由左到右进行访问。因此按层次次序

遍历此二叉树对应的树林所得的节点序列为选项B。

答案：B

17.设待排序关键码序列为(25,18,9,33,67,82,53,95,

12,70),要按关键码值递增的顺序进行排序，采取以第一个关键码

为分界元素的快速排序法，第一趟排序完成后关键码95被放到第几

个位置。(2007.04)

A)7

C)9

处在第8个位置。B)8D)10解析：快速排序法

第一趟排序后,关键码序列为(12,18,9,25,67,82,53,95,33,

70),因此关键码95

-27-

答案：B

18.设散列表的地址空间为0到：16,散列函数为h(k)=kmodl7,

用线性探查法解决碰撞。现从空的散列表开始，依次插入关键码值

190,89,217,208,75,177,则最后一个关键码177的地址为。

(2007.04)

A)6

C)8B)7D)9

解析：本题采用除留余数法构造散列函数，将关键码值190,89,

217,208,75,177分别带入h(k)=kmodl7,得到散列地址分别为3,

4,13,4,7,7,在存储关键码208时，由于其散列地址4与前面的

一个关键码发生冲突，因此其存储地址向后移1位到5。而存储关键

码177时，由于其散列地址7与前面的一个关键码发生冲突，因此其

存储地址再向后移1位到8o

答案：C

19.下列哪些是数据结构研究的内容。(2006.09)

I.数据的采集

V.数据的检索

A)II和IV

B)I、II和IIID)I、III和VC)IK川和VII.数据的逻

辑组织IV.数据的传输III.数据的存储实现

解析：数据的采集和数据的检索不属于数据结构研究的内容。数

据结构一般包括三方面内容：数据的逻辑结构，它是从逻辑关系上描

述数据，与数据的存储无关。数据的存储器内表示，它是指用计算机

语言实现的逻辑结构，它依赖于计算机语言。数据的运算，即对数据

施加的操作。

答案：C

20.下列关于数据元素的叙述中，哪一项是不正确的。

（2006.09）

A）数据元素是数据的基本单位，即数据集合中的个体

B）数据元素是有独立含义的数据最小单位

C）数据元素又称作结点

D）数据元素又称作记录

解析：数据项是具有独立含义的最小标识单位，而非数据元素。

数据元素是数据的基本单位，一个数据元素可以由若干个数据项组成,

有时也称作结点、记录、表目等。

答案：B

21.下列关于数据的存储结构的叙述中，哪一项是正确的。

（2006.09）

A）数据的存储结构是数据间关系的抽象描述

B）数据的存储结构是逻辑结构在计算机存储器中的实现

C）数据的存储结构分为线性结构和非线性结构

D）数据的存储结构对数据运算的具体实现没有影响

解析：数据的存储结构是指数据的逻辑结构在计算机存储器中的

表示，又称数据的物理结构。分为顺序存储结构和链式存储结构。数

据采用不同的存储结构，将对数据运算的具体实现有着巨大的影响。

答案：B

22.栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、

F的顺序进栈，下列哪一个序列是可能的出栈序列。（2006.09）

A)E、D、C、B、A、F

C)C、B、E、D、A、FB)B、C、E、F、A、DD)A、D、

F、E、B、C

解析：对于选项A,因为该栈最多只能容纳4个元素，而E是第

五个元素，在前4个元素还没出栈的情况下是不可能进栈再出栈的。

对于选项B,A元素不可能在D元素还没出栈的情况下先出栈；对于

选项C,其出栈序列为：・28・

C、B、E、D、A、F；对于选项D,B元素不可能在C元素还没出

栈情况下出栈，出栈序列为选项C。

答案：C

23.从单链表中删除指针s所指结点的下一个结点3其关键运

算步骤为。(2006.09)

A)st.link:=t

B)tf.link:=sD)st.link:=tf.linkC)tt.link:=st.link

解析：要从单链表中删除指针-s所指节点的下一个节点t,则原

节点t指的后继节点成为s所指的后继节点，因此关键运算步骤为:

stJink:=tt.linko

答案：D

24.按行优先顺序存储下三角矩阵

?allO?aa22Ann??21

?????anlan20??0???????ann??

的非零元素，则计算非零元素aij(lWiWjWn)的地址公式为

(2006.09)

A)LOC(aij)?LOC(all)?i?(i?l)/2?j

B)LOC(aij)?LOC(all)?i?(i?l)/2?(j?l)

C)LOC(aij)?LOC(all)?i?(i?l)/2?j

D)LOC(aij)?LOC(all)?i?(i?l)/2?(j?l)

解析：非零元素aij在矩阵中处在第i行第j歹U,在按行优先顺序

存储时，应先存储前i?l行的非零元素和同一行的前j?l个元素。如

果all的存储地址为LOC(all),则aij的存储地址为D。

答案：D

25.下列关于二叉树周游的叙述中，哪一项是正确的。

(2006.09)

A)若一个结点是某二叉树对称序的最后一个结点，则它必是该

二叉树前序的最后一个结点

B)若一个结点是某二叉树前序的最后一个结点，则它必是该二

叉树对称序的最后一个结点

C)若一个树叶是某二叉树对称序的最后一个结点，则它必是该

二叉树前序的最后一个结点

D)若一个树叶是某二叉树前序的最后一个结点，则它必是该二

叉树对称序的最后一个结点

解析：若一个树叶是某二叉树对称序的最后一个节点，则它必是

该二叉树最右边的树叶，即前序的最后一个节点。而若将“树叶”改

为“结点”则不正确，因为有可能出现二叉树最右结点无右孩子的情

况。

答案：c

26.如下所示是一棵5阶B树，该B树现在的层数为2。从该B

树中删除关键码38后，该B树的第2层的结点数为。(2006.09)

A)6B)7

-29-

C)8D)9

解析：删除38后该节点剩下的关键码的个数为1,小于「5/2

-I?1=2,所以删除后要将该结点剩余的41与双亲结点中的45一起移

至原结点的右兄弟节点，故结点数减1,变为6个。

答案：A

27.在待排序文件已基本有序的前提下，下列排序方法中效率最

高的是。(2006.09)

A)直接插入排序

C)快速排序B)直接选择排序D)归并排序

解析：直接插入排序，若文件基本有序，则比较次数最小为n?l

次，移动次数为0;直接选择排序，无论待排序文件是否基本有序,

其比较次数均为n(n?l)/2,若文件基本有序，则移动次数减少，最小

为0;快速排序在文件基本有序时蜕化为起泡排序，时间复杂度为

n(n?l)/2；对于归并排序，无论待排序文件是否基本有序，其比较次

数均为nlog2n,若文件基本有序，则移动次数减少，最小为0,可见

直接插入排序效率最高。2

答案：A

28.下列关于数据结构基本概念的叙述中，哪一条是正确的

（2006.04）

A）数据的逻辑结构分为表结构和树结构

B）数据的存储结构分为线性结构和非线性结构

C）数据元素是数据的基本单位

D）节点是有独立含义的数据最小单位

解析：数据的基本单位是数据元素，故C正确。数据的逻辑结构

可以划分为集合、线性结构、树型结构和图状结构（网状结构）。数

据的存储结构指的是数据结构在计算机中的表示（映像），它包括顺

序存储和链式存储两种结构。节点是由若干位组合起来形成的位串，

数据的最小单位是节点中的一个二进制数位（bit）。

答案：C

29.下列关于串的叙述中，哪一条是正确的。（2006.04）

A）串是由零个或多个字符组成的有限序列

B）空串是由空格构成的串

C）串只能顺序存储

D）“推入”是串的基本运算之一

解析：串是由零个或多个字符组成的有限序列；如果串中没有任

何字符，则称为空串。由一个或多个空格组成的串称为空格串，空格

串不是空串，因为空格串中有字符；串既可以顺序存储也可以链表存

储；串的基本操作一般是以“串的整体”作为操作对象，“推入”不

是串的基本运算。

答案：A30.双链表的每个结点包括两个指针域。其中rlink指向

结点的后继，llink指向结点的前驱。如果要在p所指结点前面插入q

所指的新结点，下列哪一个操作序列是正确的。(2006.04)

A)pf.rlinkf.llink:=q；pf.rlink:=q；qf.llink:=p；qt.rlink:=p

t.rlink；

B)p\.llinkt.rlink:=q；pt.llink:=q；qt.rlink:=p；qt.llink:=p\.llink；

C)qt.llink:=p；qt.rlink:=pt.rlink；pt.rlinkf.llink:=q；p

t.rlink:=q；

D)qt.rlink:=p；q\.llink:=pf.llink；pt.llinkt.rlink:=q；p\.llink:=q；

解析：首先要修改p所指节点的llink字段和原前驱节点的rlink

字段，然后置q所指节点的rlink和llink值，即qt.Hink:=p；qt.llink:=p

；；

t.llinkpt.llinkf.rlink:=qpt.llink:=q0

答案：D

31.下列哪一个不是队列的基本运算。(2006.04)

-30-

A)从队尾插入一个新元素

B)从队列中删除第i个元素

C)判断一个队列是否为空

D)读取队头元素的值

解析：队列的基本操作有：构造一个空队列；将队列清为空队列；

判断队列是否为空队列；计算队列的长度；读取队列的队头元素；向

队列插入一个元素为该队列的队尾元素；删除队列队头元素。队列只

允许在队尾插入元素，而在队头删除元素。

答案：B

32.栈结构不适用于下列哪一种应用。(2006.04)

A)表达式求值

B)树的层次次序周游算法的实现

C)二叉树对称序周游算法的实现

D)快速排序算法的实现

解析：见第4题。

答案：B

33.按层次次序将一棵有n个结点的完全二叉树的所有结点从1

到n编号，当i?n/2时,编号为i的结点的左孩子的编号是。(2006.04)

A)2i?l

C)2i+lB)2iD)不确定

解析：若对有n个节点的完全二叉树按层次从上到下，每个层次

从左至右的规则为节点编号，若i?n/2,则编号为i的节点的左孩子节

点的编号为2i；若i?n/2,则编号为i的节点没有左孩子节点。

答案：B

34.对于给出的一组权w={10,12,16,21,30},通过霍夫曼

算法求出的扩充二叉树的带权外部路径长度为。(2006.04)

A)89

C)200B)189D)300

解析：霍夫曼算法建立的扩充二叉树如下图所示。所以带权外部

路径长度为(21+16)X2+30X2+(12+10)义3=200

答案：C

35.设散列表的地址空间为0到10,散列函数为h(k)=kmodll,

用线性探查法解决碰撞。现从空的散列表开始，依次插入关键码值

95,14,27,68,82,则最后一个关键码82的地址为。(2006.04)

A)4

C)6B)5D)7

解析：本题采用除留余数法构造散列函数，将关键码值95,14,

27,68,82分别带入h(k)=kmodll,得到散列地址分别为7,3,5,

2,5,当存储关键码82时，由于其散列地址与前面的一个关键码发

生冲突，因此其存储

-31-

地址向后移1位到6o

答案：C

36.设有字符序列(Q,H,C,Y,P,A,M,S,R,D,F,X),

则新序列(F,H,C,D,P,A,M,Q,R,S,Y,X)是下列哪一个排

序算法一趟扫描的结果。(2006.04)

A)起泡排序

B)初始步长为4的希尔(shell)排序

C)二路归并排序

D)以第一个元素为分界元素的快速排序

解析：若进行升序起泡排序，则因为Q大于H,因此Q和H要

交换，新序列第一个字符应该为H；若进行降序起泡排序，Q和H位

置不变；若进行希尔排序，始步长为4,则Q应该与P分为一组，新

序列的第一个字符应该为P（升序）或Q（降序）。若进行二路归并

排序，则Q和H归并，排序后的结果应该为H,Q（升序）或者Q,

H（降序）。快速排序以第一个元素Q为分界元素处理原序列可得到

新序列。

答案：D

37.以下关于数据的逻辑结构的叙述中，哪一条是不正确的。

（2005.09）

A）数据的逻辑结构是数据间关系的描述

B）数据的逻辑结构不仅反映数据间的逻辑关系，而且反映其在

计算机中的存储方式

C）数据的逻辑结构分为线性结构和非线性结构

D）树形结构是典型的非线性结构解析：如第2题。

答案：B

38.在包含1000个元素的线性表中实现如下各运算，哪一个所

需的执行时间最短。（2005.09）

A）线性表按顺序方式存储,查找关键码值为666的结点

B）线性表按链接方式存储,查找关键码值为666的结点

C）线性表按顺序方式存储,查找线性表中第900个结点

D）线性表按链接方式存储,查找线性表中第900个结点

解析：线性表顺序方式存储，可直接计算确定第i个节点的存储

地址，其执行时间与i的值没有关系。查找链接存储方式的线性表中

的第i个节点，依次与前i?l个节点进行比较，最终确认结点的位置。

答案：c

39.在包含1000个元素的线性表中实现如下各运算，哪一个所

需的执行时间最长。（2005.09）

A）线性表按顺序方式存储，在线性表的第100个结点后面插入

一个新结点

B）线性表按链接方式存储，在线性表的第100个结点后面插入

一个新结点

C）线性表按顺序方式存储，删除线性表的第900个结点

D）线性表按链接方式存储，删除指针P所指向的结点

解析:A中需要把第1000个元素到第101个元素依次后移一位，

共需移动900个元素；B中只需从第一个节点开始，顺序查找到第100

个节点，再进行两次交换指针即可；C中在顺序表中删除一个元素,

需把删除元素的后面元素前移，共前移100个元素；D中在链接表中

删除节点，只需进行一次指针的修改即可。

答案：A

40.以下关于广义表的叙述中，哪一条是正确的。（2005.09）

A）广义表是。个或多个单元素或子表组成的有限序列

B）广义表至少有一个元素是子表

C）广义表不可以是自身的子表

D)广义表不能为空表

-32-

解析：广义表是线性表的扩展，它的定义是由n个数据元素组成

的有限序列，其中的数据元素既可以是单元素，也可以是子表；广义

表既可以是自身的子表，也可是空表。

答案：A

41-43题基于下图所示的二叉树：

41.该二叉树对应的树林包括几棵树。(2005.09)

A)1

C)3B)2D)4

解析：二叉树转换为树林，二叉树的根就是树林第一棵树的根；

二叉树的左子树转换为树林的第一棵树，二叉树的右子树对应于树林

中其余的树；二叉树右子树的根节点作为余下树中第一棵树的根节点,

其余以此类推。本题中的二叉树应该包含4棵树。

答案：D

42.如果用llink?rlink法存储该二叉树，则各结点的指针域中共

包含多少个空指针。(2005.09)

A)6

C)10B)8D)12

解析：二叉树采用llink?rlink法存储时，其指针域Mink和rlink分

别指向节点的左孩子和右孩子。题中二叉树D、G、H、I四个节点的

左右孩子和E节点的右孩子以及C节点的左孩子均为空，因此空指针

共有4X2+2X1=10个。

答案：C

43.如果将该二叉树存储为对称序线索二叉树，则结点H的左线

索指向哪一个结点（2005.09）

A）结点A

C）结点EB）结点CD）结点G

解析：采用对称序线索二叉树存储二叉树时，其访问次序是先中

序遍历左子树，然后访问根节点，最后遍历右子树。题中二叉树存储

为对称序线索二叉树的结果是：DBGEACHFI,所以节点H的左线索指

向节点C。

答案：B

44.以下关于B树运算的叙述中，哪一条是正确的o（2005.09）

A）若插入过程中根结点发生分裂，则B树的高度加1

B）每当进行插入运算，就在B树的最下面一层增加一个新结点

C）若要删除的关键码出现在根结点中，则不能真正删除，只能

做标记

D）删除可能引起B树结点个数减少，但不会造成B树高度减小

解析：对于根节点，由于没有双亲节点，所以如果根节点发生了

分裂，就要建立一个新的根节点，则B树的高度加1。

答案：A

45.对n个记录的文件进行归并排序，所需要的辅助存储空间

为。(2005.09)

A)0(1)B)0(n)

-33-

C)O(log2n)

间复杂度为0(n)。

答案：BD)0(n2)解析：归并排序需把每次归并的结果放

入另一个空间中，n个记录的文件就需再分配n个大小的空间，所以

空

二、填空题

1.按行优先顺序存储下三角矩阵Ann的非零元素，则计算非零

元素aij(lWjWWn)的地址的公式为Loc(aij)=,+i*(i?l)/2+(j?l)0

(2007.09)

解析：非零元素aij在矩阵中处在第i行第j歹U，在按行优先顺序

存储时，应先存储前i?l行的非零元素(共iX(i?l)/2个)和同一行的前

j?l个元素。如果all的存储地址为LOC(all),则aij的存储地址为

LOC(aij)?LOC(all)?i?(i?l)/2?(j?l)o

答案：Loc(all)

2.按对称序周游二叉树等同于按。(2007.09)

解析：按对称序周游二叉树相当于中序遍历二叉树。

答案：中序

3.m阶B+树的根节点至多有个孩子。(2007.09)

解析：按照B+树的定义，m阶B+树每个结点至多有m个孩子。

答案：m

4.三元组法和十字链表法都可以用于矩阵的存储表示。

(2007.04)

解析：三元组法和十字链表法均用于存储稀疏矩阵。用三元组存

储稀疏矩阵仅存储矩阵中的非零元素，十字链表法则为了避免进行删

除和插入操作时而导致的大量节点的移动。

答案：稀疏

5.有关键码值为10,20,30的三个结点，按所有可能的插入顺

序去构造二叉排序树，能构造出棵不同的二叉排序树。(2007.04)

解析：二叉排序树具有以下性质：若其左子树非空，则所有左子

树上数据元素关键字的值均小于根节点关键字的值；若其右子树非空,

则所有右子树上数据元素关键字的值均大于根节点关键字的值；其左

子树和右子树也是二叉排序树，因此能够构造出5棵二叉排序树。

答案：5

6.散列法存储的基本思想是：由结点的决定结点的存储地址。

(2006.09)

解析：散列法存储的基本思想是：由节点的关键码值决定节点的

存储地址，具体地址由散列函数决定。答案：关键码值

7.若一课二叉树的度为2的结点数为9,则该二叉树的叶结点

数为。(2006.09)

解析：二叉树的叶节点数为n0=n2+l,因此叶节点数9+1=10。

答案：10

8.在顺序表(3,6,8,10,12,15,16,18,21,25,30)中，

用二分法查找关键码值11,所需的关键码比较次数为o(2006.09)

解析：二分查找法的基本思路是不断把区间的中间元素与待查找

的元素比较，根据比较结果确定是结束查找还是在左边或右边子表并

按相同的方法继续查找。与11比较的关键码分别为15、8、10、12,

所以比较的次数为4。

答案：4

-34-

9.广义表是线性表的推广，是由零个或多个单元素或所组成

的有限序列。(2006.04)

解析：广义表是线性表的扩展，它的定义是由n个数据元素组成

的有限序列，其中的数据元素