考研数据结构和计算机组成原理在线题库每日一练（二十四）

本文提供考研数据结构和计算机组成原理在线题库每日一练，以下为具体内容

2、若A中有1000个元素，如果仅要求选出其中最大的5个元素，则采用（）排序方法最省时间。

A、起泡排序

B、快速排序

C、简单选择排序

D、希尔排序

3、可以随机访问的存储器是（）。

A、光盘

B、磁带

C、主存

D、磁盘

4、当初始序列已按键值有序，则用简单选择排序算法对其进行排序，需要进行的比较次数为（）。

A、N²

B、N-1

C、N*log₂N

D、N*(N-1)/2

5、对同一待排序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是（）。

A、元素的移动次数

B、元素之间的比较次数

C、排序的总趟数

D、使用辅助空间的数量

2、试题答案：A

试题解析：

起泡排序（Bubble Sort）是一种基本的排序算法，它的基本思想是对于相邻的两个元素，如果它们的顺序错误，则交换它们的位置，直到没有再需要交换的元素为止。因此需要进行5趟起泡排序即可以选出其中最大的5个元素。最好情况下可能一趟起泡排序即可以选出其中最大的5个元素，因此起泡排序相较于简单选择排序会更好。故本题选A。

3、试题答案：C

试题解析：

RAM是一种随机存取存储器，其特点是存储器的任何一个存储单元的内容都可以随机存取，而且存取时间与存储单元的物理位置无关。计算机系统中的主存都采用这种随机存储器。故本题选C。

4、试题答案：D

试题解析：

简单选择排序的基本思路是在待排序的序列中选择最小的元素，将其与序列的第一个元素交换位置，然后在剩下的元素中选择最小的元素，将其与序列的第二个元素交换位置，以此类推，直到整个序列有序。当初始序列已按键值有序时，并不会影响比较次数。第i次选择最小元素时，不需要对前i-1个元素进行比较，只需比较第i个元素与后面的元素，这样每一次选择最小元素时只需比较n-i次，共需要比较1+2+...+n-1=(n-1)n/2次，即N(N-1)/2次比较。故本题选D。

5、试题答案：B

试题解析：

折半插入排序和直接插入排序都是插入排序的一种，其核心思想是将待排序列分为有序区和无序区，然后将无序区的元素插入到有序区的合适位置。两者不同的地方在于插入操作的实现方式。直接插入排序是在有序区内从后往前依次比较并移动元素，找到插入位置后进行插入操作。折半插入排序是在有序区内使用折半查找的方式找到插入位置，再将元素插入到合适的位置。折半插入排序通过二分查找找到插入位置，而直接插入排序则是逐个比较后找到插入位置，因此元素之间的比较次数不同。故本题选B。