第９章 查找一、单选题1.对一棵二叉搜索树按（）遍历,可得到结点值从小到大得排列序列。A、 先序 ﻩB、 中序ﻩC、 后序ﻩD、 层次2.从具有 n 个结点得二叉搜索树中查找一个元素时,在平均情况下得时间复杂度大致为(）。A、 O（n) ﻩB、 O（1） ﻩC、 O(lo ｇ n) ﻩD、 Ｏ（ｎ 2）3.从具有 n 个结点得二叉搜索树中查找一个元素时，在最坏情况下得时间复杂度为(）.A、 O（ｎ) ﻩB、 Ｏ(1) ﻩC、 O（log ｎ) ﻩﻩD、 O（n ２)4.在二叉搜索树中插入一个结点得时间复杂度为(）。A、 O（1）ﻩﻩﻩ B、 O（ｎ)ﻩC、 O(logn)ﻩﻩ D、 O（n ２)5.分别以下列序列构造二叉搜索树,与用其它三个序列所构造得结果不同得就是()。Ａ。（1 ００，80， 90， 6 ０， １ 20,１１ 0，130） B、(10 ０，120,110,130，80， 6 ０, 90）C、(１ 0 ０,60, 8 ０, 9 ０, 120，１１ 0,1 ３ 0)Ｄ、（10 ０，８ 0， ６ 0， 90， １ 20，１３ 0，110）6.在一棵 AV Ｌ树中，每个结点得平衡因子得取值范围就是(）。A、 —1~１ B、 —2～２ Ｃ、 1～2 ﻩD、 ０~17.根据一组关键字（56,42，５ 0,64，４８)依次插入结点生成一棵Ａ VL 树,当插入到值为(）得结点时需要进行旋转调整。A、 4 ２ﻩﻩB、 ５ 0ﻩﻩC、 ６ 4ﻩﻩD、 488.深度为４得Ａ VL 树至少有（)个结点。A。9B、 8ﻩﻩC、 7ﻩ ﻩD、 69.一棵深度为 k 得 AVL 树，其每个分支结点得平衡因子均为０,则该平衡二叉树共有（)个结点。 A、2k—1—１ﻩ ﻩB、2k-1+1 ﻩ C、2k－1 ﻩD、２ k 10. 在 AVL 树中插入一个结点后造成了不平衡,设最低得不平衡结点为 A，并已知 A 得左孩子得平衡因子为 0,右孩子得平衡因子为 1，则应作( ） 型调整以使其平衡。A、 LL B、 Ｌ R Ｃ、 RL D、 RR二、推断题1.二叉搜索树得任意一棵子树中，关键字最小得结点必无左孩子，关键字最大得结点必无右孩子。2.二叉搜索树中每个结点得关键字值大于其左非空子树(若存在得话)所有结点得关键字值，且小于其右非空子树(若存在得话）所有结点得关键字值。3.二叉搜索树根据中序遍历将各结点打印出将各结点打印出来，将得到根据由小到大得排列。4.若二叉搜索树得根结点没有左儿子,则根结点一定就是值最小得结点.5.二叉搜索树一定就是满二叉树。6.从二叉搜索树得根结点一直沿右儿子向下找不一定能找到树中值最大得结点。7.二叉搜索树得充要...
