ex第七章 查找

第七章查找

一、填空

1、线性表上进行查找的方法主要有__________、_________和__________三种。

2、对于含有n个结点的顺序表，结点的查找在等概率的前提下，对于成功的查找，平均检索长度为__________，对于失败的查找，则需要比较_________次。

3、二分查找又称为折半查找，它要求线性表中结点必须按______________________排列。

4、二分查找只适用于_______存储结构，因此在经常进行删除和插入的表中不适合使用这种查找方法。

5、二叉排序树的一个重要性质：按中序遍历该树所得到的中序序列是一个_________序列。

6、解决散列查找时的产生冲突的最基本方法通常有__________和_________两种。

7、顺序查找法的平均查找长度为__________________；二分查找法的平均查找长度为__________________；分快查找法（以顺序查找确定快）的平均查找长度为__________________；分快查找法（以二分查找确定快）的平均查找长度为__________________；散列查找法采用拉链法处理冲突时的平均查找长度为__________________。

8、在各种查找方法中，平均查找长度与结点个数n无关的查找方法是______________。

9、在分快查找方法中，首先查找______________，然后查找相应的_______________。

10、在散列函数H(key)=key % p中，p应该取____________。

二、单项选择

1、已知10个数据元素为（54，28，16，34，73，62，95，60，26，43）,按照依次插入结点的方法生成一棵二叉排序列树，查找值为62的结点所需要进行的比较次数为（）。

A） 2 B） 3 C） 4 D） 5

2、下列查找表的各种方法中，不属于静态查找表的有（）。

A) 顺序表的查找 B) 有序表的查找

C) 静态树表的查找 D) 平衡二叉树

3、顺序查找法适合于存储结构为（）的线性表。

A) 散列存储 B) 顺序存储或链接存储

C) 压缩存储 D) 索引存储

4、对线性表进行二分查找时，要求线性表必须（）。

A) 以顺序方式存储

B) 以链接方式存储

C) 以顺序方式存储，且结点按关键字有序排序

D) 以链接方式存储，且结点按关键字有序排序

5、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。

A) n B) n/2

C)(n+1)/2 D) (n-1)/2

6、采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。

A) O(n2) B) O(nlog2n)

C) O(n) D) O(log2n)

7、二分查找和二分排序树的时间性能（）。

A）相同 B）不相同

8、有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，查找成功需要比较（）次。

A）1 B）2 C） 4 D）8

9、如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用（）查找方法。

A）分快 B）顺序 C）二分 D）散列

三、应用题

1、依次输入以下元素序列：78，34，45，85，45，36，91，84，78,试构造一棵二叉排序树。要在这棵二叉排序树中查找55，需要比较多少次。

2、设有一组关键字{19，01，23，14，55，20，84，27，68，11，10，77}，散列函数为 H(key)=key % 13 。采用开放地址法的线性探查再散列方法解决冲突，试在0～18的散列地址空间中对该关键字序列构造散列表。

ex第七章 查找

第七章查找 一、填空 1、线性表上进行查找的方法主要有__________、_________和__________三种。 2、对于含有n个结点的顺序表，结点的查找在等概率的前提下，对于成功的查找，平均检索长度为__________，对于失败的查找，则需要比较_________次。 3、二分查找又称为折半查找，它要求线性表中结点必须按______________________排列。 4、二分查找只适用于_______存储结构，因此在经常进行删除和插入的表中不适合使用这种查找方法。 5、二叉排序树的一个重要性质：按中序遍历该树所得到的中序序列是一个_________序列。 6、解决散列查找时的产生冲突的最基本方法通常有__________和_________两种。 7、顺序查找法的平均查找长度为__________________；二分查找法的平均查找长度为__________________；分快查找法（以顺序查找确定快）的平均查找长度为__________________；分快查找法（以二分查找确定快）的平均查找长度为__________________；散列查找法采用拉链法处理冲突时的平均查找长度为__________________。 8、在各种查找方法中，平均查找长度与结点个数n无关的查找方法是______________。 9、在分快查找方法中，首先查找______________，然后查找相应的_______________。 10、在散列函数H(key)=key % p中，p应该取____________。 二、单项选择 1、已知10个数据元素为（54，28，16，34，73，62，95，60，26，43）,按照依次插入结点的方法生成一棵二叉排序列树，查找值为62的结点所需要进行的比较次数为（）。 A） 2 B） 3 C） 4 D） 5 2、下列查找表的各种方法中，不属于静态查找表的有（）。 A) 顺序表的查找 B) 有序表的查找 C) 静态树表的查找 D) 平衡二叉树 3、顺序查找法适合于存储结构为（）的线性表。 A) 散列存储 B) 顺序存储或链接存储 C) 压缩存储 D) 索引存储 4、对线性表进行二分查找时，要求线性表必须（）。 A) 以顺序方式存储 B) 以链接方式存储 C) 以顺序方式存储，且结点按关键字有序排序 D) 以链接方式存储，且结点按关键字有序排序 5、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。 A) n B) n/2 C)(n+1)/2 D) (n-1)/2 6、采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。 A) O(n2) B) O(nlog2n) C) O(n) D) O(log2n) 7、二分查找和二分排序树的时间性能（）。 A）相同 B）不相同

