数据结构部分课后习题答案(耿国华)

第一章 绪论

一、问答题

1. 什么是数据结构？

2. 叙述四类基本数据结构的名称与含义。 3. 叙述算法的定义与特性。 4. 叙述算法的时间复杂度。 5. 叙述数据类型的概念。

6. 叙述线性结构与非线性结构的差别。 7. 叙述面向对象程序设计语言的特点。

8. 在面向对象程序设计中，类的作用是什么？ 9. 叙述参数传递的主要方式及特点。 10. 叙述抽象数据类型的概念。

二、判断题（在各题后填写“√”或“×”）

1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（ ） 2. 算法就是程序。（ ）

3. 在高级语言（如C或 PASCAL）中，指针类型是原子类型。（ ） 三、计算下列程序段中X=X+1的语句频度

for(i=1;i<=n;i++) for(j=1;j<=i;j++)

for(k=1;k<=j;k++) x=x+1;

【解答】

i=1时： 1 = (1+1)×1/2 = (1+12)/2 i=2时： 1+2 = (1+2)×2/2 = (2+22)/2 i=3时： 1+2+3 = (1+3)×3/2 = (3+32)/2 …

i=n时： 1+2+3+……+n = (1+n)×n/2 = (n+n2)/2

x=x+1的语句频度为：

f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2 =[ (1+n)×n/2 + n(n+1)(2n+1)/6 ] / 2 =n(n+1)(n+2)/6 =n3/6+n2/2+n/3

区分语句频度和算法复杂度： O(f(n)) = O(n3)

四、试编写算法，求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入ai(i=0,1,…,n),x和n，输出为Pn(x0)。通常算法的输入和输出可采用下列两种方式之一：

（1）通过参数表中的参数显式传递。 （2）通过全局变量隐式传递。

试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出 【解答】

（1）通过参数表中的参数显式传递

优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通

用性强，移置性强。

缺点：形参须与实参对应，且返回值数量有限。 （2）通过全局变量隐式传递

优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗 缺点：函数通用性降低，移植性差 算法如下：通过全局变量隐式传递参数

PolyValue() { int i,n;

float x,a[],p; printf(“\\nn=”); scanf(“%f”,&n); printf(“\\nx=”); scanf(“%f”,&x); for(i=0;i

scanf(“%f ”,&a[i]); /*执行次数：n次 */ p=a[0];

for(i=1;i<=n;i++)

{ p=p+a[i]*x; /*执行次数：n次*/ x=x*x;} printf(“%f”,p); }

算法的时间复杂度：T(n)=O(n)

通过参数表中的参数显式传递

float PolyValue(float a[ ], float x, int n) {

float p,s; int i; p=x; s=a[0];

for(i=1;i<=n;i++)

{s=s+a[i]*p; /*执行次数:n次*/ p=p*x;} return(p); }

算法的时间复杂度：T(n)=O(n)

第二章 线性表

2.1 描述以下三个概念的区别：头指针，头结点，首元素结点。 2.2 填空：

（1） 在顺序表中插入或删除一个元素，需要平均移动＿＿一半＿＿元素，具体移动的元

素个数与＿＿插入或删除的位置＿＿有关。

（2） 在顺序表中，逻辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。在单链表中，逻

辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。

（3） 在带头结点的非空单链表中，头结点的存储位置由＿＿＿＿＿＿指示，首元素结点

的存储位置由＿＿＿＿＿＿指示，除首元素结点外，其它任一元素结点的存储位置由＿＿其直接前趋的next域＿＿指示。

2.3 已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。

a. 在P结点后插入S结点的语句序列是：＿（4）、（1）＿。 b. 在P结点前插入S结点的语句序列是：（7）、（11）、（8）、（4）、（1）。 c. 在表首插入S结点的语句序列是：（5）、（12）。 d. 在表尾插入S结点的语句序列是：（11）、（9）、（1）、（6）。 供选择的语句有： （1）P->next=S;

（2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L;

（6）S->next= NULL;

（7）Q= P;

（8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P;

2.4 已知线性表L递增有序。试写一算法，将X插入到L的适当位置上，以保持线性表L的有序性。

Status Insert_SqList(SqList &va,int x)//把x插入递增有序表va中 {

if(va.length+1>va.listsize) return ERROR; va.length++;

for(i=va.length-1;va.elem[i]>x&&i>=0;i--) va.elem[i+1]=va.elem[i]; va.elem[i+1]=x; return OK; }//Insert_SqList

