散列表的平均查询长度,看看哪出错了

的生产2022-10-04 11:39:541条回答

散列表的平均查询长度,看看哪出错了
关键码{38,25,74,63,52,48},有h（k）=k mod7,若利用开地址法处理冲突,散列表长度为7,则平均查找长度为?
建立散列表：
0 1 2 3 4 5 6
63 48 空 38 25 74 52
所以平均查找长度为（1+3+1+1+2+4）7=1.7

已提交，审核后显示！提交回复

共1条回复

烟熄了共回答了18个问题 | 采纳率94.4%: 小小的错误而已.平均查找长度=∑pi*ci,ci你都求对了,pi是指查找每个元素的概率,这里pi=1/6而不是1/7.6个元素,查找每个元素的概率为1/6.; 1年前

相关推荐

如果要求频繁的对线性表进行插入和删除操作,则线性表应该采用（）存储结构.A.散列B.顺序C.链式D.任意 天新新1年前1: 凉风瑟瑟刘洋共回答了10个问题 | 采纳率90%

用链式,不需要连续存储,插入和删除效率高

1年前查看全部

下面选项中关于哈希表的查找的说法错误的是（） A.如果计算的某个散列地址为空,则查找失败 下面选项中关于哈希表的查找的说法错误的是（） A.如果计算的某个散列地址为空,则查找失败 B.如果计算的某个散列地址为非空,则查找成功 C.必须通过哈希函数计算哈希地址 D.哈希表的查找无需进行关键字的比较 yeduwuren19811年前2: 我是老鲍共回答了14个问题 | 采纳率92.9%

d
B因为有链式结构的时候第一次是查不到的
D是因为有个数字分析法是需要关键字比较的
这个是北大青鸟数据结构与算法的考试题吧

1年前查看全部

哈希表：二次探测再散列给定关键字集合｛19,1,23,14,55,68,11,82,36｝构造哈希表,设哈希函数为H（k 哈希表：二次探测再散列 给定关键字集合｛19,1,23,14,55,68,11,82,36｝构造哈希表,设哈希函数为H（key）＝key MOD 11,表的长度为11,若采用线性探测再散列,则以下结果正确吗? 0 1 2 3 4 5 6 7 8 9 10 H(key) 55 1 23 14 68 11 82 36 19 那么采用二次探测再散列处理冲突的结果应该是怎样的（重点解释你是如何计算关键子11的位置的）? ff的十三1年前1: 凝碧旧池共回答了16个问题 | 采纳率100%

h(19)=8,h(1)=1,h(23)=1->2,h(14)=3,h(15)=0,h(68)=2->3->4,h(11)=0->1->2->3->4->5,h(82)=5->6,h(36)=3->4->5->6->7线性探测正确二次探测H(19)=8H(1)=1H(23)=1,h(23+1^2)=2H(14)=3H(55)=0H(68)=2,h(68+1^2)=3,h(68-1^2)=1,h(68+2^2)=6H(11)=0,h(11+1^2)=1,h(11-1^2)=10H(82)=5H(36)=3,h(36+1^2)=4

1年前查看全部

依次散列于地址0~6中,用线性探查法解决冲突,则得到的散列表为? 依次散列于地址0~6中,用线性探查法解决冲突,则得到的散列表为? 设散列函数为h(k)=k mod 7用线性探查法解决碰撞.现从空的散列表开始,依次插入关键码23,14,9,6,30,12,18,依次散列于地址0~6中,用线性探查法解决冲突,则得到的散列表为? quan_zi1年前1: chen198282 共回答了19个问题 | 采纳率84.2%

地址 0 1 2 3 4 5 6
键值 14 18 23 9 30 12 6
另外：1、一般较解决冲突,而不是叫解决碰撞；2、真的像上面这样做哈希表效率很差,因为填装因子太大.
最后,这么简单的题,找本数据结构的书一翻就有答案啦,还在这里问,不嫌麻烦吗?

1年前查看全部

设散列表长度为11,散列函数h(x)=x%11,给定的关键字序列为：1,13,12,34,38,33,27,22. 设散列表长度为11,散列函数h(x)=x%11,给定的关键字序列为：1,13,12,34,38,33,27,22. 分别用拉链法和线性探查发解决冲突时所构造的散列表,并求出在等概率情况下,这两种方法查找成功和失败时的平均长度,请问装填因子的值是什么? mary小鱼1年前1: bigmath 共回答了16个问题 | 采纳率93.8%

