资源描述：
《数据结构第九章习题课》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1.用二分（对半）查找表的元素的速度比用顺序法()A．必然快B.必然慢C.相等D.不能确定2.具有12个关键字的有序表，折半查找的平均查找长度（）A.3.1B.4C.2.5D.53．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用()查找法。A.分块查找B.顺序查找C.折半查找D.基于属性4．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是()A．（100，80，90，60，120，110，130）B.（100，120，110，130，80，60，90）C.（1
2、00，60，80，90，120，110，130）D.(100，80，60，90，120，130，110)5.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作()型调整以使其平衡。A.LLB.LRC.RLD.RR7.下面关于B和B+树的叙述中，不正确的是()A.B树和B+树都是平衡的多叉树。B.B树和B+树都可用于文件的索引结构。C.B树和B+树都能有效地支持顺序检索。D.B树和B+树都能有效地支持随机检索。8.m阶B-树是
3、一棵()A.m叉排序树B.m叉平衡排序树C.m-1叉平衡排序树D.m+1叉平衡排序树9.设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=keyMOD13,散列地址为1的链中有（）个记录。A．1B.2C.3D.410.下面关于哈希(Hash，杂凑)查找的说法正确的是()A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小B．除留余数法是所有哈希函数中最好的C．不存在特别好与坏的哈希函数，要视情况而定D．若
4、需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可11.若采用链地址法构造散列表，散列函数为H（key）=keyMOD17，则需(（1）)个链表。这些链的链首指针构成一个指针数组，数组的下标范围为(（2）)（1）A．17B.13C.16D.任意（2）A．0至17B.1至17C.0至16D.1至1612.设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则
5、放入的位置是()A．8B．3C．5D．913.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？()A．k-1次B.k次C.k+1次D.k（k+1）/2次14.将10个元素散列到100000个单元的哈希表中，则（）产生冲突。A.一定会B.一定不会C.仍可能会15.散列表的地址区间为0-17,散列函数为H(K)=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。（1）元素59存放在散列表中的地址是（
6、）。A．8B.9C.10D.11（2）存放元素59需要搜索的次数是（）。A．2B.3C.4D.516.在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为____。答：417．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为__________。答：6,9,11,1218.在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是__________答：51
7、9.在一棵m阶B-树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个数是__________;若在某结点中删除一个关键字而导致结点合并,则该结点中原有的关键字的个数是__________。答：m-1,「m/2ù-120、哈希表是通过将查找码按选定的__(1)__和__(2)__，把结点按查找码转换为地址进行存储的线性表。哈希方法的关键是_(3)__和__(4)__。一个好的哈希函数其转换地址应尽可能__(5)__，而且函数运算应尽可能__(6)__。答：(1)哈希函数(
8、2)解决冲突的方法(3)选择好的哈希函数(4)处理冲突的方法(5)均匀(6)简单20、哈希函数H（key）=key%p中，p值最好取__________。答：小于等于表长的最大素数或不包含小于20的质因子的合数21、对于长度为255的表，采用分块查找，每块的最佳长度为__________。答：1623.如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为__________。答：(n+1)/224.__________法构造的哈希函数