2.5 写一算法，从顺序表中删除自第i个元素开始的k个元素。 [提示]：注意检查i和k的合法性。 （集体搬迁，“新房”、“旧房”） < 方法1 > 以待移动元素下标m（“旧房号”）为中心， 计算应移入位置（“新房号”）：

for ( m= i－1+k; m<= L－>last; m++) L－>elem[ m－k ] = L－>elem[ m ];

< 方法2 > 同时以待移动元素下标m和应移入位置j为中心： < 方法2 > 以应移入位置j为中心，计算待移动元素下标：

2.6已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。

Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链表L中值大于mink且小于maxk的所有元素 { p=L;

while(p->next->data<=mink) p=p->next; //p是最后一个不大于mink的元素 if(p->next) //如果还有比mink更大的元素 {

q=p->next;

while(q->datanext; //q是第一个不小于maxk的元素 p->next=q; }

}//Delete_Between

2.7试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。

（1） 以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2） 以单链表作存储结构。 [方法1]:在原头结点后重新头插一遍

[方法2]:可设三个同步移动的指针p, q, r，将q的后继r改为p 2.8 假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编

写算法，将A表和B表归并成一个按元素值递减有序的排列的线性表C，并要求利用原表（即A表和B表的）结点空间存放表C.

[提示]：参P.28 例2-1 < 方法1 >

void merge(LinkList A; LinkList B; LinkList *C) { ……

pa=A－>next; pb=B－>next; *C=A; (*C)－>next=NULL;

while ( pa!=NULL && pb!=NULL ) { if ( pa－>data <= pb－>data ) { smaller=pa; pa=pa－>next;

smaller－>next = (*C)－>next; /* 头插法 */ (*C)－>next = smaller; } else

{ smaller=pb; pb=pb－>next; smaller－>next = (*C)－>next; (*C)－>next = smaller; }

while ( pa!=NULL)

{ smaller=pa; pa=pa－>next; smaller－>next = (*C)－>next; (*C)－>next = smaller; }

while ( pb!=NULL)

{ smaller=pb; pb=pb－>next; smaller－>next = (*C)－>next; (*C)－>next = smaller; }

< 方法2 >

LinkList merge(LinkList A; LinkList B) { ??

LinkList C；

pa=A－>next; pb=B－>next; C=A; C－>next=NULL; ?? ??

return C;

while(pa||pb)

{

if(pa->datadata||!pb) {

pc=pa;q=pa->next;pa->next=pre;pa=q; //将A的元素插入新表

} else {

pc=pb;q=pb->next;pb->next=pre;pb=q; //将B的元素插入新表 }

pre=pc; }

C=A;A->next=pc; //构造新表头 }//reverse_merge

分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩余元素.

2.9

假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。

[提示]：设指针p指向s结点的前趋的前趋，则p与s有何关系？

Status Delete_Pre(CiLNode *s)//删除单循环链表中结点s的直接前驱 { p=s;

while(p->next->next!=s) p=p->next; //找到s的前驱的前驱p p->next=s; return OK; }//Delete_Pre

2.10 已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。

Status LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiList &C)//把单链表L的元素按类型分为三个循环链表.CiList为带头结点的单循环链表类型. {

s=L->next;

A=(CiList*)malloc(sizeof(CiLNode));p=A; B=(CiList*)malloc(sizeof(CiLNode));q=B;

C=(CiList*)malloc(sizeof(CiLNode));r=C; //建立头结点 while(s) {

if(isalphabet(s->data)) {

p->next=s;p=s; }

else if(isdigit(s->data)) {

q->next=s;q=s; }

{

StrAssign(c,SubString(s,i,1));

for(j=1;j

for(k=1;k<=Strlen(t)&&StrCompare(c,SubString(t,k,1));k++); //判断当前字符是否包含在t中

if(k>Strlen(t)) StrAssign(r,Concat(r,c)); } }//for

}//String_Subtract

第五章 数组和广义表

1． 假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。已知A的

基地址为1000，计算：

（1） 数组A共占用多少字节； （288）

（2） 数组A的最后一个元素的地址； （1282） （3） 按行存储时，元素A36的地址； （1126） （4） 按列存储时，元素A36的地址； （1192） [注意]：本章自定义数组的下标从1开始。

2． 设有三对角矩阵（aij）n×n ,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得

B[k]= aij ，求：

（1） 用i,j表示k的下标变换公式； （2） 用k表示i,j的下标变换公式。 i = k/3 + 1, j = k%3 + i - 1 = k%3 + k/3 或：

i = k/3 + 1, j = k - 2×( k/3 )

3. 假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放结果矩阵。

void TSMatrix_Add(TSMatrix A,TSMatrix B,TSMatrix &C)//三元组表示的稀疏矩阵加法 {

C.mu=A.mu;C.nu=A.nu;C.tu=0; pa=1;pb=1;pc=1;

for(x=1;x<=A.mu;x++) //对矩阵的每一行进行加法 {

while(A.data[pa].i

while(A.data[pa].i==x&&B.data[pb].i==x)//行列值都相等的元素 {

if(A.data[pa].j==B.data[pb].j) {

ce=A.data[pa].e+B.data[pb].e; if(ce) //和不为0 {

C.data[pc].i=x;

C.data[pc].j=A.data[pa].j; C.data[pc].e=ce; pa++;pb++;pc++; } }//if

else if(A.data[pa].j>B.data[pb].j) {

C.data[pc].i=x;

C.data[pc].j=B.data[pb].j; C.data[pc].e=B.data[pb].e; pb++;pc++; } else {

C.data[pc].i=x;

C.data[pc].j=A.data[pa].j; C.data[pc].e=A.data[pa].e pa++;pc++; }

}//while

while(A.data[pa]==x) //插入A中剩余的元素(第x行) {

C.data[pc].i=x;

C.data[pc].j=A.data[pa].j; C.data[pc].e=A.data[pa].e pa++;pc++; }

while(B.data[pb]==x) //插入B中剩余的元素(第x行) {

C.data[pc].i=x;

C.data[pc].j=B.data[pb].j; C.data[pc].e=B.data[pb].e; pb++;pc++; } }//for C.tu=pc;

}//TSMatrix_Add