常见的检索技术

常见检索技术 作者：陈亚萍学号：1101212925 手工检索（manual retrieval）是一种传统的检索方法，即以手工翻检的方式，利用工具书（包括图书、期刊、目录卡片等）来检索信息的一种检索手段。 与之对应的计算机检索（computer-based retrieval）简称机检，是指利用计算机通过各种数据库查找所需文献信息的方法，检索过程是由人操纵计算机完成的，其匹配是由计算机进行的。在检索过程中，人是整个检索方案的计设者和操纵者。利用机器及计算机，配合以相应的搜索语言和逻辑对相关课题进行检索是检索技术的发展趋势。 检索表达式，又称检索式、检索提问式，是机检中用来表达检索提问的一种逻辑运算 式。构建检索表达式需要用到相关逻辑检索及检索技术。 (一)常用检索方法概述 1.布尔逻辑运算检索——是指利用布尔运算符连接各个检索词，然后由计算机进行相应逻辑 运算，以找出所需信息的方法。它使用面最广、使用频率最高。 2.位置运算检索——位置算符检索是用一些特定的算符（位置算符）来表达检索词与检索词 之间的临近关系，并且可以不依赖主题词表而直接使用自由词进行检索的技术方法。 3.截词检索与词根检索——截词检索是预防漏检提高查全率的一种常用检索技术，大多数系 统都提供截词检索的功能。截词是指在检索词的合适位置进行截断，然后使用截词符进行处理，这样既可节省输入的字符数目，又可达到较高的查全率。词根检索是指输入某一单词，系统会自动匹配与该词具有相同词根的其他词。 4.字段检索——限定如主题、关键词等某个字段进行检索。 5.全文检索——将文件中所有文本与检索项匹配的文字资料检索方法。 6.精确检索——指检索词与结果完全匹配的检索技术。与之对应的模糊检索，则是指检索词 的基础上进行相应的扩展。 7.其他检索技术（禁用词、嵌套、限制词、大小写敏感词等） (二)分述 1.布尔逻辑检索（Boolean retrieval） 乔治·布尔（George Boole，1815年11月－1864年），爱尔兰数学家，哲学家。1848年，布尔出版了T he Mathematical Analysis of Logic，这是他对符号逻辑诸多贡献中的第一次。1854年，他出版了《The Laws of Thought》，这是他最著名的著作。在这本书中布尔介绍了现在以他的名字命名的布尔代数。由于其在符号逻辑运算中的特殊贡献，很多计算机语言中将逻辑运算称为布尔运算，将其结果称为布尔值。布尔逻辑在检索中主要分为与、逻辑或、逻辑非。 （1）逻辑与 示例数据库：CNKI 检索式：智能机器人*控制

查找技术

第7 章查找技术 课后习题讲解 1. 填空题 ⑴顺序查找技术适合于存储结构为（）的线性表，而折半查找技术适用于存储结构为（）的线性表，并且表中的元素必须是（）。 【解答】顺序存储和链接存储，顺序存储，按关键码有序 ⑵ 设有一个已按各元素值排好序的线性表，长度为125，用折半查找与给定值相等的元素，若查找成功，则至少需要比较（）次，至多需比较（）次。 【解答】1，7 【分析】在折半查找判定树中，查找成功的情况下，和根结点的比较次数最少，为1次，最多不超过判定树的深度。⑶ 对于数列{25，30，8，5，1，27，24，10，20，21，9，28，7，13，15}，假定每个结点的查找概率相同，若用顺序存储结构组织该数列，则查找一个数的平均比较次数为（）。若按二叉排序树组织该数列，则查找一个数的平均比较次数为（）。【解答】8，59/15 【分析】根据数列将二叉排序树画出，将二叉排序树中查找每个结点的比较次数之和除以数列中的 元素个数，即为二叉排序树的平均查找长度。 ⑷ 长度为20的有序表采用折半查找，共有（）个元素的查找长度为3。 【解答】4 【分析】在折半查找判定树中，第3层共有4个结点。 ⑸ 假定一个数列{25，43，62，31，48，56}，采用的散列函数为H(k)=k mod 7，则元素48的同义词是（）。 【解答】62 【分析】H(48)= H(62)=6

