数据结构习题参考答案

千里之行，始于足下让知识带有温度。第第2页/共2页精品文档推荐数据结构习题参考答案第1章概论

1.数据、数据元素、数据结构、数据类型的含义分离是什么？

数据：对客观事物的符号表示，在计算机科学中是指全部能输入到计算机中并由计算机程序处理的符号的总称。

数据元素：数据的基本单位，在计算机程序中通常作为一个整体考虑。

数据结构：数据元素之间的关系+运算，是以数据为成员的结构，是带结构的数据元素的集合，数据元素之间存在着一种或多种特定的关系。

数据类型：数据类型是用来区别不同的数据；因为数据在存储时所需要的容量各不相同，不同的数据就必需要分配不同大小的内存空间来存储，全部就要将数据划分成不同的数据类型。数据类型包含取值范围和基本运算等概念。

2.什么是数据的规律结构？什么是数据的物理结构？数据的规律结构与物理结构的区分和联系是什么？

规律结构：数据的规律结构定义了数据结构中数据元素之间的互相规律关系。数据的规律结构包含下面两个方面的信息：

①数据元素的信息；

②各数据元素之间的关系。

物理结构：也叫储存结构，是指规律结构的存储表示，即数据的规律结构在计算机存储空间中的存放形式，包括结点的数据和结点间关系的存储表示。

数据的规律结构和存储结构是密不行分的，一个操作算法的设计取决于所选定的规律结构，而算法的实现依靠于所采与的存储结构。采纳不同的存储结构，其数据处理的效率是不同的。因此，在举行数据处理时，针对不同问题，挑选合理的规律结构和存储结构十分重要。

3.数据结构的主要操作包括哪些？

对于各种数据结构而言，他们在基本操作上是相像的，最常用的操作有：

●创建：建立一个数据结构；

●清除：清除一个数据结构；

●插入：在数据结构中增强新的结点；

●删除：把指定的结点从数据结构中删除；

●拜访：对数据结构中的结点举行拜访；

●更新：转变指定结点的值或转变指定的某些结点之间的关系；

●查找：在数据结构中查找满足一定条件的结点；

●排序：对数据结构中各个结点按指定数据项的值，以升序或降序重新罗列。

4.什么是抽象数据类型？如何定义抽象数据类型？

抽象数据类型（AbstractDataType简称ADT）是指一个数学模型以及定义在此数学模型上的一组操作。ADT是与详细的物理存储无关的数据类型，因此，不论ADT的内部结构如何变化，只要其数据结构的特性不变，都不影响其外部使用。

对抽象数据类型的描述普通用（D,R,P)三元组表示，抽象数据类型的定义格式为：

ADT

