数据结构课后习题答案（修订版）(4)

{

int pos; int p;

int lenthOfStra=sizeof（a）/sizeof（char）;/*a串的长度*/ int lenthOfStrb=sizeof（b）/sizeof（char）;/*b串的长度*/ for（pos=0;pos< i-1;++pos）;/*pos指向位置i-1，注意数组下标开始于0*/

for（p=lenthOfStra-1;p>=pos;--p） {

a[p+LenthOfStrb]=a[p];/*给串b让出足够的空间*/ }

for（p=0;p<=lenthOfStrb-1;） {

a[pos++]=b[p++];/*将串b插入到串a对应的位置*/ } }

void delete（char *a,char *b） {

int lenthOfStra=sizeof（a）/sizeof（char）;/*a串的长度*/ int lenthOfStrb=sizeof（b）/sizeof（char）;/*b串的长度*/ /*调用KMP算法确定串a中首次出现串b的位置并赋值给pos*/

int pos=KMPIndex（char*a,char*b）; int p;

for（p=pos+lenthOfStrb;p<=lenthOfStra-1;++p） {

a[p-lenthOfStrb]=a[p]; }

a[p-lenthOfStrb]= ?\\0?; }

习题六答案

1．判断题

（1）╳（2）╳（3）√（4）╳（5）√（6）√（7）√ 2．单选题

（1）B （2）C （3）E，A，B （4）C （5）D

习题七答案

1． 判断题

（1） √（2）√（3）╳（4）╳（5）╳（6）╳（7）╳（8）√（9）╳ 2．单选题

（1）B（2）B（3）A（4）D（5）B（6）C（7）A（8）B（9）D（10）C 3．(1) 参考答案：

（1） 由于树结点的孩子没有左右之分，所以三个结点的树的形态只有2种：

（2） 由于二叉树的结点孩子具有左右之分，所有四个结点的二叉树的形态有14种：

3.(2). 参考答案：

（1）顺序存储方法存储该二叉树示意图如下：

T： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 结点 A B C D E F G H （2）链接存储方法存储该二叉树示意图如下：

3.(3) 参考答案： 该二叉树如下所示：

(4). 参考答案：提示：叶子结点即度为0的结点，设叶子结点的个数为no，并设树中结点的总数为N，由此可以得到两个方程： no+n1+n2+n3+……+nm =N…………(1)

n1+2*n2+3*n3+……+m*nm =N-1…………(2)

解上面的方程组可得叶子结点的个数为：1+n2+2n3+3n4+……+(m-1) nm。

(5). 参考答案：

A A

B B

C C (a) (b)

A B

(6). 参考答案：

D C E F G H (c)

A B D E F C J I H M N G K O L P (7). 参考答案：

（1）前序序列：A B D E C F G H I J K L M N O P（等于与之对应的二叉树的先序遍历） （2）后序序列：E D B G F C A J K L I H P O N M（等于与之对应的二叉树的中序遍历）

(8). 参考答案：

63 28 35 14 14 15 20 7 7 3 4 经过计算该哈夫曼树的WPL值为：（3+4）*4+7*3+（14+15+20）*2=147

4.1. 算法设计思想：对该二叉树进行中序遍历，将遍历结果存放于一个一维全局数组中，再判断该数组中的数据是否由小到大排列，如果是则该二叉数为一棵二叉排序树。

int order[maxsize]; /*定义一个全局数组，其中maxsize为该二叉树的最大结点个数*/ int i=0; /*定义一个记位指针i*/

typedef struct BtreeNode /*定义一个二叉树的结点*/ {

int data;

struct BTreeNode *lchild; struct BTreeNode *rchild; } *Btree;

/*中序递归遍历二叉树T*/ void Inorder(Btree T) { if(T= =NULL)

return; /* 递归出口*/ /*中序递归遍历二叉树T->lchild*/ if(T->lchild!=NULL) Inorder(T->lchild); order[i++]=T->data; /*将访问到的结点放入数组中，并对记位指针i加一*/ /*中序遍历二叉树T->rchild */ if(T->rchild!=NULL) Inorder(T->rchild); }