早教吧考试题库频道 --> 计算机类考试 -->软考中级 -->
A.O(n)B.O(n2)C.O(log2n)D.O(nlog2n)
题目
A.O(n)
B.O(n2)
C.O(log2n)
D.O(nlog2n)
参考答案
正确答案:A
解析:中序遍历二叉树的过程为:若二叉树非空,则先中序遍历左子树,然后访问根结点,最后中序遍历右子树。根据二叉查找树的定义,显然,对二叉查找树进行中序遍历,得到结点元素的递增序列。在二叉查找树上进行查找的过程为:若二叉查找树非空,将给定值与根结点的关键字值相比较,若相等,则查找成功;若不等,则当根结点的关键字值大于给定值时,到根的左子树中进行查找。否则到根的右子树中进行查找。若找到,则查找过程是走了一条从树根到所找到结点的路径;否则,查找过程终止于一棵空树。因此,在具有n个结点的二叉查找树上进行查找的算法复杂度与树的高度同阶,即最坏情况下的算法复杂度为O(n)。
解析:中序遍历二叉树的过程为:若二叉树非空,则先中序遍历左子树,然后访问根结点,最后中序遍历右子树。根据二叉查找树的定义,显然,对二叉查找树进行中序遍历,得到结点元素的递增序列。在二叉查找树上进行查找的过程为:若二叉查找树非空,将给定值与根结点的关键字值相比较,若相等,则查找成功;若不等,则当根结点的关键字值大于给定值时,到根的左子树中进行查找。否则到根的右子树中进行查找。若找到,则查找过程是走了一条从树根到所找到结点的路径;否则,查找过程终止于一棵空树。因此,在具有n个结点的二叉查找树上进行查找的算法复杂度与树的高度同阶,即最坏情况下的算法复杂度为O(n)。
看了A.O(n)B.O(n2)C....的网友还看了以下:
20.下列两种气体的分子数一定相等的是 ( )A.质量相等、密度不等的N2和C2H4 B.等体积等 其他 2020-05-16 …
对于n元素的向量,将其建立为一个有序单链表的时间复杂度为()。A.O(1)B.O(n)C.O(n2) 计算机类考试 2020-05-24 …
(2014•安徽模拟)如图所示,甲池的总反应式为:N2H4+O2═N2+2H2O下列关于该电池工作 化学 2020-06-23 …
已知△ABC三角形的三边分别为a,b,c且a=m2-n2,b=2mn,c=m2+n2(m>n,m, 数学 2020-07-16 …
数据结构问题!冒泡排序!为什么不选C呢?.在对n个元素进行冒泡排序的过程中,最好情况下的时间复杂度 其他 2020-07-23 …
初二数学.勾股定理那章书上的一题设△ABC的3条边长分别是a,b,c,且a=n2-1,b=2n,c 数学 2020-07-26 …
如图所示,A、B两齿轮的齿数分别为z1、z2,各自固定在过O1、O2的转轴上.其中过O1的轴与电动机 物理 2020-10-31 …
下列何者最可能具有共价网状固体的结构?(A)SO2(B)SiO2(C)P4O10(D)B2O3下列各 化学 2020-12-14 …
函数f(x)的定义域为D,若满足如下两条件:①f(x)在D内是单调函数;②存在[m2,n2]⊆D,使 其他 2021-01-04 …
试判断如下以a、b、c为边长的三角形,其中不是直角三角形的是()A.c的关系满足a2-b2=c2B. 其他 2021-01-22 …