《数据结构与算法》课后习题答案

2.3课后习题解答

2.3.2判断题

1.线性表的逻辑顺序与存储顺序总是一致的。（X）

2.顺序存储的线性表可以按序号随机存取。（J）

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

半的元素需要移动。（X）

4.线性表中的元素可以是各种各样的，但同一-线性表中的数据元素具有相同的特性，

因此属于同一数据对象。（

5.在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。

（X）

6.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（J）

7.线性表的链式存储结构优于顺序存储结构。（X）

8.在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。

（4）

9.线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（J）

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

存取的存储结构。（X）

11.静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个元素

的时间与i无关。（X）

12.线性表的特点是每个元素都有一个前驱和•个后继。（X）

2.3.3算法设计题

1.设线性表存放在向量A[ar亩ze]的前elenum个分量中，且递增有序。试写一算法，

将x插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。

【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的

相邻，不一定将向量和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分配

的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元素

的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，（也可以从高下标端开

始一边比较，一边移位）然后插入x,最后修改表示表长的变量。

intinsert(datatypeA[],int*elenum,datatypex)/*设elenum为表的最大下标*/

{if(*elenum=arrsize-l)return0;/*表已满，无法插入*/

else{i=*elenum;

while(i>=0&&A[i]>x)/*边找位置边移动*/

{A[i+l]=A[i];

i-；

)

A[i+l]=x;/*找到的位置是插入位的卜一位*/

(*elenum)++;

return1;/*插入成功*/

)

时间复杂度为O（n）。

2.已知一顺序表A,其元素值非递减有序排列，编写一个算法删除顺序表中多余的值

相同的元素。

【提示】对顺序表A,从第一个元素开始，查找其后与之值相同的所有元素，将它们删除；

再对第二个元素做同样处理，依此类推。

voiddelete(Seqlist*A)

{i=0；

while(i<A->last)/*将第i个元素以后与其值相同的元素删除

东/

{k=i+l;

while(k<=A->last&&A->data[i]==A->data[k])

k++;/*使k指向第一个与A[i]不同的元素*/

n=k-i-l;/*n表示要删除元素的个数*/

fbr(j=k;j<=A->last;j++)

A->data[j-n]=A->data[j];/*删除多余元素*/

A->last=A->last-n;

i++；

)

)

3.写一个算法，从一个给定的顺序表A中删除值在x~y(x<=y)之间的所有元素，要求

以较高的效率来实现。

【提示】对顺序表A,从前向后依次判断当前元素A->data[i]是否介于x和y之间，若是，

并不立即删除，而是用n记录删除时应前移元素的位移量；若不是，则将A->data[i]向前移

动n位。n用来记录当前己删除元素的个数。

voiddelete(Seqlist*A,intx,inty)

{i=0;

n=0;

while(i<A->last)

{if(A->data[i]>=x&&A->data[i]<=y)n++;/*若A->data[i]介于x和y之间，n自增*/

elseA->data[i-n]=A->data[i];/*否则向前移动A->data[i]*/

i++；

}

A->last-=n;

)

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

R中的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间，元素

移动次数最小。

【提示】对线性表进行两次扫描，第一次将所有的字母放在前面，第二次将所有的数字放在

字母之后，其它字符之前。

intfch(charc)/*判断c是否字母*/

{if(c>='a'&&c<='z'llc>='A'&&c<='Z')return(I);

elsereturn(0);

)

intfnum(charc)/*判断c是否数字*/

{if(c>='0'&&c<='9')return(1);

elsereturn(0);

)

voidprocess(charR[n])

{low=0;

high=n-l;

while(low<high)/*将字母放在前面*/

{while(low<high&&fch(R[low]))low++;

while(low<high&&!fch(R|high]))high—;

if(low<high)

{k=R[low];

R[low]=R[high];

R[high]=k;

)

)

low=low+l;

high=n-l;

