集合(散列、搜索树、折半)习题

《集合(散列、搜索树、折半)习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、选择题：1、对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为(A)【南京理工大学1998一、7（2分）】A．（N+1）/2B.N/2C.ND.[（1+N）*N]/22、下面关于二分查找的叙述正确的是(D)【南京理工大学1996一、3（2分）】A.表必须有序，表可以顺序方式存储，也可以链表方式存储C.表必须有序，而且只能从小到大排列B.表必须有序且表中数据必须是整型，实型或字符型D.表必须有序，且表只能以顺序方式存储3、适用于折半查找的表的存储方式及元素排列要求为(D)【南京理工大学1997一、6（2分）】A．链接方式存储，元素无序B．链接方式存储，元素有序C．顺序

2、方式存储，元素无序D．顺序方式存储，元素有序4、当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度(C)A．必定快B.不一定C.在大部分情况下要快D.取决于表递增还是递减【南京理工大学1997一、7（2分）】5、具有12个关键字的有序表，折半查找的平均查找长度（A）【中山大学1998二、10（2分）】A.3.1B.4C.2.5D.56、折半查找的时间复杂性为（D）【中山大学1999一、15】A.O（n2）B.O（n）C.O（nlogn）D.O（logn）7、散列函数有一个共同的性质，即函数值应当以(D)取其值域的每个值。A.最大概率B.最小概率

3、C.平均概率D.同等概率8、二叉查找树的查找效率与二叉树的(（1）C)有关,在(（2）C)时其查找效率最低【武汉交通科技大学1996一、2(4分)】(1):A.高度B.结点的多少C.树型D.结点的位置(2):A.结点太多B.完全二叉树C.呈单枝树D.结点太复杂。9、分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是(C)【合肥工业大学2000一、4（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，11

4、0)10、下面关于哈希(Hash，杂凑)查找的说法正确的是(C)【南京理工大学1998一、10（2分）】A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小B．除留余数法是所有哈希函数中最好的C．不存在特别好与坏的哈希函数，要视情况而定D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可11、设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，8共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是(D)【南京理工大学2001一、15（1.5分）】A．8B．3C．5D．9二次探测：h2

5、i-1(x)=(h(x)+i2)%B;h2i+1(x)=(h(x)-i2)%B;12、假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？(D)A．k-1次B.k次C.k+1次D.k（k+1）/2次13、散列表的地址区间为0-17,散列函数为H(K)=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。【北方交通大学2001】（1）元素59存放在散列表中的地址是（D）。A．8B.9C.10D.11（2）存放元素59需要搜索的次数是（C）。A．2B.3C.4D.514.将10个元素散列到1000

6、00个单元的哈希表中，则（C）产生冲突。【北京邮电大学2001一、4（2分）】A.一定会B.一定不会C.仍可能会二、判断题：1．在散列检索中，“比较”操作一般也是不可避免的。(√)【华南理工大学2001一、4（1分）】2．散列函数越复杂越好，因为这样随机性好，冲突概率小.(×)【南京理工大学1997二、5（2分）】3．哈希函数的选取平方取中法最好。(×)【青岛大学2000四、7（1分）】4．Hash表的平均查找长度与处理冲突的方法无关。（×）【南京航空航天大学1997一、9（1分）】5、顺序查找法适用于存储结构为顺序或链接存储的线性表。（√）【山东大学2001一、1(1分)】6.折半查找法

7、的查找速度一定比顺序查找法快。（×）【山东大学2001一、8(1分)】7．对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。（√）8、在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。（×）【上海海运学院1999一、8（1分）】9、完全二叉树肯定是平衡二叉树。（×）【南京航空航天大学1996六、5（1分）