在12个互异元素构成的有序数组a[1..12] 中进行二分查找(即折半查找，向下取整)，若待查..

2017年上半年上午试卷综合知识

第 61 题


知识点	数组折半查找查找
关键词	二分查找有序数组数组
章/节	计算机软件知识

在12个互异元素构成的有序数组a[1..12] 中进行二分查找(即折半查找，向下取整)，若待查找的元素正好等于a[9]，则在此过程中，依次与数组中的( )比较后，查找成功结束。

A. a[6]、a[7]、a[8]、a[9]

B. a[6]、a[9]

C. a[6]、a[7]、a[9]

D. a[6]、a[8]、a[9]

相关试题计算机软件知识

第4题

2023年上半年

中断向量提供的是（）。

第62题

2009年上半年

设L为广义表，将head(L)定义为取非空广义表的第一个元素，tail(L)定义为取非空广义表除第一个元素外剩余元素构成的广义表。若广义表L=((x，y，z)，a，(u,t,w))，..

第25题

2010年上半年

某进程有5个页面，页号为0〜4,页面变换表如下所示。表中状态位等于0和1分别表示页面不在内存或在内存。若系统给该进程分配了3个存储块，当访问的页面3不在..

知识点讲解

· 数组

· 折半查找

· 查找

数组

数组的定义及基本运算

n维数组是一种"同构"的数据结构，其每个元素类型相同、结构一致。数组是定长线性表在维数上的扩张，即线性表中的元素又是一个线性表。

数组结构的特点是：数据元素数目固定；数据元素具有相同的类型；数据元素的下标关系具有上下界的约束且下标有序。

对数组进行的基本运算有以下两种。

（1）给定一组下标，存取相应的数据元素。

（2）给定一组下标，修改相应的数据元素中某个数据项的值。

数组的顺序存储

一旦定义了数组，结构中的数据元素个数和元素之间的关系就不再发生变动，因此数组适合于采用顺序存储结构。

由于计算机的内存结构是一维线性的，因此存储多维数组时必须按照某种方式进行降维处理，即将数组元素排成一个线性序列，这就产生了次序约定问题。对二维数组有两种存储方式：一种是以列为主序的存储方式；另一种是以行为主序的存储方式。

设每个数据元素占用L个单元，m、n为数组的行数和列数，那么以行为主序优先存储的地址计算公式为

Loc(a_ij)=Loc(a₁₁)+((i-1)n+(j-1))L

同样的，以列为主序优先存储的地址计算公式为

Loc(a_ij)=Loc(a₁₁)+((j-1)m+(i-1))L

折半查找

折半查找的基本思想是：设查找表的元素存储在一维数组r[1…n]中，那么在表中的元素已经按关键字递增（或递减）的方式排序的情况下，可进行折半查找。其方法是：首先将待查的key值与表r中间位置上（下标为mid）记录的关键字进行比较，若相等则查找成功；若key>r[mid].key，则说明待查记录只可能在后半个子表r[mid+1…n]中，下一步应在后半个子表中再进行折半查找；若key<r[mid].key，说明待查记录只可能在前半个子表r[1…mid-1]中，下一步应在r的前半个子表中进行折半查找。这样通过逐步缩小范围，直到查找成功或子表为空时失败为止。

折半查找的性能分析：折半查找的过程可以用一棵二叉树描述，不妨设节点总数为n=2^h-1，则判定树是深度为h=log₂(n+1)的满二叉树。在等概率情况下，折半查找的平均查找长度为

。

当n值较大时，ASL_bs≈log₂(n+1)-1。

折半查找比顺序查找的效率高，但它要求查找表进行顺序存储并且按关键字有序排列，因此对表进行元素的插入和删除时，需要移动大量的元素，所以折半查找适用于表不易变动，且又经常进行查找的情况。

查找

1）顺序查找

顺序查找又称线性查找，顺序查找的过程是从线性表的一端开始，依次逐个与表中元素的关键字值进行比较，如果找到其关键字与给定值相等的元素，则查找成功；若表中所有元素的关键字与给定值比较都不成功，则查找失败。

2）折半查找

折半查找的过程是先将给定值与有序线性表中间位置上元素的关键字进行比较，若两者相等，则查找成功；若给定值小于该元素的关键字，那么选取中间位置元素关键字值小的那部分元素作为新的查找范围，然后继续进行折半查找；如果给定值大于该元素的关键字，那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围，然后继续进行折半查找，直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。

3）分块查找

在分块查找过程中，首先将表分成若干块，每一块中关键字不一定有序，但块之间是有序的。此外，还建立了一个索引表，索引表按关键字有序。分块查找过程需分两步进行：先确定待查记录所在的块；然后在块中顺序查找。

4）哈希表及其查找

根据设定的哈希函数H（key）和处理冲突的方法，将一组关键字映射到一个有限的连续地址集上，并以关键字在地址集中的像作为记录在表中的存储位置，这种表称为哈希表，也称散列表。这一过程所得到的存储位置称为散列地址，由此形成的查找方法称为散列查找。

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5