4．在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法 只占用一个辅助向量空间。

5．写一个在十字链表中删除非零元素aij的算法。 [提示]：“删除”两次，释放一次。

6．画出下面广义表的两种存储结构图示：

((((a), b)), ((( ), d), (e, f)))

7．求下列广义表运算的结果： （1） HEAD[((a,b),(c,d))]; （2） TAIL[((a,b),(c,d))];

（3） TAIL[HEAD[((a,b),(c,d))]];

（4） HEAD[TAIL[HEAD[((a,b),(c,d))]]]; b （5） TAIL[HEAD[TAIL[((a,b),(c,d))]]]; (d)

实习题

若矩阵Am×n中的某个元素aij是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马鞍点。

void Get_Saddle(int A[m][n])//求矩阵A中的马鞍点 {

for(i=0;i

for(min=A[i][0],j=0;j

if(A[i][j]

if(A[i][j]==min) //判断这个(些)最小值是否鞍点 {

for(flag=1,k=0;k

printf(\ } }//for

}//Get_Saddle

第六章 数和二叉树

1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。

3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，nk个度为k的结点，则该树中有多少个叶子结点？ [提示]：参考 P.116 性质3 ∵ n=n0 + n1 + …… + nk

B=n1 + 2n2 + 3n3 + …… + knk n= B + 1

∴ n0 + n1 + …… + nk = n1 + 2n2 + 3n3 + …… + knk + 1 ∴ n0 = n2 + 2n3 + …… + (k-1)nk + 1

4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。

[提示]：参考 P.148 6． 已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？ [提示]：一个叶子结点，总结点数至多有多少个？可压缩一度结点。 7． 给出满足下列条件的所有二叉树：

a) 前序和中序相同 b) 中序和后序相同 c) 前序和后序相同 [提示]：去异存同。

