1 0 0 0 0 1 1 0 1 0 1) A B C D E /\\ 3 0 4 0 /\\ 3 2 /\\ /\\ 4 3 /\\ /\\
0 1 /\\ 0 1 0 0 1 0 0 0 0 0 A 0 B 0 C 0 D 1 E 1 0 A 1 B 2 C /\\ 3 D 4 E 1 2 0 0 2) 2 /\\ 3 /\\ 2 /\\ 3 /\\ 0 A 1 B 2 C 3 D 4 E /\\ 3 0 /\\ 0 1 3) 4 /\\ 1 4 /\\ 3 /\\ 0 2 /\\ 1 2 1 3 /\\ 4)
0 A 1 B 2 C 3 D 4 E /\\ 0 4 0 1 0 2 1 2 1 3 /\\ 1 4 2 3 /\\ 2 4 /\\ 3 4 /\\ 5)
错误！未找到引用源。
分析：画出搜索树，写出结果。
(a) 深度优先搜索：ABCDE，广度优先搜索：ABCDE； (b) 深度优先搜索：ABCDE，广度优先搜索：ABCED。
错误！未找到引用源。 0 A 3 2 /\\ 1 B 2 C 3 D 4 E /\\ 0 /\\ 0 4 1 /\\ 1 2 /\\ 分析：这里用邻接表给出了图的存储结构，同时确定了邻接点的先后关系。仍然采用搜索树分析。 深度优先遍历结果：ADEBC。
错误！未找到引用源。 参考错误！未找到引用源。。
错误！未找到引用源。 参考错误！未找到引用源。。
错误！未找到引用源。 参考课本P173。
错误！未找到引用源。 3 B 1 3 5 A 1 C 2 3 4 F V-U D 2 3 E 普里姆算法： U U到V-U中各顶点的最小代价 最小代B C D E F 价边 {A} {B,C,D,E,F} AB/3 AC/1 AD/2 ∞ ∞ AC/1 {A,C} {B,D,E,F} AB/3 AD/2 CE/5 CF/4 AD/2 {A,C,D} {B,E,F} AB/3 CE/5 DF/2 DF/2 {A,C,D,F} {B,E} AB/3 FE/3 AB/3 {A,C,D,F,B} {E} BE/1 BE/1 {A,C,D,F,B,E} {} 克鲁斯卡尔算法：
依次选择代价最小的边：AC, BE, AD, DF，然后，可以选择AB或BC或EF即可。 最小生成树的总代价是9。
错误！未找到引用源。 A B C D E F G 分析：可能的拓扑有序序列有多种，A之后可能是B或D，逐渐类推可得到所有可能的拓扑序列：ADBCGFE, ABDCGFE, ABCDGFE, ABCGDFE, ABCGFDE, ABCGFED，共6种。
错误！未找到引用源。
1 3 2 5 7 2 2 2 3 9 5 1 3 8 2 3 事件 v1 v2 v3 最早发生时间ve 0 2 5 最晚发生时间vl 0 7 5 活动 a(1,2) a(1,3) a(1,4) 4 1 5 6 最早开始时间e 0 0 0 最晚开始时间l 5 0 2
v4 3 5 a(2,5) 2 7 v5 8 8 a(3,5) 5 5 v6 5 6 a(3,6) 5 6 v7 11 11 a(4,6) 3 5 v8 11 11 a(5,7) 8 8 v9 13 13 a(5,8) 8 9 a(6,8) 5 6 a(7,8) 11 11 a(7,9) 11 11 a(8,9) 11 11 整个工程完工需要13天，关键路径有1?3?5?7?8?9和1?3?5?7?9。
错误！未找到引用源。
8 A B 6 4 2 3 F C 3 2 6 5 E D 1 终点 B C D E F 最短路径 8 AB 从A到各顶点的最短路径 8 AB 6 ADEB 6 ADEB 7 ADFC ADFC ∞ 2 AD 8 ADC 8 ADC 7 ADF 3 ADE 4 ADF 7 ADEB ADFC ∞ 6 AF 4 3 AD ADE 2 4 ADF 6 错误！未找到引用源。 3 A 5 D 2 1 2 B 4 C 0 3 BA ∞ 2 AC ∞ ∞ 2 CD 0 3 BA ∞ 2 AC ∞ ∞ 0 3 BA ∞ 2 AC ∞ ∞ 2 CD 0 4 CB ∞ 0 ∞ 2 A(0)
0 5 0 4 CB 5 BAC ∞ 5 DA 1 DB 0 0 BAC ∞ 4 0 2 CB CD 5 1 7 0 DA DB DAC A(1) 0 7 CBA 0 4 DBA 1 DB 6 DBAC 0
4 ACD A(2) 6 4 5 2 ACB AC ACD 3 0 5 7 BA BAC BACD 7 4 0 2 CBA CB CD 4 DBA 1 DB 6 DBAC 0 ACDB AC 3 0 5 BA BAC 6 3 0 CDBA CDB 4 1 6 DBA DB DBAC 7 BACD 2 CD 0
A(3) A(4)
错误！未找到引用源。
分析：等概率情况下查找成功时ASL = (n+1)/2 = 5.5；若查找失败的概率为0.2，则ASL = 0.8×(10+1)/2 + 0.2×11 = 6.6。
技巧：可以用归纳法。查找第1个元素比较10个关键字，查找第2个元素比较9个关键字，……，查找第10个元素比较1个关键字，总共比较10+9+…+1=55个关键字，ASL=55/10=5.5。 提示：以上分析都是按照课本上的算法，如果遇到其他具体算法还需要具体分析。①
错误！未找到引用源。
分析：画出判定树进行分析、计算。 8 4 2 6 12 10 14 1 3 5 7 9 11 13 15 技巧：不断计算区间的中点下标(即两端下标之和除以2)作为根结点，最终画出判定树。
ASL = (1×1+2×2+4×3+8×4)/15 = 49/15。查找第3个元素需要比较4个关键字，即第8、4、2和第3个。
错误！未找到引用源。
分析：比较8个关键字才能找到的元素位于判定树的第8层。对长度为1023的有序表折半查找的判定树有10层，第1至8层应该是满二叉树，所以恰好比较8次才找到的有27 = 128个，至多比较8次就能找到的是位于判定树第1至8层所有结点，共28-1 = 255个。
错误！未找到引用源。
①
按照课本上的算法，查找从后往前进行，所以查找第1个元素要比较10个关键字。查找失败时，由于和“哨兵”记
录多比较了1次，所以需要比较11个关键字。
分析：相当于索引顺序表的查找，当采用顺序查找时为使平均查找长度最小，应该划分成sqrt(n) = 100块。具体分析参见“错误！未找到引用源。错误！未找到引用源。”。
错误！未找到引用源。
思路：根据中序遍历序列是否升序来判断。 非递归算法：
bool IsBinarySortTree ( BinTree bt ) {
InitStack(S);
p = bt; pre = 0; // pre保持为p的中序前驱 while ( p or ! StackEmpty(S) ) { if ( p ) {
Push(S, p); p = p->lchild; } else {
p = Pop(S);
if ( pre and (p->data <= pre->data) ) return false; // 不是二叉排序树 pre = p; // 记下前驱结点 p = p->rchild; } }
return true; // 二叉排序树 }
递归算法：
bool IsBinarySortTree ( BinTree bt ) {
pre = NULL;
return IsBST ( bt, pre ); // 调用递归算法 }
// 判断二叉树bt是否是二叉排序树，pre是bt的前驱结点 bool IsBST (BinTree bt, BinTree &pre ) {
if ( bt==0 ) return true; // 空树是二叉排序树 else {
if ( not IsBST(bt->lchild, pre) ) return false; // 左子树
if ( pre and (bt->data <= pre->data) ) return false; // 根结点 pre = bt; // 保持前驱结点
if ( not IsBST(bt->rchild, pre ) ) return false; // 右子树 return true; } }
错误！未找到引用源。
