1.
表的查找效率取决于散列函数、处理冲突的方法和装填因子。显然，冲突的产生概率与装填因子（表中记录数与表长之比）的大小成正比，即装填得越满越容易发生冲突，
采用合适的处理冲突的方式避免产生聚集现象，也将提高查找效率，例如用拉链法解决冲突时就不存在聚集现象，用线性探测法解决冲突时易引起聚集现象，
2.
哈希法把要存储的值映射成哈希值，根据hash值寻址存储，查找的时间复杂度为O（1）
但也可能出现不同的数据映射成相同的hash值的情况，这是哈希冲突。设计的比较好的哈希函数能够减少哈希冲突，但是冲突是不可避免的，冲突造成查找的时间增加，因此我们普通的哈希表并不放满，而是定义一个负载因子。就是哈希表的容量除以哈希表的长度，一般为0.7左右。
影响哈希表查找速度的不是元素个数，而是负载因子。
3.
线性探测：本位置x被占据，就寻找下一位x+1，直至找到空位置，所以：
（注意看清题目“K的第一个字母在字母表中的序号”）
D=4mode11=4，1次
B=2mod11=2，1次
T=20mod11=9，1次
M=13mod11=2->3，2次
C=3mod11=3->4->5，3次
I=9mod11=9->10，2次
K=11mod11=0，1次
X=24mod11=2->3->4->5->6，5次
T=20mod11=9->10->0->1，4次
9个数字，共20次，所以20/9。
4. 问的是“至少”，那么设表原来为空表。 第一个：直接找到坑，入坑，1次； 第二个：和第一个同hash，找到坑被第一个给占了，找下一个，入坑，2次； 第三个：第一个被占了，第二个也被占了，找第三个，入坑，3次； 。。。 第n个：n次； 一共：（1+n）*n / 2 次 【开放地址法（除了随机探测）都是（1+n）*n / 2 次】
5.
有序表中所有元素以递增或递减方式排列，对数据之间的关系进行了描述，是一种逻辑结构。
顺序表是指用一组地址连续的存储单元依次存储数据元素的线性结构。
哈希表 用散列法存储的线性表叫散列表。
单链表 用一组地址任意的存储单元存放线性表中的数据元素，均只是一种存取结构，不是逻辑结构。
6.
栈可以是顺序存储，也可以是链式存储，与存储结构无关。循环队列是队列的顺序存储结构，链表是线性表的链式存储结构，用散列法存储的线性表叫散列表，都与存储结构有关
网友评论