while(low<high)/*将数字放在字母后面，其它字符前面*/

{while(low<high&&fnum(R[low]))low++;

while(low<high&&!fnum(R[high]))high—;

if(low<high)

{k=R|low];

R[low]=R[high];

R[high]=k;

5.线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前m个

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

(aha2,...,am,bhb2,...,bn)改变为:

(b|,b2,・•♦,bn,a1,a2,・•♦,am)。

【提示】比较m和n的大小，若m<n,则将表中元素依次前移m次；否则，将表中元素依次

后移n次。

voidprocess(Seqlist*L,intm,intn)

{if(m<=n)

for(i=l;i<=m;i++)

{x=L->data[0];

for(k=l;k<=L->last;k++)

L->data[k-l]=L->data[k];

L->data[L->1ast]=x;

)

elsefor(i=l;i<=n;i++)

{x=L->data[L->last];

for(k=L->last-l;k>=0;k--)

L->data[k+1]=L->data[k];

L->data[0]=x;

)

)

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

结点插入到表L中，使得L仍然递增有序，并且分析算法的时间复杂度。

LinkListinsert(LinkListL,intx)

{P=U

while(p->next&&x>p->next->data)

p=p->next;/*寻找插入位置*/

s=(LNode*)malloc(sizeof(LNode));/*申请结点空间*/

s->data=x;/*填装结点*/

s->next=p->next;

p->next=s;/*将结点插入到链表中*/

return(L);

7.假设有两个已排序(递增)的单链表A和B,编写算法将它们合并成一个链表C而

不改变其排序性。

LinkListCombine(LinkListA,LinkListB)

{C=A;

rc=C;

pa=A->next;/,*pa指向表A的第一个结点*/

pb=B->next;/,*pb指向表B的第一个结点*/

free(B);/,*释放B的头结点*/

while(pa&&pb)/*将pa、pb所指向结点中，值较小的一个插入到链表C的表尾*/

if(pa->data<pb->data)

{rc->next=pa;

rc=pa;

pa=pa->next;

)

else

{rc->next=pb;

rc=pb;

pb=pb->next;

if(pa)rc->next=pa;

elserc->next=pb;/*将链表A或B中剩余的部分链接到链表C的表尾*/

return(C);

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

结点的指针，编写算法删除该结点的前驱结点。

【提示】利用循环单链表的特点，通过s指针可循环找到其前驱结点p及p的前驱结点q,

然后可删除结点*p。

vioddelepre(LNode*s)

{LNode*p,*q;

P=S；

while(p->next!=s)

{q=p；

p=p->next;

)

q->next=s;

free(p);

)

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

的交集C,要求C同样以元素递增的单链表形式存储。

【提示】交集指的是两个单链表的元素值相同的结点的集合，为了操作方便，先让单链表C

带有一个头结点，最后将其删除掉。算法中指针p用来指向A中的当前结点，指针q用来

指向B中的当前结点，将其值进行比较，两者相等时，属于交集中的一个元素，两者不等

时，将其较小者跳过，继续后面的比较.

LinkListIntersect(LinkListA,LinkListB)

{LNode*q,*p,*r,*s;

LinkListC;

C=(LNode*)malloc(sizeof(LNode));

C->next=NULL;

r=C;

P=A;

q=B;

while(p&&q)

if(p->data<q->data)p=p->next;

elseif(p->data==q->data)

{s=(LNode*)malloc(sizeof(LNode));

s->data=p->data;

r->next=s;

r=s;

p=p->next;

q=q->next;

)

elseq=q->next;

r->next=NULL;

C=C->next;

returnC;

)

10.设有一个双向链表，每个结点中除有prior、data利next域外，还有一个访问频度

freq域，在链表被起用之前，该域的值初始化为零。每当在链表进行一次Locata(L,x)运算后,

令值为x的结点中的freq域增1,并调整表中结点的次序，使其按访问频度的非递增序列排

列，以便使频繁访问的结点总是靠近表头。试写•个满足上述要求的Locata(L,x)算法。

【提示】在定位操作的同时，需要调整链表中结点的次序：每次进行定位操作后，要查看所

查找结点的freq域，将其同前面结点的freq域进行比较，同时进行结点次序的调整。

typedefstnactdnode

{datatypedata;

intfreq;

structDLnode*prior,*next;

)DLnode,*DLinkList;

DlinkListLocate(DLinkListL,datatypex)

{p=L->next;

while(p&&p->data!=x)p=p->next;/*杳找值为x的结点，使p指向它*/

if(!p)retum(NULL);/*若查找失败，返回空指针*/

p->freq++;/*修改p的freq域*/

while(p->prior!=L&&p->prior->freq<p->freq)/*调整结点的次序*/

{k=p->prior->data;

p->prior->data=p->data;

p->data=k;

k=p->prior->freq;

p->prior->freq=p->freq;

p->freq=k;

p=p->prior;

)

return(p);/*返回找到的结点的地址*/

3.3课后习题解答##

3.3.1选择题

1.向一个栈顶指针为Top的链栈中插入一个p所指结点时，其操作步骤为（C）。

A.Top->next=p;B.p->next=Top->next;Top->next=p;

C.p->next=Top;Top=p;D.p->next=Top;Top=Top->next;

2.对于栈操作数据的原则是（B）。

A.先进先出B.后进先出C.后进后出D.不分顺序

3.若已知一个栈的入栈序列是1,2,3,…n其输出序列为pi,p%P3，…，PN,若PN是“，

则Pi是（D）o

A.iB.n-iC.n-i+1D.不确定

4.表达式a*（b—c）+d的后缀表达式是（B）。

A.abcd*-+B.abc-*d+C.abc*-d+D.+-*abcd

5.采用顺序存储的两个栈共享空间top[i]代表第i个栈（i=l,2）的栈顶，栈1的

底在S[l],栈2的底在S[m],则栈满的条件是（B）o

A.top[2]-top[l]l=0B.top[l]+l=top[2]

C.top[l]+top[2]=mD.top[l]=top[2]

6.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（C）。

A.edcbaB.decbaC.dceabD.abcde

7.在一个链队列中，若f,r分别为队首、队尾指针，则插入s所指结点的操作为（B）。

A.f->next=r;f=s;B.r->next=s;r=s;

C.s->next=r;r=s;D.s->next=f;fcs;

8.用不带头结点的单链表存储队列时，在进行删除运算时（D）。

A.仅修改头指针B.仅修改尾指针

C.头、尾指针都要修改D.头、尾指针可能都要修改

9.递归过程或函数调用时，处理参数及返回地址，要用一种称为（C）的数据结构。

A.队列B.静态链表C.栈D.顺序表

10.栈和队都是（C）o

A.顺序存储的线性结构B.链式存储的非线性结构

C.限制存取点的线性结构D.限制存取点的非线性结构

3.3.2判断题

1.栈和队列的存储，既可以采用顺序存储结构，又可以采用链式存储结构。（J）

2.任何一个递归过程都可以转换成非递归过程。（J）

3.若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列325,6,4,1。（V）

4.通常使用队列来处理函数的调用。（X）

5.循环队列通常用指针来实现队列的头尾相接。（义）

3.3.3简答题

1.循环队列的优点是什么？如何判别它的空和满？

循环队列的优点是能够克服“假溢满”现象。

设有循环队列sq,队满的判别条件为：

（sq->rear+l）%maxsize==sq->front;或sq->num==maxsize»

队空的判别条件为：

sq->rear=sq->fronto

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

栈和队列都是操作受限的线性表，栈的运算规则是“后进先出”，队列的运算规则是“先

进先出”。栈的应用如数制转换、递归算法的实现等，队列的应用如树的层次遍历等。

3.什么是递归？递归程序有什么优缺点？

一个函数在结束本函数之前，直接或间接调用函数自身，称为递归。例如，函数f在执

行中，又调用函数f自身，这称为直接递归；若函数f在执行中，调用函数g,而g在执行

中，又调用函数f,这称为间接递归。在实际应用中，多为直接递归，也常简称为递归。

递归程序的优点是程序结构简单、清晰，易证明其正确性。缺点是执行中占内存空间较

多，运行效率低。

4.设有编号为1,2,3,4的四辆车，顺序进入一个栈式结构的站台，试写出这四辆车开出

车站的所有可能的顺序（每辆车可能入站，可能不入站，时间也可能不等）。

1234,1243,1324,1342,1432,213,2143,2314,2341,2431,3214,3241,3421,4321

4.3课后习题解答###

4.3.1选择题

1.下面关于串的叙述错误的是（C）。

A.串是字符的有限序列

B.串既可以采用顺序存储，也可以采用链式存储

C.空串是由空格构成的串

D.模式匹配是串的种重要运算

2.串的长度是指（B）。

A.串中所含不同字母的个数B.串中所含字符的个数

C.串中所含不同字符的个数D.串中所含非空格字符的个数

3.已知串S='aaab',其Next数组值为（A）»

A.0123B.1123C.1231D.1211

4.二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的

范围从0到8,列下标j的范围从1至U10,则存放M至少需要（D）个字节；M的第8列和

第5行共占（A）个字节；若M按行优先方式存储，元素M[8]⑶的起始地址与当M按列优

先方式存储时的（C）元素的起始地址一致。

（1）A.90B.180C.240D.540

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

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

5.数组A中，每个元素的存储占3个单元，行下标i从1到8,列下标j从1到10,

从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是（C）,若该数组

按行存放，元素A网⑸的起始地址是（D）,若该数组按列存放，元素A[8||5]的起始地址是

(B)„

(DA.80B.100C.240D.270

(2)A.SA+141B.SA+144C.SA+222D.SA+225

(3)A.SA+141B.SA+180C.SA+117D.SA+225

6.稀疏矩阵采用压缩存储，•般有（C）两种方法。

A.二维数组和三维数组B.三元组和散列

C.三元组表和十字链表D.散列和十字链表

4.3.2判断题

1.串相等是指两个串的长度相等。（X）

2.KMP算法的特点是在模式匹配时指示主串的指针不会变小。（J）

3.稀疏矩阵压缩存储后，必会失去随机存取功能。（J）

4.数组是线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。

（X）

5.若采用三元组存储稀疏矩阵，把每个元素的行下标和列下标互换，就完成了对该矩

阵的转置运算。（X）

6.若一个广义表的表头为空表，则此广义表亦为空表。（X）

7.所谓取广义表的表尾就是返回广义表中最后一个元素。（X）

4.3.3简答题

1.KMP算法较朴素的模式匹配算法有哪些改进？

KMP算法主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分

匹配时，KMP算法的优点更为突出。

2.设字符串S='aabaabaabaac',P=*aabaac'o

（1）给出S和P的next值和nextval值；

（2）若S作主串，P作模式串，试给出利用KMP算法的匹配过程。

【解答】

（1）S的next与nextval值分另U为012123456789和002002002009,p的next与nextval

值分别为012123和002003。

（2）利用BF算法的匹配过程：利用KMP算法的匹配过程：

第一趟匹配：aabaabaabaac第一趟匹配：aabaabaabaac

aabaac（i=6,j=6）aabaac（i=6,j=6）

第二趟匹配：aabaabaabaac第二趟匹配：aabaabaabaac

aa(i=3,j=2)(aa)baac

第一:趟匹配：aabaabaabaac第三趟匹配：aabaabaabaac

a(i=3,j=l)(成功)(aa)baac

第四趟匹配：aabaabaabaac

aabaac(i=9,j=6)

第五趟匹配：aabaabaabaac

aa(i=6,j=2)

第六趟匹配：aabaabaabaac

a(i=6J=l)

第七趟匹配：aabaabaabaac

(成功)aabaac(i=13,j=7)

3.假设按行优先存储整数数组A[9][3][5][8]时，第一个元素的字节地址是100,每个整

数占4个字节。问下列元素的存储地址是什么？

(1)a(xx)o(2闭]]](3)aj]25(4)ag247

【解答】(l)LOC(aoooo)=100

(2)LOC(aiiii)=100+(3*5*8*1+5*8*1+8*1+1)*4=776

(3)LOC(43125)=100+(3*5*8*3+5*8*1+8*2+5)*4=1784

(4)LOC(a8247)=100+(3*5*8*8+5*8*2+8*4+7)*4=4816

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

'ana,、

2

^21322

233a34

343^44

aij

ia2m,2m-1^2m,2m)

按以下方式存储于一维数组B|4m]中(m为一个整数):

0123456...k...4m-14m

ana12^213i22233ax^43aij^2m-1,2ma2m,2m-1^2m,2m

写出卜标转换函数k=f(i,j)。

【解答】

由题目可知，每一行有两个非0元素。

当i为奇数时,第i行的元素为:如、a“i+i),此时k=2*(i-l)+j-i=i+j-2

