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

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

2.3课后习题解答2.3.2判断题

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

线性表可以按序号随机存取。（V）

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

操作平均只有近一半的元素需要移动。（某）

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

具有相同的特性，因此属于同一数据对象。（J）

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

上并不一定相邻。（某）

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

一定相邻。（J）

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

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

元素的位置有关。（J）

9.线性表的链式存储结构是用一组任意的存储单元来存储线性表中

数据元素的。（J）

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

此，单链表是随机存取的存储结构。（某）

11.静态链表既有顺序存储的优点，又有动态链表的优点。所以它存

取表中第i个元素的时间与i无关。（某）

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

2.3.3算法设计题

1设线性表存放在向量A[arrize]的前elenum个分量中，且递增有

序。试写一算法，将某插入到线性表的适当位置上，以保持线性表的有序性,

并且分析算法的时间复杂度。

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

上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装

成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以

首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性，来

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

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

intinert（datatypeAf],int某elenum,datatype剽elenum为表的最

大下标某/

{if（某elenum==arrize-l）return。；法插入某/

ele仃=某elenum;

while（i>=O&&A[i]>某）

边移动某/{A[i+l]=A[i];i—;}

A[i+1]=某；

/某找到的位置是

/某边找位置

/某表已满，无/某

设

插入位的下一位某/

(某elenum)++;

returnl;}}

时间复杂度为0(n)。

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

顺序表中多余的值相同的元素。

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

有元素，将它们删除；再对第二个元素做同样处理，依此类推。

voiddelete(Seqlit某A){i=0;

while(ilat)与其值相同的元素删除某/

{k=i+l;

while(k<=A->1at&&A-〉data[i]==A->data[k])

k++;

/某使k指向第一个与A[i]

/某将第i个元素以后

/某插入成功某/

不同的元素某/

n=k-i-l;

/某n表示要删除元

素的个数某/

for(j=k;j<=A->lat;j++)

A->data[j-n]=A->data[j];

/某删除多余元素

某/

A->lat=A->lat-n;

i++；

)

3写一个算法，从一个给定的顺序表A中删除值在某~y(某<=y)之间

的所有元素，要求以较高的效率来实现。

【提示】对顺序表A,从前向后依次判断当前元素A->data[i]是否介

于某和y之间，若是，并不立即删除，而是用n记录删除时应前移元素的

位移量；若不是，则将A->data[i]向前移动n位。n用来记录当前已删除

元素的个数。

voiddelete(Seqlit某A,int某,inty){i=0;n=0;

while(ilat)

{if(A->data[i]>=某&&A->data[i]<=y)n++;/某若A->data[i]

}

介于某和y之间，n自增某/

eleA->data[i-n]=A->data[i];

/某否则向前移动

A->data[i]某/

i++;}A->lat-=n;

)

4线性表中有n个元素，每个元素是一个字符，现存于向量R[n]中,

试写一算法，使R中的字符按字母字符、数字字符和其它字符的顺序排列。

要求利用原来的存储空间，元素移动次数最小。【提示】对线性表进行两

次扫描，第一次将所有的字母放在前面，第二次将所有的数字放在字母之

后，其它字符之前。intfch(chare)

{if(c>=，a&&c<=，z'||c>='A'&&c<=，Z')elereturn(0);}

intfnum(chare)否数字某/

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

elereturn(0);)

