习题解答
1．请将算法4-1改为用while循环来实现。 答：改写的算法4-1可以是如下所示。
Concat_St(St1, St2) {
char St3[maxsize]; St3_len=0;
if (St1_len+St2_len>maxsize+1) {
printf(“两串长度之和超长！”); return(NULL); } else { i=1；
while (i<=St1_len) {
St3[i]=St1[i]; i++;
} j=1;
while (j<= St2_len) {
St3[j+St1_len]=St2[j]; j++;
}
St3_Len=St1_len+St2_len; St3[St3_len+1]= “\\0”; return(St3); } }
/* 新串放不下两个串 */
/* 创建一个新的顺序串为空 */
2．算法4-2也可以这样来描述，直接核对相应位置上的字符是否相同，然后再分别情况做出判断：一是有不相同的字符出现，一是有一个字符串比另一个字符串长，最后则是两个串完全相等。按照这样的设计，改写算法4-2。 答：按照这样的设计，算法4-2的描述如下。
Equal_St(St1, St2) { i=1;
while (St1[i] != “\\0”) {
if (St1[i] == St2[i]) /* 相等，继续比较 */ i++; else black; }
/* 不等，强制退出 */
/* 两串进行比较 */
- 17 -
习题解答
if (St1[i] != St2[i]) return (0); else {
if (St1[i] != “\\0” || St2[i] != “\\0”) /* 比较是由于长度不同而结束 */ }
return (0); else return (1);
/* 比较是由于相应位置上的字符不同而结束 */
}
3．算法：
Trans_St(St，ch1，ch2) { i=1；
While(St[i]！=\ {
if(St[i]==ch1) St[i]==ch2； i++； } }
是通过while循环来实现将顺序串St中所有的字符ch1改为字符ch2的。请改写成用for循环来实现相同的功能。 答：用for 循环改写的算法如下。
Trans_St(St, ch1, ch2) {
for (i=1; i<=St_len; i++) if (St[i] == ch1) St[i] = ch2; }
4．编写一个算法，将顺序串St中所有的大写字母全部换成小写字母。(提示：大写英文字母A~Z对应的ASCII码为65~90，小写英文字母a~z对应的ASCII码为97~122，在大写字母的ASCII码上加32，就是对应小写字母的ASCII码) 答：算法编写如下。
Catosm_St(St) {
for (i=1; i<=St_len; i++) if ((A<=St[i])&&(St[i]<=Z)) St[i]=St[i]+32; }
5．已知顺序串St，编写一个算法，将其中第i个字符开始连续的j个字符删除。（提示：先要判断所给参数是否合理，然后通过将第i+j开始往后的字符全部移动j个位置，完成删除的功能） 答：算法编写如下。
- 18 -
习题解答
Moveij(St, i, j) {
if (i+j<=St_len) {
for (k=i+j; k<=St_len; k++) /* 将i+j开始往后的所有字符前移j个位置 */ St[k-j]=St[k]; St_len=St_len-j; St[St_len]= “\\0”; } else
printf (“参数不合理，无法进行删除！”); }
/* 修改St的长度 */ /* 安放新的串结束符 */
6．在算法4-12的最后，为了释放被删结点使用的存储空间，先做了操作：
ptr->Next = NULL;
把由指针ptr指向的最后一个要释放空间的结点的Next域设置为NULL，然后通过while循环完成释放。其实，由于知道要释放空间的结点共有m个，因此可以取消这一操作，改用for循环通过m来控制释放空间的结点个数。请试着按照这一思路改写那一小段算法。 答：改写一小段算法如下。
for (j=1; j<=m; j++) { ptr=rtr; rtr=rtr->Next; free(ptr); }
7．编写一个算法，功能是复制一个链串。 答：复制一个完整的链串，是一件比较容易的事情。其算法起名为Copy_Lt()，参数为Lt1。具体编写如下。
Copy_Lt(Lt1) {
ptr=Lt1_h; rtr=malloc(size); rtr->Data=ptr->Data; Lt2_h=rtr; ptr=ptr->Next; while (ptr != NULL) {
qtr=malloc(size); qtr->Data=ptr->Data; rtr->Next=qtr; ptr=ptr->Next; }
rtr->Next=NULL; return(Lt2_h); }
- 19 -
习题解答
算法是通过while循环，不断修改指针ptr，以便指向链串Lt1的各个结点；指针rtr总是指向当前已形成的新链串Lt2的最后一个结点；用指针qtr指向刚申请到的新存储结点，并把它链入到rtr所指结点的后面。 8．已知两个mⅹn的矩阵A和B。编写一个算法，求C=A+B。即C也是一个mⅹn的矩阵，其元素满足条件：
cij = aij + bij（1≤i≤m，1≤j≤n）
答：算法名为Add_Mt()，参数为A，B，C。
Add_Mt(A, B, C) {
for (i=1; i<=m; i++) for (j=1; j<=n; j++) C[i][j] = A[i][j] + B[i][j]; }
第5章习题解答（此处树的高度不计算根节点）
一、填空
1．结点数为7的二叉树的高度最矮是 2 ，最高是 6 。 2．给定二叉树的结点数，要使树高为最大，那么该树应该是 单枝 形状。
3．给定二叉树的结点数，要使树高为最矮，那么该树应该是 完全二叉树 形状。 4．如果一棵满二叉树的深度为6，那么它共有 127 个结点，有 64 个叶结点。 5．有15个结点的二叉树，最少有 1 个叶结点，最多有 8 个叶结点。 6．由n个带权值的叶结点生成的哈夫曼树，最终共有 2n-1个结点。 7．将一棵完全二叉树按层次进行编号。那么，对编号为i的结点，如果有左孩子，则左孩子的编号应该是 2i ；如果有右孩子，则右孩子的编号应该是 2i+1 。 8．若二叉树共有n个结点，采用二叉链表存储结构。那么在所有存储结点里，一共会有 2n 个指针域，其中有 n+1 个指针域是空的。 9．深度为5的二叉树，至多有 31 个结点。 10．在二叉树中，有一个结点具有左、右两个孩子。那么在中序遍历序列里，它的右孩子一定排在它的 右 边。
二、选择
1．在所给的4棵二叉树中， C 不是完全二叉树。
2．把一棵深度为3的左单支二叉树改造成完全二叉树时，要增添 D 个空结点。 A．10 B．8 C．6 D．4 3．设有一棵5个结点的二叉树，其先序遍历序列为：A-B-C-D-E，中序遍历序列为：B-A-D-C-E，那么它的后序遍历序列为 B 。 A．A-B-D-E-C B．B-D-E-C-A C．D-E-C-A-B D．A-B-C-D-E
- 20 -