当i为偶数时，第i行的元素为:ag)、知,此时k=2*(i-l)+j-I+l=i+j-l

综上所述，k=i+j-i%2-l«

5.设有nxn的带宽为3的带状矩阵A,将其3条对角线上的元素存于数组B[3][n]中,

使得元素B[u][v]=au，试推导出从(ij)到(u,v)的下标变换公式。

【解答】

u=j-i+l

v=j-l

6.现有如下的稀疏矩阵A（如图所示），要求画出以下各种表示方法。

（1）三元组表表示法

（2）十字链表法。

000220-15

0133000

000-600

000000

9100000

0028000

【解答】

（1）三元组表表示法:

ijV

11422

216-15

32213

4233

534-6

65191

76328

（2）十字链表法:

7.画出下列广义表的头尾表示存储结构示意图。

(1)A=((a,b,c),d,(a,b,c))

(2)B=(a,(b,(c,d),e),f)

(1)

5.3课后习题解答

5.3.1选择题

1.下列说法正确的是（C）。

A.二义树中任何一个结点的度都为2

B.二叉树的度为2

C.一棵二叉树的度可小于2

D.任何一棵二叉树中至少有一个结点的度为2

2.以二叉链表作为二叉树的存储结构，在具有n个结点的二叉链表中（n>0）,空链域

