5.1 静态查找法

5.1 静态查找法

　　考试大纲涉及本节的知识点有：顺序表查找、有序表查找、静态树表查找和索引顺序表查找。

一、选择题

　　1．选择题题目部分
　　● 顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为(n+1)/2，二分法查找只适用于查找顺序存储的有序表，平均比较次数为 （1） 。在此假定N为线性表中节点数，且每次查找都是成功的。
　　（1）A．N+1 B．2log2^N C．log2^N D．N/2
　　● 设有100个节点，用二分法查找时，最大比较次数是 （2） 。
　　（2）A．25 B．50 C．10 D．7
　　● 某顺序存储的表格，其中有90 000个元素，已按关键项的值按上升顺序排列。
　　现假定对各个元素进行查找的概率是相同的，并且各个元素的关键项的值皆不相同。用顺序查找法查找，平均比较次数约为 （3） ，最大比较次数为 （4） 。
　　现把90 000个元素按排列顺序划分成若干组，使每组有g个元素（最后一组可能不足g个）。查找时，先从头一组开始，通过比较各组的最后一个元素的关键项的值，找到欲查找的元素所在的组，然后再用顺序查找法找到欲找的元素。在这种查找法中，使总的平均比较次数最小是 （5） ，此时的平均比较次数是 （6） 。
　　当g的值大于等于90 000时，此方法的查找速度接近于 （7） 。　
　　（3）A．25 000　　　B．30 000　　　　　C．45 000　　D．90 000
　　（4）A．25 000　　　B．30 000 　　　　 C．45 000　　D．90 000
　　（5）A．100　　　　 B．200　　　　　　 C．300　　　D．400
　　（6）A．100　　　　 B．200　　　　　　 C．300　　　D．400
　　（7）A．快速分类法　B．斐波那契查找法　C．二分法　　D．顺序查找法
　　● 若一个表中共有900个元素，查找每个元素的概率相同，采用索引顺序查找，并假定采用顺序查找法来确定所在的块时，将表分成 （8） 块的查找性能最优。
　　（8）A．30 B．5 C．90 D．100
　　● 当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度 （9） 。
　　（9）A．必定快　　　　　　　B．不一定
　　　　 C．在大部分情况下要快　D．取决于表是递增还是递减
　　● 在等概率情况下，线性表的顺序查找的平均查找长度ASL为O(n)，有序表的折半查找的ASL为O(log₂ⁿ)，对静态树表，在最坏的情况下，ASL为 （10） ，而当它是一棵平衡树时，ASL为O(log₂ⁿ)。
　　（10）A．O(n) B．O(log₂ⁿ) C．O((log₂ⁿ)/2) D．O(nlog₂ⁿ)
　　2．选择题练习的答案与分析
　　题号 （1）
　　答案 C
　　习题分析：
　　顺序查找的平均比较次数为，折半查找的平均比较次数为，答案C符合要求。
　　题号 （2）
　　答案 D
　　习题分析：
　　二分法查找，最大的比较次数应为log₂ⁿ⁺¹，因此应为7次。
　　题号 （3） （4） （5） （6） （7）
　　答案 　C　　  D 　　C 　　C 　　D
　　习题分析：
　　本题考查了线性表的查找方法。人们常用以下两个值来衡量解决查找问题的方法A的有效性：
　　　　　　MAX(A)=为找到具有给定键值的节点所需的比较次数的最大值
　　　　　　AVG(A)=为找到具有给定键值的节点所需的比较次数的平均值
　　对线性表进行查找的基本方法有：顺序查找法、二分查找法和分块查找法等。
　　顺序查找法是最简单的查找方法。它把线性表中的节点的键依次与给定的键值作比较，如果找到所需节点，则查找成功；如果查遍整个线性表仍未找到所需节点，则查找失败。
　　　　　　　　MAX（顺序查找法）=表中元素个数n
　　如果表中每个元素被查找的概率相同，那么：
　　　　　　　　　　AVG（顺序查找法）≈n/2
　　在本题中，对90 000个元素进行顺序查找，其平均比较次数为4500次，最大比较次数为90 000次。
　　题目中给出的第二种查找方法是分块查找法。假定有一个有n个元素的线性表F，并有m个正整数g1,g2,…,gm，其中g1+g2+…+gm=n。把表F划分成为m组，每组中有gi个元素，即F的头g1个元素构成组F1，接着g2个元素构成组F2，依此类推得到m个F的分组Fi。查找时，先把键值与Fi的最后一个元素的键值进行比较，以确定该键值对应的元素所在的组，然后再在组中顺序查找被查找的元素。查找时为了找到第i个组，要经过i次比较，找到所在组的最大比较次数是m次，在组中用顺序查找法，最多次数为g次，由此得到：
　　　　　　　　　MAX（分块查找法）=max{i+gi|i=1,2,…,m}
　　　　　　　　　　　AVG分块查找法）=

　　在本题中，每组元素个数都为g，而m=n/g，n=90 000，因此：
　　　　　　　　　　　MAX（分块查找法）=n/g+g=90 000/g+g
　　　　　　　　　　　AVG（分块查找法）=(m+g+2)/2≈(m+g)/2
　　由于m*g=n，所以要使AVG最小只有使m=g=300，此时，AVG（分块查找法）≈300。
　　如果g的值大于等于90 000，那就意味着整个表F都分在第一组。由于在组内用顺序查找法，因此此时分块查找法相当于顺序查找法。其实，若g=1，那么分块查找法也退化为顺序查找法。
　　题号 （8）
　　答案 A
　　习题分析：
　　题目中说明了是索引顺序查找，这就说明了分的数据块具有块内无序、块间有序的特点。
　　下面来分别计算题目备选答案中给出的分块方案的平均查询时间。
　　A．分30块，这样每块30个元素：
　　　　　　　　查找时间为(30+1)/2+(30+1)/2=62/2
　　B．分45块，这样每块20个元素：
　　　　　　　　查找时间为(45+1)/2+(20+1)/2=67/2
　　C．分90块，这样每块10个元素：
　　　　　　　　查找时间为(90+1)/2+(10+1)/2=102/2
　　D．分100块，这样每块9个元素：
　　　　　　　　查找时间为(100+1)/2+(9+1)/2=111/2
　　题号 （9）
　　答案 C
　　习题分析：
　　在一般情况下，折半查找的时间效率为O(log₂^N)，而顺序查找的平均比较次数为O(N)。
　　题号 （10）
　　答案 A
　　习题分析：
　　静态树表在最坏情况下退化为一棵单分支树，相当于线性表的顺序查找。
　　3．训练自测表（如表5-1所示）

表5-1 选择题练习自测表