a) D L R 与L D R 的相同点：D R，如果无 L，则完全相同, 如果无 LR，?。 b) L D R 与L R D 的相同点：L D，如果无 R，则完全相同。 c) D L R 与L R D 的相同点：D，如果无 L R，则完全相同。 （如果去D，则为空树） 7． n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child域有多少个？

[提示]：参考 P.119

8．画出与下列已知序列对应的树Ｔ：

树的先根次序访问序列为GFKDAIEBCHJ； 树的后根次序访问序列为DIAEKFCJHBG。 [提示]：

（1）先画出对应的二叉树

（2）树的后根序列与对应二叉树的中序序列相同

9．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为： 0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10 （1）请为这8个字母设计哈夫曼编码， （2）求平均编码长度。

10．已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点的指针,是

否可不用递归且不用栈来完成?请简述原因. [提示]：无右子的“左下端”

11. 画出和下列树对应的二叉树：

12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。

13．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。 [提示]： [方法1]：（1）按先序查找；（2）超前查看子结点（3）按后序释放； void DelSubTree(BiTree *bt, DataType x) {

if ( *bt != NULL && (*bt) ->data==x ) { FreeTree(*bt); *bt =NULL; }

else DelTree( *bt, x)

void DelTree(BiTree bt, DataType x) { if ( bt )

{ if (bt->LChild && bt->LChild->data==x) { FreeTree(bt->LChild); bt->LChild=NULL; }

if (bt->RChild && bt->RChild->data==x) { FreeTree(bt->RChild); bt->RChild=NULL; }

DelTree(bt->LChild, x); DelTree(bt->RChild, x); } }

[方法2]：（1）先序查找；（2）直接查看当前根结点（3）用指针参数； [方法3]：（1）先序查找；（2）直接查看当前根结点 （3）通过函数值，返回删除后结果； （参示例程序）

14．分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。 [提示]：

（1）先查看线索，无线索时用下面规律：

（2）结点*p在先序序列中的后继为其左子或右子；

（3）结点*p在后序序列中的前驱也是其左子或右子。

15．分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。（参例题）

16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。 [提示]：

（1）可将孩子-兄弟链表划分为根、首子树、兄弟树，递归处理。 （2）可利用返回值，或全局变量。

17．对以孩子-兄弟链表表示的树编写计算树的深度的算法。 18．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。 （参课本）

19．设二叉树按二叉链表存放，写算法判别一棵二叉树是否是一棵正则二叉树。正则二叉树是指：在二叉树中不存在子树个数为1的结点。 [提示]：可利用任何递归、非递归遍历算法。

20．计算二叉树最大宽度的算法。二叉树的最大宽度是指：二叉树所有层中结点个数的最大值。 [提示]： [方法一]：

（1）利用队列，初值为根

（2）出队访问，并将左、右子入队，直到队空 （3）记录每一层中最后一个结点在队中的位置

（4）第i层最后一个结点的右子，必是第i+1层的最后一个结点 （5）第1层最后一个结点在队中的位置为0

[方法二]：利用层号和全局数组，任意遍历、统计 21．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。

22. 证明：给定一棵二叉树的前序序列与中序序列，可唯一确定这棵二叉树； 给定一棵二叉树的后序序列与中序序列，可唯一确定这棵二叉树； 23. 二叉树按照二叉链表方式存储，编写算法将二叉树左右子树进行交换。

第七章 图

7.1

已知如图所示的有向图，请给出该图的： （1） 每个顶点的入度、出度； （2） 邻接矩阵； （3） 邻接表； （4） 逆邻接表； （5） 十字链表； （6） 强连通分量。

7.2 已知如图所示的无向图，请给出该图的：

（1） 邻接多重表；（要求每个边结点中第一个顶点号小于第二个顶点号，且每个顶点

的各邻接边的链接顺序，为它所邻接到的顶点序号由小到大的顺序。）

（2） 从顶点1开始，深度优先遍历该图所得顶点序列和边的序列；（给出深度优先搜

索树）

（3） 从顶点1开始，广度优先遍历该图所得顶点序列和边的序列。（给出广度优先搜

索树）

7.3

已知如图7.31所示的AOE-网，试求：

（1） 每个事件的最早发生时间和最晚发生时间； （2） 每个活动的最早开始时间和最晚开始时间； （3） 给出关键路径。

7.4

已知如图7.30所示的有向网，试利用Dijkstra算法求顶点1到其余顶点的最短路径，

并给出算法执行过程中各步的状态。

7.5

编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。

Status Build_AdjList(ALGraph &G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表 {

InitALGraph(G); scanf(\

if(v<0) return ERROR; //顶点数不能为负 G.vexnum=v; scanf(\

if(a<0) return ERROR; //边数不能为负 G.arcnum=a;

for(m=0;m

G.vertices[m].data=getchar(); //输入各顶点的符号 for(m=1;m<=a;m++) {

t=getchar();h=getchar(); //t为弧尾,h为弧头 if((i=LocateVex(G,t))<0) return ERROR;

if((j=LocateVex(G,h))<0) return ERROR; //顶点未找到 p=(ArcNode*)malloc(sizeof(ArcNode));

if(!G.vertices.[i].firstarc) G.vertices[i].firstarc=p; else {

for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc); q->nextarc=p; }

p->adjvex=j;p->nextarc=NULL; }//while return OK;

}//Build_AdjList

7.6

试在邻接矩阵存储结构上实现图的基本操作：InsertVertex(G,v); InsertArc(G, v, w);

DeleteVertex(G,v)和DeleteArc(G, v, w)。

//本题中的图G均为有向无权图,其余情况容易由此写出

Status Insert_Vex(MGraph &G, char v)//在邻接矩阵表示的图G上插入顶点v {

if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE; G.vexs[++G.vexnum]=v; return OK; }//Insert_Vex

Status Insert_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上插入边(v,w) {

if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(i==j) return ERROR; if(!G.arcs[i][j].adj) {

G.arcs[i][j].adj=1; G.arcnum++; }

return OK; }//Insert_Arc

Status Delete_Vex(MGraph &G,char v)//在邻接矩阵表示的图G上删除顶点v {

n=G.vexnum;

if((m=LocateVex(G,v))<0) return ERROR;

G.vexs[m]<->G.vexs[n]; //将待删除顶点交换到最后一个顶点 for(i=0;i

G.arcs[i][m]=G.arcs[i][n];

G.arcs[m][i]=G.arcs[n][i]; //将边的关系随之交换 }

G.arcs[m][m].adj=0; G.vexnum--; return OK; }//Delete_Vex

