免费智能真题库 > 历年试卷 > 程序员 > 2019年上半年 程序员 上午试卷 综合知识
  第40题      
  知识点:   动态查找表   树的存储结构及遍历操作   二叉排序树   二叉树   排序
  关键词:   遍历   二叉排序树   二叉树   排序        章/节:   常用数据结构   常用算法       

 
对一棵二叉排序进行( )遍历,可得到该二叉树中结点关键字的有序序列。
 
 
  A.  先序
 
  B.  中序
 
  C.  后序
 
  D.  层序
 
 
 

 
  第39题    2012年上半年  
   41%
已知某二叉树的先序遍历序列为ABCD,中序遍历序列为BADC,则该二叉树的后序遍历序列为(39)。
  第40题    2011年上半年  
   31%
当二叉树的结构形如(40)时,其后序遍历序列和中序遍历序列相同。
  第42题    2009年下半年  
   63%
对于n个元素的关键字序列K1K2,…,Kn,若有
 
  第41题    2013年下半年  
   50%
在一棵非空的二叉排序树(二叉查找树)中,进行(41)遍历运算并输出所访问结点的关键码后,可得到一个有序序列。
  第41题    2011年上半年  
   49%
对长度为n的有序表进行二分(折半)查找时,无论查找指定的一个元素是否成功, 最多只与表中的(41)个元素进行比较即可。
  第42题    2018年上半年  
   35%
若关键码序列(47,61,55,39,10,26,90,82)采用散列法进行存储和查找。设散列函数为H(Key)=Key mod 11(mod表示整除取余运..
   知识点讲解    
   · 动态查找表    · 树的存储结构及遍历操作    · 二叉排序树    · 二叉树    · 排序
 
       动态查找表
        若在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已存在的某个数据元素,则称此类查找表为动态查找表。动态查找表的特点是表结构是动态生成的。
        1)二叉排序树的定义
        二叉排序树又称二叉查找树,它或者是一棵空树,或者是具有以下性质的二叉树。
        .若它的左子树非空,则左子树上所有节点的值均小于根节点的值。
        .若它的右子树非空,则右子树上所有节点的值均大于或等于根节点的值。
        .左、右子树本身就是两棵二叉排序树。
        2)二叉排序树的查找过程
        若二叉树为非空,将给定值与根节点的关键字值进行比较,若相等,则查找成功;若不等,则当根节点的关键字值大于给定值时,到根的左子树中进行查找;否则到根的右子树进行查找。
        3)二叉排序树中插入节点的操作
        二叉排序树是通过依次输入数据元素并把它们插到二叉树的适当位置上构造起来的,具体过程如下:读入一个元素,建立一个新节点。若二叉排序树非空,则将新节点的值与根节点的值进行比较,如果小于根节点的值,则插入左子树中,否则插入右子树中;若二叉树为空,则新节点作为二叉排序树的根节点。
        4)二叉排序树中删除节点的操作
        在二叉排序树中删除一个节点,不能把以该节点为根的子树都删除,只能删除这个节点并仍旧保持二叉排序树的特性。
 
       树的存储结构及遍历操作
        1)树的存储结构
        树是非线性的结构,存储树时,须把树中节点之间存在的关系反映在树的存储结构中。树有很多存储结构,这里仅介绍最常用的两种。
        (1)树的标准存储结构。
        树的标准存储结构由节点的数据和指向子节点的指针数组组成;对于度为M的树,其指针数组中的元素个数为M
        (2)树的带逆存储结构。
        由于树的带逆存储结构需要一个从子节点指向父节点的指针,因而该结构在标准存储结构的基础上,需要在树的节点中增加一个指向其双亲节点位置的指针。
        2)树的遍历
        树的遍历是树的基本操作之一,也是最重要的操作之一。树的遍历含义是指:按照某种要求依次访问树中的每个节点,每个节点均被访问一次且仅被访问一次。常用的树的遍历方法可分为前序遍历、后序遍历和中序遍历。
        (1)树的前序遍历。
        首先访问根节点,然后从左到右前序遍历根节点的各棵子树。树的前序遍历递归算法如下:
        
        若利用栈来记录当前未访问完的子树的根节点指针,则前序遍历的非递归算法如下:
        
        (2)树的后序遍历。
        树的后序遍历的基本思想是:先依次遍历每棵子树,然后访问根节点,与后序遍历二叉树相同。树的后序遍历递归算法如下:
        
        (3)树的中序遍历。
        树的中序遍历的基本思想是:先左子树,遍历根节点,然后依次遍历其他各棵子树,类似二叉树的中序遍历。树的中序遍历递归算法如下:
        
 
       二叉排序树
        二叉排序树又称为二叉查找树,它或者是一棵空树,或者是满足以下性质的二叉树。
        (1)若它的左子树非空,则左子树上所有节点的值均小于根节点的值。
        (2)若它的右子树非空,则右子树上所有节点的值均大于根节点的值。
        (3)左、右子树本身就是两棵二叉排序树。
        二叉排序树的查找过程是:若二叉排序树非空,则将给定值与根节点的关键字值相比较,若相等,则查找成功;若不等,则当根节点的关键字值大于给定值时,到根的左子树中进行查找;否则到根的右子树中进行查找。若找到,则查找过程是走了一条从树根到所找到节点的路径;否则查找过程终止于一棵空树。
        二叉排序树中插入节点的操作:每读入一个元素,建立一个新节点,若二叉树非空,则将新节点的值与根节点的值相比较,如果小于根节点的值,则插入到左子树中,否则插入到右子树中;若二叉排序树为空,则新节点作为二叉排序树的根节点。
        二叉排序树中删除节点的操作:在二叉树中删除一个节点,不能把以该节点为根的子树都删除,只能删除这个节点并仍旧保持二叉排序树的特性,也就是说,删除二叉排序树上一个节点相当于删除有序数列中的一个元素。假设二叉排序树上的被删除节点为*pp指针指向被删除节点),*f为其双亲节点,则删除节点*p的过程可分为以下3种情况。
        ①若*p节点为叶子节点,即p→lchild及p→rchild均为空,则由于删去叶子节点后不破坏整棵树的结构,因此只需修改*p节点的双亲节点*f的相应指针即可,即f→lchild(或f→rchild)=NULL。
        ②若*p节点只有左子树或者只有右子树,此时只要将*p的左子树或右子树接成其双亲节点*f左子树或右子树,即令f→lchild(或f→rchild)=p→lchild,或f→lchild(或f→rchild)=p→rchild。
        ③若*p节点的左、右子树均不空,则不能像上面那样简单处理,删除*p节点时应将*p的左子树、右子树连接到适当的位置,并保持二叉排序树的特性。可采用以下两种方法进行处理:一是令*p的左子树为*f的左(或右)子树,而将*p的右子树下接到*p的中序遍历的直接前驱节点*s的右孩子指针上;二是用*p的中序直接前驱(或后继)节点*s代替*p节点,然后删除*s节点。
 
       二叉树
               二叉树的定义
               二叉树(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个记录的文件内容为{R1R2,…,Rn},其相应的关键字为{k1k2,…,kn}。经过排序确定一种排列{Rj1Rj2,…,Rjn},使得它们的关键字满足如下递增(或递减)关系:kj1≤kj2≤…≤kjn(或kj1kj2≥…≥kjn)。
   题号导航      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 /
 
第40题    在手机中做本题