免费智能真题库 > 历年试卷 > 信息系统管理工程师 > 2019年上半年 信息系统管理工程师 上午试卷 综合知识
  第10题      
  知识点:   树的定义   数据结构
  关键词:   数据结构   一对多   数据        章/节:   数据结构与算法基本概念       

 
数据结构中,树描述了集合中元素之间的一对多逻辑关系,即( )。
 
 
  A.  线性关系
 
  B.  层次关系
 
  C.  网状关系
 
  D.  继承关系
 
 
 

 
  第6题    2013年上半年  
   31%
对于一棵非空二叉树,若先访问根节点的每一棵子树,然后再访问根节点的方式通常称为(6) 。
  第11题    2020年下半年  
   31%
树是一种数据结构,它是由n (n≥0)个有限结点组成一个具有层次关系的集合。下面叙述中,(11)不符合树的特点。
  第10题    2018年上半年  
   40%
假设某树有n个结点,则其中连接结点的分支数目为( ) 。
   知识点讲解    
   · 树的定义    · 数据结构
 
       树的定义
        树(tree)是n(n≥0)个结点的有限集。n=0的树称为空树;当n≠0时,树中的结点应该满足以下两个条件:
        (1)有且仅有一个特定的结点称之为根。
        (2)其余结点分成m (m≥0)个互不相交的有限集合T1,T2,…,Tm,其中每一个集合又都是一棵树,称T1,T2,…,Tm为根结点的子树。
        以上定义是一个递归定义,它反映了树的固有特性,因为一棵树是由根和它的子树构成,而子树又是由子树的根和更小的子树构成。如下图所示的树中,A是根结点,其余结点分成三个互不相交的子集:S1={B,E,F}, S2={C},S3={D, G,H,I,J,K},这三个集合分别构成了A的三棵子树;在S3构成的子树中,D是根结点,D又具有三棵子树,这三棵子树的根结点分别是G,H和I;对于结点G和I,它们的子树均为空。
        
        树
        图中树的表示类似于自然界中一棵倒长的树,“树型结构”由此得名,这种表示方法比较形象、直观,因而容易为人们所接受,是树的一种最常用的表示方法。树型结构除以上表示方法外,还有括号表示法、凹入表示法和嵌套集合表示形式。下图给出了上图中树的这三种表示形式。
        
        树的表示
        在下图的树中,采用线段连接两个相关联的结点,如A和B,D和H等。其中A和D是上端结点,B和H是下端结点。称A、D分别是B、H的双亲(或父母或前件),B和H分别为A和D的子女(或孩子或后件)。由于E和F的双亲为同一结点,称E和F互为兄弟。在任何一棵树中,除根结点外,其他任何一个结点有且仅有一个双亲,有0个或多个子女,且它的子女恰巧为其子树的根结点。将一结点拥有的子女数称为该结点的度,树中所有结点度的最大值称为树的度。称树中连接两个结点的线段为树枝。在树中,若从结点Ki开始沿着树枝自上而下能到达结点Kj,则称从Ki到Kj存在一条路径,路径的长度等于所经过的树枝的条数。在下图中,从结点A到结点J存在一条路径,路径的长度为3;从D到K也存在一条路径,路径的长度为2。将从树根到某一结点Ki的路径中Ki前所经过的所有结点称为Ki的祖先;反之,以某结点Ki为根的子树中的任何一个结点都称为Ki的子孙。下图中,A、D、H均为J和K的祖先,而G、H、I、J和K均为D的子孙。
        树中结点的层次:从树根开始定义,根结点为第一层,根的子女结点构成第二层,依次类推,若某结点Kj位于第i层,则其子女就位于第i+1层。称树中结点的最大层次数为树的深度或高度。下图中,A结点位于第一层,B、C、D位于第2层,E、F、G、H和I位于第三层等,整棵树的高度为4。
        
        树
        如果树中任意结点的子树均看成是从左到右有次序的,不能随意交换,则称该树是有序树;否则称之为无序树。如下图所示的两棵树,若看成是有序树,它们是不等价的;若看成是无序树,两者相等。
        
        树
        由m(m≥0)棵互不相交的树构成的集合称为森林。森林和树的概念十分相近,每个结点的子树的集合即为一个森林;而在森林中的每棵树之上加一个共同的根,森林就成为了一棵树。
        二叉树(Binary Tree)是另一种树型结构,它的特点是每个结点至多只有两棵子树,在二叉树中不存在度大于2的结点,并且二叉树的子树有左右之分,它的次序是不能任意颠倒的。
 
       数据结构
        根据数据元素之间关系的不同特性,通常有下列4类基本的逻辑结构,即集合结构、线性结构、树形结构、图形结构。
        1)线性结构
        线性表是最常用且最简单的一种数据结构。线性表中除第一个元素外,每个元素均只有一个直接前驱;除最后一个元素外,每个元素都只有一个直接后继。
        栈是限定仅在表尾进行插入或删除操作的线性表,是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。
        队列是一种先进先出(FIFO)的线性表,它只允许在表的一端进行插入,而在另一端删除元素。
        2)树
        树是nn≥0)个互不相交的有限集,当n=0时称为空树。在一棵非空树中,有且仅有一个节点称为根节点;当n>1时,其余的节点可分为若干个不相交的集合,其中每一个集合本身又是一棵树,这些集合称为根节点的子树。
        3)图
        图是由两个集合VE组成的二元组,记为G=(V, E),其中V是顶点的非空有限集合,E是图中边的有限集合。
   题号导航      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题    在手机中做本题