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