5.1 静态查找法
5.1 静态查找法
考试大纲涉及本节的知识点有:顺序表查找、有序表查找、静态树表查找和索引顺序表查找。
一、选择题
1.选择题题目部分
● 顺序查找法适用于查找顺序存储或链式存储的线性表,平均比较次数为(n+1)/2,二分法查找只适用于查找顺序存储的有序表,平均比较次数为 (1) 。在此假定N为线性表中节点数,且每次查找都是成功的。
(1)A.N+1 B.2log2N C.log2N 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(log2n),对静态树表,在最坏的情况下,ASL为 (10) ,而当它是一棵平衡树时,ASL为O(log2n)。
(10)A.O(n) B.O(log2n) C.O((log2n)/2) D.O(nlog2n)
2.选择题练习的答案与分析
题号 (1)
答案 C
习题分析:
顺序查找的平均比较次数为,折半查找的平均比较次数为,答案C符合要求。
题号 (2)
答案 D
习题分析:
二分法查找,最大的比较次数应为log2n+1,因此应为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(log2N),而顺序查找的平均比较次数为O(N)。
题号 (10)
答案 A
习题分析:
静态树表在最坏情况下退化为一棵单分支树,相当于线性表的顺序查找。
3.训练自测表(如表5-1所示)
表5-1 选择题练习自测表
题 号 | 考 查 点 | 得 分 |
(1) | 二分法查找的平均比较次数 | |
(2) | 二分法查找的最大比较次数 | |
(3)~(7) | 顺序查找和二分法查找 | |
(8) | 索引顺序查找 | |
(9) | 顺序查找和二分法查找的比较 | |
(10) | 静态树表的查找 |
5.1 静态查找法
未经允许不得转载:5.1 静态查找法