发布时间 : 星期四 文章数据结构考试试题库含答案解析更新完毕开始阅读41bd9befae45b307e87101f69e3143323868f5f5
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个得分点，每段话一个得分。
2. 请给出数据的逻辑结构的含义，并举例说明数据的逻辑结构通常有哪些。
数据的逻辑结构：指数据元素之间的逻辑关系。即用自然语言描述数据，它与数据的存储无关，是独立于计算机的，逻辑结构有四种。（一个得分点） 集合结构： 仅同属一个集合（结构名字个得分点、举例得分点） ?
线性结构: 一对一（1:1) （结构名字个得分点、举例得分点） ?
树 结 构: 一对多（1:n) （结构名字个得分点、举例得分点）
?
图 结 构: 多对多 (m:n) （结构名字个得分点、举例得分点）
?
评分标准：每段话一个得分点，总共5个得分点。
什么是数据的物理结构？有哪些物理结构？数据的物理结构与逻辑结构有什么区别与联系？
数据的物理结构：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。（一个得分点）
存储结构可分为4大类：顺序、链式、索引、散列。（共2个得分点，一个得分点） 区别：数据的逻辑结构属于用户视图，是面向问题的，数据的存储结构属于具体实现的视图，是面向计算机的。（一个得分点）
联系：一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构其处理的效率往往不同。（一个得分点）
评分标准：共5个得分点，按照每段话各自标注的得分点进行评分。
3. 求两个正整数 m，n 中的最大数MAX的算法
（1）若 m > n 则 max=m （2）若 m <= n 则 max=n
请根据上述算法解释一下算法的组成要素有哪些，分别是什么。 算法由操作、控制结构、数据结构3要素组成
操作包含：算术运算、关系比较、逻辑运算、数据传送（输入、输出、赋值）（一个得分点）
例子中有关系比较和赋值计算的操作。（一个得分点）
控制结构包含：顺序结构、选择结构、循环结构（一个得分点） 例子中有选择结构（一个得分点）
数据结构：算法操作的对象是数据，数据间的逻辑关系、数据的存储方式及处理方式就是数据结构。（一个得分点）