分析:如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂,而伴随着大量元素的移动,时间复杂度也会大大增加.

Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上删除边(v,w) {

if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(G.arcs[i][j].adj) {

G.arcs[i][j].adj=0; G.arcnum--; }

return OK; }//Delete_Arc

7.7

试对邻接表存储结构重做题6。

//为节省篇幅,本题只给出Insert_Arc算法.其余算法请自行写出.

Status Insert_Arc(ALGraph &G,char v,char w)//在邻接表表示的图G上插入边(v,w) {

if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j;p->nextarc=NULL;

if(!G.vertices[i].firstarc) G.vertices[i].firstarc=p; else {

for(q=G.vertices[i].firstarc;q->q->nextarc;q=q->nextarc) if(q->adjvex==j) return ERROR; //边已经存在 q->nextarc=p; }

G.arcnum++; return OK; }//Insert_Arc

7.8

试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中，是否存在由顶点vi到顶点vj的路径（i≠j）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。

int visited[MAXSIZE]; //指示顶点是否在当前路径上

int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0 {

if(i==j) return 1; //i就是j else {

visited[i]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) {

k=p->adjvex;

if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径 }//for

}//else

}//exist_path_DFS

7.9

同上题要求。试基于图的广度优先搜索策略写一算法。

int exist_path_BFS(ALGraph G,int i,int j)//广度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0 {

int visited[MAXSIZE]; InitQueue(Q); EnQueue(Q,i);

while(!QueueEmpty(Q)) {

DeQueue(Q,u); visited[u]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) {

k=p->adjvex; if(k==j) return 1;

if(!visited[k]) EnQueue(Q,k); }//for }//while return 0;

}//exist_path_BFS

7.10

