免费智能真题库 > 历年试卷 > 数据库系统工程师 > 2019年上半年 数据库系统工程师 上午试卷 综合知识
第7题      2019年上半年 数据库系统工程师 上午试卷 综合知识
所属知识点   数据结构与算法       
考点辞典   B-树      查找   

 
B-树是一种平衡的多路查找树。以下关于B-树的叙述中,正确的是( )。
 
 
  A.  根结点保存树中所有关键字且有序排列
 
  B.  从根结点到每个叶结点的路径长度相同
 
  C.  所有结点中的子树指针个数都相同
 
  D.  所有结点中的关键字个数都相同
 
 
 

  数据结构与算法 知识点 更多相关真题:    更多>  
 
  第5题    2019年上半年  
   44%
令序列X、Y、Z的每个元素都按顺序进栈,且每个元素进栈和出栈仅一次。则不可能得到的出栈序列是( )。
  第6题    2019年上半年  
   48%
以下关于单链表存储结构特征的叙述中,不正确的是( )。
  第8题    2018年上半年  
   40%
设有n阶三对角矩阵A,即非零元素都位于主对角线以及与主对角线平行且紧邻的两条对角线上,现对该矩阵进行按行压缩存储,若其压储空间用数组B表示,A的元素下标从0开始,B的元素下标从1开始。已知..
 

B-树
B-树的定义:一棵m阶的B-树,或为空树,或为满足下列特性的m叉树。
(1)树中每个节点至多有m棵子树。
(2)若根节点不是叶子节点,则至少有两棵子树。
(3)除根之外的所有非终端节点至少有棵子树。
(4)所有的非终端节点中包含下列数据信息,即
n,A0,K1,A1,K2A2,…,Kn,An)
式中,Ki(i=1,2,…,n)为关键字,且Ki<Ki+1(i=1,2,…,n-1);Ai(i=1,2,…,n)为指向子树根节点的指针,且指针Ai-1,所指子树中所有节点的关键字均小于Ki(i=1,2,…,n),An所指子树中所有节点的关键字均大于Kn,为节点中关键字的个数。
(5)所有的叶子节点都出现在同一层次上,并且不带信息(可以看作外部节点或查找失败的节点,实际上这些节点不存在,指向这些节点的指针为空)。
B-树上进行查找的过程是:首先在根节点所包含的关键字中查找给定的关键字,若找到则成功返回;否则确定待查找的关键字所在的子树并继续进行查找,直到查找成功或查找失败(指针为空)时为止。
未完......点击标题查看......
1)定义
树型结构是一类重要的非线性数据结构,其中以树和二叉树最为常用。
树是由一个或多个节点组成的有限集T,它满足以下两个条件:有一个特定的节点称为根节点;其余的节点分成m个互不相交的有限集T1, T2, …, Tm,其中每个集又都是一棵树,称T1, T2, …, Tm为根节点的子树。
可见树的定义是递归的,即一棵树由子树构成,子树又由更小的子树构成。
2)相关概念
.一个节点的子树数目称为该节点的度。
.树中各节点的度的最大值称为树的度。
.树中节点的最大层次称为树的深度。
若将树中节点的各子树看成是从左到右具有次序的,即不能交换,则称该树为有序树,否则称为无序树。
未完......点击标题查看......
查找
1)顺序查找
顺序查找又称线性查找,顺序查找的过程是从线性表的一端开始,依次逐个与表中元素的关键字值进行比较,如果找到其关键字与给定值相等的元素,则查找成功;若表中所有元素的关键字与给定值比较都不成功,则查找失败。
2)折半查找
折半查找的过程是先将给定值与有序线性表中间位置上元素的关键字进行比较,若两者相等,则查找成功;若给定值小于该元素的关键字,那么选取中间位置元素关键字值小的那部分元素作为新的查找范围,然后继续进行折半查找;如果给定值大于该元素的关键字,那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围,然后继续进行折半查找,直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。
3)分块查找
在分块查找过程中,首先将表分成若干块,每一块中关键字不一定有序,但块之间是有序的。此外,还建立了一个索引表,索引表按关键字有序。分块查找过程需分两步进行:先确定待查记录所在的块;然后在块中顺序查找。
4)哈希表及其查找
根据设定的哈希函数H(key)和处理冲突的方法,将一组关键字映射到一个有限的连续地址集上,并以关键字在地址集中的像作为记录在表中的存储位置,这种表称为哈希表,也称散列表。这一过程所得到的存储位置称为散列地址,由此形成的查找方法称为散列查找。
未完......点击标题查看......
       树的存储结构及遍历操作
       树是非线性结构,存储树时,须把树中结点之间存在的关系反映在树的存储结构中。树有很多存储结构,这里仅介绍最常用的两种。
       1)树的标准存储结构
       树的标准存储结构由结点的数据和指向子结点的指针数组组成;对于度为M的树,其指针数组中的元素个数为M。
       2)树的带逆存储结构
       由于树的带逆存储结构需要一个从子结点指向父结点的指针,因而该结构在标准存储结构的基础上,需要在树的结点中增加一个指向其双亲结点位置的指针。
       树的遍历是树的基本操作之一,也是最重要的操作之一。树的遍历含义是指:按照某种要求依次访问树中的每个结点,每个结点均被访问一次且仅被访问一次。常用的树的遍历方法可分为前序遍历、后序遍历和中序遍历。
       (1)树的前序遍历。首先访问根结点,然后从左到右前序遍历根结点的各棵子树。树的前序遍历递归算法如下:
       
未完......点击标题查看......

 题号导航      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 /
 
↓第7题