查找和排序

习题习题习题习题习题习题习题习题习题

第 9 章 查找

一、单选题

1、静态查找表与动态查找表两者的根本差别在于A、逻辑结构不同 B、 存储实现不同

C、施加的操作不同 D、 数据元素的类型不同

2、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为Ａ、n B、n/2 C、(n+1)/2 D、(n-1)/2

。 。 3、对线性表进行二分查找时，要求线性表必须A、以顺序方式存储 B、以链式方式存储

C、以顺序方式存储，且结点按关键字有序排序

D、以链式方式存储，且结点按关键字有序排序

4、在表长为n的顺序表中进行顺序查找，在查找不成功时，与关键字比较的次数为

A、n B、1 C、 n+1 D、n-1

5、对于有序表（2，5，7，11，22，45，49，62，71，77，90，93，120），折半查找值为90的结点时，经过 比较后查找成功。

A、 1 B、 2 C、4 D、5

6.快速排序在最坏情况下的时间复杂度是( )。

A、O(log2n) B、O(nlog2n) C、O(n2) D、O(n3)

7、如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用查找方法。

A、分块 B、顺序 C、二分 D、散列

8、有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情 况下查找成功所需的平均比较次数为 。

A、35／12 B、37／12 C、39／12 D、43／12

9、当采用分块查找时，数据的组织方式为A、数据分为若干块，每块内数据有序

B、数据分为若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）