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

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

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

A、 排序的总趟数

B、 元素的移动次数

C、 使用辅助空间的数量

D、 元素之间的比较次数

2、表长为1000的顺序存储的线性表，当在任何一个位置上插入一个元素的概率相等时，插入一个新元素所需移动元素的平均个数为（ ）。

A、1000

B、1001

C、500

D、499

3、下列说法中不正确的是（）。

A、无向图的极大连通子图称为连通分量

B、连通图的广度优先搜索中一般要采用队列来暂存刚访问过的结点

C、连通图的深度优先搜索中一般要采用栈来暂存刚访问过的结点

D、无向图的遍历不可采用广度优先搜索算法

4、在顺序存储的线性表（a1，a2，...，an）中，删除一个元素的平均移动次数为（）。

A、n/2

B、(n-1)/2

C、(n+1)/2

D、n

1、试题答案：D

试题解析：

【考点】本题考查折半插入排序和直接插入排序的异同。
【解析】直接插入排序的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。整个排序过程为进行n-1趟插入。折半插入排序是对插入排序算法的一种改进，插入排序算法过程就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。两种排序算法仅在将元素插入正确位置时选择的查找方法不同。因此二者排序的总趟数不变，都是n-1次，A错误。元素的移动次数取决于序列的初始状态，B错误。使用的辅助空间均为O(1)，C错误。由于直接插入排序在查找正确位置时选择了顺序查找，折半插入排序选择折半查找，二者比较次数可能不同，故本题选D。

2、试题答案：C

试题解析：

插入位置的范围是1~n+1。在第一个位置上插入一个元素需要移动1000个元素，在第二个位置上插入一个元素需要移动999个元素，以此类推，在第i个位置上插入一个元素需要移动1001-i个元素。因此，插入一个新元素所需移动元素的平均个数为((0+1000)×1001/2)/1001=500个。故本题选C。

3、试题答案：D

试题解析：

广度优先搜索（BFS）和深度优先搜索（DFS）是两种常见的无向图遍历算法，其中BFS通常使用队列来暂存已访问的节点，而DFS则通常使用栈来暂存已访问的节点。无向图可以采用BFS或DFS进行遍历。故本题选D。

4、试题答案：B

试题解析：

在顺序存储的线性表中，删除一个元素需要将该元素之后的所有元素向前移动一位。设删除的元素在位置i（1≤i≤n），则移动的次数为n-i。对于任意的i，该元素被删除的概率为1/n，因此平均移动次数为((n-1)+(n-2)+...+1+0)/n=(n-1)/2。故本题选B。