免费智能真题库 > 历年试卷 > 程序员 > 2015年下半年 程序员 上午试卷 综合知识
  第41题      
  知识点:   动态查找表   二叉排序树   排序   树的定义
  关键词:   二叉排序树   排序        章/节:   常用算法       

 
(41) 不符合二叉排序的定义。
 
 
  A. 
 
  B. 
 
  C. 
 
  D. 
 
 
 

 
  第41题    2019年上半年  
   33%
对于给定的关键字序列{47,34,13,12,52,38,33,27, 5},若用链地址法(拉链法)解决冲突来构造哈希表,且哈希函数为H(ke..
  第41题    2018年下半年  
   62%
对于关键字序列(10,34,37,51,14,25,56,22,3),用线性探查法解决冲突构造哈希表,哈希函数为H(key)=key%11,关键字25存入的..
  第42题    2013年下半年  
   47%
若关键码序列(23,35,14,49,8,12,30,7)采用散列法进行存储和查找。设散列函数为H(Key)=Key%11,采用线性探查法(顺序地探查可用存储..
   知识点讲解    
   · 动态查找表    · 二叉排序树    · 排序    · 树的定义
 
       动态查找表
        若在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已存在的某个数据元素,则称此类查找表为动态查找表。动态查找表的特点是表结构是动态生成的。
        1)二叉排序树的定义
        二叉排序树又称二叉查找树,它或者是一棵空树,或者是具有以下性质的二叉树。
        .若它的左子树非空,则左子树上所有节点的值均小于根节点的值。
        .若它的右子树非空,则右子树上所有节点的值均大于或等于根节点的值。
        .左、右子树本身就是两棵二叉排序树。
        2)二叉排序树的查找过程
        若二叉树为非空,将给定值与根节点的关键字值进行比较,若相等,则查找成功;若不等,则当根节点的关键字值大于给定值时,到根的左子树中进行查找;否则到根的右子树进行查找。
        3)二叉排序树中插入节点的操作
        二叉排序树是通过依次输入数据元素并把它们插到二叉树的适当位置上构造起来的,具体过程如下:读入一个元素,建立一个新节点。若二叉排序树非空,则将新节点的值与根节点的值进行比较,如果小于根节点的值,则插入左子树中,否则插入右子树中;若二叉树为空,则新节点作为二叉排序树的根节点。
        4)二叉排序树中删除节点的操作
        在二叉排序树中删除一个节点,不能把以该节点为根的子树都删除,只能删除这个节点并仍旧保持二叉排序树的特性。
 
       二叉排序树
        二叉排序树又称为二叉查找树,它或者是一棵空树,或者是满足以下性质的二叉树。
        (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节点。
 
       排序
        假设含n个记录的文件内容为{R1R2,…,Rn},其相应的关键字为{k1k2,…,kn}。经过排序确定一种排列{Rj1Rj2,…,Rjn},使得它们的关键字满足如下递增(或递减)关系:kj1≤kj2≤…≤kjn(或kj1kj2≥…≥kjn)。
 
       树的定义
        树(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的结点,并且二叉树的子树有左右之分,它的次序是不能任意颠倒的。
   题号导航      2015年下半年 程序员 上午试卷 综合知识   本试卷我的完整做题情况  
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 /
 
第41题    在手机中做本题