考研数据结构在线题库每日一练（六十二）

本文提供考研数据结构在线题库每日一练，以下为具体内容

1、求整数n （n≥0）阶乘的算法如下，其时间复杂度是

A、 O（log₂n）

B、 O（n）

C、 O（nlog₂n）

D、 O（n²）

2、下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(n*log2n)的是（ ）。

A、快速排序

B、冒泡排序

C、直接选择排序

D、堆排序

3、以下排序算法中，不稳定的是（ ）。

A、直接插入排序

B、冒泡排序

C、堆排序

D、归并排序

4、算法指的是（ ）。

A、计算机程序

B、解决问题的计算方法

C、排序算法

D、解决问题的有限运算序列

5、向一棵m阶B-树进行关键字插入，当结点的关键字数目在插入之前为（ ）时，插入关键字时需要分裂该结点。

A、m-1

B、m-2

C、m

D、m+1

1、试题答案：B

试题解析：

【考点】本题考查时间复杂度的计算。
【解析】上述算法为递归算法。由程序段可以分析，当n<=1时，函数调用1次；当n>1时，函数的调用次数与n的大小有关，函数会调用n-1次，而乘法形式出现的n不影响调用次数，可以看做fact(n-1)的系数。根据上述程序该递归算法的时间复杂度分两部分讨论，当n<=1时，时间复杂度为O(1)；当n>1时，时间复杂度为T(n-1)+1。根据时间复杂度的运算规则，上述程序的时间复杂度为O(n)，故本题选B。

2、试题答案：D

试题解析：

对于A，快速排序的时间复杂度受数据初始状态影响，平均情况下时间复杂度为O(n*log₂n)，在最坏情况下（初始序列完全有序）的时间复杂度为O(n²)。对于B，冒泡排序的时间复杂度受数据初始状态影响，平均情况下时间复杂度为O(n²)，在最好情况下（初始序列完全有序）时间复杂度为O(n)。对于C，直接选择排序的操作为：通过n-i次关键字间的比较，从n-i+1个记录中选择出关键字最小的记录，并和第i个记录交换。其时间复杂度不受序列初始状态影响，恒为O(n²)。堆排序是利用堆这种数据结构而设计的排序算法，堆排序是一种选择排序，它的时间复杂度不受数据初始状态影响，最好最坏情况下时间复杂度都是O(n*log₂n)。故本题选D。

3、试题答案：C

试题解析：

由下表知，插入排序、冒泡排序、归并排序都属于稳定的排序算法，而堆排序是不稳定的排序算法。故本题选C。

4、试题答案：D

试题解析：

算法是指解题方案的准确而完整的描述。算法不等于程序，也不等于计算方法，更不是排序算法。故本题选D。

5、试题答案：A

试题解析：

在m阶B-树中，每个结点最多有m-1个关键字，每个结点最多有m个子节点。当要向一个结点插入关键字时，如果该结点的关键字数目小于m-1，则可以直接将关键字插入该结点中。但如果该结点已经有了m个关键字，则必须将该结点分裂成两个结点，同时将一个关键字上推到该结点的父节点中，以保证父节点的关键字数目不超过m-1。因此，当一个结点的关键字数目为m-1时，插入一个新的关键字需要进行结点的分裂操作。故本题选A。