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，A，I，D，C，H}，对其按字母的字
典序列的次序进行排列，希尔(Shell)排序的第一趟(d1=5)结果应为（D ）。
A．{B，F，C，J，A，E，D，I，C，H} B．{C，B，D，A，E，F，I，C，J，H} C．{B，F，C，E，A，I，D，C，H，J} D．{A，B，D，C，E，F，I，J，C，H}
23. 给定排序码值序列为{F，B，J，C，E，A，I，D，C，H}，对其按字母的字典序列的次序进行排列，冒泡排序(大数下沉)的第一趟排序结果应为（C ）。
A．{B，F，C，J，A，E，D，I，C，H} B．{C，B，D，A，E，F，I，C，J，H} C．{B，F，C，E，A，I，D，C，H，J} D．{A，B，D，C，E，F，I，J，C，H}
24. 给定排序码值序列为{F，B，J，C，E，A，I，D，C，H}，对其按字母的字典
序列的次序进行排列，快速排序的第一趟排序结果为（B ）。
A．{B，F，C，J，A，E，D，I，C，H} B．{C，B，D，A，E，F，I，C，J，H} C．{B，F，C，E，A，I，D，C，H，J} D．{A，B，D，C，E，F，I，J，C，H}
25. *给定排序码值序列为{F，B，J，C，E，A，I，D，C，H}，对其按字母的字典序列的次序进行排列，二路归并排序的第一趟排序结果是（A ）。
A．{B，F，C，J，A，E，D，I，C，H} B．{C，B，D，A，E，F，I，C，J，H} C．{B，F，C，E，A，I，D，C，H，J} D．{A，B，D，C，E，F，I，J，C，H}
简答题
第一章绪论
1. 请分别给出数据、数据对象、数据元素、数据项的含义，并说明四者的关系。
数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并能被计算机程序处理的符号的总称。（一个得分点）
数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，相当于表中的一条记录。（一个得分点）
数据项：相当于记录的“域”, 是数据的不可分割的最小单位,如学号（一个得分点）
数据对象：性质相同的数据元素的集合，是数据的一个子集.例如: 同一个班的所有学生记录集合。（一个得分点）
关系：包含关系：数据泛指所有。数据对象是数据的一个子集，由数据元素组成，
数据元素是由数据项组成。（一个得分点） 评分标准，总共5个得分点，每段话一个得分。
数据结构考试试题库含答案解析
