数据结构章节练习题及答案8.docx
第8章查找算法1 .请简述查找的作用。查找的作用是根据给定值从一个数据集合中搜索某个元素。假设某 个元素的关键字值与给定值相等，那么查找成功；否那么查找失败。2 .请简述静态查找和动态查找的含义。静态查找只根据给定值在数据集合中按关键字查找匹配元素、访 问匹配元素的属性，而不对数据集合进行插入元素、删除元素等操作; 而动态查找可能会在查找过程中向数据集合中插入一个新元素或从 数据集合中删除一个已有元素。3 .请简述各种查找算法的适用范围。各种查找算法的适用范围：(a)顺序查找虽然查找效率最低，但其对待查找数据集合的存储 结构无特别要求，在对数据集合进行增、册h改等操作时效率较高， 因此，根据那些不需要经常作查找操作的关键字进行查找时，一般采 用顺序查找算法。假设经常作查找操作，那么应使用效率较高的其他查找 算法。(b)折半查找和分块查找主要适用于数据集合增、册h改等操 作较少的情况；二叉排序树查找那么适用于数据集合变化较频繁的情 况。(c)哈希查找虽然在理论上具有最短的平均查找长度，但它占 用的存储空间较多，且在实际中只有哈希函数构造得好才能到达常量 级的平均查找长度。而要想构造出好的哈希函数，必须以大量数据为基础，因此，哈希查找主要适用于数据分布的情况。4 .请简述顺序查找对待查找数据集合的要求及顺序查找的具体步骤。顺序查找是一种最简单、直观的查找算法，适用于采用任何存储结构的数据集合，其具体步骤为：(a)按预先规定的顺序依次将数据集合中每个元素的关键字与给定值进行比拟，假设某个元素的关键字与给定值相同，那么查找成功；(b)假设遍历所有元素后，仍没有找到关键字与给定值相同的元 素，那么查找失败。5 .请简述折半查找对待查找数据集合的要求及折半查找的具体 步骤。折半查找，又称二分查找，它要求数据集合采用顺序表存储结构, 且数据集合中的元素是按关键字大小有序排列的。假设数据集合的元 素按关键字递增排列，折半查找算法的具体步骤为：(a)对于包含n个元素的递增数据集合R=R1, R2,Rn(Ri<Ri+l),根据给定元素K进行折半查找，初始化待查找数据 集合的下标起始位置low=l和结束位置high二n。(b)计算中间元素下标mid=|_(low+high)/2，假设Rmid=K,那么 查找成功，折半查找算法结束；假设Rmid<K,那么令low=mid+1；否 那么，假设 Rmid>K,那么令 high二mid-1。(C)假设新的待查找数据集合不为空，即low<high,那么返回到上一步在新的数据集合(Rlow,Rlow+1 ,.,Rhigh)上继续进行折半 查找；否那么查找失败。6 .请简述分块查找对待查找数据集合的要求及分块查找的具体 步骤。在分块查找算法中，除了待查找的数据集合外，还需建立一个索 引表。待查数据集合与索引表的关系描述如下：(a)将包含n个元 素的待查找数据集合均匀分为b块(即b个子集合)，前b-1块中元 素数目s4n/bj,最后一块中元素数目小于等于s。(b)分块后块内 元素可以无序，但块间必须有序，这里假设块间为递增排列，即第i+1 块中的任一元素大于第i块中的任一元素(i<b)。(c)构造一个包 含b个元素的索引表，用于记录每块的起始位置和最大元素值。分块查找算法的具体步骤为：(a)在索引表中查找，确定待查 找元素在哪一块，由于索引表有序，因此可以使用二分查找算法。(b) 在已确定的块中，进行顺序查找。7 .请简述二叉排序树的定义。二叉排序树，又称二叉查找树，它或者是一棵空树，或者是具有 如下性质的二叉树：(a)假设它的左子树非空，那么左子树上所有结点的值均小于根结 点的值。(b)假设它的右子树非空，那么右子树上所有结点的值均大于根结 点的值。(c)左、右子树也分别是二叉排序树。8 .请简述二叉排序树的插入和创立过程。二叉排序树的插入过程：在二叉排序树中插入一个新结点，应保证插入新结点后的二叉树 仍然是一棵二叉排序树。对于一个给定元素K,将其插入到二叉排序 树中的具体步骤如下：(a)假设二叉排序树为一棵空树，那么将元素K作为二叉排序树的 根结点。(b)假设K等于根结点的值，那么该元素已经是二叉排序树中的结 点，不需重复插入，直接返回；假设K小于根结点的值，那么将K插入 到左子树中；假设K大于根结点的值，那么将K插入到右子树中。重复 该步骤，直至要插入的子树为空，此时将K作为该子树的根结点。二叉排序树的创立过程就是不断插入新结点的过程。9 .请简述二叉排序树的查找过程。对于给定值K,先将K与根结点的值比拟，假设相等那么查找成功; 假设K小于根结点的值，那么在左子树中继续进行二叉排序树的查找； 否那么，假设K大于根结点的值，那么在右子树中继续进行二叉排序树的 查找。重复该过程，直至找到匹配的结点，查找成功；或者子树为空, 查找失败。10 .请简述哈希表的元素存储原理。确定一函数h,对于关键字值是k的元素，以k为自变量计算函 数值h(k),这个函数值被解释为一片连续存储空间中的一个地址(即 数组中的一个下标值)，元素即被存入到这个地址中。11 .请简述常用的四种哈希函数及其计算规那么。除余法：选取一个适当的正整数P（通常P为不大于哈希表存储 空间尺寸的最大素数），以元素的关键字值k除以P,得到的余数作 为元素的存储地址，即h（k）=k%po数字分析法：假设元素的关键字由多位组成，且关键字的位数比存 储空间地址码位数多、每一位的取值范围及关键字的取值分布情况预 先知道,那么可以对元素关键字的各位进行分析,去掉分布较集中的位、 保存分布较均匀的位。折叠法：假设元素的关键字由多位组成，且关键字的位数比存储空 间地址码位数多，但关键字的取值分布情况未知，那么可以用折叠法将 关键字分为几段（除了最后一段位数可以少一些，其他各段的位数均 等于存储空间地址码位数），并将所有段的值做叠加求和运算，将叠 加和的最高位进位舍去后取剩余局部作为元素的存储地址。平方取中法：对元素的关键字值求平方，并取中间几位作为元素 的存储地址。12 .请简述常用的两种哈希表冲突处理方法。开放定址法：按照某个探查序列在哈希表中进行搜索，直至找到 一个空闲的地址，将发生冲突的新元素存储在该地址中。拉链法：将所有同义词存储在一个线性链表中，从而防止开放定 址法中的“二次聚集”现象。用拉链法构造的哈希表，假设其有m个存 储地址（下标为0, 1,那么每个地址存储一个线性链表的头指针，映射到地址i的元素以结点的方式插入到地址i所对应的链表 中。
