数据结构与算法设计课后习题及答案详解

第一章

1.数据结构研究的主要内容包括逻辑结构、存储结构和算法。

2.数据元素是数据的基本单位，数据项是数据的最小标示单位。

3.根据数据元素之间关系的不同，数据的逻辑结构可以分为集合、树形、线性、图状。

4.常见的数据存储结构有四种类型：顺序、链式、索引、散列。

5.可以从正确性、可读性、健壮性、高效性四方面评价算法的质量。

6.在一般情况下，一个算法的时间复杂度是问题规模的函数。

7.常见时间复杂度有：常数阶O（1）、线性阶O（n）、对数阶O（log2 n）、平方阶O（n²）和指数阶O（2ⁿ）。通常认为，具有常数阶量级的算法是好算法，而具有指数阶量

级的算法是差算法。

8.时间复杂度排序由大到小（n+2）！>2ⁿ＋²>（n+2）4次方>nlog2 n>100000.

问答题：

1.什么叫数据元素？

数据元素是数据的基本单位，是数据这个集合的个体，也称为元素、结点、顶点、记录。

2.什么叫数据逻辑结构？什么叫数据存储结构？

数据逻辑结构：指数据元素之间存在的固有的逻辑结构。

数据存储结构：数据元素及其关系在计算机内的表示。

3.什么叫抽象数据类型？

抽象数据类型是指数据元素集合以及定义在该集合上的一组操作。

4.数据元素之间的关系在计算机中有几种表示方法？

顺序、链式、索引、散列。

5.数据的逻辑结构与数据的存储结构之间存在着怎样的关系？

相辅相成，不可分割。

6.什么叫算法？算法的性质有哪些？

算法：求解问题的一系列步骤的集合。

可行性、有容性、确定性、有输入、有输出。

7.评价一个算法的好坏应该从哪几方面入手？

正确性、可读性、健壮性、高效性。

第二章

1.线性表中，第一个元素没有直接前驱，最后一个元素没有直接后继。

2.线性表常用的两种存储结构分别是顺序存储结构和链式存储结构。

3.在长度为n的顺序表中，插入一个新元素平均需要移动表中的n/2个元素，删除一个元素平均需要移动（n-1）/2个元素。

4.在长度为n的顺序表的表头插入一个新元素的时间复杂度为O（n），在表尾插入一个新元素的时间复杂度为O（1）。

5.已知顺序表中每个元素占用3个存储单位，第13个元素的存储结构为336，则顺序表的首地址为300.

6.线性表的顺序存储结构通过物理相邻位置来反映数据元素之间的逻辑关系。

7.线性表的链式存储结构通过指针来反映数据元素之间的逻辑关系。

8.在长度为n的顺序表中，若删除i位置处的元素，则i的可能取值范围为1≤i≤n

9.已知一指针p指向非空不带头单链表的某一个结点，若p满足条件“p->next ！=NULL”，则p指向单链表的不是最后一个结点。

10.双向链表的每个结点均包含2个指针域，一个是指向前驱，一个是指向后继。

11.若p指针指向不带头双向循环链表的某个结点，则判断该链表只有一个结点的条件是p->prior==p->next。

12.若对线性表进行的主要操作是查询操作，则该线性表应该采用顺序存储结构；若需要频繁进行插入和删除操作，则该线性表应该采用链式存储结构。

13.线性表所含结点的个数称为线性表的表长。表长为0的线性表称为空表。

14.线性表的链式存储结构主要有单链表、循环链表、双链表。

15.在静态链表中，结点之间的逻辑关系通过游标来表示。

第三章

1.能够实现递归函数调用的一种数据结构是堆栈。

2.允许在一端插入，在另一端删除的线性表称为队列。插入的一端为队尾，删除的一端为队头。

3.在一个循环队列Q中，判断队空的条件为Q.front == Q.rear，判断队满的条件为（Q.rear+1）%QUEUESIZE==Q.front。

4.判别循环队列队空和队满的放法有：设置一个标志位，设置一个计数器和少用一个储存空间。

5.已知用求数组sq[50]存放循环队列的元素，且头指针和尾指针分别为19和2，则该队列的当前长度为33。

