文档介绍：第9章 查找
一、单选题
对一棵二叉搜索树按（）遍历，可得到结点值从小到大的排列序列。
A. 先序 B. 中序 C. 后序 D. 层次
从具有n个结点的二叉搜索树中查找一个元素时，在平均情况下的时间复杂度大致为（）。
A. O(n) B. O(1) C. O(logn) D. O(n2)
从具有n个结点的二叉搜索树中查找一个元素时，在最坏情况下的时间复杂度为（）。
A. O(n) B. O(1) C. O(logn) D. O(n2)
在二叉搜索树中插入一个结点的时间复杂度为（）。
A. O(1) B. O(n) C. O(logn) D. O(n2)
分别以下列序列构造二叉搜索树，与用其它三个序列所构造的结果不同的是（）。
A．（100，80， 90， 60， 120，110，130）
B.（100，120，110，130，80， 60， 90）
C.（100，60， 80， 90， 120，110，130）
D.（100，80， 60， 90， 120，130，110）
在一棵AVL树中，每个结点的平衡因子的取值围是（）。
A. -1~1 B. -2~2 C. 1~2 D. 0~1
根据一组关键字（56，42，50，64，48）依次插入结点生成一棵AVL树，当插入到值为（）的结点时需要进行旋转调整。
A. 42 B. 50 C. 64 D. 48
深度为4的AVL树至少有（）个结点。
A．9 B. 8 C. 7 D. 6
一棵深度为k的AVL树，其每个分支结点的平衡因子均为0，则该平衡二叉树共有（）个结点。
-1-1 -1+1 -1
在AVL树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作（ ） 型调整以使其平衡。
A. LL B. LR C. RL D. RR
二、判断题
二叉搜索树的任意一棵子树中，关键字最小的结点必无左孩子，关键字最大的结点必无右孩子。
二叉搜索树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。
二叉搜索树按照中序遍历将各结点打印出将各结点打印出来，将得到按照由小到大的排列。
若二叉搜索树的根结点没有左儿子，则根结点一定是值最小的结点。
二叉搜索树一定是满二叉树。
从二叉搜索树的根结点一直沿右儿子向下找不一定能找到树中值最大的结点。
二叉搜索树的充要条件是任一结点的值均大于其左孩子的值，小于其右孩子的值。
若二叉搜索树中关键码互不相同，则其中最小元素和最大元素一定是叶子结点。
在任意一棵非空二叉搜索树中，删除某结点后又将其插入，则所得二叉搜索树与原二叉搜索树相同。
当向二叉搜索树中插入一个结点，则该结点一定成为叶子结点。
AVL树是指左右子树的高度差的绝对值不大于1的二叉树。
AVL是一棵二叉树，其树上任一结点的平衡因子的绝对值不大于1。
在