试利用栈的基本操作，编写按深度优先策略遍历一个强连通图的、非递归形式的算法。算法中不规定具体的存储结构，而将图Graph看成是一种抽象数据类型。

void STraverse_Nonrecursive(Graph G)//非递归遍历强连通图G {

int visited[MAXSIZE]; InitStack(S);

Push(S,GetVex(S,1)); //将第一个顶点入栈 visit(1); visited=1;

while(!StackEmpty(S)) {

while(Gettop(S,i)&&i) {

j=FirstAdjVex(G,i); if(j&&!visited[j]) {

visit(j);

visited[j]=1;

Push(S,j); //向左走到尽头 }

}//while

if(!StackEmpty(S)) {

Pop(S,j); Gettop(S,i);

k=NextAdjVex(G,i,j); //向右走一步 if(k&&!visited[k]) {

visit(k); visited[k]=1; Push(S,k); } }//if }//while

}//Straverse_Nonrecursive

分析:本算法的基本思想与二叉树的先序遍历非递归算法相同,请参考6.37.由于是强连通图,所以从第一个结点出发一定能够访问到所有结点.

7.11

采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径（指顶点序列中不含有重现的顶点）的算法。

[提示]：利用深度搜索，增设一个深度参数，深度超过k 则停止对该结点的搜索。

int visited[MAXSIZE];

int exist_path_len(ALGraph G,int i,int j,int k)//判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径 {

if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求 else if(k>0) {

visited[i]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) {

l=p->adjvex; if(!visited[l])

if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一 }//for

visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中 }//else

return 0; //没找到 }//exist_path_len

7.12

下图是带权的有向图G的邻接表表示法。从结点V1出发，深度遍历图G所得结点序列为（ A ），广度遍历图G所得结点序列为（ B ）；G的一个拓扑序列是（ C ）；从结点V1到结点V8的最短路径为（ D ）；从结点V1到结点V8的关键路径为（ E ）。

其中A、B、C的选择有：

① V1,V2,V3,V4,V5,V6,V7,V8 ② V1,V2,V4,V6,V5,V3,V7,V8 ③ V1,V2,V4,V6,V3,V5,V7,V8 ④ V1,V2,V4,V6,V7,V3,V5,V8 ⑤ V1,V2,V3,V8,V4,V5,V6,V7 ⑥ V1,V2,V3,V8,V4,V5,V7,V6 ⑦ V1,V2,V3,V8,V5,V7,V4,V6 D、E的选择有：

① V1,V2,V4,V5,V3,V8 ② V1,V6,V5,V3,V8 ③ V1,V6,V7,V8

V1,V2,V5,V7,V8 1 6 0 v1 ④ 3 1 4 6 5 50 ∧ 3 11 ∧

1 2 v2 v3 v4 v5 v6 v7 v8 ∧ 2 43 7 8 ∧ 4 12 ∧ 2 38 7 20 ∧ 题12图 4 1 3 4 5 6 24 ∧ 6 12 ∧ 6 7 7.13

已知一棵以二叉链表作存储结构的二叉树，试编写按层次顺序（同一层自左至右）遍历二叉树的算法。

void LayerOrder(Bitree T)//层序遍历二叉树 {

InitQueue(Q); //建立工作队列 EnQueue(Q,T);

while(!QueueEmpty(Q)) {

DeQueue(Q,p); visit(p);

if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); }

}//LayerOrder

第八章 查找

8.1 若对大小均为n的有序的顺序表和无序的顺序表分别进行查找，试在下列三种情况下分别讨论两者在等概率时的平均查找长度是否相同？

（1） 查找不成功，即表中没有关键字等于给定值K的记录。 （2） 查找成功，且表中只有一个关键字等于给定值K的记录。

（3） 查找成功，且表中有若干个关键字等于给定值K的记录，一次查找要求找出

所有记录。

[提示]：均用顺序查找法。

8.2 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查

找长度。

[提示]：根据P.191 ASL定义计算平均查找长度。

8.3 试推导含12个结点的平衡二叉树的最大深度并画出一棵这样的树。

