一个无序序列可以通过构造一棵()树而变成一个有序序列,构造树的过程即为对无序序列进行排序的过程。

题目
填空题
一个无序序列可以通过构造一棵()树而变成一个有序序列,构造树的过程即为对无序序列进行排序的过程。
参考答案和解析
正确答案: 二叉排序树
解析: 暂无解析
如果没有搜索结果或未解决您的问题,请直接 联系老师 获取答案。
相似问题和答案

第1题:

已知一棵二叉树的先序遍历序列和中序遍历序列可以唯一地构造出该二叉树。()

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


参考答案:正确

第2题:

将一个无序序列中的元素依次插入到一棵(60),并进行中序遍历,可得到一个有序序列。

A.完全二叉树

B.最小生成树

C.二叉排序树

D.最优二叉树


正确答案:C
解析:本题考查数据结构基础知识。
  一个连通图的生成树是一个极小连通子图,它包含图中的全部顶点,但只有构成一棵树的n-1条边。把生成树各边的权值总和称为生成树的权,把权值最小的生成树称为最小生成树。
  哈夫曼树又称最优二叉树,是一类带权路径长度最短的树。若深度为k的二叉树有 2k-1个结点,则称其为满二叉树。可以对满二叉树中的结点进行连续编号:约定编号从根结点起,自上而下、自左至右依次进行。深度为k、有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称之为完全二叉树。
  二叉排序树又称二叉查找树,它或者是一棵空树,或者是具有如下性质的二叉树。
  .若它的左子树非空,则左子树上所有结点的值均小于根结点的值。
  .若它的右子树非空,则右子树上所有结点的值均大于根结点的值。
  .左、右子树本身就是两棵二叉排序树。
  显然,将一个无序序列中的元素依次插入到一棵二叉排序树中并进行中序遍历,可得到一个有序序列。

第3题:

● 关于二叉排序树的说法,错误的是 (27) 。

(27)

A. 对二叉排序树进行中序遍历,必定得到结点关键字的有序序列

B. 依据关键字无序的序列建立二叉排序树,也可能构造出单支树

C. 若构造二叉排序树时进行平衡化处理,则根结点的左子树结点数与右子树结点数的差值一定不超过1

D. 若构造二叉排序树时进行平衡化处理,则根结点的左子树高度与右子树高度的差值一定不超过1


正确答案:C

 

第4题:

设有查找表{5,14,2,6,18,7,4,16,3},依次取表中数据,构造一棵二叉排序树。并说明如何通过序列的二叉排序树得到相应序列的排序结果,对上述二叉排序给出中序遍历的结果。
(1)

(2)中序遍历
中序2,3,4,5,6,7,14,16,18

第5题:

中序遍历二叉排序树可以得到一个有序的序列。()


答案:对
解析:
二叉排序树的左子树一定小于根节点,右子树一定大于根节点,中序遍历的顺序是首先中序遍历左子树,然后访问根节点,最后中序遍历右子树,所以中序遍历二叉排序树可以得到一个有序序列。

第6题:

在一棵二叉排序树中,按【 】遍历得到的节点序列是有序序列。


正确答案:中序
中序 解析:二叉排序树的特点是左子树各节点的值小于树根节点,右子树各节点的值大于等于树根节点的值。中序遍历是“左子树—树根节点—右子树”,因此要得到有序节点序列,应进行中序遍历。

第7题:

● 将一个无序序列中的元素依次插入到一棵 (60) ,并进行中序遍历,可得到一个有序序列。

(60)

A. 完全二叉树

B. 最小生成树

C. 二叉排序树

D. 最优二叉树


正确答案:C

第8题:

● 已知一个二叉树的先序遍历序列为①、②、③、④、⑤,中序遍历序列为②、①、④、③、⑤,则该二叉树的后序遍历序列为 (57) 。对于任意一棵二叉树,叙述错误的是 (58) 。

(57)A. ②、③、①、⑤、④

B. ①、②、③、④、⑤

C. ②、④、⑤、③、①

D. ④、⑤、③、②、①

(58)A. 由其后序遍历序列和中序遍历序列可以构造该二叉树的先序遍历序列

B. 由其先序遍历序列和后序遍历序列可以构造该二叉树的中序遍历序列

C. 由其层序遍历序列和中序遍历序列可以构造该二叉树的先序遍历序列

D. 由其层序遍历序列和中序遍历序列不能构造该二叉树的后序遍历序列


正确答案:C,B
试题(57)、(58)分析
  本题考查数据结构基础知识。
  遍历运算是二叉树的基本运算,主要有先序、中序、后序和层序遍历。
  先序遍历的基本方法:对于非空二叉树,先访问根结点,然后先序遍历根的左子树,最后先序遍历根的右子树。因此,若已知某二叉树的先序遍历序列,则可直接得到其树根结点。
  中序遍历的基本方法:对于非空二叉树,先中序遍历根的左子树,然后访问根结点,最后中序遍历根的右子树。因此,若已知某二叉树的根结点,则一可根据中序遍历序列将该二叉树左右子树上的结点划分开。
  后序遍历的基本方法:对于非空二叉树,首先后序遍历根的左子树,接着后序遍历根的右子树,最后访问根结点。因此,若已知某二叉树的后序遍历序列,则可直接得到其树根结点。
  题中给出的先序遍历序列为①、②、③、④、⑤,可知树根结点是①,据此再结合中序遍历序列②、①、④、③、⑤,可知②是根结点①左子树上的结点,由于是左子树上唯一的一个结点,因此②是根结点①的左孩子。对于右子树上的结点④、③、⑤,因右子树的先序遍历序列为③、④、⑤,因此③是根结点①的右孩子。依此类推,可知④是结点③的左孩子,⑤是结点③的右孩子。该二叉树如下图所示。

 
  从二叉树的遍历过程可知,从先序遍历序列和后序遍历序列中无法将左子树和右子树上的结点区分开,因此,由某棵二叉树的先序遍历序列和后序遍历序列不能构造出该二叉树的中序遍历序列。
  层序遍历二叉树的方法:设二叉树的根结点所在层数为1,则层序遍历二叉树的操作定义为从树的根结点出发,首先访问第一层的结点(根结点),然后从左到右依次访问第二层上的结点,接着是第三层上的结点,依此类推,自上而下、自左至右逐层访问树中各层上的结点。

 

第9题:

设有一个整数序列d{40,28,6,72,100,3,54}依次取出序列中的数,构造一棵二叉排序树。并对上述二叉排序树,在等概率条件下,求成功查找的平均查找长度。
(1)

(2)ASL=(1×1+2×2+3×3+4)/7=18/7

第10题:

对二叉排序树遍历的结果是一个有序序列。


正确答案:正确