数据结构与算法--PTA第七章习题

数据结构与算法--PTA第七章习题答案

一、判断

1. 将M个元素存入用长度为S的数组表示的散列表，则该表的装填因子为M/S。T
2. 即使把2个元素散列到有100个单元的表中，仍然有可能发生冲突。T
3. 将 10 个元素散列到 100 000 个单元的哈希表中，一定不会产生冲突。F

二、单选

1. 已知一个长度为16的顺序表L，其元素按关键字有序排列。若采用二分查找法查找一个L中不存在的元素，则关键字的比较次数最多是：B

   A.4

   B.5

   C.6

   D.7

2. 用二分查找从100个有序整数中查找某数，最坏情况下需要比较的次数是：A

   A.7

   B.10

   C.50

   D.99

3. 在下列查找的方法中，平均查找长度与结点个数无关的查找方法是：C

   A.顺序查找

   B.二分法

   C.利用哈希（散列）表

   D.利用二叉搜索树

4. 将10个元素散列到100000个单元的哈希表中，是否一定产生冲突？B

   A.一定会

   B.可能会

   C.一定不会

   D.有万分之一的可能会

5. 设散列表的地址区间为[0,16]，散列函数为H(Key)=Key%17。采用线性探测法处理冲突，并将关键字序列{ 26，25，72，38，8，18，59 }依次存储到散列表中。元素59存放在散列表中的地址是：D

   A.8

   B.9

   C.10

   D.11

6. 从一个具有N个结点的单链表中查找其值等于X的结点时，在查找成功的情况下，需平均比较多少个结点？D

   A.N/2

   B.N

   C.(N−1)/2

   D.(N+1)/2

7. 对一个长度为 10 的排好序的表用二分法查找，若查找不成功，至少需要比较的次数是（）。B

   A.4

   B.3

   C.5

   D.6