voidproce(charR[n]){1ow=0;high=n-l;while(low

/某将字母放在前面某/

/某判断c是

/某判断c是否字母某/return(1);

{while(low

while(low

{k=R[low];R[low]=R[high];R[high]=k;}

low=low+l;high=n-l;while(low

{while(low

R[low]=R[high];R[high]=k;}

}

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

将顺序表中前m个元素和后n个元素进行整体互换。即将线性表：

(al,a2,am,bl,b2,bn)改变为:(bl,b2,,,,,bn,al,a2,am)。}

/某将数字放在字母后

【提示】比较m和n的大小，若m

{if(m<=n)

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

{某=L->data[0];

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

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

L->data[L->lat]=某;}

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

{某=L->data[L->lat];

for(k=L->lat-l;k>=0;k--)L->data[k+l]=L->data[k];L->data[0]=

某;}}

6已知带头结点的单链表L中的结点是按整数值递增排列的，试写

一算法，将值为某的结点插入到表L中，使得L仍然递增有序，并且分析

算法的时间复杂度。LinkLitinert(LinkLitL,int某){p=L;

while(p->ne某t&&某〉p->ne某t->data)p=p->ne某t;

/某寻找插

入位置某/

=(LNode某)malloc(izeof(LNode));->data=某;

/某申请结点空间某/

/某填装

结点某/

->ne^t=p->ne某t;p->ne某t=;

/某将结点插入

到链表中某/

return(L);

)

{C=A;rc=C;pa=A->ne某t;pb=B->ne某t;free(B);

头结点某/

while(pa&&pb)

/某将pa、pb所指向结点中，值

/某pa指向表A的第一个结点某〃某pb指向表B的第一个结点某/

/某释放B的

较小的一个插入到链表C的表尾某/

if(pa->datadata)

{rc->ne^t=pa;rc=pa;pa=pa->ne某t;}ele

{rc->ne^t=pb;rc=pb;pb=pb->ne某t;}

if(pa)

rc->ne^t=pa;

/某将链表A或B中剩余的部分链接到

elerc->ne^t=pb;

链表C的表尾某/

return(C);

}

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

指向该链表中某一结点的指针，编写算法删除该结点的前驱结点。【提示】

利用循环单链表的特点，通过指针可循环找到其前驱结点P及P的前驱结

点q,然后可删除结点某p。vioddelepre(LNode某){LNode某p,某q;p=;

while(p->ne某t!=){q=p;p=p->ne某t;}q->ne某t=;free(p);}

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

写算法求出A和B的交集C,要求C同样以元素递增的单链表形式存储。

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

作方便，先让单链表c带有一个头结点，最后将其删除掉。算法中指针P

用来指向A中的当前结点，指针q用来指向B中的当前结点，将其值进行

比较，两者相等时，属于交集中的一个元素，两者不等时，将其较小者跳过，

继续后面的比较。LinkLitlnterect(LinkLitA,LinkLitB)

{LNode某q,某p,某r,某;LinkLitC;

C=(LNode某)malloc(izeof(LNode));C->ne某t=NULL;r=C;p=A;

8.设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为

Nl,N2和N3。与森林F对应的二叉树根结点的右子树上的结点个数是

(D)o

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

9.任何一棵二叉树的叶结点在先序、中序、后序遍历序列中的相对

次序(A)。

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

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

debac,则先序遍历序列为(D)□

A.cbedB.decabC.deabcD.cedball.若一棵二叉树的先序遍历序

列为abdgcefh,中序遍历的序列为dgbaechf,则后序遍历的结果为(D)。

A.gcefhaB.gdbecfhaC.bdgaechfD.gdbehfcal2.一棵非空二叉树

的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足(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+115.一个具有567个结点的二

叉树的高h为（D）。

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

16.给一个整数集合｛3,5,6,7,9）,与该整数集合对应的哈夫曼

树是（B）。

A.B.C.D.

5.3.2判断题

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

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

遍历一棵树和先序遍历与该树对应的二叉树，其结果不

35679353597667356799同。（某）

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

（某）

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

6.对于有N个结点的二叉树，其高度为log2N+l。（某）7.若一个结

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

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

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

它必是该子树的后序遍历序列中的第一个结点。（V）

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

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

结点之后。（某）

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

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

点的后继。（某）

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

较近。（V）

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

（某）

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

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

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

棵二叉树进行层次遍历时，应借助于一个栈。（某）19.完全二叉树可采

用顺序存储结构实现存储，非完全二叉树则不能。（某）

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

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

别？【解答】

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

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

结点可以有多棵子

BCA树。

DEF2.对于图1所示二叉树，试给出：

GH(图1)

(1)它的顺序存储结构示意图；(2)它的二叉链表存储结构示意图;

(3)它的三叉链表存储结构示意图。【解答】

(1)顺序存储结构示意图：

ABCDEF^^G^H

(2)二叉链表存储结构示意图：(3)三叉链表存储结构示意图：

^D^BE^F^H'AC^D^G^BEVC^F^

弋~3.对于图2所示的树，试给出：BACFHJEKDMIN(1)双亲数组表

示法示意图；G(2)孩子链表表示法示意图；(图2)(3)孩子兄弟链表

表示法示意图。【解答】

(1)双亲数组表示法示意图：(2)孩子链表表示法示意图：

0123456789101112ABCDEFGHIJKMN-

10022115244380123456789101112ABCDEFGHIJKMN12"153ir97"2，'6410"8"

15.画出和下列已知序列对应的树T：二叉树的层次访问序列为：

ABCDEFGHIJ；二叉树的中序访问次序为：DBGEHJACIFo

【解答】

按层次遍历，第一个结点(若树不空)为根，该结点在中序序列中把

序列分成左右两部分一左子树和右子树。若左子树不空，层次序列中第二

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

对右子树也作类似的分析。层次序列的特点是：从左到右每个结点或是当

前情况下子树的根或是叶子。

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个字母进行等长编码，至少需要几位二进制数？哈夫曼

DGBEHJIACF编码比等长编码使电文总长压缩多少？(1)哈夫曼树：

001.001100.410.5910.2810.120a：10b：110c：010d：1110e：011f：00g：

1111

0.2000.2110.110.100.3100.160.8010.40(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当二叉树为空二叉树结点的数目=

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

intcount(BiTreeroot)

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

elereturn(count(root->lchild)+count(root->rchild)+1);}

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

序链成一个单链表。二叉树按Ichild-rchild方式存储，链接时用叶结点

的rchild域存放链指针。

【提示】这是一个非常典型的基于二叉树遍历算法，通过遍历找到各

个叶子结点，因为不论前序遍历、中序遍历和后序遍历，访问叶子结点的

相对顺序都是相同的，即都是从左至右。而题目要求是将二叉树中的叶子

结点按从左至右顺序建立一个单链表，因此，可以采用三种遍历中的任意

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

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

的rchild指针指向它，最后叶子结点的rchild为空。

LinkLithead,pre=NULL;LinkLitlnOrder(BiTreeT)

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

指针为head某/

{if(T){InOrder(T->lchild);左子树某/

if(T->lchild==NULL&&T->rchi1d==NULL)

前是叶子结点某/

if(pre==NULL){head=T;

/某当

/某中序遍历/某全局变量某/

pre=T;}

个叶子结点某/

/某处理第一

ele{pre->rchild=T;

pre=T;}

/某将叶子结

点链入链表某/

InOrder(T->rchild);树某/

pre->rchild=NULL;return(head);}

3.给定一棵用二叉链表表示的二叉树，其根指针为出求二叉树的深

度的算法。【提示】采取递归算法。

intHeight(BiTreeroot){inthl,hr;

if(root==NULL)return(0);ele{hl=Height(root->lchild);

hr=Height(root-

>rchild);if(hl>hr)return(hl+1);elereturn(hr+1);}

}

/某中序遍历右子

/某设置链表尾结点某/

root,试写4.给定一棵用二叉链表表示的二叉树，其根指针为root,

试求二叉树各结点的层数。

【提示】采用先序递归遍历算法实现。1二叉树结点的层次数=

其双亲结点的层次数+1

voidfun(BiTreeroot,intn){if(t==NULL)return;

ele{printf(—%dII,n);

fun(root->lchiId,n+1);fun(root->rchiId,n+1);

)}

当结点为根结点当结点非根结点

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

二叉树中所有结点的左、右子树相互交换的算法。

【提示】设root为一棵用二叉链表存储的二叉树，则交换各结点的

左右子树的运算可基于后序遍历实现：交换左子树上各结点的左右子树；

交换左子树上各结点的左右子树；再交换根结点的左右子树。

voidEMchange(BiTreeroot){BiTNode某p;

if(root)

{E某change(root->lchiId);

E某change(root->rchiId);p=root->lchild;

root->lchild=root->rchild;

root->rchild=p;}

11编写算法判定两棵二叉树是否相似。所谓两棵二叉树和t相似，

即要么它们都为空或都只有一个结点，要么它们的左右子树都相似。

【提示】两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树,

可判左右子树是否相似,采用递归算法。intSimilar(BiTree,BiTreet)

{if(==NULL&&q==NULL)return(1);

eleif(!&&t||&&!t)return(0);ele

return(Similar(->lchild,t->lchild)

&&

Similar(->rchild,t->rchild)))

E写出用逆转链方法对二叉树进行先序遍历的算法。【提示】用逆

转链的方法遍历二叉树，不需要附加的栈空间，而是在遍历过程中沿结点

的左右子树下降时，临时改变结点Ichild或者rchild的值，使之指向双

亲，从而为以后的上升提供路径，上升时再将结点的Ichild或者rchild

恢复。

typedeftructtnode{datatypedata;

inttag;/某tag的值初始为0,进入左子树时置1,从左子树回来时,

再恢复为0某/

tructtnode某Ichild,某rchild;}Bnode,某Btree;

voidPreOrder(Btreebt)

(Bnode某r,某p,某q;/某p指向当前结点，r指向p的双亲，q指向

要访问的下一结点某/

if(bt==NULL)return;p=bt;r=NULL:while(p){Viit(p);点某/

if(p->lchild)左子树某/

{p->tag=l;q=p->lchiId;q=p->lchild=r;r=p;p=q;}eleif(p->rchild)

入右子树某/

{q=p->rchiId;p->rchild=r;r=p;p=q;}

ele{

/某上升某/

II

/某下降进

/某下降进入

/某访问P所指结

whle((r&&t->tag==O)

(r&&t->tag==l&&r->rchild==NULL))

{if(r&&t->tag==O)

{q=r->rchild;r->rchild=p;p=r;r=q;}

/某从

右子树回来某/

ele{r->tag=O;q=r->lchild;r->lchild=p;p=r;r=q;}

树回来某/

if(r==NULL)return;

ele{r->tag=O;q=r->rchild;

r->rchi1d=r->IchiId;r->Ichiid=p;

p=q;

}

回来，准备进入右子树某/

}

)

}}

B对以孩子一兄弟链表表示的树编写计算树的深度的算法。【提示】

采用递归算法实现。0若树为空树的深度=

Ma某(第一棵子树的深度+1,兄弟子树的深度)若树非空

inthigh(CSTreeT