问题:已知一个线性表(38,25,74,63,52,48),假定采用散列函数h(key)=key%7计算散列地址,并散列存储在散列表A[0..6]中,若采用线性探测方法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为__________.
A.1.5 B.1.7 C.2.0 D.2.3
分析:利用该散列函数散列存储结果为
68|48 | |38|25|74|52
位置 0 1 2 3 4 5 6
平均查找长度=总的查找次数/元素数=(1*3+2*1+3*1+4*1)/6=2.0
参考答案:(52)C
能分析一下具体怎么解答吗???
要计算散列表上的平均查找长度,我们首先必须要知道在建立这个散列表时,每个数据存储时进行了几次散列。这样就知道哪一个元素,查找的长度是多少。
散列表的填表过程如下:首先存入第一个元素38,由于h(38)=38%7=3,又因为3号单元现在没有数据,所以把38存入3号单元。 接着存入第二个元素25,由于h(25)=25%7=4,又因为4号单元现在没有数据,所以把25存入4号单元。 接着存入第三个元素74,由于h(74)=74%7=4,此时的4号单元已经被25占据,所以进行线性再散列,线性再散列的公式为:Hi=(H(key)+di)% m ,其中的di=1,2,3,4...。所以H1=(4+1)%7=5,此时的单元5没有存数据,所以把74存入到5号单元。 接着存入第四个元素63,由于h(63)=63%7=0,此时的0号单元没有数据,所以把63存入0号单元。 接着存入第五个元素52,由于h(52)=52%7=3,此时的3号单元已被38占据,所以进行线性再散列:H1=(3+1)%7=4,但4号单元也被占据了,所以再次散列:H2=(3+2)%7=5,但5号单元也被占据了,所以再次散列:H3=(3+3)%7=6,6号单元为空,所以把52存入6号单元。 最后存入第六个元素48,由于h(48)=48%7=6,此时的6号单元已被占据,所以进行线性再散列:H1=(6+1)%7=0,但0号单元也被占据了,所以再次散列:H2=(6+2)%7=1,1号单元为空,所以把48存入1号单元。 如果一个元素存入时,进行了N次散列,相应的查找次数也是N,所以38,25,63这三个元素的查找长度为1,74的查找长度为2,48的查找长度为3,52的查找长度为4。所以平均查找长度为:(1+1+1+2+3+4)/6=2。
相关推荐
当查找一个对象时,首先计算目标对象的散列码,然后在对应索引的链表中进行线性搜索。虽然链表搜索相对较慢,但如果散列函数设计得足够好,使得冲突较少,大部分情况下仅需检查少数几个元素,就能找到目标对象,从而...
开放寻址法包括线性探测、二次探测和双散列探测等,当某个位置被占用时,寻找下一个空闲位置。链地址法是将冲突的元素链接到同一个索引对应的链表中。 3. **C语言实现**:在C语言中,通常使用结构体来表示散列表。...
- **开散列**:当发生冲突时,寻找一个新的位置进行存储,如线性探测再散列、二次探测再散列、双重散列等。 - **闭散列**:当发生冲突时,在同一个位置上进行处理,通常采用链地址法或开放寻址法。 #### 三、哈希表...
- 链式存储方式:每个节点包含一个数据元素和指向下一个节点的指针,不需连续存储空间。 - 索引存储方式:除了数据元素外,还有索引表来指示元素的位置,如B树。 - 散列存储方式:通过哈希函数将数据映射到特定...
哈希表的关键在于它的“哈希”概念,这里的“哈希”来源于英文的"Hash",直译为“散列”,即通过对键进行特定计算得到一个唯一的索引值,这个索引值直接对应数组中的位置,从而快速定位到数据。 哈希表的主要特性是...
哈希表,又称散列表,是一种高效的数据存储和查找结构,其主要原理是通过散列函数将关键码值(Key value)映射到一个固定大小的数组中的特定位置,从而实现快速访问。这个映射过程使得我们可以直接根据键(Key)来...
链表则弥补了这一不足,每个节点包含数据和指向下一个节点的指针,插入和删除只需改变几个指针即可。栈是后进先出(LIFO)的数据结构,常用于函数调用和表达式求值;队列则是先进先出(FIFO)的结构,常用于任务调度...
- **树**:是一种典型的非线性数据结构,其中每个节点最多有一个父节点,但可以有多个子节点。 - **图**:由顶点集合和边集合构成,边可以是有向的也可以是无向的。 ### 数据结构真题解析 1. **单项选择题解析**...
链表则由一系列节点组成,每个节点包含数据和指向下一个节点的指针,允许在任意位置插入和删除,但访问速度较慢。 栈是一种后进先出(LIFO)的数据结构,常用于函数调用、表达式求值等场景。队列则是先进先出(FIFO...
线性探测法是一种处理冲突的方法,若所有关键码散列到同一位置,探测的总次数是n-1(n个关键码,第一个位置没有冲突)。 4. **链表与折半查寻**:链表不适合折半查寻,因为链表的元素不是连续存储的,无法通过索引...
在这个文件中,散列函数是一个内部方法hash(),它通过一系列位操作来计算最终的散列值。为了找到对应的数组位置,HashMap使用了indexFor()方法,该方法通过将散列值与数组长度减一进行按位与操作来得到索引值: ```...
链表由一系列节点组成,每个节点包含数据和指向下一个节点的指针。这允许动态地添加或删除元素,但查找元素需要遍历整个链表,效率相对较低。 栈是一种后进先出(LIFO)的数据结构,常用于函数调用、表达式求值等...
搜索树是一种特殊的树形结构,其中每个节点的值都大于其左子树的所有节点,小于其右子树的所有节点,这使得查找、插入和删除操作非常高效。竞赛树是用于数据竞赛的一种特殊树,通常用于解决排序和查找问题。 散表是...
4. **散列结构**:散列表(哈希表)通过散列函数将数据映射到固定大小的数组中,实现快速的查找、插入和删除操作,但可能出现冲突问题,解决方法有开放寻址法和链地址法。 5. **堆栈**:栈是一种后进先出(LIFO)的...
一个数据结构可以用一个二元组表示为S=(D,R),其中D是数据结构中的数据的非空有限集合,R是定义在D上的关系的非空有限集合。数据结构可分为逻辑结构和物理(存储)结构两大类。逻辑结构是指数据的逻辑关系,主要分为...
对于连通图而言,最少边数是一个需要关注的理论问题。 知识点12:算法实现与操作 - 后缀算式(逆波兰表示法)与中缀算式的转换是栈的应用之一。 - 对于堆排序,了解每个分支结点的筛运算的时间复杂度对于分析整个...
线性结构包括数组、链表、栈和队列等,它们的数据元素之间存在着一对一的关系。数组是最基本的线性结构,提供了随机访问的优势;链表则通过指针链接元素,允许动态调整大小;栈是后进先出(LIFO)的数据结构,常用在...
而非线性结构包括树和图,这些结构中的元素可能存在多对多的关系,比如一个元素可以有多个前驱和后继。 存储结构指的是数据在计算机中的实际表示,包括顺序存储、链式存储、索引存储和散列存储等。顺序存储结构中,...