的特点是数据结构中元素的存储地址与其关键字之间存在某种映射关系。A.树形存储结构B.链式存

Question

的特点是数据结构中元素的存储地址与其关键字之间存在某种映射关系。

A．树形存储结构

B．链式存储结构

C．索引存储结构

D．散列存储结构

Answer 1

正确答案：D
解析：很显然，这是散列(hash)存储结构。散列存储结构将结点按其关键字的散列地址存储到散列表中。常用的散列函数有除余法、基数转换法、平方取中法、折叠法、移位法和随机数法等。两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。这种现象称为冲突或碰撞。发生冲突的两个关键字称为该散列函数的同义词。冲突的频繁程度除了与h相关外，还与表的填满程度相关。设m和n分别表示表长和表中填入的结点数，则将a=n/m定义为散列表的装填因子。a越大，表越满，冲突的机会也越大，通常取a≤1。解决冲突的方法是设法在散列表中找一个空位，通常有两类方法处理冲突，分别是开放定址法和拉链法。前者是将所有结点均存放在散列表T[0，…，m-1]中，后者通常是将互为同义词的结点链成一个单链表，而将此链表的头指针放在散列表T[0，…，m-1]中。