数据结构考研分类复习真题 第九章 答案[7]

．()散列表存储的基本思想是用关键字的值决定数据元素的存储地址

()散列表存储中解决碰撞的基本方法

① 开放定址法 形成地址序列的公式是Hi=(H(key)+di)% m其中m是表长di是增量根据di取法不同又分为三种

a．di =…m 称为线性探测再散列其特点是逐个探测表空间只要散列表中有空闲空间就可解决碰撞缺点是容易造成聚集即不是同义词的关键字争夺同一散列地址

b．di =… ±k(k≤m/) 称为二次探测再散列它减少了聚集但不容易探测到全部表空间只有当表长为形如j+(j为整数)的素数时才有可能

c．di =伪随机数序列称为随机探测再散列

② 再散列法 Hi=RHi(key) i=…k是不同的散列函数即在同义词产生碰撞时用另一散列函数计算散列地址直到解决碰撞该方法不易产生聚集但增加了计算时间

③ 链地址法 将关键字为同义词的记录存储在同一链表中散列表地址区间用H[m]表示分量初始值为空指针凡散列地址为i(≤i≤m)的记录均插在以H[i]为头指针的链表中这种解决方法中数据元素个数不受表长限制插入和删除操作方便但增加了指针的空间开销这种散列表常称为开散列表而①中的散列表称闭散列表含义是元素个数受表长限制

④ 建立公共溢出区 设H[m]为基本表凡关键字为同义词的记录都填入溢出区

O[m]

()用分离的同义词表和结合的同义词表解决碰撞均属于链地址法链地址向量空间中的每个元素不是简单的地址而是关键字和指针两个域散列地址为i(≤i≤m)的第一个关键字存储在地址空间向量第i个分量的关键字域前者的指针域是动态指针指向同义词的链表具有上面③的优缺点后者实际是静态链表同义词存在同一地址向量空间(从最后向前找空闲单元)以指针相连节省了空间但易产生堆积查找效率低

()要在被删除结点的散列地址处作标记不能物理的删除否则中断了查找通路

()记录 负载因子

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []