4、设有序顺序表为 { 10, 20, 30, 40, 50, 60, 70 }，采用折半搜索时，搜索成功的平均搜索长度是多少？ 答案：
ASLsucc = (1*1 + 2*2 + 3*4 ) / 7 = 17 / 7
5、 在结点个数为n(n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？
答案：结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1,有n层；它有1个叶结点，n-1个分支结点。
6、 一棵高度为h的满k叉树有如下性质: 第h层上的结点都是叶结点, 其余各层上每个结点都有k棵非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从1开始对全部结点进行编号, 试问:
(1) 各层的结点个数是多少?
(2) 编号为i的结点的父结点(若存在)的编号是多少? (3) 编号为i的结点的第m个孩子结点(若存在)的编号是多少?
(4) 编号为i的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少? (5) 若结点个数为 n, 则高度h是n 的什么函数关系?
答案：
（1）各层的结点个数是ki (i=0,1,2,....,h)
（2）编号为i的结点的父结点(若存在)的编号是└ (i+k-2)/k」 （3）编号为i的结点的第m个孩子结点(若存在)的编号是(i-1)*k+m+1
（4）当(i-1)%k<>0时有右兄弟， 右兄弟的编号为 i+1
（5）若结点个数为 n ，则高度h和n 的关系为：h=logk(n*(k-1)+1)-1 (n=0时h=-1)
7、 写出下列中缀表达式的后缀形式：
(1) A* - B + C
(2) (A + B) * D + E / (F + A * D) + C (3) A && B|| ! (E > F) {注：按C++的优先级) (4) !(A && !( (B < C)||(C > D) ) )||(C < E)
答案：各中缀表达式的后缀形式如下： （1）AB-*C+ (2)AB+D*EFAD*+/+C+ (3)AB&&EF>!|| (4)ABC
8、 画出下列广义表的图形表示和它们的存储表示：
(1) D(A(c), B(e), C(a, L(b, c, d))) (2) J1(J2(J1, a, J3(J1)), J3(J1))
答案：广义表（1）的图形表示为： A D C a b L c d
c B e
广义表（2）的图形表示为： J1
J2 a J3 广义表（1）的存储表示为： A D 0 D 2 2 2 ^ B 0 A 1 C ^ 0 B 1 e ^ C L 0 L 1 b 1 C 1 d ^ 0 C 1 a 2 ^ 广义表（2）的存储表示为：
J1 0 J1 2 2 ^
J2 0 J2 2 1 a 2 ^
9、题目：11、将下面的森林变换成二叉树（7分）。 B
J3 0 J3 2 ^ A C D E F H G I J K
答案：
A B E C F G D H I
J
K 10、将算术表达式 ((a+b)+c*(d+e)+f)*(g+h) 转化为二叉树。（答案：
* + + + f g h + * a b c +
d e 11、根据所给有向图，写出一个拓扑序列。（5分）
3
1 4 6 7分）
答案：
其中的一个拓扑序列为：V1，V2，V3，V4，V5，V6，V7 12、 将给定的图简化为最小的生成树，要求从顶点1出发。（7分）
2 8 1 5 3 15 7 7 5 3 10 12 6 9 4 2
6 答案:
13、某子系统在通信联络中只可能出现8种字符，其出现的概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11试设计赫夫曼编码。 答案：
6 6 2 3 1 5 3 4 7 2 7 15 5