的个数为（C）。

A.2n-lB.n-1C.n+1D.2n+l

3.线索化二叉树中，某结点*p没有孩子的充要条件是（B）。

A.p->lchild=NULLB.p->ltag=lJ3.p->rtag=l

C.p->ltag=OD.p->lchild=NULL且p->ltag=l

4.如果结点A有3个兄弟，而且B是A的双亲，则B的度是（B）。

A.3B.4C.5D.1

5.某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号值为1,2,...n。

且有如下性质:T中任意结点v,其编号等于左子树上的最小编号减1，而v的右子树的结点中,

其最小编号等于v左子树上结点的最大编号加1,这是按（B）编号的。

A.中序遍历序列B.先序遍历序列C.后序遍历序列D.层次顺序

6.设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点,B中右指针

域为空的结点有（C）个。

A.n-1B.nC.n+1D.n+2

7.一棵完全二叉树上有1001个结点，其中叶子结点的个数是（C）。

A.500B.501C.490D.495

8.设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为Nl,N2和N3。与

森林F对应的二叉树根结点的右子树上的结点个数是（D）。

A.N1B.N1+N2C.N2D.N2+N3

9.任何一棵二叉树的叶结点在先序、中序、后序遍历序列中的相时次序（A）。

A.不发生改变B.发生改变C.不能确定D.以上都不对

