数据结构考试题库含答案(4)

13. 已知图的邻接表下图所示，则从顶点0出发按广度优先遍历的结果是（ ），

按深度优先遍历的结果是（ ）。

A．0 1 3 2 B．0 2 3 1 C．0 3 2 1 D．0 1 2 3

14. 当在一个有序的顺序表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（ C ）。

A．必定快 B．不一定

C．在大部分情况下要快 D．取决于表递增还是递减

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

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

第八章 查找

1. 顺序查找法适合于存储结构为（B ）的线性表。

A．散列存储 B．顺序存储或链式存储 C．压缩存储 D．索引存储

2. 在查找过程中，若同时还要增、删工作，这种查找称为（ B ）。

A、 静态查找 B、 动态查找 C、 内查找 D、 外查找

3. 索引顺序表的特点是顺序表中的数据（ A ）。

A、 有序 B、 无序 C、 块间有序 D、 散列

4. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为

（C）

A、 n

B、n/2 C、(n+1)/2

D、(n-1)/2

5. *将10个元素散列到1000000个单元的哈希表，则（ C ）产生冲突。

A、 一定会 B、一定不会 C、仍可能会 D、以上都不对

6. *散列表的地址区间为0~16，散列函数H(k)=k，采用线性探测法解决地

址冲突，将关键字26、25、72、38、1、18、59依次存储到散列表中。元素59存放在散列表中的地址为（ A ）

A、 8 B、 9 C、 10 D、 11

7. 设有序表的关键字序列为{1,3,9,12,32,41,45,62,75,77,82,95,100}，当采用二

分查找法查找值为82的节点时，经（ C ）次比较后查找成功。

A、 1

B、 2 C、 3

D、 4

8. 设有100个元素，用折半查找法进行查找时，最大、最小比较次数分别时

（ A ）

A、 7,1 B、6,1 C、5,1 D、8,1

第九章 排序

1. 对n个不同的记录按排序码值从小到大次序重新排列，用冒泡(起泡)排序方

法，初始序列在 （A ） 情况下，与排序码值总比较次数最少。

A．按排序码值从小到大排列 B．按排序码值从大到小排列 C．随机排列(完全无序) D．基本按排序码值升序排列

2. 对n个不同的记录按排序码值从小到大次序重新排列，用冒泡(起泡)排序方

法，在 （B） 情况下，与排序码值总比较次数最多。

A．按排序码值从小到大排列 B．按排序码值从大到小排列 C．随机排列(完全无序) D．基本按排序码值升序排列

3. 对n个不同的记录按排序码值从小到大次序重新排列，用直接插入排序方法，

初始序列在 （A） 情况下，与排序码值总比较次数最少。

A．按排序码值从小到大排列 B．按排序码值从大到小排列 C．随机排列(完全无序) D．基本按排序码值升序排列

4. 对n个不同的记录按排序码值从小到大次序重新排列，用直接插入排序方法，

初始序列在 （B） 情况下，与排序码值总比较次数最多。

A．按排序码值从小到大排列 B．按排序码值从大到小排列 C．随机排列(完全无序) D．基本按排序码值升序排列

5. 对n个不同的记录按排序码值从小到大次序重新排列，用快速排序方法在

（C） 情况下，与排序码值总比较次数最少。

A．按排序码值从小到大排列 B．按排序码值从大到小排列 C．随机排列(完全无序) D．基本按排序码值升序排列

6. 对n个不同的记录按排序码值从小到大次序重新排列，用快速排序方法，在

（A） 情况下与排序码值总比较次数最多。

A．按排序码值从小到大排列 B．按排序码值从大到小排列 C．随机排列(完全无序) D．基本按排序码值升序排列

7. 用冒泡排序方法对n个记录按排序码值从小到大排序时，当初始序列是按排

序码值从大到小排列时，与码值总比较次数是 （D） 。

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

8. 下列排序方法中，与排序码值总比较次数与待排序记录的初始序列排列状态

无关的是 (D) 。

A．直接插入排序 B．冒泡排序 C．快速排序 D．直接选择排序

9. 将6个不同的整数进行排序，至少需要比较 (A) 次。

A．5 B．6 C．15 D．21

10. 将6个不同的整数进行排序，至多需要比较 (C) 次。

A．5 B．6 C．15 D．21

11. *若需要时间复杂度在O(nlog2n)内，对整数数组进行排序，且要求排序方法

是稳定的，则可选择的排序方法是 (B) 。

A．快速排序 B．归并排序 C．堆排序 D．直接插入排序

12. 当待排序的整数是有序序列时，采用 (B) 方法比较好，其时间复杂度为

O(n)。

A．快速排序 B．冒泡排序 C．归并排序 D．直接选择排序

13. 当待排序的整数是有序序列时，采用 （A）方法比较差，达到最坏情况下

时间复杂度为O(n2)。

A．快速排序 B．冒泡排序 C．归并排序 D．直接选择排序

14. 当待排序的整数是有序序列时，无论待排序序列排列是否有序，采用 （D）

方法的时间复杂度都是O(n2)。

A．快速排序 B．冒泡排序 C．归并排序 D．直接选择排序

15. *堆是一种 (B) 排序。

A．插入 B．选择 C．交换 D．归并

16. *若一组记录的排序码值序列为{40，80，50，30，60，70}，利用堆排序方

法进行排序，初建的大顶堆是 (D ) 。

A．80，40，50，30，60，70 B．80，70，60，50，40，30 C．80，70，50，40，30，60 D．80，60，70，30，40，50

17. 若一组记录的排序码值序列为{50，80，30，40，70，60}利用快速排序方法，

以第一个记录为基准，得到一趟快速排序的结果为（B ） 。

A．30，40，50，60，70，80 B．40，30，50，80，70，60 C．50，30，40，70，60，80 D．40，50，30，70，60，80

18. *下列几种排序方法中要求辅助空间最大的是（C ） 。

A．堆排序 B．直接选择排序 C．归并排序 D．快速排序

19. 已知A[m]中每个数组元素距其最终位置不远，采用下列 (A) 排序方法最

节省时间。

A．直接插入 B．堆 C．快速 D．直接选择

20. *设有10000个互不相等的无序整数，若仅要求找出其中前10个最大整数，

最好采用 （B） 排序方法。

A．归并 B．堆 C．快速 D．直接选择

21. *在下列排序方法中不需要对排序码值进行比较就能进行排序的是 （A） 。

A：基数排序 B．快速排序 C．直接插入排序 D．堆排序

22. *给定排序码值序列为{F，B，J，C，E …… 此处隐藏：2379字，全部文档内容请下载后查看。喜欢就下载吧 ……