资源描述：
《大数据结构查找习题及问题详解》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、实用第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.分别以下列序
2、列构造二叉搜索树，与用其它三个序列所构造的结果不同的是（）。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.-1~1B.-2~2C.1~2D.0~17.根据一组关键字（56，42，50，64，48）依次插入结点生成一棵AVL树，当插入到值为（）的结点时需要进行旋转调整。A.42B.
3、50C.64D.488.深度为4的AVL树至少有（）个结点。A．9B.8C.7D.6文档实用1.一棵深度为k的AVL树，其每个分支结点的平衡因子均为0，则该平衡二叉树共有（）个结点。A.2k-1-1B.2k-1+1C.2k-1D.2k2.在AVL树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作（）型调整以使其平衡。A.LLB.LRC.RLD.RR二、判断题1.二叉搜索树的任意一棵子树中，关键字最小的结点必无左孩子，关键字最大的结点必无右孩子。2.二
4、叉搜索树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。3.二叉搜索树按照中序遍历将各结点打印出将各结点打印出来，将得到按照由小到大的排列。4.若二叉搜索树的根结点没有左儿子，则根结点一定是值最小的结点。5.二叉搜索树一定是满二叉树。6.从二叉搜索树的根结点一直沿右儿子向下找不一定能找到树中值最大的结点。7.二叉搜索树的充要条件是任一结点的值均大于其左孩子的值，小于其右孩子的值。8.若二叉搜索树中关键码互不相同，则其中最小元素和最大元素一定是
5、叶子结点。9.在任意一棵非空二叉搜索树中，删除某结点后又将其插入，则所得二叉搜索树与原二叉搜索树相同。10.当向二叉搜索树中插入一个结点，则该结点一定成为叶子结点。11.AVL树是指左右子树的高度差的绝对值不大于1的二叉树。12.AVL是一棵二叉树，其树上任一结点的平衡因子的绝对值不大于1。13.在AVL树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。文档实用三、填空题1.在一棵二叉搜索树上实施遍历后，其关键字序列是一个有序表。2.一个无序序列可以通过构造一棵_______而变成一个有序序列，构
6、造树的过程即为对无序序列进行排序的过程。3.在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定________该结点的值，右子树上所有结点的值一定________该结点。4.从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明_______，若元素的值小于根结点的值，则继续向_______查找，若元素的值大于根结点的值，则继续向________查找。5.向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则接着向根结点的________插入，若元素的值大于根结点的值，则接着向根结点的_
7、_______插入。6.根据n个元素建立一棵二叉搜索树的时间复杂度大致为________。7.二叉树中某一结点左子树的深度减去右子树的深度称为该结点的_______。8.深度为4的平衡二叉树中至少有个结点，至多有个结点。9.在一棵AVL树中，每个结点的左子树高度与右子树高度之差的绝对值不超过________。四、应用题1.一棵二叉搜索树的结构如下图所示，结点的值为1～8，请标出各结点的值。2.若依次输入序列{62,68,30,61,25,14,53,47,90,84}中的元素，生成一棵二叉搜索树。画出生成后的二叉搜
8、索树（画出生成过程）。3.依次读入给定的整数序列{7,16,4,8,20,9,6,18,5}，构造一棵二叉搜索文档实用树,并计算在等概率情况下该二叉搜索树的平均查找长度ASL。（要求给出构造过程）1.从空二叉树开始，严格按照二叉搜索树的插入算法（不进行平衡旋转），逐个插入关键码{18,73,10,5,68,99,27,41,51,32,25}构造出一棵二叉搜