10.若一棵二叉树的后序遍历序列为dabec,中序遍历序列为debac,则先序遍历序列

为（D）。

A.cbedB.decabC.deabcD.cedba

11.若,棵二叉树的先序遍历序列为abdgcefh,中序遍历的序列为dgbaechf,则后序遍

历的结果为（D）。

A.gcefhaB.gdbecfhaC.bdgaechfD.gdbehfca

12.一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足

（B）。

A.所有的结点均无左孩子B.所有的结点均无右孩子

C.只有一个叶子结点D.是一棵满二叉树

13.引入线索二叉树的目的是（A）。

A.加快查找结点的前驱或后继的速度

B.为了能在二叉树中方便的进行插入与删除

C.为了能方便的找到双亲

D.使二叉树的遍历结果唯一

14.设高度为h的二叉树匕只有度为0和度为2的结点，则此类二叉树中所包含的结点

数至少为（B）。

A.2*hB.2*h-lC.2*h+lD.h+1

15.一个具有567个结点的二叉树的高h为（D）。

A.9B.10C.9至566之间D.10至567之间

5.3.2判断题

1.二叉树是树的特殊形式。（J）

2.由树转换成二叉树，其根结点的右子树总是空的。（J）

3.先根遍历一棵树和先序遍历与该树对应的二叉树，其结果不同。（X）