6.若用不带头结点的单链表来表示链队列，且链队头指针为front，则队列为空的条件为是front->next=NULL。

7.已知链队列Q的头、尾指针分别是front和rear，则出队操作是p = Q->front；Q->front=Q->front->next；free(p)。

8.栈的特点是后进先出，队列的特点是先进先出。

9.对于栈和队列，无论它们采用的是顺序储存结构还是链式储存结构，进行插入和删除操作的时间复杂度都是O(1)。

10.表达式d/(b—c) + a的后缀表达式为dbc—/a+。

第六章

1.除根结点以外，树中每个结点有1个前驱，0个或多个后继。

2.如图6-40所示的树有3个叶结点，有3个分支结点，度为3，A的结点的兄弟是B和C。

3.树的储存结构主要有双亲储存结构、孩子储存结构和孩子兄弟储存结构。

4.若用一棵完全二叉树的结点个数为10，则编号最大的分支结点的编号为5。

5.已知采用二叉树链表作为储存结构的一棵二叉树共有10个结点，则二叉树链表有20个指针域。

6.一棵具有10个结点的二叉树共有5和叶结点，则该二叉树有4个度为2的结点。1个度为1的结点。

7.一棵具有31个结点的满二叉树。它的高度是5，共有16个叶结点。

8.若二叉树的中序遍历序列和后序遍历序列相同，则该二叉树一定满足任何子结点都没有右子树。

9.一棵二叉树的中序遍历序列为CAEFDRB，则它的前序遍历序列为RACEBD。

10.根据遍历方法不同，线索二叉树分为‘前序线索二叉树，后序线索二叉树，中序线索二叉树。

11.树的后根遍历序列与其对应二叉树的中序遍历序列相同。

12.若二叉树的右子树为空，则与其对应的森林有1课树。

13.在哈夫曼树中，权值较大的叶结点一定离根结点较近。

14.哈夫曼树不存在度为1的结点。

第七章

1.有向图的极大连通子图称为强连通分量。

2.一个具有n个顶点的完全无向图的边数为1/2[n(n-1)];一个具有n个顶点的完全有向图的弧数为n(n-1)

3.在有向图中，顶点的度等于顶点的入度与出度之和。

4.一个有16个顶点的无向图，至少应该有15条边才能确保它是连通图。

5.一个有10个顶点的有向图，它最多能有90条边。

6.在有10个顶点的有向图中，每个顶点的度的最大值可以达到18.

7.迪杰斯特拉算法是按路径长度递增的次序产生最短路径的算法。

8.图的存储结构主要有邻接矩阵、邻接表、十字链表和邻接多重表四种。

9.图的遍历方法主要有深度优先搜索遍历和广度优先搜索遍历两种。

10．构造图的最小生成树的方法主要有普里姆算法和克鲁斯卡尔算法两种。

11.用图中的顶点表示活动，用弧表示活动间的先后关系，这样的有向图称为AOV网。

12.时间Vk的最早发生时间是从源点到顶点Vk的最大路径长度。

13.在AOE网中，从源点到汇点之间具有最大路径长度的路径称为关键路径。

14.一个有n个顶点的无向图，采用邻接矩阵作为存储结构，则求图中边数的方法是矩阵中1的个数除以2。求任一顶点的度的方法是计算该行中1的个数。

15.Prim算法适用于求稠密图的最小生成树，Kruskal算法适用于求稀疏图的最小生成树。

第八章

1.动态查找表和静态查找表的主要区别在于：动态查找表有插入和删除操作

2.顺序查找在查找成功情况下的平均查找长度为（n+1）/ 2；在查找失败情况下的平均查找长度为n+1.

3.折半查找只能使用顺序存储结构。

4.已知一个有序表为{10,23,35,46,48,55,59,,72,83,88,99}，当用折半查找方法查找

值为46和83的元素时，分别需要比较3次和4次才能查找成功；若采用顺序查找是，分别需要比较4次和10次才能查找成功。

5.索引顺序表上的查找分两个阶段，它们是确定待查元素所在的块和在块内查找待查的元素。

6.在一棵m阶B—树种，若在某结点中插入一个新关键字而引起该结点，则此结点中原有的关键字的个数是m-1；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是(m/2)-1。

