无序表：ASL=n+1；有序表：ASL=（n+1）/2+m；两者不相同。 9.3

5 2 8 1 3 6 9 ASL=1/10（1+2*2+4*3+3*44 7 10 ）=2.9 9.11

9.14

30 20 30 20 50 20 20 20 30 50 60 52 30 20

删除50后

50 60 20 30 50 60 68 70 50 52 20

60 70 52 20 60 删除68后 9.19

2643 54 1 02 7 1 0 3 6 3 1

0 1 2 3 4 5 6 7 8 9 1

0

ASL=（4*1+2*2+3+6）/8=17/8 9.25

int Search-Seq(SSTable ST, KeyType key){ //在顺序表ST中顺序查找其关键字等于key的数据元素，ST按关键字自大至小有序，

//若找到，则函数值为该元素在表中的位置，否则为0

ST.elem[ST.length+1].key=key;

for (i=1; ST.elem[i].key>key; ++i);

if (ST.elem[i].key==key)&&(i<=ST.length) return i

else return 0 ; }//Search-Seq 9.31

TelemType Maxv(Bitree T){

//返回二叉排序树T中所有结点的最大值 for (p=T; p->rchild; p=p->rchild); return p->data; }//Maxv

TelemType Minv(Bitree T){

//返回二叉排序树T中所有结点的最小值 for (p=T; p->lchild; p=p->lchild); return p->data; }//Minv

Status IsBST(Bitree T){ //判别T是否为二叉排序树 if (!T) return OK; else if

((!T->lchild)||((T->lchild)&&(IsBST(T->lchild)&&(Maxv(T->lchild)data)))

&&((!T->rchild)||((T->rchild)&&

(IsBST(T->rchild)&&(Minv(T->rchild)>T->data)))

return OK

else return ERROR; }//IsBST 9.33

Status OutputGEx(Bitree T, TelemType x){ //从大到小输出给定二叉排序树T中所有值不小于x的数据元素 if (T) {

if (OutputGEx(T->rchild, x)) if (T->data>=x) { print(T->data);