免费智能真题库 > 历年试卷 > 软件设计师 > 2018年下半年 软件设计师 上午试卷 综合知识
  第59题      
  知识点:   二叉排序树   查找   二叉查找树   排序
  关键词:   二叉查找树   二叉检索树   二叉排序树   关键码   检索树   排序        章/节:   计算机软件知识       

 
可以构造出下图所示二叉排序(二叉检索树、二叉查找树)的关键码序列是( )。

 
 
  A.  10 13 17 19 23 27 31 40 65 91
 
  B.  23 40 91 17 19 10 31 65 27 13
 
  C.  23 19 40 27 17 13 10 91 65 31
 
  D.  27 31 40 65 91 13 10 17 23 19
 
 
 

 
  第61题    2016年下半年  
   56%
以下关于二叉排序树(或二叉查找树、二叉搜索树)的叙述中,正确的是(61) 。
  第27题    2022年上半年  
   53%
对长度为n的有序顺序进行折半查找(即二分查找)的过程可用一棵判定树表该判定树的形态符合()的特点。
  第59题    2014年下半年  
   36%
某个二叉查找树(即二叉排序树)中进行查找时,效率最差的情形是该二叉查找树是()。
   知识点讲解    
   · 二叉排序树    · 查找    · 二叉查找树    · 排序
 
       二叉排序树
        二叉排序树又称为二叉查找树,它或者是一棵空树,或者是满足以下性质的二叉树。
        (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节点。
 
       查找
        1)顺序查找
        顺序查找又称线性查找,顺序查找的过程是从线性表的一端开始,依次逐个与表中元素的关键字值进行比较,如果找到其关键字与给定值相等的元素,则查找成功;若表中所有元素的关键字与给定值比较都不成功,则查找失败。
        2)折半查找
        折半查找的过程是先将给定值与有序线性表中间位置上元素的关键字进行比较,若两者相等,则查找成功;若给定值小于该元素的关键字,那么选取中间位置元素关键字值小的那部分元素作为新的查找范围,然后继续进行折半查找;如果给定值大于该元素的关键字,那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围,然后继续进行折半查找,直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。
        3)分块查找
        在分块查找过程中,首先将表分成若干块,每一块中关键字不一定有序,但块之间是有序的。此外,还建立了一个索引表,索引表按关键字有序。分块查找过程需分两步进行:先确定待查记录所在的块;然后在块中顺序查找。
        4)哈希表及其查找
        根据设定的哈希函数H(key)和处理冲突的方法,将一组关键字映射到一个有限的连续地址集上,并以关键字在地址集中的像作为记录在表中的存储位置,这种表称为哈希表,也称散列表。这一过程所得到的存储位置称为散列地址,由此形成的查找方法称为散列查找。
 
       二叉查找树
        二叉查找树又称为二叉排序树,它或者是一棵空树,或者是具有如下性质的二叉树。
        (1)若它的左子树非空,则左子树上所有结点的关键码值均小于根结点的关键码值;
        (2)若它的右子树非空,则右子树上所有结点的关键码值均大于根结点的关键码值;
        (3)左、右子树本身就是两棵二叉查找树。
        一棵二叉查找树如下图(a)所示。下图(b)所示的二叉树不是二叉查找树,因为46比54小,它应该在根结点54的左子树上。
        
        二叉查找树与非二叉查找树
        从二叉查找树的定义可知,对二叉查找树进行中序遍历,可得到一个关键码递增有序的结点序列。
 
       排序
        假设含n个记录的文件内容为{R1R2,…,Rn},其相应的关键字为{k1k2,…,kn}。经过排序确定一种排列{Rj1Rj2,…,Rjn},使得它们的关键字满足如下递增(或递减)关系:kj1≤kj2≤…≤kjn(或kj1kj2≥…≥kjn)。
   题号导航      2018年下半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况  
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 /
 
第59题    在手机中做本题