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

 
设有关键码序列(10, 40, 30, 20),根据该序列构建的二叉排序是(41)。
 
 
  A. 
 
  B. 
 
  C. 
 
  D. 
 
 
 

 
  第43题    2019年上半年  
   54%
已知有序数组a的前10000个元素是随机整数,现需查找某个整数是否在该数组中。以下方法中,( )的查找效率最高。
  第41题    2013年下半年  
   50%
在一棵非空的二叉排序树(二叉查找树)中,进行(41)遍历运算并输出所访问结点的关键码后,可得到一个有序序列。
  第39题    2019年下半年  
   45%
在(39)中,要按照确定的计算关系来找到给定关键码的存储位置。
   知识点讲解    
   · 动态查找表    · 二叉排序树    · 排序
 
       动态查找表
        若在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已存在的某个数据元素,则称此类查找表为动态查找表。动态查找表的特点是表结构是动态生成的。
        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)。
   题号导航      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题    在手机中做本题