数据结构章节练习题及答案8

第8章查找算法

i.请简述查找的作用。

查找的作用是根据给定值从一个数据集合中搜索某个元素。若某

个元素的关键字值与给定值相等，则查找成功；否则查找失败。

2.请简述静态查找和动态查找的含义。

静态查找只根据给定值在数据集合中按关键字查找匹配元素'访

问匹配元素的属性，而不对数据集合进行插入元素'删除元素等操作;

而动态查找可能会在查找过程中向数据集合中插入一个新元素或从

数据集合中删除一个已有元素。

3.请简述各种查找算法的适用范围。

各种查找算法的适用范围：

(a)顺序查找虽然查找效率最低，但其对待查找数据集合的存储

结构无特别要求，在对数据集合进行增'册h改等操作时效率较高，

因此，根据那些不需要经常作查找操作的关键字进行查找时，一般采

用顺序查找算法。若经常作查找操作，则应使用效率较高的其他查找

算法。

(b)折半查找和分块查找主要适用于数据集合增'册h改等操

作较少的情况；二叉排序树查找则适用于数据集合变化较频繁的情

况。

(c)哈希查找虽然在理论上具有最短的平均查找长度，但它占

用的存储空间较多，且在实际中只有哈希函数构造得好才能达到常量

级的平均查找长度。而要想构造出好的哈希函数，必须以大量数据为

基础，因此，哈希查找主要适用于数据分布已知的情况。

4.请简述顺序查找对待查找数据集合的要求及顺序查找的具体

步骤。

顺序查找是一种最简单'直观的查找算法，适用于采用任何存储

结构的数据集合，其具体步骤为：

(a)按预先规定的顺序依次将数据集合中每个元素的关键字与

给定值进行比较，若某个元素的关键字与给定值相同，则查找成功；

(b)若遍历所有元素后，仍没有找到关键字与给定值相同的元

素，则查找失败。

5.请简述折半查找对待查找数据集合的要求及折半查找的具体

步骤。

折半查找，又称二分查找，它要求数据集合采用顺序表存储结构,

且数据集合中的元素是按关键字大小有序排列的。假设数据集合的元

素按关键字递增排列，折半查找算法的具体步骤为：

(a)对于包含n个元素的递增数据集合R=(R[1],R[2],R[n]}

(R[i]<R[i+l])，根据给定元素K进行折半查找，初始化待查找数据

集合的下标起始位置low=l和结束位置high=no

(b)计算中间元素下标mid=|_(low+high)/2_|,若R[mid]==K,则

查找成功，折半查找算法结束；若R[midJ<K,则令low=mid+l；否

则，若R[mid]>K,则令high=mid-l。

(c)若新的待查找数据集合不为空，即low<high,则返回到上

一步在新的数据集合(R[low],R[low+1.,R[high])上继续进行折半

查找；否则查找失败。

6.请简述分块查找对待查找数据集合的要求及分块查找的具体

步骤。

在分块查找算法中，除了待查找的数据集合外，还需建立一个索

引表。待查数据集合与索引表的关系描述如下：(a)将包含n个元

素的待查找数据集合均匀分为b块(即b个子集合)，前b-1块中元

素数目s=Ln/bJ,最后一块中元素数目小于等于So(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%p。

数字分析法：若元素的关键字由多位组成，且关键字的位数比存

储空间地址码位数多'每一位的取值范围及关键字的取值分布情况预

先知道，则可以对元素关键字的各位进行分析,去掉分布较集中的位'

保留分布较均匀的位。

折叠法：若元素的关键字由多位组成，且关键字的位数比存储空

间地址码位数多，但关键字的取值分布情况未知，则可以用折叠法将

关键字分为几段（除了最后一段位数可以少一些，其他各段的位数均

等于存储空间地址码位数），并将所有段的值做叠加求和运算，将叠

加和的最高位进位舍去后取剩余部分作为元素的存储地址。

平方取中法：对元素的关键字值求平方，并取中间几位作为元素

的存储地址。

12.请简述常用的两种哈希表冲突处理方法。

开放定址法：按照某个探查序列在哈希表中进行搜索，直至找到

一个空闲的地址，将发生冲突的新元素存储在该地址中。

拉链法：将所有同义词存储在一