7.二叉排序树查找成功是的平均查找长度一般为log2n。

8.哈希函数的构造方法主要有直接定址法、除留余数法、数字分析法、平方取中法和折叠移位法。

9.在哈希函数h（key）=key%m中，m值最好取小于等于表长的素数。

10.常用的处理冲突的方法有：开放定址法和链地址法。

问答题

1.顺序查找时间为O（n），折半查找时间为O（log2n）,哈希法为O（1），为什么有高效率的查找方法而低效率的方法不被放弃？

不同的查找方法使用的范围不同，高效率的查找方法并不是在所有情况下都比其他查找方法效率要高，而且也不是在所有情况下都可以采用。

2.为什么有序的单链表不能进行折半查找？

因为链表无法进行随机访问，若要访问链表中的结点，必须从头指针开始依次遍历链表，从而浪费大量时间。另外，也不好设定查找结束的条件。

3.在查找算法中，监视哨的作用是什么？

监视哨的作用是免去查找过程中每次都要检测整个表是否查找完毕，提高了查找效率。

第九章

1.根据在排序过程中使用的存储器将排序方法分为内部排序和外部排序。

2.常用的插入排序有直接排序、折半排序和希尔排序。

3.对于直接插入排序和直接选择排序，若待排序序列基本有序，则选用直接插入排序较好；若待排序序列为逆序，则选用直接选择排序较好。

4.直接插入排序在最好情况下的时间复杂度为O（n），在最坏的情况下的时间复杂度为O（n2）。

5.若堆中某一数据元素在数组中的下标为30，则它的左孩子的下标为61，右孩子的下标为62。

6.对于堆排序和快速排序，若带排序列基本有序，则选用堆排序较好；若待排序序列无序，则选用快速排序较好。

7.常用的选择排序方法有直接选择排序和堆排序。

8.设有字母序列｛P,D,F,Z,E,P,N,B,X,M,G,W｝，请写出按二路归并排序方法对该序列进行一趟扫描后的结果是D P F Z E P B N M X G W。

9.若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的比较和数据元素的移动。

10.基数排序所用队列可以是顺序队列，也可以是链队列。

问答题

1.已知关键字序列｛15,20,80,50,10,40｝，请给出冒泡排序的每一趟结果。

答：第一趟：15 20 50 10 40 80

第二趟：15 20 10 40 50 80

第三趟：15 10 20 40 50 80

第四趟：10 15 20 40 50 80

2.已知关键字序列｛52,43,78,99,85,30,40｝，请给出快速排序的第一趟和第二趟的结果。

答：第一趟：40 43 30 52 85 99 78

第二趟：30 40 43 52 78 85 99

3.已知关键字序列｛50,80,75,30,20,90,45,65,5,9｝，增量序列为5,3,1。请给出希尔排序的每一趟结果。

答：第一趟：50 45 65 5 9 90 80 75 30 20

第二趟：5 9 30 20 45 65 50 75 90 80

第三趟：5 9 20 30 45 50 65 75 80 90

4.已知关键字序列｛500,10,200,800,150,250,70,30,300｝，请给出构建大根堆的过程。

5.已知关键字序列｛50,3,80,10,20,60,40,90,1｝，请给出二路归并排序的每一趟结果。

答：第一趟：3 50 10 80 20 60 40 90 1

第二趟：3 10 50 80 20 40 60 90 1

第三趟：3 10 20 40 50 60 80 90 1

第四趟：1 3 10 20 40 50 60 80 90

6. 已知关键字序列｛501,023,417,225,418,391,565,359｝，请给出基数排序的每一趟结果。

答：第一趟：501 391 023 225 565 417 418 359

第二趟：501 417 418 023 225 359 565 391

第三趟：023 225 359 391 417 418 501 565

7.设有10000个无序的数据元素，可供选择的排序方法有：归并排序、基数排序、堆排序、希尔排序和快速排序。现在希望用最快速度挑选出前10个最大的数据元素，问采用什么方法最好？为什么？

答：这几种方法速度都很快，但归并排序、基数排序、希尔排序和快速排序都是在排序结束后才能确定数据元素的顺序，无法提前知道数据元素的有序性。只有堆排序，每次均输出最大（或最小）的数据元素，因此采用它比较合适。

