一般练习

1. 复习下面概念：数据存储和访问，检索（查找），检索码（关键码），关联数据，字典（查找表，映射，关联表），静态字典，动态字典，平均检索长度，索引，关联，有序集合，二分法检索，判定树，散列表（哈希表），散列，散列函数（哈希函数，杂凑函数），冲突（碰撞），同义词，负载因子，数字分析法，折叠法，中平方法，除余法，基数转换法，内消解技术，外消解技术，开地址法，探查序列，线性探查，双散列探查，溢出区方法，桶散列，拉链法，集合和元素，属于关系，全集，外延表示，内涵表示（集合描述式），基数，空集，并集，交集，补集，排序线性表，位向量，二叉排序树，最佳二叉排序树，动态规划，带权路径长度，平衡二叉排序树（AVL树），平衡因子，失衡和调整，多分支排序树，B树，B＋树，结点分裂和合并。

2. 采用简单线性表实现集合时，可以考虑保持或者不保持元素的唯一性。请分析采用这两种不同技术时各主要操作的效率，以及存储占用方面的性质。

3. 假设公共超集 = {a, b, c, d, e, f, g, h, i, j, k, l, m, n}，请用位向量表示：

a) = {a, d, f, g, h, i, m}， = {b, c, g, h, i, k, m, n}， = {a, b, d, f, g, h, n}

b) ，，，，

4. 设散列表字典中包含17个存储位置，用k % 17作为散列函数。请首先给定一组12个关键码的序列，采用下面冲突消解技术，画出将全部关键码存入后的状态：

a) 采用线性探查法消解冲突；

b) 采用另一函数k % 5的双散列技术消解冲突。

5. 将整数1, 2, 3按不同顺序插入一棵空的二叉排序树，总共可以产生出多少棵不同的二叉排序树？请画出这些二叉排序树。

6. 图8.24中是一棵二叉排序树，假定存入树理的关键码是1到9，请确定每个关键码的存储位置。

7. 将序列46, 78, 35, 99, 70, 48, 121, 10, 66, 54, 26依次插入一棵开始为空的二叉排序树。请画出全部插入完成时二叉树的情况，并求出在关键码检索概率相等的情况下，所有成功检索情况的平均长度。

8. 在前一题构造出的二叉排序树中删除关键码78, 66, 46, 70, 121，请画出每一步删除后二叉排序树的情况。

9. 哪些关键码插入序列可以生成图8.25中的二叉排序树？请列出所有满足条件的序列。

10. 给定关键码集合 {Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec}，采用字典序。请完成下面工作：

a) 将上述关键码顺序插入空二叉排序树，画出结果，求出其平均检索长度；

b) 将上述关键码顺序插入空AVL树，画出结果，求出其平均检索长度。

11. 设有关键码a, b, c, d, e，且有，，，。请做出相应的最佳二叉排序树。

12. 设有关键码1，2，……，20，请画出一棵4阶B树，其中包含这些关键码。再请画出一棵4阶B+树，其中包含这些关键码。

13. 请设计一个算法，在给定的二叉排序树里找到两个不同关键码所在结点的最小公共祖先，也就是距离这两个结点最近的公共祖先结点。

编程练习

1. 请基于简单顺序表定义一个字典类，实现各种操作。

2. 请基于第1题定义的类，派生出一个采用二分法检索的字典类。首先弄清需要重新定义哪些操作，而后在派生类里定义它们。

3. 请基于简单线性表定义一个集合类，实现各种操作。

4. 请基于排序线性表的概念定义一个集合类。可以考虑从第3题定义的类派生，或者完全重新定义，实现重要的集合运算。

5. 请基于散列表结构实现一个集合类，定义重要的集合操作。

6. 请实现一个二叉排序树字典，它允许关键码重复的项。如果插入时遇到同样的关键码，这种字典另行记录这个关键码和它关联的新数据。请考虑这种情况对整个字典设计的影响，以及在这种情况下的检索和删除操作。首先做出一个合理设计，并给出充分理由说明设计的合理性，而后实现这个字典类。

7. 修改8.6.1节定义二叉排序树字典类，使其初始化方法可以接受一个二叉树结点（及其关联子树）作为参数。为保证字典类正确工作，初始化方法需要检查所给参数及其子树是否构成合法的二叉排序树结构。请完成这个初始化函数。

扩充上述的初始化方法，使之也可以接受一个表（其元素是关键码/数据的关联）作为参数。初始化方法将把表中的项逐个插入排序树中。

8. 请给8.6.1节的二叉排序树字典类增加一个操作merge(self,another)，它把另一棵二叉排序树another的结点并入本排序树。采用递归方式比较容易定义好这一操作。希望操作的时间复杂性是O(n + m)，其中n和m是两棵树中的结点个数。注意，在归并后应该把another树里的根指针置空。

9. 第8.6.1节提出了一种二叉排序树的删除算法。请考虑与之不同的删除算法，要求能正确删除数据项，而且保证在任何二叉排序树上执行删除操作，树高度都不会增加。请实现所提出的算法，并从效率、删除效果等方面比较两个算法。

10. 第8.6.3节提出可以用三个字典取代构造最佳二叉排序树时使用的三个矩阵。请基于字典重新实现最佳二叉排序树的构造算法。

11. 第8.6.3节的最佳二叉树构造算法build_opt_btree完成后返回一对矩阵（两个两维的表）。请另外定义一个函数，其参数是内部结点和外部结点的权值表。它先调用上述函数构造出描述最佳二叉排序树的两个矩阵，然后根据矩阵中的信息，使用BinTNode结点对象构造出相应的二叉排序树。

12. 请收集你所在班级（或年级）的同学姓名，以此作为关键码设计一个散列字典（用一个固定大小的list作为基本存储）。由于姓名用是字符串，可以应用Python标准函数hash得到一个散列值，再通过取模将函数值归结到字典下标范围内。冲突消解采用双散列的方式，同样对姓名的hash值做散列。把字典的大小作为参数，以便统计负载因子从0.5变到1.0的不同情况下，在所有姓名插入字典过程中出现冲突的次数。