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

2.3 课后习题解答 2.3.2 判断题

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

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

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

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

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

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

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

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

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

11．静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。（×）

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

2.3.3 算法设计题

1．设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。

【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，（也可以从高下标端开始一边比较，一边移位）然后插入x ，最后修改表示表长的变量。

int insert (datatype A[],int *elenum,datatype x) elenum为表的最大下标*/

{if (*elenum==arrsize-1) return 0; 法插入*/

else {i=*elenum;

while (i>=0 && A[i]>x)

边移动*/ {A[i+1]=A[i]; i--; }

A[i+1]=x;

/*找到的位置是

/*边找位置

/*表已满，无 /*

设

插入位的下一位*/

(*elenum)++;

return 1; } }

时间复杂度为O(n)。

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

【提示】对顺序表A，从第一个元素开始，查找其后与之值相同的所有元素，将它们删除；再对第二个元素做同样处理，依此类推。 void delete(Seqlist *A) {i=0;

while(ilast) 与其值相同的元素删除*/

{k=i+1;

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

k++;

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

/*将第i个元素以后

/*插入成功*/

不同的元素*/

n=k-i-1;

/*n表示要删除元

素的个数*/

for(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用来记录当前已删除元素的个数。

void delete(Seqlist *A,int x,int y) {i=0; n=0;

while (ilast)

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

}

介于x和y之间，n自增*/

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

/*否则向前移动

A->data[i]*/

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

}

4．线性表中有n个元素，每个元素是一个字符，现存于向量R[n]中，试写一算法，使R中的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间，元素移动次数最小。 【提示】对线性表进行两次扫描，第一次将所有的字母放在前面，第二次将所有的数字放在字母之后，其它字符之前。 int fch(char c)

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

int fnum(char c) 否数字*/

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

else return (0); }

void process(char R[n]) {low=0; high=n-1; while(low

/*将字母放在前面*/

/*判断c是

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

{while(low

while(low

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

}

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

{while(low

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

}

5．线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前m个元素和后n个元素进行整体互换。即将线性表： （a1, a2, … , am, b1, b2, … , bn）改变为： （b1, b2, … , bn , a1, a2, … , am）。 }

/*将数字放在字母后

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

{if(m<=n)

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

{x=L->data[0];

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

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

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

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

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

for(k=L->last-1;k>=0;k- -) L->data[k+1]=L->data[k]; L->data[0]=x; } }

6．已知带头结点的单链表L中的结点是按整数值递增排列的，试写一算法，将值为x 的结点插入到表L中，使得L仍然递增有序，并且分析算法的时间复杂度。 LinkList insert(LinkList L, int x) {p=L;

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而不改变其排序性。 LinkList Combine(LinkList A, LinkList B)

{C=A; rc=C; pa=A->next; pb=B->next; free(B);

头结点*/

while (pa && pb)

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

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

/*释放B的

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

if(pa->datadata)

{rc->next=pa; rc=pa; pa=pa->next; } else

{rc->next=pb; rc=pb; pb=pb->next; }

if(pa)

rc->next=pa;

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

else rc->next=pb;

链表C的表尾*/

return(C);

}

8．假设长度大于1的循环单链表中，既无头结点也无头指针，p为指向该链表中某一结点的指针，编写算法删除该结点的前驱结点。 【提示】利用循环单链表的特点，通过s指针可循环找到其前驱结点p及p的前驱结点q，然后可删除结点*p。 viod delepre(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中的当前结点，将其值进行比较，两者相等时，属于交集中的一个元素，两者不等时，将其较小者跳过，继续后面的比较。 LinkList Intersect(LinkList A, LinkList B)

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

C= (LNode *)malloc(sizeof(LNode)); C->next=NULL; r=C; p=A;

8．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为N1，N2和N3。与森林F对应的二叉树根结点的右子树上的结点个数是（D）。

A．N1 B．N1+N2 C．N2 D．N2+N3

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

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

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

debac，则先序遍历序列为（D）。

A．cbed B．decab C．deabc D．cedba 11．若一棵二叉树的先序遍历序列为abdgcefh，中序遍历的序列为dgbaechf，则后序遍历的结果为（D）。

A． gcefha B． gdbecfha C． bdgaechf D． gdbehfca 12．一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（B）。

A．所有的结点均无左孩子 B．所有的结点均无右孩子 C．只有一个叶子结点 D．是一棵满二叉树 13．引入线索二叉树的目的是（A）。 A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲

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

14．设高度为h的二叉树上只有度为０和度为２的结点，则此类二叉树中所包含的结点数至少为（B）。

A．2*h B． 2*h-1 C． 2*h+1 D．h+1 15．一个具有567个结点的二叉树的高h为（D）。

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

16．给一个整数集合{3，5，6，7，9}，与该整数集合对应的哈夫曼树是（B）。

A． B． C． D．

5.3.2 判断题

1．二叉树是树的特殊形式。（√）

2．由树转换成二叉树，其根结点的右子树总是空的。（√） 3．先根遍历一棵树和先序遍历与该树对应的二叉树，其结果不

3 5 6 7 9 3 5 3 5 9 7 6 6 7 3 5 6 7 9 9 同。（×）

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

5．完全二叉树中，若一个结点没有左孩子，则它必是叶子。（√） 6．对于有N个结点的二叉树，其高度为?log2N?＋1。（×） 7．若一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的先序遍历序列中的最后一个结点。（√）

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

9．不使用递归也可实现二叉树的先序、中序和后序遍历。（√） 10．先序遍历二叉树的序列中，任何结点的子树的所有结点不一定跟在该结点之后。（×）

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

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

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

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

15．用一维数组存放二叉树时，总是以先序遍历存储结点。（×） 16．由先序序列和后序序列能唯一确定一棵二叉树。（×）

17．由先序序列和中序序列能唯一确定一棵二叉树。（√） 18．对一棵二叉树进行层次遍历时，应借助于一个栈。（×） 19．完全二叉树可采用顺序存储结构实现存储，非完全二叉树则不能。（×）

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

1．一棵度为2的树与一棵二叉树有何区别？树与二叉树之间有何区别？ 【解答】

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

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

B C A 树。

D E F 2．对于图1所示二叉树，试给出：

G H (图 1)

（1）它的顺序存储结构示意图； （2）它的二叉链表存储结构示意图； （3）它的三叉链表存储结构示意图。 【解答】

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

A B C D E F ^ ^ ^ G ^ ^ H

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

^ D ^ B E ^ ^ F ^ H ^ A C ^ ^ D ^ ^ G ^ B E ^ A ^ C ^ ^ F ^ H ^

^ G ^ 3．对于图2所示的树，试给出： B A C F H J E K D M I N （1）双亲数组表示法示意图； G （2）孩子链表表示法示意图； (图 2) （3）孩子兄弟链表表示法示意图。 【解答】

（1）双亲数组表示法示意图： （2）孩子链表表示法示意图：

0 1 2 3 4 5 6 7 8 9 10 11 12 A B C D E F G H I J K M N -1 0 0 2 2 1 1 5 2 4 4 3 8 0 1 2 3 4 5 6 7 8 9 10 11 12 A B C D E F G H I J K M N 12 ^ 1 5 3 11 ^ 9 7 ^ 2 ^ 6 4 10 ^ 8 ^

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

D G B E H J I A C F 编码比等长编码使电文总长压缩多少？ （1）哈夫曼树：

0 0 1.00 1 1 0 0.41 0.59 1 0.28 1 0.12 0 a：10 b：110 c：010 d：1110 e：011 f：00 g：1111

0.20 0 0.21 1 0.11 0.10 0.31 0 0.16 0.80 1 0.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 当二叉树非空

int count(BiTree root)

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

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

2．请设计一个算法，要求该算法把二叉树的叶结点按从左至右的顺序链成一个单链表。二叉树按lchild-rchild方式存储，链接时用叶结点的rchild域存放链指针。

【提示】这是一个非常典型的基于二叉树遍历算法，通过遍历找到各个叶子结点，因为不论前序遍历、中序遍历和后序遍历，访问叶子结点的相对顺序都是相同的，即都是从左至右。而题目要求是将二叉树中的叶子结点按从左至右顺序建立一个单链表，因此，可以采用三种遍历中的任意一种方法遍历。这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。

LinkList head,pre=NULL; LinkList InOrder(BiTree T)

/*中序遍历二叉树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->rchild); 树*/

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

3．给定一棵用二叉链表表示的二叉树，其根指针为出求二叉树的深度的算法。 【提示】采取递归算法。

int Height(BiTree root) { int hl,hr;

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

hr=Height(root->rchild); if (hl>hr) return (hl+1); else return(hr+1); }

}

/*中序遍历右子

/*设置链表尾结点*/

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

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

其双亲结点的层次数＋1

void fun (BiTree root, int n) { if (t==NULL) return;

else{ printf(―%d‖,n);

fun(root->lchild,n+1); fun(root->rchild,n+1);

} }

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

5．给定一棵用二叉链表表示的二叉树，其根指针为root，试写出将二叉树中所有结点的左、右子树相互交换的算法。

【提示】设root 为一棵用二叉链表存储的二叉树，则交换各结点的左右子树的运算可基于后序遍历实现：交换左子树上各结点的左右子树；交换左子树上各结点的左右子树；再交换根结点的左右子树。

void Exchange(BiTree root) { BiTNode *p;

if (root)

{ Exchange(root->lchild);

Exchange(root->rchild); p=root->lchild;

root->lchild=root->rchild;

root->rchild=p; }

11．编写算法判定两棵二叉树是否相似。所谓两棵二叉树s和t相似，即要么它们都为空或都只有一个结点，要么它们的左右子树都相似。

【提示】两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左右子树是否相似，采用递归算法。 int Similar(BiTree s, BiTree t)

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

else if(!s && t || s && !t) return (0); else

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

&&

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

12．写出用逆转链方法对二叉树进行先序遍历的算法。 【提示】用逆转链的方法遍历二叉树，不需要附加的栈空间，而是在遍历过程中沿结点的左右子树下降时，临时改变结点lchild或者rchild的值，使之指向双亲，从而为以后的上升提供路径，上升时再将结点的lchild或者rchild恢复。

typedef struct tnode { datatype data;

int tag; /*tag的值初始为0，进入左子树时置1，从左子树回来时，再恢复为0*/

struct tnode *lchild, *rchild; } Bnode, *Btree;

void PreOrder(Btree bt)

{ Bnode *r, *p, *q; /*p指向当前结点，r指向p的双亲，q指向要访问的下一结点*/

if(bt==NULL) return; p=bt; r= NULL: while( p) { Visit(p); 点*/

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

{ p->tag=1; q=p->lchild; q=p->lchild=r; r=p; p=q; } else if(p->rchild) 入右子树*/

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

else {

/*上升*/

||

/*下降进

/*下降进入

/*访问p所指结

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

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

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

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

/*从

右子树回来*/

else { r->tag=0; q=r->lchild; r->lchild=p; p=r; r=q;}

树回来*/

if (r==NULL) return;

else { r->tag=0; q=r->rchild;

r->rchild= r->lchild; r->lchild=p;

p=q;

}

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

}

}

} }

13．对以孩子－兄弟链表表示的树编写计算树的深度的算法。 【提示】采用递归算法实现。 0 若树为空 树的深度＝

Max（第一棵子树的深度＋1，兄弟子树的深度） 若树非空

int high(CSTree T)

{ if (T==NULL ) return ( 0 ); /*若树为空，返回0*/ else { h1=high (t->lchild ); /**h1为T的第一棵子树的深度*/

h2=high(t->nextsibling ); /*h2为t的兄弟子树的深度*/

return(max(h1+1,h2)); } }

/*从左子树/*从左子

14．对以孩子链表表示的树编写计算树的深度的算法。 【提示】采用递归算法实现。

#define MAXNODE 树中结点的最大个数 int high(SNode t[MAXNODE],int j) { if(t[j].firstchild==NULL) return(1); 树*/

else { p=t[i].firstchild;

max=high(t,p->data); p=p->nextchild; while(p)

{ h=high(t,p->data); if(h>max) max=h; p=p->nextchild;

}

return(max+1);

}

}

/*若根结点没有子

1

树的深度＝

max(所有子树的深度)＋1

若根结点有子树

若根结点没有子树

15．对以双亲链表表示的树编写计算树的深度的算法。 【提示】从每一个结点开始，从下向上搜索至根结点，记录结点的层次数，其中的最大值就是树的深度。

int high(PNode t[ ], int n) /*求有n个结点的树t的深度*/ { maxh=0;

for (i=0 ;i

{ if (t[i].parent==-1 ) h=1; else { s=i;

h=1;

while (t[s].parent != -1 )

{ s=t[s].parent ;

h++;} }

if (h>maxh) maxh=h; }

}

return(maxh) ;

6.3.1 选择题

1．n条边的无向图的邻接表的存储中，边结点的个数有（A）。 A．n B．2n C．n/2 D．n*n

2．n条边的无向图的邻接多重表的存储中，边结点的个数有（A）。 A．n B．2n C．n/2 D．n*n 3．下列哪一种图的邻接矩阵是对称矩阵？（B）。

A．有向图 B．无向图 C．AOV网 D．AOE网

4．最短路径的生成算法可用（C）。

A．普里姆算法 B．克鲁斯卡尔算法 C．迪杰斯特拉算法 D．哈夫曼算法

5．一个无向图的邻接表如下图所示：

序号 vertex firstedge 0 1 2 3 v1 v2 v3 v4 1 0 1 0 ∧ 3 2 ∧ 3 ∧ 1 ∧

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