建立一个哈希表,每一位数据即为哈希地址,迭装填因子为0.7.用平方探测再散列方案解决冲突,并求ASL；
写出进行直接插入排序,简单选择排序,冒泡排序的每一趟结果,并写出快速排序进行一次划分后的结果；
(数据:1,3,7,1,0,6,8,8,0,2,0,8)
1.
①建立一棵二叉排序树
②建立一个哈希表,每一位数据即为哈希地址,迭装填因子为0.7.用平方探测再散列方案解决冲突,并求ASL；
③写出进行直接插入排序,简单选择排序,冒泡排序的每一趟结果,并写出快速排序进行一次划分后的结果；
④将每一位数据作为一个页面调用,若在分页方式下的内存分块数为5块,试求出当分别用FIFO和LRU方式进行页面淘汰时缺页中断率,要求有过程(用表面出过程);

1年前查看全部

对于线性表（7,34,55,25,64,46,20,10）进行散列存储时,若选用H（K）=K %9作为散列函数,则散列地 对于线性表（7,34,55,25,64,46,20,10）进行散列存储时,若选用H（K）=K %9作为散列函数,则散列地址为1的元素有（）个, A．1 B．2 C．3 D．4 qq黄果树1年前1: 玉匣启龙共回答了21个问题 | 采纳率95.2%

答案选D,4个.分别是：55,64,46,10.
H（K）= K%9,表示除以9的余数.由于地址重叠造成冲突,所以散列存储时,通常还要有解决冲突的办法,如线性探查法等等.

1年前查看全部

如题：假定一个待散列存储的线性表为（32,78,29,63,48,94,25,36,18,70,49,80）,散列地址空 如题：假定一个待散列存储的线性表为（32,78,29,63,48,94,25,36,18,70,49,80）,散列地址空间为HT[13] 若采用除留余数法构造散列函数和链接法处理冲突,求出平均查找长度? 饰品网转让1年前0: 共回答了个问题 | 采纳率

查看全部

假定对线性表（38,25,74,52,48）进行散列存储,采用H（K）=K%7作为散列函数,若分别采用线性探测法和链接法 假定对线性表（38,25,74,52,48）进行散列存储,采用H（K）=K%7作为散列函数,若分别采用线性探测法和链接法处理冲突,则对各自散列表进行查找的平均查找长度分别为____和______. 还要稍微加上一点过程的解释才行哦~ 忘记双鱼1年前1: 漫漫无语共回答了9个问题 | 采纳率66.7%

首先,各个数的散列值是(3,4,4,3,0).
如果用线性探测法,散列表为
0 :48
3 :38
4 :25
5 :74
6 :52
查找各数需要的长度依次为(0,0,2,3,0),所以平均是1.
如果用链接法,散列表为
0 :48
3 :38 -> 52
4 :25 -> 74
查找各数需要的长度依次为(0,0,1,1,0),平均是0.4.

1年前查看全部

一个线性表为B=（12,23,45,57,20,03,78,31,15,36）,设散列表散列函数为H（key）= ke 一个线性表为B=（12,23,45,57,20,03,78,31,15,36）,设散列表散列函数为H（key）= key % 13并 并用线性探查法解决冲突,请画出散列表, 一个线性表为B=（12,23,45,57,20,03,78,31,15,36）,设散列表为HT[0..12], 散列函数为H（key）= key % 13并用线性探查法解决冲突,请画出散列表, qiji113771年前1: 玩美工作室共回答了18个问题 | 采纳率100%

空单元我用X表示：
78 X 15 03 X 57 31 20 X 45 23 36 12

1年前查看全部

