免费智能真题库 > 历年试卷 > 软件设计师 > 2018年下半年 软件设计师 上午试卷 综合知识
第59题      2018年下半年 软件设计师 上午试卷 综合知识
所属知识点           关键词   二叉查找树   二叉检索树   二叉排序树   关键码   检索树   排序
考点辞典   二叉排序树      查找   排序

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

 
 
  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
 
 
 

   知识点 更多相关真题:    更多>  
 
  第58题    2014年上半年  
   42%
某二叉树如图所示,若进行顺序存储(即用一维数组元素存储该二叉树中的结点且通过下标反映结点间的关系,例如,对于下标为i的结点,其左孩子的下标为2i、右孩子的下标为2i+1),则该数组的大小至..
  第51题    2019年下半年  
   59%
某树共有n个结点,其中所有分支结点的度为k(即每个非叶子结点的子树数目),则该树中叶子结点的个数为( )。
  第64题    2013年上半年  
   28%
一个高度为h的满二叉树的结点总数为2h-1,从根结点开始,自上而下、同层次结点从左至右,对结点按照顺序依次编号,即根结点编号为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。
未完......点击标题查看......
1)定义
树型结构是一类重要的非线性数据结构,其中以树和二叉树最为常用。
树是由一个或多个节点组成的有限集T,它满足以下两个条件:有一个特定的节点称为根节点;其余的节点分成m个互不相交的有限集T1, T2, …, Tm,其中每个集又都是一棵树,称T1, T2, …, Tm为根节点的子树。
可见树的定义是递归的,即一棵树由子树构成,子树又由更小的子树构成。
2)相关概念
.一个节点的子树数目称为该节点的度。
.树中各节点的度的最大值称为树的度。
.树中节点的最大层次称为树的深度。
若将树中节点的各子树看成是从左到右具有次序的,即不能交换,则称该树为有序树,否则称为无序树。
未完......点击标题查看......
查找
1)顺序查找
顺序查找又称线性查找,顺序查找的过程是从线性表的一端开始,依次逐个与表中元素的关键字值进行比较,如果找到其关键字与给定值相等的元素,则查找成功;若表中所有元素的关键字与给定值比较都不成功,则查找失败。
2)折半查找
折半查找的过程是先将给定值与有序线性表中间位置上元素的关键字进行比较,若两者相等,则查找成功;若给定值小于该元素的关键字,那么选取中间位置元素关键字值小的那部分元素作为新的查找范围,然后继续进行折半查找;如果给定值大于该元素的关键字,那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围,然后继续进行折半查找,直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。
3)分块查找
在分块查找过程中,首先将表分成若干块,每一块中关键字不一定有序,但块之间是有序的。此外,还建立了一个索引表,索引表按关键字有序。分块查找过程需分两步进行:先确定待查记录所在的块;然后在块中顺序查找。
4)哈希表及其查找
根据设定的哈希函数H(key)和处理冲突的方法,将一组关键字映射到一个有限的连续地址集上,并以关键字在地址集中的像作为记录在表中的存储位置,这种表称为哈希表,也称散列表。这一过程所得到的存储位置称为散列地址,由此形成的查找方法称为散列查找。
未完......点击标题查看......
排序
1)简单排序
简单排序包括直接插入排序、冒泡排序、简单选择排序等。
2)希尔排序
希尔排序的基本思想是:先将整个待排记录序列分割成若干序列,然后分别进行直接插入排序,待整个序列中的记录基本有序时,再对全体记录进行一次直接插入排序。
3)快速排序
快速排序是对冒泡排序的一种改进。先通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,然后分别对这两部分记录继续进行排序,以达到整个序列有序。
4)堆排序
堆排序的基本思想(小根堆)是:对一组待排序记录的关键字,首先把它们按堆的定义排成一个堆序列,从而输出堆顶的最小关键字;然后将剩余的关键字再调整成新堆,便得到次小的关键字,如此反复进行,直到全部关键字排成有序序列。
5)归并排序
未完......点击标题查看......

 题号导航      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题