贵州统招专升本《数据结构（C语言版第2版）》课后习题严蔚敏著第七章习题及答案

                              第七章课后习题

（1）对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）。

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

答案：C

解释：总查找次数N=1+2+3+…+n=n(n+1)/2，则平均查找长度为N/n=(n+1)/2

（2）适用于折半查找的表的存储方式及元素排列要求为（ ）。

A．链接方式存储，元素无序 B．链接方式存储，元素有序

C．顺序方式存储，元素无序 D．顺序方式存储，元素有序

答案：D

解释：折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

（3）如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用( )查找法。

A．顺序查找 B．折半查找

C．分块查找 D．哈希查找

答案：C

解释：分块查找的优点是：在表中插入和删除数据元素时，只要找到该元素对应的块，就可以在该块内进行插入和删除运算。由于块内是无序的，故插入和删除比较容易，无需进行大量移动。如果线性表既要快速查找又经常动态变化，则可采用分块查找。

（4）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（ ）比较大小，查找结果是失败。

A．20，70，30，50 B．30，88，70，50

C．20，50 D．30，88，50

答案：A

解释：表中共10个元素，第一次取(1+10)/2=5，与第五个元素20比较，58大于20，再取(6+10)/2=8，与第八个元素70比较，依次类推再与30、50比较，最终查找失败。