数据结构求答案 3 判断题第26题 (2) 分消除递归不一定需要使用栈。正确错误第27题 (2) 分在开散列表 数据结构求答案 3 判断题 第26题 (2) 分 消除递归不一定需要使用栈。 正确 错误 第27题 (2) 分 在开散列表中不会出现堆积现象。 正确 错误 第28题 (2) 分 在链栈上进行进栈操作时，不需判断栈满。 正确 错误 第29题 (2) 分 算法的正确性，一般不进行形式化的证明，而是用测试来验证。 正确 错误 第30题 (2) 分 顺序表不需存放指针，链表要存放指针，故链表的存储空间要求总是比顺序表大。 正确 错误 第31题 (2) 分 如果n个顶点的无向图有n条边，则图中肯定有回路。 正确 错误 第32题 (2) 分 图G的生成树T是G的子图。 正确 错误 第33题 (2) 分 数组的基本运算有读、写、插入、删除等。 正确 错误 第34题 (2) 分 不管树的深度和形态如何，也不可能构造出一棵有100个结点的哈夫曼树。 正确 错误 第35题 (2) 分 如果根结点的左子树和右子树高度差不超过1，则该二叉树是平衡二叉树。 正确 错误 第36题 (2) 分 排序的目的是为了方便以后的查找。 正确 错误 第37题 (2) 分 以中序方式遍历一个堆，则得到一个有序序列。 正确 错误 第38题 (2) 分 二叉树中可能所有结点的度都小于2。 正确 错误 第39题 (2) 分 顺序表可以按序号随机存取。 正确 错误 第40题 (2) 分 在二叉排序树中，即使删除一个结点后马上再插入该结点，该二叉排序树的形态也可能不同。 正确 错误 第41题 (2) 分 队列在使用中必须设置两个指针，分别指向真正的队头和队尾的位置。 正确 错误 第42题 (2) 分 数据的逻辑结构和运算集组成问题的数学模型，与计算机无关。 正确 错误 第43题 (2) 分 对称矩阵压缩存储后仍然可以随机存取。 正确 错误 第44题 (2) 分 有向图中顶点i的出度等于邻接矩阵中第i行中1的个数；入度等于第i列中1的个数。 正确 错误 第45题 (2) 分 树和森林都可转化为二叉树，故对给定的二叉树，不能区分是由树还是森林转换来的。 正确 错误 第46题 (2) 分 循环队列中入队和出队的节点位置可出现在数组的任一端，已不满足“一端进另一端出”的要求，故实际上已不是队列了。 正确 错误 第47题 (2) 分 顺序查找法不仅可用于顺序表上的查找，也可用于链表上的查找。 正确 错误 第48题 (2) 分 有向图中边数等于邻接矩阵中1的个数；也等于邻接表中的边表结点数。 正确 错误 第49题 (2) 分 直接插入排序是稳定的，而Shell排序就是调用若干趟直接插入排序，故也是稳定的。 正确 错误 第50题 (2) 分 基数排序不需进行关键字间的比较，故执行时间比基于比较的排序方法要快。 正确 错误 不会水的鱼5551年前1: zouyong 共回答了19个问题 | 采纳率94.7%

1对2对3对4对5错6对7对错8对9错10错11错12对13对14对15错16对17对18错19错20错21对22对23错24错

1年前查看全部

