免费智能真题库 > 历年试卷 > 程序员 > 2020年下半年 程序员 上午试卷 综合知识
  第40题      
  知识点:   二叉树   数组
  章/节:   常用数据结构       

 
对于一棵结点数为n(n>1)的完全二叉树,从根结点这一层开始,按照从上往下、从左到右的顺序,把结点依次存储在数组A[1..n]中。设某结点在数组A中的位置为i,且它有右孩子,则该右孩子结点在A中的位置是( )。
 
 
  A.  2i-1
 
  B.  2i
 
  C.  2i+1
 
  D.  log2(i+1)
 
 
 

  相关试题:树          更多>  
 
  第41题    2013年下半年  
   50%
在一棵非空的二叉排序树(二叉查找树)中,进行(41)遍历运算并输出所访问结点的关键码后,可得到一个有序序列。
  第40题    2011年下半年  
   32%
非空二叉排序树的定义是:若根结点具有左子树,则左子树中所有结点的关键码均小于根结点的关键码;若根结点具有右子树,则右子树..
  第38题    2019年上半年  
   65%
根据权值集合{0.30, 0.25, 0.25, 0.12, 0.08}构造的哈夫曼树中,每个权值对应哈夫曼树中的一个叶结点,( )。
   知识点讲解    
   · 二叉树    · 数组
 
       二叉树
               二叉树的定义
               二叉树(Binary Tree)是n(n≥0)个节点的有限集合,它或者是空树(n=0),或者是由一个根节点及两棵互不相交的、分别称为左子树和右子树的二叉树所组成。
               二叉树与树的区别如下。
               .二叉树的节点的子树要区分左子树和右子树,即使在节点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。
               .二叉树的节点的最大度为2,而树中不限制节点的度数。
               二叉树的运算
               二叉树的基本运算是遍历,其他运算可建立在遍历运算的基础上。
               二叉树的性质
               二叉树具有以下性质。
               (1)二叉树第i层上的节点数目最多为2i-1(i≥1)个。
               (2)深度为k的二叉树至多有2k-1(k≥1)个节点。
               (3)在任意一棵二叉树中,若终端节点数为n0,度为2的节点数为n2,则n0=n2+1。
               (4)具有n个节点的完全二叉树的深度为[log2n]+1。
               (5)对一棵有n个节点的完全二叉树的节点按层次自左至右进行编号,则对任意节点i有以下性质。
               .若i=1,则节点i是二叉树的根,无双亲;若i>1,则其双亲为
               .若2i>n,则节点i无左孩子;否则其左孩子为2i
               .若2i+1>n,则节点i无右孩子;否则其右孩子为2i+1。
               若深度为k的二叉树有2k-1个节点,则称其为满二叉树。
               深度为k、有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树编号从1至n的节点一一对应时,称之为完全二叉树。
               二叉树的存储结构
               1)顺序存储结构
               用一组地址连续的存储单元存储二叉树中的数据元素,必须把节点排成一个适当的线性序列,并且节点在这个序列中的相互位置能反映出节点之间的逻辑关系。
               顺序存储结构用于完全二叉树时既简单又节省空间,而对于一般二叉树则不适用。因为在顺序存储结构中,以节点在存储单元中的位置来表示节点之间的关系,那么对于一般的二叉树来说,也必须按照完全二叉树的形式存储,也就是要添上一些实际并不存在的"虚节点",这将造成空间的浪费。
               2)链式存储结构
               由于二叉树中的节点包含有数据元素、左子树根、右子树根及双亲等信息,因此可以用三叉链表或二叉链表来存储二叉树,链表的头指针指向二叉树的根节点。
               二叉树的遍历
               遍历是指按某种策略访问树中的每个节点,且仅访问一次。由于二叉树所具有的递归性质,一棵非空的二叉树可以看作由根节点、左子树和右子树三部分构成,因此若能依次遍历这三部分中的每个节点信息,也就遍历了整棵二叉树。按照遍历左子树要在遍历右子树之前进行的约定,根据访问根节点位置的不同,可得到二叉树的前序、中序和后序3种遍历方法。
               遍历二叉树的基本操作就是访问节点,不论按照哪种次序遍历,对含有n个节点的二叉树,遍历算法的时间复杂度都为O(n)。在最坏情况下,二叉树是有n个节点且深度为n的单枝树,遍历算法的空间复杂度也为O(n)。
               遍历二叉树的过程实质上是按一定规则,将树中的节点排成一个线性序列的过程,因此遍历操作得到的是树中节点的一个线性序列。在每一种序列中,有且仅有一个起始点和一个终节点,其余节点有且仅有唯一的直接前驱和直接后继。
               对二叉树还可以进行层序遍历。层序遍历就是从树的根节点出发,首先访问第1层的树根节点,然后从左到右依次访问第2层上的节点,以此类推,自上而下、自左到右逐层访问树中各层上节点的过程。
               线索二叉树
               若n个节点的二叉树采用链表作存储结构,则链表中含有n+1个空指针域,利用这些空指针域来存放指向节点的前驱和后继信息。线索链表的节点结构如下图所示。
               
               线索链表的节点结构
               若二叉树的二叉链表采用上图所示的节点结构,则相应的链表称为线索链表,其中指向节点前驱、后继的指针称为线索,加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。
               二叉树的应用:最优二叉树
               霍夫曼树又称最优二叉树,是一类带权路径长度最短的树。
               路径:是指从树中一个节点到另一个节点之间的通路,路径上的分支数目称为路径长度。
               树的路径长度:是从树根到每一个叶子的路径长度之和。节点的带权路径长度为从该节点到树根之间的路径长度与该节点权的乘积。
               树的带权路径长度:指树中所有叶子节点的带权路径长度之和,记为
               
               式中,n为带权叶子节点的数目;wi为叶子节点的权值;li为叶子节点到根的路径长度。
               霍夫曼树是指权值为w1w2,…,wnn个叶子节点的二叉树中带权路径长度最小的二叉树。
               构造最优二叉树的霍夫曼算法如下。
               (1)根据给定的n个权值w1w2,…,Wn构成n棵二叉树的集合F={T1,T2,…,Tn},其中每棵二叉树Ti中只有一个带权为wi的根节点,其左右子树均空。
               (2)在F中选取两棵根节点的权值最小的树作为左右子树,构造一棵新的二叉树,置新构造二叉树的根节点的权值为其左、右子树根节点的权值之和。
               (3)从F中删除这两棵树,同时将新得到的二叉树加入到F中。
               重复(2)、(3),直到F中只含一棵树时为止。这棵树便是霍夫曼树。
               树和森林
               1)树的存储结构
               .树的双亲表示法:用一组地址连续的单元存储树的节点,并在每个节点中附设一个指示器,指示其双亲节点在该存储结构中的位置。显然这种表示对于求指定节点的双亲或祖先都十分方便,但对于求指定节点的孩子及后代则需要遍历整个数组。
               .树的孩子表示法:在存储结构中用指针指示出节点的每个孩子,由于树中每个节点的子树数目不尽相同,因此在采用链式存储结构时可以考虑多重链表。
               .树的孩子兄弟表示法:又称二叉链表表示法。在链表的节点中设置两个指针域分别指向该节点的第一个孩子和下一个兄弟。利用这种存储结构便于实现树的各种操作。
               2)树和森林的遍历
               (1)树的遍历。树的遍历分为先根遍历和后根遍历两种。
               .先根遍历:先访问树的根节点,然后依次先根遍历根的各棵子树。对树的先根遍历等同于对转换所得的二叉树进行先序遍历。
               .后根遍历:先依次后根遍历树根的各棵子树,然后访问树根节点。树的后根遍历等同于对转换所得的二叉树进行中序遍历。
               (2)森林的遍历。森林的遍历分为前序遍历和后序遍历两种。
               .前序遍历森林:若森林非空,访问森林中第一棵树的根节点,前序遍历第一棵子树根节点的子树森林,再前序遍历除第一棵树之外剩余的树所构成的森林。
               .后序遍历森林:若森林非空,后序遍历森林中第一棵树的子树森林,访问第一棵树的根节点,后序遍历除第一棵树之外剩余的树所构成的森林。
               3)树、森林与二叉树的转换
               (1)树、森林转换为二叉树。利用树的孩子兄弟表示法可导出树与二叉树的对应关系,在树的孩子兄弟表示法中,从物理结构上看与二叉树的二叉链表表示法相同,因此就可以用这种同一存储结构的不同解释将一棵树转换为一棵二叉树。
               将一个森林转换为一棵二叉树的方法是:先将森林中的每一棵树转换为二叉树,再将第一棵树的根作为转换后的二叉树的根,第一棵树的左子树作为转换后二叉树根的左子树,第二棵树作为转换后二叉树根的右子树,第三棵树作为转换后二叉树根的右子树的右子树,以此类推,森林就可以转换为一棵二叉树。
               (2)二叉树转换为树和森林。若二叉树非空,则二叉树根及其左子树为第一棵树的二叉树形式,二叉树根的右子树又可以看作一个由森林转换后的二叉树,应用同样的方法,直到最后产生一棵没有右子树的二叉树为止,这样就得到了一个森林。为了进一步得到树,可用树的二叉链表表示的逆方法,即节点的右子树的根、右子树的右子树的根……找出原本是同一个双亲的兄弟。二叉树转换为树或森林是唯一的。
 
       数组
               数组的定义及基本运算
               一维数组是长度固定的线性表,数组中的每个数据元素类型相同。n维数组是定长线性表在维数上的扩张,即线性表中的元素又是一个线性表。
               设有n维数组Ab1b2,…,bn],其每一维的下界都为1,bi是第i维的上界。从数据结构的逻辑关系角度来看,A中的每个元素Aj1j2,…,jn](1≤jibi)都被n个关系所约束。在每个关系中,除第一个和最后一个元素外,其余元素都只有一个直接后继和一个直接前驱。因此就单个关系而言,这n个关系仍是线性的。
               以下面的二维数组Am][n]为例,可以把它看成是一个定长的线性表,它的每个元素也是一个定长线性表。
               
               可将A看作一个行向量形式的线性表:
               Am*n=[[a11a12a1n][a21a22a2n]…[am1am2amn]]
               也可将A看作列向量形式的线性表:
               Am*n=[[a11a21am1][a12a22am2]…[a1na2namn]]
               数组结构的特点如下:
               (1)数据元素数目固定。一旦定义了一个数组结构,就不再有元素的增减变化。
               (2)数据元素具有相同的类型。
               (3)数据元素的下标关系具有上下界的约束且下标有序。
               在数组中通常做下面两种操作:
               (1)取值操作。给定一组下标,读其对应的数据元素。
               (2)赋值操作。给定一组下标,存储或修改与其相对应的数据元素。
               几乎所有的程序设计语言都提供了数组类型。实际上,在语言中把数组看成是具有共同名字的同一类型多个变量的集合。需要注意的是,不能对数组进行整体的运算,只能对单个数组元素进行运算。
               数组的顺序存储
               由于数组一般不作插入和删除运算,也就是说,一旦定义了数组,则结构中的数据元素个数和元素之间的关系就不再发生变动,因此数组适合于采用顺序存储结构。
               对于数组,一旦确定了它的维数和各维的长度,便可为它分配存储空间。反之,只要给出一组下标便可求得相应数组元素的存储位置,也就是说,在数据的顺序存储结构中,数据元素的位置是其下标的线性函数。
               二维数组的存储结构可分为以行为主序(按行存储)和以列为主序(按列存储)两种方法,如下图所示。
               
               二维数组的两种存储方式
               设每个数据元素占用L个单元,mn为数组的行数和列数,那么以行为主序优先存储的地址计算公式为:
               Loc(aij)=Loc(a11)+((i-1)×n+(j-1))×L
               同理,以列为主序优先存储的地址计算公式为:
               Loc(aij)=Loc(a11)+((j-l)×m+(i-1))×L
   题号导航      2020年下半年 程序员 上午试卷 综合知识   本试卷我的完整做题情况  
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 /
 
第40题    在手机中做本题