《数据结构》《数据结构》（（CC语言版）语言版）第第99章查找章查找计算机与信息工程学院计算机与信息工程学院于江德于江德复习提要复习提要查找方法比较式查找法计算式查找法基于树的查找法基于线性表的查找法分块（或索引顺序表）查找法折半（或二分）查找法顺序查找法对存储结构和关键字排列方式没有特殊要求只适合顺序存储的有序表另建一个索引表，分块有序，块间可用折半查找，块内顺序查找二叉排序树平衡二叉树（AVL）B-树B+树——哈希法/散列法/杂凑法在记录存储位置与关键字之间建立确定的关系——哈希函数左子树上所有节点的值<根节点的值<右子树上所有节点的值左、右子树深度之差的绝对值不超过1的二叉排序树一种平衡的多路查找树，m叉树B-树的变型树，关键字信息全部在叶子结点中，其它结点是其索引31.1.某顺序存储的表格中有某顺序存储的表格中有9000090000个元素，已个元素，已按关键字值升序排列，假定对每个元素进按关键字值升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关行查找的概率是相同的，且每个元素的关键字的值皆不相同。用顺序查找法查找时，键字的值皆不相同。用顺序查找法查找时，平均比较次数约为（）平均比较次数约为（）AA．．2500025000BB．．3000030000CC．．4500045000DD．．900009000042.2.若查找每个记录的概率均等，则在具有若查找每个记录的概率均等，则在具有nn个记录的连续顺序文件中采用顺序查找法查个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度找一个记录，其平均查找长度ASLASL为为()()。。A.(n-1)/2B.n/2A.(n-1)/2B.n/2C.(n+1)/2D.nC.(n+1)/2D.n52’.2’.对长度为对长度为nn的有序单链表，若查找每个元的有序单链表，若查找每个元素的概率相等，则顺序查找到表中任一元素素的概率相等，则顺序查找到表中任一元素的平均查找长度为（）。的平均查找长度为（）。AA．．n/2n/2BB．（．（n+1n+1））/2/2CC．（．（nn－－11））/2/2DD．．n/4n/463.3.下面关于二分查找的叙述正确的是下面关于二分查找的叙述正确的是()()A.A.表必须有序，表可以顺序方式存储，也可以链表必须有序，表可以顺序方式存储，也可以链表方式存储表方式存储B.B.表必须有序且表中数据必须是整型，实型或字表必须有序且表中数据必须是整型，实型或字符型符型C.C.表必须有序，而且只能从小到大排列表必须有序，而且只能从小到大排列D.D.表必须有序，且表只能以顺序方式存储表必须有序，且表只能以顺序方式存储74.4.有一个长度为有一个长度为1212的有序表，按二分查找法的有序表，按二分查找法对该表进行查找，在表内各元素等概率情对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均比较次数为（况下，查找成功所需的平均比较次数为（））A.37/12A.37/12B.35/12B.35/12C.39/12C.39/12D.43/12D.43/12先看一个具体的情况，假设：先看一个具体的情况，假设：n=1n=111分析分析折半查找折半查找的平均查找长度的平均查找长度66663333999911114444101022225555777788881111111112121212判定树判定树i1234567891011Ci112222333333334444444412495.5.适用于折半查找的表的存储方式及元素排适用于折半查找的表的存储方式及元素排列要求为列要求为()()AA．链接方式存储，元素无序．链接方式存储，元素无序BB．链接方式存储，元素有序．链接方式存储，元素有序CC．顺序方式存储，元素无序．顺序方式存储，元素无序DD．顺序方式存储，元素有序．顺序方式存储，元素有序106.6.有一个有序表为有一个有序表为{1,3,9,12,32,41,45,62,75,77,{1,3,9,12,32,41,45,62,75,77,82,95,100},82,95,100},当二分查找值为当二分查找值为8282的结点时的结点时,,（（）次比较后查找成功。）次比较后查找成功。A.1B.2C.4D.8A.1B.2C.4D.8117.7.具有具有1212个关键字的有序表，折半查找的平个关键字的有序表，折半查找的平均查找长度（）均查找长度（）A.3.1B.4C.2.5D.5A.3.1B.4C.2.5D.5128.8.当采用分块查找时，数据的组织方式为当采用分块查找时，数据的组织方式为(())AA．数据分成若干块，每块内数据有序．数据分成若干块，每块内数据有序BB．数据...
