第1题:
● 对于二叉查找树(Binary Search Tree) ,若其左子树非空,则左子树上所有结点的值均小于根结点的值;若其右子树非空,则右子树上所有结点的值均大于根结点的值;左、右子树本身就是两棵二叉查找树。因此,对任意一棵二叉查找树进行 (61) 遍历可以得到一个结点元素的递增序列。在具有 n 个结点的二叉查找树上进行查找运算,最坏情况下的算法复杂度为 (62) 。
(61)
A. 先序
B. 中序
C. 后序
D. 层序
(62)
A. O(n2
B. O(nlog2n)
C. O(log2n)
D. O(n)
第2题:
A、左子树
B、右子树
C、左右两棵子树
D、根接点
第3题:
第4题:
在具有101个元素的顺序表中查找值为x的元素结点时,平均比较元素的次数为()。
A.50
B.51
C.100
D.101
第5题:
对于二叉查找树(Binary Search Tree),若其左子树非空,则左子树上所有结点的值均小于根结点的值;若其右子树非空,则右子树上所有结点的值均大于根结点的值。左、右子树本身就是两棵二叉查找树。因此,对任意一棵二叉查找树进行(61)遍历可以得到一个结点元素的递增序列。在具有n个结点的二叉查找树上进行查找运算,最坏情况下的算法复杂度为(62)。
A.先序
B.中序
C.后序
D.层序
第6题:
此题为判断题(对,错)。
第7题:
二叉排序树或者是一棵空树,或者是具有如下性质的二叉树:特其左子树非空,则左子树上所有节点的值均小于根节点的值;若其右子树非空,则右子树上所有节点的值均大于根节点的值;其左、右子树本身就是两棵二叉排序树。根据该定义,对一棵非空的二叉排序树进行______遍历,可得到一个节点元素的递增序列。
A.前序(根、左、右)
B.中序(左、根、右)
C.后序(左、右、根)
D.层序(从树根开始,按层次)
A.
B.
C.
D.
第8题:
●二叉排序树或者是一棵空树,或者是具有如下性质的二叉树:若其左子树非空,则左子树上所有结点的值均小于根结点的值;若其右子树非空,则右子树上所有结点的值均大于根结点的值;其左、右子树本身就是两棵二叉排序树。根据该定义,对一棵非空的二叉排序树进行 (42)遍历,可得到一个结点元素的递增序列
(42)
A. 先序(根、左、右)
B. 中序(左、根、右)
C. 后序(左、右、根)
D. 层序(从树根开始,按层次)
第9题:
树形查找
二叉排序树:每个结点的值都大于其左子树任一结点的值而小于其右子树任一结点的值。
查找
function treesrh(k:keytype):pointer;
var q:pointer;
begin
q:=root;
while (q<>nil) and (q^.key<>k) do
if k<q^.key then q:=q^.left
else q:=q^.right;
treesrh:=q;
end;
第10题:
阅读下列说明和流程图,将应填入(n)的语句写在对应栏内。
【流程图说明】
下面的流程(如图1所示)用N-S盒图形式描述了在一棵二叉树排序中查找元素的过程,节点有3个成员:data, left和right。其查找的方法是:首先与树的根节点的元素值进行比较:若相等则找到,返回此结点的地址;若要查找的元素小于根节点的元素值,则指针指向此结点的左子树,继续查找;若要查找的元素大于根节点的元素值,则指针指向此结点的右子树,继续查找。直到指针为空,表示此树中不存在所要查找的元素。
【算法说明】
【流程图】
将上题的排序二叉树中查找元素的过程用递归的方法实现。其中NODE是自定义类型:
typedef struct node {
int data;
struct node * left;
struct node * right;
}NODE;
【算法】
NODE * SearchSortTree(NODE * tree, int e)
{
if(tree!=NULL)
{
if(tree->data<e)
(4); //小于查找左子树
else if(tree->data<e)
(5); //大于查找左子树
else return tree;
}
return tree;
}