⑹ 在散列技术中，处理冲突的两种主要方法是（）和（）。 【解答】开放定址法，拉链法 ⑺ 在各种查找方法中，平均查找长度与结点个数无关的查找方法是（）。 【解答】散列查找 【分析】散列表的平均查找长度是装填因子的函数，而不是记录个数n的函数。 ⑻ 与其他方法相比，散列查找法的特点是（）。【解答】通过关键码计算记录的存储地址，并进行一定的比 2. 选择题 ⑴ 静态查找与动态查找的根本区别在于（）。 A 它们的逻辑结构不一样 B 施加在其上的操作不同 C 所包含的数据元素的类型不一样 D 存储实现不一样【解答】B 【分析】静态查找不涉及插入和删除操作，而动态查找涉及插入和删除操作。 ⑵ 有一个按元素值排好序的顺序表（长度大于2），分别用顺序查找和折半查找与给定值相等的元素，比较次数分别是s和b，在查找成功的情况下，s 和b的关系是（）；在查找不成功的情况下，s 和b的关系是（）。 A s=b B s>b C s D 不能确定 【解答】D，D 【分析】此题没有指明是平均性能。例如，在有序表中查找最大元素，则顺序查找比折半查找快，而平均性能折半查找要优于顺序查找，查找不成功的情况也类似。 ⑶ 长度为12的有序表采用顺序存储结构，采用折半查找技术，在等概率情况下，查找成功时的平均查找长度是（），查找失败时的平均查找长度是（）。 A 37/12 B 62/13 C 3 9/12 D 49/13 【解答】A，B

第7章自测练习题参考答案

第7章自测练习题参考答案 1．有一个有序文件，其中各记录的关键字为： {3,4,5,6,7,8,10,17,19,20,27,32,43,54,65,76,87}， 当用折半查找算法查找关键字为4,20,65时，其比较次数分别为多少? 解： 该有序文件长度为17，根据折半查找算法画出判定树如下图所示。从图中可得出：当关键字为4,20,65时，其比较次数分别为3，4，3。 2.若对大小均为n 的有序顺序表和无序顺序表分别进行顺序查找，试就下列三种情况分别讨论两者在等查找概率时的平均查找长度是否相同? (1)查找失败； (2)查找成功； (3)查找成功，表中有多个关键字等于给定值的记录，一次查找要求找出所有记录。 解： (1)平均查找长度不相同。有序顺序表小于等于无序顺序表。 (2)平均查找长度相同。 (3) 平均查找长度不相同，有序顺序表小于等于无序顺序表。 3.试按下列次序将各关键字插入到二叉平衡树中，画出重新平衡的情况。关键字依次为：8、9、12、2、1、5、3、6、7、11 解： ～(j)所示。 RR (b)不调整 (a)初始 (d)不调整 (e)调整

4.已知长度为12的表： （Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec ）。 (1) 试按表中元素的顺序，依次插入一棵初始为空的二叉树；试画出插入完成之后的二叉排序树，并求其在等查找概率情况下查找成功的平均查找长度。 (2)若对表中元素先进行排序构成有序表，试求在等查找概率情况下对此有序表进行二分查找时查找 (f)调整 (g)不调整 (h)不调整 (i)调整 (j)调整

三分查找技术

