对包含n个元素的散列表进行查找,平均查找长度为()。
A.不直接依赖于n
B.O(n2)
C.O(log2n)
D.O(n)
A.不直接依赖于n
B.O(n2)
C.O(log2n)
D.O(n)
对包含n个元素的散列表进行查找,平均查找长度()。
A.为O(log2n)
B.为O(n)
C.不直接依赖于n
D.直接依赖于表长m
A.23/8
B.20/8
C.17/8
D.14/8
已知一个线性表为(38,25,74,63,52,48),假定采用H(K)=K mod 7计算散列地址进行散列存储,若利用线性探测的开放定址法处理冲突,则在该散列表上进行查找的平均查找长度为();若利用链地址法处理冲突,则在该散列上进行查找的平均查找长度为()。
A.1.5,1
B.1.7,3/2
C.2,4/3
D.2.3,7/6
在地址空间为0~16的散列区中,对以下关键字序列构造两个散列表:
1)用线性探测开放定址法处理冲突;
2)用链地址法处理冲突。
并分别求这两个散列表在等概率情况下查找成功和不成功的平均查找长度。设散列函数为H(key)=i/2,其中i为关键字中第一个字母在字母表中的序号。
查找
实验目的:
(1)掌握顺序查找、二分查找的递归及非递归算法。
(2)掌握散列表上的各种操作。
(3)熟练掌握在二叉排序树上各种操作的实现方法。
(4)掌握和理解本实验中出现的一些基本的C语言语句。
(5)体会算法在程序设计中的重要性。
实验内容:
(1)给出顺序表上顺序查找元素的算法。
(2)给出非递归的二分查找算法。
(3)编写拉链法处理冲突的查找程序。
假定对有序表:(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找,试回答下列问题:
①画出描述折半查找过程的判定树;
②若查找元素54,需依次与哪些元素比较?
③若查找元素90,需依次与哪些元素比较?.
④假定每个元素的查找概率相等,求查找成功时的平均查找长度。
设散列表的长度为13,散列函数为H(K)=K%13,给定的关键字序列为19,14,23,1,68,20,84,27,55,11,10,79。试画出分别用链地址法和线性探测法解决冲突时所构造的散列表,并求等概率下这两种方法的成功和不成功的平均查找长度。