[提示]：沿最左分支生长，前提是：其任一祖先的右分支与左分支等深，如不等深，则先生长右分支，而生长右分支的前提是：其任一祖先的左分支与右分支等深，如不等深，则先生长左分支，如此交互考虑，逐步生长，直到12个结点。

8.4 试从空树开始，画出按以下次序向2-3树，即3阶B-树中插入关键码的建树过程：20，

30，50，52，60，68，70。如果此后删除50和68，画出每一步执行后2-3树的状态。

8.5 选取哈希函数H(k)=(3k)，用线性探测再散列法处理冲突。试在0～10的散列地址

空间中，对关键字序列（22，41，53，46，30，13，01，67）构造哈希表，并求等概率情况下查找成功与不成功时的平均查找长度。 [提示]：平均查找长度参考P.225。

0 22 1

1

2 41 1

3 30 2

4 01 2

5 53 1

6 46 1

7 13 2

8 67 6

9

10

ASLsucc = (1×4 + 2×3 + 6) / 8 = 2

ASLunsucc = ( 2 + 1 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 1 ) / 11 = 40 / 11

8.6 试为下列关键字建立一个装载因子不小于0.75的哈希表，并计算你所构造的哈希表的

平均查找长度。

（ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG，CHANG，CHAO，YANG，JIN） [提示]：（1）由装填因子求出表长，（2）可利用字母序号设计哈希函数， （3）确定解决冲突的方法。

8.7 试编写利用折半查找确定记录所在块的分块查找算法。

8.8 试写一个判别给定二叉树是否为二叉排序树的算法。设此二叉树以二叉链表作存储结

构，且树中结点的关键字均不同。 [提示]：检验中序遍历序列是否递增有序？

[方法1]：用非递归中序遍历算法，设双指针pre, p 一旦pre->data > p->data 则返回假

[方法2]：用递归中序遍历算法，设全局指针pre，（参中序线索化算法） 一旦pre->data > p->data 则返回假 [方法3]：用递归（中序或后序）算法

（1）空树是（2）单根树是（3）左递归真（4）右递归真 （5）左子树的右端小于根（6）右子树的左端大于根

int last=0,flag=1;

int Is_BSTree(Bitree T)//判断二叉树T是否二叉排序树,是则返回1,否则返回0 {

if(T->lchild&&flag) Is_BSTree(T->lchild); if(T->datadata;

if(T->rchild&&flag) Is_BSTree(T->rchild); return flag; }//Is_BSTree

8.9 编写算法，求出指定结点在给定的二叉排序树中所在的层数。

8.10 编写算法，在给定的二叉排序树上找出任意两个不同结点的最近公共祖先（若在两结点A、B中，A是B的祖先，则认为A是A、B的最近公共祖先）。 [提示]： （1） 假设A<=B， （2） 从根开始，左走或右走，直到A在左（或根），B在右（或根）。

8.11 编写一个函数，利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序性。 [提示]：（1）表中已经有x，（2）表中没有x 参P. 231

8.12 已知长度为12的表：

（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）。

（1） 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的

二叉排序树并求其等概率的情况下查找成功的平均查找长度。 （2） 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折

半查找时查找成功的平均查找长度。 （3） 按表中元素的顺序依次构造一棵平衡二叉排序树，并求其等概率的情况下查找

成功的平均查找长度。

[提示]：画出判定树或排序树，根据P.191 ASL定义计算平均查找长度。

8.13 含有9个叶子结点的3阶B-树中至少有多少个非叶子结点？含有10个叶子结点的3阶B-树中至少有多少个非叶子结点？ [提示]：叶子结点对应空指针。

8.14 写一时间复杂度为O(log2n + m)的算法，删除二叉排序树中所有关键字不小于x的结点，并释放结点空间。其中n为树中的结点个数，m为被删除的结点个数。 [提示]： （1） p=root （2） 如果p->key大于、等于x，则删除p->rchild和p， （3） 左走一步，转（2） （4） 如果p->key小于x，则反复右走， （5） 转（2） （6） 直到p==NULL

void Delete_NLT(BiTree &T,int x)//删除二叉排序树T中所有不小于x元素结点,并释放空间 {

if(T->rchild) Delete_NLT(T->rchild,x);

本文来源：https://www.bwwdw.com/article/t1kg.html