怎么制作网站模版,惠州网站制作维护,网站技术介绍,长沙网络公司大全目录 一、查找的概念#xff08;一#xff09;静态查找和动态查找#xff08;二#xff09;二分查找的适用情况#xff08;三#xff09;查找算法中的监视哨 二、散列查找#xff08;一#xff09;同义词#xff08;二#xff09;构造哈希函数#xff08;三#xf… 目录 一、查找的概念一静态查找和动态查找二二分查找的适用情况三查找算法中的监视哨 二、散列查找一同义词二构造哈希函数三散列查找的步骤四冲突和解决冲突 三、树形查找一二叉搜索树的定义二平衡二叉搜索树的定义三平衡二叉搜索树结点的个数 一、查找的概念
一静态查找和动态查找 1、简述静态查找和动态查找的概念并举例相应的查找名称。 答查找某个特定元素是否在表中和它的相关属性称为静态查找例如顺序、折半、分块、散列查找等若在查找过程中需要插入或删除查找表的元素则为动态查找例如树形查找中的二叉搜索树、平衡二叉树、B树等。
二二分查找的适用情况 1、什么情况下可以采用二分查找若数据元素的个数为n则查找成功的平均查找长度是多少 答二分折半查找要求线性表必须采用顺序存储结构且表中元素按关键字有序排列由于在二分判定树中比较次数最多不会超过树的高度h⌈log2(n1)⌉即二分查找成功的平均查找长度为O(log2n)。 2、对于一个有序顺序表来说折半查找是否任何时候都比顺序查找快为什么 答并不是只是一般情况下折半查找比顺序查找快因为折半查找每次比较都可以排除一半的元素从而减少了查找时间。例如若要查找的元素为顺序表的第一个元素则通过顺序查找会比折半查找快。
三查找算法中的监视哨 1、在很多查找和排序算法中经常使用“监视哨”其目的是什么? 答监视哨的作用是免去了查找过程中每次都要检测整个表是否查找完毕提高了查找效率。
二、散列查找
一同义词 1、在采用线性探测法处理冲突的散列表中所有同义词在表中是否一定相邻 答不一定相邻。因为发生了冲突即出现两个不同的关键字被哈希函数散列到同一个地址的情况都争夺哈希地址。
二构造哈希函数 1、简述构造哈希函数的常用方法。 答简述构造哈希函数的常用方法有以下 1直接定址法选取关键字或关键字的某个线性函数值为哈希地址 2除留余数法选取关键字除以某个整数的余数作为哈希地址即通过取余运算得到的余数作为哈希地址 3平方取中法取关键字平方的中间几位作为哈希地址 4折叠法将关键字分割成位数相同的几段然后叠加求和作为哈希地址。 2、如何衡量Hash函数的优劣 答评价Hash函数的优劣有能否将关键字均匀影射到哈希空间上有无好的解决冲突的方法计算哈希函数是否简单高效等。另外一个好的哈希函数可以减小冲突但不可能避免冲突。
三散列查找的步骤 1、假设已按散列函数H和冲突处理方法R建立了散列表试写出散列查找的步骤。 答设查找哈希表的关键字KEY首先通过散列函数计算地址然后用关键字KEY与该地址的关键字进行比较若当前地址为空则查找失败若相同则查找成功若不同则通过冲突处理方法R得到下一个地址进行比较直到相同为止其中若按照冲突处理方法R得到的新地址又比较为空则证明查找失败。
四冲突和解决冲突 1、简要叙述hash表技术中的冲突概念并指出三种解决冲突的方法。 答两个不同的关键字被哈希函数散列到同一个地址的情况则称为冲突解决冲突的方法有线性探查法、平方探查法、双散列法、链地址法等等。
三、树形查找
一二叉搜索树的定义 1、什么是二叉搜索树 答用于查找的二叉树其中每个结点的值不小于左子树结点的值不大于右子树结点的值。
二平衡二叉搜索树的定义 1、什么是平衡二叉搜索树有哪些动态平衡调整操作 答平衡二叉树以二叉搜索树为基础若二叉搜索树中左、右子树的高度之差的绝对值不超过1则称为平衡二叉树其左、右子树也为一棵平衡二叉树。有以下动态平衡调整操作 ①左单旋转LL ②右单旋转RR ③先左后右双旋转LR ④先右后左双旋转RL。
三平衡二叉搜索树结点的个数 1、一棵具有m层的AVL树至少有多少个结点最多有多少个结点 答一棵具有 m 层的平衡二叉树AVL最多有2m-1个结点另外由斐波那契数列Fibonacci可得最少有f(m) f(m-1) f(m-2) 1个结点其中f(1) 1 、f(2) 2、f(3) 4。
