A E(前） L M E（后） P X A E(前） L E（后） M P X
A E(前） E（后） L M P X
A E(前） E（后） L M P X
A E(前） E（后） L M P X
A E(前） E（后） L M P X
第82页 习题3.2 4
因为文本中只有一个以G开头的情况，文本的字符个数是47个，而模式为6个字符子串，所以比较次数为47-6+1=42个。
第87页 习题3.3 2
注意实线上只要计算两者的差值就可以。 可以. 算法的时间复杂度为O(nlog2n).
第93页 习题3.4 8
给出所给定的元素的所有可能的序列，找出按字符的大小递增的那个序列就是符合要求的排序。效率是n!.
98 习题3.5 1
a. 邻接矩阵
a b c d e f g a 0 1 1 1 1 0 0 b 1 0 0 1 0 1 0 c 1 0 0 0 0 0 1 d 0 1 0 0 0 1 0 e 1 0 0 0 0 0 1 f 0 1 0 1 0 0 0 g 0 0 1 0 1 0 0
邻接链表
a ->b->c->d->e b->a->d->f c->a->g d->a->b->f e->a->g f->b->d g->c->e
b. 深度优先查找遍历图：
从a开始深度优先查找顺序：
a->b->d->f->c->g->e
99 习题3.5 z 4
广度优先查找遍历图：
a->b->c->d->e->f->g
第四章 分治法
第135页 习题5.1 6 合并排序排序过程：
E X A M P L E E X A M P L E E X A M P E L A E X E L M P A E E L M P X
第135页 习题5.1 7
合并排序是稳定的排序算法。
第140页 习题5.2 1
快速排序的递归调用树如下：
第140页 习题5.2 3
快速排序算法不是稳定的排序算法。
因为相同元素排序前、后的次序不一定相同。
第144页 习题5.3 5
对于该二叉树，各种遍历算法的结果如下： a. 先序：abdecf b. 中序：dbeacf c. 后序：debfca
习题5.3 8 a.
2 3 8 9 0 7 5 1 4 6
b. 中序：3 0 5 1 n-1
后序：5 3 0 1 n-1
后序排列的最后一个元素必须是根节点。
// 第117页 习题4.6 3
第五章 减治法
105 习题4.1 7
插入排序过程如下：
E1 X A M P L E2 E1 X A M P L E2 A E1 X M P L E2 A E1 M P X L E2 A E1 L M P X E2 A E1 E2 L M P X
109 习题4.2 5 a、
拓扑排序结果： d, a, c ,b, g, e, f 或 d, a, b, g, e, c, f
b. 该图有一个环路， 所以无解
120 习题4.4 3
a. 要4次
总共有13个元素，最多需要比较键值的次数是 log2 13 +1 = x b. n=13;
第一次迭代 l=0; r=12; m=(0+12)/2=6 ;
第二次迭代： l=0, r=5, m=(0+5)/2=2 或 l=7, r=12 , m=(7+12)/2=9 第三次迭代： l=0, r=m-1=2-1=1; 或 l=3, r=5 m=(3+5)/2=4;
第四次迭代： l=0, r=0; m-1=2-1=1; 或 l=3, r=5 m=(3+5)/2=4;
c. log2 13 d. log2 (13 +1)
121习题4.4 4