数据结构习题第9章

《数据结构习题第9章》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第9章查找一、选择题1.在表长为n的链表中进行顺序查找，等概率情况下查找成功的ASL*（）。A.n;B.（n+l）/2C.V^+l;D.Iog2（n+1）-12.折半查找有序表（4，6，10，12，20，30，50，70，88，100）,若查找元素58,则它将依次与表中（）比较大小，查找结果是失败。A.20，70，30，50B.30，70，50C.20,70,50D.30,88,503.对22个记录的有序表作折半查找，查找失败时，至少需要比较（）次关键字。A.3B.4C.5D.64.链表适用于（）查找。A.顺序B.折半C.顺序查找和折半D.随机5.设哈希表

2、长为14,哈希函数是H（key）=key%ll,表中己有数据的关键字为15,38,61,84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是（）。A.1B.4C.6D.96.适用于折半查找的表的存储方式及元素排列要求为（）。A.链接方式存储，元素无序B.链接方式存储，元素有序C.顺序方式存储，元素无序D.顺序方式存储，元素有序7.对长度为3的顺序表做顺序查找，若查找第1个元素的概率为1/2.，查找第2个元素的概率为1/3,查找第3个元素的概率为1/6,则成功查找表中任一元素的平均查找长度为（）。A.5/3B.6/3C.7

3、/3D.8/38.一个哈希表中有n个元素，用哈希法进行查找的平均查找长度为（）。A.0（1）B.O（n）C.O（log2n）D.O（n2）9.设哈希表的长度为m，采用除留余数法：H（key）=key%p,一般选择p为（）。A.等于mB.大于m的最小质数C.小于或等于m的最大质数D.小于或等于m的最大合数10.哈希表的平均査找长度（）。A.与处理冲突的方法有关而与表的长度无关B.与处理冲突的方法有关且与表的长度有关C.与处理冲突的方法无关而与表的长度有关D.与处理冲突的方法无关且与表的K:度无关二、填空题1.在数据的存放无规律的线性表中进行检索的最佳方法是1

4、.折半查找有序表（4,6，12,20,28,38,50,70,88,100）,若查找表中元素20,它将依次与表中元素比较大小。1.线性有序表（apa2，a3，…，a256）是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索次。设有100个结点，用二分法查找时，最大比较次数是。2.在各种查找方法中，平均查找长度与记录个数n无关的查找方法是。3.哈希法存储的基本思想是由决定数据的存储地址。4.有一个表长为m的散列表，初始状态为空，现将n（n

5、n个关键码的散列地址都相同，则探测的总次数是o三、判断题1.有n个数存放在一维数组中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。（）2.折半查找的效率肯定高于顺序查找。（）3.在二叉排序树屮插入一个新结点，该新结点肯定是叶子结点。（）4.一棵二叉排序树的先序遍历序列正好是待排序数据的非递减序列。（）5.n个结点的二叉排序树有多种，其中树的高度最小的二叉排序树是最佳的。（）6.哈希函数的选择原则之一是函数比较简单且能在较短时间内计算出结果。（）7.在哈希检索中，“比较”操作一般是不可避免的。（）8.哈希函数越复杂越好，因为这样随机性好，冲

6、突概率小。（）四、计算题1.画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均査找长度。2.在一棵空的二叉排序树中依次插入关键字序列为12,7，17,11，16,2，13,9,21，请両出所得到的二叉排序树。3.已知长度为12的表：（Jan,Feb,Mar,Apr,May，June,July,Aug,Sep,Oct,Nov,Dec）（1）试按表屮元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。（2）若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进

7、行折半查找时查找成功的平均查找长度。（3）按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下査找成功的平均查找长度。4.假定对有序表：（3,4，5，7，24，30，42，54，63,72,87,95）进行折半查找，回答下列问题：（1）画出描述折半査找过程的判定树；（2）若查找元素54,需依次与哪些元素比较？(3)若查找元素90,需依次与哪些元素比较？(4)假定每个元素的查找概率相等，求查找成功时的平均查找长度。1.选取散列函数H(key)=(3*key)%11,用线性探测法处理冲突，对下列关键码序列｛22,41，53,8,46,30，1,31，6

8、6｝构造一个哈希地址空间为0〜10,表长为11的哈希表，。五、算法