第一章

1.数据结构研究的主要内容包括逻辑结构、存储结构和算法。

2.数据元素是数据的基本单位，数据项是数据的最小标示单位。

3.根据数据元素之间关系的不同，数据的逻辑结构可以分为集合、树形、线性、图状。

4.常见的数据存储结构有四种类型：顺序、链式、索引、散列。

5.可以从正确性、可读性、健壮性、高效性四方面评价算法的质量。

6.在一般情况下，一个算法的时间复杂度是问题规模的函数。

7.常见时间复杂度有：常数阶O（1）、线性阶O（n）、对数阶O（log2 n）、平方阶O（n²）和指数阶O（2ⁿ）。通常认为，具有常数阶量级的算法是好算法，而具有指数阶量级的算法是差算法。

8.时间复杂度排序由大到小（n+2）！>2ⁿ＋²>（n+2）4次方>nlog2 n>100000.

问答题：

1.什么叫数据元素？

数据元素是数据的基本单位，是数据这个集合的个体，也称为元素、结点、顶点、记录。

2.什么叫数据逻辑结构？什么叫数据存储结构？

数据逻辑结构：指数据元素之间存在的固有的逻辑结构。

数据存储结构：数据元素及其关系在计算机内的表示。

3.什么叫抽象数据类型？

抽象数据类型是指数据元素集合以及定义在该集合上的一组操作。

4.数据元素之间的关系在计算机中有几种表示方法？

顺序、链式、索引、散列。

5.数据的逻辑结构与数据的存储结构之间存在着怎样的关系？

相辅相成，不可分割。

6.什么叫算法？算法的性质有哪些？

算法：求解问题的一系列步骤的集合。

可行性、有容性、确定性、有输入、有输出。

7.评价一个算法的好坏应该从哪几方面入手？

正确性、可读性、健壮性、高效性。

第二章

1.线性表中，第一个元素没有直接前驱，最后一个元素没有直接后继。

2.线性表常用的两种存储结构分别是顺序存储结构和链式存储结构。

3.在长度为n的顺序表中，插入一个新元素平均需要移动表中的n/2个元素，删除一个元素平均需要移动（n-1）/2个元素。

4.在长度为n的顺序表的表头插入一个新元素的时间复杂度为O（n），在表尾插入一个新元素的时间复杂度为O（1）。

5.已知顺序表中每个元素占用3个存储单位，第13个元素的存储结构为336，则顺序表的首地址为300.

6.线性表的顺序存储结构通过物理相邻位置来反映数据元素之间的逻辑关系。

7.线性表的链式存储结构通过指针来反映数据元素之间的逻辑关系。

8.在长度为n的顺序表中，若删除i位置处的元素，则i的可能取值范围为1≤i≤n

9.已知一指针p指向非空不带头单链表的某一个结点，若p满足条件“p->next ！=NULL”，则p指向单链表的不是最后一个结点。

10.双向链表的每个结点均包含2个指针域，一个是指向前驱，一个是指向后继。

11.若p指针指向不带头双向循环链表的某个结点，则判断该链表只有一个结点的条件是p->prior==p->next。

12.若对线性表进行的主要操作是查询操作，则该线性表应该采用顺序存储结构；若需要频繁进行插入和删除操作，则该线性表应该采用链式存储结构。

13.线性表所含结点的个数称为线性表的表长。表长为0的线性表称为空表。

14.线性表的链式存储结构主要有单链表、循环链表、双链表。

15.在静态链表中，结点之间的逻辑关系通过游标来表示。

第三章

1.能够实现递归函数调用的一种数据结构是堆栈。

2.允许在一端插入，在另一端删除的线性表称为队列。插入的一端为队尾，删除的一端为队头。

3.在一个循环队列Q中，判断队空的条件为Q.front == Q.rear，判断队满的条件为（Q.rear+1）%QUEUESIZE==Q.front。

4.判别循环队列队空和队满的放法有：设置一个标志位，设置一个计数器和少用一个

储存空间。

5.已知用求数组sq[50]存放循环队列的元素，且头指针和尾指针分别为19和2，则该队列的当前长度为33。

6.若用不带头结点的单链表来表示链队列，且链队头指针为front，则队列为空的条件为是front->next=NULL。

