首页 > 软考

网友您好，请在下方输入框内输入要搜索的题目：

请输入或粘贴题目内容搜题

搜题

拍照、语音搜题，请扫码下载APP

题目内容（请给出正确答案）

[主观题]

● 对于二叉查找树（Binary Search Tree），若其左子树非空，则左子树上所有结点的值均小于根结点的

值；若其右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身就是两棵二叉查找树。因此，对任意一棵二叉查找树进行（61）遍历可以得到一个结点元素的递增序列。在具有 n 个结点的二叉查找树上进行查找运算，最坏情况下的算法复杂度为（62）。

（61）

A. 先序

B. 中序

C. 后序

D. 层序

（62）

A. O(n2

B. O(nlog2n)

C. O(log2n)

D. O(n)

答案

查看答案

发布时间：2020-08-30

更多“● 对于二叉查找树（Binary Search Tree），若其左子树非空，则左子树上所有结点的值均小于根结点的”相关的问题

第1题

在某个二叉查找树（即二叉排序树）中进行查找时，效率最差的情形是该二叉查找树是（59) 。A.完全二叉

在某个二叉查找树（即二叉排序树）中进行查找时，效率最差的情形是该二叉查找树是(59) 。

A.完全二叉树

B.平衡二叉树

C.单枝树

D.满二叉树

点击查看答案

第2题

A．查找树B．满二叉树C．平衡树但不是满二叉捌D．B+树

A．查找树

B．满二叉树

C．平衡树但不是满二叉捌

D．B+树

点击查看答案

第3题

用关键字序列10、20、30、40、50构造的二叉排序树（二叉查找树)为（63)。A．B．C．D．

用关键字序列10、20、30、40、50构造的二叉排序树(二叉查找树)为(63)。

用关键字序列10、20、30、40、50构造的二叉排序树（二叉查找树)为（63)。A．B．C．D．用

A．

B．

C．

D．

点击查看答案

第4题

利用逐点插入建立序列（50，72，43，85，75，20，35，45，65，30)对应的二叉查找树后，查找元素35要进行（29)

利用逐点插入建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉查找树后，查找元素35要进行(29)次元素间比较。

A．2

B．3

C．4

D．5

点击查看答案

第5题

结点数目为n的二叉查找树（二叉排序树)的最小高度为（52)、最大高度为（53)。A．nB．C．[log2n]D．[log2（n

结点数目为n的二叉查找树(二叉排序树)的最小高度为(52)、最大高度为(53)。

A．n

B．结点数目为n的二叉查找树(二叉排序树)的最小高度为(52)、最大高度为(53)。A．nB．C．[lo

C．[log2n]

D．[log2(n+1)]

点击查看答案

第6题

从具有n个结点的二叉查找树中查找一个元素时，在最坏情况下进行成功查找的时间复杂度为（51)。A．O（n

从具有n个结点的二叉查找树中查找一个元素时，在最坏情况下进行成功查找的时间复杂度为(51)。

A．O(n)

B．O(1)

C．O(log2n)

D．O(n2)

点击查看答案

第7题

结点数目为n的二叉查找树（二叉排序树）的最小高度为（56）、最大高度为（57）。

结点数目为n的二叉查找树（二叉排序树）的最小高度为（56）、最大高度为（57）。A.AB.BC.CD

A.A

B.B

C.C

D.D

点击查看答案

第8题

以下关于二叉排序树（或二叉查找树、二叉搜索树)的叙述中，正确的是（)A.对二叉排序树进行先序、中序

以下关于二叉排序树(或二叉查找树、二叉搜索树)的叙述中，正确的是()

A.对二叉排序树进行先序、中序和后序遍历，都得到结点关键字的有序序列

B.含有N个结点的二叉排序树高度为【log2n】+1

C.从根到任意二个叶子结点的路径上，结点的关键字呈现有序排列的特点

D.从左到右排列同层次的结点，’其关键字呈现有序排列的特点

点击查看答案

第9题

对于两棵具有相同关键码集合而形状不同的二叉搜索树，按中序遍历它们得到的序列的各元素的顺序是一样的。()

对于两棵具有相同关键码集合而形状不同的二叉搜索树，按中序遍历它们得到的序列的各元素的顺序是一样的。（)

此题为判断题(对，错)。

点击查看答案

第10题

求最优二叉搜索树算法的时间复杂度为O(n²)，下面给出一个求拟最优二叉搜索树的试探算法，

求最优二叉搜索树算法的时间复杂度为O（n²)，下面给出一个求拟最优二叉搜索树的试探算法，

可将算法的时间复杂度降低到O(nlog₂n)，算法的思想是对于关键码序列(key_low，key_low+1，…，key_high)，轮流以key_k为根，k=low，low+1，…，h，求使得|W[low-1][k-1]-W[k][high]|达到最小的k，用key_k作为由该序列构成的拟最优二叉搜索树的根。然后对以keyu为界的左子序列和右子序列，分别施行同样的操作，建立根key_k的左子树和右子树，试编写一个函数，实现上述试探算法。要求该函数的时间复杂度应为O(nlog₂n)。

点击查看答案