严蔚敏++数据结构习题集答案

第二章 习题与解答

一 判断题

1．线性表的逻辑顺序与存储顺序总是一致的。 2．顺序存储的线性表可以按序号随机存取。

3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。

4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。

5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 7．线性表的链式存储结构优于顺序存储结构。

8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。

10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

二 单选题 (请从下列A，B，C，D选项中选择一项)

1．线性表是( ) 。

(A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。

2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（ ）个元素。

(A) n/2 (B) n+1/2 (C) n -1/2 (D) n

3．线性表采用链式存储时，其地址( ) 。

(A) 必须是连续的； (B) 部分地址必须是连续的； (C) 一定是不连续的； (D) 连续与否均可以。

4．用链表表示线性表的优点是（ ）。

(A)便于随机存取

(B)花费的存储空间较顺序存储少 (C)便于插入和删除

(D)数据元素的物理顺序与逻辑顺序相同

5． 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采

用( )存储方式最节省运算时间。 (A)单链表 (B)双链表 (C)单循环链表

(D)带头结点的双循环链表

6． 循环链表的主要优点是( ) 。

(A)不在需要头指针了

(B)已知某个结点的位置后，能够容易找到他的直接前趋 (C)在进行插入、删除运算时，能更好的保证链表不断开 (D)从表中的任意结点出发都能扫描到整个链表

7． 下面关于线性表的叙述错误的是( )。

(A) 线性表采用顺序存储，必须占用一片地址连续的单元； (B) 线性表采用顺序存储，便于进行插入和删除操作； (C) 线性表采用链式存储，不必占用一片地址连续的单元； (D) 线性表采用链式存储，不便于进行插入和删除操作；

8． 单链表中，增加一个头结点的目的是为了（ ）。

(A) 使单链表至少有一个结点 (B)标识表结点中首结点的位置

（C）方便运算的实现 (D) 说明单链表是线性表的链式存储

9． 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则

采用（ ）存储方式最节省运算时间。

(A) 单链表 (B) 仅有头指针的单循环链表 (C) 双链表 (D) 仅有尾指针的单循环链表 10． 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）

存储方式最节省运算时间（ ）。 (A) 单链表 (B) 顺序表 (C) 双链表 (D) 单循环链表

三 填空题

1．带头结点的单链表H为空的条件是__________________。

1． 非空单循环链表L中*p是尾结点的条件是__________________。

3．在一个单链表中p所指结点之后插入一个由指针f所指结点，应执行s->next=________;和p->next=_____________的操作。

4．在一个单链表中p所指结点之前插入一个由指针f所指结点，可执行以下操作：

s->next=________; p->next=s; t=p->data;

p->data=___________; s->data=___________;

5．在顺序表中做插入操作时首先检查_________________。

四 算法设计题

1． 设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。试写一算法，将x 插

入到线性表的适当位置上，以保持线性表的有序性。并且分析算法的时间复杂度。 2． 已知一顺序表A，其元素值非递减有序排列，编写一个函数删除顺序表中多余的值相同

的元素。

3． 编写一个函数，从一给定的顺序表A中删除值在x~y(x<=y)之间的所有元素，要求以较

高的效率来实现。

提示：可以先将顺序表中所有值在x~y之间的元素置成一个特殊的值，并不立即删除它们，然后从最后向前依次扫描，发现具有特殊值的元素后，移动其后面的元素将其删除掉。

4． 线性表中有n个元素，每个元素是一个字符，现存于向量R[n]中，试写一算法，使R中

的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间，元素移动次数最小。（研54） 5． 线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前m个元素

和后n个元素进行整体互换。即将线性表

（a1, a2, … , am, b1, b2, … , bn） 改变为： （b1, b2, … , bn , a1, a2, … , am）。

6． 已知带头结点的单链表L中的结点是按整数值递增排列的，试写一算法，将值为x 的

结点插入到表L中，使得L仍然有序。并且分析算法的时间复杂度。 7． 假设有两个已排序的单链表A和B，编写一个函数将他们合并成一个链表C而不改变其

排序性。

8． 假设长度大于1的循环单链表中，既无头结点也无头指针，p为指向该链表中某一结点

的指针，编写一个函数删除该结点的前趋结点。

9． 已知两个单链表A和B分别表示两个集合，其元素递增排列，编写一个函数求出A和

B的交集C，要求C同样以元素递增的单链表形式存储。 10． 设有一个双向链表，每个结点中除有prior、data和next域外，还有一个访问频度

freq域，在链表被起用之前，该域其值初始化为零。每当在链表进行一次Locata(L,x)运算后，令值为x的结点中的freq域增1，并调整表中结点的次序，使其按访问频度的递减序列排列，以便使频繁访问的结点总是靠近表头。试写一个算法满足上述要求的Locata(L,x)算法。

五 上机实习题目

1． Josephu 问题

Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。 提示：用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。 2． 一元多项式的相加 提示：

（1） 一元多项式的表示问题：对于任意一元多项式：

Pn(x)= P0+ P1X1+ P2X2+ … + PiXi+ … + PnXn

可以抽象为一个由“系数-指数”对构成的线性表，且线性表中各元素的指数项是递增的：

P=( ( P0,0), ( P1,1), ( P2,2), … , ( Pn,n) )

(2 ) 用一个单链表表示上述线性表，结点结构为：

typedef sturct node

{ float coef; /*系数域*/ coef exp next int exp; /*指数域*/

struct node *next; /*指针域*/

} Ploy Node;

约瑟夫环问题

约瑟夫环问题：设编号为1，2，3，??，n的n(n>0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。

源程序代码：（在Tubro C 2.0测试通过） #include #include

struct node {

int number; /* 人的序号 */ int cipher; /* 密码 */

struct node *next; /* 指向下一个节点的指针 */ };

struct node *CreatList(int num) /* 建立循环链表 */ {

int i;

struct node *ptr1,*head;

if((ptr1=(struct node *)malloc(sizeof(struct node)))==NULL) {

perror(\ return ptr1; }

head=ptr1;

ptr1->next=head; for(i=1;i

if((ptr1->next=(struct node *)malloc(sizeof(struct node)))==NULL) {

perror(\ ptr1->next=head; return head; }

ptr1=ptr1->next; ptr1->next=head; }

return head; }

main() {

int i,n=30,m; /* 人数n为30个 */ struct node *head,*ptr; randomize();

head=CreatList(n); for(i=1;i<=30;i++) {

head->number=i; head->cipher=rand(); head=head->next; }

m=rand(); /* m取随机数 */

i=0; /* 因为我没办法删除head指向的节点，只会删除head的下一节点，所以只能从0数起。*/

while(head->next!=head) /* 当剩下最后一个人时，退出循环 */ {

if(i==m) {

ptr=head->next; /* ptr记录数到m的那个人的位置 */ printf(\ printf(\

m=ptr->cipher; /* 让m等于数到m的人的密码 */

head->next=ptr->next; /* 让ptr从链表中脱节，将前后两个节点连接起来 */ head=hea/d->next; /* head移向后一个节点 */ free(ptr); /* 释放ptr指向的内存 */

i=0; /* 将i重新置为0，从0再开始数 */ } else {

head=head->next; i++; } }

printf(\ printf(\ free(head); /* 让最后一个人也出列 */ }

第三章 习题

一、 基本题

1．填空：线性表、栈和队列都是_____结构，可以在线性表的_____位置插入和删除元素，对于栈只能在_______位置插入和删除元素，对于队只能在______位置插入和______位置删除元素。

2. 栈和队列数据结构的特点，什么情况下用到栈，什么情况下用到队列？

3．设有编号为1，2，3，4的四辆车，顺序进入一个栈式结构的站台，试写出这四辆车开出车站的所有可能的顺序（每辆车可能入站，可能不入站，时间也可能不等）。

4．试证明：若借助栈由输入序列1，2，… ，n得到输出序列为p1p2…pn (它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i

二、 设计算法题

1． 假设称正读和反读都相同的字符序列为“回文”，例如，“abcddcba”、 “qwerewq”是

回文，“ashgash”不是回文。是写一个算法判断读入的一个以‘@’为结束符的字符序列是否为回文。

2． 设以数组se[m]存放循环队列的元素，同时设变量rear 和front分别作为队头队尾指针，

且队头指针指向队头前一个位置，写出这样设计的循环队列入队出队的算法。 3． 假设以数组se[m]存放循环队列的元素，同时设变量rear 和num分别作为队尾指针和队

中元素个数记录，试给出判别此循环队列的队满条件，并写出相应入队和出队的算法。 4． 假设以带头结点的循环链表表示一个队列，并且只设一个队尾指针指向尾元素结点（注

意不设头指针），试写出相应的置空队、入队、出队的算法。 5． 设计一个算法判别一个算术表达式的圆括号是否正确配对。 6． 写一个算法，借助于栈将一个单链表置逆。

7．两个栈共享向量空间v[m]，它们的栈底分别设在向量的两端，每个元素占一个分量，试写出两个栈公用的栈操作算法：push(i,x)、pop(i)和top(i)，i=0和1 ,用以指示栈号。

三、 实验题目

1． 背包问题的求解：

假设有一个能装入总体积为T的背包和n件体积分别为w1 , w2 , … , wn 的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1 +w2 + … + wn=T，要求找出所有满足上述条件的解。例如：当T=10，各件物品的体积{1，8，4，3，5，2}时，可找到下列4组

解：（1，4，3，2）

（1，4，5） （8，2） （3，5，2）。

提示：可利用回溯法的设计思想来解决背包问题。首先将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i 件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入背包的那件物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，，直至求得满足条件的解，或者无解。

由于回溯求解的规则规则是“后进先出”因此自然要用到栈。

2． 模拟停车厂管理的问题。

设停车厂只有一个可停放几辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达的先后顺序依次排列，若车场内已停满几辆汽车，则后来的汽车只能在门外的便道上等候，一旦停车场内有车开走，则排在便道上的第一辆车即可进入；当停车场内某辆车要离开时，由于停车场是狭长的通道，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门后，为它让路的车辆再按原次序进入车场。在这里假设汽车不能从便道上开走。试设计一个停车场管理程序。

第四章习题

算法设计题

1．利用C的库函数strlen,strcpy和strcat写一个算法void StrInsert(char *S,char *T,int t) ，将串T插入到S的第i个位置上。若i大于S的长度，则插入不执行。

2．利用C的库函数strlen,strcpy（或strncpy）写一个算法void StrDelete(char *S,int t,int m) ，删除串S中从位置I开始的连续的m个字符。若i≥strlen(S)，则没有字符被删除；若i+m≥strlen(S)，则将S中从位置i开始直至末尾的字符均被删去。

3．采用顺序结构存储串，编写一个函数，求串和串的一个最长的公共子串。

4．采用顺序存储结构存储串，编写一个函数计算一个子串在一个字符串中出现的次数，如果该子串不出现则为0。

第五章习题

一、单项选择题

1. 二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范 围从0到8，列下标j的范围从1到10，则存放M至少需要（1）个字节；M的第8列和第5行共占（2）个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的（3）元素的起始地址一致。（） （1） A.90 B.180 C.240 D.540

（2） A.108 B.114 C.54 D.60

（3） A.M[8][5] B.M[3][10] C.M[5][8] D.M[0][9]

2. 二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范 围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存储时元素（1）的起始地址相同。（）

A.m[2][4] B.M[3][4] C.M[3][5] D.M[4][4]

3. 数组A中，每个元素A的存储占3个单元，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是（1），若该数组按行存放时，元素A[8][5]的起始地址是（2），若该数组按列存放时，元素A[8][5]的起始地址是（３）。

（1） A. 80 B.100 C.240 D.270

（2） A.SA+141 B.SA+144 C.SA+222 D.SA+225 （3） A.SA+141 B.SA+180 C.SA+222 D.SA+225

4. 稀疏矩阵一般的压缩存储方法有两种，即（） A.二维数组和三维数组 B. 三元组和散列 C.三元组和十字链表 D. 散列和十字链表

5.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（） A.正确 B.错误

6.假设按行优先存储整数数组A[9][3][5][8]时，第一个元素的字节地址时１００，每个整数占４个字节。问下列元素的存储地址是什么。

(1) a0000 (2)a1111 (3)a3125 (4)a8247

7.设有三对角矩阵An×n，将其三条对角线上的元素存于数组B[3][n]中，使得元素B[u][v]=aij，试推倒出从（i,j）到 (u,v)的下标变换公式。

8.假设一个准对角矩阵：

a11 a12

a21 a22

a33 a34

a43 a44

…. aij a2m-1,2m-1 a2m-1,2m a2m,2m-1 a2m,2m

按以下方式存储于一维数组B[4m]中: 0 1 2 3 4 5 6 … k … 4m-1 4m A11 a12 a21 a22 a33 a34 a43 … aij … a2m-1,2m a2m,2m-1 a2m,2m

写出由一对下标（i,j）求k的转换公式。

9.画出下列广义表的存储结构式意图。

（１） A=((a,b,c),d,(a,b,c)) （２） B=(a,(b,(c,d),e),f)

二、算法设计

1．对于二维数组A[m][n],其中m<=80,n<=80，先读入m,n，然后读该数组的全部元素，对如下三种情况分别编写相应函数： (1)求数组A靠边元素之和

(2)求从A[0][0]开始的互不相邻的各元素之和

(3)当m=n时，分别求两条对角线的元素之和，否则打印m!=n的信息

2．有数组A[4][4]，把1到16个整数分别按顺序放入A[0][0]...A[0][3]，A[1][0]...A[1][3] A[2][0]...A[2][3]，A[3][0]...A[3][3]中，编写一个函数获取数据并求出两条对角线元素的乘积。

3．只猴子要选大王，选举办法如下：所有猴子按1，2，...，n编号围坐一圈，从第1号开始按1、2、...、m报数，凡报m号的退出圈外，如此循环报数，直到圈内剩下一只猴子时，这只猴子就是大王。n和m由键盘输入，打印出最后剩下的猴子号。编写一个程序实现上述函数。

4．如果矩阵A中存在这样的一个元素A[i][j]满足下列条件：A[i][j]是第i行中值最小的元素，且又是第j列中最大的元素，则称之为该矩阵的一个马鞍点。编写一个函数计算出m*n的矩阵A的所有马鞍点。

5．现有如下的稀疏矩阵A（如图所示），要求画出以下各种表示方法。 （1）三元组表示法 （2）十字链表法

15 0 0 22 0 -15 0 13 3 0 0 0 0 0 0 -6 0 0 0 0 0 0 0 0 91 0 0 0 0 0

0 0 28 0 0 0

6．假设稀疏矩阵A和B（具有相同的大小m*n）都采用三元组表示，编写一个函数计算C=A+B，要求C也采用三元组表示。

7．假设稀疏矩阵A和B（分别为m*n和n*1矩阵）采用三元组表示，编写一个函数计算C=A*B，要求C也是采用稀疏矩阵的三元组表示。

8．假设稀疏矩阵只存放其非0元素的行号、列号和数值，以一维数组顺次存放，行号为-1结束标志。

例如：如图所示的稀疏矩阵M，则存在一维数组D中： D[0]=1， D[1]=1，D[2]=1，D[3]=1，D[4]=5 D[5]=10，D[6]=3，D[7]=9，D[8]=5，D[9]= -1 M =:

1 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

现有两个如上方法存储的稀疏矩阵A和B，它们均为m行n列，分别存放在数组A和B中，编写求矩阵加法C=A+B的算法，C亦放在数组C中。

９．已知A和B为两个n*n阶的对称矩阵，输入时，对称矩阵只输入下三角形元素，按压缩存储方法存入一维数组A和B中，编写一个计算对称矩阵A和B的乘积的函数。

10．假设L为非递归并且不带共享子表的广义表，设计一个复制广义表L的算法。

同步综合练习及参考答案 （一） 基础知识题 6.1 加设在树中，结点x是结点y的双亲时，用(x,y)来表示树变。已知一棵树边的集合为：{(i,m),(i,n),(b,e),(e,i),(b,d),(a,b),(g,i),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用树形表示法画出此树，并回答下列问题：

（1） 哪个是根结点？ （2） 哪些是叶结点？ （3） 哪个是g的双亲？ （4） 哪些是g的祖先？ （5） 哪些是g的孩子？ （6） 哪些是e的子孙？

（7） 哪些是e的兄弟？哪些是f的兄弟？ （8） 结点b和n的层次各是多少？ （9） 树的深度是多少？

（10） 以结点c为根的子树的深度是多少？ （11） 树的度数是多少？

解：

（1） a是根结点。

（2） m,n,j,k,l是叶结点。 （3） c是g的双亲。 （4） a,c是g的祖先。 （5） g的孩子是j,k.。 （6） e的子孙是 i,m,n.。

（7） e的兄弟是a,f的兄弟是g。 （8） h,b在第五层。 （9） 树的深度为3。

（10） 以C为根的子树的深度为3。 （11） 树的度数为3。

6．2 一棵度为2的有序属于一棵二叉树有何区别？ 解：

区别：度为2的树有二个分支，没有左右之分；以可二叉树也有两个分支，但有左右之分，且左右不能交换。

6．3 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 解：

3个结点树形态： 3个结点的二叉树：

6．4已知一棵树为m的树中有n1个度为1的结点，n2个度为2的结点，…nm个度为m的结点，问该书中有多少片叶子？ 解：

因为 n1+n2+…+nM+n0+=1+n1+2n2+…+mnM =>n0+=1+n2+…+(m-1)nM

6.5 一个深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序（同层自左至右）从未有过开始对全部结点编号，问：

（1） 各层的结点数目是多少？

（2） 编号为i的结点的双亲结点（若存在）的编号是多少？

（3） 编号为i的结点的第j个孩子结点（若存在）的编号是多少？

（4） 编号为i的结点有右兄弟的条件是什么？其右兄弟的编号是多少？ 解：

（1） Ki-1 （2）

（3） Ki+j-1

（4） (i-1)MOD K<>0 ,i+1

6．6 高度为h的完全二叉树至少有多少个结点？至多有多少个结点？ 解：

至少有：2h-1， 至多有：2h-1

6．7 在具有n个结点的k叉树（k≥2）的k叉树链表表示中，有多少个空指针？ 解：

（k-1）n+1个空指针

6．8 假设二叉树包含的结点数据为1，3，7，2，12。 （1） 画出两棵高度最大的二叉树；

（2） 画出两棵完全二叉树，要求每个双亲结点的值大于其孩子结点的值。 6．9 试找出分别满足下面条件的所有二叉树：

（1）前序序列和中序序列相同； （2）中序序列和后序序列相同； （3）前序序列和后序序列相同； （4）前序、中序、后序序列均相同。 解：

（1） 空二叉树或任一结点均无左子树的非空二叉树

（2） 空二叉树或任一结点均无左子树的非空二叉树 （3） 空二叉树或仅有一个结点的二叉树 （4） 同（3）

6．10 试采用顺序存储方法和链接存储方法分别画出6. 30所示各二叉树的存储结构。 解：①顺序存储：

(a)1 2 φφ 3 φ φ φ φ 4 φ φ φ φ φ φ φ φ φ φ 5

(b)1 φ 2 φ φ 3 φ φ φ φ φ φ φ 4 φ φ φ φ φ φ φ φ φ φ φ φ 5

(c)1 φ 2 φ φ 3 4 φ φ φ φ 5 6 φ φ φ φ φ φ φ φ φ φ φ 7 8 (d)1 2 3 4 φ 5 6 φ 7 φ φ φ φ 8 9 ②连接存储：

6．11 分别写出图6.30所示各二叉树的前序、中序和后序序列。 解：

6．12 若二叉树中个结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列的中序列均能惟一地确定一棵二叉树，但由前序序列和后序序列却不一定能惟一地确定一棵二叉树。

（1） 已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画

出此二叉树。

（2） 已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出

此二叉树。

（3） 已知两棵二叉树前序序列和后序序列均为AB和BA，请画出这两棵不同的二叉树。 解：

6．13 对二叉树中结点进行按层次顺序（每一层自左至右）的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树的层次序列。现已知一棵二叉树的层次序列为ABCDEFGHIJ，中序序列为DBGEHJACIF，请画出该二叉树。 解：

6．14 试画出图6.30所示各二叉树的前序、中序和后序线索树及相应的线索链表。 解：

（以c为例）

① 前序：1 2 3 5 7 8 6 4 ② 前序：1 7 5 8 3 6 2 4

6．15 在何种线索树中，线索对所求指定结点在相应次序下的前趋和后继并无帮助？ 解：

在前序线索树中找某一点的前序前趋以及在后序线索树中寻找某一点的后继，线索并无多大帮助。

6．16 对图6.31所示的森林：

（1） 求各树的前序序列和后序序列： （2） 求森林的前序序列和后序序列： （3） 将此森林转换为相应的二叉树：

（4） 给出（a）所示树的双亲链表表示、孩子链表表示、双亲孩子链表表示及孩子兄

弟链表表示等四种存储结构，并指出哪些存储结构易于求指定结点的祖先，哪些易于求指定结点的后代？

解：

(1) a b c

前序 ABCDEF GHIJK LMPQRNO 后序 BDEFCA IJKHG QRPMNOL (2) 前序： ABCDEFGHIGKLMPQRNO 后序： BDEFCAIJKHGQRPMNOL

(3) 二叉树 (4) 1

① 孩子链表表示发：

② 双亲链表表示发：

结点 0 1 2 3 4 5 6 data A B C D E F parent -1 0 1 1 3 3 3

③ 双亲孩子链表： ④ 孩子兄弟链表表示： ⑤ 易于求祖先：双亲链表面 双亲孩子 ⑥ 易于求后代：孩子链表 双亲孩子

6．17 画出图6.32所示的各二叉树所应的森林

6．18 高度为h的严格二叉树至少有多少个结点？至多有多少个结点？ 解：

最多有2n-1 最少有 2n-1

6．19 在什么样的情况下，等长编码是最优的前缀码？ 解：

当字符集中的各字符使用频率均匀时。 6．20 下属编码哪一组不是前缀码？

{00，01，10，11}，{0，1，00，11}，{0，10，110，111} 解：

因为前缀码中不可能存在一个元素是另一个的前面部分。 所以第二组不是。

6．20 假设用于通信的电子由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中

出现的概率分别为{0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10} （1） 为这8个字母设计哈夫曼编码。

（2） 若用三位二进制数（0~7）对这个8个字母进行等长编码，则哈夫曼编码的平均

码长是等长编码的百分之几？它使电文总长平均压缩多少？

解：

① ②哈夫曼编码码长：

4*0.07+2*0.19+5*0.02+4*0.06+5*0.03+2*0.21+4*0.1=2.71 等长码长： 3

905 平均缩了10%

（二） 算法设计题

6.22 二叉树的遍历算法可写为通用形式。例如，通用的中序遍历为：

void Inorder(BinTree T,void(*Visit)(Datatype x)) { if (T)

{Inorder(T->lchild,Visit); /*遍历左子树*/

Visit(T->data); /*通过函数指针调用它所指的函数来访问结点*/ Inorder(T->rchild,Visit); /*遍历右子树*/ } }

其中Visit是一个函数指针，它指向形如void f（DdataType x）的函数。因此我们可以将访问结点的操作写在函数f中，通过调用语句Inorder（root，f）将f的地址传递给Visit，来执行遍历操作。请写一个打印结点的数据的函数，通过调用上述算法来完成书中6.3节的中序遍历。

解：

#include“stdio.h” #define Null 0

typedef char DataType; typedef struct node {

DataType data;

Struct node lchild,rchild;

}BinTree; BinTree *root; BinTree *Q[100];

BinTree CreateBinTree() /*建立二叉树*/ {

char ch;

int front,rear; BinTree root,s; Root=Null; front=1; rear=0;

ch=getchar(); while(ch!=’#’) {

s=Null;

if(ch!=’@’) {

s=(BinTree*)malloc(sizeof(BinTree)); s->data=ch; s->lchild=Null; s->rchild=Null; }

rear ++; Q[rear]=s;

if(rear==1) root=s; else {

if(s&&Q[front])

if(rear%2==0) Q[front]->lchild=s; else

Q[front]->rchild=s; if(rear%2==1) front++; }

ch=getchar(); }

return root; }

main() {

root=CreateBinTree(); Inorder(root); }

① 中序遍历法之一

Inorder(BinTree *t) {

if(t) {

Inorder(t->lchild); Visit(t->data);

Inorder(t->rchild); } }

Vist(int i) {

printf(“%c”,i); }

② 中序遍历法之二

Inorder(BinTree *t) {

if(t) {

Inorder(t->lchild); printf(“%c”,t->data); Inorder(t->rchild); } }

6.23 以二叉链表为存储结构，分别写出求二叉树结点总数及叶子总数的算法。 解：

① 计算结点总数

int CountNode(BinTree *root) {

int num1,num2;

if(root==Null) return(0);

else if(root->lchild==Null&&rooot->rchild==Null) return(1); else {

num1=CountNode(root->lchild); num2=CountNode(root->rchild); return(num1+num2+1); } }

② 计算叶子总数

int CountLeafs(BinTree *root) {

int num1,num2;

if(root==Null) return(0);

else if(root->lchild==Null&&root->rchild==Null) return(1); else {

num1=CountLeafs(root->lchild); num2=CountLeafs(root->rchild); return(num1+num2);

} }

6.24 以二叉链表为存储结构，分别写出求二叉树高度及宽度的算法。所谓宽度是指在二叉

树的各层上，具有结点数最多的那一层上的结点总数。 解：

① 求树的高度

思想：对非空二叉树，其深度等于左子树的最大深度加1。

Int Depth(BinTree *T) {

int dep1,dep2;

if(T==Null) return(0); else {

dep1=Depth(T->lchild); dep2=Depth(T->rchild);

if(dep1>dep2) return(dep1+1); else return(dep2+1); }

② 求树的宽度

思想：按层遍历二叉树，采用一个队列q，让根结点入队列，最后出队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。 int Width(BinTree *T)

{

int front=-1,rear=-1; /* 队列初始化*／ int flag=0,count=0,p;

/* p用于指向树中层的最右边的结点，标志flag记录层中结点数的最大值。*／if(T!=Null) {

rear++; q[rear]=T; flag=1; p=rear; }

while(front

front++; T=q[front];

if(T->lchild!=Null) {

rear++;

q[rear]=T->lchild; count++; }

if(T->rchild!=Null) {

rear++;

q[rear]=T->rchild; count++; }

if(front==p) /* 当前层已遍历完毕*/ {

if(flag

p=rear; /* p指向下一层最右边的结点*/ }

} /* endwhile*/ return(flag); }

6.25 以二叉链表为存储结构，写一算法交换各结点的左右子树。 解：

思想：借助栈来进行对换。

Swap(BinTree*T) {

BinTree *stack[100], *temp; int top=-1; root=T; if(T!=Null) }

top++;

stack[top]=T; while(top>-1) {

T=stack[top]; top--;

if(T->child!=Null||T->rchild!=Null)

{ /*交换结点的左右指针*/ temp=T->lchild;

T->lchild=T->rchild; T->rchild=temp; }

if(T->lchild!=Null) {

top++;

stack[top]=T->lchild; }

if(T->rchild!=Null) {

top++;

stack[top]=T->rchild; } }

} /*endwhile*/ } /*endif*/

main() {

int I,j,k,l; printf(“\\n”);

root=CreateBinTree(); Inorder(root); i=CountNode(root); j=CountLeafs(root); k=Depth(root); l=Width(root);

printf(“\\nThe Node ’s Number:%d”,i); printf(“\\nThe Leafs’s Number:%d”,j); printf(“\\nThe Depth is:%d”,k); printf(“\\nThe width is:%d”,l); Swap(root);

Printf(“\\nThe swapTree is:”); Inorder(root); } 6．26 以二叉表为存储结构，写一个拷贝二叉表的算法哦（BinTree root,BinTree *newroot）,其中新树的结点是动态申请的，为什么newroot要说明为BinTree形指针的指针？ 解：

CopyTree(BinTree root,BinTree *(newroot)) }

if(root!=Null) {

*newroot=(BinTree *)malloc(sizeof(BinTree)); (*newroot)->data=root->data;

CopyTree(root->lchild,&(*newroot)->lchild); CopyTree(root->rchild,&(*newroot)->rchild); Inorder(*newroot); }

else return(Null); }

main() {

BinTree *newroot; int I,j,k,l; printf(“\\n”);

root=CreateBinTree(); Inorder(root); Printf(“\\n”); /*Swap(root);*/ &(*newroot)=Null;

CopyTree(root,&*newroot); }

6．27 以二叉树表为存储结构，分别写处在二叉树中查找值为x的结点在树中层数的算法。 解：

int h=-1,lh=1,count=0;charx=’c’; /*赋初值*/

Level(BinTree T,int h,int lh) /*求X结点在树只的层树*/ {

if(T==Null)h=0;

else if (T->data==x) {

h=lh; count=h; } else {

h++;

Level(T->lchild,h,lh);

If(h==-1)Level(T->rchild,h,lh);

} }

main() {

BinTree *(*newroot); Printf(“\\n”);

Root=CreateBinTree(); Inorder(root); Printf(“\\n”); Level(root,h,lh); Printf(“%d”,count); }

6.28一棵n个结点的完全二叉树以向量作为存储结构，试写一非递归算法实现对该树的前序遍历。 解：

思想：采用栈，先让跟结点如栈，然后退栈，如有左右孩子，则先让右孩子如栈，然后左孩子如栈，如此反复实现前序遍历。

typedef struct {

int data[100];

int top; }seqstack; seqstack *s;

Perorder(char a[],int n) {

int i=1,count=1; s->top=-1;

if(n==0)return(0); else {

if(I<=n) {

s->top++;

s->data[s->top]=a[I]; }

while(count

printf(“%c”,s->data[s->top]); count++; s->top--;

if(s->data[s->top]);==a[i]) { /*若栈顶结点为a[i]结点，则退栈，保证父结点比孩子结点先退栈 */ printf(“%c”,s->data[s->top]); count++; s->top--; }

if((2*i+1)

i=2*i; s->top++;

s->data[s->top]=a[i+1]; s->top++;

s->data[s->top]=a[i];

}

else if(a*i

{

i=2*i; s->top++;

s->data[s->top]=a[i]; }

else if(i/2%2==1)i=i/2/2+1;

/*父结点没有右兄弟，回到祖父结点大右兄弟*/ else i=i/2+1; /*回到父结点的右兄弟*/ } } } main() {

char A[]=“kognwyuvb”; int n=strlen(A);

s=(seqstack *)malloc(sizeof(seqstack)); printf(“\\n”); Perorder(A,n); }

6．29 以二叉树表为存储结构，写一算法对二叉树进行层次遍历（定义见习题6.13）。提示：应使用队列来保存各层的结点。 解：

void TransLevel(BinTree *T) {

int front=0,rear=0; int p;

if(T!=Null) {

printf(“%c”,T->data); q[rear]=T; rear++; }

while(front

T=q[front]; Front++;

if(T->lchild!=Null) {

printf(“%c”,T->lchild->data); q[rear]=T->lchild; rear++;

}

if(T->rchild!=Null) {

printf(“%c”,T->rchild->dara); q[rear]=T->rchild;

rear++; } }

}

main() {

printf(“\\n”);

root=CreateBinTree(); Inorder(root); Printf(“\\n”); TransLevel(root); }

6．30 以二叉树表为存储结构，写一算法用括号形式（keyLT,RT）打印二叉树，其中key是根结点数据，LT和RT分别是括号形式的左右子树。并且要求：空树不打印任何信息，一给结点x的树打印形式是x，而不应是（x，，）d的形式。 解：

viod Print(BinTree T) /*哟感括号形式打印二叉树*/ {

if(T!=Null) {

if(T->lchild==Null&&T->rchild==Null) /*只有根结点*/ printf(“%c”,T->data);

else /*T->lchild!=Null||T->rchild!=Null*/ {

printf(“(”);

printf(“%c”,T->data);

if(T->lchild->lchild==Null&&T->lchild->rchild==Null) printf(“)”); Print(T->lchild);

if(T->rchild!=Nulll)printf(“,”); printf(“)”); printf(“)”); } } } main() {

printf(“\\n”);

root=CreateBinTree(); Inorder(root); printf(“\\n”); Print(root); }

6.31以线索链表为存储结构，分别写出在前序线索树中查找给定结点*p的后继，以及在后序线索树中查找*p的后序前趋的算法。 解：

① 找结点p的前序后继

BinTheNode * PreorderSuccessor(BinThrNode *p) {

BinThrNode *q;

if(p->rtag==Thread)

q=p->rchild; /*右子树为空*/

else

{ if(p->ltag==list)

q=p->lchild； /*左子树非空*/

if(p->ltag==Thread)

q=p->rchild; /*左子树为空*/

}

return(q); }

②找结点p的后序继

BinTheNode * PostorderSuccssor(BinThrNode *p) {

BinThrNode *q;

if(p->ltag==Thread)

q=p->lchild; /*左子树为空*/ else

{if(p->rtag==list)

q=p->rchild; /*右子树非空*/ if(p->ltag==Thread)

q=p->lchild; /*右子树为空*/ }

return(q); }

/*说明：list\\Thread为特殊标志，其值分别为0与1.*/ 6．32 完成6.6.1 节算法CreateHuffmanTree中调用的三个函数：InputWeight,SelecMin和InitHuffmanTree. 解：

① 初始化

InitHuffmanTree(HuffmanTree T) { int i;

for(i=0;iparent=-1;

T[i]->lchild=-1; T[i]->rchild=-1; T[i]->weigh=0;

} }

② 读入叶子结点权值

InputWeigh(HuffmanTree T)

{ int I;

for(i=0;i

scanf(“%d”,&T[i]->weigh);

}

③ 选出两个权至最小的根结点

SelecMin(HuffmanTree T,i-1,&p1,&p2) int i,p1,p2;

{ int j,small1,small2;

small1=small2=max; /*设max为整型最大值*/

for(j=0;j

if(T[j]->parent==-1)

if(T[j]->weigh

{small2=small1; /*改变最小权、次小权及对应位置*/ small1=t[j]->weigh; p2=p1; p1=j; }

else

if(T[j]->weigh

{small2=T[j]->weigh; /*改变最小权及对应位置*/ p2=j; }

} 6．33 分别写出对文件进行哈夫谩码的算法，以及对编码文件进行解码的算法。为简单起见，可以假设文件存放在一个字符向量。 解：

① 编码算法

设哈夫曼树已求出。

HuffmanCode(code,tree) Codetype code[];

Huffmantype tree[] /*以求出*/ { int I,j,c,p;

codetype cd; /*缓冲区变量*/ for(i=0;istart=n; c=i+1;

p=tyee[i]->parent; while(p!=0) { cd->start=n; c=i+1;

p=tyee[i]->parent; while(p!=0)

{ cd->start--;

if(tree[p-1]->lchild==c)

cd->bit[cd-start]=’0’;/*type[i]是左子树，生成代码为‘0’*/ else

cd->bit[cd->start]=’1’；/*type[i]是右子树，生成代码为‘1’*/

c=p;

p=tree[p-1]->parent; }

code[i]=cd; } } 注：结构体 typedef struct

{ char bit[n]; /*位串*/

int start; /*编码在位串的起始位置*/

char ch; /*字库*/

}codetype;

codetype code[n]; ② 译码算法

Decode(code,tree) Codetype code[]; Huffmantype tree[]; { int I,j,c,p,b;

int endfily=-1; /*电文结束标志*/

i=m; /*从根结点开始往下搜索*/ scanf(“d”，&b); /*读入一个二进制代码*/ while(b!=endfily) { if(b==0)

i=tyee[i]->lchild-1; /*走向左孩子*/ else

i=tyee[i]->rchild-1; /*走向右孩子*/

if(tyee[i].child==0) /*tyee[i]为叶结点*/

{ outchar(code[i]->ch); /*译码，即输出叶结点对应的字符*/ i=m; /*回归根结点*/ P=tyee[p-1]->parent; }

scanf(“%d”,&b); /*读入下一个二进制代码*/

}

if(tyee[i].lchild!=0) /*电文读完但未到叶结点*/

printf(“\\n ERRoR\\n”); /*输出电文有错信息*/

}

同步综合练习及参考答案 （一） 基础知识题

7．1 在图7.23所是的各无向图中：

（1） 找出所有的简单环。

（2） 那些图是连通图？对非连通图给出其连通分量。

（3） 那些图是自由树（或森林）？ //自由树的概念见 7.4节 解：

（1） 简单环 （a）(1 2 3 1)

(b) 无

(c) （1 2 3 1） （2 3 4 2） （1 2 4 3 1） (d) 无

（2） 连通图（a）（c）（d） 非连通图（b）的连通分量为 （3） 自由树 （d）

森林 （b）

7．2 在图7.24所是的有向图中：

（1） 该图是强连通的码？若不是，则给出其强连通分量。 （2） 请给出所有简单路径及有向环。 （3） 请给出每个顶点的度、入度和出度。 （4） 请给出其邻接表、邻接矩阵及逆邻接表。 解：

（1） 图是强连通的。

（2） 所有简单路径（重复环未计算）

（v1）（v2）（v3）（v4）

(v1 v2)(v2 v3)(v3 v1)(v1 v4)(v4 v3)

(v1 v2 v3)(v2 v3 v1)(v3 v1 v4)(v3 v1 v2)(v1 v4 v3)(v4 v3 v1)

（v1 v2 v3 v1）（v2 v3 v1 v4）（v3 v1 v4 v3）（v4 v3 v1 v2） 有向环

（v1 v2 v4 v1）（v4 v1 v4 v4） (3) 各顶点的度、入度、和出度。 (4) ①邻接表

② 邻接矩阵集。 ③ 逆邻接表

7．3 假设图的顶点是A,B,?,请根据下属的邻接矩阵画出相应的无向图或有向图。 解：

7．4 假设一颗完全二叉树包含A,B,?,G第七个结点，写出其邻接表和邻接矩阵。 解：

① 完全二叉树 ② 邻接矩阵 ③ 邻接表

7．5 对n各顶点的无向图和有向图，采用邻接矩阵和邻接表表示，如何判别下列有关问题：

（1） 图中有多少条边？

（2） 任意两个顶点I和j是否有边相连？ （3） 任意一个顶点的度是多少？ 解：

① 对于无向图

（1） 图中边数等于邻接矩阵中1的各数的一半；邻接表中的边表中结点各数的

一半。

（2） 若邻接矩阵中A[i,j]≠0则I和j两个顶点有边相连。

（3） 顶点I的度为第I行中1的个数；邻接表中I的边表结点个数j. ② 对于有向图

（1） 图中边树等于邻接矩阵中的个数；邻接表中的出边表中结点数。 （2） 若邻接矩阵中A[i,j]>0则I和j两个顶点有边相连；

邻结表中I得出边表是否有结点j，决定I和j两个顶点有边相连。

（3）顶点I的度为第I行中1的个数加上第I列中1的个数之和；

邻接表中i得出边表结点个数加上边表中结点I的个数之和。

7．6 n个顶点的连通图至少有几条边？强连通图呢？ 解：

①n个顶点的连通图至少有n-1条边。 ②n个顶点的强连通图至少有n条边。

7．7 DFS和BFS遍历采用什么样的数据结构来暂存顶点？当要求连通图的生成树的高度最小，应采用何种遍历？ 解：

①DFS采用了栈；BFS采用了队列。 ②采用BFS。

7．8画出以顶点v1为初始源点遍历图7。25所示的有向图所得到的DFS和BFS生成森林。 解：

7．9按顺序输入顶点对：（1，2），（1，6），（2，6），（1，4），（6，4），（1，3），（3，4），（6，5），（4，5），（1，5），（3，5），根据第7.2.2节中算法CreateALGraph画出相应的邻接表，并写出在该邻接表上，从顶点4开始搜索所得的DFS和BFS序列，及DFS和BFS生成树。 解：

依题意构造有向图： ①邻接表

②DFS和BFS序列

DFS序列：4 5 3 1 6 2

BFS序列：4 5 3 6 1 2 ③DFS和BFS生成树

DFS生成树 BFS生成树

7.10什么样的图其最小生成树是唯一的？用Prim和Kruskal求最小生成数的时间各为多少？他们分别适合于哪个图？

解：①具有n的结点，n-1条边的连通图其生成树是唯一的。 ② 的结点，e条边的无向连通图求最小生成树的时间分别为

Prim: O(n2); Kruskal:O(e*log2e) ③ Prim适应于稠密图（点少边多）；Kruskal 适应于稀疏图（点多边少）。

7．11 对图7.26所示的连通图，请分别用Pirm和Kruskal 算法构造其最小生成树。 解：

① Pirm算法构造的生成树。 ② Kruskal 算法构造的生成树。

7．12 对图7.27所示的有向网，试利用Dijkstra算法求出从源点1到其它各顶点的最短路径，并写出执行短发过程中扩充红点集的每天次循环状态（类似表7.2）. 解：

7．13 是写出图7.28所示有向图的所有拓扑序列，并指出应用教材中 NonPrefirtTopSort算法求得的是哪个序列，设邻接表的边表结点中的邻接点序号是递增的。 解：

NonPreFirtTopSort算法求得的序列是： V0 V1 V5 V2 V6 V3 V4 其余序列有多种（略）。

7．14 什么样的DAG的拓扑序列是唯一的？ 解：

设DAG中有n个结点，则当DAG中有至少n-1个不同的后继结点且至少有n-1个前缀结点时其拓扑序列是唯一的。

7．15 以V4为源点，给出用DFS搜索7.28的道德你拓扑序列。 V4 V3 V2 V0 V1 V5 V6. （二） 算法设计题

7．16 试在无向图的邻接矩阵和邻接表上实现如下算法： （1） 往图中插入一个顶点 （2） 往图中插入一条边 （3） 删去图中某顶点 （4） 删去图中某条边 解：

（1） 插入给定结点

① 邻接表

viod Inser-ALGraph(ALGraph *G,int k) {

int i; G->n++;

for(i=G->n;i>k;i--)

{

G->adjlist[i].vertex=G->adjlist[i-1].vertex;

G->adjlist[i].firstedge=G->adjlist[i-1].Firstedge; }

G->adjlist[i].vertex=getchar(); G->adjlist[i].firstedge=Null; }

② 邻接矩阵

void Inser-Mgraph (mGraph *G,int k) {int i,j; G->n++;

for(i=G->n;i>k;i--)G->vexs[i]=G->vexs[i-1]; G->cexs[k]=getchar(); for(i=G->n;i>k;i--)

{ for(j=G->n;j>k;j--)

G->e[i][j]=G->e[i-1][j-1]; G->e[i][j]=0;

for(j=k-1;j>=0;j--)

G->e[i][j]=G->e[i-1][j]; }

for(j=G->n;j>=0;j--)G->e[i][j]=0; for(i=k-1;i>=0;j--) { for(j=g->n;j>k;j--)

G->e[i][j]=G->e[i][j-1]; G->e[i][j]=0 } }

⑵插入一条边 ① 邻接表

InsertLAGraph (ALGraph *G,int m,INT n) { EdgeNode *E;

EdgeNode *sm=new EdgeNode; EdgeNode *sn=new Edgenode; Sm->adjvex=n;sm->next=Null; Sn->adjvex=m;sn->next=Null;

for(E=G->adjlist[m].firstedge;E!=NULL;E=E->next) { }

E=sm;

for(E=G->adjlist[n].firstedge;E!=NULL;E=E->next) { } E=sn;

}

② 邻接矩阵

void InsertLMGraph(mGraph *G,int m,int n) { G->e[m][n]=1;

}

（3）删除某结点 ① 邻接表

void DelVALGraph(ALGraph *g,int k) { int I; G->n--;

EdgeNode *e *s;

for(E=G->adjlist[k].firstdge;E!=NULL;E=E->next)

{ for (s=G->adjlist[E->adjvxe].firstedge;E!=NULL;E->E->next) if(s->adjvex==k) {s=s->next;break;} }

for(i=k;in;i++)

{ G->adjlist[i].vertex=G->adjlist[i+1].vextex;

G->adjlist[i].first[i].firstedge=G->adjlist[i+1].firstedge;

}

}

② 邻接矩阵

void delvMGraph(mGraph *G,int k) {int i,j; G->n--;

for(i=k;i<=g->n;i++) G->vexs[i]=G->vexs[i+1]; for(i=0;i

for(j=k;j<=n;j++) G->e[i][j]=G->e[i][j];

for(i=k;i<=G->n;i++)

{for(j=0;je[i][j]=G->e[i+1][j]; for(j=k;j<=n;j++) G->e[i][j]=G->e[i+1][j]; } }

(4)删除某条边 ① 邻接表

void dellALGraph(ALGraph *G,int m,int n) {EdgeNode *s;

for(S=G->adjlist[m].firstedge; s->adjvex!=k;s=s->next) s=s->next; for(s=G->adjlist[n].firstedge;

s->adjvex!=k;s=s->next) s=s->next;

}

②邻接矩阵

void InsertLMGraph(mGraph *G,int m,int n) {G->e[m][n]=0; G->e[n][m]=0; }

7.17 下面的伪代码是一个广度优先搜索算法,试以图7.29中的V4为源点执行该算法,请回答下述问题:

(1) 对图中顶点Vn+1,它需要入队多少次?它被重复访问多少次? (2) 若要避免重复访问同一个顶点的错误,应如何修改此算法?

Void BFS(ALGraph *G,int k)

{//以下省略局部变量的说明,visited各分量初值为假

InitQueue(&Q); //置空队列 EnQueue(&Q,k); //k入队 While(!QueueEmpty(&Q))

{I=DeQueue(&Q); //vi出队

visited[I]=true //置访问标记// printf(“%c”,G->adjilist[i],vertes); //访问j

for(p=G->adjilist[i],firstedge;p;p=p->adjves=j)//依次搜索vi的邻接点vj (不妨设p->adjves=j)

if(!Visited[p->adjves]) //若vj未被访问 EnQueue(&Q,p->adjves); //vj入队 } //endwhile } //BFS

解：

对图中顶点vn+1,它需入队n次？它被重复访问n-1次。 若要避免重复访问同一个顶点的错误，应修改算法如下： Void BFS(ALGraph*G,int K)

{ /*以下省略局部变量得说明，visited各分量初值为假*/ InitQueue(&Q); /*置空队列*/

EnQueue(&Q,k); /*k队列*/ While(!QueueEmpty(&Q))

{I=DeQueue(&Q); /*vi出队*/ visited[I]=true /*置访问标记*/ printf(“%c”,G->adjilist[i],vertes);/*访问vi*/

for(p=G->adjlist[i],firstedge;p;p->adjves=j)

/*依次搜索vi的邻接点vj（不妨设p->adjves=j）*/ if(!Vvisit[p->adjves]) /*若vj未访问过*/ {

EnQueue(&Q,p->adjves); /*/vj入队*/ Visited[p->adjvex]=TRUE; }

} /*endwhile*/ } /*BFS*/

7.18 试以邻接表和邻接矩阵为存储结构，分别写出基于DFS和BFS遍历的算法来判别顶点vi和vj(I<>j)之间是否有路径。 解：

/*基于邻接表方式*/ /*所有数据类型*/ #define maxvn 10 typedef struct node { int vertex; int vertex;

setuct node *list; } vertexNode

vertexNode *head[maxvn];

bool JUDGE(vertexNode *adjl[maxvn],int n,int j);

/*深度优先搜索判别n个顶点的有向图中顶点I到顶点j是否存在路径*/ { int stack[maxvn]; bool visit[maxvm]; int top,k; vertexNODE *p; bool yes;

for(k=1;k<=n;k++) visit[k]=false; top=1;

stack[top]=i; visit[i]=True; yes=false; do{

p=adjl[stack[top]];

while(!p=NULL&&visit[p->vertex]p=p->link); if(p==NULL)

top=top-1; /*p之后无邻接结点，退栈*/ else

{i=p->vertex; /*p指向的顶点未访问*/ if(i==j) yes=true; else

{ visit[i]=true; top=top+1; stack[top]=i;

}

}while(top1=0&&!yes); return(yes); }

7．19 试分别写出求DFS和BFS生成树（或生成森林）的算法，要求打印出所有的树边。 解：

①/*以Vi为树根，对邻接矩阵表示的图G进行DFS搜索*/

void DFSM(Mgraph *G,int ) { int j;

printf(“visit vertex:%c”,G->vexs[i]); visitcd[i]=True; for(j=0;j<=G->n;j++)

if(G->edges[i][j]==1&&!visit[j]) { print(“edye:%d?%d\\n”,i,j); DESM(G,j); } }

②/*以VI为树根，对邻接矩阵表示的图G进行DFS搜索*/ void DFSM(Mgraph *G,int k) { int i,j;

SETNULL(Q); /*置空队Q*/ Printf(‘%/“，G.vexs[k]);

Visited[k]=True; /*标志Vk+1已经访问过*/ ENQUEUE(Q,k); /* 已经访问过的顶点如队列*/ While(!EMPTY(Q)) /*队列非空时执行*/

{i=DEQUEUE(Q); /*队头元素序号出队列*/ for(j=0;j

{print(“edye:%d?%d\\n”,i,j); /*访问过的边*/ print(“%c\\n”,G,vexs[j]); visited[j]=True;

ENQUEUE(Q,j); /*访问过的顶点如队*/ } } }

7.20写一算法切连通分量的个数并输出各连通分量的顶点集。 解：

/*修改DFS函数，每当使visited[i]=true时打印printf（“%D”，i）；可输出各连通分量顶点集。*/

{int i; int m=0;

for(i=0;i

visited[i]=False; for(i=0;i

printf(“comp end\\n”); }

printf(“共有m个连通分量”); }

7.21 设图中各边上的权值均相等，是以邻接矩阵和邻接表为存储结构，分别写出算法：

（1） 求顶点 Vi到Vj(i<>j)顶点的最短路径； （2） 求源点Vi 到其余各顶点的最短路径。

要求输出路径上的所有顶点（提示：利用BFS遍历的思想） 解：

利用BFS的遍历思想，同时构造一棵树，使每个孩子结点均指向双亲，当搜索到目标结点时，则从目标回溯到根结点即可，具体算法如下：

typedef struct node { int data;

struct node *parent; }Tree;

void Path(ALGraph,*G,int i,int j) /*以邻接点存储*/ { int k; /*求vi到vj的最短路径*/ CirQueue Q; /*将DataType改为 int */ EdyeNode P;

InitQueue(&Q) /*队列初始化*/ Visit[i]=TRVE; /*源点*/

S=(tree)mallo((sizeof(Tree)); 新建一个结点 s->data=i /*树根*/ s->patent=NULL;

EnQueue(&Q,i); /*入队列*/ While(!Queue Empty(&Q)) { k=DeQueue(&Q);

p=G->dajlist[k]->firstdeye; while(P)

{ if(! Visited[p->adjvex]) { visited[p->adjvex]=TRVE;

*S=(Tree*)mallo((sizeof(Tree)); /*新结点*/ s->data=p->adkvex; s->parent->data=k; EnQueue(&Q,p->adjvex);

} /*end if */

if(p->adjvex==j)bread; /*已搜索到j点*/ p-=p->next;

} /*end if */

if(p->adjvex==j)break; /*已搜索到j点，结束搜索*/ } /*end if */

while(s!=NULL) /*此时打印出来的路径为反序*/ { printf(“%d”,G->adjlist[s->data]->vertex) s=s->parent; }

（2）求源点到其余各顶点最短路径，则可调用上面算法。

Void PathALL(ALGraph *G.int i) {int j,

for(j=0;fn;j++) if(j!=i) path(G,i,j); }

对于用邻接矩阵存储的图:

(1) 求顶点vi到顶点vj(i≠j)最短路径 算法思想，采用弗洛伊德算法，可表示为

A[K][i,j]=Min(A k-1[i,j],A k-1[i,k]+A k-1[k.j])(1<=i<=n,1<=j<=n)

其中k表示第k次迭代运算。A[0][i,j]=A[i,j]. #define MAXVEX 100

void floyd(a,c,n) /*c为已知邻接矩阵，a为待求矩阵，n为源点数*/ int a[MAXVEX][MAXVEX] c[MAXVEX][MAXVEX],n; {int i,j,k;

for(i=1;i<=n;i++) for(j=1;j<=n;j++) a[i][j]=c[i][j];

for(i=1;i<=n;i++) a[i][j]=0; for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++)

if(a[i][k]+a[k][j]

}

7.22以邻接表为存储结构，写一个基于DFS遍历策略的算法，求图中通过某顶点vk的简单回路（若存在）。 解：

算法思想，从给定顶点v4出发进行深度优先搜索，在搜索过程中判断当前访问的顶点是否为v4。若是，则找到一条回路。否则继续搜索。为此设一个顺序栈cycle记录构成回路的顶点序列，把访问顶点的操作改为将当前访问的顶点入栈；相应地，若从某一顶点出发搜索完再回溯，则做退栈操作，同时要求找到的回路的路径应大于2。另外还设置一个found，出值为0，当找到回路后为1。

Void dfscycle (ALGrph *G,int V4) {int i,j,top=0,V=V4,found=0,w; int Visitde[100],cycle[100]; EdgeNode *P; i=1;

cycle[i]=Vi /*从V是开始搜索*/ Visitde[v]==1; P=G[v]->firstedge;

While(p!=NULL!!top>0)&&!found) { while(p!=NULL&&!found)

if(p->adjvex==V4&&i<2)found=1; /*找到回路*/

else if(visited[p->adjvex]==0)p=p->next; /*找到下一个邻接点*/ elst

{w=p->adjvex; /*记下路径，继续搜索*/ visited[w]=1; i++;

cycle[i]=w; top++;

stack[top]=p;

p=G[w]->firstedge; }

if(!found&&top>0) /*沿原路径退回后，另选路径进行搜索*/ { p=attack[top]; top--; p=p->next; i--; }

} /*end while*/

if(found)

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

printf(“%d,”,cycle[j]); /*打印回路的顶点序列*/ printf(“%d,\\n”,V); }

else printf(“设有通过点V4的回路！\\n”) }

7．23 写一算法求有向图的所有根（若存在），分析算法的时间复杂度。 解：

算法思想：以有向图的每一个结点为源点对圆进行搜索，若能搜索到每个结点。则该结点为根。否则不是。

Void searchroot （ALGraph *G） { int i;

for(i=0;in;i++) {for(j=0;jn;j++)

visited[j]=false; /*标志向量初始化*/ DPS(G,i); /*以Vi为源点开始DPS搜索*/ } }

void DPS(ALGtaph *G,int i) { int count=0; EdgeNode *P; Visited[i]=true; count ++;

p=G->adjlist[i]->firstedge; while(p)

{if(!Visited[p->adjvex]) DPS(G,p->adjvex); P=p->next; }

if(count==G->n) /*该结点是根结点*/ printf(“%c”,G->adjlist[i]->vertex); }

7．24 改写7.5节的算法print,试输出的从源点到各终点的最短路径是正想。（提示：使用栈暂存路径）。 解：

使用栈暂存路径

void Ptint(PathP,Distance D) { int i,pre; seqstack *S;

s->top=-1 /*置空栈*/ for(i=0;i

{printf(“\\n distanck:%d,Path;”,D[i]);

/*输出终点I的最短距离*/ s->top++;

s->stack[s->top]=i; /*i入栈*/

pre=p[i]; /*栈终点的前趋*/ while(s->top>1)

{printf(“%d”,s->stack[s->top]); /*输出路径*/ s->top--;

} /*end while */

} /*end for*/ }

7.24改写7.5节的算法print，使输出的从源点到各终点的最短路径是正向。（提示：使用栈暂存路径）。

解：

使用栈暂存路径

void Print(PathP,Distance D) { int ,pre;

seqstack *s;

s->top=-1 /*置空栈*/ for(i=0;i

{printf(“\\n distanck:%d,path:”,D[i]);

/*输出终点i的最短距离*/ s->top++;

s->stack[s->top]=i; /*I入栈*/

pre=p[i]; /*栈终点的前趋*/ while(pre!=-1) {s->top++;

s->stack[s->top]=pre; /*路径入栈保存*/ pre=p[pre]; /*继续上溯前趋*/ }

while(s->top>-1)

{printf(“%d”,s->stack[s->top]); /*输出路径*/ s->top--;

} /*end while*/ } /*end for*/ }

7.25 对7.6节的NonSuccFirstTopSort算法，分别以邻接矩阵和邻接表作为存储结构， 写出其具体算法，并分析算法的时间。 解：

① 用逆邻接表作为G的存储结构。 Void NonSuccPirstTopSort(G)

{int outdehree[maxvertexNum]; /*出度向量，Maxvertexnum>=G,n*/ seqstack S,T; /*应将栈中data向量改为int类型*/ int i,j,count=0; Edgenode *P;

for(i=0;i

for(p=G->adjlist[i]->firstedge;p;p->next) /*扫描的入边表*/ outdegree[p->adjvex]++; /*出度为1*/ Initstack(&S); /*置空栈*/ Initstack(&T); for(i=0;in;i++) if(outdegree[i]==0)

push（&S,i） /*出度为零的顶点i入栈 */

while(!stackEmpty(&S)) /*栈非空，即图中有出度为0的顶点*/ {i=pop(&S); push(&T,i); count++;

for(p=G->adjlist[i]->firstedge;P;p=p->next); /*扫描的i入边表*/ {j=p->adjvex; /*j是i的入边的起点*/

outdegree[j]--; /*j的出度减肥。相当于删去边*/ if(!outdegree[i]) /*j无后继*/ push(&S,j); }/*end for*/ } /*end while*/ if(countn)

printf(“\\n The Graph is not a DAG.\\n”); /*图中有环，排序失败*/ else

{while(!stackEmpty(&S)) /*输出拓扑序列*/ {i=po(&T);print(“%d”,G->adjlist[i]->vertex);} } }

②用邻接矩阵作为存储结构。

Void NoSucePirstTopSort(Mgraph *G) {seqstack s,T;

int i,j,count=0; /*用i,j代表Vi,Vj*/

Initstack(&S); Initstack(&T);

for(i=0;in;i++)

for(j=0;jn;j++) if(G->edges[i][j]= =0)

push(&S,i); /*出度为0，入栈*/ while(!sruckEmpty(&S)) { i=po(&S); push(&T,i); count+ +;

for(j=0;jn;j++)

G->edges[i][j]=0; /*修改邻接矩阵*/ for(i=0;in;i++) for(j=0;jn;j++) if(G->edges[i][j]= =0)

push(&S,i);

} /*end while */ if(countn)

printf(“\\n The Graph is not a DAG.\\n”);

else

{while(!stackEmpty(&T)) /*输出拓扑序列*/ {i=pop(&T);

printf(“%d”,G->adjlist[i]->vertex); } } }

7.26设有向图一个DAG，试以邻接矩阵和邻接表作为存储结构，写出对7.6节的DFSTopSort求精的算法。问什么有向图不是DAG时，该算法不能正常工作？

解： ① 用邻接矩阵作为存储结构。

Void DPSTopSort(Mgraph*G,i,Setstack T) {int j;

visited[i]=true;

for(j=0;jm;j++) /*栈所i有的邻接点j*/ if(G->edges[i][j]= =1) if(!visited[j])

DPSTopSort(G,j,T);

Push(&T,i); /*从I出发的搜索已完成，保存i*/ }

② 用邻接表作为存储结构。

Void DPSTopSort(ALGraph G,i,T) {int j;

visited[i]=true;

for(p=G->adjlist[i]->firstedge;p;p=p->next) if(!visited[p->adjvex])

DPSTopSort(G,p->adjvex,T); Push(&T,i); }

由于有向图不是DAG时，从某点出发的搜索将陷入循环状态，所以算法不能正常工作。

7．27 利用拓扑排序算法的思想写一算法判别有向图中是否存在有向环，当有向环 存在时，输出构成环的顶点。 解：

设有向图用邻接表存储 Void SearckCycle(ALGraph G) {int i;

EdgeNode *P;

for(i=0;in;i++) /*对每一个顶点i*/ for(p=G->adjlist[i]->firstedge;p;p=p->next) /*扫描i的出边表*/ if(p->next=G->adjlist[i]->firstedge) /*存在环*/ printf(“%d”,G->adjlist[i]->vertex); }

8-1 设有序顺序表中的元素依次为017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的二叉搜索树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。 【解答】

509

154 677 553 897 017 275

094 14170 503 512 612 765 908 ASLsucc?

11 45 C?(1?2*2?3*4?4*7)??i1414i?114 ASLunsucc115'159?C?(3*1?4*14)??i1515i?015

8-2 若对有n个元素的有序顺序表和无序顺序表进行顺序搜索, 试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同?

(1) 搜索失败;

(2) 搜索成功, 且表中只有一个关键码等于给定值k的对象;

(3) 搜索成功, 且表中有若干个关键码等于给定值k的对象, 要求一次搜索找出所有对象。

【解答】

(1) 不同。因为有序顺序表搜索到其关键码比要查找值大的对象时就停止搜索，报告失败信息，不必搜索到表尾；而无序顺序表必须搜索到表尾才能断定搜索失败。

(2) 相同。搜索到表中对象的关键码等于给定值时就停止搜索，报告成功信息。

(3) 不同。有序顺序表中关键码相等的对象相继排列在一起，只要搜索到第一个就可以连续搜索到其它关键码相同的对象。而无序顺序表必须搜索全部表中对象才能确定相同关键码的对象都找了出来，所需时间就不相同了。

前两问可做定量分析。第三问推导出的公式比较复杂，不再进一步讨论。

8-3 假定用一个循环链表来实现一个有序表，并让指针head指向具有最小关键码的结点。指针current初始时等于head，每次搜索后指向当前检索的结点，但如果搜索不成功则current重置为head。试编写一个函数search(head, current, key)实现这种搜索。当搜索成功时函数返回被检索的结点地址，若搜索不成功则函数返回空指针0。请说明如何保持指针current以减少搜索时的平均搜索长度。 【解答】 current 10 20 30 40 50 60 head

相应的搜索函数可以定义为链表及链表结点类的友元函数，直接使用链表及链表结点类的私有数据成员。

template

ListNode * Search ( ListNode * head, ListNode *& current, Type key ) { ListNode * p, * q;

if ( key < current ) { p = head; q = current; } else { p = current; q = head; }

while ( p != q && p->data < key ) p = p->link; if ( p->data == key ) { current = p; return p; } else { current = head; return NULL; } }

//循链搜索其值等于key的结点 //找到, 返回结点地址 //未找到, 返回空指针

//确定检测范围, 用p, q指示

8-4 考虑用双向链表来实现一个有序表，使得能在这个表中进行正向和反向搜索。若指针p总是指向最后成功搜索到的结点，搜索可以从p指示的结点出发沿任一方向进行。试根据这种情况编写一个函数search(head, p, key)，检索具有关键码key的结点，并相应地修改p。最后请给出搜索成功和搜索不成功时的平均搜索长度。 【解答】

p

∧ 10 head 20 30 40 50 60 70 ∧

template

DblListNode * Search ( DblListNode * head, DblListNode *& p, Type key ) { //在以head为表头的双向有序链表中搜索具有值key的结点。算法可视为双向链表类和双向链表结点

类的友元

//函数。若给定值key大于结点p中的数据, 从p向右正向搜索, 否则, 从p向左反向搜索。 DblListNode * q = p;

if ( key < p->data ) { while ( q != NULL && q->data > key ) q = q-> lLink; } //反向搜索

else { while ( q != NULL && q->data < key ) q = q-> rLink; } //正向搜索 if ( q != NULL && q->data == key ) { p = q; return p; }

//搜索成功

else return NULL; }

?i?1n??1??(i?k?1)??(k?i?1)??n???n*(n?3)?i2?i?i*n??n?n?3?i2?i?i*nk?1k?i?1??2?2n 如果指针p处于第i个结点(i = 1, 2, ?, n)，它左边有i-1个结点，右边有n-i个结点。找到左边第i-1号结点比较2次，找到第i-2号结点比较3次，?，找到第1号结点比较i次，一般地，找到左边第k个结点比较i-k+1次(k = 1, 2, ?, i-1)。找到右边第i+1号结点比较2次，找到第i+2号结点比较3次，?，找到第n号结点比较n-i+1次，一般地，找到右边第k个结点比较k-i+1次(k = i+1, i+2, ?, n)。因此，当指针处于第i个结点时的搜索

成功的平均数据比较次数为

2ASL?1n?n??n?3i?i?i*n?succ?n2?3n?1i?1??2?n???3n一般地，搜索成功的平均数据比较次数为

?i?1n???(i?k)?k?0?(k?i?1)??(n?1)???n*(n?3)?i2?i?i*n?1??(n?1)k?i??2?如果指针p处于第i个结点(i = 1, 2, ?, n)，它左边有i个不成功的位置，右边有n-i+1个不

成功的位置。

ASL?1(n?1)2?n??n*(n?3)22?1??2nunsucci?0?2?i?i?i*n???7n?6n?1一般地，搜索不成功的平均数据比较次数为

8-5 在一棵表示有序集S的二叉搜索树中，任意一条从根到叶结点的路径将S分为3部分：在该路径左边结点中的元素组成的集合S1；在该路径上的结点中的元素组成的集合S2；在该路径右边结点中的元素组成的集合S3。S = S1 ? S2 ? S3。若对于任意的a ? S1, b ? S2, c ? S3， 是否总有a ? b ? c？为什么？ 【解答】

答案是否定的。举个反例：看下图粗线所示的路径 45 15

25

65

35 50 70 S1 = { 15 }, S2 = { 25, 30, 35, 45 }, S3 = { 40, 50, 65, 70 }

40 30 c = 40 ? S3，b = 45 ? S2，b ? c 不成立。

8-6 设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 37, 70, 29 }, 试画出从空树起，逐个输入各个数据而生成的二叉搜索树。

【解答】

46 46 46 46 46 46 25 25 78 25 78 25 78 25 78 空树 加46

加78 加25

62 12 62 12 37 62 加62 46 46 加12 加37

25 78 25 78 12 37 62 12 37 62 70 29 70

加29 加70

8-7 在二叉搜索树上删除一个有两个子女的结点时，可以采用以下三种方法：

(1) 用左子树TL上具有最大关键码的结点X顶替，再递归地删除X。

(2) 交替地用左子树TL上具有最大关键码的结点和右子树TR上具有最小关键码的结点顶替，再递归地删除适当的结点。

(3) 用左子树TL上具有最大关键码的结点或者用右子树TR上具有最小关键码的结点顶替，再递归地删除适当的结点。可随机选择其中一个方案。

试编写程序实现这三个删除方法，并用实例说明哪一个方法最易于达到平衡化。 【解答】

① 在被删结点有两个子女时用左子树TL中具最大关键码的结点顶替的算法：

template BstNode * BST :: leftReplace ( BstNode * ptr ) {

BstNode * temp = ptr->leftChild; ptr->data = temp->data; return temp; }

template BstNode * BST :: rightReplace ( BstNode * ptr ) {

//进到ptr的右子树 //搜寻中序下最后一个结点 //用该结点数据代替根结点数据

//进到ptr的左子树

//用该结点数据代替根结点数据

while ( temp->rightChild != NULL ) temp = temp->rightChild; //搜寻中序下最后一个结点

② 在被删结点有两个子女时用右子树TR中具最小关键码的结点顶替的算法：

BstNode * temp = ptr->rightChild; ptr->data = temp->data; return temp; }

while ( temp->leftChild != NULL ) temp = temp->leftChild;

(1) 用左子树TL上具有最大关键码的结点X顶替，再递归地删除X。

template void BST :: Remove ( Type& x, BstNode *& ptr ) { //私有函数：在以ptr为根的二叉搜索树中删除含x的结点。若删除成功则新根通过ptr返回。 BstNode * temp; if ( ptr != NULL )

if ( x < ptr->data ) Remove ( x, ptr->leftChild );

//在左子树中执行删除 //在右子树中执行删除

else if ( x > ptr->data ) Remove ( x, ptr->rightChild );

else if ( ptr->leftChild != NULL && ptr->rightChild != NULL ) {

}

}

// ptr指示关键码为x的结点，它有两个子女 //在ptr的左子树中搜寻中序下最后一个结点顶替x //在temp为根的子树中删除该结点

// ptr指示关键码为x的结点，它只有一个或零个子女

//只有右子女 //只有左子女

temp = leftReplace ( ptr );

Remove ( ptr->data, temp ); else { }

temp = ptr;

if ( ptr->leftChild == NULL ) ptr = ptr->rightChild; else if ( ptr->rightChild == NULL ) ptr = ptr->leftChild;

delete temp;

(2) 交替地用左子树TL上具有最大关键码的结点和右子树TR上具有最小关键码的结点顶替，再递归地删除适当的结点。

template void BST :: Remove ( Type& x, BstNode *& ptr, int& dir ) {

//私有函数：在以ptr为根的二叉搜索树中删除含x的结点。若删除成功则新根通过ptr返回。在参数//引用变量dir, 作为调整方向的标记。若dir = 0, 用左子树上具有最大关键码的结点顶替被删关键码; 若dir = 1,

//用右子树上具有最小关键码的结点顶替被删关键码结点, 在调用它的程序中设定它的初始值为0。 女

if ( dir == 0 ) {

temp = leftReplace ( ptr ); dir = 1; 点顶替x

}

} else {

temp = rightReplace ( ptr ); dir = 0;

//在ptr的右子树中搜寻中序下第一个结点//在ptr的左子树中搜寻中序下最后一个结

BstNode * temp; if ( ptr != NULL )

if ( x < ptr->data ) Remove ( x, ptr->leftChild, dir );

//在左子树中执行删除

//在右子树中执行删除

else if ( x > ptr->data ) Remove ( x, ptr->rightChild, dir );

表中有一个

else if ( ptr->leftChild != NULL && ptr->rightChild != NULL ) {

// ptr指示关键码为x的结点，它有两个子

顶替x

}

Remove ( ptr->data, temp, dir ); } else { }

// ptr指示关键码为x的结点，它只有一个

//在temp为根的子树中删除该结点

或零个子女

temp = ptr;

if ( ptr->leftChild == NULL ) ptr = ptr->rightChild; else if ( ptr->rightChild == NULL ) ptr = ptr->leftChild;

//只有右子女 //只有左子女

delete temp;

(3) 用左子树TL上具有最大关键码的结点或者用右子树TR上具有最小关键码的结点顶替，再递归地删除适当的结点。可随机选择其中一个方案。

#include

template void BST :: Remove ( Type& x, BstNode *& ptr ) {

//私有函数：在以ptr为根的二叉搜索树中删除含x的结点。若删除成功则新根通过ptr返回。在程序//随机数发生器rand( ), 产生0?32767之间的随机数, 将它除以16384, 得到0?2之间的浮点数。若其大于1, 用左

//子树上具有最大关键码的结点顶替被删关键码; 若其小于或等于1, 用右子树上具有最小关键码的结点顶替被删

//关键码结点, 在调用它的程序中设定它的初始值为0。 女

if ( (float) ( rand ( ) / 16384 ) > 1 ) { temp = leftReplace ( ptr ); dir = 1; 点顶替x

}

} else {

temp = rightReplace ( ptr ); dir = 0;

//在ptr的右子树中搜寻中序下第一个结点//在ptr的左子树中搜寻中序下最后一个结

BstNode * temp; if ( ptr != NULL )

if ( x < ptr->data ) Remove ( x, ptr->leftChild );

//在左子树中执行删除 //在右子树中执行删除

else if ( x > ptr->data ) Remove ( x, ptr->rightChild );

中用到一个

else if ( ptr->leftChild != NULL && ptr->rightChild != NULL ) {

// ptr指示关键码为x的结点，它有两个子

顶替x

}

Remove ( ptr->data, temp ); } else { }

// ptr指示关键码为x的结点，它只有一个

//在temp为根的子树中删除该结点

或零个子女

temp = ptr;

if ( ptr->leftChild == NULL ) ptr = ptr->rightChild; else if ( ptr->rightChild == NULL ) ptr = ptr->leftChild;

//只有右子女 //只有左子女

delete temp;

8-8将关键码DEC, FEB, NOV, OCT, JUL, SEP, AUG, APR, MAR, MAY, JUN, JAN 依次插入到一棵初始为空的AVL树中，画出每插入一个关键码后的AVL树，并标明平衡旋转的类型。 【解答】 加NOV 加OCT 加JUL 加DEC 加FEB FEB FEB DEC FEB DEC DEC +2 左单旋 FEB FEB NOV DEC NOV DEC NOV DEC

NOV NOV OCT JUL OCT FEB +2 DEC FEB OCT NOV 左单旋

加AUG NOV FEB OCT

NOV NOV NOV 加APR 加MAR OCT OCT OCT 右单旋 FEB FEB FEB SEP JUL JUL SEP SEP -2 DEC JUL AUG AUG APR AUG DEC APR DEC MAR APR

NOV NOV 加MAY OCT OCT FEB FEB 左单旋 SEP JUL +2 MAR SEP AUG AUG JUL MAY APR DEC MAR APR DEC

MAY

NOV -2 MAR

加JUN OCT FEB FEB NOV 左右双旋 AUG MAR AUG SEP MAY OCT JUL SEP APR JUL MAY APR DEC DEC JUN

JUN MAR 加JAN NOV FEB AUG JUL MAY OCT

APR DEC JAN JUN SEP

8-9 将关键码1, 2, 3, ?, 2k-1依次插入到一棵初始为空的AVL树中。试证明结果树是完全平衡的。 【解答】

所谓“完全平衡”是指所有叶结点处于树的同一层次上，并在该层是满的。此题可用数学归纳法证明。

当k = 1时，21-1 = 1，AVL树只有一个结点，它既是根又是叶并处在第0层，根据二叉树性质，应具有20 = 1个结点。因此，满足完全平衡的要求。 设k = n时，插入关键码1, 2, 3, ?, 2n-1到AVL树中，恰好每一层(层次号码i = 0, 1, ?, n-1)有2i个结点，根据二叉树性质，每一层达到最多结点个数，满足完全平衡要求。则当k = n+1时，插入关键码为1, 2, 3, ?, 2n-1, 2n, ?, 2n+1-1，总共增加了从2n到2n+1-1的2n+1-1-2n +1 = 2n个关键码，使得AVL树在新增的第n层具有2n个结点，达到该层最多结点个数，因

此，满足完全平衡要求。

8-10设散列表为HT[13], 散列函数为 H (key) = key 。用闭散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。采用线性探查法寻找下一个空位, 画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。 (2) 采用双散列法寻找下一个空位, 再散列函数为 RH (key) = (7*key) % 10 + 1, 寻找下一个空位的公式为 Hi = (Hi-1 + RH (key)) % 13, H1 = H (key)。画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度。 【解答】 使用散列函数 H(key) = key mod 13，有 H(12) = 12, H(23) = 10, H(45) = 6, H(57) = 5, H(20) = 7, H(03) = 3, H(78) = 0, H(31) = 5, H(15) = 2, H(36) = 10. (1) 利用线性探查法造表：

0 1 2 3 4 5 6 7 8 9 10 11 12 78

15 03 57 45 20 31 23 36 12 (1) (1) (1) 搜索成功的平均搜索长度为

(1) (1) (1) (4)

(1) (2) (1)

114 ASLsucc = 10(1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) = 10 搜索不成功的平均搜索长度为

361ASLunsucc = 13(2 + 1 + 3 + 2 + 1 + 5 + 4 + 3 + 2 + 1 + 5 + 4 + 3) = 13

(2) 利用双散列法造表： Hi = (Hi-1 + RH (key)) % 13, H1 = H (key) 0 1 2 3 4 5 6 7 78 15 03 57 45 20 (1) (1) (1) 搜索成功的平均搜索长度为

8 31 9 36 10 11 23 12 12 (1)

(1) (1) (1) (3) (5) (1)

116ASLsucc = 10(1 + 1 + 1 + 1 + 1 + 1 + 3 + 5 + 1 + 1) = 10

静态数据表类定义

#include const int DefaultSize = 100;

template class dataList

template class Element { friend class dataList ; private: Type key;

//排序码 //其它数据成员

field otherdata;

//数据表元素类的定义

//数据表的前视声明

public:

Type getKey ( ) { return key; }

//取当前结点的排序码 //将当前结点的排序码修改为x //结点x的值赋给this

void setKey ( const Type x ) { key = x; }

Element& operator = ( Element& x )

{ key = x->key; otherdata = x->otherdata; }

int operator == ( Type& x ) { return key == x->key; } //判this与x相等 int operator <= ( Type& x ) { return key <= x->key; } //判this小于或等于x int operator > ( Type& x ) { return key > x->key; } int operator < ( Type& x ) { return key > x->key; }

template class dataList {

//用顺序表来存储待排序的元素，这些元素的类型是Type private:

Element * Vector; int MaxSize, CurrentSize; public:

datalist ( int MaxSz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) { Vector = new Element [MaxSize]; } int length ( ) { return CurrentSize; }

Element& operator [ ] ( int i ) { return Vector[i]; } void swap ( Element & x, Element & y ) //交换x, y }

{ Element temp = x; x = y; y = temp; }

//排序

void Sort ( );

//构造函数

//存储待排序元素的向量 //最大元素个数与当前元素个数 //用于快速排序的一次划分算法

}

//判this大于x //判this小于x

int Partition ( const int low, const int high )

静态链表类定义

template class staticlinkList;

template class Element { friend class staticlinkList; private: Type key; int link; public:

Type getKey ( ) { return key; } int getLink ( ) { return link; } }

template class staticlinkList { private:

//静态链表的类定义

//取当前结点的排序码 //将当前结点的排序码修改为x //取当前结点的链接指针 //将当前结点的链接指针置为ptr

void setKey ( const Type x ) { key = x; } void setLink ( const int ptr ) { link = ptr; }

//排序码，其它信息略 //结点的链接指针

//静态链表元素类的定义 //静态链表类的前视声明

Element *Vector; int MaxSize, CurrentSize; public:

//存储待排序元素的向量

//向量中最大元素个数和当前元素个数

dstaticlinkList ( int Maxsz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) { Vector = new Element [Maxsz]; }

}

9-1 什么是内排序? 什么是外排序? 什么排序方法是稳定的? 什么排序方法是不稳定的? 【解答】内排序是排序过程中参与排序的数据全部在内存中所做的排序，排序过程中无需进行内外存数据传送，决定排序方法时间性能的主要是数据排序码的比较次数和数据对象的移动次数。外排序是在排序的过程中参与排序的数据太多，在内存中容纳不下，因此在排序过程中需要不断进行内外存的信息传送的排序。决定外排序时间性能的主要是读写磁盘次数和在内存中总的记录对象的归并次数。

不稳定的排序方法主要有希尔排序、直接选择排序、堆排序、快速排序。不稳定的排序方法往往是按一定的间隔移动或交换记录对象的位置，从而可能导致具有相等排序码的不同对象的前后相对位置在排序前后颠倒过来。其他排序方法中如果有数据交换，只是在相邻的数据对象间比较排序码，如果发生逆序(与最终排序的顺序相反的次序)才交换，因此具有相等排序码的不同对象的前后相对位置在排序前后不会颠倒，是稳定的排序方法。但如果把算法中判断逆序的比较“>(或<)”改写成“≥(或≤)”，也可能造成不稳定。

9-2 设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次排序码比较。 (1) 直接插入排序 (2) 希尔排序(增量为5,2,1) (3) 起泡排序 (4) 快速排序 (5) 直接选择排序 (6) 基数排序 (7) 堆排序 (8) 二路归并排序 【解答】

(1) 直接插入排序

初始排列 0 i = 1 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7 i = 8 i = 9

[ 12 ] [ 2 [ 2 [ 2 [ 2 [ 2 [ 2 [ 2 [ 2 [ 2

1 2 12 ] 12 12 12 10 10 10 6 6

2 16 16 16 ] 16 16 12 12 12 10 10

3 30 30 30 30 ] 28 16 16 16 12 12

4 28 28 28 28 30 ] 28 16* 16* 16 16

5 10 10 10 10 10 30 ] 28 20 16* 16*

6 16* 16* 16* 16* 16* 16* 30 ] 28 20 18

7 20 20 20 20 20 20 20 30 ] 28 20

8 6 6 6 6 6 6 6 6 30 ] 28 9 18 18 18 18 18 18 18 18 18 30 ] 排序码比较次数 1 1 1 2 5 3 3 3 8

(2) 希尔排序(增量为5,2,1)

初始排列 0 d = 5

12

1 2 2 16 3 30 4 28 5 10 6 16*

7 20

8 6

9 18

排序码比较次数 1+1+1+1+1 = 5

d = 2 d = 1

10 10 2

2 2 6

16 16 10

6 6 12

18 16* 16

12 12 16*

16* 18 18

20 20 20

30 30 28

28 28 30

(1+1+2+1) + (1+1 +1+1) = 9

1+1+3+1+3+1+1 +1+2 = 14

希尔(shell)本人采取的增量序列为 ?n/2?, ??n/2?/2?, ??n/2?/2?/2?, ?,1。一般地，增量序列可采用?nα?, ??nα?α?, ??nα?α?α?, ?, 1。大量实验表明，取α=0.45454的增量序列比取其他的增量序列的优越性更显著。计算 ?0.45454n? 的一个简单方法是用整数算术计算(5*n-1)/11。需要注意，当?< 1/2时，增量序列可能不以1结束，需要加以判断和调整。

(3) 起泡排序

初始排列 0 i = 0 i = 1 i = 2 i = 3 i = 4 i = 5 i = 6

[ 12 2 2 2 2 2 2 2

1 2 [ 12 6 6 6 6 6 6

2 16 6 [ 12 10 10 10 10 10

3 30 16 10 [ 12 12 12 12 12

4 28 30 16 16 [ 16 16 16 16

5 10 28 30 16* 16* [ 16* 16* 16*

6 16* 10 28 30 18 18 [ 18 18

7 20 16* 16* 28 30 20 20 20

8 6 20 18 18 28 30 28 28

9 18 ]

排序码比较次数 9

18 ] 8 20 ] 7 20 ] 6 20 ] 28 ] 30 ] 30

5 4 3

(4) 快速排序

Pivot Pvtpos 12 6 28 18 16*

0,1,2,3 0,1 4,5,6,7,8 4,5,6 4

0 [ 12 [ 6

1 6 2 2 2

6 6

10

12

10

12

10

12

2 16 10 ]

3 30 pos

16

16*

20

30

4 28

5 10

6 16*

7 20

8 6

9 18 ]

排序码比较次数 9

pos 2 pos pos

12 [ 28

18 ] 2

pos 2 pos [ 2 ]

[ 10 ] 12

[ 28 16 16*

pos pos pos [ 18

16 pos pos

18 18

[ 16* 16 ]

pos 16*

[ 16 ]

16* pos

[ 20 ] 20

28 28

30 30

1

20 30 pos pos 20 ]

28

18 ] 5 [ 30 ]

3

6

左子序列递归深度为1，右子序列递归深度为3。 (5) 直接选择排序

初始排列 0 1 i = 0 i = 1 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7 i = 8

[ 12 2 2 2 2 2 2 2 2 2

2 [ 12 6 6 6 6 6

2 16 16 10 10 10 10 10

3 30 30 30 12 12 12 12 12

4 28 28 28 [ 28 16 16 16 16 16

5 10 10 10 16 16 [ 28 16* 16* 16* 16*

6 16* 16* 16* 16* 16* 16* [ 28 18 16 16

7 20 20 20 20 20 20 20 [ 20 20 20

8 6 6 12 12 30 30 30 30 [ 30 28

9 18 ] 18 ] 18 ] 18 ] 18 ] 18 ] 18 ] 28 ] 28 ] 排序码比较次数 9 8 7 6 5 4 3 2 1

6 [ 16

6 10 [ 30 28 6 10 12

[ 30 ]

(6)基数排序

12 2 16 30 28 10 16* 20 6 18

按最低位分配

r[0] r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8] r[9]

20 6

2 18 10 16* 12 16 28 30 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]

收集 30 28 10 20 12 2 16 16* 6 18

按最高位分配 r[0] r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8] r[9] 18 * 16 16

6 2

2

12 10 28 20 30 10

12

16

18

20

28

30 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9]

6

16* 收集

(7) 堆排序

第一步，形成初始的最大堆 (略)，第二步，做堆排序。

12 30 12

2 16 28 16 28 16 **30 28 10 16 20 18 10 16 20 18 10 16*

2 6 12 2 6 30 20 6 18 初始排列，不是最大堆 形成初始最大堆 交换0# 与9# 对象 20 28 6 18 16 20 16 20 16 **12 6 10 16* 12 18 10 16 12 18 10 16 2 28 30 2 6 30 2 28 30 从0# 到8# 重新形成堆 交换0# 与8# 对象 从0# 到 7# 重新形成堆

16* 2 18

12 16 18 16 12 16 **2 6 10 18 12 6 10 16 2 6 10 16

20 28 30 20 28 30 20 28 30 交换0# 与7# 对象 从0# 到6# 重新形成堆 交换0# 与6# 对象

16* 10 16

12 16 12 16 12 10 **2 6 2 6 16 18 2 6 16 18 10 18

20 28 30 20 28 30 20 28 30

从0# 到5# 重新形成堆 交换0# 与5# 对象 从0# 到4# 重新形成堆

2 6 12

12 10 6 10 6 10 2 16 16 18 * 2 16 16 18 * 12 16 16 18 * 20 28 30 20 28 30 20 28 30

交换0# 与4# 对象 从0# 到3# 重新形成堆 交换0# 与3# 对象

2 6 10

6 10 2 10 6 2 ***12 16 12 16 12 16 16 18 16 18 16 18

20 28 30 20 28 30 20 28 30

从0# 到2# 重新形成堆 交换0# 与2# 对象 从0# 到1# 重新形成堆

2 2

6 10 6 10

** 12 16 12 16 16 18 16 18 20 28 30 20 28 30 0# 0# 到 交换与1# 对象 从1# 重新形成堆，得到结果

(8) 二路归并排序 采用迭代的方法进行归并排序。设待排序的数据对象有n个。首先把每一个待排序的数据对象看作是长度为的初始归并项，然后进行两两归并，形成长度为2的归并项，再对它们两两归并，形成长度为4的归并项，如此一趟一趟做下去，最后得到长度为n的归并结果。

12 2 16 30 28 10 16* 20 6 18

排序码比较5次

2 12 16 30 10 28 6 18 16* 20

12 排序码比较6次 *2 12 16 30 10 16 20 28 6 18

排序码比较7次

* 2 10 12 16 16 20 28 30 6 18

排序码比较9次

* 2 6 10 12 16 16 18 20 28 30

9-3 在起泡排序过程中，什么情况下排序码会朝向与排序相反的方向移动，试举例说明。在快速排序过程中有这种现象吗？ 【解答】 如果在待排序序列的后面的若干排序码比前面的排序码小，则在起泡排序的过程中，排序码可能向与最终它应移向的位置相反的方向移动。例如，

57 40 38 11 13 34 48 75 6 19 9 7 如9向相反方向移动 6 57 40 38 11 13 34 48 75 7 19 9 如19向相反方向移动 6 7 57 40 38 11 13 34 48 75 9 19 如9向最终方向移动 6 7 9 57 40 38 11 13 34 48 75 19 如13向相反方向移动 6 7 9 11 57 40 38 13 19 34 48 75 如13向最终方向移动 6 7 9 11 13 57 40 38 19 34 48 75 如34向相反方向移动 6 7 9 11 13 19 57 40 38 34 48 75 6 7 9 11 13 19 34 57 40 38 48 75

9-4 试修改起泡排序算法，在正反两个方向交替进行扫描，即第一趟把排序码最大的对象放到序列的最后，第二趟把排序码最小的对象放到序列的最前面。如此反复进行。 【解答1】

template void dataList :: shaker_Sort ( ) {

//奇数趟对表Vector从前向后, 比较相邻的排序码, 遇到逆序即交换, 直到把参加比较排序码序列 //中最大的排序码移到序列尾部。偶数趟从后向前, 比较相邻的排序码, 遇到逆序即交换, 直到把 //参加比较排序码序列中最小的排序码移到序列前端。

int i = 1, j; int exchange; while ( i < CurrentSize ) {

exchange = 0;

//起泡排序趟数不超过n-1 //假定元素未交换 //逆向起泡 //发生逆序

//交换, 最小排序码放在Vector[i-1]处 //做“发生了交换”标志 ////当exchange为0则停止排序 //正向起泡 //发生逆序

//交换, 最大排序码放在Vector[n-i]处 //做“发生了交换”标志 //当exchange为0则停止排序

for ( j = CurrentSize-i; j >= i; j-- ) if ( Vector[j-1] > Vector[j] ) { }

if ( exchange == 0 ) break;

exchange = 1;

Swap ( Vector[j-1], Vector[j] );

for ( j = i; j <= CurrentSize-i-1; j++ ) if ( Vector[j] > Vector[j+1] ) { }

if ( exchange == 0 ) break; i++;

exchange = 1;

Swap ( Vector[j], Vector[j+1] );

} }

【解答2】

template void dataList :: shaker_Sort ( ) { int low = 1, high = CurrentSize-1, i, j; int exchange; while ( low < high ) {

j = low;

//当比较范围多于一个对象时排序 //记忆元素交换位置

//正向起泡 //交换 //发生逆序

//记忆右边最后发生交换的位置j

for ( i = low; i < high; i++ )

if ( Vector[i] > Vector[i+1] ) {

j = i;

Swap ( Vector[i], Vector[i+1] );

} }

} high = j;

//比较范围上界缩小到j //反向起泡 //发生逆序

//交换

//记忆左边最后发生交换的位置j //比较范围下界缩小到j

for ( i = high; i > low; i-- ) } low = j;

if ( Vector[i-1] > Vector[i] ) {

j = i;

Swap ( Vector[i-1], Vector[i] );

9-5 如果待排序的排序码序列已经按非递减次序有序排列，试证明函数QuickSort( )的计算时间将下降到O(n2)。 【证明】

若待排序的n个对象的序列已经按排序码非递减次序有序排列，且设排序的时间代价为T(n)。当以第一个对象作为基准对象时，应用一次划分算法Partition，通过n-1次排序码比较，把只能把整个序列划分为：基准对象的左子序列为空序列，右子序列为有n-1个对象的非递减有序序列。对于这样的递归QuickSort( )算法，其时间代价为 T(n) = (n-1) + T(n-1) = (n-1) + {( n-2) + T(n-2) } = (n-1) + (n-2) + {(n-3) + T(n-3) } = ?? = (n-1) + (n-2) + (n-3) + ? + { 2 + T(1) } = (n-1) + (n-2) + (n-3) + ? + 2 + 1 = n(n-1)/2 = O(n2)

9-6 在实现快速排序的非递归算法时，可根据基准对象，将待排序排序码序列划分为两个子序列。若下一趟首先对较短的子序列进行排序，试证明在此做法下，快速排序所需要的栈的深度为O(log2n)。 【解答】

由快速排序的算法可知,所需递归工作栈的深度取决于所需划分的最大次数。如果在排序过程中每次划分都能把整个待排序序列根据基准对象划分为左、右两个子序列。假定这两个子序列的长度相等，则所需栈的深度为 S(n) = 1 + S(n/2) =

= 1 + { 1 + S(n/4) } = 2 + S(n/4) = 2 + { 1 + S(n/8) } = 3 + S(n/8) = ??

= log2n + S(1) = log2n (假设1个对象的序列所用递归栈的深度为0)

如果每次递归左、右子序列的长度不等，并且先将较长的子序列的左、右端点保存在递归栈中，再对较短的子序列进行排序，可用表示最坏情况的大O表示法表示。此时其递归栈的深度不一定正好是log2n，其最坏情况为O(log2n)。

9-7 在实现快速排序算法时，可先检查位于两端及中点的排序码，取三者之中的数值不是最大也不是最小的排序码作为基准对象。试编写基于这种思想的快速排序算法，并证明对于已

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