哈希表查找不成功的平均查找长度题目是：将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中。散列表的存储 哈希表查找不成功的平均查找长度 题目是：将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组，散列函数为： H(key) = (keyx3) MOD 7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。 (1) 请画出所构造的散列表。 (2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 前面那个画表和查找成功的长度，都不是问题，成功的长度也好理解，就是一次成功和一次没成功多挪了几次的相加除以总数就行了。 问题是这个不成功的平均长度： 接下来讨论不成功的情况, 看表2，计算查找不成功的次数就直接找关键字到第一个地址上关键字为空的距离即可，但根据哈希函数地址为MOD7，因此初始只可能在0~6的位置。等概率情况下，查找0~6位置查找失败的查找次数为： 看地址0，到第一个关键字为空的地址2的距离为3，因此查找不成功的次数为3. 地址1，到第一个关键为空的地址2的距离为2，因此查找不成功的次数为2. 地址2，到第一个关键为空的地址2的距离为1，因此查找不成功的次数为1. 地址3，到第一个关键为空的地址4的距离为2，因此查找不成功的次数为2. 地址4，到第一个关键为空的地址4的距离为1，因此查找不成功的次数为1. 地址5，到第一个关键为空的地址2(注意不是地址9，因为初始只可能在0~6之间，因此循环回去)的距离为5，因此查找不成功的次数为5. 地址6，到第一个关键为空的地址2(注意不是地址9，因为初始只可能在0~6之间，因此循环回去)的距离为4，因此查找不成功的次数为4. 因此查找不成功的次数表如下表所示 Key 7 8 30 11 18 9 14 Count 3 2 1 2 1 5 4 我表示这段看的莫名其妙，完全不知道在说什么。 到底所谓的地址是哪个？为什么第一个地址为3后第二个2？怎么想的？ pikmon1年前1: xuyaoting 共回答了15个问题 | 采纳率80%

所谓地址是指散列函数的hash值
采用线性探测再散列法处理冲突，查询时，当遇到第一个为空时才能认为是查找失败

1年前查看全部

求高手帮忙，JAVA问题已知哈希函数为H(k)=3k%7，给定散列区空间长度m=9，用线性探测再散列处理冲突，对关键字序 求高手帮忙，JAVA问题 已知哈希函数为H(k)=3k%7，给定散列区空间长度m=9，用线性探测再散列处理冲突，对关键字序列（9，11，28，4，32，15，2）造hash表，并列出冲突次数。 微黑1年前1: mmrabbit940 共回答了19个问题 | 采纳率89.5%

28 2 X 15 X 11 9 4 32
1 5 1 1 1 3 4 总冲突=16次

1年前查看全部

数据结构算法问题（两个）1.已知闭散列表的长度为10（散列地址空间为0..9）,散列函数为H（k）=k%8,采用线性重新 数据结构算法问题（两个） 1.已知闭散列表的长度为10（散列地址空间为0..9）,散列函数为H（k）=k%8,采用线性重新散列技术解决冲突.将下列一组数据{5,16,48,7,9,82,1,39}依次插入到散列表中,请画出插入这组数据后的散列表. 2.已知关键字序列（89,12,34,76,5,9,56）,采用直接插入排序法按关键字递增（从小到大）排序,给出每一趟排序的结果. sharpbat0011年前1: christapple 共回答了17个问题 | 采纳率94.1%

全是很基础的概念性东西,第一个线性重散列,再通过散列函数计算的位置已经有元素时,向后找到一个空位置放入即可,所以结果为：
地址 0 1 2 3 4 5 6 7 8 9
元素 16 48 9 82 1 5 7 39
第二个插入排序更没有什么了,这个你自己看就好了,每一次就是前几个元素的正确排序,比如
第一次：89
第二次：12,89
第三次：12,34,89
一次,到最后一次,为排好的有序数组

1年前查看全部

散列表的平均查找长度A．与处理冲突方法有关而与表的长度无关B．与处理冲突方法无关而与表的长度有关C．与处理冲突方法有关而 散列表的平均查找长度 A．与处理冲突方法有关而与表的长度无关 B．与处理冲突方法无关而与表的长度有关 C．与处理冲突方法有关而与表的长度有关 D．与处理冲突方法无关而与表的长度无关 paul19831年前1: 得未曾有共回答了16个问题 | 采纳率93.8%

A
问题有点含混,其实从根本上说,应该是既与冲突处理的方法有关,也与表的装填因子有关,只是与表的长度不直接相关

1年前查看全部

数据结构的简单问题已知哈希函数为H(key)=key%11,哈希表长度为13,用线性探测再散列的方法处理冲突.表中已依次 数据结构的简单问题 已知哈希函数为H(key)=key%11,哈希表长度为13,用线性探测再散列的方法处理冲突.表中已依次存放了关键字为22、12、24、30、52和43的6个记录,现将关键字63填入哈希表,其哈希地址是,给出具体求解过程 lantian19981年前1: 我爱-夏天共回答了21个问题 | 采纳率85.7%

依次计算已经存放各关键字的位置：
22 % 11 = 0
12 % 11 = 1
24 % 11 = 2
30 % 11 = 7
52 % 11 = 8
43 % 11 = 10
都没有发生冲突,其位置就是散列函数值
63 % 11 = 8
与52 发生冲突,按照线性探测再散列的方法处理冲突,先探查8 + 1 = 9,这个位置空,没有关键字冲突,因此哈希地址为9

1年前查看全部

求大虾解答【数据结构】判断题判断题第26题 (2) 分在开散列表中不会出现堆积现象.正确错误第27题 (2) 分 求大虾解答【数据结构】判断题 判断题 第26题 (2) 分 在开散列表中不会出现堆积现象. 正确 错误 第27题 (2) 分 计算机的速度越快,算法的时间复杂性就越低. 正确 错误 第28题 (2) 分 顺序表不需存放指针,链表要存放指针,故链表的存储空间要求总是比顺序表大. 正确 错误 第29题 (2) 分 如果某种排序算法是不稳定的,则该方法没有实际的应用价值. 正确 错误 第30题 (2) 分 对任何图,执行一次深度优先或广度优先遍历后,就可访问到图中所有节点. 正确 错误 第31题 (2) 分 二叉树中不可能有两个结点在先根、中根和后根序列中的相对次序都不变. 正确 错误 第32题 (2) 分 链栈一般不需要头结点,因为无头结点的链栈运算也很方便. 正确 错误 第33题 (2) 分 数组的基本运算有读、写、插入、删除等. 正确 错误 第34题 (2) 分 树的度是指树中结点的最大度数,所以二叉树的度为2. 正确 错误 第35题 (2) 分 在顺序表中按值查找运算的复杂性为O(1). 正确 错误 第36题 (2) 分 n个结点的有向图,若它有n(n－1)条边,则它一定是强连通的. 正确 错误 第37题 (2) 分 基数排序不需进行关键字间的比较,故执行时间比基于比较的排序方法要快. 正确 错误 第38题 (2) 分 用线性探测法解决突出时,同义词在散列表中是相邻的. 正确 错误 第39题 (2) 分 不管树的深度和形态如何,也不可能构造出一棵有100个结点的哈夫曼树. 正确 错误 第40题 (2) 分 如果根结点的左子树和右子树高度差不超过1,则该二叉树是平衡二叉树. 正确 错误 第41题 (2) 分 有时冒泡排序的速度会快过快速排序. 正确 错误 第42题 (2) 分 缩短关键路径上活动的工期一定能够缩短整个工程的工期. 正确 错误 第43题 (2) 分 线性结构可以顺序存储,也可以链接存储.非线性结构只能链接存储. 正确 错误 第44题 (2) 分 单链表中取第i个元素的时间与i成正比. 正确 错误 第45题 (2) 分 二分查找所对应的判定树,是一棵理想平衡的二叉排序树. 正确 错误 第46题 (2) 分 堆排序是一种巧妙的树型选择排序. 正确 错误 第47题 (2) 分 拓扑排序可以分析某工程能否顺利进行. 正确 错误 第48题 (2) 分 利用栈可将递归程序转化成非递归程序. 正确 错误 第49题 (2) 分 设串的长度为n,则其子串个数为n(n+1)/2. 正确 错误 第50题 (2) 分 线性表、树、图等都可以用广义表表示. 正确 错误 密码88031年前1: 沐浴月光共回答了20个问题 | 采纳率85%

第26题 (2) 分
在开散列表中不会出现堆积现象.
正确

第27题 (2) 分
计算机的速度越快,算法的时间复杂性就越低.
错误

第28题 (2) 分
顺序表不需存放指针,链表要存放指针,故链表的存储空间要求总是比顺序表大.
错误

第29题 (2) 分
如果某种排序算法是不稳定的,则该方法没有实际的应用价值.
错误

第30题 (2) 分
对任何图,执行一次深度优先或广度优先遍历后,就可访问到图中所有节点.
错误

第31题 (2) 分
二叉树中不可能有两个结点在先根、中根和后根序列中的相对次序都不变.
正确

第32题 (2) 分
链栈一般不需要头结点,因为无头结点的链栈运算也很方便.
正确

第33题 (2) 分
数组的基本运算有读、写、插入、删除等.
错误

第34题 (2) 分
树的度是指树中结点的最大度数,所以二叉树的度为2.
错误

第35题 (2) 分
在顺序表中按值查找运算的复杂性为O(1).
错误

第36题 (2) 分
n个结点的有向图,若它有n(n－1)条边,则它一定是强连通的.
正确

第37题 (2) 分
基数排序不需进行关键字间的比较,故执行时间比基于比较的排序方法要快.
错误

第38题 (2) 分
用线性探测法解决突出时,同义词在散列表中是相邻的.
正确

第39题 (2) 分
不管树的深度和形态如何,也不可能构造出一棵有100个结点的哈夫曼树.
正确

第40题 (2) 分
如果根结点的左子树和右子树高度差不超过1,则该二叉树是平衡二叉树.
错误

第41题 (2) 分
有时冒泡排序的速度会快过快速排序.
正确

第42题 (2) 分
缩短关键路径上活动的工期一定能够缩短整个工程的工期.
错误

第43题 (2) 分
线性结构可以顺序存储,也可以链接存储.非线性结构只能链接存储.
错误

第44题 (2) 分
单链表中取第i个元素的时间与i成正比.
正确

第45题 (2) 分
二分查找所对应的判定树,是一棵理想平衡的二叉排序树.
正确

第46题 (2) 分
堆排序是一种巧妙的树型选择排序.
正确

第47题 (2) 分
拓扑排序可以分析某工程能否顺利进行.
正确

第48题 (2) 分
利用栈可将递归程序转化成非递归程序.
正确

第49题 (2) 分
设串的长度为n,则其子串个数为n(n+1)/2.
错误

第50题 (2) 分
线性表、树、图等都可以用广义表表示.
正确

1年前查看全部

C++STL中有没有散列类型的容器 gxlydcg1年前1: w1309278 共回答了19个问题 | 采纳率84.2%

C++98STL没有.但是Boost C++模板库当然有,C++11也有

1年前查看全部

散列表的平均查询长度,看看哪出错了

共1条回复

相关推荐

大家在问