7.已知链队列Q的头、尾指针分别是front和rear，则出队操作是p = Q->front；Q->front=Q->front->next；free(p)。

8.栈的特点是后进先出，队列的特点是先进先出。

9.对于栈和队列，无论它们采用的是顺序储存结构还是链式储存结构，进行插入和删除操作的时间复杂度都是O(1)。

10.表达式d/(b—c) + a的后缀表达式为dbc—/a+。

第六章

1.除根结点以外，树中每个结点有1个前驱，0个或多个后继。

2.如图6-40所示的树有3个叶结点，有3个分支结点，度为3，A的结点的兄弟是B和C。

3.树的储存结构主要有双亲储存结构、孩子储存结构和孩子兄弟储存结构。

4.若用一棵完全二叉树的结点个数为10，则编号最大的分支结点的编号为5。

5.已知采用二叉树链表作为储存结构的一棵二叉树共有10个结点，则二叉树链表有20个指针域。

6.一棵具有10个结点的二叉树共有5和叶结点，则该二叉树有4个度为2的结点。1个度为1的结点。

7.一棵具有31个结点的满二叉树。它的高度是5，共有16个叶结点。

8.若二叉树的中序遍历序列和后序遍历序列相同，则该二叉树一定满足任何子结点都没有右子树。

9.一棵二叉树的中序遍历序列为CAEFDRB，则它的前序遍历序列为RACEBD。

10.根据遍历方法不同，线索二叉树分为‘前序线索二叉树，后序线索二叉树，中序线索二叉树。

11.树的后根遍历序列与其对应二叉树的中序遍历序列相同。

12.若二叉树的右子树为空，则与其对应的森林有1课树。

13.在哈夫曼树中，权值较大的叶结点一定离根结点较近。

14.哈夫曼树不存在度为1的结点。

第七章

1.有向图的极大连通子图称为强连通分量。

2.一个具有n个顶点的完全无向图的边数为1/2[n(n-1)];一个具有n个顶点的完全有向图的弧数为n(n-1)

3.在有向图中，顶点的度等于顶点的入度与出度之和。

4.一个有16个顶点的无向图，至少应该有15条边才能确保它是连通图。

5.一个有10个顶点的有向图，它最多能有90条边。

6.在有10个顶点的有向图中，每个顶点的度的最大值可以达到18.

7.迪杰斯特拉算法是按路径长度递增的次序产生最短路径的算法。

8.图的存储结构主要有邻接矩阵、邻接表、十字链表和邻接多重表四种。

9.图的遍历方法主要有深度优先搜索遍历和广度优先搜索遍历两种。

10．构造图的最小生成树的方法主要有普里姆算法和克鲁斯卡尔算法两种。

11.用图中的顶点表示活动，用弧表示活动间的先后关系，这样的有向图称为AOV网。

12.时间Vk的最早发生时间是从源点到顶点Vk的最大路径长度。

13.在AOE网中，从源点到汇点之间具有最大路径长度的路径称为关键路径。

14.一个有n个顶点的无向图，采用邻接矩阵作为存储结构，则求图中边数的方法是矩阵中1的个数除以2。求任一顶点的度的方法是计算该行中1的个数。

15.Prim算法适用于求稠密图的最小生成树，Kruskal算法适用于求稀疏图的最小生成树。

第八章

1.动态查找表和静态查找表的主要区别在于：动态查找表有插入和删除操作

2.顺序查找在查找成功情况下的平均查找长度为（n+1）/ 2；在查找失败情况下的平均查找长度为n+1.

3.折半查找只能使用顺序存储结构。

4.已知一个有序表为{10,23,35,46,48,55,59,,72,83,88,99}，当用折半查找方法查找值为46和83的元素时，分别需要比较3次和4次才能查找成功；若采用顺序查找是，分别需要比较4次和10次才能查找成功。

5.索引顺序表上的查找分两个阶段，它们是确定待查元素所在的块和在块内查找待查的元素。

6.在一棵m阶B—树种，若在某结点中插入一个新关键字而引起该结点，则此结

点中原有的关键字的个数是m-1；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是(m/2)-1。

7.二叉排序树查找成功是的平均查找长度一般为log2n。

