type
status
date
slug
summary
tags
category
icon
password
前言：
算法与数据结构第五次作业
目录：
一、二分查找算法的适用条件是什么？写出此算法。
条件：数据元素已经按照关键字排好序的有序表；顺序结构存放的。
算法：
二、索引顺序表的查找思想是什么？
索引顺序表是分块的表，块间有序，块内无序。
查找思想：建立索引表，查找时在索引表中确定要查找的元素在哪个块，再在此块内查找。
三、什么是二叉排序树？给出下面的一组数作为关键字所生成的二叉排序树。(45,24,50,10,35,96)
二叉排序树，或者是一棵空树，或者满足：左子树的关键字都小于根节点，右子树的关键字都大于根节点；左右子树又是二叉排序树。
四、输入一个正整数序列(40,28,6,72,100,3,54,1,80,91,38)，建立一棵二叉排序树，然后删除结点72，分别画出该二叉树及删除结点72后的二叉树。
<ins/>
五、什么是哈希函数？构造哈希函数的方法有哪些？处理哈希冲突的方法有哪些？
对关键字k设计一个函数f(k)，表示此关键字对应的地址，即使k与其地址f(k)对应，使得由关键字k可以直接找到其对应的地址，称函数为f(k)哈希（hash）函数。
构造哈希函数的方法有：直接定址法；数字分析法；平方取中法；折叠法；除留余数法；随机数法。
处理哈希冲突的方法：开放定址法；再哈希法；链地址法；建立公共溢出区。
六、已知一组关键字（19,14,23,1,68,20,84,27,55,11,10,79），哈希函数为：H(key)=key MOD 13，哈希表长为m=16。设每个记录的查找概率相等，用线性探测再散列处理冲突，即Hi=(H(key)+di)MOD m构造散列表。
冲突，
冲突， 冲突，
冲突，冲突，冲突，
冲突，冲突，
冲突，冲突，
冲突，冲突，3 冲突， 冲突，冲突， 冲突， 冲突，冲突，
七、给出以下术语的英文翻译：
• 图：Graph
• 顶点：Vertex
• 边：Edge
• 邻接表：Adjacency List
• 邻接矩阵：Adjacency Matrix
• 深度优先搜索：Depth-First Search(DFS)
• 广度优先搜索：Breadth-First Search(BFS)
• 最小（代价）生成树：Minimum(Cost)Spanning Tree
• 查找：Search
• 关键字：Primary key
• 二分查找：Binary Search
• 二叉排序树：Binary Sort Tree
• 哈希表：Hash Table
八、写出二叉排序树的查找算法。
九、输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），试完成：（1）按次序构造一棵二叉排序树；（2）依此二叉排序树，如何得到一个从大到小的有序序列？
(1)二叉排序树
(2) 从大到小的有序序列
二叉排序树的中序遍历（左→根→右）可以得到升序序列。如果要得到降序序列，只需进行反向中序遍历（右→根→左）。
十、设哈希表表长 m 为 20，哈希函数为 H(k)=k MOD 13，给定的关键值序列为{6,1,36,10,16,20,19,27,42,11}。试求出用线性探测法解决冲突时所构造的哈希表，并求出在等概率情况下，查找成功的平均查找长度 ASL。
(1) 构造的哈希表
(2) 平均查找长度：
<ins/>
- 作者:EageYren
- 链接:https://eageyren.edu.deal/learning/algorithm5
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
