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

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

1、快速排序在（ ）情况下最不利于发挥其长处。

A、被排序的数据量太大

B、被排序数据中含有多个相同的关键字.

C、被排序的数据完全无序

D、被排序的数据已基本有序

2、请指出在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键码12需做多少次关键码比较（ ）。

A、2

B、3

C、5

D、4

3、不带头结点的单链表head为空的判定条件是（ ）。

A、

B、

C、

D、

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

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

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

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

D、上述定义都不对

5、如对图2所示的有向图进行拓扑排序，得到的拓扑序列可能是（ ）。

A、3，1，2，4，5，6

B、3，1，2，4，6，5

C、3，1，4，2，5，6

D、3，1，4，2，6，5

1、试题答案：D

试题解析：

快速排序的基本思想是通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后再按此方法对这两部分记录进行排序，以达到整个序列有序的目的。在被排序数据已经基本有序的情况下，每次划分时都只能将序列分为一个较小的子序列和一个较大的子序列，导致递归树的深度增加，时间复杂度也会增加，使得快速排序的效率大大降低。因此，对于已经基本有序的数据，选择其他排序算法可能更加适合。故本题选D。

2、试题答案：D

试题解析：

mid=(0+10)/2=5，关键码15>12，在15的左半边查找；mid=(0+4)/2=2，7<12，在7的右半边查找；mid=(3+4)/2=3，10<12，在10的右半边查找；mid=(4+4)/2=4，14>12，查找失败。关键码的比较次数为4，故本题选D。

3、试题答案：A

试题解析：

不带头结点的单链表head为空，表示该链表中没有任何节点，即链表为空。因此，判定该链表是否为空需要判断链表的头指针head是否为NULL。故本题选A。

4、试题答案：C

试题解析：

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

5、试题答案：D

试题解析：

拓扑排序（Topological Sorting）是对有向无环图（DAG）进行排序的一种算法。它将有向无环图中的结点按照一定的顺序排列，使得图中任意一条有向边所指向的结点都排在它自己前面。拓扑排序可以用来解决任务调度、依赖关系等问题。故本题选D。