免费智能真题库 > 历年试卷 > 数据库系统工程师 > 2019年上半年 数据库系统工程师 上午试卷 综合知识
第10题      2019年上半年 数据库系统工程师 上午试卷 综合知识
所属知识点   数据结构与算法        关键词   有序数组   数组
考点辞典   数组   数组   查找

 
已知有序数组a的前10000个元素是随机整数,现需查找某个整数是否在该数组中。以下方法中,( )的查找效率最高。
 
 
  A.  二分查找法
 
  B.  顺序查找法
 
  C.  逆序查找法
 
  D.  哈希查找法
 
 
 

  数据结构与算法 知识点 更多相关真题:    更多>  
 
  第9题    2019年上半年  
   65%
某有向图G的邻接表如下图所示,可看出该图中存在弧<v2, v3>,而不存在从顶点V1出发的弧。以下关于图G的叙述中,错误的是( )。
  第8题    2019年上半年  
   61%
对于给定的关键字序列{47, 34, 13, 12, 52, 38, 33, 27, 5},若用链地址法(拉链法)解决冲突来构造哈希表,且哈希函数为H(key)=key%ll,则( )。
  第8题    2018年上半年  
   40%
设有n阶三对角矩阵A,即非零元素都位于主对角线以及与主对角线平行且紧邻的两条对角线上,现对该矩阵进行按行压缩存储,若其压储空间用数组B表示,A的元素下标从0开始,B的元素下标从1开始。已知..
 

数组
       数组的定义及基本运算
       n维数组是一种"同构"的数据结构,其每个元素类型相同、结构一致。数组是定长线性表在维数上的扩张,即线性表中的元素又是一个线性表。
       数组结构的特点是:数据元素数目固定;数据元素具有相同的类型;数据元素的下标关系具有上下界的约束且下标有序。
       对数组进行的基本运算有以下两种。
       (1)给定一组下标,存取相应的数据元素。
       (2)给定一组下标,修改相应的数据元素中某个数据项的值。
       数组的顺序存储
       一旦定义了数组,结构中的数据元素个数和元素之间的关系就不再发生变动,因此数组适合于采用顺序存储结构。
       由于计算机的内存结构是一维线性的,因此存储多维数组时必须按照某种方式进行降维处理,即将数组元素排成一个线性序列,这就产生了次序约定问题。对二维数组有两种存储方式:一种是以列为主序的存储方式;另一种是以行为主序的存储方式。
未完......点击标题查看......
数组
数组是最常用的数据结构之一,在程序中,数组常用来实现顺序存储的线性表。数组由固定个数的元素组成,全部元素的类型相同,元素依次顺序存储。每个元素对应一个下标,数组元素按数组名和元素的下标引用,引用数组元素的下标个数称为数组的维数。
在C语言中,n个元素的数组中,第一个元素的下标为0,最后一个元素的下标为n-1。
数组可以分为静态数组和动态数组两类。
(1)静态数组是指数组的存储空间分配是在使用之前进行,在程序运行中不能改变,不利于数组的扩展。
(2)动态数组是在程序执行中进行数组存储空间的分配。
动态数组一般采用链式存储结构,而静态数组一般采用顺序存储结构。
数组元素可以是任意类型,当元素本身又是数组时,就构成了多维数组。多维数组是一维数组的推广,最常用的是二维数组。在C语言中,数组元素按行优先顺序存放。
一般用多维数组表示矩阵,矩阵的类型有对称矩阵、三角矩阵(下三角矩阵或上三角矩阵)和对角矩阵。
稀疏矩阵的存储:用顺序存储结构的三元数组对稀疏矩阵进行存储,分别记录行、列和值。
未完......点击标题查看......
查找
1)顺序查找
顺序查找又称线性查找,顺序查找的过程是从线性表的一端开始,依次逐个与表中元素的关键字值进行比较,如果找到其关键字与给定值相等的元素,则查找成功;若表中所有元素的关键字与给定值比较都不成功,则查找失败。
2)折半查找
折半查找的过程是先将给定值与有序线性表中间位置上元素的关键字进行比较,若两者相等,则查找成功;若给定值小于该元素的关键字,那么选取中间位置元素关键字值小的那部分元素作为新的查找范围,然后继续进行折半查找;如果给定值大于该元素的关键字,那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围,然后继续进行折半查找,直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。
3)分块查找
在分块查找过程中,首先将表分成若干块,每一块中关键字不一定有序,但块之间是有序的。此外,还建立了一个索引表,索引表按关键字有序。分块查找过程需分两步进行:先确定待查记录所在的块;然后在块中顺序查找。
4)哈希表及其查找
根据设定的哈希函数H(key)和处理冲突的方法,将一组关键字映射到一个有限的连续地址集上,并以关键字在地址集中的像作为记录在表中的存储位置,这种表称为哈希表,也称散列表。这一过程所得到的存储位置称为散列地址,由此形成的查找方法称为散列查找。
未完......点击标题查看......

 题号导航      2019年上半年 数据库系统工程师 上午试卷 综合知识   本试卷我的完整做题情况 
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
↓第10题