8.哈希函数的构造方法主要有直接定址法、除留余数法、数字分析法、平方取中法和折叠移位法。

9.在哈希函数h（key）=key%m中，m值最好取小于等于表长的素数。

10.常用的处理冲突的方法有：开放定址法和链地址法。

问答题

1.顺序查找时间为O（n），折半查找时间为O（log2n）,哈希法为O（1），为什么有高效率的查找方法而低效率的方法不被放弃？

不同的查找方法使用的范围不同，高效率的查找方法并不是在所有情况下都比其他查找方法效率要高，而且也不是在所有情况下都可以采用。

2.为什么有序的单链表不能进行折半查找？

因为链表无法进行随机访问，若要访问链表中的结点，必须从头指针开始依次遍历链表，从而浪费大量时间。另外，也不好设定查找结束的条件。

3.在查找算法中，监视哨的作用是什么？

监视哨的作用是免去查找过程中每次都要检测整个表是否查找完毕，提高了查找效率。

第九章

1.根据在排序过程中使用的存储器将排序方法分为内部排序和外部排序。

2.常用的插入排序有直接排序、折半排序和希尔排序。

3.对于直接插入排序和直接选择排序，若待排序序列基本有序，则选用直接插入排序较好；若待排序序列为逆序，则选用直接选择排序较好。

4.直接插入排序在最好情况下的时间复杂度为O（n），在最坏的情况下的时间复杂度为O（n2）。

5.若堆中某一数据元素在数组中的下标为30，则它的左孩子的下标为61，右孩子的下标为62。

6.对于堆排序和快速排序，若带排序列基本有序，则选用堆排序较好；若待排序序列无序，则选用快速排序较好。

7.常用的选择排序方法有直接选择排序和堆排序。

8.设有字母序列｛P,D,F,Z,E,P,N,B,X,M,G,W｝，请写出按二路归并排序方法对该序列进行一趟扫描后的结果是D P F Z E P B N M X G W。

9.若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的比较和数据元素的移动。

10.基数排序所用队列可以是顺序队列，也可以是链队列。

问答题

1.已知关键字序列｛15,20,80,50,10,40｝，请给出冒泡排序的每一趟结果。

答：第一趟：15 20 50 10 40 80

第二趟：15 20 10 40 50 80

第三趟：15 10 20 40 50 80

第四趟：10 15 20 40 50 80

2.已知关键字序列｛52,43,78,99,85,30,40｝，请给出快速排序的第一趟和第二趟的结果。

答：第一趟：40 43 30 52 85 99 78

第二趟：30 40 43 52 78 85 99

3.已知关键字序列｛50,80,75,30,20,90,45,65,5,9｝，增量序列为5,3,1。请给出希尔排序的每一趟结果。

答：第一趟：50 45 65 5 9 90 80 75 30 20

第二趟：5 9 30 20 45 65 50 75 90 80

第三趟：5 9 20 30 45 50 65 75 80 90

4.已知关键字序列｛500,10,200,800,150,250,70,30,300｝，请给出构建大根堆的过程。

5.已知关键字序列｛50,3,80,10,20,60,40,90,1｝，请给出二路归并排序的每一趟结果。

答：第一趟：3 50 10 80 20 60 40 90 1

第二趟：3 10 50 80 20 40 60 90 1

第三趟：3 10 20 40 50 60 80 90 1

第四趟：1 3 10 20 40 50 60 80 90

6. 已知关键字序列｛501,023,417,225,418,391,565,359｝，请给出基数排序的每一趟结果。

答：第一趟：501 391 023 225 565 417 418 359

第二趟：501 417 418 023 225 359 565 391

第三趟：023 225 359 391 417 418 501 565

7.设有10000个无序的数据元素，可供选择的排序方法有：归并排序、基数排序、堆排序、希尔排序和快速排序。现在希望用最快速度挑选出前10个最大的数据元素，问采用什么方法最好？为什么？

答：这几种方法速度都很快，但归并排序、基数排序、希尔排序和快速排序都是在排序结束后才能确定数据元素的顺序，无法提前知道数据元素的有序性。只有堆排序，每次均输出最大（或最小）的数据元素，因此采用它比较合适。