某一维数组中依次存放了数据元素15 23 38 47 55 62 88 95 102 123 采用折半（二分）法..

2010年下半年上午试卷综合知识

第 60 题


知识点	数组查找
关键词	数据一维数组数组
章/节	计算机软件知识

某一维数组中依次存放了数据元素15, 23, 38, 47, 55, 62, 88, 95, 102, 123, 采用折半（二分）法查找元素95时，依次与（60)进行了比较。

A. 62, 88, 95

B. 62, 95

C. 55, 88, 95

D. 55, 95

相关试题计算机软件知识

第23题

2011年上半年

某文件管理系统在磁盘上建立了位示图（bitmap)，记录磁盘的使用情况。若系统的字长为32位，磁盘上的物理块依次编号为0、1、2、…，那么4096号物理块的使用..

第23题

2022年上半年

嵌入式操作系统的(23)是指“从减少成本和缩短研发周期考虑，要求嵌入式操作系统能针对硬件变化进行结构与功能上的配置，以满足不同应用需要”

第56题

2016年上半年

某公司数据库中的元件关系模式为P（元件号，元件名称，供应商，供应商所在地，库存量），函数依赖集F如下所示：
F={元件号→元件名称，（元件号，供应商..

知识点讲解

· 数组

· 查找

数组

数组的定义及基本运算

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

查找

1）顺序查找

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

2）折半查找

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

3）分块查找

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

4）哈希表及其查找

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

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

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