数据结构练习第八章 查找

《数据结构练习第八章 查找》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构练习第八章查找1.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为()A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，32．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。A.O(1)B.O(log2n)C.O(n)D.O(n2)3．在二叉排序树中插入一个结点的时间复杂度为（）。A.O(1)B.O(n)C.O(log2n)D.O(n2)4．设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（）。A.log2n+1B.

2、log2n-1C.log2nD.log2(n+1)5．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。A.25B.10C.7D.16．顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。A.O(n)B.O(n2)C.O(n1/2)D.O(1og2n)7．设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（）。A.O(n)B.O(n2)C.O(nlog2n)D.O(1og2n)8．（）二叉排序树可以得到一个从小到大的有序序列。A.先序遍历B.中序遍历C.后序遍历D.层次遍历9．设一组初始记录关键字序列为(13，1

3、8，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（）。A.1B.2C.3D.410．设某散列表的长度为100，散列函数H(k)=k%P，则P通常情况下最好选择（）。A.99B.97C.91D.9311．在二叉排序树中插入一个关键字值的平均时间复杂度为（）。A.O(n)B.O(1og2n)C.O(nlog2n)D.O(n2)12．设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为()。A.A[1]，A[2]，A[3]，A[4]B.A[1]，A[14]，A

4、[7]，A[4]C.A[7]，A[3]，A[5]，A[4]D.A[7]，A[5]，A[3]，A[4]13．设散列表中有m个存储单元，散列函数H(key)=key%p，则p最好选择（）。A.小于等于m的最大奇数B.小于等于m的最大素数C.小于等于m的最大偶数D.小于等于m的最大合数14．设顺序表的长度为n，则顺序查找的平均比较次数为（）。A.nB.n/2C.(n+1)/2D.(n-1)/215．设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（）次比较。A.1B.2C.3D.45116．设顺序线性表的长度

5、为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（）。A.6B.11C.5D.6.517．设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（）。A.4B.5C.6D.718．二叉排序树中左子树上所有结点的值均（）根结点的值。A.C.=D.!=19．设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做（）次线性探测。A.n2B.n(n+1)C.n(n+1)/2D.n(n-1)/220．用散列函数求元素在散列表中的存储位置时，可能会

6、出现不同的关键字得到相同散列函数值的冲突现象。可用于解决上述问题的是()A.线性探测法B.除留余数法C.平方取中法D.折叠法21．22．在线性表的散列存储中，若用m表示散列表的长度，n表示待散列存储的元素的个数，则装填因子a等于（）。A．n/mB．m/nC．n/(n+m)D．m/(n+m)23．从一棵B_树删除元素的过程中，若最终引起树根结点的合并，则新树高度是（）。A．原树高度加1B．原树高度减1C．原树高度D．不确定24．向二叉搜索树中插入一个元素时，其时间复杂度大致为（　　）。Ａ.O（log2n）B.O(n)C.O(1)D.0(nlog2n)25．5阶B树

7、中，每个结点最多有（）个关键码。A．2B．3C．4D．526．对一棵二叉排序树采用中根遍历进行输出的数据一定是（　　）A.递增或递减序列B.递减序列C.无序序列D.递增序列27．一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，查找成功时的比较次数为（　　）A.1B.2C.4D.828．若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不超过()A.B.nC.D.n+129．闭散列表中由于散列到同一个地址而引起的“堆积”现象，是()A.由同义词之间发生冲突引起的B.由非同义词之间发生冲突引起

8、的C.由同义词之间或非同