4.先根遍历森林和先序遍历与该森林对应的二叉树，其结果不同。（X）

5.完全二叉树中，若一个结点没有左孩子，则它必是叶子。（J）

6.对于有N个结点的二叉树，其高度为Llog2N」+l。（X）

7.若一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的

先序遍历序列中的最后一个结点。（J）

8.若一个结点是某二叉树子树的中序遍历序列中的第一个结点，则它必是该子树的后

序遍历序列中的第一个结点。（J）

9.不使用递归也可实现二叉树的先序、中序和后序遍历。（J）

10.先序遍历二叉树的序列中，任何结点的子树的所有结点不一定跟在该结点之后。（X）

II.先序和中序遍历用线索树方式存储的二叉树，不必使用栈。（X）

12.在后序线索二叉树中，在任何情况下都能够很方便地找到任意结点的后继。（X）

13.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。（V）

14.在哈夫曼编码中，出现频率相同的字符编码长度也一定相同。（X）

15.用一维数组存放二叉树时，总是以先序遍历存储结点。（X）

16.由先序序列和后序序列能唯•确定一棵二叉树。（X）

17.由先序序列和中序序列能唯一确定一棵二叉树。（J）

18.对一棵二叉树进行层次遍历时，应借助于一个栈。（X）

19.完全二叉树可采用顺序存储结构实现存储，非完全二叉树则不能。（X）

20.满二叉树一定是完全二叉树，反之未必。（J）

5.3.3简答题

1.一棵度为2的树与一棵二叉树有何区别？树与二叉树之间有何区别？

【解答】

①二叉树是有序树，度为2的树是无序树，二叉树的度不一定是2。

②二叉树是有序树，每个结点最多有两棵子树，树是无序树，且每个结点可以有多棵子

树。

2.对于图I所示二叉树，试给出：

（1）它的顺序存储结构示意图；

（2）它的二叉链表存储结构示意图;

（3）它的三叉链表存储结构示意图。

【解答】

（1）顺序存储结构示意图：

ABCDEFAAAGAAH

（2）二叉链表存储结构示意图:（3）三叉链表存储结构示意图:

3.对于图2所示的树，试给出：

（1）双亲数组表示法示意图；

（2）孩子链表表示法示意图；

（3）孩子兄弟链表表示法示意图。

【解答】

（I）双亲数组表示法示意图：（2）

ro

A工

r

_0_

