算法与数据结构 -凯发k8导航

将键值1，2，3，4，5，6，7，8，9，10的10个元素以某种顺序插入某二叉搜索树后，发现这个树的根是3。问这个树的高度可能为多少？（规定仅有根的树的高度为0） a.2b.3c.4d.5e.6f.7正确答案：3；4；5；6；7

考虑规模为n的二叉搜索树中，put,get,del,in四个方法的时间复杂度数量级。四个方法中，有（）个方法在最差情况下，具有o(n)的时间复杂度 a.1b.2c.3d.4正确答案：4

高度为4的平衡二叉树最少有（）个节点。 a.12b.15c.7d.9正确答案：12

设一个二叉树有p个出度（此处可以理解为子节点的个数）为0的节点，q个出度为1的节点，r个出度为2的节点，问下列叙述何者正确？ a.此树的总节点数为p q rb.叶节点有p个c.根节点有r个d.p=r 1正确答案：此树的总节点数为p q r；叶节点有p个；p=r 1

设x是一个完全二叉树，x共有5个深度为3的节点，并以非嵌套列表的形式给所有节点编号（此部分可参考”608优先队列和二叉堆“）。选出正确的选项。 a.x共有12个节点b.x共有13个节点c.6号节点有子节点12和13d.6号节点有子节点12e.7号节点有1个子节点f.7号节点没有子节点正确答案：x共有12个节点；6号节点有子节点12；7号节点没有子节点

关于树mytree=['a',['b',['d',[],[]],['e',[],[]]],['c',['f',[],[]],[]]]的说法，何者正确？ a.左子树是['b',['d',[],[]],['e',[],[]]]b.左子树的根是'b'c.右子树是['c',['f',[],[]],[]]d.右子树的根是'e'正确答案：左子树是['b',['d',[],[]],['e',[],[]]]；左子树的根是'b'；右子树是['c',['f',[],[]],[]]

四叉树是一种树状结构，常用于图像或空间索引，典型体现为快速加载低清图像或地图，并随着读入数据的量的增加，逐渐提高解析度。四叉树的每个节点，恰有0或4个子节点，且每个子节点的地位也不同（在图像或空间信息处理上，子节点的地位通常表示相对位置）。以下关于非空的四叉树的说法，何者错误？ a.四叉树的节点数量符合4k 1形式，其中k是非负整数b.若某个四叉树有n个节点，则有ceil(n*3/4)个节点为叶节点c.若某个四叉树有n个节点，则有n//4个节点不是叶节点d.若某个四叉树有n个节点，则树的高度有ceil(log（）4(n))层正确答案：若某个四叉树有n个节 …

以下关于空树说法何者正确？ a.是一个树，但不是一个二叉树b.是一个树，也是一个二叉树c.不是一个树，而是一个二叉树d.不是一个树，也不是一个二叉树正确答案：是一个树，也是一个二叉树

此处规定二叉树中，左子节点与右子节点地位不同（即某个父节点只有一个子节点时，也要区分它是左子节点还是右子节点）。定义一个函数c(n)，为按照此方法，构建一个包含n个节点的，符合规则的树的方法数。问c(1),c(2),c(3),c(4)的值。 a.1，1，2，3b.1，1，2，4c.1，2，4，8d.1，2，5，14正确答案：1，2，5，14

设x是一个完全二叉树，x共有33个节点，并以非嵌套列表的形式给所有节点编号1~33（此部分可参考”608优先队列和二叉堆“）。选出错误的选项。 a.树的高度为5b.18号节点的父节点是9号c.23号没有子节点d.整个树的左子树比右子树多1个节点e.23号节点的父节点是11号f.27号节点的父节点是14号正确答案：整个树的左子树比右子树多1个节点；27号节点的父节点是14号

以下哪些排序方式，其最坏情况的时间复杂度o(n^2)的？ a.快速排序b.选择排序c.冒泡排序d.插入排序e.归并排序正确答案：快速排序；选择排序；冒泡排序；插入排序

现在有一个几乎顺序排列的，非常大的列表。问以下哪些算法有可能得到时间复杂度o(n)? a.冒泡排序b.插入排序c.选择排序d.归并排序e.快速排序正确答案：冒泡排序；插入排序；归并排序