{

数据对象D：

数据关系R：

基本操作P：

｝ADT

其中，D是数据对象，R是D上的关系集，P是对D的基本操作集。

数据对象和数据关系的定义用伪代码来描述。基本操作的定义格式为：

基本操作名（参数表）

初始条件：

操作结果：

初始条件说明操作执行之前数据结构和参数应满足的条件；操作结果说明操作完成后，数据结构的变化情况和应返回的结果。

5.什么是算法？算法的基本特征是什么？

算法：是在有限的步骤内解决数知识题的过程，是以一步接一步的方式来具体描述计算机如何将输入转化为所要求的输出的过程，即算法是对计算机上执行的计算过程的详细描述。一个有效的算法必需满足的五个重要特性：

①有穷性：算法必需能在有限的时光内做完，即在任何状况下，算法必需能在执行有限个步骤之后终止，都不能陷入无穷循环中。

②确定性：算法中的每一个步骤，必需经过明确的定义，并且能够被计算机所理解和执行，而不能是抽象和含糊的概念，更不允许有二义性。

③输入：算法有0个或多个输入值，来描述算法开头前运算对象的初始状况，这是算法执行的起点或是依据。0个输入是指算法本身给出了运算对象的初始条件。

④输出：算法至少有1个或多个输出值，反映对运算对象的处理结果，没有输出的算法没有任何意义。

⑤可行性：算法中要做的运算都是基本运算，能够被精确地举行。即算法中执行的任何计算都可以被分解为基本的运算步，每个基本的运算步都可以在有限的时光内完成。

6.什么是算法分析？算法分析主要考虑哪几方面的内容？

算法的讨论与实际问题直接相关，用来解一个问题可以有无数不同的算法，他们之间的效果可能会有很大差异。算法设计者最关怀的就是什么是有效的算法，如何评价一个算法的优劣，如何从多种算法中挑选好的算法。除了要首先考虑算法的正确性外，还要分析和评价算法的性能。分析和评价算法的性能主要要考虑以下两个方面：

①时光代价：执行算法所耗费的时光。一个好的算法首先应当比其他算法的运行时光代价要小。算法的时光代价的大小用算法的时光复杂度来度量。

②空间代价：执行算法所耗费的存储空间，主要是辅助空间。算法运行所需的空间消耗是衡量算法优劣的另一个重要因素。算法的空间代价的大小用算法的空间复杂度来度量。

7.分析下面算法的时光复杂度。

（1）答：时光复杂度为n2

（2）时光复杂度：n

（3）时光复杂度：n

（4）时光复杂度：n2

（5）时光复杂度：O(log2n)

8.算法设计中的递归、穷举、递推和迭代等算法的基本思想是什么？

递推法：是利用问题本身所具有的一种递推关系求解问题的一种办法。它把问题求解分成若干步，找出相邻几步的关系，从而达到求解问题的目的。具有如下性质的问题可以采纳递推法：当得到问题规模为i-1的解后，由问题的递推性质，能构造出问题规模为i的解。因此，程序可以从i=0或i=1动身，由已知i-1规模的解，通过递推，获得问题规模为i的解，直至得到问题规模为n的解。

递归法：递归策略是利用函数直接或间接地调用自身来完成某个计算过程。能采纳递归描述的算法通常有这样的特征：为求解规模为n的问题，设法将它分解成规模较小的问题，然后从这些小问题的解便利地构造出更大问题的解，并且这些规模较小的问题也能采纳同样的分解和综合办法，分解成规模更小的问题，并从这些更小问题的解构造出较大规模问题的解。

穷举法：穷举搜寻法也称穷举法或搜寻法是对可能是解的众多候选解按某种挨次举行逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解。

迭代法：数值分析中通过从一个初始估量动身寻觅一系列近似解来解决问题（普通是解方程或者方程组）的过程，为实现这一过程所使用的办法统称为迭代法。

9.算法设计中的分治策略、贪心策略、动态规划策略、回溯策略以及分支定界策略的基本思想是什么？

分治策略的基本思想是把一个规模为n的问题划分为若干个规模较小、且与原问题相像的子问题，然后分离求解这些子问题，最后把各子结果合并得到囫囵问题的解。分解的子问题通常与原问题相像，所以可以递归地使用分治策略来求解。

贪心策略的基本思想是把一个整体最优问题分解为一系列的最优挑选问题，决策一旦做出，就不能再更改。它是通过若干次的贪心挑选而得出最优解（或较优解）的一种解题策略。

动态规划策略与贪心策略类似，将一个问题划分为重复的子问题，通过对相同子问题的求解来解决较大问题，即将一个问题的解决计划视为一系列决策的结果。不同的是，在贪心策略中，每采纳一次贪心准则便做出一个不行撤回的决策，可能得不到问题的最优解。而在动态规划中，处理要根据某种规章举行挑选，还要考察每个最优决策序列中是否包含一个最优子序列，目的是得到问题的最优解。

回溯策略也叫摸索法，它的基本思想是：在一些问题求解进程中，先挑选某一种可能状况向前探究，当发觉所选用的摸索性操作不是最佳挑选，需退回一步，重新挑选继续举行摸索，直到找到问题的解或者证实问题无解。

分支定界策略也常常被称为分支限界策略，它的基本思想是：首先确定目标值的上下界，然后一边搜寻一边剪掉空间树的某些不行能产生最优解的分支，提高搜寻效率。

其次章线性表

1．具有什么特征的数据结构被称为线性表？

线性表是一种最常用、最容易的典型线性数据结构，应用十分广泛。线性表是由n（n0）个数据元素组成的一个有限序列，线性表中数据元素的个数n称为线性表的长度。当n=0时，称为空表。

对于非空线性表，数据元素之间存在一对一的关系，详细特性如下：

第一个数据元素没有前驱；

最后一个数据元素没有后继外；

其他数据元素都是首尾相接、有且惟独一个前驱和后继。

2．如何实现线性表的挨次存储结构？

把线性表的结点按规律挨次依次存放在一组地址延续的存储单元里就构成了线性表的挨次存储，采纳挨次存储结构的线性表简称挨次表。线性表的挨次存储结构有如下特点：

●线性表中全部元素所占的存储空间是延续的；

●线性表的规律挨次与物理挨次全都；

●数组中的每一个元素的位置可以用公式来确定。假设线性表中的第一个数据元素的

存储地址（指第一个字节的地址，即首地址）为LOC(e1)，每一个数据元素占k个

字节，则线性表中第i个元素ei在计算机存储空间中的存储地址为：

LOC(ei)=LOC(e1)+(i-1)k

3．如何实现线性表的4种链式存储结构？

数据结构中的每一个数据元素对应于一个存储单元，这种存储单元称为存储结点，简称结点。每个结点分为两部分：一部分用于存放数据元素的值，称为数据域；另一部分是指针，用于指向与该结点在规律上相连的其他结点，称为指针域。对于线性表，指针域用于指向该结点的前一个或后一个结点（即前驱结点或后继结点）。通过结点的指针域将n个结点按其规律结构衔接在一起的数据存储结构，称为链式存储结构。

单向链表：在线性链表中，用一个特地的指针指向线性表中第一个结点，每一个结点的指针都指向它的下一个规律结点，线性链表的最后一个结点的指针为空（用NULL或0表示），表示链表终止，这样的线性链表称为单向链表。下图是单向链表暗示图。

线性表的单向链式存储

循环链表：将单向链表最后一个结点的指针指向头结点，这样囫囵链表就构成一个循环，这种链式存储结构称为单向循环链表，简称循环链表。头结点的指针域指向线性表的第一个元素的结点；循环链表中最后一个结点的指针域不再是NULL，而是指向头结点。惟独头结点的循环链表称为空循环链表。下图是带头结点的非空循环链表和空循环链表暗示图。

带头结点的循环链表

双向链表：双向链表的每个结点含有两个指针域，一个指针指向其前驱结点；另一个指针指向其后继结点。双向链表结点的结构下图（a）所示。

双向循环链表：假如将双向链表第一个结点的prev指针指向最后一个结点，将最后一个结点的next指针与指向第一个结点，就构成了双向循环链表。下图（b）和（c）是双向链表和双向循环表的规律结构暗示图。

图双向链表结点结构及双向链表

4．挨次表和线性链表分离有哪些优点和缺点？

线性表的挨次存储与链式存储比较

5．请列举出一些线性表问题的实例。

①按员工号排序的员工基本状况表；

②奥运会各项竞赛日程；

③按学号记录的同学的成果单；

等等。

6.对于挨次表和单向链表，如何实现统计重复元素个数的操作？

（c）双向循环链表

（a）双向链表结点结构

在挨次表中实现统计重复元素个数的操作：

在教材的【描述2-1】中，增强一个统计重复元素个数的成员函数：intCount(constT//返回x浮现的次数

在教材的【描述2-2】中，增强查找重复元素个数的成员函数的实现：//实现统计重复元素个数

template

intLinearList::Count(constT

for(inti=0;i

intLinkList::Count(constT

intcount=0;

while(p!=NULL

p=p->next;

}

returncount;

}

第3章栈和队列

1．具有什么特征的数据结构被称为栈和队列？先进后出、栈顶、栈底、先进先出、队头、队尾的概念是什么？

栈：一种插入和删除都只能在表的同一端举行的线性表。

队列：一种只允许在表的一端举行插入操作，而在表的另一端举行删除操作的线性表。

先进后出：元素是以e1，e2，……en挨次进入数据结构，以相反的挨次即en，en-1，……

e1离开数据结构。

栈顶：允许举行插入和删除操作的一端。

栈底：栈中与栈顶相对的另一端。

先进先出：元素是以e1，e2，……en挨次进入数据结构，以相同的挨次即e1，e2，……

en。离开数据结构。

队头：允许删除操作的一端。

队尾：允许插入操作的一端。

2．简述在挨次栈的栈顶插入一个元素的操作过程。

在插入元素之前，首先要推断栈是否为满，假如栈满，返回“沾满无法插入”等错误提醒信息；否则让top指针（指向当前挨次栈的栈顶）向后移动一个元素空间（元素大小），将要插入的元素放入top指针指向的内存单元中。

3.一个栈的输入序列为1、2、3，试给出所有可能的出栈序列。

可分为三种状况：

①、当惟独一个存储空间时，惟独一种出栈序列：1、2、3.

②、当有两个存储空间时，有：1、2、3，2、1、3，2、3、1等3种出栈序列

③、当存储空间大于等于三个时，有：1、2、3，2、1、3，2、3、1，3、2、1

等4种出栈序列。

4．循环队列的优点是什么？在循环队列中，仅依据头尾指针相等，无法推断队列是“空”还是“满”。要解决这个问题，常用的两种办法是什么？

循环队列的优点有两点：一是可以避开发生挨次队列的“假上溢”现象；二是充分利用队列的存储空间。

两种推断队列是“空”还是“满”的办法：一是商定少用一个元素空间；二是使用计数器size记录当前队列的实际长度。

5.简述在链接栈中插入一个元素的操作过程。

链接栈的插入操作，先将待进栈结点的指针域指向本来的栈顶结点，然后将栈顶指针top修改指向该结点，使进栈元素结点成为新的栈顶结点。

6．请列举出一些可以用栈和队列表示的实际问题。

全部“后进先出”(LIFO，LastInFirstOut）的实际问题都可以用栈表示。栈的应用主要有：数制的转换、括号的匹配检查、行编辑处理、表达式求解、走迷宫以及高级语言中函数的嵌套调用和递归的实现等。

全部“先进先出”(FIFO，FirstInFirstOut）的实际问题都可以用队列表示。如日常中的排队问题，队列的应用主要有：操作系统中各种资源哀求排队和各种缓冲区的先进先出管理，各种应用系统中的大事规划和大事模拟，树的层次遍历和图的广度优先遍历等。

第4章数组、字符串与广义表

1.具有什么特征的数据结构被称为数组？

数组可以看成是形如（index，value）的数据集合，其中，index是元素的索引，表示数据的规律位置，随意两个数据的index都不相同；value表示数据元素的值。

2.设有二维数组a[5][6]，每个元素占相邻的8个字节，存储器按字节编址，已知a的起始地址是1000，试计算：

（1）数组a的最后一个元素起始地址；

1000+（30-1）*8=1232。

（2）按行序优先时，元素a[3][5]的起始地址；

1000+（3*6+5）*8=1184

（3）按行列序优先时，元素a[4][3]的起始地址。

1000+（3*5+4）*8=1152

3.请简述数组和矩阵的关系。

矩阵是指纵横罗列的二维数据表格。在高级语言编程中，通常用二维数组来描述一个矩阵，从而可以对矩阵中的元素举行随机存取。但矩阵的索引通常从1而不是像数组那样从0开头，并且使用A（i，j）而不是A[i，j]的形式来引用矩阵中的元素。

4.矩阵有哪些基本运算？

矩阵的操作包括转置、加法、减法和乘法等。

5.稀疏矩阵的特点是什么？为什么要对稀疏矩阵采纳压缩存储技术？

稀疏矩阵的特点是矩阵中非零元素个数远远少于矩阵零元素个数。

采纳压缩存储技术主要是为了节约空间。

6.设A和B是稀疏矩阵，都以三元组作为存储结构，请写出矩阵相加的算法C=A+B。

//稀疏矩阵的三元组表示

#include

usingnamespacestd;

#defineM50

#defineN50

#defineMaxSize20

typedefintElemType;

typedefstruct

{

intr;

intc;

ElemTyped;

}TupNode;

typedefstruct

{

introws;

intcols;

intnums;

TupNodedata[MaxSize];

}TSMatrix;

intA[M][N],B[M][N];

//建立三元组

voidCreateMat(intA[M][N],TSMatrix

t.rows=row;t.cols=col;t.nums=0;

for(i=0;ib.data[j].c)

{

c.data[k].r=b.data[j].r;

c.data[k].c=b.data[j].c;

c.data[k].d=b.data[j].d;

j++;k++;

}

else

{

v=a.data[i].d+b.data[j].d;

if(v!=0)

{

c.data[k].r=a.data[i].r;

c.data[k].c=a.data[i].c;

c.data[k].d=v;

k++;

}

i++;j++;

}

}

elseif(a.data[i].r>row>>col;

cout>A[i][j];

cout>B[i][j];

CreateMat(A,a,row,col);

CreateMat(B,b,row,col);

cout并有∈E(G)，称vi为弧尾，vj为弧头。

无向图：若E(G)中的顶点偶对是无序的，则这些无序偶对就形成了无向边，此时图G称为无向图。

顶点的度、顶点的入度和顶点的出度：在无向图中，与顶点vi相关联的边的数目称为顶点vi的度。在有向图中，以顶点vi为弧头的弧的数目称为顶点vi的入度；以顶点vi为弧尾的弧的数目称为vi的出度；顶点vi的入度和出度之和称为vi的度。

路径和路径长度：在图G中，若存在一个顶点序列(0iv,1iv,…,1-niv)，使得对于随意

0≤j∈有相同弧尾nV1的下一条弧。不同表示办法猎取到的结果会有所不同（邻接矩阵法按顶点编号挨次，邻接压缩表和邻接链表按边的添加挨次）。

添加一个顶点：向图中添加一个新顶点。

添加一条边：对无向图，向图中添加一条新边；对有向图，向图中添加一条新弧。猎取一个顶点中存储的数据：按照顶点编号猎取该顶点中存储的数据。

推断一条边是否存在：对无向图，推断两个顶点nV1和nV2之间是否存在边；对有向图，推断是否存在从顶点nV1到顶点nV2的弧。

设置一条边的权：对无向图，设置指定边(nV1,nV2)上的权；对有向图，设置指定弧上的权。

猎取一条边的权：对无向图，猎取指定边(nV1,nV2)上的权；对有向图，猎取指定弧上的权。

5.请简述图的三种常用表示办法。

邻接矩阵法：用矩阵来表示各顶点之间的衔接关系。对于有n个顶点的图G=(V,E)，其邻接矩阵A为n*n的方阵，元素A[i][j]（0≤i,j∈上的权。

邻接压缩表：邻接矩阵的一种压缩表示形式，使用3个挨次表来表示图中顶点之间的衔接关系和权。设图中共有n个顶点{v0,v1,…,vn-1}，3个挨次表分离为s、w和h。在s中依次记录与顶点vi（i=0,1,…,n-1）相关联的顶点；在w中依次记录s中存储的各条边的权；在h中依次记录与顶点vi相关联的顶点在s中的起始存储位置。

邻接链表：图的一种链式存储结构。每个顶点中设置一个指向链表头的指针，在链表中保存与该顶点相邻接的顶点信息（包括顶点位置及两个顶点形成的边的权）。

6.请简述图的两种常用遍历办法及每一种遍历办法中结点的拜访挨次。

广度优先遍历：类似于树的逐层遍历，即先从某一个顶点开头拜访，然后拜访与该顶点相邻接且未被拜访过的顶点集V1(G)，再拜访与V1(G)中顶点相邻接且未被拜访过的顶点集V2(G)，重复该过程直至与初始顶点连通的全部顶点都被拜访完。对于非连通图或非强连通图，还要从某一个未被拜访的顶点开头重复上一过程，直至全部顶点拜访完毕。

深度优先遍历：类似于树的先序遍历，即从某一个顶点开头拜访，拜访后将该顶点去

除得到若干子图，对每个子图再依次举行深度优先遍历。

7.请列举最小生成树和最短路径可以用于解决什么应用问题。

请参考例6-1和例6-2。

8.请简述Prim算法的作用和详细步骤。

Prim算法用于最小生成树问题求解。对于有n个顶点的图G=(V,E)，Prim算法从空树T开头，根据以下规章将n个顶点和n-1条边依次添加到树中，形成最小生成树：

（a）从某一顶点v0'开头，将该顶点作为树的根结点加入到T中，使得T中的数据元素集合D={v0'}，数据元素关系集合R={}。

（b）对于一个顶点在集合D中、另一个顶点在集合V-D中的那些边，找出权最小的一条边，将该边在集合V-D中的顶点vi'（i=1,2,…,n-1）加入到集合D中，并将顶点间关系（jD(vj',vi')+D(vi',vk')，

则表明路径(vj',…,vi',…,vk')的长度更短，此时令D(vj',vk')=D(vj',vi')+D(vi',vk')并更新从顶点vj'到顶点vk'的路径。

第7章排序算法

1.请简述排序的作用。

排序的作用是将一个待排序元素集合按关键字递增（或递减）挨次收拾为一个有序序列。

2.请简述稳定排序和不稳定排序的含义。

若采纳某种排序算法对任一组元素举行排序，在排序前后，那些具有相同关键字值的元素之间的相对次序都保持不变，则将这种排序算法称为是稳定的，否则称为是不稳定的。3.请简述各种排序算法的适用范围。

排序算法的适用范围如下：

（a）直接插入排序、容易挑选排序和冒泡排序都是容易排序算法，它们的时光复杂度和空间复杂度分离为O(n2)和O(1)。若待排序元素数量n较小，可以选用直接插入排序和冒泡排序。另外，当待排序元素基本有序时，也应选用直接插入排序和冒泡排序，此时时光复杂度都能达到O(n)。若元素本身数据量较大，元素移动操作代价较高，则应选用平均移动元素次数最少的容易挑选排序。希尔排序是对直接插入排序算法的改进，大大降低了时光复杂度，但它是一种不稳定的排序算法。

（b）堆排序、迅速排序和归并排序主要适用于待排序元素数量n较大的状况，当待排序元素数量n较小时，它们的性能有可能劣于容易排序算法。因此，在实际应用时，迅速排序算法和归并排序算法常常与容易排序算法结合使用（例如，可以先用迅速排序算法将集合划分为规模更小的子集合，对于元素数量较小的子集合，则用直接插入排序算法举行排序）。在全部平均时光复杂度为O(nlog2n)的算法中，尽管迅速排序在最坏状况下时光复杂度较高，但它通常被认为是平均性能最好的一种算法，并且通过优化可以降低最坏状况浮现的概率。归并排序是一种稳定的排序算法，其时光性能普通要优于堆排序，但它所需要的辅助空间较多，当应用环境要求排序前后具有相同值的元素相对次序不能转变时可以考虑使用。堆排序所需的辅助空间最少，当可用空间十分有限时可以考虑使用。

（c）箱排序和基数排序的时光复杂度最低，但它们的空间复杂度最高。箱排序主要适用于待排序元素长度（即d值）较小的状况，在实际中应用不多；基数排序是箱排序的改进，主要适用于整数或字符串的排序，或者与其他排序算法结合举行实数的排序（例如，可以先用基数排序算法按整数部分将元素分成若干个子集合，再对每个子集合应用直接插入排序算法举行排序）。

5.请简述插入排序、挑选排序、交换排序、归并排序和分配排序的原理。

插入排序：按关键字大小每次将一个待排序的元素插入到已排序的序列中，直至全部元素都插入完毕。

挑选排序：每次从待排序的元素中挑选具有最小（或最大）关键字的元素放到已排序序列的尾部（或头部），直至全部元素都排序完毕。

交换排序：从待排序的元素中挑选两个次序相反的元素举行交换，直至随意两个元素的次序都正确。

K路归并排序：每次将K（K≥2）个已排序的子序列组合在一起，形成一个有序的序列，重复该过程直至得到一个包含全部待排序元素的有序序列。

分配排序：按照元素本身所具有的值将各元素逐一映射到一组有序空间中，最后再依次从有序空间中将各元素取出即形成了排序结果。

5.请简述直接插入排序的详细步骤。

直接插入排序是一种容易排序算法，其详细步骤为：

（a）初始已排序区为空，将第一个待排序的元素插入到已排序区中。

（b）将后继每一个待排序的元素依次取出，并根据关键字大小将其插入到已排序区中的适当位置，使该序列仍然有序。

（c）重复上一步骤直至将待排序的元素都插入到已排序序列中。

6.请简述希尔排序的详细步骤。

希尔排序，又称为“缩小增量排序”，其详细步骤为：

（a）令n为待排序元素数目，设置增量序列{d0,d1,…,dk}，其中n>d0>d1>…>dk=1。

（b）按增量di（i依次取值为0,1,…,k）将待排序元素分为di组，将全部下标距离为di的倍数的元素放在同一组中，即R[1],R[1+di],R[1+2*di],…在第一组中，R[2],R[2+di],R[2+2*di],……在其次组中，……，依此类推。然后分离在各组内举行直接插入排序。

（c）重复上一步骤直至最后以1为增量对全部待排序元素举行直接插入排序。

7.请简述容易挑选排序的详细步骤。

容易挑选排序是一种容易排序算法，其详细步骤为：

（a）初始已排序区为空，待排序区包含全部待排序元素。

（b）从待排序区中挑选具有最小关键字的元素，将其与待排序区的第一个元素交换位置，并将该位置加到已排序区中。

（c）重复上一步骤直至全部元素都排序完毕。

8.请简述堆的定义和堆的构建过程。

堆的定义：

对于包含n个元素的集合R={R[1],R[2],…,R[n]}，若满足：

（1）R[i]≤R[2*i]且R[i]≤R[2*i+1]（即R所表示的彻低二叉树中每一棵子树的根结点的值均不大于其孩子结点的值）。

（2）或R[i]≥R[2*i]且R[i]≥R[2*i+1]（即R所表示的彻低二叉树中每一棵子树的根结点的值均不小于其孩子结点的值）。

则称集合R为堆。若满足前一个条件则称R为小根堆，满足后一个条件则称R为大根堆。

堆的构建过程：

堆普通采纳自底向上的构建办法，即在将以某一结点为根结点的二叉树构建成堆之前，先将其左子树和右子树构建成堆。以叶子结点为根的子树必定是堆，因此，对于由n个元素构成的彻低二叉树，其对应的堆的构建过程从R[?n/2?]作为根结点的子树开头，依次对R[?n/2?-1]、R[?n/2?-2]、…、R[1]作为根结点的树举行堆的构建。

在将一棵R[i]作为根结点的子树收拾为堆时，惟独根结点不满足堆的条件，因此，需将根结点与后继层中的结点依次比较并不断将根结点下移直至该子树满足堆的条件，这里以大根堆构建为例介绍其详细过程：

（a）若R[i]存在左孩子R[2*i]，则令j=2*i；若R[i]存在右孩子R[2*i+1]且R[2*i+1]>R[2*i]，则令j=2*i+1。将R[j]与R[i]比较，若R[i]较小，则将R[i]和R[j]交换，并令i=j。

（b）重复上述步骤直至R[i]无孩子结点或R[i]比其孩子结点都大，此时该子树即为堆。

9.请简述堆排序的详细步骤。

堆排序的详细过程：

（a）采纳自底向上的办法将包含n个元素的待排序集合R={R[1],R[2],…,R[n]}收拾为大根堆，其元素数目i=n，初始时已排序集合R'为空集；

（b）将R[1]与R[i]交换，并将i算作已排序集合中的元素位置，更新待排序集合中最后一个元素的位置i=i-1，此时待排序集合R={R[1],R[2],…,R[i]}，已排序集合R'={R[i+1],

R[i+2],…,R[n]}。明显，待排序集合R={R[1],R[2],…,R[i]}中惟独根结点R[1]不满足大根堆的条件，通过下移R[1]重新将R收拾为大根堆；

（c）重复上一步骤直至待排序集合R={R[1]}，此时直接将R[1]作为已排序集合R'中的元素，堆排序过程结束。

10.请简述冒泡排序的详细步骤。

冒泡排序是一种容易排序算法，其详细步骤为：

（a）初始已排序区为空，待排序区包含全部待排序元素。

（b）在一轮排序中，对待排序区全部相邻元素先前至后举行两两比较，若相邻两个元素次序相反（即前一个元素的关键字值大于后一个元素的关键字值），则交换它们的位置。每轮排序后，待排序区中的最大元素会移到待排序区的尾部，将待排序区的最后一个元素放到已排序区的头部。

（c）重复上一步骤直至待排序区中只剩下一个元素或者在一轮排序中没有浮现相邻元素交换的状况，此时直接将待排序区中的全部元素按原次序放到已排序区的头部，冒泡排序结束。

11.请简述迅速排序中划分的含义和过程。

划分的含义：

划分是以指定元素x为基准将一个集合R分为两个子集R1和R2，其中R1中的元素都小于或等于x，R2中的元素都大于或等于x。

划分的过程：

对于包含(high-low+1)个元素的待排序集合R={R[low],R[low+1],…,R[high]}，以R[k]（low≤k≤high）为基准对其举行划分的详细过程为：

（a）令i、j分离指向集合R的第一个元素和最后一个元素（即i=low、j=high），并将R[k]与R[i]交换（即初始基准元素在i所指向的位置，此时基准元素前面没有任何元素，下面向基准元素后面、位置在i+1到j之间的元素根据从后至前的挨次逐一检查其是否大于或等于基准元素）。

（b）若j!=i且R[j]≥R[i]，则令j=j-1，重复直至R[j]R[j]或i==j。上述处理后，若i!=j（即通过R[i]>R[j]这个条件退出循环）则将R[i]与R[j]交换、j=j-1，并回到上一步（该步处理结束后，基准元素在i所指向的位置，此时基准元素前面的元素都小于或等于基准元素，而位置j后面的元素都大于或等于基准元素，下面继续对基准元素后面、位置在i+1到j之间的元素根据从后至前的挨次逐一检查其是否大于或等于基准元素）；否则集合划分操作结束。

12.请简述迅速排序的详细步骤。

迅速排序就是对集合不断划分的过程：通过划分可以将一个集合分为两个子集合，若子集合中元素数目大于1则再对子集合分离举行划分，重复该过程直至终于每个子集合中元素数目都小于或等于1时迅速排序结束。

13.请简述二路归并排序的详细步骤。

二路归并排序的详细步骤为：

（a）对于包含n个元素的待排序集合，将其分为n个长度为1的子序列。

（b）将每两个相邻的子序列举行归并，得到?n/2?个长度为2的子序列和0或1个长

度为1的子序列。

（c）在此基础上，再对每两个相邻的子序列举行归并，得到?n/4?个长度为4的子序列和0或1个长度小于4的子序列。

（d）重复该过程直至得到一个长度为n的有序序列为止。

14.请简述箱排序的详细步骤。

箱排序的详细步骤为：

（1）假设待排序元素的取值范围为m~m+n-1，则箱子数量为n，设置包含n个元素的队列集合B={B[0],B[1],…,B[n-1]}代表n个箱子。

（2）依次取出每一个待排序元素，若其值为m+i（i=0,1,…,n-1），则通过入队操作将其放在箱子B[i]中。

（3）从B[0]开头，依次检查集合B中每一个队列所代表的箱子，若箱子不为空，则通过出队操作将箱子中的元素逐个取出并依次加到已排序集合中。

15.请简述基数排序的详细步骤。

基数排序是对箱排序的改进和推广，它先将待排序元素按规章分解得到多个重量、再按照每一个重量对元素举行多次箱排序。

（a）对于数字排序问题，基数排序办法先将每一个数字写成以r为基数的按权绽开式形式：N=an-1*rn-1+…+a0*r0+a-1*r-1+…+a-m*r-m；再根据从低位到高位（即从r-m开头到rn-1）的挨次举行n+m次箱排序。

（b）对于字符串排序问题，基数排序办法根据从后至前的挨次对字符串中的每个字符分离举行箱排序。若待排序字符串中最长的字符串长度为n，则需举行n次箱排序；若某一字符串长度为m（0≤m≤n），则该字符串在前(n-m)次箱排序中对应的字符值为'\0'。

第8章查找算法

1.请简述查找的作用。

查找的作用是按照给定值从一个数据集合中搜寻某个元素。若某个元素的关键字值与给定值相等，则查找胜利；否则查找失败。

2.请简述静态查找和动态查找的含义。

静态查找只按照给定值在数据集合中按关键字查找匹配元素、拜访匹配元素的属性，而不对数据集合举行插入元素、删除元素等操作；而动态查找可能会在查找过程中向数据集合中插入一个新元素或从数据集合中删除一个已有元素。

3.请简述各种查找算法的适用范围。

各种查找算法的适用范围：

（a）挨次查找虽然查找效率最低，但其对待查找数据集合的存储结构无特殊要求，在对数据集合举行增、删、改等操作时效率较高，因此，按照那些不需要常常作查找操作的关键字举行查找时，普通采纳挨次查找算法。若常常作查找操作，则应使用效率较高的其他查找算法。

（b）折半查找和分块查找主要适用于数据集合增、删、改等操作较少的状况；二叉排序树查找则适用于数据集合变化较频繁的状况。

（c）哈希查找虽然在理论上具有最短的平均查找长度，但它占用的存储空间较多，且在实际中惟独哈希函数构造得好才干达到常量级的平均查找长度。而要想构造出好的哈希函数，必需以大量数据为基础，因此，哈希查找主要适用于数据分布已知的状况。

4.请简述挨次查找对待查找数据集合的要求及挨次查找的详细步骤。

挨次查找是一种最容易、直观的查找算法，适用于采纳任何存储结构的数据集合，其详细步骤为：

（a）按预先规定的挨次依次将数据集合中每个元素的关键字与给定值举行比较，若某个元素的关键字与给定值相同，则查找胜利；

（b）若遍历全部元素后，仍没有找到关键字与给定值相同的元素，则查找失败。

5.请简述折半查找对待查找数据集合的要求及折半查找的详细步骤。

折半查找，又称二分查找，它要求数据集合采纳挨次表存储结构，且数据集合中的元素是按关键字大小有序罗列的。假设数据集合的元素按关键字递增罗列，折半查找算法的详细步骤为：

（a）对于包含n个元素的递增数据集合R={R[1],R[2],…,R[n]}（R[i]≤R[i+1]），按照给定元素K举行折半查找，初始化待查找数据集合的下标起始位置low=1和结束位置high=n。

（b）计算中间元素下标mid=?(low+high)/2?，若R[mid]==K，则查找胜利，折半查找算法结束；若R[mid]K，则令high=mid-1。

（c）若新的待查找数据集合不为空，即low≤high，则返回到上一步在新的数据集合（R[low],R[low+1],…,R[high]）上继续举行折半查找；否则查找失败。

6.请简述分块查找对待查找数据集合的要求及分块查找的详细步骤。

在分块查找算法中，除了待查找的数据集合外，还需建立一个索引表。待查数据集合与索引表的关系描述如下：（a）将包含n个元素的待查找数据集合匀称分为b块（即b个子集合），前b-1块中元素数目s=?n/b?，最后一块中元素数目小于等于s。（b）分块后块内元素可以无序，但块间必需有序，这里假设块间为递增罗列，即第i+1块中的任一元素大于第i块中的任一元素（i<b）。（c）构造一个包含b个元素的索引表，用于记录每块的起始

位置和最大元素值。

分块查找算法的详细步骤为：（a）在索引表中查找，确定待查找元素在哪一块，因为索引表有序，因此可以使用二分查找算法。（b）在已确定的块中，举行挨次查找。

7.请简述二叉排序树的定义。

二叉排序树，又称二叉查找树，它或者是一棵空树，或者是具有如下性质的二叉树：（a）若它的左子树非空，则左子树上全部结点的值均小于根结点的值。

（b）若它的右子树非空，则右子树上全部结点的值均大于根结点的值。

（c）左、右子树也分离是二叉排序树。

8.请简述二叉排序树的插入和创建过程。

二叉排序树的插入过程：

在二叉排序树中插入一个新结点，应保证插入新结点后的二叉树仍然是一棵二叉排序树。对于一个给定元素K，将其插入到二叉排序树中的详细步骤如下：

（a）若二叉排序树为一棵空树，则将元素K作为二叉排序树的根结点。

（b）若K等于根结点的值，则该元素已经是二叉排序树中的结点，不需重复插入，直接返回；若K小于根结点的值，则将K插入到左子树中；若K大于根结点的值，则将K插入到右子树中。重复该步骤，直至要插入的子树为空，此时将K作为该子树的根结点。

二叉排序树的创建过程就是不断插入新结点的过程。

9.请简述二叉排序树的查找过程。

对于给定值K，先将K与根结点的值比较，若相等则查找胜利；若K小于根结点的值，则在左子树中继续举行二叉排序树的查找；否则，若K大于根结点的值，则在右子树中继续举行二叉排序树的查找。重复该过程，直至找到匹配的结点，查找胜利；或者子树为空，查找失败。

10.请简述哈希表的元素存储原理。

确定一函数h，对于关键字值是k的元素，以k为自变量计算函数值h(k)，这个函数值被解释为一片延续存储空间中的一个地址（即数组中的一个下标值），元素即被存入到这个地址中。

11.请简述常用的四种哈希函数及其计算规章。

除余法：选取一个适当的正整数p（通常p为不大于哈希表存储空间尺寸的最大素数），以元素的关键字值k除以p，得到的余数作为元素的存储地址，即h(k)=k%p。

数字分析法：若元素的关键字由多位组成，且关键字的位数比存储空间地址码位数多、每一位的取值范围及关键字的取值分布状况预先知道，则可以对元素关键字的各位举行分析，去掉分布较集中的位、保留分布较匀称的位。

折叠法：若元素的关键字由多位组成，且关键字的位数比存储空间地址码位数多，但关键字的取值分布状况未知，则可以用折叠法将关键字分为几段（除了最后一段位数可以少一些，其他各段的位数均等于存储空间地址码位数），并将全部段的值做叠加求和运算，将叠加和的最高位进位舍去后取剩余部分作为元素的存储地址。

平方取中法：对元素的关键字值求平方，并取中间几位作为元素的存储地址。

12.请简述常用的两种哈希表矛盾处理办法。

开放定址法：根据某个探查序列在哈希表中举行搜寻，直至找到一个空闲的地址，将发生矛盾的新元素存储在该地址中。

拉链法：将全部同义词存储在一个线性链表中，从而避开开放定址法中的“二次聚拢”现象。用拉链法构造的哈希表，若其有m个存储地址（下标为0,1,…,m-1），则每个地址存储一个线性链表的头指针，映射到地址i的元素以结点的方式插入到地址i所对应的链表中。

第9章文件

1.请简述文件的定义。

文件，是由大量具有相同性质的记录组成的集合。

2.请简述文件的组成。

文件是大量性质相同的数据记录的集合，即一个文件包含一条或多条记录。

记录是一个实体的全部数据项的集合，即一条记录包含一个或多个数据项。

数据项（也称为字段或属性）是反映实体某一方面属性的数据表示，是文件存取最基本的操作对象。

3.请简述文件的分类。

按文件中记录的信息长度，可以将文件分为定长记录文件和不定长记录文件。若每个记录含有相同长度的信息，则称这类记录为定长记录；否则，若每个记录含有不同长度的信息，则称这类记录为不定长记录。由定长记录组成的文件称为定长文件；由不定长记录组成的文件则称为不定长文件。

按记录中关键字的数目，可以将文件分为单关键字文件和多关键字文件。若文件中的记录惟独一个用于唯一标识记录的主关键字，则这类文件称为单关键字文件；若文件中的记录除了含有一个主关键字之外，还包含若干次关键字，则这类文件称为多关键字文件。

4.请简述文件检索操作中的四种查询方式。

按照检索条件的不同可以分为以下4种查询方式：

（a）容易查询：按照给定值x按单个关键字查询关键字值k等于x的记录。

（b）区域查询：按照给定取值范围按单个关键字查询满足条件的记录。

（c）函数查询：按照统计函数计算的值查询记录。

（d）布尔查询：将以上3种查询用规律运算符(包括规律与、规律或、规律非)衔接起来所形成的查询。

5.请简述文件各维护操作的含义和过程。

文件维护是指对文件中记录所举行的插入、删除、修改等操作。这些操作的详细含义和操作过程描述如下：

（a）插入：向文件中添加一条新的记录。若文件按某个关键字挨次罗列，则插入记录前普通要先通过检索确定插入点的位置。

（b）删除：从文件中删除一条记录。删除记录前普通要先通过检索确定所要删除记录的位置。

（c）修改：对记录中的一个或多个数据项举行修改。若文件按某个关键字挨次罗列，且对关键字值举行了修改操作，则修改后还需将记录移动到正确的位置（普通采纳先删除再插入的方式实现）。

6.请简述文件的四种基本组织方式。

挨次结构、索引结构、散列结构和链式结构。

7.请简述磁盘的规律结构。

磁盘的结构如下：

（a）一个磁盘包含若干个盘片，全部盘片组成了盘片组；每个盘片有上下两面，称为盘面；每个盘面上有无数同心圆形式的磁道，数据就存放在这些磁道上；每个磁道又可以划分为若干段，称为扇区，一个扇区就是一次读写的最小数据量。

（b）每个盘面都配有一个读写磁头，通过读写磁头可以对磁道上的数据举行读写操作；

全部读写磁头都安装在动臂上，通过动臂可以将读写磁头移动到任一磁道上；全部盘面上具有相同半径的磁道就构成了圆柱面，一个磁盘上圆柱面的个数就是一个盘面上的磁道数，同一时刻全部读写磁头都位于一个圆柱面上。

（c）主轴带动全部盘面高速旋转，使得读写磁头可以拜访到一个磁道上的全部扇区。

8.请简述对磁盘存储器举行一次读写操作的详细过程。

对磁盘存储器举行一次读写操作的详细步骤为：

（a）按照待读写数据所处的柱面，用动臂将读写磁头移动到此柱面上。

（b）按照待读写数据所处的扇区，用主轴带动盘面将该扇区转到读写磁头下面。

（c）用指定盘面上的读写磁头读写所需数据。

9.请简述在磁盘上存储信息的原则。

盘面的转速很快，磁盘读写数据的时光大部分花在柱面定位上。寻查时光的长短取决于读写磁头移过的柱面数，所以在磁盘上存储信息时应尽量将相关的信息放在同一柱面或者邻近柱面上，以削减寻查时光。

10.请简述挨次文件的定义和分类。

挨次文件的定义：

挨次文件是结构最容易的文件，文件中记录的物理挨次与规律挨次全都，即记录按其规律挨次依次存放在文件中。

挨次文件的分类：

根据存储方式的不同，挨次文件可以分为延续挨次文件和串联挨次文件。在延续挨次文件中，所有记录挨次地存放在外存的一片延续存储空间中。延续挨次文件的优点是存取速度快，缺点是存储空间尺寸需预先确定。在串联挨次文件中，以块为单位将记录存储在外存上，块中的各记录挨次存放在一片延续存储空间中，但块与块之间可以不延续，通过链指针将各块按一定挨次衔接起来。串联挨次文件的优点是文件便于扩充，缺点是存取速度慢。

根据记录是否有序，挨次文件可以分为有序挨次文件和无序挨次文件。在有序挨次文件中，所有记录按主关键字有序罗列；在无序挨次文件中，记录按实际插入挨次罗列。有序挨次文件的优点是若记录定长则按主关键字检索时速度较快，无序挨次文件的优点是插入记录时效率较高。

11.请简述挨次文件批量处理的步骤。

将待处理的挨次文件称为主文件，主文件按主关键字大小挨次罗列；对文件的插入、删除、修改等操作哀求所有放在事务文件中。按照事务文件中的操作对主文件举行更新生成新的主文件，详细处理步骤如下：

（a）对事务文件根据主文件中主关键字的挨次举行排序（对于修改主关键字值的操作，应转为删除记录和插入记录两个操作）。

（b）挨次读出主文件与事务文件中的记录，比较它们的主关键字值：

①若主文件记录的关键字值小于事务文件记录的关键字值，则说明没有对该主文件记录做任何操作，此时将主文件记录直接写入新的主文件中，并读取下一条主文件记录。

②若关键字值相同，则依据事务文件记录举行更改或删除操作，若为删除操作，则主文件记录不需要写入新的主文件中，若为修改操作则要将修改后的记录写入新的主文件中，操作完毕后分离读取下一条主文件记录和事务文件记录。

③若主文件记录的关键字值大于事务文件记录的关键字值，则为插入操作，需将事务文件中的记录直接写入到新的主文件中，并读取下一条事务文件记录。

12.请简述索引文件的构成。

索引文件由主文件和索引表两部分构成。主文件中存储了全部的数据记录；索引表是一个映射关系表，存储了规律记录和物理记录的一一对应关系。

13.请简述索引文件（即索引非挨次文件）和索引挨次文件的区分。

索引非挨次文件的主文件中各记录是无序的；索引挨次文件的主文件中各记录是按主关键字有序罗列的。

14.请简述索引文件的检索过程。

索引文件的检索过程为：

（a）将索引表读入内存中，并按照检索条件在索引表中举行查找（因为索引项按关键字有序罗列，因此在索引表上可以采纳折半查找算法）。

（b）若索引表中存在匹配项，则按照匹配索引项中存储的物理地址直接读取外存上的相应记录；若索引表中不存在该记录，则说明外存上也不存在该记录、不需做外存拜访操作。

15.请简述索引文件插入、删除、修改等维护操作的过程。

插入：在索引文件中插入一条新的记录时，直接将该记录写入主文件的末尾，并在索引表中插入索引项。

删除：在删除一条记录时，只需在索引表中删除对应的索引项即可。

修改：在修改记录时，需将修改后的记录写入主文件的末尾，并同时对索引表举行修改、将索引项中的物理地址改为修改后记录的存储地址。

16.请简述稠密索引和稀疏索引的区分。

在索引非挨次文件中，记录没有按关键字有序罗列，因此在建立索引表时，每个记录都必需对应一个索引项，这样建立的索引表称为稠密索引。这类索引表虽然管理成本较高，但它的优点是按照索引表即可确定待检索记录是否存在并可以按照索引项直接定位到记录，削减了外存操作。

在索引挨次文件中，记录按关键字有序罗列，因此可以对文件中的记录分块，每块对应一个索引项，这样建立的索引表称为稀疏索引。在做检索操作时，这类索引表只能给出匹配记录可能在哪个范围中，无法直接定位到记录，但它占用的存储空间小、便于管理。

17.请简述ISAM文件的组织办法。

在ISAM文件中，每个柱面的磁道被分为3个部分：

（a）一部分磁道作为记录存储的基本区，其中每一磁道将记录按主关键字大小举行有序挨次存储。

（b）一部分磁道作为记录存储的溢出区，在一个已满磁道中插入新记录时，就会产生溢出的记录（即该磁道容纳不下的记录），这些溢出记录以链表形式存储在溢出区中。

（c）一部分磁道作为索引区，用于存储磁道索引表。与基本区和溢出区相对应，表中的每一索引项又由基本索引项和溢出索引项组成。基本索引项用来存放基本区一个磁道中记录的最大关键字值和第一个记录的位置；溢出索引项用来存放从该磁道溢出记录的最大关键字值和该磁道在溢出区中的第一个溢出记录的位置。

18.请简述VSAM文件的组织办法。

VSAM文件由索引集、挨次集和数据集三部分组成。文件的记录都存放在数据集中，数据集中的每一个结点称为一个控制区间，该区间是一片延续的存储空间、按关键字挨次存储若干条记录；挨次集中存放每一控制区间的索引项，索引项包括两部分内容：控制区间的最大关键字值和指向该控制区间的指针，若干规律上相邻的控制区间的索引项就构成了挨次集中的一个结点；索引集是按树型层次结构组织的索引集合，双亲结点包含了指向孩子结点的指针及该孩子结点中的最大关键字值，以挨次集中的结点作为叶子结点，可以构造一棵以索引集为非叶子结点的B+树。

19.请简述散列文件的组织办法。

散列文件中的记录是以桶为单位成组存放的。若一个桶能存放m条记录，则当桶中已有m条同义词记录时，再存放第m+1条同义词记录就会发生“溢出”。在散列文件中，通

常采纳拉链法作为矛盾处理办法，即将第m+1条同义词记录存放到另一个称为“溢出桶”的桶中，相应地，将存放前m条同义词记录的桶称为“基桶”，在基桶中设置一个指向溢出桶的指针。

20.请简述多关键字文件