o

c

n

（3）孩子兄弟链表表示法示意图:

【解答】

在二叉树中某结点所对应的森林中结点为叶子结点的条件是该结点在森林中既没有孩

子也没有右兄弟结点。

5.将题5图所示的二叉树转换成相应的森林。

（题5图）

【解答】森林：

6.证明：在结点数多于1的哈夫曼树中不存在度为1的结点。

证明：由哈夫曼树的构造过程可知，哈夫曼树的每一分支结点都是由两棵子树合并产生

的新结点，其度必为2,所以哈夫曼树中不存在度为1的结点。

7.证明：若哈夫曼树中有n个叶结点，则树中共有2n—1个结点。

证明：n个叶结点，需经n-1次合并形成哈夫曼树，而每次合并产生一个分支结点，所

以树中共有2n-l个结点。

8.证明：由二叉树的前序序列和中序序列可以唯地确定一棵二叉树。

证明：给定二叉树结点的前序序列和对称序（中序）序列，可以唯一确定该二叉树。因

为前序序列的第一•个元素是根结点，该元素将二叉树中序序列分成两部分，左边（设1个元

素）表示左子树，若左边无元素，则说明左子树为空；右边（设r个元素）是右子树，若为

空，则右子树为空。根据前序遍历中“根一左子树一右子树”的顺序，则由从第二元素开始

的1个结点序列和中序序列根左边的1个结点序列构造左子树，由前序序列最后r个元素序

列与中序序列根右边的r个元素序列构造右子树。

9.已知一棵度为m的树中有囚个度为1的结点，血个度为2的结点.....小个度

为m的结点，问该树中共有多少个叶子结点？有多少个非终端结点？

解：设树中共有n个结点，即个叶结点，那么

=

nn（）4-ni+...+nin（1）

树中除根结点外，每个结点对应着一个分支，而度为k的结点发出k个分支，所以：

n=n।+2*3+…+m*nm+l（2）

由（1）、（2）可知n0=n2+2*n3+3*n4+...+（m-1）*nm+1

10.在具有n（n>l）个结点的树中，深度最小的那棵树其深度是多少？它共有多少叶

子和非叶子结点？深度最大的那棵树其深度是多少？它共有多少叶子和非叶子结点？

2;n-1;1;n;1,n-1

11.设高度为h的二叉树上只有度为0和度为2的结点，问该二叉树的结点数可能达到

的最大值和最小值。

最大值：2h-l；最小值：2h-l

12.求表达式：a+b*（c—d）—e/f的波兰式（前缀式）和逆波兰式（后缀式）。

波兰式：-+a*b-cd/ef逆波兰式：abcd-*+ef/-

13.画出和下列已知序列对应的树T：

树的先根次序访问序列为：GFKDAIEBCHJ；

树的后根访问次序为：DIAEKFCJHBG。

【解答】对应的二叉树和树分别如下左、右图所示：

14.画出和下列已知序列对应的森林F：

森林的先根次序访问序列为：ABCDEFGH1JKL；

森林的后根访问次序为：CBEFDGAJIKLHo

15.画出和下列已知序列对应的树T：

二叉树的层次访问序列为：ABCDEFGHIJ；

二叉树的中序访问次序为：DBGEHJACIF。

【解答】

按层次遍历，第一个结点（若树不空）为根，该结点在中序序列中把序列分成左右两部

分一左子树和右子树。若左子树不空，层次序列中第二个结点左子树的根；若左子树为空，

则层次序列中第二个结点右子树的根。对右子树也作类似的分析。层次序列的特点是：从左

到右短个结点或是当前情况下子树的根或是叶子。

16.假设用于通信的电文由字符集｛a,b,c,d,e,f,g｝中的字母构成。它们在电文中出现的频

度分别为｛0.31,0.16,0.10,0.08,0.11,0.20,0.04｝,

（1）为这7个字母设计哈夫曼编码。

