数据结构第九章习题.ppt

第九章习题一、选择题

1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为()。【北京航空航天大学2000一、8（2分）】

A．(n-1)/2B.n/2C.(n+1)/2D.n

2.下面关于二分查找的叙述正确的是()【南京理工大学1996一、3（2分）】

A.表必须有序，表可以顺序方式存储，也可以链表方式存储B.表必须有序且表中数据必须是整型，实型或字符型C.表必须有序，而且只能从小到大排列

D.表必须有序，且表只能以顺序方式存储

√√√具有12个关键字的有序表，折半查找的平均查找长度（）【中山大学1998二、10（2分）】

A.3.1B.4C.2.5D.5折半查找的时间复杂性为（）【中山大学1999一、15】

A.O（n2）B.O（n）C.O（nlogn）D.O（logn）√5．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是()【合肥工业大学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，110)

√6.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作()型调整以使其平衡。【合肥工业大学2001一、4（2分）】

A.LLB.LRC.RLD.RR

7．下列关于m阶B-树的说法错误的是()【南京理工大学1997一、9（2分）】

A．根结点至多有m棵子树B．所有叶子都在同一层次上

C.非叶结点至少有m/2(m为偶数)或m/2+1（m为奇数）棵子树D.根结点中的数据是有序的

√√8.下面关于m阶B树说法正确的是()【南京理工大学1999一、5（2分）】

①每个结点至少有两棵非空子树；②树中每个结点至多有m一1个关键字;

③所有叶子在同一层上;④当插入一个数据项引起B树结点分裂后，树长高一层。

A．①②③B.②③C.②③④D.③

9.下面关于B和B+树的叙述中，不正确的是()【北方交通大学2001一、17（2分）】

A.B树和B+树都是平衡的多叉树。B.B树和B+树都可用于文件的索引结构。

C.B树和B+树都能有效地支持顺序检索。D.B树和B+树都能有效地支持随机检索。

10.m阶B-树是一棵()【北京邮电大学2000二、2（20/8分）】

A.m叉排序树B.m叉平衡排序树C.m-1叉平衡排序树D.m+1叉平衡排序树

√√√11.m路B+树是一棵(（1）)，其结点中关键字最多为(（2）)个，最少(（3）)个。【中科院计算机1999一、5】

A.m路平衡查找树B.m路平衡索引树D.m路键树E.m-1F.mG.m+1H.┌m/2┐-1I.┌m/2┐J.┌m/2┐+1

12.下面关于哈希(Hash，杂凑)查找的说法正确的是()【南京理工大学1998一、10（2分）】

A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小

B．除留余数法是所有哈希函数中最好的

C．不存在特别好与坏的哈希函数，要视情况而定

D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可

√BFI13.关于杂凑查找说法不正确的有几个()【南京理工大学2000一、16（1.5分）】

（1）采用链地址法解决冲突时，查找一个元素的时间是相同的

（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的

（3）用链地址法解决冲突易引起聚集现象

（4）再哈希法不易产生聚集

A.1B.2C.3D.4

14.设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是()【南京理工大学2001一、15（1.5分）】

A．8B．3C．5D．9

√√15.假定有k个关键字互为同义词，