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

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

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

A、快速排序

B、冒泡排序

C、直接选择排序

D、堆排序

2、具有n个结点的满二叉树，其叶子结点有（ ）个。

A、n/2

B、(n-1)/2

C、(n+1)/2

D、n/2-1

3、图中有关路径的定义是（ ）。

A、由不同顶点所形成的序列

B、由不同边所形成的序列

C、由顶点和相邻顶点序偶构成的边所形成的序列

D、上述定义都不对

4、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度和在给定值为x的结点后插入一个新结点的时间复杂度分别为（ ）。

A、O(1)，O(n)

B、O(n)，O(n)

C、O(1)，O(1)

D、O(n)，O(1)

1、试题答案：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。

2、试题答案：C

试题解析：

对任何一棵二叉树，若终端结点为n₀，度为2的结点为n₂，则n₀=n₂+1。满二叉树仅含有叶子结点和度为2的结点，因此n=n₀+n₂=2*n₀-1，解得n₀=(n+1)/2，故本题选C。

3、试题答案：C

试题解析：

选项A中，仅仅指出路径由不同顶点所构成的序列，但并没有明确说明这些顶点是如何连接起来的；选项B中，仅仅指出路径由不同边所构成的序列，但并没有明确说明这些边是连接哪些顶点的。因此，这两个选项都没有给出完整的路径定义。图论中，路径指的是图中从一个顶点到另一个顶点的一系列边构成的序列。在有向图中，路径由一系列有向边连接的顶点构成；在无向图中，路径由一系列无向边连接的顶点构成。路径的长度是指路径上所有边的权值之和。由于路径是由顶点和相邻顶点的边构成的，因此选项C描述了路径的定义是正确的。故本题选C。

4、试题答案：A

试题解析：

对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为O(1)，因为只需要将新结点插入到p之后，然后更新指针即可。而在给定值为x的结点后插入一个新结点的时间复杂度为O(n)，因为需要先遍历整个链表找到值为x的结点，然后再进行插入操作。故本题选A。