【标准化说明】三分查找技术与简单应用 三分查找技术适用于答案在某一个区间内，这个区间的特点的是，以答案为分点的两侧区间都单调的增大或者减小： 如右图就是一个分的例子： 三分的区间为[l,r]其中最低点为答案 每次把区间分为3个等分 取x1=l+(r-l)/3 ,x2=r-(r-l)/3 作为分点，看谁更接近标准答案， 并以此来更新左右区间，继续进行二分，直到得到(无限逼 近)答案。 Trick or Treat Description Johnny and his friends have decided to spend Halloween night doing the usual candy collection from the households of their village. As the village is too big for a single group to collect the candy from all houses sequentially, Johnny and his friends have decided to split up so that each of them goes to a different house, collects the candy (or wreaks havoc if the residents don't give out candy), and returns to a meeting point arranged in advance. There are n houses in the village, the positions of which can be identified with their Cartesian coordinates on the Euclidean plane. Johnny's gang is also made up of n people (including Johnny himself). They have decided to distribute the candy after everybody comes back with their booty. The houses might be far away, but Johnny's interest is in eating the candy as soon as possible. Keeping in mind that, because of their response to the hospitality of some villagers, some children might be wanted by the local authorities, they have agreed to fix the meeting point by the river running through the village, which is the line y = 0. Note that there may be houses on both sides of the river, and some of the houses may be houseboats (y = 0). The walking speed of every child is 1 meter per second, and they can move along any direction on the plane. At exactly midnight, each child will knock on the door of the house he has chosen, collect the candy instantaneously, and walk back along the shortest route to the meeting point. Tell Johnny at what time he will be able to start eating the candy. Input Each test case starts with a line indicating the number n of houses ( 1n50 000). The next n lines describe the positions of the houses; each of these lines contains two floating point numbers x and y ( -200 000 x, y 200 000), the coordinates of a house in meters. All

第7章 查找技术习题解析

查找技术-----习题解析课后习题讲解1 1. 填空题 ⑴顺序查找技术适合于存储结构为（）的线性表，而折半查找技术适用于存储结构为（）的线性表，并且表中的元素必须是（）。 【解答】顺序存储和链接存储，顺序存储，按关键码有序 ⑵设有一个已按各元素值排好序的线性表，长度为125，用折半查找与给定值相等的元素，若查找成功，则至少需要比较（）次，至多需比较（）次。 【解答】1，7 【分析】在折半查找判定树中，查找成功的情况下，和根结点的比较次数最少，为1次，最多不超过判定树的深度。 ⑷长度为20的有序表采用折半查找，共有（）个元素的查找长度为3。 【解答】4 【分析】在折半查找判定树中，第3层共有4个结点。 ⑸假定一个数列{25，43，62，31，48，56}，采用的散列函数为H(k)=k mod 7，则元素48的同义词是（）。 【解答】62 【分析】H(48)= H(62)=6 ⑹在散列技术中，处理冲突的两种主要方法是（）和（）。 【解答】开放定址法，拉链法 ⑺在各种查找方法中，平均查找长度与结点个数无关的查找方法是（）。 【解答】散列查找 【分析】散列表的平均查找长度是装填因子的函数，而不是记录个数n的函数。 ⑻与其他方法相比，散列查找法的特点是（）。 【解答】通过关键码计算记录的存储地址，并进行一定的比较

2. 选择题 ⑴静态查找与动态查找的根本区别在于（）。 A 它们的逻辑结构不一样 B 施加在其上的操作不同 C 所包含的数据元素的类型不一样 D 存储实现不一样 【解答】B 【分析】静态查找不涉及插入和删除操作，而动态查找涉及插入和删除操作。 ⑵有一个按元素值排好序的顺序表（长度大于2），分别用顺序查找和折半查找与给定值相等的元素，比较次数分别是s和b，在查找成功的情况下，s和b的关系是（）；在查找不成功的情况下，s和b的关系是（）。 A s=b B s>b C s

第7章 查找

第7章查找 一、基本概念 查找（Searching）：就是在按某种数据结构形式存储的数据集合中，找出满足指定条件的结点（或记录）。 1、分类 按查找的条件分类，有按主关键字或次关键字查找。 按查找的数据的存放的存储器分类，可划分为内查找和外查找。 内查找：整个查找过程都在内存进行。 外查找：查找过程中需要访问外存。 按查找的目的分类，可划分为静态查找和动态查找。若在查找的同时对表做修改操作，则相应的表称之为动态查找表（Dynamic Search Table），否则称之为静态查找表（Static Search Table）。 2、平均查找长度ASL（Average Search Length） 在查找过程中对关键字需要执行的平均比较次数。它是衡量一个查找算法次序优劣的标准。 其中：n是结点的个数；p i是查找第i个结点的概率，若不特别声明，均认为每个结点的查找概率相等，即p1=p2=…=p n=1/n；c i是找到第i个结点所需进行的比较次数。 二、线性表的查找 线性表上进行查找的方法主要有三种：顺序查找、二分查找和分块查找。 1、顺序查找 顺序查找（Sequential Search）算法基本思想是：从表的一端开始顺序扫描线性表，依次将扫描到的结点关键字与给定值K相比较，若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。 顺序查找方法适用于线性表的顺序存储结构和链式存储结构。 下面是类型说明及算法：

1）算法中监视哨R[0]的作用是为了在for循环中省去判定防止下标越界的条件，从而节省比较的时间。 2）对于含有n个结点的顺序表，结点的查找在等概率的前提下，对于成功的查找，平均检索长度为(n+1)/2，对于失败的查找，则需要比较n+1次。 2、二分查找（有序表查找） 二分查找（Binary Search）又称为折半查找，它要求线性表中结点必须按关键字值递增或递减顺序排列。 二分查找的基本思想：首先用要查找的关键字K与中间位置的结点的关键字相比较，这个中间结点把线性表分成了两个子表，若比较结果相等则查找完成；若不相等，再根据K与该中间结点关键字的比较大小确定下一步查找哪个子表，这样递归下去，直到找到满足条件的结点或者该线性表中没有这样的结点。 算法如下： 效率分析： 1）在等概率假设下，二分查找成功时的平均查找长度近似于log2(n+1)-1；在最坏情况下查找成功的比较次数为log2n，比顺序查找（最坏n+1次）效率要高。 2）二分查找只适用于顺序存储结构，因此在经常进行删除和插入的表中不适合使用这种查找方法。 3、分块查找(索引顺序表查找) 分块查找（Blocking Search）：又称为索引顺序查找，其性能介顺序查找和二分查找之间。 分块查找的基本思想：分块查找要求把顺序表分成若干块，每一块中的键值存储顺序是任意的，但要求“分块有序”，即前一块中的最大键值小于后一块中最小键值。即块间结点有序，块内结点任意。另外，还需要建立一个索引表，索引表中的每一项对应顺序表的一块，索引项由关键字域和链域组成，关键字域存放对应块内结点的最大键值，链域存放对应块首结点的位置。索引表中的索引项是按键值递增顺序存放。

第7章 查找技术习题解析

查找技术-----习题解析课后习题讲解 1 1. 填空题 ⑴顺序查找技术适合于存储结构为（）的线性表，而折半查找技术适用于存储结构为（）的线性表，并且表中的元素必须是（）。 【解答】顺序存储和链接存储，顺序存储，按关键码有序 ⑵设有一个已按各元素值排好序的线性表，长度为125，用折半查找与给定值相等的元素，若查找成功，则至少需要比较（）次，至多需比较（）次。 【解答】1，7 【分析】在折半查找判定树中，查找成功的情况下，和根结点的比较次数最少，为1次，最多不超过判定树的深度。 ⑷长度为20的有序表采用折半查找，共有（）个元素的查找长度为3。 【解答】4 【分析】在折半查找判定树中，第3层共有4个结点。 ⑸假定一个数列{25，43，62，31，48，56}，采用的散列函数为H(k)=k mod 7，则元素48的同义词是（）。 【解答】62 【分析】H(48)= H(62)=6 ⑹在散列技术中，处理冲突的两种主要方法是（）和（）。 【解答】开放定址法，拉链法 ⑺在各种查找方法中，平均查找长度与结点个数无关的查找方法是（）。 【解答】散列查找 【分析】散列表的平均查找长度是装填因子的函数，而不是记录个数n的函数。 ⑻与其他方法相比，散列查找法的特点是（）。 【解答】通过关键码计算记录的存储地址，并进行一定的比较

2. 选择题 ⑴静态查找与动态查找的根本区别在于（）。 A 它们的逻辑结构不一样 B 施加在其上的操作不同 C 所包含的数据元素的类型不一样 D 存储实现不一样 【解答】B 【分析】静态查找不涉及插入和删除操作，而动态查找涉及插入和删除操作。 ⑵有一个按元素值排好序的顺序表（长度大于2），分别用顺序查找和折半查找与给定值相等的元素，比较次数分别是s和b，在查找成功的情况下，s和b的关系是（）；在查找不成功的情况下，s和b的关系是（）。 A s=b B s>b C s