数据结构实验:开放地址法哈希与二叉排序树操作

3 下载量 175 浏览量 更新于2024-09-09 收藏 20KB DOC 举报
本资源包含了三道关于数据结构的编程练习题目,针对不同的数据结构和算法进行实战操作。 1. **问题A - 开放定址法处理冲突的哈希表**: 这是一道关于哈希表的题目,要求使用哈希函数H(k) = (3k) % 11,以及开放定址法解决哈希冲突。具体规则是通过di = i * ((7k) % 10 + 1)来确定散列地址。你需要根据给定的0~10的散列地址空间和关键字序列构建哈希表,并计算查找每个关键字的实际比较次数,最后输出平均查找长度。例如,输入序列224153463013167的平均查找长度为2.125。 2. **问题B - 判定二叉排序树**: 本题考查二叉排序树的性质判断。你需要编写一个程序,输入二叉树的先序遍历序列,判断其是否为二叉排序树。如果是,输出"It is an BinaryOrderTree!",反之则输出"It is not an BinaryOrderTree!"。输入样例532004007600800的二叉树满足排序条件,输出结果为一个有序的中序遍历序列和确认信息。 3. **问题C - 二叉排序树的操作**: 这个题目涉及二叉排序树的常见操作:查找、删除和插入。以后续继线索链表作为存储结构,你需实现以下功能: - 查找:找到所有大于a且小于b的键值,若不存在则输出"Not Found"。 - 删除:删除给定的键值,返回删除节点后的中序遍历结果,如果要删除的节点不存在,则输出原始二叉树的中序遍历。 - 插入:在删除的基础上,将新的键值插入到树中,同样考虑重复插入的情况,输出插入后的中序遍历。 这些题目综合考察了学生对哈希表的实现、二叉排序树的理解,以及基本的查找、删除和插入操作的编程能力。通过解决这些问题,学生可以加深对数据结构如哈希表和二叉树的理论知识与实际应用的理解,同时提高编程技能。