《数据结构》习题汇编08第八章查找试题.doc

《《数据结构》习题汇编08第八章查找试题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构课程（本科）第七章试题一、单项选择题1.若搜索每一个元素的概率相等，则在长度为n的顺序表上搜索到表中任一元素的平均搜索长度为（）。A.nB.n+1C.(n-1)/2D.(n+1)/22.对长度为10的顺序表进行搜索，若搜索前面5个元素的概率相同，均为1/8，搜索后面5个元素的概率相同，均为3/40，则搜索到表中任一元素的平均搜索长度为（）。A.5.5B.5C.39/8D.19/43.对长度为3的顺序表进行搜索，若搜索第一个元素的概率为1/2，搜索第二个元素的概率为1/3，搜索第三个元素的概率为1/6，则

2、搜索到表中任一元素的平均搜索长度为（）。A.5/3B.2C.7/3D.4/34.对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度为（）。A.n/2B.(n+1)/2C.(n-1)/2D.n/45.对于长度为n的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为（）的值的向上取整。A.log2(n+1)B.log2nC.n/2D.(n+1)/26.对于长度为n的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为（）的值的向下取整加一。A.log2(n+1

3、)B.log2nC.n/2D.(n+1)/27.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（）的值除以9。A.20B.18C.25D.228.对于长度为18的有序顺序表，若采用折半搜索，则搜索第15个元素的搜索长度为（）。A.3B.4C.5D.69.对具有n个元素的有序顺序表进行折半搜索，则搜索任一元素的时间复杂度为（）。A.O(n)B.O(n2)C.O(1)D.O(log2n)10.在一棵高度为h的具有n个元素的二叉搜索树中，搜索所有元素的搜索长度中最大的为（）。A.nB

4、.log2nC.(h+1)/2D.h+111.从具有n个结点的二叉搜索树中搜索一个元素时，在等概率情况下进行成功搜索的时间复杂度大致为（）。A.O(n)B.O(1)C.O(log2n)D.O(n2)1.从具有n个结点的二叉搜索树中搜索一个元素时，在最坏情况下进行成功搜索的时间复杂度为（）。A.O(n)B.O(1)C.O(log2n)D.O(n2)2.向具有n个结点的二叉搜索树中插入一个元素时，其时间复杂度大致为（）。A.O(1)B.O(log2n)C.O(n)D.O(nlog2n)3.在一棵AVL树（高度平衡的

5、二叉搜索树）中，每个结点的平衡因子的取值范围是（）。A.-1～1B.-2～2C.1～2D.0～14.向一棵AVL树（高度平衡的二叉搜索树）插入元素时，可能引起对最小不平衡子树的调整过程，此调整分为（）种旋转类型。A.2B.3C.4D.55.向一棵AVL树（高度平衡的二叉搜索树）插入元素时，可能引起对最小不平衡子树的左单或右单旋转的调整过程，此时需要修改相关（）个结点指针域的值。A.2B.3C.4D.56.向一棵AVL树（高度平衡的二叉搜索树）插入元素时，可能引起对最小不平衡子树的双向旋转的调整过程，此时需要修改

6、相关（）个结点指针域的值。A.2B.3C.4D.5参考答案：1.D2.C3.A4.B5.A6.B7.C8.A9.D10.D11.C12.A13.B14.A15.C16.A17.C二、填空题1.以顺序搜索方法从长度为n的顺序表或单链表中搜索一个元素时，其时间复杂度为________。2.对长度为n的搜索表进行搜索时，假定搜索第i个元素的概率为pi，搜索长度（即在搜索过程中依次同有关元素比较的总次数）为ci，则在搜索成功情况下的平均搜索长度的计算公式为________。3.假定一个顺序表的长度为40，并假定搜索每个

7、元素的概率都相同，则在搜索成功情况下的平均搜索长度为________。4.以折半搜索方法从长度为n的有序表中搜索一个元素时，时间复杂度为________。5.从有序表(12,18,30,43,56,78,82,95)中折半搜索元素56时，其搜索长度为________。6.假定对长度n=50的有序表进行折半搜索，则对应的判定树中最后一层的结点数为______个。1.从一棵二叉搜索树中搜索一个元素时，若给定值小于根结点的值，则需要向________继续搜索。2.从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的

8、值，则需要向________继续搜索。3.向一棵二叉搜索树中插入一个新元素时，若该新元素的值小于根结点的值，则应把它插入到根结点的________上。4.向一棵二叉搜索树中插入一个新元素时，若该新元素的值大于根结点的值，则应把它插入到根结点的________上。5.向一棵二叉搜索树________一个元素时，若查找到的根结点为空值，则应把该元素结点链接到这个空指针位置上。6.根据n个元