（2）对这7个字母进行等长编码，至少需要儿位二进制数？哈夫曼编码比等长编码使电文

总长压缩多少？厂、

L1.00）

(1)哈夫曼树：

a：10

b：110

c：010

d：1110

e：Oil

f：00

g：nil

(2)对这7个字母进行等长编码，至少需要3位二进制数。

等长编码的平均长度：0.31*3+0.16*3+0.10*3+0.08*3+0.11*3+0.20*3+0.04*3=3

哈夫曼编码：0.31*2+0.16*3+0.10*3+0.08*4+0.11*3+0.20*2+0.04*4=2.54

哈夫曼编码比等长编码使电文总长压缩了：1-2.54/3=15.33%

5.3.4算法设计题

1.给定一棵用二叉链表表示的二叉树，其根指针为root,试写出求二叉树结点的数目

的算法。

【提示】采用递归算法实现。

”0当二叉树为空

二叉树结占的数目=-

左子树结点数FI+右子树结点数目+1当二叉树非空

intcount(BiTreeroot)

{if(root==NULL)return(0);

elsereturn(count(root->lchild)+count(root->rchild)+l);

)

2.请设计一个算法，要求该算法把二叉树的叶结点按从左至右的顺序链成一个单链表。

二叉树按Ichild-rchild方式存储，链接时用叶结点的rchild域存放链指针。

【提示】这是一个非常典型的基于二叉树遍历算法，通过遍历找到各个叶子结点，因为不论

前序遍历、中序遍历和后序遍历，访问叶子结点的相对顺序都是相同的，即都是从左至右。

而题目要求是将二叉树中的叶子结点按从左至右顺序建立一个单链表，因此，可以采用三种

遍历中的任意一种方法遍历。这里使用中序递归遍历。设置前驱结点指针pre,初始为空。

第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，

最后叶子结点的rchild为空。

LinkListhead,pre=NULL;/*全局变量*/

LinkListInOrder(BiTreeT)

/*中序遍历二叉树T,将叶子结点从左到右链成一个单链表，表头指针为head*/

{if(T){InOrder(T->lchild);/*中序遍历左子树*/

if(T->lchild==NULL&&T->rchild==NULL)/*当前是叶子结点*/

if(pre==NULL)

{head=T;

pre=T;}/*处理第一个叶子结点*/

else{pre->rchild=T;

pre=T;}/*将叶子结点键入链表*/

InOrder(T->rchi1d);/*中序遍历右子树*/

pre->rchild=NULL；/*设置链表尾结点*/

return(head);

)

3.给定一棵用二叉链表表示的二叉树，其根指针为root,试写出求二叉树的深度的算

法。

【提示】采取递归算法。

intHeight(BiTreeroot)

{inthl,hr;

if(root==NULL)return(O);

else{hl=Height(root->lchild);

hr=Height(root->rchiId);

if(hl>hr)return(hl+1);

elseretum(hr+l);

)

)

4.给定一棵用二叉链表表示的二叉树，其根指针为root,试求二叉树各结点的层数。

【提示】采用先序递归遍历算法实现。

当结点为根结点

二叉树结点的层次数=

其双亲结点的层次数+1当结点非根结点

voidfun(BiTreeroot,intn)

{if(t=NULL)return;

else{printfC4%d,,,n);

fun(root->lchild,n+l);

fun(root->rchild,n+l);

)

}

5.给定一棵用二叉链表表示的二叉树，其根指针为root,试写出将二叉树中所有结点

的左、右子树相互交换的算法。

【提示】设root为一棵用二叉链表存储的二叉树，则交换各结点的左右子树的运算可基于

后序遍历实现：交换左子树上各结点的左右子树；交换左子树上各结点的左右子树；再交换

根结点的左右子树。

voidExchange(BiTreeroot)

{BiTNode*p;

if(root)

{Exchange(root->lchild);