9.1 在分块检索中，对256个元素的线性表分成多少块最好？每块的最佳长度是多少？若每块的长度为8，其平均检索的长度是多少？

9.2 设有关键码A、B、C和D，按照不同的输入顺序，共可能组成多少不同的二叉排序树。请画出其中高度较小的6种。

9.3 已知序列17，31，13，11，20，35，25，8，4，11，24，40，27。请画出由该输入序列构成的二叉排序树，并分别给出下列操作后的二叉排序树。

（1）插入数据9；（2）删除结点17；（3）再删除结点13

9.4 试写一算法判别给定的二叉树是否为二叉排序树，设此二叉树以二叉链表为存储结构，且树中结点的关键字均不相同。

9.5 设T是一棵给定的查找树，试编写一个在树T中删除根结点值为a的子树的程序。要求在删除的过程中释放该子树中所有结点所占用的存储空间。这里假设树T中的结点采用二叉链表存储结构。

9.6 含有12个节点的平衡二叉树的最大深度是多少（设根结点深度为10），并画出一棵这样的树。

9.7 试用Adelson插入方法依次把结点值为60，40，30，150，130，50，90，80，96，25的记录插入到初始为空的平衡二叉排序树中，使得在每次插入后保持该树仍然是平衡查找树。请依次画出每次插入后所形成的平衡查找树。

9.8 结点关键字k1，k2，k3，k4，k5为一个有序序列，它们的相对使用频率分别为p1=6，p2=8，p3=12，p4=2，p5=16，外部结点的相对使用频率分别为q0=4，q1=9，q2=8，q3=12，q4=3，q5=2。试构造出有序序列k1，k2，k3，k4，k5所组成的最优查找树。

9.9 证明Huffman算法能正确地生成一棵具有最小带权外部路枝长度的二叉树。

9.10 假设通讯电文中只用到A，B，C，D，E，F六个字母，它们在电文中出现的相对频率分别为：8，3，16，10，5，20，试为它们设计Huffman编码。

9.11 含有9个叶子结点的3阶B-树中至少有多少个非叶子结点？含有10个叶子结点的3阶B-树中至少有多少个非叶子结点？

9.12 编写在B-树中插入结点与删除结点的算法程序。

9.13用依次输入的关键字23、30、51、29、27、15、11、17和16建一棵3阶B-树，画出建该树的变化过程示意图（每插入一个结点至少有一张图）。

9.14设散列表长度为11，散列函数H（x）=x % 11，给定的关键字序列为：1，13，12，34，38，33，27，22。试画出分别用拉链法和线性探测法解决冲突时所构造的散列表，并求出在等概率的情况下，这两种方法查找成功和失败时的平均查找长度。

9.15设散列表为T[0..12]，即表的大小m=13。现采用再哈希法（双散列法）解决冲突。散列函数和再散列函数分别为：

H0（k）=k % 13、

Hi=（Hi-1+REV（k+1）%11+1）%13；i=1，2，…，m-1

其中，函数REV（x）表示颠倒10进制数的各位，如REV（37）=73，REV（1）=1等。若插入的关键码序列为{2，8，31，20，19，18，53，27}。

（1）试画出插入这8个关键码后的散列表。

（2）计算检索成功的平均查找长度ASL。